Paper 2021/1516

Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round

Nai-Hui Chia
Kai-Min Chung
Xiao Liang
Takashi Yamakawa
Abstract

From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first $\epsilon$-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 $NP \subseteq BQP$ or relying on non-black-box simulation. The $\epsilon$-simulatability we target is a relaxation of the standard simulation-based security that allows for an arbitrarily small noticeable simulation error $\epsilon$. 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 $\epsilon$-simulator; - $\epsilon$-zero-knowledge commit-and-prove whose commit stage is extractable with $\epsilon$-simulation; - $\epsilon$-simulatable coin-flipping; - $\epsilon$-zero-knowledge arguments of knowledge for $NP$ for which the knowledge extractor is also an $\epsilon$-simulator; - $\epsilon$-zero-knowledge arguments for $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 $\epsilon$-simulatability of the post-extraction state of the adversary.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
SimulationExtractionPost-Quantum
Contact author(s)
nc67 @ rice edu
kmchung @ iis sinica edu tw
xiao crypto @ gmail com
takashi yamakawa @ ntt com
History
2023-11-04: last of 2 revisions
2021-11-20: received
See all versions
Short URL
https://ia.cr/2021/1516
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1516,
      author = {Nai-Hui Chia and Kai-Min Chung and Xiao Liang and Takashi Yamakawa},
      title = {Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1516},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1516}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.