Cryptology ePrint Archive: Report 2014/865

Impossibility of Black-Box Simulation Against Leakage Attacks

Rafail Ostrovsky and Giuseppe Persiano and Ivan Visconti

Abstract: 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).

Category / Keywords: zero knowledge, MPC, resettability, succinct arguments, impossibility results, black-box vs non-black-box simulation

Original Publication (with minor differences): IACR-CRYPTO-2015

Date: received 21 Oct 2014, last revised 22 Jun 2015

Contact author: ivan visconti at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20150622:085818 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]