Signatures From Pseudorandom States via $\bot$-PRFs

• URL: http://arxiv.org/abs/2311.00847v6
• Date: Sun, 06 Oct 2024 20:07:48 GMT
• Title: Signatures From Pseudorandom States via $\bot$-PRFs
• Authors: Mohammed Barhoush, Amit Behera, Lior Ozer, Louis Salvail, Or Sattath,
• Abstract summary: We introduce new definitions for $bot$-PRG and $bot$-PRF. Our main application is a (quantum) digital signature scheme with classical public keys and signatures.
• Score: 0.11650821883155184
• License:
• Abstract: Different flavors of quantum pseudorandomness have proven useful for various cryptographic applications, with the compelling feature that these primitives are potentially weaker than post-quantum one-way functions. Ananth, Lin, and Yuen (2023) have shown that logarithmic pseudorandom states can be used to construct a pseudo-deterministic PRG: informally, for a fixed seed, the output is the same with $1-1/poly$ probability. In this work, we introduce new definitions for $\bot$-PRG and $\bot$-PRF. The correctness guarantees are that, for a fixed seed, except with negligible probability, the output is either the same (with probability $1-1/poly$) or recognizable abort, denoted $\bot$. Our approach admits a natural definition of multi-time PRG security, as well as the adaptive security of a PRF. We construct a $\bot$-PRG from any pseudo-deterministic PRG and, from that, a $\bot$-PRF. Even though most mini-crypt primitives, such as symmetric key encryption, commitments, MAC, and length-restricted one-time digital signatures, have been shown based on various quantum pseudorandomness assumptions, digital signatures remained elusive. Our main application is a (quantum) digital signature scheme with classical public keys and signatures, thereby addressing a previously unresolved question posed in Morimae and Yamakawa's work (Crypto, 2022). Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys.

Related papers

• Anonymous Public-Key Quantum Money and Quantum Voting [15.80411915665245]
  We develop the formal definitions of privacy for quantum money schemes. We then construct the first public-key quantum money schemes that satisfy these security notions. We show that the no-cloning principle, a result of quantum mechanics, allows us to construct schemes, with security guarantees that are classically impossible.
  arXiv  Detail & Related papers  (2024-11-07T07:21:28Z)
• PRS Length Expansion [4.31241676251521]
  Pseudo-random quantum states (PRS) are a key primitive in quantum cryptography. This work conjectures that some PRS generators can be expanded, and provides a proof for such expansion for some specific examples.
  arXiv  Detail & Related papers  (2024-11-05T16:06:59Z)
• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs. This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• On black-box separations of quantum digital signatures from pseudorandom states [1.9254132307399263]
  We show that there $textitdoes not$ exist a black-box construction of a quantum digital signatures scheme. Our result complements that of Morimae and Yamakawa (2022), who described a $textitone-time$ secure QDS scheme with classical signatures.
  arXiv  Detail & Related papers  (2024-02-13T03:36:35Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Public-Key Encryption with Quantum Keys [11.069434965621683]
  We study the notion of quantum public-key encryption (qPKE) where keys are allowed to be quantum states. We show that computational assumptions are necessary to build quantum public-key encryption.
  arXiv  Detail & Related papers  (2023-06-13T11:32:28Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.