The recent work of Garg, Jain, and Sahai formulates a meaningful notion of zero-knowledge in presence of leakage; and provides a construction which satisfies a weaker variant of this notion called (1+e)-leakage-resilient-zero-knowledge, for every constant e>0. In this weaker variant, roughly speaking, if the verifier learns L bits of leakage during the interaction, then the simulator is allowed to access (1+e).L bits of leakage. The round complexity of their protocol is n/e.
In this work, we present the first construction of leakage-resilient zero-knowledge satisfying the ideal requirement of e=0. While our focus is on a feasibility result for e=0, our construction also enjoys a constant number of rounds. At the heart of our construction is a new ``public-coin preamble'' which allows the simulator to recover arbitrary information from a (cheating) verifier in a ``straight line.'' We use non-black-box simulation techniques to accomplish this goal.Category / Keywords: foundations / Zero Knowledge, Leakage, Interactive Proofs Publication Info: Manuscript Date: received 27 Jun 2012, last revised 17 Feb 2013 Contact author: omkant at cs utexas edu Available formats: PDF | BibTeX Citation Version: 20130217:160056 (All versions of this report) Discussion forum: Show discussion | Start new discussion