Peikert, an assistant professor in the School of Computer Science, earned the honor for “Bonsai Trees, or How to Delegate a Lattice Basis,” which he presented during Eurocrypt 2010, one of the premier international conferences of cryptography, held May 30-June 3 in Monaco and Nice, France. Peikert said lattice-based cryptography is a relatively new kind that has the promise of high efficiency, parallelism, and--unlike essentially all other standard crypto--resistance to attacks by quantum computers.

“We dealt with one of the main outstanding problems in the area,” Peikert said. “Previous designs for ‘digital signatures’ and ‘identity-based encryption’ were simple and efficient, but their security analysis relied on a not-entirely-sound shortcut called a ‘random oracle.’ The main question was whether this shortcut could be removed (and without hurting efficiency too much), thereby making the schemes rest on a much more rigorous foundation. The paper solves exactly this problem—and, as a bonus side-effect, the techniques also make it possible to design what's called a hierarchical ID-based encryption scheme, which is a more flexible structure that can better distribute trust and withstand unintended exposures of secret keys.”

Peikert’s co-authors were recently graduated Georgia Tech Ph.D. student David Cash (now a postdoctoral researcher at University of California, San Diego), as well as Dennis Hofheinz and Eike Kiltz of CWI (Centrum Wiskunde & Informatica) in Amsterdam. The full text of their paper is available here.