Resettable Statistical Zero Knowledge
Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Abstract:
Two Central notions of Zero Knowledge that provide strong, yet seemingly incomparable security guarantees against malicious verifiers are those of Statistical Zero Knowledge and resettable Zero Knowledge. The current state of the art includes several feasibility and impossibility results regarding these two notions separately. However, the question of achieving Resettable Statistical Zero Knowledge (i.E., Resettable Zero Knowledge and Statistical Zero Knowledge simultaneously) for non-trivial languages remained open.In this paper, we show:
Resettable Statistical Zero Knwledge with unbounded prover: under the assumption that sub-exponentially hard one-way functions exist,/ensuremathr SZK=\SZK. In other words, every language that admits a Statistical Zero -Knowledge (\ensuremath SZK. In other words, every language that admits a Statistical Zero-Knowledge (\ensuremath rSZK) proof system. Further, the result can be re-stated unconditionally provided there exists a sub-exponentially hard language in SZK). Moreover; under assumption that ( standard) one way functions exist, all languages L such that the complement of L is random self reducible, admit a \ensuremath rSZK; in other words: \ensuremathco-RSR ⊆\ensuremath rSZK.
Resettable Statistical Zero Knowledge with efficient prover: efficient-prover Resettable Statistical Zero-Knowledge proof systems exist for all languages that admit hash proof systems (e.g.,QNR, QR,DDH, DCR). Furthermore, for these languages we construct a two-round resettable statistical witness-indistinguishable argument system.
The round complexity of our proof systems is ο(log), where k is the security parameter, and all our simulators are black- box.
comment: TCC 2012: 494-511
Fetch PDF file of the paper
| Back to Publications List |