A New Variant of the Cramer-Shoup Leakage-Resilient Public Key Encryption
Sujuan Li
School of Computer Science and Technology, NNU
School of Sciences, NJUT
Nanjing, China
Email: lisujuan1978@126.com
Futai Zhang, Yinxia Sun, Limin Shen
School of Computer Science and Technology, NNU
Nanjing, China
Email: zhangfutai@njnu.edu.cn
Abstract—We present a new variant of the Cramer-Shoup
leakage-resilient public key encryption. The proposed scheme is
more computational efficient than the original Cramer-Shoup
leakage-resilient public key encryption scheme. It enjoys a
shorter (public/secret) key length, and a higher relative leakage
ratio. The new scheme is proved semantically secure against
adaptive chosen ciphertext attack in the standard model under
the decisional Diffie-Hellman assumption.
Keywords-CCA2; leakage resilient; DDH; Cramer-Shoup
encryption scheme;
I. INTRODUCTION
Traditional cryptographic schemes assume that the secret
keys are completely hidden from the adversaries. However
several works [1][2] indicate that the conventional attack
model fails to capture some attacks in the real world. Most
of these attacks are classified as key leakage attacks in which
the attackers may obtain some partial information about the
secret states of the cryptosystems. To stand against such
attacks, there has been a surge of interest in creating leakage-
resilient cryptographic schemes[3][4][5][6].
Cramer and Shoup presented the first practical CCA-
secure public key encryption system, based on the decision-
al Diffie-Hellman (DDH) assumption[11][12]. They later
generalized their construction by considering an algebraic
primitive they call universal hash proof system and showed
that this framework yields not only the original DDH-based
Cramer-Shoup scheme but also encryption schemes based
on quadratic residuosity and on Paillier’s assumption[13].
In Crypto’09 M.Naor et al.[4] introduced a generic con-
struction of a public-key encryption scheme that is resilient
to key leakage from the universal hash proof system. Nat-
urally they proved that the variants of the Cramer-Shoup
cryptosystem are CCA1-secure with key-leakage of L/4
bits, and CCA2-secure with key-leakage of L/6 bits from
the practical side where L is the length of the secret key. As
widely known, both the computational cost and public/secret
key length are significant factors that affect applications
of cryptographic algorithms. When key leakage attacks are
taken into consideration, the relative key-leakage ratio is
also an important concern in real applications. Hence, it
is interesting and challenging to produce leakage resilient
cryptographic algorithms which enjoy a low computational
cost, a short key length, as well as a high relative key-leakage
ratio.
Our Contribution. We focus on this issue in this paper.
To reach our goal, we simplify some parameters in the
Cramer-Shoup leakage-resilient public key encryption (CS-
LR-PKE for short)[4] scheme. As a result, we get a public
key encryption scheme which can not only achieve CCA2-
security without random oracles under the hardness of the
decisional Diffie-Hellman problem but also enjoys a lower
computational cost, a shorter (public/secret) key length, and
a higher relative key leakage ratio. Due to the advancement
of fast multi-exponentiation algorithms[8][10], which makes
the cost of computing double exponentiation very close to
that of computing a single exponentiation, we note that the
improvement on the computational speed in our scheme
may not be significant. Nevertheless, our work suggests a
new way to obtain new and efficient public key encryption
schemes from such CS-LR-PKEs. Our method may apply to
some other variants of CS-LR-PKE. We think it is interesting
to show new ways of constructing more efficient variants of
CS-LR-PKE without sacrificing CCA2-security.
Organization. We proceed as follows. Firstly, in Section II
we review some related tools, computational problems and
the security model for leakage-resilient PKE schemes. Then,
in Section III we present the concrete construction of our
modified leakage-resilient PKE scheme with formal security
proofs. To demonstrate performances of our scheme, a com-
parison with the original Cramer-Shoup leakage-resilient
PKE schemes is made in Section IV. Finally, we give a
conclusion in Section V.
II. P
RELIMINARY
In this section we present some basic notions, definitions,
and tools that will be used in our constructions and security
proofs. We formally state the decisional Diffie-Hellman
assumption and present the notion of average-case strong
extractors.
A. Computational Assumptions
Let G be a probabilistic polynomial-time algorithm that
takes as input a security parameter n and outputs a triplet
2012 Fourth International Conference on Intelligent Networking and Collaborative Systems
978-0-7695-4808-1/12 $26.00 © 2012 IEEE
DOI 10.1109/iNCoS.2012.64
342