On Efficient Non-Interactive Oblivious Transfer with Tamper-Proof Hardware.

Ricardo Faleiro, Manuel Goulão, Leonardo Novo +1 more

Few primitives are as intertwined with the foundations of cryptography as Oblivious Transfer (OT). Not surprisingly, with the advent of quantum information processing, a major research path has emerged, aiming to minimize the requirements necessary to achieve OT by leveraging quantum resources, while also exploring the implications for secure computation. Indeed, OT has been the target of renewed focus regarding its newfound quantum possibilities (and impossibilities), both towards its computation and communication complexity. For instance, non-interactive OT, known to be impossible classically, has been strongly pursued. In its most extreme form, non-interactive chosen-input OT (one-shot OT) is equivalent to a One-Time Memory (OTM). OTMs have been proposed as tamper-proof hardware solutions for constructing One-Time Programs -- single-use programs that execute on an arbitrary input without revealing anything about their internal workings. In this work, we leverage quantum resources in the Noisy-Quantum-Storage Model to achieve: 1. Unconditionally-secure two-message non-interactive OT -- the smallest number of messages known to date for unconditionally-secure chosen-input OT. 2. Computationally-secure one-shot OT/OTM, with everlasting security, assuming only one-way functions and sequential functions -- without requiring trusted hardware, QROM, or pre-shared entanglement. 3. One-Time Programs without the need for hardware-based solutions or QROM, by compiling our OTM construction with the [GKR08, GIS+10] compiler.

Mihir Bellare Y, Silvio M. Micali

Andrew Y. Lindell

Vladimir Kolesnikov

Hossein Ghodosi

Naor and Pinkas (1999a) pointed out that 'this is of interest, given the possibility of implementing Oblivious Transfer using physical means, e.g., via a noisy channel or quantum cryptography. However, some of these reductions are not particularly efficient. .. '. Using tamper-proof smart cards, we propose some radically different approaches to the Oblivious Transfer problem. Despite the simplicity of our model, we achieve unconditional security and privacy for both the sender and receiver. In contrast to all known oblivious transfer protocols, which require extensive computations, the proposed schemes are very computationally efficient.

Ventzislav Nikov, Svetla Nikova⋆, Bart Preneel A +1 more