The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information. In particular, under what we call the subgroup indistinguishability assumption, of which the QR and DCR are special cases, we can construct a scheme that has: • Key-dependent message (circular) security. Achieves security even when encrypting affine functions of its own secret key (in fact, w.r.t. affine "key-cycles" of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of functions beyond affine functions using previous techniques of [BGK, ePrint09] or [BHHI, Eurocrypt10]. • Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently computable) function of the secret key is given to the adversary. A proper selection of parameters allows for a "leakage rate" of (1 − o(1)) of the length of the secret key. • Auxiliary-input security. Remains secure even if any sufficiently hard to invert (efficiently computable) function of the secret key is given to the adversary. Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1 − o(1)) of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of [NS, Crypto09], using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length. Key-dependent messages. The shortcoming of the standard security definition in the case where the plaintext to be encrypted depends on the secret key was already noticed in [GM84] . It was later observed that this situation is not so unlikely and may sometimes even be desirable [CL01, ABHS05, LC03]. Black, Rogoway and Shrimpton [BRS02] formally defined KDM-security: the attacker can obtain encryptions of (efficient) functions of its choosing, taken from some specified class of functions F, applied to the secret key. The requirement is that the attacker cannot tell if all of its queries are answered by encryptions of some constant symbol 0, instead of the requested values. This definition is extended to the case of many (say n) users that can encrypt each others' secret keys: the attacker queries now contain a function to be applied to all secret keys, and an identity of the user whose public key should be used to encrypt. This latter case is referred to as KDM (n) -security while the single-user case is called KDM (1) -security. Boneh, Halevi, Hamburg and Ostrovsky [BHHO08] constructed a public key encryption scheme that is KDM (n) secure w.r.t. all affine functions, 1 under the decisional Diffie-Hellman (DDH) assumption, for any polynomial n. This first result was followed by the work of Applebaum, Cash, Peikert and Sahai [ACPS09] who proved that a variation of Regev's scheme [Reg05] is also KDM secure w.r.t. all affine functions, under the learning with errors (LWE) assumption. More recent works by Brakerski, Goldwasser and Kalai [BGK09] and by Barak, Haitner, Hofheinz and Ishai [BHHI09] presented each general and different techniques to extend KDMsecurity to richer classes of functions. In [BGK09], the notion of entropy-κ KDM-security is introduced. A scheme is entropy-κ KDM-secure if it remains KDM-secure even if the secret key is sampled from a high-entropy distribution, rather than a uniform one. They show that an entropyκ KDM-secure scheme implies a scheme that is KDM-secure w.r.t. roughly any pre-defined set of functions of polynomial cardinality. In [BHHI09], the notion of targeted public-key encryption is introduced. A targeted encryption scheme can be thought of as a combination of oblivious transfer and encryption: it is possible to encrypt in such a way that the ciphertext is decryptable only if a certain bit of the secret key takes a predefined value. They show that a targeted encryption scheme implies a KDM-secure scheme w.r.t. all functions computable by circuits of some predefined (polynomial) size. These two results achieve incomparable performance. While in the former, the public key and ciphertext lengths depend on the size of the function class (but not on its complexity) and are independent of the number of users n, in the latter the public key size does not depend on the function class, but the ciphertext length is linear in the product of n times the complexity of the functions. Leakage resiliency. The work on cold boot attacks by Halderman et al. [HSH + 08], gave rise to the notion of public-key encryption resilient to (bounded) memory leakage attacks, presented by Akavia, Goldwasser and Vaikuntanathan [AGV09] and further explored by Naor and Segev [NS09] . In their definition, security holds even if the attacker gets some information of its choosing (depending on the value of the public key) on the scheme's secret key, so long as the total amount of information leaked does not exceed an a-priori information theoretic bound. More formally, the attacker can request and receive f (sk) for a length-restricted function f . 2 [AGV09, NS09] presented public-key encryption schemes that are resilient to leakage of even a 1 − o(1) fraction of the secret key (we
Brakerski and Goldwasser REF proposed a leakage-resilient PKE under the subgroup indistinguishability, which is a theoretical performance evaluation in improving the leakage rate.
Circular and leakage resilient public-key encryption under subgroup indistinguishability
IACR Cryptology ePrint Archive
IACR Cryptology ePrint Archive
Computer Science Mathematics