Achieving Constant Round Leakage-Resilient Zero-Knowledge

Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit the physical characteristics of a cryptographic device to learn useful information about the internal state of the device. Designing protocols that deliver meaningful security even in the presence of such leakage attacks is a challenging task.

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 + 

ε

)-leakage-resilient-zero-knowledge, for every constant

ε

 > 0. In this weaker variant, roughly speaking, if the verifier learns ℓ bits of leakage during the interaction, then the simulator is allowed to access (1 + 

ε

)·ℓ bits of leakage. The round complexity of their protocol is

$\lceil \frac{n}{\epsilon}\rceil$

.

In this work, we present the first construction of leakage-resilient zero-knowledge satisfying the ideal requirement of

ε

 = 0. While our focus is on a feasibility result for

ε

 = 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.