‘Bonsai’ Best Paper for Peikert

June 1, 2010

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.