Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.08367

Non-Interactive Oblivious Transfer and One-Time Programs from Noisy Quantum Storage

Ricardo Faleiro, Manuel Goulão, Leonardo Novo, Emmanuel Zambrini Cruzeiro

Published Oct 10, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2410.08367

Related papers

Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].

arXiv:1511.01363•Leibniz international proceedings in informatics•Nov 4, 2015•5 citations

Towards Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ( i.e. , reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114 n adaptive queries to the token (for n the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.

arXiv:1810.05226•Quantum•Apr 8, 2021•9 citations

Oblivious transfer and quantum non-locality

Stefan Wolf, Jürg Wullschleger

Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT

arXiv:quant-ph/0502030•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•55 citations

Error-tolerant oblivious transfer in the noisy-storage model

Cosmo Lupo, James T. Peat, Erika Andersson +1 more

The noisy-storage model of quantum cryptography allows for information-theoretically secure two-party computation based on the assumption that a cheating user has at most access to an imperfect, noisy quantum memory, whereas the honest users do not need a quantum memory at all. In general, the more noisy the quantum memory of the cheating user, the more secure the implementation of oblivious transfer, which is a primitive that allows universal secure two-party and multiparty computation. For experimental implementations of oblivious transfer, one has to consider that also the devices held by the honest users are lossy and noisy, and error correction needs to be applied to correct these trusted errors. The latter are expected to reduce the security of the protocol, since a cheating user may hide themselves in the trusted noise. Here we leverage entropic uncertainty relations to derive tight bounds on the security of oblivious transfer with a trusted and untrusted noise. In particular, we discuss noisy storage and bounded storage, with independent and correlated noise.

arXiv:2302.04236•Physical Review Research•Sep 7, 2023•8 citations

Building one-time memories from isolated qubits

Yi-Kai Liu

One-time memories (OTM's) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM's using quantum mechanical devices. It is known that OTM's cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on isolated qubits - qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements.

arXiv:1304.5007•Conference on Innovations in Theoretical Computer Science•Jan 12, 2014•12 citations

All-or-nothing oblivious transfer based on the quantum one-way function

Ping Wang, Yiting Su, Zhiwei Sun

Oblivious transfer (OT) is one of the keystones of secure multi-party computation. It is generally believed that unconditionally secure OT is impossible. In this article, we propose a practical and secure quantum all-or-nothing oblivious transfer protocol based on the quantum one-way function. The protocol is built upon a quantum public-key encryption construction, and its security relies on the no-cloning theorem and no-communication theorem. Practical security is reflected in limitations on non-demolition measurements.

Frontiers in Physics•Aug 9, 2022•4 citations
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.
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ( i.e. , reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114 n adaptive queries to the token (for n the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.
Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT
The noisy-storage model of quantum cryptography allows for information-theoretically secure two-party computation based on the assumption that a cheating user has at most access to an imperfect, noisy quantum memory, whereas the honest users do not need a quantum memory at all. In general, the more noisy the quantum memory of the cheating user, the more secure the implementation of oblivious transfer, which is a primitive that allows universal secure two-party and multiparty computation. For experimental implementations of oblivious transfer, one has to consider that also the devices held by the honest users are lossy and noisy, and error correction needs to be applied to correct these trusted errors. The latter are expected to reduce the security of the protocol, since a cheating user may hide themselves in the trusted noise. Here we leverage entropic uncertainty relations to derive tight bounds on the security of oblivious transfer with a trusted and untrusted noise. In particular, we discuss noisy storage and bounded storage, with independent and correlated noise.
One-time memories (OTM's) are simple tamper-resistant cryptographic devices, which can be used to implement one-time programs, a very general form of software protection and program obfuscation. Here we investigate the possibility of building OTM's using quantum mechanical devices. It is known that OTM's cannot exist in a fully-quantum world or in a fully-classical world. Instead, we propose a new model based on isolated qubits - qubits that can only be accessed using local operations and classical communication (LOCC). This model combines a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits), and can be implemented using current technologies, such as nitrogen vacancy centers in diamond. In this model, we construct OTM's that are information-theoretically secure against one-pass LOCC adversaries that use 2-outcome measurements.
Oblivious transfer (OT) is one of the keystones of secure multi-party computation. It is generally believed that unconditionally secure OT is impossible. In this article, we propose a practical and secure quantum all-or-nothing oblivious transfer protocol based on the quantum one-way function. The protocol is built upon a quantum public-key encryption construction, and its security relies on the no-cloning theorem and no-communication theorem. Practical security is reflected in limitations on non-demolition measurements.