Abstract Hedged public-key encryption (HPKE), introduced by Bellare et al. (ASIACRYPT 2009), provides useful security when the per-message randomness fails to be uniform due to faulty implementations or adversarial actions. The HPKE scheme achieves IND-CPA (chosen plaintext attack) security when the randomness they used is of high quality, but, when the randomness is poor quality, rather than breaking completely, it achieves a weaker but a useful notion of security called IND-CDA (chosen distribution attack) as long as the message and randomness together have sufficient min-entropy. However, little research on HPKE in the presence of key leakage was done. In this paper, we study HPKE featuring key leakage-resilience and formulate appropriate security notion for key leakage-resilient HPKE. We work in the continual key leakage model where the secret key is refreshed periodically and an adversary can learn arbitrary but bounded leakage on the secret key between the updates. We present two generic constructions of continual leakage-resilient HPKE in the standard model by using a continual leakage-resilient all-but-one lossy trapdoor function. Finally, we give an instantiation of leakage-resilient HPKE under the linear assumption in bilinear groups.
Abstract Hedged public-key encryption (HPKE), introduced by Bellare et al. (ASIACRYPT 2009), provides useful security when the per-message randomness fails to be uniform due to faulty implementations or adversarial actions. The HPKE scheme achieves IND-CPA (chosen plaintext attack) security when the randomness they used is of high quality, but, when the randomness is poor quality, rather than breaking completely, it achieves a weaker but a useful notion of security called IND-CDA (chosen distribution attack) as long as the message and randomness together have sufficient min-entropy. However, little research on HPKE in the presence of key leakage was done. In this paper, we study HPKE featuring key leakage-resilience and formulate appropriate security notion for key leakage-resilient HPKE. We work in the continual key leakage model where the secret key is refreshed periodically and an adversary can learn arbitrary but bounded leakage on the secret key between the updates. We present two generic constructions of continual leakage-resilient HPKE in the standard model by using a continual leakage-resilient all-but-one lossy trapdoor function. Finally, we give an instantiation of leakage-resilient HPKE under the linear assumption in bilinear groups.
Lossy Trapdoor Functions (LTFs) was introduced by Peikert and Waters in 2008. The importance of the LTFs was justified by their numerous cryptographic applications, like the construction of injective one-way trapdoor functions, CCA-secure public-key encryption, etc. However, little research on application of LTFs to key-leakage resilient public-key encryption was done. In this article we introduce a new variant of LTFs featuring leakage-resilience, namely lrLTFs and give a realization of lrLTFs with leakage rate 1/Θ(κ) (where κ is the security parameter) under the Decisional Diffie-Hellman (DDH) assumption. We further improve the leakage rate to 1-o(1) over a composite-order group in which the Decisional Composite Residuosity (DCR) assumption holds. We also introduce a new notion of key-leakage attacks, which we call weak key-leakage attacks, for bridging the adaptive and non-adaptive key-leakage attacks in the setting of public-key cryptosystem. In this model, the leakage adversary only gets a part of public key before accessing to a leakage oracle. We show that lrLTFs imply public-key encryption schemes secure against chosen-ciphertext weak key-leakage attacks in a black-box sense.
We present a new generic construction of a public-key encryption (PKE) scheme secure against leakage-resilient chosen-ciphertext attacks (LR-CCA), from any Hash Proof System (HPS) and any one-time lossy filter (OT-LF). Efficient constructions of HPSs and OT-LFs from the DDH and DCR assumptions suggest that our construction is a practical approach to LR-CCA security. Most of practical PKEs with LR-CCA security, like variants of Cramer-Shoup scheme, rooted from Hash Proof Systems, but with leakage rates at most 1/4 − o(1) (defined as the ratio of leakage amount to secret-key size). The instantiations of our construction from the DDH and DCR assumptions result in LR-CCA secure PKEs with leakage rate of 1/2 − o(1). On the other hand, our construction also creates a new approach for constructing IND-CCA secure (leakage-free) PKE schemes, which may be of independent interest.
Leakage resilient cryptography is often considered in the presence of a very strong leakage oracle: An adversary may submit arbitrary efficiently computable function f to the leakage oracle to receive f(x), where x denotes the entire secret that a party possesses. This model is somewhat too strong in the setting of public-key encryption (PKE). It is known that no secret-key leakage resilient PKE scheme exists if the adversary may have access to the secret-key leakage oracle to receive only one bit after it was given the challenge ciphertext. Similarly, there exists no sender-randomness leakage resilient PKE scheme if one-bit leakage occurs after the target public key was given to the adversary. At TCC 2011, Halevi and Lin have broken the barrier of after-the-fact leakage, by proposing the so-called split state model, where a secret key of a party is explicitly divided into at least two pieces, and the adversary may have not access to the entire secret at once, but each divided pieces, one by one. In the split-state model, they have constructed post-challenge secret-key leakage resilient CPA secure PKEs from hash proof systems, but the construction of CCA secure post-challenge secret-key leakage PKE has remained open. They have also remained open to construct sender-randomness leakage PKE in the split state model. This paper provides a solution to the open issues. We also note that the proposal of Halevi and Lin is post-challenge secret-key leakage CPA secure against a single challenge ciphertext; not against multiple challenges. We present an efficient generic construction that converts any CCA secure PKE scheme into a multiple-challenge CCA secure PKE that simultaneously tolerates post-challenge secret-key and sender-randomness leakage in the split state model, without any additional assumption. In addition, our leakage amount of the resulting schemes is the same as that of Halevi and Lin CPA PKE, i.e., (1/2+γ)l/2 where l denotes the length of the entire secret (key or randomness) and γ denotes a universal (possitive) constant less than 1/2. Our conversion is generic and available for many other public-key primitives. For instance, it can convert any identity-based encryption (IBE) scheme to a post-challenge master-key leakage and sender-randomness leakage secure IBE.
Lossy trapdoor functions (LTFs) were first introduced by Peikert and Waters (STOC’08). Since their introduction, lossy trapdoor functions have found numerous applications. They can be used as tools to construct important cryptographic primitives such as injective one-way trapdoor functions, chosen-ciphertext-secure public key encryptions, deterministic encryptions, et al. In this paper, we focus on the lossy trapdoor functions in the presence of continuous leakage. We introduce the new notion of updatable lossy trapdoor functions (ULTFs) and give their formal definition and security properties. Based on these, we extend the security model to the LTFs against continuous leakage when the evaluation algorithm is leakage resilient. Under the standard DDH assumption and DCR assumption, respectively, we show two explicit lossy trapdoor functions against continuous leakage in the standard model. In these schemes, using the technology of matrix kernel, the trapdoor can be refreshed at regular intervals and the adversaries can learn unbounded leakage information on the trapdoor along the whole system life. At the same time, we also show the performance of the proposed schemes compared with the known existing continuous leakage resilient lossy trapdoor functions.
Abstract Lossy trapdoor functions (LTFs), introduced by Peikert and Waters (STOC’08), have already been found to be a very useful tool in constructing complex cryptographic primitives in a black-box manner, such as one-way trapdoor functions, deterministic public-key encryption, CCA-secure public-key encryption, etc. Due to the existence of the side-channel attack, the leakage of trapdoor information in lossy trapdoor function systems can lead to the impossibility of provable security. Recently, Zhang et al. introduced a model of consecutive and continual leakage-resilient and updatable lossy trapdoor functions (ULTFs) and provided a concrete construction to achieve the security. Meanwhile, they proposed a consecutive and continual leakage-resilient public-key encryption scheme. However, in this paper, we demonstrate that the correctness of injective function can not be satisfied. Furthermore, the attacker can easily distinguish the evaluation key of ULTFs generated by the challenger according to the security model. Finally, we show two new constructions based on the continual leakage-resilient public-key encryption scheme of Brakerski et al. (FOCS 2010) and demonstrate the security of our scheme in the consecutive and continual leakage model.
There has been much recent progress in constructing cryptosystems that maintain their security without requiring uniform randomness and perfect secrecy. These schemes are motivated by a diverse set of problems such as providing resilience to side-channel leakage, using weak physical sources of randomness as secret keys, and allowing deterministic encryption for high-entropy messages. The study of these problems has significantly deepened our understanding of how randomness is used in cryptographic constructions and proofs. Nevertheless, despite this progress, some basic and seemingly achievable security properties have eluded our reach. For example, we are unable to prove the security of basic tools for manipulating weak/leaky random sources, such as as pseudo-entropy generators and seed-dependent computational condensers. We also do not know how to prove leakage-resilient security of any cryptosystem with a uniquely determined secret key. In the context of deterministic encryption we do not have a standardmodel constructions achieving the strongest notion of security proposed by Bellare, Boldyreva and O’Neill (CRYPTO ’07), that would allow us to encrypt arbitrarily correlated messages of sufficiently large individual entropy. In this work, we provide broad black-box separation results, showing that the security of such primitives cannot be proven under virtually any standard cryptographic hardness assumption via a reduction that treats the adversary as a black box. We do so by formalizing the intuition that “the only way that a reduction can simulate the correctly distributed view for an attacker is to know all the secrets, in which case it does not learn anything useful from the attack”. Such claims are often misleading and clever way of getting around them allow us to achieve a wealth of positive results with imperfect/leaky randomness. However, in this work we show that this intuition can be formalized and that it indeed presents a real barrier for the examples given above. ∗IBM Research. wichs@cs.nyu.edu