Accession Number:

ADA582583

Title:

Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security

Descriptive Note:

Technical rept.

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2012-11-05

Pagination or Media Count:

33.0

Abstract:

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak FOCS01 introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth FOCS12 instead requires the existence of an Oblivious Transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

Descriptors:

Subject Categories:

  • Cybernetics
  • Defense Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE