A Meta-complexity Characterization of Minimal Quantum Cryptography
We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.
Authors
- Bruno Pasqualotto Cavalar (ORCID: https://orcid.org/0000-0002-0458-8767)
- Boyang Chen (ORCID: https://orcid.org/0000-0001-7393-4363)
- Zhengfeng Ji (ORCID: https://orcid.org/0000-0002-7659-3178)
- Zihan Hu (ORCID: https://orcid.org/0009-0009-7005-9220)
- Matthew Gray
- Andrea Coladangelo (ORCID: https://orcid.org/0000-0002-6773-2711)
- Xingjian Li (ORCID: https://orcid.org/0000-0002-8058-7491)
Institutions
- University of Washington (US)
- University of Oxford (GB)
- École Polytechnique Fédérale de Lausanne (CH)
- Seattle University (US)
- Tsinghua University (CN)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800783
- Primary Topic
- Cryptography and Data Security
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China
- Engineering and Physical Sciences Research Council