When I first came across Oblivious Transfer, I found the name a little strange, because the whole point of the protocol is that one party stays “oblivious” — deliberately kept in the dark — about part of the information the other party sends. Quantum Oblivious Transfer (QOT) is the quantum-mechanical version of this idea. I use it to describe a two-party cryptographic primitive where a sender transmits information to a receiver in such a way that the receiver only learns some of it, and the sender never finds out which part the receiver actually got. What makes the quantum version interesting to me is that it uses the physical properties of quantum states — superposition and the no-cloning theorem — to enforce this “obliviousness” in a way that does not rely purely on computational hardness assumptions. I see it as one of the building blocks of secure multi-party computation, and it matters because almost any two-party secure computation can be built once you have a working oblivious transfer primitive.
History and Background
I trace the origin of Oblivious Transfer back to Michael Rabin’s 1981 paper, where he proposed a classical scheme in which a message is transmitted with a 50% chance of arriving. Later, Even, Goldreich, and Lempel reformulated this into the more commonly used “1-out-of-2” oblivious transfer. The quantum version came soon after quantum cryptography itself started gaining attention, largely inspired by Stephen Wiesner’s idea of “quantum money” and conjugate coding from the early 1970s (though it was published only in 1983). Charles Bennett, Gilles Brassard, Claude Crépeau, and Marie-Hélène Skubiszewska were among the first to formally propose a quantum oblivious transfer protocol in the early 1990s, building on the BB84 quantum key distribution idea. I find it interesting that this history is tightly interwoven with quantum bit commitment, since early researchers believed both primitives could be built unconditionally secure using quantum mechanics alone — a belief that was later shown to be only partially true.
Problem Statement
I want to solve the following problem: a sender, whom I will call Alice, holds two secret messages, $m_0$ and $m_1$. A receiver, Bob, wants to learn exactly one of them, say $m_b$ for a bit $b$ that only he chooses. The protocol must guarantee two things at once — Alice must never learn which bit $b$ Bob chose, and Bob must never learn anything about the other message $m_{1-b}$. Classical solutions to this rely on computational assumptions such as the hardness of factoring or discrete logarithms. I use the quantum version because it promises to enforce these guarantees using the laws of physics, particularly the fact that measuring a quantum state disturbs it and that quantum states cannot be perfectly copied.
Core Concepts
Before I explain the mechanism, I want to lay out a few terms I rely on throughout:
- Qubit — the quantum analogue of a bit, represented as a vector in a two-dimensional Hilbert space, $\vert\psi\rangle = \alpha\vert0\rangle + \beta\vert1\rangle$.
- Conjugate bases — two bases, usually the rectilinear basis ${\vert0\rangle,\vert1\rangle}$ and the diagonal basis ${\vert+\rangle,\vert-\rangle}$, such that measuring in the wrong basis gives a random result.
- No-cloning theorem — I rely on the fact that an unknown quantum state cannot be copied exactly, which prevents a dishonest Bob from measuring a qubit in both bases.
- 1-out-of-2 OT ($\binom{2}{1}$-OT) — the standard flavor of oblivious transfer I focus on here, where the receiver gets exactly one of two messages.
How It Works
I break the protocol (following the Bennett–Brassard–Crépeau–Skubiszewska style construction) into the following steps:
- Alice prepares a random sequence of qubits, each one encoding a random classical bit in a randomly chosen basis (rectilinear or diagonal), just like in BB84.
- Alice sends this sequence of qubits to Bob over a quantum channel.
- Bob, for each qubit, randomly chooses a basis to measure in and records the outcome. Because Bob does not know Alice’s original basis choices, roughly half of his measurements will be in the wrong basis and thus produce essentially random, unusable bits.
- Alice announces her basis choices over a public classical channel (but not the actual bit values).
- Bob tells Alice which of his measurements were made in the same basis as hers — these positions form a shared, correct sub-string that Bob knows with certainty, and the rest are noise-corrupted from Bob’s perspective.
- Crucially, Bob does not tell Alice which of his measurements matched — instead, he privately splits the qubit positions into two disjoint sets, one for a string he will use to decode $m_0$ and one for $m_1$, and reports these sets to Alice without revealing which set actually corresponds to his correctly-measured bits.
- Alice uses the announced sets to build two masks, and sends $m_0 \oplus \text{mask}_0$ and $m_1 \oplus \text{mask}_1$ to Bob over the classical channel.
- Bob can only successfully remove the mask for the set where he actually knows the correct measurement outcomes, so he recovers exactly one message and the other stays hidden behind random noise he cannot correct.
Working Principle
I think of the internal logic in terms of a race between Alice’s honesty and Bob’s uncertainty. Because Bob must commit to a measurement basis before Alice reveals her own basis choices, he is physically prevented from getting both possible readings of any qubit — trying to preserve the qubit unmeasured, or copying it, is blocked by the no-cloning theorem. This asymmetry of information — Bob knows some bits correctly but not which combination Alice will need to protect the other message — is what forces the “obliviousness.” At the same time, Alice cannot tell which qubits Bob measured correctly, because that information was never sent back to her; only the partitioned sets are, and both partitions look symmetric to her.
Mathematical Foundation
I represent Alice’s qubits using the four BB84 states:
$$ \vert0\rangle,\ \vert1\rangle,\ \vert+\rangle = \frac{\vert0\rangle+\vert1\rangle}{\sqrt2},\ \vert-\rangle = \frac{\vert0\rangle-\vert1\rangle}{\sqrt2} $$
If Bob measures in the wrong basis, quantum mechanics tells me the outcome is uniformly random:
$$ P(\text{correct outcome} \mid \text{wrong basis}) = \frac{1}{2} $$
The expected fraction of qubits Bob measures correctly is:
$$ E[\text{correct fraction}] = \frac{1}{2} $$
The final masking step uses a one-time-pad style XOR:
$$ c_0 = m_0 \oplus k_0, \qquad c_1 = m_1 \oplus k_1 $$
where $k_0, k_1$ are keys derived from the two partitioned sets of qubit outcomes. Bob can only compute $m_b = c_b \oplus k_b$ correctly for the set $b$ where his measurement outcomes are error-free with overwhelming probability, while the other key is effectively random from his point of view, so $c_{1-b} \oplus k_{1-b}’$ (his guessed key) reveals nothing useful about $m_{1-b}$.
Diagrams
sequenceDiagram
participant A as Alice
participant B as Bob
A->>B: Sends qubits in random bases
B->>B: Measures each qubit in a random basis
A->>B: Announces her basis choices (public channel)
B->>A: Sends two disjoint index sets (not revealing which is correct)
A->>B: Sends m0 XOR key0 and m1 XOR key1
B->>B: Recovers only mb using the correct index setPseudocode
Protocol QuantumOT(m0, m1):
Alice:
for i in 1..n:
bit[i] = random(0,1)
basis[i] = random(RECT, DIAG)
qubit[i] = encode(bit[i], basis[i])
send qubit[1..n] to Bob
Bob:
for i in 1..n:
bBasis[i] = random(RECT, DIAG)
result[i] = measure(qubit[i], bBasis[i])
choose b in {0,1} // Bob's secret choice
(set0, set1) = partition(1..n) // one set matches Alice basis, order kept secret
send (set0, set1) to Alice
Alice:
receive basis[1..n] known already
key0 = deriveKey(bit values restricted to set0)
key1 = deriveKey(bit values restricted to set1)
c0 = m0 XOR key0
c1 = m1 XOR key1
send (c0, c1) to Bob
Bob:
kb = deriveKey(result values restricted to setb) // reliable only for correct set
mb = cb XOR kb
output mb
Step-by-Step Example
Suppose I let Alice prepare 8 qubits with the following bits and bases:
| Position | Bit | Basis |
|---|---|---|
| 1 | 0 | RECT |
| 2 | 1 | DIAG |
| 3 | 1 | RECT |
| 4 | 0 | DIAG |
| 5 | 1 | RECT |
| 6 | 0 | RECT |
| 7 | 1 | DIAG |
| 8 | 0 | DIAG |
Bob measures with his own random bases: RECT, RECT, RECT, DIAG, DIAG, RECT, DIAG, RECT. Comparing to Alice’s bases, Bob’s measurements are correct at positions 1, 3, 4, 6, 7 (five out of eight, close to the expected half). Bob privately splits positions into set0 = {1,3,6,8} and set1 = {2,4,5,7}, choosing to place mostly-correct positions into set0 because he wants $m_0$. Alice, using her known bit values restricted to each set, derives key0 and key1, and sends the two masked messages. Bob, only trusting set0 (which he engineered to overlap heavily with his correct measurements), successfully strips the mask off $m_0$, while $m_1$’s mask uses position 8 where Bob’s basis did not match, so his recovered value is scrambled.
Time Complexity
I measure QOT’s complexity in terms of the number of qubits $n$ transmitted. State preparation, transmission, and measurement are each $O(n)$ operations. The classical post-processing — basis comparison, partitioning, and XOR masking — is also $O(n)$. So the overall time complexity is:
$$ T(n) = O(n) $$
There is no meaningfully different best, average, or worst case here since every qubit undergoes the same fixed sequence of operations regardless of outcome.
Space Complexity
I need to store $n$ qubits (or their classical descriptions during simulation), $n$ basis bits for Alice, $n$ measurement results for Bob, and two index sets of size up to $n$. This gives:
$$ S(n) = O(n) $$
Correctness Analysis
I consider the protocol correct if, whenever both parties are honest, Bob reliably recovers exactly the message he intended and learns nothing usable about the other. This follows from two facts: first, when Bob measures in the same basis Alice used, quantum mechanics guarantees he reads the correct bit with certainty (ignoring channel noise); second, when the bases differ, the outcome is uniformly random and independent of the true bit, so no information leaks. As long as Bob genuinely commits to his basis choices before Alice reveals hers, and as long as no cloning of the original qubits is possible, the scheme is correct and oblivious under the standard formalism.
Advantages
- Security does not depend solely on unproven computational hardness assumptions.
- Impossible for Bob to secretly learn both messages due to the no-cloning theorem.
- Naturally composes with other quantum protocols such as quantum key distribution.
- Provides a foundation for building general secure multi-party computation.
Disadvantages
- Requires real quantum hardware (single-photon sources, quantum channels), which is expensive and error-prone.
- Vulnerable to practical side-channel attacks not modeled in the idealized theory.
- Later theoretical work (Lo’s impossibility results) showed that unconditionally secure OT cannot be achieved by quantum communication alone without additional assumptions, similar to bit commitment.
- Noise in real quantum channels reduces the raw key rate significantly.
Applications
- Secure multi-party computation protocols that need OT as a primitive.
- Privacy-preserving auctions and voting systems.
- Secure database queries where a client retrieves one record without the server learning which one.
- Quantum-safe cryptographic toolkits being explored for post-quantum-secure infrastructure.
Implementation in C
Because real QOT needs quantum hardware, I implement a classical simulation of the protocol so the logic can be studied and tested.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 16 /* number of simulated qubits */
/* Simulated qubit: a bit and the basis it was encoded in (0 = RECT, 1 = DIAG) */
typedef struct {
int bit;
int basis;
} Qubit;
int random_bit() { return rand() % 2; }
int main() {
srand((unsigned)time(NULL));
Qubit qubits[N];
int aliceBits[N], aliceBasis[N];
int bobBasis[N], bobResult[N];
/* Step 1: Alice prepares random bits and bases */
for (int i = 0; i < N; i++) {
aliceBits[i] = random_bit();
aliceBasis[i] = random_bit();
qubits[i].bit = aliceBits[i];
qubits[i].basis = aliceBasis[i];
}
/* Step 2 & 3: Bob measures with his own random bases */
for (int i = 0; i < N; i++) {
bobBasis[i] = random_bit();
if (bobBasis[i] == qubits[i].basis) {
bobResult[i] = qubits[i].bit; /* correct measurement */
} else {
bobResult[i] = random_bit(); /* random outcome, wrong basis */
}
}
/* Step 4: Alice reveals her bases publicly */
/* Step 5: Bob finds positions where bases matched */
int matchCount = 0;
int matchIndex[N];
for (int i = 0; i < N; i++) {
if (bobBasis[i] == aliceBasis[i]) {
matchIndex[matchCount++] = i;
}
}
printf("Bob matched %d out of %d positions.\n", matchCount, N);
/* Bob picks his desired message index b and builds set0/set1 without revealing b */
int b = 0; /* Bob wants m0 */
int m0 = 0b1010, m1 = 0b0101; /* Alice's two 4-bit messages, simplified */
/* For simplicity, derive a 4-bit key from the first 4 matched positions for set b */
int key = 0;
for (int i = 0; i < 4 && i < matchCount; i++) {
key = (key << 1) | qubits[matchIndex[i]].bit;
}
int c0 = m0 ^ key;
int recovered_m0 = c0 ^ key; /* Bob can reproduce key because his measurement matched */
printf("Alice's m0 = %d, recovered m0 by Bob = %d\n", m0, recovered_m0);
(void)m1; (void)b;
return 0;
}
I keep this implementation deliberately simplified: it captures the essential logic (random basis mismatch causing noise, and correct-basis positions giving a reliable shared key) without needing an actual quantum simulator.
Sample Input and Output
Given the random nature of the protocol, a typical run might print:
Bob matched 9 out of 16 positions.
Alice's m0 = 10, recovered m0 by Bob = 10
The exact match count varies each run since it depends on random basis choices, but it hovers around half of $N$.
Optimization Techniques
- Increasing $n$ improves the statistical reliability of the matched-position key at the cost of more qubits.
- Using error-correcting codes (like Cascade or LDPC, borrowed from QKD) helps reconcile small discrepancies from real channel noise.
- Privacy amplification via universal hashing reduces any residual information Alice might have about Bob’s choice.
- Batching multiple OT instances together (OT extension) reduces the number of expensive quantum operations needed for large numbers of transfers.
Common Mistakes
- Assuming quantum communication alone gives unconditional security without accounting for the impossibility results proven later by Lo and others.
- Forgetting that Bob must commit to his basis before Alice reveals hers — revealing early breaks obliviousness.
- Not distinguishing between the “all bits” case and the proper $\binom{2}{1}$-OT case, which requires the careful two-set partitioning step.
- Ignoring channel noise in real implementations, which can leak partial information if not handled with proper reconciliation and privacy amplification.
Further Reading
- Bennett, C. H., Brassard, G., Crépeau, C., Skubiszewska, M.-H., “Practical Quantum Oblivious Transfer,” CRYPTO 1991. https://link.springer.com/chapter/10.1007/3-540-46766-1_29
- Crépeau, C., “Equivalence Between Two Flavours of Oblivious Transfers,” CRYPTO 1987. https://link.springer.com/chapter/10.1007/3-540-48184-2_31
- Lo, H.-K., “Insecurity of Quantum Secure Computations,” Physical Review A, 1997. https://arxiv.org/abs/quant-ph/9611031
- Wiesner, S., “Conjugate Coding,” ACM SIGACT News, 1983. https://dl.acm.org/doi/10.1145/1008908.1008920
- Bennett, C. H., Brassard, G., “Quantum Cryptography: Public Key Distribution and Coin Tossing,” 1984 (the original BB84 paper). https://arxiv.org/abs/2003.06557 (modern reprint/annotated version)
