HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: Post-Quantum Oblivious Transfer

7 min read

Oblivious transfer is the humblest-looking primitive 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 OPRF's rounding step needs.

Prerequisites: Lattice Foundations (LWE, and the idea of a KEM). The consumer of this primitive is Rounding by Oblivious Transfer.

1. The primitive

1-out-of-2 Oblivious Transfer (OT):

  • The sender has two messages, m₀ and m₁.
  • The receiver has a choice bit c ∈ {0, 1}.
  • After the protocol, the receiver learns m_c — and only m_c, nothing about the other message.
  • The sender learns nothing about c.

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. For us the use is narrow and concrete: in the OPRF's round two, each PRF coefficient needs to be rounded, and the client (receiver) must obliviously pick the correct rounding of a server-provided table without the server (sender) learning which entry it picked (article 08).

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."

2. The classical construction, and why it fails us

The textbook OT is, once again, elegantly short and built on Diffie–Hellman. 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 m₀ under one and m₁ 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 discrete log in a group, which Shor breaks. Since the OT is 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 we removed everywhere else. An adversary recording the round-two traffic could, post-quantum, recover the receiver's choice bits, which in our setting 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.

3. OT from a KEM: the ML-KEM-768 construction

The clean post-quantum route builds OT from a Key-Encapsulation Mechanism (KEM). A KEM is the modern shape of public-key encryption: KeyGen makes a keypair (dk, ek); Encaps(ek) takes a public encapsulation key and produces a ciphertext plus a shared secret; Decaps(dk, ct) recovers the shared secret. We use ML-KEM-768 — the NIST-standardized, Module-LWE-based KEM (formerly Kyber). Its security is the lattice hardness from article 01, so it is post-quantum by construction.

The 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, which looks uniform to anyone without the secret. That lets the receiver present two keys — one real, one decoy — such that the sender cannot tell which is which.

The protocol (receiver has choice bit c):

  1. Receiver. Run KeyGen to get a real keypair (dk, ek_real) — it keeps dk. Generate a second encapsulation key ek_decoy by a method that yields a valid-looking key for which it does not know the secret (e.g., sample it obliviously / discard the secret). It arranges the two keys into slots (ek_0, ek_1) so that slot c holds ek_real and slot 1−c holds ek_decoy. It sends both keys.
  2. Sender. For each slot b ∈ {0,1}, run Encaps(ek_b) to get (ct_b, ss_b), then use the shared secret ss_b as a one-time pad (via a hash/KDF) to mask message m_b. Send both masked messages and both ciphertexts.
  3. Receiver. It can decapsulate only the slot whose secret it kept — slot c, the real key — recovering ss_c and unmasking m_c. For the decoy slot it does not know the secret, so ss_{1−c} is pseudorandom to it (Module-LWE), and m_{1−c} stays hidden.

Both privacy properties fall out:

  • Receiver privacy (sender learns nothing about c): the two keys are indistinguishable (real ek vs. decoy both look like uniform Module-LWE samples), so the sender cannot tell which slot is real.
  • Sender privacy (receiver learns only m_c): recovering m_{1−c} would require the decoy slot's shared secret, which is pseudorandom under Module-LWE without the discarded key.

There is a real subtlety — a malicious receiver might try to construct both keys as real, so it can decapsulate both messages and defeat sender privacy. Hardening against that (making the decoy provably decoy, or using a committed construction) is the difference between "honest-but- curious" and "malicious" security, and it is the kind of detail the implementation pins down. The takeaway for this article: the KEM's indistinguishability of keys is the hinge, and ML-KEM gives it to us post-quantumly.

4. The cost problem, and OT extension

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: OT extension (Ishai–Kilian– Nissim–Petrank, "IKNP," 2003). It says you can do a small, fixed number of "real" (public-key) OTs — say a security parameter's worth, ~128 — and then, using only cheap symmetric-key operations (hashing), turn them into arbitrarily many OTs. 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 the same move for oblivious transfer.

The mechanics, in spirit: the base OTs set up correlated random bits between the two parties; a clever transposition and a hash then "extend" each correlated seed into a fresh OT whose messages are masked by hash outputs. The expensive lattice KEM work is amortized once, and each additional transfer costs a couple of hashes. Because the extension is purely symmetric (hash functions like SHAKE), it is post-quantum for free — hashes are quantum-safe with at most a mild parameter bump. So the composition is: a few ML-KEM base OTs (post-quantum public-key) → IKNP extension (post-quantum symmetric) → thousands of cheap OTs.

We could have skipped extension and just done the ~32 public-key OTs the rounding actually needs (recall from article 02 that we only round PRESENCE_TRUNC = 32 coefficients, not 512 — that truncation already shrank the OT count 16×). For 32 transfers, base OTs alone are borderline acceptable. We kept the extension machinery because it makes the per-coefficient cost negligible, keeps the design robust if the number of rounded coefficients ever grows, and matches the standard, well-audited MPC building block rather than a bespoke shortcut. It is the "use the boring, battle-tested construction" instinct.

5. Why OT is the right shape for rounding

It is worth previewing why this specific primitive fits the rounding job so well, because it justifies the whole detour. Rounding a noisy value near a boundary depends on a bit that is secret-shared between client and server (neither may see the true value). OT is exactly "the receiver selects the correct branch of a two-way table the sender prepared, without either learning the other's secret." So the server builds, for each coefficient, a little table encoding "if the shared bit is 0, the rounding is this; if 1, it is that," and the client obliviously pulls the branch corresponding to its 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 the next article.

6. Summary

  • Oblivious Transfer lets a receiver pick one of two sender messages, learning only its choice, with the sender learning nothing about the choice. It is complete for secure computation and, for us, the tool that finishes the OPRF's rounding.
  • The classical DH-based OT is Shor-broken, and the OT sits inside the discovery path, so it must be post-quantum.
  • We build it from ML-KEM-768, exploiting that a real encapsulation key is indistinguishable from a decoy — receiver privacy from key-indistinguishability, sender privacy from Module-LWE.
  • OT extension (IKNP) turns a handful of expensive lattice base OTs into thousands of cheap symmetric-hash OTs, and stays post-quantum because the extension is all hashing.
  • OT's "select a branch of a sender-built table blindly" shape is exactly what secret-shared rounding needs — the topic of article 08.

References

  • M. Rabin, "How to Exchange Secrets with Oblivious Transfer," 1981; S. Even, O. Goldreich, A. Lempel, "A Randomized Protocol for Signing Contracts," 1985 — the origins of OT.
  • T. Chou, C. Orlandi, "The Simplest Protocol for Oblivious Transfer," LATINCRYPT 2015 — the classical DH construction we could not use post-quantum.
  • Y. Ishai, J. Kilian, K. Nissim, E. Petrank, "Extending Oblivious Transfers Efficiently," CRYPTO 2003 — OT extension (IKNP).
  • NIST, FIPS 203 (ML-KEM), 2024 — the post-quantum KEM our base OT is built from.
  • Wikipedia: Oblivious transfer, Key encapsulation mechanism, Kyber.

Next: Algorithm: Rounding by Oblivious Transfer (Route B).