Revision History for: Oblivious Transfer
- 2025-06-24 at 21:25 by JuliaM
Functionality Description
Oblivious Transfer (OT) is a foundational two-party cryptographic functionality. It enables a sender to transfer part of their data to a receiver in such a way that:
- The sender does not learn which part was received.
- The receiver learns only the chosen part, and nothing about the rest.
The most common variant is 1-out-of-2 OT, denoted as $OT_{1-2}$, in which:
The sender holds two messages $m_0 , m_1 \\\in \\\{0,1\\\}^n$
The receiver holds a choice bit $b \\\in \\\{0,1\\\}$
The receiver learns $m_b$ and gains no information about $m_{1-b}$
The sender learns nothing about $b$.This makes OT a core primitive for secure two-party computation (2PC) and multi-party computation (MPC).
Protocols
No protocols implement this functionality yet.
Classical Analogues
OT is a classical functionality. OT was first introduced by Michael Rabin in 1981 [1] as “Rabin OT”, where the sender sends a message to the receiver, who obtains it with probability 1/2, and the sender does not know whether it was received.
The 1-out-of-2 OT variant was introduced later by Even, Goldreich, and Lempel in 1985 [2] and became the standard formulation.
Classically, OT can be built using the following tools:
- Public-key cryptography (e.g., Diffie-Hellman, RSA).
- Assumptions like Learning With Errors (LWE) for post-quantum security.
Real-world Use Cases
OT is an important cryptographic primitive that unlocks a variety of cryptographic protocols, such as:
- Secure Two-Party Computation (2PC): All known 2PC protocols reduce to OT.
- Private Set Intersection (PSI) and Private Information Retrieval (PIR).
- Zero-Knowledge Proofs: OT enables secure simulation and extraction in ZK protocols.
- Oblivious RAM (ORAM): Used for secure memory access patterns.
- Password-Based Authentication: OT enables password checks without revealing the password.
Properties
To state the formal properties of this functionality let the $\\\mathtt{Sender}(m_0, m_1)$ and the $\\\mathtt{Receiver}(b)$ be the parties, then an OT has the following properties:
Correctness: The honest receiver outputs $m_b$ with probability: $\\\text{Pr} [\\\text{Receiver outputs} m_b] = 1$.
Receiver Privacy: The sender’s view is statistically/computationally independent of the receiver’s choice bit $b$.
Sender Privacy: The receiver’s view reveals no information about $m_{1-b}$, beyond negligible in statistical or computational distance.The OT is impossible to achieve both-ways security, classically or quantumly[3] in the information-theoretic way.
The security of OT can be:
- Information-theoretic (in one direction).
- Computational (based on standard assumptions).
- Statistical (in bounded-storage or hybrid models).
The computational OT can be constructed based on One-Wayness or Indistinguishability:
- Based on the hardness of inverting or distinguishing encrypted messages (e.g., ElGamal).
- In quantum-resistant OT, based on LWE or code-based assumptions.
In the Universal Composable (UC) framework, OT is composable and serves as a universal primitive. Any general secure computation protocol can be built from OT based on the result of Kilian [5].
In the quantum world as well, OT can be constructed under different sets of assumptions.
Further Information
Quantum OT schemes:
OT protocols can be constructed using quantum communication + computational assumptions:- Mahadev-style classical-verifier quantum protocols.
- LWE-based secure OT with post-quantum security.
Or alternatively in Relativistic settings [5], or the Bounded-quantum-storage model [6]
There are also quantum protocols with one-sided information-theoretic security, i.e. the Receiver is guaranteed full security; the sender has computational security (or vice versa).
Related Primitives
- Bit Commitment and OT are inter-reducible in many settings.
- Random OT (ROT): Variant where the sender’s messages are randomly chosen.
- OT with Abort or Fairness: OT with conditions where one party can halt the protocol but not gain unfair advantage
References
- Rabin, Michael O. “How to exchange secrets with oblivious transfer.” Cryptology ePrint Archive (2005).
- Even, Shimon, Oded Goldreich, and Abraham Lempel. “A randomized protocol for signing contracts.” Communications of the ACM 28, no. 6 (1985): 637-647.
- Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
- Kilian, Joe. “Founding crytpography on oblivious transfer.” In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 20-31. 1988.
- Kent, Adrian. “Location-oblivious data transfer with flying entangled qudits.” Physical Review A—Atomic, Molecular, and Optical Physics 84, no. 1 (2011): 012328.
- Damgård, Ivan B., Serge Fehr, Louis Salvail, and Christian Schaffner. “Cryptography in the bounded-quantum-storage model.” SIAM Journal on Computing 37, no. 6 (2008): 1865-1890.
- 2025-05-16 at 09:18 by JuliaM
Functionality Description
Oblivious Transfer (OT) is a foundational two-party cryptographic functionality. It enables a sender to transfer part of their data to a receiver in such a way that:
- The sender does not learn which part was received.
- The receiver learns only the chosen part, and nothing about the rest.
The most common variant is 1-out-of-2 OT, denoted as $OT_{1-2}$, in which:
The sender holds two messages $m_0 , m_1 \\\in \\\{0,1\\\}^n$
The receiver holds a choice bit $b \\\in \\\{0,1\\\}$
The receiver learns $m_b$ and gains no information about $m_{1-b}$
The sender learns nothing about $b$.This makes OT a core primitive for secure two-party computation (2PC) and multi-party computation (MPC).
Classical Analogues
OT is a classical functionality. OT was first introduced by Michael Rabin in 1981 [1] as “Rabin OT”, where the sender sends a message to the receiver, who obtains it with probability 1/2, and the sender does not know whether it was received.
The 1-out-of-2 OT variant was introduced later by Even, Goldreich, and Lempel in 1985 [2] and became the standard formulation.
Classically, OT can be built using the following tools:
- Public-key cryptography (e.g., Diffie-Hellman, RSA).
- Assumptions like Learning With Errors (LWE) for post-quantum security.
Real-world Use Cases
OT is an important cryptographic primitive that unlocks a variety of cryptographic protocols, such as:
- Secure Two-Party Computation (2PC): All known 2PC protocols reduce to OT.
- Private Set Intersection (PSI) and Private Information Retrieval (PIR).
- Zero-Knowledge Proofs: OT enables secure simulation and extraction in ZK protocols.
- Oblivious RAM (ORAM): Used for secure memory access patterns.
- Password-Based Authentication: OT enables password checks without revealing the password.
Properties
To state the formal properties of this functionality let the $\\\mathtt{Sender}(m_0, m_1)$ and the $\\\mathtt{Receiver}(b)$ be the parties, then an OT has the following properties:
Correctness: The honest receiver outputs $m_b$ with probability: $\\\text{Pr} [\\\text{Receiver outputs} m_b] = 1$.
Receiver Privacy: The sender’s view is statistically/computationally independent of the receiver’s choice bit $b$.
Sender Privacy: The receiver’s view reveals no information about $m_{1-b}$, beyond negligible in statistical or computational distance.The OT is impossible to achieve both-ways security, classically or quantumly[3] in the information-theoretic way.
The security of OT can be:
- Information-theoretic (in one direction).
- Computational (based on standard assumptions).
- Statistical (in bounded-storage or hybrid models).
The computational OT can be constructed based on One-Wayness or Indistinguishability:
- Based on the hardness of inverting or distinguishing encrypted messages (e.g., ElGamal).
- In quantum-resistant OT, based on LWE or code-based assumptions.
In the Universal Composable (UC) framework, OT is composable and serves as a universal primitive. Any general secure computation protocol can be built from OT based on the result of Kilian [5].
In the quantum world as well, OT can be constructed under different sets of assumptions.
Further Information
Quantum OT schemes:
OT protocols can be constructed using quantum communication + computational assumptions:- Mahadev-style classical-verifier quantum protocols.
- LWE-based secure OT with post-quantum security.
Or alternatively in Relativistic settings [5], or the Bounded-quantum-storage model [6]
There are also quantum protocols with one-sided information-theoretic security, i.e. the Receiver is guaranteed full security; the sender has computational security (or vice versa).
Related Primitives
- Bit Commitment and OT are inter-reducible in many settings.
- Random OT (ROT): Variant where the sender’s messages are randomly chosen.
- OT with Abort or Fairness: OT with conditions where one party can halt the protocol but not gain unfair advantage
References
- Rabin, Michael O. “How to exchange secrets with oblivious transfer.” Cryptology ePrint Archive (2005).
- Even, Shimon, Oded Goldreich, and Abraham Lempel. “A randomized protocol for signing contracts.” Communications of the ACM 28, no. 6 (1985): 637-647.
- Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
- Kilian, Joe. “Founding crytpography on oblivious transfer.” In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 20-31. 1988.
- Kent, Adrian. “Location-oblivious data transfer with flying entangled qudits.” Physical Review A—Atomic, Molecular, and Optical Physics 84, no. 1 (2011): 012328.
- Damgård, Ivan B., Serge Fehr, Louis Salvail, and Christian Schaffner. “Cryptography in the bounded-quantum-storage model.” SIAM Journal on Computing 37, no. 6 (2008): 1865-1890.
- 2025-05-15 at 20:23 by Mina Doosti
Functionality Description
Oblivious Transfer (OT) is a foundational two-party cryptographic functionality. It enables a sender to transfer part of their data to a receiver in such a way that:
- The sender does not learn which part was received.
- The receiver learns only the chosen part, and nothing about the rest.
The most common variant is 1-out-of-2 OT, denoted as $OT_{1-2}$, in which:
The sender holds two messages $m_0 , m_1 in {0,1}^n$
The receiver holds a choice bit $b in {0,1}$
The receiver learns $m_b$ and gains no information about $m_{1-b}$
The sender learns nothing about $b$.This makes OT a core primitive for secure two-party computation (2PC) and multi-party computation (MPC).
Protocols
No protocols implement this functionality yet.
Classical Analogues
OT is a classical functionality. OT was first introduced by Michael Rabin in 1981 [1] as “Rabin OT”, where the sender sends a message to the receiver, who obtains it with probability 1/2, and the sender does not know whether it was received.
The 1-out-of-2 OT variant was introduced later by Even, Goldreich, and Lempel in 1985 [2] and became the standard formulation.
Classically, OT can be built using the following tools:
- Public-key cryptography (e.g., Diffie-Hellman, RSA).
- Assumptions like Learning With Errors (LWE) for post-quantum security.
Real-world Use Cases
OT is an important cryptographic primitive that unlocks a variety of cryptographic protocols, such as:
- Secure Two-Party Computation (2PC): All known 2PC protocols reduce to OT.
- Private Set Intersection (PSI) and Private Information Retrieval (PIR).
- Zero-Knowledge Proofs: OT enables secure simulation and extraction in ZK protocols.
- Oblivious RAM (ORAM): Used for secure memory access patterns.
- Password-Based Authentication: OT enables password checks without revealing the password.
Properties
To state the formal properties of this functionality let the $mathtt{Sender}(m_0, m_1)$ and the $mathtt{Receiver}(b)$ be the parties, then an OT has the following properties:
Correctness: The honest receiver outputs $m_b$ with probability: $text{Pr} [text{Receiver outputs} m_b] = 1$.
Receiver Privacy: The sender’s view is statistically/computationally independent of the receiver’s choice bit $b$.
Sender Privacy: The receiver’s view reveals no information about $m_{1-b}$, beyond negligible in statistical or computational distance.The OT is impossible to achieve both-ways security, classically or quantumly[3] in the information-theoretic way.
The security of OT can be:
- Information-theoretic (in one direction).
- Computational (based on standard assumptions).
- Statistical (in bounded-storage or hybrid models).
The computational OT can be constructed based on One-Wayness or Indistinguishability:
- Based on the hardness of inverting or distinguishing encrypted messages (e.g., ElGamal).
- In quantum-resistant OT, based on LWE or code-based assumptions.
In the Universal Composable (UC) framework, OT is composable and serves as a universal primitive. Any general secure computation protocol can be built from OT based on the result of Kilian [5].
In the quantum world as well, OT can be constructed under different sets of assumptions.
Further Information
Quantum OT schemes:
OT protocols can be constructed using quantum communication + computational assumptions:- Mahadev-style classical-verifier quantum protocols.
- LWE-based secure OT with post-quantum security.
Or alternatively in Relativistic settings [5], or the Bounded-quantum-storage model [6]
There are also quantum protocols with one-sided information-theoretic security, i.e. the Receiver is guaranteed full security; the sender has computational security (or vice versa).
Related Primitives
- Bit Commitment and OT are inter-reducible in many settings.
- Random OT (ROT): Variant where the sender’s messages are randomly chosen.
- OT with Abort or Fairness: OT with conditions where one party can halt the protocol but not gain unfair advantage
References
- Rabin, Michael O. “How to exchange secrets with oblivious transfer.” Cryptology ePrint Archive (2005).
- Even, Shimon, Oded Goldreich, and Abraham Lempel. “A randomized protocol for signing contracts.” Communications of the ACM 28, no. 6 (1985): 637-647.
- Lo, Hoi-Kwong. “Insecurity of quantum secure computations.” Physical Review A 56, no. 2 (1997): 1154.
- Kilian, Joe. “Founding crytpography on oblivious transfer.” In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 20-31. 1988.
- Kent, Adrian. “Location-oblivious data transfer with flying entangled qudits.” Physical Review A—Atomic, Molecular, and Optical Physics 84, no. 1 (2011): 012328.
- Damgård, Ivan B., Serge Fehr, Louis Salvail, and Christian Schaffner. “Cryptography in the bounded-quantum-storage model.” SIAM Journal on Computing 37, no. 6 (2008): 1865-1890.