[go: up one dir, main page]

What a lovely hat

Is it made out of tin foil?

Paper 2023/1620

Commitments from Quantum One-Wayness

Dakshita Khurana, University of Illinois Urbana-Champaign
Kabir Tomer, University of Illinois Urbana-Champaign
Abstract

One-way functions are central to classical cryptography. They are both necessary for the existence of non-trivial classical cryptosystems, and sufficient to realize meaningful primitives including commitments, pseudorandom generators and digital signatures. At the same time, a mounting body of evidence suggests that assumptions even weaker than one-way functions may suffice for many cryptographic tasks of interest in a quantum world, including bit commitments and secure multi-party computation. This work studies one-way state generators [Morimae-Yamakawa, CRYPTO 2022], a natural quantum relaxation of one-way functions. Given a secret key, a one-way state generator outputs a hard to invert quantum state. A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography. We obtain an affirmative answer to this question by proving that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation. Along the way, we build an intermediate primitive with classical outputs, which we call a (quantum) one-way puzzle. Our main technical contribution is a proof that one-way puzzles imply quantum bit commitments.

Note: Minor updates to the proof of Claim 4.2

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
quantumcommitmentone-way statespseudorandom
Contact author(s)
dakshita @ illinois edu
ktomer2 @ illinois edu
History
2024-01-29: last of 2 revisions
2023-10-19: received
See all versions
Short URL
https://ia.cr/2023/1620
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1620,
      author = {Dakshita Khurana and Kabir Tomer},
      title = {Commitments from Quantum One-Wayness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1620},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1620}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.