February 14, 2005
11:00, IMU Maple Room

An Oblivious Transfer Protocol with Log-Squared Communication

Helger Lipmaa

Abstract:
After a 1-out-of-n computationally-private information retrieval protocol, a chooser will obtain one element of the database, without the sender getting to know which element was obtained. We propose a family of two-round 1-out-of-n computationally-private information retrieval protocols for log d-bit elements that has the following properties: (a) In the asymptotically optimal case, it has communication \Theta((log^2 n)(k+\log n)(log d)) bits, where k is the security parameter; (b) It can be based on an arbitrary, semantically secure, length-flexible, additively homomorphic public-key cryptosystem. In particular, the sender-privacy of the new protocols can be based on the assumption that the Decisional Composite Residuosity Problem is hard. The proposed protocols can be transformed to two-round computationally chooser-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocols for elements from Z_d, with the same asymptotical communication, that is secure assuming that the underlying cryptosystem is IND-CPA secure, i.e., in the standard model.

Biography:
Helger Lipmaa received a Ph.D. from the University of Tartu, Estonia, in 1999. At this time, he was mainly working on digital time-stamping, helping to create the technological background necessary for the Estonian law of digital signatures. Since 2001, he has been working as a professor of cryptology at the Helsinki University of Technology, Finland. His research interests are in cryptology. While he has been doing work in many different aspects of cryptology (starting from creating the fastest software implementation of the AES block-cipher and ending with work in the field of theoretical foundations of cryptology), his current work is mainly centered on constructing efficient yet provably secure cryptographic protocols. Recently, he has also been working on privacy-preserving data mining. In the last four years he has published about 20 papers, and served on many program committees. He has been very active in supporting computer science education in Estonia, being a co-organizer of Estonian Winter School of Computer Science (since 1998) and of Estonian Theory Days (since 2002).