Author(s):

Jain, Abhishek; Pietrzak, Krzysztof

Title: 
Parallel repetition for leakage resilience amplification revisited

Title Series: 
LNCS

Affiliation 

Abstract: 
If a cryptographic primitive remains secure even if ℓ bits about the secret key are leaked to the adversary, one would expect that at least one of n independent instantiations of the scheme remains secure given n·ℓ bits of leakage. This intuition has been proven true for schemes satisfying some special informationtheoretic properties by Alwen et al. [Eurocrypt'10]. On the negative side, Lewko and Waters [FOCS'10] construct a CPA secure publickey encryption scheme for which this intuition fails. The counterexample of Lewko and Waters leaves open the interesting possibility that for any scheme there exists a constant c>0, such that n fold repetition remains secure against c·n·ℓ bits of leakage. Furthermore, their counterexample requires the n copies of the encryption scheme to share a common reference parameter, leaving open the possibility that the intuition is true for all schemes without common setup. In this work we give a stronger counterexample ruling out these possibilities. We construct a signature scheme such that: 1. a single instantiation remains secure given ℓ = log(k) bits of leakage where k is a security parameter. 2. any polynomial number of independent instantiations can be broken (in the strongest sense of keyrecovery) given ℓ′ = poly(k) bits of leakage. Note that ℓ does not depend on the number of instances. The computational assumption underlying our counterexample is that noninteractive computationally sound proofs exist. Moreover, under a stronger (nonstandard) assumption about such proofs, our counterexample does not require a common reference parameter. The underlying idea of our counterexample is rather generic and can be applied to other primitives like encryption schemes. © 2011 International Association for Cryptologic Research.

Keywords: 
Cryptographic primitives; Parallel repetition; Computational assumptions; Encryption schemes; Keyrecovery; Leakageresilience; Noninteractive; Polynomial number; Publickey encryption scheme; Reference parameters; Secret key; Security parameters; Signature Scheme

Conference Title:

TCC: Theory of Cryptography Conference

Volume: 
6597

Publisher:

Springer

Date Published:

20110101

Start Page: 
58

End Page:

69

DOI: 
10.1007/9783642195716_5

Open access: 
no 