Public-Key Cryptosystems Resilient to Key Leakage

Most of the work in the formal analysis of cryptographic schemes traditionally
concentrated in abstract adversarial models that do not capture side-channel
attacks. Such attacks exploit various forms of unintended information leakage,
which is inherent to almost all physical implementations. In light of the
prevalence of such attacks there are several attempts to model them and suggest
schemes that are resistant to them. Inspired by recent side-channel attacks, especially the
"**cold
boot attacks**", Akavia, Goldwasser
and Vaikuntanathan (TCC '09) suggested a framework for modeling the security of
encryption schemes against a wide class of side-channel attacks, in which
adversarially chosen functions of the secret key are leaked to the attacker. The
functions may be chosen after the public key is known but there total length is
limited. We revisit this framework and our main results are
as follows:

- We present a generic construction of a public-key encryption scheme that
is resilient to key leakage from any
**universal hash proof system**. The construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying proof system. Existing constructions of such proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the*decisional Diffie-Hellman*assumption (and its progressively weaker d-Linear variants), the quadratic residuosity assumption, and Paillier's composite residuosity assumption. - We construct a new hash proof system based on the decisional Diffie-Hellman assumption (and its d-Linear variants), and show that the
resulting scheme is resilient to any leakage
of
**L(1-o(1))**bits. In addition, we prove that the recent scheme of Boneh et al. (CRYPTO '08), constructed to be a "**circular-secure**" encryption scheme, is resilient to any leakage of**L(1-o(1))**bits. These two proposed schemes complement each other in terms of efficiency. - We extend the framework of key leakage to the setting of chosen-ciphertext
attacks. On the theoretical side, we prove that the
**Naor-Yung paradigm**is applicable in this setting as well, and obtain as a corollary encryption schemes that are**CCA2-secure**with any leakage of**L(1-o(1))**bits. On the practical side, we prove that variants of the**Cramer-Shoup cryptosystem**(along the lines of our generic construction) are**CCA1-secure**with any leakage of**L/4**bits, and CCA2-secure with any leakage of**L/6**bits.