Krzysztof Pietrzak (CWI) and an international team won the Best Paper Award at Eurocrypt 2011 in Tallinn. They received the prize for their paper Efficient Authentication from Hard Learning Problems. The researchers proposed simple and secure cryptographic authentication methods for small devices, such as wireless car keys. Their results are the first to be at the same time highly efficient and provably secure for most small applications. The new methods can also be implemented on RFID chips, which are used in electronic passports and the OV chip card.
Simple and secure
Many electronic identification devices use RFID chips. These are very small, so there is no computing power for complicated identification algorithms. A very efficient and simple authentication method called HB was proposed by cryptographers Hopper and Blum in 2001. Using limited computation, this protocol seemed very suitable for small devices. Unfortunately, it is not secure against ‘active’ adversaries who can intercept and change messages. For this reason this protocol has not been actually used in practice. Many methods were developed since, but they were either too weak, or needed too many computations for small chips. The award winning team came up with a completely new way of constructing protocols that are not only as efficient as HB, but also provide sufficient security in practice. It is the first theoretical description of a provably secure scheme with only two verification rounds, making it very efficient.
A prototype of a chip running the new verification method is currently being implemented by the embedded security group at the Ruhr-University Bochum, which cooperates with the Centrum Wiskunde & Informatica (CWI) in Amsterdam. In future, the developed techniques are used to achieve other cryptographic tasks than authentication, like encryption schemes. The international team members are Eike Kiltz (Ruhr-University Bochum), Krzysztof Pietrzak (CWI, Amsterdam), David Cash (University of California, San Diego), Abhishek Jain (University of California, Los Angeles) and Daniele Venturi (Sapienza University of Rome). The award winning work was done when Kiltz was working at CWI and the three other authors were visiting CWI. Krzysztof Pietrzak is member of the CWI research group Cryptology and Information Security. This group investigates fundamental questions about cryptography from a broad scientific perspective, especially mathematics, computer science and physics.
More information:
Eurocrypt 2011, May 2011: http://www.iacr.org/conferences/eurocrypt2011/index.php
Homepage Krzysztof Pietrzak: http://homepages.cwi.nl/~pietrzak/
Picture: electronic car key, Shutterstock
