Towards Universal Quantum Tamper Detection

• URL: http://arxiv.org/abs/2509.12986v1
• Date: Tue, 16 Sep 2025 11:49:17 GMT
• Title: Towards Universal Quantum Tamper Detection
• Authors: Anne Broadbent, Upendra Kapshikar, Denis Rochette,
• Abstract summary: We give the first treatment of tamper detection against arbitrary quantum maps.<n>We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family.<n>Our results provide the first evidence that quantum tamper detection is strictly more powerful than its classical counterpart.
• Score: 2.064612766965483
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tamper-resilient cryptography studies how to protect data against adversaries who can physically manipulate codewords before they are decoded. The notion of tamper detection codes formalizes this goal, requiring that any unauthorized modification be detected with high probability. Classical results, starting from Jafargholi and Wichs (TCC 2015), established the existence of such codes against very large families of tampering functions, subject to structural restrictions ruling out identity and constant maps. Recent works of Boddu and Kapshikar (Quantum, 7) and Bergamaschi (Eurocrypt 2024) have extended these ideas to quantum adversaries, but only consider unitary tampering families. In this work, we give the first general treatment of tamper detection against arbitrary quantum maps. We show that Haar-random encoding schemes achieve exponentially small soundness error against any adversarial family whose size, Kraus rank, and entanglement fidelity obey natural constraints, which are direct quantum analogues of restrictions in the classical setting. Our results unify and extend previous works. Beyond this, we demonstrate a fundamental separation between classical and quantum tamper detection. Classically, relaxed tamper detection which allows either rejection or recovery of the original message cannot protect even against the family of constant functions. This family is of size $2^n$. In contrast, we show that quantum encodings can handle this obstruction, and we conjecture and provide evidence that they may in fact provide relaxed tamper detection and non-malleable security against any family of quantum maps of size up to $2^{2^{\alpha n}}$ for any constant $\alpha <\frac{1}{2}$, leading to a conjecture on the existence of universal quantum tamper detection. Our results provide the first evidence that quantum tamper detection is strictly more powerful than its classical counterpart.

Related papers

• Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE [6.626421278252587]
  A classical obfuscator for quantum circuits is a program that outputs the classical description of a quantum circuit $Q$.<n>We show that (relative to a classical oracle) there exists a classical obfuscator for all pseudo-deterministic quantum circuits.
  arXiv  Detail & Related papers  (2025-10-09T16:19:12Z)
• Quantum Error Correction in Adversarial Regimes [0.7476861985233554]
  In adversarial settings, where attackers can deliberately and strategically corrupt quantum data, standard quantum error correction reaches its limits.<n>Quantum list decoding offers a promising alternative.<n>By allowing the decoder to output a short list of possible errors, it becomes possible to tolerate far more errors, even under worst-case noise.
  arXiv  Detail & Related papers  (2025-09-10T19:08:56Z)
• Quantum State Obfuscation from Classical Oracles [18.878095837031292]
  A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation. We develop a new array of techniques that we use to construct a quantum state obfuscator.
  arXiv  Detail & Related papers  (2024-01-18T18:42:28Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• 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)
• Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More [13.02553999059921]
  We provide both negative and positive results for publicly verifiable quantum money. We propose a framework for building quantum money and quantum lightning. We discuss potential instantiations of our framework.
  arXiv  Detail & Related papers  (2022-11-22T04:17:32Z)
• 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)
• 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)
• 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)
• 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)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  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.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

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.