Limits of a conjecture on a leakage-resilient cryptosystem

English

Galindo, David[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) > ; CNRS/LORIA, Nancy, France]

Venkatesh, Srinivas Vivek[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]

[en] Cryptography ; Leakage-resilient cryptography ; ElGamal ; Hidden number problem ; Lattice-based attacks

[en] Recently it was conjectured that an ElGamal-based public-key encryption scheme with stateful decryption resists lunch-time chosen ciphertext and leakage attacks in the only computation leaks information model. We give a non-trivial upper bound on the amount of leakage tolerated by this conjecture. More precisely, we prove that the conjecture does not hold if more than a (3/8 + o (1)) fraction of the bits are leaked at every decryption step, by showing a lunch-time attack that recovers the full secret key. The attack uses a new variant of the Hidden Number Problem, that we call Hidden Shares – Hidden Number Problem, which is of independent interest.