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

• URL: http://arxiv.org/abs/2502.13830v1
• Date: Wed, 19 Feb 2025 15:45:28 GMT
• Title: The Round Complexity of Black-Box Post-Quantum Secure Computation
• Authors: Rohit Chatterjee, Xiao Liang, Omkant Pandey, Takashi Yamakawa,
• Abstract summary: We study the round complexity of secure multi-party computation (MPC) in the post-quantum regime.<n>Our focus is on the fully black-box setting, where both the construction and security reduction are black-box.<n>We present the first black-box, constant-round construction in the multi-party setting, instantiable using various standard post-quantum primitives.
• Score: 7.683672647857481
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the round complexity of secure multi-party computation (MPC) in the post-quantum regime. Our focus is on the fully black-box setting, where both the construction and security reduction are black-box. Chia, Chung, Liu, and Yamakawa [FOCS'22] demonstrated the infeasibility of achieving standard simulation-based security within constant rounds unless $\mathbf{NP} \subseteq \mathbf{BQP}$. This leaves crucial feasibility questions unresolved. Specifically, it remains unknown whether black-box constructions are achievable within polynomial rounds; also, the existence of constant-round constructions with respect to $\epsilon$-simulation, a relaxed yet useful alternative to standard simulation, remains unestablished. This work provides positive answers. We introduce the first black-box construction for PQ-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)$ rounds. These results have already been applied in the oracle separation between classical-communication quantum MPC and $\mathbf{P} = \mathbf{NP}$ in Kretschmer, Qian, and Tal [STOC'25]. As for $\epsilon$-simulation, Chia, Chung, Liang, and Yamakawa [CRYPTO'22] resolved the issue for the two-party setting, leaving the multi-party case open. We complete the picture by presenting the first black-box, constant-round construction in the multi-party setting, instantiable using various standard post-quantum primitives. En route, we obtain a black-box, constant-round post-quantum commitment achieving a weaker version of 1-many non-malleability, from post-quantum one-way functions. Besides its role in our MPC construction, this commitment also reduces the assumption used in the quantum parallel repetition lower bound by Bostanci, Qian, Spooner, and Yuen [STOC'24]. We anticipate further applications in the future.

Related papers

• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Scheme of quantum communications based on Witting polytope [55.2480439325792]
  Presented paper describes how to use this configuration for a quantum key distribution protocol based on contextuality using some illustrative examples with 40 "quantum cards" In a more general case, two arbitrary quantum systems with four basis states (ququarts) can be used instead.
  arXiv  Detail & Related papers  (2025-03-24T08:26:48Z)
• The Black-Box Simulation Barrier Persists in a Fully Quantum World [9.887919546667598]
  We show that only languages in $mathbfBQP$ admit constant-round $textitfully-quantum$ BBZK. It illuminates the nature of quantum zero-knowledge and provides valuable insights for designing future protocols in the quantum realm.
  arXiv  Detail & Related papers  (2024-09-10T08:17:17Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• On black-box separations of quantum digital signatures from pseudorandom states [1.9254132307399263]
  We show that there $textitdoes not$ exist a black-box construction of a quantum digital signatures scheme. Our result complements that of Morimae and Yamakawa (2022), who described a $textitone-time$ secure QDS scheme with classical signatures.
  arXiv  Detail & Related papers  (2024-02-13T03:36:35Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• A New Approach to Post-Quantum Non-Malleability [8.859667450008452]
  We provide the first $mathitconstant$-$mathitround$ construction of post-quantum non-malleable commitments. We achieve the standard notion of non-malleability with respect to commitments.
  arXiv  Detail & Related papers  (2022-07-12T21:47:39Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier.
  arXiv  Detail & Related papers  (2020-11-05T05:40:05Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.