Односторонние функции против совершенно обязательных обязательств

10

Если OWF существуют, то возможна статистически обязательная фиксация битов. [1]

Известно ли, что если существуют OWF, то возможно обязательное согласование битов?
Если нет, существует ли известное разделение черного ящика между ними?


[1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem и
http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator

Мухаммед Аль-Туркистани
источник

Ответы:

6

В недавней работе с Рафаэлем Пассом показано, что без этих дополнительных предположений о сложности Барака-Онг-Вадхана неинтерактивные обязательства не могут основываться на односторонних функциях в «черном ящике». На самом деле, даже с этими дополнительными допущениями (когда они оформлены как некое свойство удара, предполагаемое в дополнение к однонаправленности), разделение черного ящика сохраняется:

http://eprint.iacr.org/2012/523.pdf

(строительство Барак-Онг-Вадхана не является черным ящиком).

Мохаммад
источник
3

Для положительного ответа на этот вопрос, в соответствии с некоторыми дополнительными теоретико-сложными допущениями, см. Статью «Дерандомизация в криптографии» Барака, Онга и Вадхана.

user686
источник