We present the first adaptive OT protocol simultaneously satisfying these requirements. The sole complexity assumption required is that given $(g,g^a,g^b,g^c,Q)$, where $g$ generates a bilinear group of prime order $p$ and $a,b,c$ are selected randomly from $\Zp$, it is hard to decide if $Q = g^{abc}$. All prior protocols in the standard model either do not meet our efficiency requirements or require dynamic ``q-based'' assumptions.
Our construction makes an important change to the established ``assisted decryption'' technique for designing adaptive OT. As in prior works, the sender commits to a database of $n$ messages by publishing an encryption of each message and a signature on each encryption. Then, each transfer phase can be executed in time independent of $n$ as the receiver blinds one of the encryptions and proves knowledge of the blinding factors and a signature on this encryption, after which the sender helps the receiver decrypt the chosen ciphertext. One of the main obstacles to designing an adaptive OT scheme from a simple assumption is realizing a suitable signature for this purpose (i.e., enabling signatures on group elements in a manner that later allows for efficient proofs.) We make the observation that a secure signature scheme is not necessary for this paradigm, provided that signatures can only be forged in certain ways. We then show how to efficiently integrate an insecure signature into a secure adaptive OT construction.
Category / Keywords: cryptographic protocols / oblivious transfer, signatures, F-signatures, bilinear maps Publication Info: Full version of work in TCC 2011. Date: received 27 Feb 2010, last revised 14 Jan 2011 Contact author: matthewdgreen at gmail com Available format(s): PDF | BibTeX Citation Version: 20110114:190036 (All versions of this report) Short URL: ia.cr/2010/109 Discussion forum: Show discussion | Start new discussion