Recovering Secrets From Prefix-Dependent Leakage

Abstract

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.

Keywords

• galton–watson process
• discrete logarithm problem
• cryptanalysis
• 94a60
• 11t71