Beyond quadratic speedups in quantum attacks on symmetric schemes

• URL: http://arxiv.org/abs/2110.02836v1
• Date: Wed, 6 Oct 2021 15:10:31 GMT
• Title: Beyond quadratic speedups in quantum attacks on symmetric schemes
• Authors: Xavier Bonnetain, Andr\'e Schrottenloher, Ferdinand Sibleyras
• Abstract summary: We report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit.
• Score: 30.01567358439495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only, with a more than quadratic time speedup compared to the best classical attack. We study the 2XOR-Cascade construction of Ga\v{z}i and Tessaro (EUROCRYPT~2012). It is a key length extension technique which provides an n-bit block cipher with 5n/2 bits of security out of an n-bit block cipher with 2n bits of key, with a security proof in the ideal model. We show that the offline-Simon algorithm of Bonnetain et al. (ASIACRYPT~2019) can be extended to, in particular, attack this construction in quantum time \~O($2^n$), providing a 2.5 quantum speedup over the best classical attack. Regarding post-quantum security of symmetric ciphers, it is commonly assumed that doubling the key sizes is a sufficient precaution. This is because Grover's quantum search algorithm, and its derivatives, can only reach a quadratic speedup at most. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit. In particular, the 2XOR-Cascade cannot be used to generically strengthen block ciphers against quantum adversaries, as it would offer only the same security as the block cipher itself.

Related papers

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• Quantum Key Leasing for PKE and FHE with a Classical Lessor [19.148581164364387]
  We consider the problem of secure key leasing, also known as revocable cryptography. This problem aims to leverage unclonable nature of quantum information. We construct a secure key leasing scheme to lease a decryption key of a (classical) public-key, homomorphic encryption scheme.
  arXiv  Detail & Related papers  (2023-10-22T15:25:29Z)
• 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)
• 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)
• 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 Key-length Extension [17.52560033614633]
  Quantum computers will reduce the effective key length of basic secret-key primitives, such as blockciphers. We provide positive results, with concrete and tight bounds, for both of these constructions against quantum attackers in ideal models. We introduce techniques for partially-quantum proofs without relying on analyzing the classical and quantum oracles separately.
  arXiv  Detail & Related papers  (2021-05-04T01:40:42Z)
• 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 Period Finding against Symmetric Primitives in Practice [3.04585143845864]
  We present the first complete implementation of the offline Simon's algorithm, and estimate its cost to attack the Chaskey, the block cipher PRINCE and the NIST lightweight candidate AEAD scheme Elephant. These attacks require a reasonable amount of qubits, comparable to the number of qubits required to break RSA-2048. We stress that our attacks could be applied in the future against today's communications, and recommend caution when choosing symmetric constructions for cases where long-term security is expected.
  arXiv  Detail & Related papers  (2020-11-13T17:12:49Z)
• 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)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)

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.