Einwegfunktionen im Vergleich zu perfekt verbindlichen Verpflichtungen

10

Wenn OWFs existieren, ist eine statistisch bindende Bitbindung möglich. [1]

Ist bekannt, dass bei Vorhandensein von OWFs eine perfekt bindende Bitbindung möglich ist?
Wenn nein, gibt es eine bekannte Black-Box-Trennung zwischen ihnen?


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

Mohammad Al-Turkistany
quelle

Antworten:

6

In einer kürzlich durchgeführten Arbeit mit Rafael Pass wurde gezeigt, dass nicht interaktive Verpflichtungen ohne diese zusätzlichen Komplexitätsannahmen von Barak-Ong-Vadhan nicht auf Einwegfunktionen in einer Black-Box-Weise basieren können. Selbst mit diesen zusätzlichen Annahmen (wenn sie als eine Art Schlageigenschaft formalisiert werden, die zusätzlich zur Einbahnstraße angenommen wird) gilt immer noch eine Black-Box-Trennung:

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

(Der Bau von Barak-Ong-Vadhan ist keine Black-Box).

Mohammad
quelle
3

Eine positive Antwort auf diese Frage finden Sie unter einigen zusätzlichen komplexitätstheoretischen Annahmen in der Veröffentlichung "Derandomisierung in der Kryptographie" von Barak, Ong und Vadhan.

user686
quelle