Author(s):

Kiltz, Eike; Pietrzak, Krzysztof

Title: 
Leakage resilient ElGamal encryption

Title Series: 
LNCS

Affiliation 

Abstract: 
Blinding is a popular and wellknown countermeasure to protect publickey cryptosystems against sidechannel attacks. The high level idea is to randomize an exponentiation in order to prevent multiple measurements of the same operation on different data, as such measurements might allow the adversary to learn the secret exponent. Several variants of blinding have been proposed in the literature, using additive or multiplicative secretsharing to blind either the base or the exponent. These countermeasures usually aim at preventing particular sidechannel attacks (mostly power analysis) and come without any formal security guarantee. In this work we investigate to which extend blinding can provide provable security against a general class of sidechannel attacks. Surprisingly, it turns out that in the context of publickey encryption some blinding techniques are more suited than others. In particular, we consider a multiplicatively blinded version of ElGamal publickey encryption where  we prove that the scheme, instantiated over bilinear groups of prime order p (where p  1 is not smooth) is leakage resilient in the genericgroup model. Here we consider the model of chosenciphertext security in the presence of continuous leakage, i.e., the scheme remains chosenciphertext secure even if with every decryption query the adversary can learn a bounded amount (roughly log(p)/2 bits) of arbitrary, adversarially chosen information about the computation.  we conjecture that the scheme, instantiated over arbitrary groups of prime order p (where p  1 is not smooth) is leakage resilient. Previous to this work no encryption scheme secure against continuous leakage was known. Constructing a scheme that can be proven secure in the standard model remains an interesting open problem.

Keywords: 
Provable security; Encryption schemes; General class; Side channel attack; The standard model; ElGamal; Blinding technique; Chosen ciphertext security; Ciphertexts; Decryption query; Elgamal encryption; Exponentiations; Formal security; Group models; Multiple measurements; Open problems; Power analysis; Prime orders; Publickey cryptosystems; Publickey encryption; Secret exponents

Conference Title:

ASIACRYPT: Theory and Application of Cryptology and Information Security

Volume: 
6477

Conference Dates:

December 59, 2010

Conference Location:

Singapore

ISBN:

9783642173721

Publisher:

Springer

Date Published:

20100114

Start Page: 
595

End Page:

612

Copyright Statement: 
© 2010 International Association for Cryptologic Research.

DOI: 
10.1007/9783642173738_34

Open access: 
no 