Paper 2018/798

Recovering Secrets From Prefix-Dependent Leakage

Houda Ferradi, Rémi Géraud, Sylvain Guilley, David Naccache, and Mehdi Tibouchi


We discuss how to recover a secret bitstring given partial information obtained during a computation over that string, assuming the computation is a deterministic algorithm processing the secret bits sequentially. That abstract situation models certain types of side-channel attacks against discrete logarithm and RSA-based cryptosystems, where the adversary obtains information not on the secret exponent directly, but instead on the group or ring element that varies at each step of the exponentiation algorithm. Our main result shows that for a leakage of a single bit per iteration, under suitable statistical independence assumptions, one can recover the whole secret bitstring in polynomial time. We also discuss how to cope with imperfect leakage, extend the model to $k$-bit leaks, and show how our algorithm yields attacks on popular cryptosystems such as (EC)DSA.

Available format(s)
Publication info
Published elsewhere. Major revision. MATHCRYPT 2018
Galton--Watson processdiscrete logarithm problemcryptanalysis
Contact author(s)
mehdi tibouchi @ normalesup org
2018-10-15: last of 3 revisions
2018-09-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Houda Ferradi and Rémi Géraud and Sylvain Guilley and David Naccache and Mehdi Tibouchi},
      title = {Recovering Secrets From Prefix-Dependent Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2018/798},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.