Test of Time 2002 Awards

Daniele Micciancio:
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions

This paper was an inflection point for lattice-based cryptography, helping transform it from a relatively small and fragmented research area into a thriving subfield of cryptography with immense theoretical and practical impact. It showed that cryptography based on lattices can be both efficient and secure under worst-case complexity assumptions, a feat never reached by number-theory based cryptography.

With remarkable foresight, the paper first boldly put forward a conjecture on the worst-case hardness of “algebraically structured” lattices, then rigorously proved that such hardness gives rise to similarly structured average-case hardness, and finally convincingly argued that this structure admits fast implementation on modern microprocessors.

The paper’s worst-case, and hence average-case, hardness conjectures have withstood the test of time. The techniques introduced in this paper have evolved and grown to an immense body of work, shaping many future results in the area.

Michael Luby:
LT Codes

The paper “LT Codes” describes the first implementation of so-called “universal erasure codes”, which are almost optimal codes for any channel over which data may be lost under any loss model. More specifically, the paper shows how to realize the powerful “digital fountain” concept introduced in earlier work of Byers, Luby, Mitzenmacher and Rege, whose implementation had proved elusive. The actual implementation is extremely elegant and is a perfect example of the power of analytical techniques from CS theory to shape the design of an important real-world artifact.

The ideas in the paper have been hugely influential in both the academic and the technological worlds. Among its thousands of academic citations are works in CS theory, information theory, network coding, optimal and wireless communications, sensor networks, content distribution and data storage. On the practical side, LT codes and their derivatives have become integral parts of several standards for wired and wireless networks.