Quantum Unpredictability

• URL: http://arxiv.org/abs/2405.04072v1
• Date: Tue, 7 May 2024 07:19:25 GMT
• Title: Quantum Unpredictability
• Authors: Tomoyuki Morimae, Shogo Yamada, Takashi Yamakawa,
• Abstract summary: We introduce a quantum analog of unpredictable state generators (UPSGs) UPSGs are implied by pseudorandom function-like states generators (PRFSs), which are a quantum analog of pseudorandom functions (PRFs) Our findings suggest that, for many applications, quantum unpredictability, rather than quantum pseudorandomness, is sufficient.
• Score: 8.093227427119325
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Unpredictable functions (UPFs) play essential roles in classical cryptography, including message authentication codes (MACs) and digital signatures. In this paper, we introduce a quantum analog of UPFs, which we call unpredictable state generators (UPSGs). UPSGs are implied by pseudorandom function-like states generators (PRFSs), which are a quantum analog of pseudorandom functions (PRFs), and therefore UPSGs could exist even if one-way functions do not exist, similar to other recently introduced primitives like pseudorandom state generators (PRSGs), one-way state generators (OWSGs), and EFIs. In classical cryptography, UPFs are equivalent to PRFs, but in the quantum case, the equivalence is not clear, and UPSGs could be weaker than PRFSs. Despite this, we demonstrate that all known applications of PRFSs are also achievable with UPSGs. They include IND-CPA-secure secret-key encryption and EUF-CMA-secure MACs with unclonable tags. Our findings suggest that, for many applications, quantum unpredictability, rather than quantum pseudorandomness, is sufficient.

Related papers

• Pseudorandom Function-like States from Common Haar Unitary [1.0067421338825544]
  We construct classically-accessible adaptive secure PRFSGs in the invertible quantum Haar random oracle (QHRO) model. Our PRFSG constructions resemble the classical EvenMansour encryption based on a single permutation, and are secure against any unbounded number of queries.
  arXiv  Detail & Related papers  (2024-11-05T15:48:27Z)
• Existential Unforgeability in Quantum Authentication From Quantum Physical Unclonable Functions Based on Random von Neumann Measurement [45.386403865847235]
  Physical Unclonable Functions (PUFs) leverage inherent, non-clonable physical randomness to generate unique input-output pairs. Quantum PUFs (QPUFs) extend this concept by using quantum states as input-output pairs. We show that no random unitary QPUF can achieve existential unforgeability against Quantum Polynomial Time adversaries. We introduce a second model where the QPUF functions as a nonunitary quantum channel, which also guarantees existential unforgeability.
  arXiv  Detail & Related papers  (2024-04-17T12:16:41Z)
• Commitments are equivalent to statistically-verifiable one-way state generators [5.088702935364181]
  One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We show that O(n/log(n)-copy-OWSGs (n represents the input length) are equivalent to poly(n)-copy-OWSGs and to quantum commitments.
  arXiv  Detail & Related papers  (2024-04-04T06:06:38Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• 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)
• Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
  We study the relationship between notions of pseudorandomness in the quantum and classical worlds. We show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs. We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions.
  arXiv  Detail & Related papers  (2023-06-09T01:16:58Z)
• 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)
• One-Wayness in Quantum Cryptography [9.09597656634436]
  We study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions. We show that Quantum digital signatures are equivalent to OWSGs. We introduce an variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs.
  arXiv  Detail & Related papers  (2022-10-07T08:21:21Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• 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)
• Semantic Security for Quantum Wiretap Channels [68.24747267214373]
  We consider the problem of semantic security via classical-quantum and quantum wiretap channels. We use explicit constructions to transform a non-secure code into a semantically secure code, achieving capacity by means of biregular irreducible functions.
  arXiv  Detail & Related papers  (2020-01-16T09:55:49Z)

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.