Quantum-secure message authentication via blind-unforgeability

• URL: http://arxiv.org/abs/1803.03761v4
• Date: Thu, 20 Apr 2023 09:23:06 GMT
• Title: Quantum-secure message authentication via blind-unforgeability
• Authors: Gorjan Alagic, Christian Majenz, Alexander Russell and Fang Song
• Abstract summary: We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
• Score: 74.7729810207187
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition. We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the "hash-and-MAC" paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving. Finally, we demonstrate that blind unforgeability is stronger than a previous definition of Boneh and Zhandry [EUROCRYPT '13, CRYPTO '13] in the sense that we can construct an explicit function family which is forgeable by an attack that is recognized by blind-unforgeability, yet satisfies the definition by Boneh and Zhandry.

Related papers

• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects. Despite its strength, indifferentiability is not known to offer security against pre-processing attacks. We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
  arXiv  Detail & Related papers  (2024-10-22T00:41:47Z)
• Certified Robustness of Quantum Classifiers against Adversarial Examples through Quantum Noise [68.1992787416233]
  We show that adding quantum random rotation noise can improve robustness in quantum classifiers against adversarial attacks. We derive a certified robustness bound to enable quantum classifiers to defend against adversarial examples.
  arXiv  Detail & Related papers  (2022-11-02T05:17:04Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• Deniable Encryption in a Quantum World [6.550883342516878]
  We study (sender-)deniable encryption in a setting where the encryption procedure is a quantum algorithm. We show that quantum unlocks a fundamentally stronger form of deniable encryption, which we call perfect unexplainability.
  arXiv  Detail & Related papers  (2021-12-30T09:45:24Z)
• A Unified Framework For Quantum Unforgeability [0.0]
  We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions. We prove how our definitions subsume previous ones while considering more fine-grained adversarial models. We show that the strongest level of unforgeability, namely existential unforgeability, can only be achieved if only to previously queried messages are considered to be forgeries.
  arXiv  Detail & Related papers  (2021-03-25T17:31:59Z)
• Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
  We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model. This yields the first post-quantum succinct argument system from any falsifiable assumption.
  arXiv  Detail & Related papers  (2021-03-15T05:09:17Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Classical proofs of quantum knowledge [10.432041176720842]
  We define the notion of a proof of knowledge in the setting where the verifier is classical. We show that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an adversary.
  arXiv  Detail & Related papers  (2020-05-04T17:45:21Z)

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.