Leakage-Resilient Zero Knowledge

On Thursday at the workshop on Formal and Computational Cryptographic Proofs, Amit Sahai from UC Los Angeles presented his work on leakage-resilient zero-knowledge proofs and their applications. He started with addressing some criticisms leakage-resilient cryptography has received, and stated that he was a theoretician, and that the goal was not to make a system which is secure against all possible physical attacks, but rather to find out what the minimal physical assumptions are to do interesting cryptography.

Leakage resilience (LR) cryptography is an attempt to construct systems which are, to some extent, secure against side-channel attacks. To model this, one augments an existing security notion by allowing the adversary to make leakage queries: the adversary picks a function and receives the image of the state of the system he is attacking under that function; it is assumed that the function has to be bounded in some sense not to completely rule out security. LR cryptography is a very active area, though the focus has so far been on non-interactive primitives. Sahai's talk on the other hand focused on interactive zero-knowledge proofs and their applications to LR universally composable multiparty computation.

In zero-knowledge (ZK) proofs, a prover tries to convince a verifier of the validity of a statement (for which he has a witness) without revealing anything else. This is formalised by requiring that there exist a simulator which simulates the view of the verifier without knowing a witness. The problem with defining a LR version of zero knowledge is that leakage of the witness violates the notion of ZK itself. The best we can hope for is therefore that the verifier learns nothing beyond what is leaked of the witness. Different relaxations of LR include the assumption that only computation leaks information or allowing a leakage-free pre-processing phase. In contrast, Sahai's guiding principle is: "leak any time anywhere", in particular on the entire state of the prover and throughout the entire protocol.

Leakage-resilient ZK is defined by requiring that there exist a simulator, which for the verifier is indistinguishable from a prover. Moreover, in the ideal world this simulator is also allowed to make leakage queries. The difficultly is that the simulator has to simulate a view which is consistent even after the leakage queries. There are parallels to "adaptive security without erasure" for ZK, where the adversary is allowed to corrupt the prover (or simulator) and thus learn its full state. However, for LR-ZK matters are even worse, as the simulator must continue its simulation after leakage queries.

A technique to achieve adaptive security are equivocable commitments, which can be opened to several values. Combining this with another trick consisting in making the verifier commit to its challenge ahead of time (and letting the simulator extract this value in the beginning of the simulation), Sahai et al. construct LR-ZK proofs satisfying the following. If the adversary's bound on the leakage function is λ then for any ε there exists a simulator which may make leakage queries bounded by (1+ε)λ. Sahai concluded with showing applications to LR multiparty computation and discussing additional issues one faces there.