On this page
Two parties, one answer
In 1982 Andrew Yao posed the millionaires' problem: two millionaires want to know which of them is richer, without either revealing their wealth. It is the founding example of secure two-party computation: two parties, each with a private input, jointly compute a function and learn the output and nothing more.
The idea now sits under real systems. Threshold signatures split a key between machines so no single one ever holds it. Private set intersection lets two organisations find shared records without exchanging their lists. Each is the same shape: compute together, reveal only the answer.
Privacy is half of it. Fairness is the other half.
A protocol can keep both inputs private and still be unfair. Imagine the last message of the protocol: one party receives it and learns the output first. If that party is malicious, it can stop there. It now knows the answer; the other party never will.
Complete fairness means either both parties get the output or neither does. In 1986 Richard Cleve showed that, between two parties without an honest majority, complete fairness cannot be achieved in general; even fair coin tossing is impossible. For two decades that was widely read as "two-party fairness is impossible".
It is not quite. In 2008 Gordon, Hazay, Katz and Lindell showed that some non-trivial functions can be computed with complete fairness after all, including a version of the millionaires' problem. Which functions admit fairness depends on their structure; one property that comes up is whether the function contains an embedded XOR.
What quantum changes
"Quantum" enters secure computation in two separate ways, and it helps to keep them apart.
Quantum computers attacking classical cryptography
A large, fault-tolerant quantum computer running Shor's algorithm would factor integers and compute discrete logarithms efficiently. That breaks RSA, Diffie–Hellman and elliptic-curve cryptography, including ECDSA signatures and the pairing-based assumptions under proof systems such as Groth16 and KZG-based PLONK. Grover's algorithm gives a quadratic speed-up for brute-force search, which is handled by using larger keys and hash outputs.
The response is post-quantum cryptography: schemes built on problems with no known efficient quantum attack, such as lattice problems and hash functions. In August 2024 NIST published its first post-quantum standards: ML-KEM for key establishment (FIPS 203), and ML-DSA and SLH-DSA for signatures (FIPS 204 and 205).
Protocols that run on quantum computers
The second question is what parties with quantum computers can achieve together. Some things get easier; some known limits get sharper.
In 1997 Hoi-Kwong Lo showed that unconditionally secure two-party quantum computation is impossible when one party is malicious. Quantum bit commitment, a basic building block, was shown impossible unconditionally in the same period. Under computational assumptions, such as a one-way permutation secure against quantum adversaries, secure quantum bit commitment does become possible.
Fairness remained open, and for quantum protocols Ben-Or and co-authors had given an impossibility result (FOCS 2006).
Where ePrint 2026/883 fits
Secure Two-Party Quantum Computation with Complete Fairness without Trusted Third Party, by Arpita Maitra, Goutam Paul, Asim K. Pal, Asmita Samanta and Hridam Basu, takes up that open question.
The paper shows, for the first time, that some functions admit secure two-party quantum computation with complete fairness and no trusted third party, in sharp contrast with the impossibility result of Ben-Or et al. Its keywords, the millionaires' problem and embedded XOR, place it in the same line of thinking as the classical results above: impossibility in general does not mean impossibility for every function.
It is open access on the IACR Cryptology ePrint Archive as 2026/883, licensed CC BY.
If you ship cryptography today
Foundational research like this does not change what you deploy next week. The quantum question in general should change how you plan.
- Inventory. Find where you depend on RSA or elliptic curves: TLS, signatures, wallets, key exchange, proof systems.
- Prioritise long-lived secrets. Data encrypted today can be recorded today and decrypted later ("harvest now, decrypt later"). Confidentiality that must last years is the first candidate for post-quantum key establishment.
- Be precise about proofs. For pairing-based proof systems, a quantum adversary threatens soundness, the ability to forge new proofs. Groth16's zero knowledge is perfect, so what old proofs hid stays hidden. Hash-based STARKs are generally considered plausibly post-quantum.
- Design for agility. Keep algorithms behind interfaces and versioned formats, so swapping one is a migration rather than a rewrite.
None of this needs a working quantum computer to be worth doing. It needs a clear view of which assumptions your system rests on.
