Leakage-Resilient Zero Knowledge

In this paper, we initiate a study of zero knowledge proof systems in the presence of side-channel attacks. Specifically, we consider a setting where a cheating verifier is allowed to obtain arbitrary bounded leakage on the

entire state

(

including the witness and the random coins

) of the prover

during the entire protocol execution

. We formalize a meaningful definition of

leakage-resilient zero knowledge

(LR-ZK) proof system, that intuitively guarantees that

the protocol does not yield anything beyond the validity of the statement and the leakage obtained by the verifier

.

We give a construction of LR-ZK interactive proof system based on standard general assumptions. To the best of our knowledge, this is the first instance of a cryptographic

interactive protocol

where the adversary is allowed to perform leakage attacks during the protocol execution on the

entire state

of honest party (in contrast, prior work only considered leakage

prior

to the protocol execution, or very limited leakage

during

the protocol execution). Next, we give an LR-NIZK proof system based on standard number-theoretic assumptions.

Finally, we demonstrate the usefulness of our notions by giving two concrete applications:

We initiate a new line of research to relax the assumption on the “tamper-proofness” of hardware tokens used in the design of various cryptographic protocols. In particular, we give a construction of a universally composable multiparty computation protocol in the

leaky token model

(where an adversary in possession of a token is allowed to obtain arbitrary bounded leakage on the

entire state

of the token) based on standard general assumptions.

Next, we give simple, generic constructions of

fully

leakage-resilient signatures in the bounded leakage model as well as the continual leakage model. Unlike the recent constructions of such schemes, we also obtain security in the “noisy leakage” model.