Improving Algorithms for Side-Channel Cryptanalysis

In side-channel attacks, attackers learn protected information by measuring an external hardware or software artifact, such as execution time or electromagnetic radiation. In cryptographic implementations, side-channel attacks can reveal secret keys and other sensitive information. However, an attacker’s measurements may be noisy or imperfect, and they might learn only a few bits of secret information.

But even this small leak can break some cryptographic algorithms. With the DSA and ECDSA digital signature algorithms, an attacker can compute a secret signing key with only a handful of bits leaked each time the victim computes a digital signature. In a beautiful turn of mathematics, this key recovery calculation can be carried out by finding a short vector in an algebraic lattice.

In On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem, UC San Diego CSE/CNS faculty member Nadia Heninger and Martin R. Albrecht, from Information Security Group, Royal Holloway and the University of London, show how to recover secret keys by providing an algorithm to search the lattice for the key with less information and fewer signatures than was thought possible. Their paper will be presented on October 19 at the Eurocrypt hybrid conference in Zagreb, Croatia.