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 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.