Oblivious transfer is the humblest-looking primitive (building block) in cryptography and one of the most powerful: a sender offers two messages, a receiver picks one, and afterward the receiver knows only its choice while the sender does not know which was chosen. This article builds it from a post-quantum key-encapsulation mechanism, and shows how to turn a handful of expensive transfers into thousands of cheap ones, which is what the rounding step of the OPRF (the oblivious pseudorandom function at the heart of discovery) needs.
Prerequisites: Lattice Foundations (LWE, the learning-with-errors lattice problem underneath everything here, and the idea of a KEM, a key-encapsulation mechanism). The consumer of this primitive is Rounding by Oblivious Transfer.
1-out-of-2 Oblivious Transfer (OT):
It sounds almost too symmetric to be possible. The receiver gets one message but not the other, and the sender never learns which one was taken.
Yet from this one gadget you can bootstrap essentially all of secure two-party computation. It is a known "complete" primitive: every other secure-computation task can, in principle, be assembled out of it.
For us the use is narrow and concrete. In the OPRF's round two, each coefficient of the PRF (the pseudorandom function the OPRF evaluates) has to be rounded, and the client (the receiver) must obliviously pick the correct rounding from a table the server built, without the server learning which entry it picked (Rounding by Oblivious Transfer).
Why does rounding need OT at all? Because the correct rounded value depends on a secret split between the two parties, and neither is allowed to see the other's half. OT is precisely the tool for "let the receiver select the right answer from a table the sender built, blindly."
The textbook OT is, once again, elegantly short and built on Diffie–Hellman, the classic key-agreement trick behind most of today's encrypted connections.
In the Chou–Orlandi "simplest OT," the receiver sends a group element that is either a real public key or a decoy, depending on its choice bit. The sender encrypts m0 under one and m1 under the other. The receiver can only decrypt the one matching its real key. Two exponentiations, done.
And, once again, it rests on the hardness of the discrete-logarithm problem (the same foundation elliptic-curve cryptography stands on), which Shor's algorithm breaks on a quantum computer.
That matters more here than it might seem, because the OT sits inside the discovery path: it is how round two of the OPRF completes. A classical OT would reintroduce exactly the harvest-now-decrypt-later exposure (an adversary recording traffic today to decrypt it once quantum computers arrive) that we removed everywhere else.
Concretely: an adversary recording the round-two traffic could later, with a quantum computer, recover the receiver's choice bits. In our setting those bits are derived from the secret PRF value.
So the OT has to be post-quantum too. No exceptions inside the discovery path; that discipline is the whole point.
The clean post-quantum route builds OT from a Key-Encapsulation Mechanism, or KEM.
A KEM is the modern shape of public-key encryption. KeyGen makes a keypair (dk, ek): a
decapsulation (private) key and an encapsulation (public) key. Encaps(ek) takes the public half and produces a
ciphertext plus a shared secret. Decaps(dk, ct) recovers that shared secret.
We use ML-KEM-768, the KEM formerly known as Kyber, standardized by NIST (the US standards body) and built on Module-LWE, a structured variant of the LWE problem. Its security is the lattice hardness from Lattice Foundations, so it is post-quantum by construction.
The whole construction turns on one property of good KEMs: a real encapsulation key is
indistinguishable from a random one. An ek is roughly a Module-LWE sample, and to anyone
without the secret it looks uniform, indistinguishable from random noise.
That is what lets the receiver present two keys (one real, one decoy) with the sender unable to tell which is which.
The protocol, with the receiver holding choice bit c:
KeyGen for a real keypair (dk, ek_real) and keep dk. Generate a
second encapsulation key ek_decoy by a method that yields a valid-looking key whose
secret it does not know: sampling it obliviously, or discarding the secret. Arrange the
two into slots (ek_0, ek_1) so that slot c holds the real key and slot 1−c holds the
decoy. Send both.Encaps(ek_b) to get (ct_b, ss_b). Stretch the shared
secret ss_b into mask bits with a key-derivation function, a hash that turns one secret
into as many pseudorandom bits as you need. Use those bits as a one-time pad
over message mb, and send both masked messages with both ciphertexts.ss_c and unmasking mc. For the decoy slot it has no secret, so ss_(1−c) is
pseudorandom to it under Module-LWE, and m1−c stays sealed.Both privacy properties fall out of that.
There is a real subtlety here. A malicious receiver might construct both keys as real, so it can decapsulate both messages and defeat sender privacy.
Hardening against that (making the decoy provably a decoy, or using a committed construction) is the difference between two standard security models. Honest-but-curious means the other side follows the protocol and only snoops on what it legitimately sees. Malicious means it may deviate from the protocol however it likes. Which model you are in is the kind of detail the implementation has to pin down.
The takeaway for this article is narrower: the KEM's indistinguishability of keys is the hinge, and ML-KEM gives us that post-quantumly.
Public-key OT is expensive: each transfer is a couple of KEM operations and a kilobyte or two on the wire. Our rounding step needs one OT per rounded coefficient (potentially thousands), and doing thousands of KEM operations per lookup would be far too slow.
The escape is one of the prettiest results in practical MPC: secure multi-party computation, the study of protocols that compute on inputs the parties will not show each other. The result is OT extension (Ishai–Kilian–Nissim–Petrank, "IKNP," 2003).
It says you can do a small, fixed number of real public-key OTs (a security parameter's worth, the count that sets the overall security level, roughly 128) and then turn them into arbitrarily many OTs using only cheap symmetric-key operations, meaning hashing.
The analogy is a hybrid encryption you already know. You do one expensive public-key handshake to establish a seed, then encrypt gigabytes with a fast symmetric cipher. OT extension is that same move, for oblivious transfer.
The mechanics, in spirit: the base OTs set up correlated random bits between the two parties. A clever transposition (flipping a matrix of those bits along its diagonal) and a hash then extend each correlated seed into a fresh OT whose messages are masked by hash outputs.
So the expensive lattice KEM work is paid once and spread across every later transfer, and each additional transfer costs a couple of hashes. And because the extension is purely symmetric (hash functions like SHAKE, a standard hash with stretch-to-any-length output), it is post-quantum for free, since hashes are quantum-safe with at most a mild parameter bump.
The composition, end to end: a few ML-KEM base OTs (post-quantum public-key) → IKNP extension (post-quantum symmetric) → thousands of cheap OTs.
It is tempting to think extension is optional here. Recall from
The Lattice OPRF that we round only PRESENCE_TRUNC = 32 coefficients
rather than all 512, so truncation already shrank the work 16×.
But each rounded coefficient is a 1-of-256 selection, and a 1-of-256 selection is built from eight 1-of-2 transfers. So 32 coefficients means 256 transfers, plus the "sacrifice" rows the consistency check consumes: extra transfers deliberately opened and thrown away to catch cheating.
That is well past what raw public-key OTs would carry comfortably, and extension amortizes the whole lot onto a fixed 128 ML-KEM base OTs.
We kept the extension machinery for three reasons: it makes the per-coefficient cost negligible, it keeps the design robust if the number of rounded coefficients ever grows, and it matches a standard, well-audited MPC building block rather than a bespoke shortcut. Call it the "use the boring, battle-tested construction" instinct.
It is worth previewing why this particular primitive fits the rounding job so well, because that is what justifies the whole detour.
Rounding a noisy value near a boundary depends on a bit that is secret-shared between client and server. Each holds a random-looking half, and only the two halves together determine the bit, so neither party may see the true value.
Now read the definition of OT again: the receiver selects the correct branch of a two-way table the sender prepared, without either learning the other's secret. That is the same shape.
So the server builds, for each coefficient, a small table encoding "if the shared bit is 0 the rounding is this, and if 1 it is that." The client obliviously pulls the branch matching its own share.
The server learns neither the client's share nor which branch was taken. The client learns only its correct rounded bit. That marriage of OT to rounding is the subject of Rounding by Oblivious Transfer.