Wednesday, 15.6.2011, 12:30
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 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 on the entire state of honest party during the protocol execution (in contrast, prior work only considered leakage prior to the protocol execution, or very limited leakage during during the protocol execution). Next, we give an LR-NIZK argument system based on standard assumptions.
Finally, we demonstrate the usefulness of our notions by giving two concrete applications:
-- We show how to do UC secure computation in the "leaky token model" (i.e., where an adversary in possession of a token can obtain arbitrary bounded leakage on the entire state of the token) based on standard assumptions.
-- Next, we give a new construction of fully leakage-resilient signatures in the bounded leakage model (as well as the continual leakage model) based on standard assumptions. In contrast to the recent constructions of fully leakage resilient signatures, our scheme is also secure in the "noisy leakage" model.
Joint work with Abhishek Jain and Amit Sahai.