Abstract
Leakage resilient cryptography is often considered in the presence of a very strong leakage oracle: An adversary may submitarbitrary efficiently computable functionf to the leakage oracle to receivef(x), wherex 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 onlyone 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 ofafter-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 theentire 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 asingle challenge ciphertext; not againstmultiple challenges. We present an efficient generic construction that converts any CCA secure PKE scheme into amultiple-challenge CCA secure PKE that simultaneously toleratespost-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 thesame as that of Halevi and Lin CPA PKE, i.e., (1/2+γ)l/2 wherel 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.
