Practical Adaptive Oblivious Transfer from Simple Assumptions
Matthew Green, Susan Hohenberger · 2011
In an adaptive oblivious transfer (OT) protocol, a sender commits to a database of messages and then repeatedly interacts with a receiver in such a way that the receiver obtains one message per interaction of his choice (and nothing more) while the sender learns nothing about any of the choices. Recently, there has been significant effort to design practical adaptive OT schemes and to use these protocols as a building block for larger database applications. To be well suited for these applications, the underlying OT protocol should: (1) support an efficient initialization phase where one commitment can support an arbitrary number of receivers who are guaranteed of having the same view of the database, (2) execute transfers in time independent of the size of the database, and (3) satisfy a strong notion of security under a simple assumption in the standard model. 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