Регистрация Войти
Рейтинг:3
jacobi_matrix avatar Crypto

Однородные и неоднородные ППТ

флаг in
jacobi_matrix

Во время чтения бумаги

Я наткнулся на случай, в котором нужно было указать, предполагают ли авторы однородных или неоднородных нападающих. Насколько я знаю, неоднородные PPT в основном представляют собой последовательность PPT, поэтому $\mathcal{A}=\{\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}_n\}$, а на входе $х$ размера $|х| = \лямбда$, $\mathcal{A}_\lambda$ называется. Почему эта модель "сильнее" униформы? Не удалось объявить злоумышленника $\mathcal{А}$ просто встроить всех остальных злоумышленников в свое описание и вызвать подходящего? Есть ли проблемы, которые мы знаем, как решить в однородной модели, но не можем (если не с более слабыми гарантиями) в неоднородной модели?

79
1 + 0
Рейтинг:1
Mark avatar Crypto
флаг ng
Mark

Рассмотрим унарное перечисление всех машин Тьюринга, например. машина $ млн $ представлен $1^{\lambda_M}$ для некоторого уникального целого числа $\лямбда_M$. Проблема остановки невычислима даже в таком «разреженном» представлении. Но он неравномерно вычислим, так как каждая машина Тьюринга $ млн $ либо останавливается, либо нет, и мы можем «жестко закодировать» это решение в каждой машине Тьюринга. $А_{\лямбда_М}$.

Если бы мы могли «равномерно генерировать» $A_i$, то есть эффективно генерировать их исключительно из описания $я$, вы были бы правы. В приведенном выше примере вы не можете, так как не знаете, каждая ли машина Тьюринга $ млн $ останавливается.

0 + 5
флаг us
Mikero
Еще один способ увидеть, что неоднородные алгоритмы могут делать то, чего не могут однородные алгоритмы: существует бесчисленное множество неоднородных алгоритмов, но счетно много однородных алгоритмов.
1
Ответить
jacobi_matrix avatar
флаг in
jacobi_matrix
Спасибо за ответ. Мне было интересно, знаем ли мы практические проблемы, которые становятся проще в неоднородной модели. Перефразируя, как схема шифрования/обязательства/подписи... может предложить определенный уровень безопасности, когда мы предполагаем однородных злоумышленников, но более низкие уровни безопасности против неоднородных злоумышленников, если мы можем построить однородного злоумышленника, жестко закодировав других в свои собственное описание (и при этом иметь полиномиальный размер описания)
0
Ответить
Mark avatar
флаг ng
Mark
@jacobi_matrix См. раздел 4 [еще один взгляд на герметичность 2] (https://eprint.iacr.org/2016/360.pdf) для обсуждения предположений о неравномерной твердости. Стоит отметить, что несколько родственное понятие атак с «предварительной обработкой» (где можно получить конкретный совет) имеет ряд примеров, когда они помогают (и могут привести к практическим атакам), например [атака затора]( https://en.wikipedia.org/wiki/Logjam_(computer_security)), или многие проблемы в криптографии на основе решетки (хотя большинство криптосистем с решеткой каждый раз генерируют новые экземпляры, ограничивая опасность предварительного вычисления).
1
Ответить
Mark avatar
флаг ng
Mark
@jacobi_matrix проблема в том, что вы не можете построить единого противника, жестко закодировав другие в его описании, поскольку генерация произвольного $A_i$ может быть неэффективно вычислима (или даже вычислима вообще, например, «разреженная проблема остановки» неоднородный алгоритм, приведенный в моем ответе). Более того, вы не можете просто «хранить» их все в едином противнике, так как у единого противника было бы слишком большое описание.
1
Ответить
jacobi_matrix avatar
флаг in
jacobi_matrix
Идеальный! Раздел, на который вы ссылаетесь, и пример атаки на затор действительно помогли. Проблема заключалась в том, что я думал (очевидно, ошибочно), что строка совета должна быть самим размером ввода (например, закодирована в унарном коде). Еще раз спасибо .
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.