Paper 2014/865

Impossibility of Black-Box Simulation Against Leakage Attacks

Rafail Ostrovsky, Giuseppe Persiano, and Ivan Visconti


In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted). More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel -- PKC 13] to prove lower bounds for leakage-resilient security. Indeed, we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks. Our results show that the open problem of [Ananth, Goyal, Pandey -- Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. -- STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).

Note: 07-11-2014: the main technique is described as an extension of the one introduced by Nielsen et al. in [NVZ13].

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2015
zero knowledgeMPCresettabilitysuccinct argumentsimpossibility resultsblack-box vs non-black-box simulation
Contact author(s)
ivan visconti @ gmail com
2015-06-22: last of 2 revisions
2014-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rafail Ostrovsky and Giuseppe Persiano and Ivan Visconti},
      title = {Impossibility of Black-Box Simulation Against Leakage Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2014/865},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.