Nadia Heninger, Associate Professor | University of California, San Diego
Breaking the Lattice Barrier for the Hidden Number Problem
In the video below, Nadia Heninger discusses Breaking the Lattice Barrier for the Hidden Number Problem.
Presented at the NTT Research Upgrade 2021 Summit on September 21, 2021.
Digital signatures are important in many applications to allow the verification of the authenticity of a website, file, or the like. The Elliptic Curve Digital Signature Algorithm (ECDSA) is used to create such signatures, and, while more complex, is believed to give improved security over the Digital Signature
Algorithm, which is a U.S. federal standard and so may be regarded as the state of the art. With uses including Bitcoin, the security of ECDSA has naturally attracted much attention.
At Upgrade 2021, Professor Nadia Heninger (University of California San Diego) presented joint work with Prof. Martin R. Albrecht (University of London) demonstrating that side-channel attacks on ECDSA are more practical than had previously been thought. Side-channel attacks use information like processing time, power usage or electromagnetic radiation to obtain partial information such as the most significant bit(s) of a secret. This partial information can then be used to bootstrap a brute-force attack to obtain the full secret, thus side-stepping the full difficulty of breaking a cipher.
ECDSA applications are a favorite target for such attacks, modeled as follows: the attacker obtains partial information about the one-time nonces used to generate a series of signatures and uses it to obtain the long-term private key of the signer – enabling the attacker to impersonate the signer. The brute-force attack has often been represented as a search for the shortest vector in a high-dimensional lattice, which is a well-studied problem. The assumed difficulty of this search is the so-called lattice barrier, which has previously been taken to be a guarantee of the difficulty of such attacks on ECDSA.
With a more careful analysis of the problem, Heninger argued the difficulty of the attack has been overstated. For example, a solution may not require the shortest vector of the lattice to be discovered, only one whose length is within a small constant multiple of the shortest vector.
Similarly, she showed the previously assumed susceptibility of lattice solving to input noise has been overestimated, and that techniques exist to enable the attacker to overcome this. The techniques presented have been implemented and thoroughly tested: throughout, Heninger presented numerical evidence of the speed-ups possible over standard techniques. As a real-world proof of practicality, her team used these techniques to (benignly) break into some Bitcoin accounts using insufficiently long nonces.
In conclusion, Professor Heninger presented an outline of proposed future work and gave the address where the implemented code can be obtained.
Associate Professor | University of California, San Diego
Nadia Heninger is an Associate Professor of Computer Science and Engineering at the University of California, San Diego. Her primary research interests are in cryptography and security, with particular interest in cryptography in practice, cryptanalysis, privacy, lattices, computational number theory, and coding theory. From 2013 until 2018, She was an assistant professor in the Computer and Information Science Department at the University of Pennsylvania. Before then, she was a postdoctoral visiting researcher at Microsoft Research New England in Cambridge, MA, and an NSF mathematical sciences postdoctoral fellow in the Department of Computer Science and Engineering at UC San Diego. Professor Heninger has a Ph.D. in computer science from Princeton University and a B.S. in electrical engineering and computer science from UC Berkeley.