Paper 2026/883
Complete Fairness in Secure Two-party Computation from Quantum One-Wayness
Abstract
In 1997, Mayers, and Lo and Chau, in their papers proved that if one of the parties is malicious, it is not possible to achieve unconditional security in quantum bit-commitment (Phy. Rev. Lett, 1997). Moreover, Lo showed that it is not possible to achieve unconditional security in two-party quantum computation (Phy. Rev. A, 1997). However, restricting the computational power of the adversary, via assumptions like the existence of one-wayness, it has been shown that secure quantum bit-commitment is indeed possible by Dumais, Mayers, and Salvail (EUROCRYPT 2000). In their paper, they showed that with the assumption of a one-way permutation that is secure against any polynomial-time quantum adversary, one can achieve a secure quantum bit-commitment scheme. Although security is guaranteed, complete fairness remains an issue in quantum two-party computation for the real-world framework. In this paper, we show for the first time that secure two-party quantum computation with complete fairness is achievable for the same class of functions as studied by Gordon, Hazay, Katz, and Lindell (STOC 2008) in the classical domain. This seems to stand in sharp contrast to the impossibility result of Ben-Or, Crepeau, Gottesman, Hassidim, and Smith (FOCS 2006). However, they considered a malicious quantum adversary with unconditional computational power and used a broadcast channel. On the other hand, we use the hybrid model idea of Gordon, Hazay, Katz, and Lindell with a non-simultaneous channel and the idea of composition by Ran Canetti (Journal of Cryptology, 2000) to achieve complete fairness in the quantum domain, under the assumption of a computationally bounded adversary. At first, we design secure two-party computation protocols in a hybrid model, using a trusted third party. Then we prove how these protocols achieve complete fairness in the hybrid model. Finally, we construct a secure two-party communication protocol and show how we can use this to remove the trusted third party of the hybrid model and achieve both security and complete fairness in the real-world model. In this context, we devise a zero-knowledge proof and use it as an important tool in our protocol.
Note: Updated with motivation for quantum solution and stronger ZK argument.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Embedded XORFairnessMillionaires' problemSecure quantum computation
- Contact author(s)
-
arpita maitra @ tcgcrest org
goutam paul @ isical ac in
asmitasamanta6 @ gmail com
hridam basu @ gmail com - History
- 2026-11-05: revised
- 2026-05-05: received
- See all versions
- Short URL
- https://ia.cr/2026/883
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/883,
author = {Arpita Maitra and Goutam Paul and Asim K. Pal and Asmita Samanta and Hridam Basu},
title = {Complete Fairness in Secure Two-party Computation from Quantum One-Wayness},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/883},
year = {2026},
url = {https://eprint.iacr.org/2026/883}
}