Quantum commitments and signatures without one-way functions

DOI10.1007/978-3-031-15802-5_10MaRDI QIDQ6097265zbMATH OpenFDO

Authors Tomoyuki Morimae, Takashi Yamakawa

Publication date 12 June 2023

Published in Advances in Cryptology – CRYPTO 2022 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.06369

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: In the classical world, the existence of commitments is equivalent to the existence of one-way functions. In the quantum setting, on the other hand, commitments are not known to imply one-way functions, but all known constructions of quantum commitments use at least one-way functions. Are one-way functions really necessary for commitments in the quantum world? In this work, we show that non-interactive quantum commitments (for classical messages) with computational hiding and statistical binding exist if pseudorandom quantum states exist. Pseudorandom quantum states are sets of quantum states that are efficiently generated but their polynomially many copies are computationally indistinguishable from the same number of copies of Haar random states [Ji, Liu, and Song, CRYPTO 2018]. It is known that pseudorandom quantum states exist even if $BQP=QMA$ (relative to a quantum oracle) [Kretschmer, TQC 2021], which means that pseudorandom quantum states can exist even if no quantum-secure classical cryptographic primitive exists. Our result therefore shows that quantum commitments can exist even if no quantum-secure classical cryptographic primitive exists. In particular, quantum commitments can exist even if no quantum-secure one-way function exists. In this work, we also consider digital signatures, which are other fundamental primitives in cryptography. We show that one-time secure digital signatures with quantum public keys exist if pseudorandom quantum states exist. In the classical setting, the existence of digital signatures is equivalent to the existence of one-way functions. Our result, on the other hand, shows that quantum signatures can exist even if no quantum-secure classical cryptographic primitive (including quantum-secure one-way functions) exists.

Recommendations

• Cryptography from pseudorandom quantum states
• Classical binding for quantum commitments
• Collapse-binding quantum commitments without random oracles
• Quantum commitments from complexity assumptions
• One-way functions imply secure computation in a quantum world

Cites work

• (Pseudo) random quantum states with binary phase
• A Pseudorandom Generator from any One-way Function
• Bit commitment using pseudorandomness
• Classical binding for quantum commitments
• Collapse-binding quantum commitments without random oracles
• Computational indistinguishability between quantum states and its cryptographic application
• scientific article; zbMATH DE number 1722671 (Why is no real title available?)
• scientific article; zbMATH DE number 1263182 (Why is no real title available?)
• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• Improving the Security of Quantum Protocols via Commit-and-Open
• Lower bounding the AND-OR tree via symmetrization
• New directions in cryptography
• Oblivious transfer is in MiniQCrypt
• One-way functions imply secure computation in a quantum world
• Perfectly concealing quantum bit commitment from any quantum one-way permutation
• Pseudorandom quantum states
• Quantum bit commitment with application in quantum zero-knowledge proof (extended abstract)
• Quantum cryptography: public key distribution and coin tossing
• Scalable pseudorandom quantum states
• Statistically-hiding quantum bit commitment from approximable-preimage-size quantum one-way function
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(50)

• Public-key quantum signature for classical messages without third-party verification
• One-way functions imply secure computation in a quantum world
• Asymptotics of quantum contract signing
• One-shot signatures and applications to hybrid quantum/classical authentication
• Pseudorandom (function-Like) quantum state generators: new definitions and applications
• General properties of quantum bit commitments (extended abstract)
• Black-box separations for non-interactive classical commitments in a quantum world
• From the hardness of detecting superpositions to cryptography: quantum public key encryption and commitments
• A new framework for quantum oblivious transfer
• Cloning games: a general framework for unclonable primitives
• Cryptography with certified deletion
• Secure computation with shared EPR pairs (or: how to teleport in zero-knowledge)
• Commitments to quantum states
• Quantum cryptography in Algorithmica
• Pseudorandomness with proof of destruction and applications
• Weakening assumptions for publicly-verifiable deletion
• Public-key encryption with quantum keys
• Quantum CCA-secure PKE, revisited
• Quantum advantage from one-way functions
• Unconditionally secure quantum commitments with preprocessing
• Unconditionally secure commitments with quantum auxiliary inputs
• Quantum public-key encryption with tamper-resilient public keys from one-way functions
• How (not) to build quantum PKE in Minicrypt
• On central primitives for quantum cryptography with classical communication
• Exponential quantum one-wayness and EFI pairs
• Quantum cryptography and meta-complexity
• Translating between the common Haar random state model and the unitary model
• Pseudorandomness in the (inverseless) Haar random oracle model
• The power of a single Haar random state: constructing and separating quantum pseudorandomness
• A meta-complexity characterization of quantum cryptography
• Hard quantum extrapolations in quantum cryptography
• A new world in the depths of Microcrypt: separating OWSGs and quantum money from QEFID
• Oracle separation between quantum commitments and quantum one-wayness
• Quantum public-key encryption of quantum states, and more
• Quantum CCA-secure PKE, revisited
• On black-box separations of quantum digital signatures from pseudorandom states
• Robust combiners and universal constructions for quantum cryptography
• Quantum pseudorandom scramblers
• Quantum unpredictability
• Signatures from pseudorandom states via -PRFs
• Non-interactive zero-knowledge arguments with certified deletion
• MicroCrypt assumptions with quantum input sampling and pseudodeterminism: constructions and separations
• On the limitations of pseudorandom unitaries. Or: cryptographic applications of LOCC indistinguishability of identical versus independent Haar unitaries
• Pseudorandom function-like states from common Haar unitary
• Publicly verifiable deletion: general compilers from minimal assumptions
• Revocable encryption, programs, and more: the case of multi-copy security
• The black-box simulation barrier persists in a fully quantum world
• Quantum pseudorandom scramblers
• A note on the minimality of one-way functions in post-quantum cryptography
• Unconditional quantum cryptography with a bounded number of keys

This page was built for publication: Quantum commitments and signatures without one-way functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097265)