Fonctions à sens unique vs engagements parfaitement contraignants

10

Si des OWF existent, un engagement de bits à liaison statistique est possible. [1]

Est-il connu que si des OWF existent, un engagement de bits parfaitement contraignant est possible?
Si non, existe-t-il une séparation connue entre les boîtes noires?


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

Mohammad Al-Turkistany
la source

Réponses:

6

Dans un travail récent avec Rafael Pass, il est montré que sans ces hypothèses de complexité supplémentaire de Barak-Ong-Vadhan, les engagements non interactifs ne peuvent pas être basés sur des fonctions à sens unique dans une boîte noire. En fait, même avec ces hypothèses supplémentaires (lorsqu'elles sont formalisées comme une sorte de propriété de frappe supposée en plus d'un sens unique), une séparation dans la boîte noire reste valable:

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

(la construction de Barak-Ong-Vadhan n'est pas une boîte noire).

Mohammad
la source
3

Pour une réponse positive à cette question, sous quelques hypothèses théoriques de complexité supplémentaires, voir l'article "Derandomization in Cryptography" de Barak, Ong et Vadhan.

user686
la source