The Round Complexity of Black-Box Post-Quantum Secure Computation (original) (raw)

Paper 2025/250

The Round Complexity of Black-Box Post-Quantum Secure Computation

Xiao Liang, The Chinese University of Hong Kong

Omkant Pandey, Stony Brook University

Takashi Yamakawa, NTT Social Informatics Laboratories

Abstract

We study the round-complexity of secure multi-party computation (MPC) in the post-quantum regime where honest parties and communication channels are classical but the adversary can be a quantum machine. Our focus is on the mathitfully\mathit{fully}mathitfully black-box setting where both the construction as well as the security reduction are black-box in nature. In this context, Chia, Chung, Liu, and Yamakawa [FOCS'22] demonstrated the infeasibility of achieving standard simulation-based security within constant rounds, unless mathbfNPsubseteqmathbfBQP\mathbf{NP} \subseteq \mathbf{BQP}mathbfNPsubseteqmathbfBQP. This outcome leaves crucial feasibility questions unresolved. Specifically, it remains unknown whether black-box constructions are achievable within polynomial rounds; additionally, the existence of constant-round constructions with respect to epsilon\epsilonepsilon-$\mathit{simulation}$, a relaxed yet useful alternative to the standard simulation notion, remains unestablished. This work provides positive answers to the aforementioned questions. We introduce the first black-box construction for post-quantum MPC in polynomial rounds, from the minimal assumption of post-quantum semi-honest oblivious transfers. In the two-party scenario, our construction requires only omega(1)\omega(1)omega(1) rounds. These results have already found application in the oracle separation between classical-communication quantum MPC and mathbfP=mathbfNP\mathbf{P} = \mathbf{NP}mathbfP=mathbfNP in the recent work of Kretschmer, Qian, and Tal [STOC'25]. As for epsilon\epsilonepsilon-simulation, Chia, Chung, Liang, and Yamakawa [CRYPTO'22] resolved the issue for the two-party setting, leaving the general multi-party setting as an open question. We complete the picture by presenting the first black-box and constant-round construction in the multi-party setting. Our construction can be instantiated using various standard post-quantum primitives including lossy public-key encryption, linearly homomorphic public-key encryption, or dense cryptosystems. En route, we obtain a black-box and constant-round post-quantum commitment that achieves a weaker version of the standard 1-many non-malleability, from the minimal assumption of post-quantum one-way functions. Besides its utility in our post-quantum MPC construction, this commitment scheme also reduces the assumption used in the lower bound of quantum parallel repetition recently established by Bostanci, Qian, Spooner, and Yuen [STOC'24]. We anticipate that it will find more applications in the future.

Note: Added information about grants.

BibTeX

@misc{cryptoeprint:2025/250, author = {Rohit Chatterjee and Xiao Liang and Omkant Pandey and Takashi Yamakawa}, title = {The Round Complexity of Black-Box Post-Quantum Secure Computation}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/250}, year = {2025}, url = {https://eprint.iacr.org/2025/250} }