PRS Length Expansion

• URL: http://arxiv.org/abs/2411.03215v1
• Date: Tue, 05 Nov 2024 16:06:59 GMT
• Title: PRS Length Expansion
• Authors: Romi Levy, Thomas Vidick,
• Abstract summary: 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.
• Score: 4.31241676251521
• License:
• Abstract: One of the most fundamental results in classical cryptography is that the existence of Pseudo-Random Generators (PRG) that expands $k$ bits of randomness to $k+1$ bits that are pseudo-random implies the existence of PRG that expand $k$ bits of randomness to $k+f(k)$ bits for any $f(k)=poly(k)$. It appears that cryptography in the quantum realm sometimes works differently than in the classical case. Pseudo-random quantum states (PRS) are a key primitive in quantum cryptography, that demonstrates this point. There are several open questions in quantum cryptography about PRS, one of them is - can we expand quantum pseudo-randomness in a black-box way with the same key length? Although this is known to be possible in the classical case, the answer in the quantum realm is more complex. This work conjectures that some PRS generators can be expanded, and provides a proof for such expansion for some specific examples. In addition, this work demonstrates the relationship between the key length required to expand the PRS, the efficiency of the circuit to create it and the length of the resulting expansion.

Related papers

• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way [0.0]
  Pseudorandom Quantum States (PRS) were introduced by Ji, Liu and Song as quantum analogous to Pseudorandom Generators. Short-PRSs, that is PRSs with logarithmic size output, have been introduced in literature along with cryptographic applications. Here we show that it is not possible to shrink the output of a PRS from 2021 to logarithmic qubit length while still preserving the pseudorandomness property.
  arXiv  Detail & Related papers  (2024-02-20T19:02:43Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  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.
  arXiv  Detail & Related papers  (2023-11-01T20:54:50Z)
• 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)
• 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 Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• 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)
• Scalable Pseudorandom Quantum States [14.048989759890476]
  In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e. the (statistical) security parameter for an $n$-qubit PRS is roughly $n$. We show that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a emphstatistically secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security.
  arXiv  Detail & Related papers  (2020-04-04T17:15:03Z)

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.