прямолинейная симуляция

11

Кто-нибудь знает какой-либо хороший справочник по значению симуляции прямолинейности? В настоящее время я глубоко знаком с универсальной средой составления (UC) Canetti, но я не могу найти какой-либо хороший справочник по значению прямолинейного моделирования. Любая помощь приветствуется.

Ясир Собхдел
источник

Ответы:

10

Здесь «прямая линия» противопоставляется «перемотке». Симулятор является «прямолинейным», если он не «перематывает» сторону, для которой он симулирует.

Например, в протоколе с нулевым знанием симулятор обычно перематывает «верификатор». В прямолинейном смысле этого перематывания не происходит.

Впервые я увидел термин «симулятор прямой линии» в статье Рафаэля Пасс (« Об отрицательности в моделях Common Reference String и Random Oracle». (CRYPTO'03) ) и M.Sc. дипломная работа ( Альтернативные варианты доказательств с нулевым знанием ).

Редактировать: я нашел более раннюю статью: « Параллельное нулевое знание: уменьшение потребности в ограничениях по времени» от Синтии Дворк и Амит Сахай, которая датируется 1998 годом. Дополнительные сведения см. В комментарии Алона Розена ниже.

М.С. Дусти
источник
Я не знаю термина «симулятор прямой линии», но мне кажется, что «прямая линия» контрастирует с «ветвлением», аналогично линейной временной зависимости от временной логики ветвления и эквивалентности трассы и эквивалентности бисимуляции (ветвления). Есть что-нибудь к этому?
Дэйв Кларк
Ну, я так не думаю. Я нашел другую ссылку, которая соответствует моему определению.
MS Dousti
Объяснение Садека такое же, как и в любом контексте, в котором я слышал используемые термины. Вот некоторые лекционные заметки Нью-Йоркского университета в классе Adv Crypto прошлого года, в которых обсуждается эта тема; в частности, см. п.8.
Даниэль Апон,
Детерминированный звучит как возможный синоним.
Дэйв Кларк
5
Более раннее использование концепции симулируемости прямой линии (хотя, возможно, и не под этой терминологией) можно найти в: (1) Ран Канетти, Одед Голдрайх, Шафи Голдвассер, Сильвио Микали: Сбрасываемое знание с нуля (расширенная аннотация). STOC 2000: 235-244 и (2) Ран Канетти, Марк Фишлин: Универсально составимые обязательства. КРИПТО 2001: 19-40. Понятие появляется в определении UC, потому что невозможно перемотать «среду». Ранее он возник в другом контексте при одновременном нулевом знании, где симулятор перемотки может столкнуться с проблемами.
Алон Розен
3

Не существует формального определения того, что значит быть симулятором прямой линии. Это только интуитивная идея, которую можно использовать для неформального описания вещей. Я очень скептически отношусь к тому, можно ли вообще определить, что значит не перематывать машину. Действительно, перемотка машины сама по себе является неформальным термином! Что мы на самом деле имеем в виду, перематывая машину, так это то, что мы можем исследовать множество возможных путей выполнения машины из данного состояния. Формальные аргументы основаны на количестве таких казней, которые нам нужно изучить, прежде чем мы сможем получить люк или другую информацию, которая нам нужна для дальнейшего продолжения нашего доказательства.


источник