Keyless secrecy against bounded adversaries

• URL: http://arxiv.org/abs/2609.12251v1
• Date: Thu, 10 Sep 2026 22:17:06 GMT
• Title: Keyless secrecy against bounded adversaries
• Abstract summary: We introduce a keyless coding/crypt computation primitive that asks for two guarantees at once.<n>Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed.<n>We obtain the first efficient non-malleable code secure against global quantum tampering.
• Score: 2.064612766965483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a keyless coding/cryptographic primitive that asks for two guarantees at once: the receiver is never fooled into accepting a message other than the one sent, and the adversary learns nothing about the message unless the receiver aborts. Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed. The only restriction is on the adversary's online computation: the receiver aborts if nothing arrives by a fixed deadline, so the adversary must forward something before it, and her map in that window is computed by a circuit of size (or depth) at most $p$; before and after, she is unbounded. For every polynomial $p$ we construct such an efficient quantum scheme, encoding $k$-bit messages into $n = O(k)$ qubits with circuits of size $\mathrm{poly}(n,p)$. No classical scheme achieves this type of everlasting security, at any choice of parameters. Our techniques also resolve open questions about universal tamper detection against families restricted in cardinality rather than in circuit size. We settle a question of Broadbent, Kapshikar and Rochette on relaxed tamper detection. As a corollary, we obtain the first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.

Related papers

• The uncloneable bit exists [0.5352699766206808]
  We establish quantum uncloneable encryption with unconditional security.<n>We prevent two non-communicating adversaries from simultaneously decrypting a single ciphertext $-$ even when both are given the key.
  arXiv  Detail & Related papers  (2026-03-09T20:33:33Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• 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.<n>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)
• 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)
• Split-State Non-Malleable Codes and Secret Sharing Schemes for Quantum Messages [14.150289683819759]
  We introduce the notions of split-state non-malleable codes and secret sharing schemes for quantum messages secure against quantum adversaries with shared entanglement. More precisely, we construct efficiently encodable and decodable split-state non-malleable codes and secret sharing schemes for quantum messages preserving entanglement with external systems.
  arXiv  Detail & Related papers  (2023-08-12T05:15:35Z)
• Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions [12.45203887838637]
  We construct quantum public-key encryption from one-way functions. In our construction, public keys are quantum, but ciphertexts are classical.
  arXiv  Detail & Related papers  (2023-04-04T13:57: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)
• From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments [8.834776091974218]
  We show the first public key encryption scheme from cryptographic emphnon-abelian group actions. We construct the scheme through a new abstraction called swap-trapdoor function pairs. We give a simple and efficient compiler that converts the flavor of quantum bit commitments.
  arXiv  Detail & Related papers  (2022-10-12T07:40:05Z)
• 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)
• Fault tolerant quantum data locking [0.0]
  We present a quantum data locking protocol that employs pseudo-random circuits consisting of Clifford gates only. We show that information can be encrypted into $n$-qubit code words using order $n. As an application, we discuss an efficient method for encrypting the output of a quantum computer.
  arXiv  Detail & Related papers  (2020-03-25T16:07:41Z)

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.