Chris Peikert Receives TCC Test of Time Award for work in lattice cryptography

Chris Peikert, the Patrick C. Fischer Development Professor in Theoretical Computer Science, and his co-author Alon Rosen have received the TCC Test of Time Award for their paper on efficient collision-resistant hashing on cyclic lattices. The award was presented at the Fifteenth Theory of Cryptography Conference (TCC) in Baltimore on November 14, 2017.

The Award recognizes outstanding papers, presented at the TCC at least eight years ago, that have made a significant contribution to the theory of cryptography and beyond.

Peikert and Rosen’s award is for their paper, “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices,” published in TCC 2006, “for advancing the use of hard algebraic lattice problems in cryptography, paving the way for major theoretical and practical advances.”

The development of more powerful computers and better algorithms has, over time, meant that once-secure cryptographic protocols can now be broken. Today, stronger public-key schemes such as the RSA or Diffie-Hellman cryptosystems are considered highly secure – but those approaches will be vulnerable to attacks by coming quantum computers.

Prof. Peikert’s research has focused on developing new, stronger mathematical foundations for cryptography, with a particular focus on geometric objects called lattices. Lattices yield cryptographic schemes having unique and attractive properties, such as apparent immunity to quantum attacks, and high levels of efficiency and parallelism.

The TCC award is essentially a recognition of a long line of works by Prof. Peikert and others who laid the foundations for practically efficient lattice-based cryptography.

The paper describes how Peikert and Rosen built the first practically very efficient “collision resistant hash function” (a tool with many uses across cryptography) with a sound theoretical analysis under mild “worst case” hardness assumptions that also appears to be “quantum safe.”

Further work led to substantial progress toward realizing the full potential of lattices in cryptography by strengthening the theoretical foundations of the area, designing new private-key and public-key encryption systems that enjoy rich functionality and strong security properties, and making lattice cryptography efficient and practical.

In the past year, Google has successfully tested post-quantum cryptography at scale in Chrome using an algorithm created by Peikert and his collaborators. Under the test, a small fraction of connections between desktop Chrome and Google’s servers used the post-quantum key-exchange algorithm in addition to the elliptic-curve key-exchange algorithm that would typically be used. The test allowed Google to gain real-world experience with the larger data structures that post-quantum algorithms require.

Prof. Peikert received his PhD in Computer Science from MIT in 2006 and he joined CSE in Fall 2015 from the faculty of Georgia Institute of Technology. Among several other recognitions of his scholarly contributions, Peikert has received a Sloan Foundation Fellowship, a Bergmann Memorial Research Award, and Best Paper awards at EUROCRYPT and STOC.