Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
This work addresses a foundational challenge in post-quantum cryptography by enabling practical, efficient protocols for secure computation, though it relies on a relaxation of standard security.
The paper tackles the problem of building constant-round and black-box two-party computation secure against quantum adversaries, which was previously shown impossible under standard simulation-based security. It achieves this by introducing ε-simulatability, a relaxation allowing small simulation error, and constructs protocols from minimal assumptions like post-quantum oblivious transfers or one-way functions, with applications including extractable commitments and zero-knowledge arguments.
From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first $ε$-simulatable two-party computation (2PC) against quantum polynomial-time (QPT) adversaries that is both constant-round and black-box (for both the construction and security reduction). A recent work by Chia, Chung, Liu, and Yamakawa (FOCS'21) shows that post-quantum 2PC with standard simulation-based security is impossible in constant rounds, unless either $\mathbf{NP} \subseteq \mathbf{BQP}$ or relying on non-black-box simulation. The $ε$-simulatability we target is a relaxation of the standard simulation-based security that allows for an arbitrarily small noticeable simulation error $ε$. Moreover, when quantum communication is allowed, we can further weaken the assumption to post-quantum secure one-way functions (PQ-OWFs), while maintaining the constant-round and black-box property. Our techniques also yield the following set of constant-round and black-box two-party protocols secure against QPT adversaries, only assuming black-box access to PQ-OWFs: - extractable commitments for which the extractor is also an $ε$-simulator; - $ε$-zero-knowledge commit-and-prove whose commit stage is extractable with $ε$-simulation; - $ε$-simulatable coin-flipping; - $ε$-zero-knowledge arguments of knowledge for $\mathbf{NP}$ for which the knowledge extractor is also an $ε$-simulator; - $ε$-zero-knowledge arguments for $\mathbf{QMA}$. At the heart of the above results is a black-box extraction lemma showing how to efficiently extract secrets from QPT adversaries while disturbing their quantum state in a controllable manner, i.e., achieving $ε$-simulatability of the post-extraction state of the adversary.