Historically, adaptive OT protocols were analyzed with respect to a ``half-simulation'' definition which Naor and Pinkas showed to be flawed. In 2007, Camenisch, Neven, and shelat, and subsequent other works, demonstrated efficient adaptive protocols in the full-simulation model. These protocols, however, all use standard rewinding techniques in their proofs of security and thus are not universally composable. Recently, Peikert, Vaikuntanathan and Waters presented universally composable (UC) non-adaptive OT protocols (for the 1-out-of-2 variant). However, it is not clear how to preserve UC security while extending these protocols to the adaptive k-out-of-N setting. Further, any such attempt would seem to require O(N) computation per transfer for a database of size N. In this work, we present an efficient and UC-secure adaptive k-out-of-N OT protocol, where after an initial commitment to the database, the cost of each transfer is constant. Our construction is secure under bilinear assumptions in the standard model.
Category / Keywords: cryptographic protocols / oblivious transfer, UC security, bilinear maps Publication Info: To appear in ASIACRYPT 2008. Date: received 10 Apr 2008, last revised 28 Oct 2008 Contact author: mgreen at cs jhu edu Available formats: PDF | BibTeX Citation Note: Updated publication information. Version: 20081028:204229 (All versions of this report) Discussion forum: Show discussion | Start new discussion