On the Feasibility of Extending Oblivious Transfer

Yehuda Lindell, Hila Zarosim

Enrique Larraia

Yuval Ishai, Joe Kilian, Kobbi Nissim B +1 more

Yehuda Lindell, Hila Zarosim

Oblivious transfer is one of the most basic and important building blocks in cryptography. As such, understanding its cost is of prime importance. Beaver (STOC 1996) showed that it is possible to obtain poly(n) oblivious transfers given only n actual oblivious transfer calls and using one-way functions, where n is the security parameter. In addition, he showed that it is impossible to extend oblivious transfer information theoretically. The notion of extending oblivious transfer is important theoretically (to understand the complexity of computing this primitive) and practically (since oblivious transfers can be expensive and thus extending them using only one-way functions is very attractive). Despite its importance, very little is known about the feasibility of extending oblivious transfer, beyond the fact that it is impossible information theoretically. Specifically, it is not known whether or not one-way functions are actually necessary for extending oblivious transfer, whether or not it is possible to extend oblivious transfers with adaptive security, and whether or not it is possible to extend oblivious transfers when starting with just a few. In this paper, we address these questions and provide almost complete answers to all of them. We show that the existence of any oblivious transfer extension protocol with security for static semihonest adversaries implies one-way functions, that an oblivious transfer extension protocol with adaptive security implies oblivious transfer with static security, and that the existence of an oblivious transfer extension protocol from only O(log n) oblivious transfers implies oblivious transfer itself.

Christian Cachin

Mariana F. Ramos, Michael Hentschel, Federico Valbusa +7 more

We present an experimentally feasible implementation of a secure multiparty computation application enabled by quantum oblivious transfer (QOT) on an entanglement-based physical layer. The QOT protocol uses polarization-encoded entangled states to share oblivious keys between two parties with quantum key distribution (QKD) providing authentication. Our system integrates the post-processing for QOT and QKD, both sharing a single physical layer, ensuring efficient key generation and authentication, respectively. Authentication involves hashing messages into a cryptographic context, verifying tags, and replenishing keys. This process uses a parallel QKD pipeline specifically for authentication, not for secure key generation. Oblivious keys are generated over a distance up to 25.8 km with a channel loss of 8.47 dB. In a back-to-back setup, a QOT rate of [Formula: see text] OTs/second is achieved, corresponding to 1 minute and 53 seconds per OT, primarily limited by the entanglement source. Using pre-distributed oblivious keys improved the rate to 0.11 OTs/second, or 9.1 seconds per OT. The considered QOT protocol is statistically correct, computationally secure for an honest receiver, and statistically secure for an honest sender, assuming a computationally hiding, statistically binding commitment. An experimentally feasible use case is demonstrated for privacy-preserving fingerprint matching against no-fly lists for border control. The fingerprint is secret-shared across two sites, ensuring security, while the matching is performed using the MASCOT protocol, supported by QOT. The application required 128 1-out-of-2 OTs, each with message length of 128 bits, with the highest security achieved in 20 minutes and 39 seconds. This work demonstrates the feasibility of QOT in secure quantum communication applications.