Bonsai Best Paper for Eike Kiltz

Researcher Eike Kiltz from the Centrum Wiskunde & Informatica  (CWI) in Amsterdam, received the Best Paper Award from the EuropCrypt 2010 Conference that was held in Monaco and Nice. He and co-authors Dennis Hofheinz, David Cash and Chris Peikert were honoured for their joint paper ‘Bonsai Trees, or How to Delegate a Lattice Basis’. Eurocrypt, together with its US pendant Crypto , is the premier international conference in cryptography.

The work deals with lattice-based cryptography which is a relatively new kind of cryptography that has the promise of - unlike essentially all other crypto that is currently used by the industry- resistance to attacks by quantum computers. Previous designs for ‘digital signatures’ and ‘identity-based encryption’ were simple and efficient, but didn’t come with a rigorous security analysis.

Quantum computers,  if they can ever be constructed, are much faster than 'classical' computers.  In such a quantum era the internet security that is used by banks will become completely useless. The current security system, based on RSA encryption, derives its security on the computational difficulty of factoring large integers and decomposing them as a product of prime numbers.  This means that for a conventional computer, breaking the RSA encryption system is not feasible. However, a  quantum computer could break this security in an instant.

Kiltz also presented his award-winning research at the workshop ‘Public Key Cryptography and the Geometry of Numbers’ on the use of lattices in the construction of public-key cryptographic protocols. The workshop took place in May 2010 at the Royal Netherlands Academy of Arts and Sciences (KNAW) in Amsterdam and was organized by Ronald Cramer (CWI) and David Mandell Freeman (Stanford University, USA).