HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Theses

Quantum Algorithms for Cryptanalysis and Quantum-safe Symmetric Cryptography

Abstract : Modern cryptography relies on the notion of computational security. The level of security given by a cryptosystem is expressed as an amount of computational resources required to break it. The goal of cryptanalysis is to find attacks, that is, algorithms with lower complexities than the conjectural bounds. With the advent of quantum computing devices, these levels of security have to be updated to take a whole new notion of algorithms into account. At the same time, cryptography is becoming widely used in small devices (smart cards, sensors), with new cost constraints. In this thesis, we study the security of secret-key cryptosystems against quantum adversaries. We first build new quantum algorithms for k-list (k-XOR or k-SUM) problems, by composing exhaustive search procedures. Next, we present dedicated cryptanalysis results, starting with a new quantum cryptanalysis tool, the offline Simon's algorithm. We describe new attacks against the lightweight algorithms Spook and Gimli and we perform the first quantum security analysis of the standard cipher AES. Finally, we specify Saturnin, a family of lightweight cryptosystems oriented towards post-quantum security. Thanks to a very similar structure, its security relies largely on the analysis of AES.
Document type :
Theses
Complete list of metadata

https://hal.inria.fr/tel-03142366
Contributor : André Schrottenloher Connect in order to contact the contributor
Submitted on : Monday, February 15, 2021 - 11:14:16 PM
Last modification on : Friday, January 28, 2022 - 3:43:31 AM
Long-term archiving on: : Sunday, May 16, 2021 - 9:26:34 PM

File

thesis_manuscript_final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03142366, version 1

Citation

André Schrottenloher. Quantum Algorithms for Cryptanalysis and Quantum-safe Symmetric Cryptography. Cryptography and Security [cs.CR]. Sorbonne Université, 2021. English. ⟨tel-03142366v1⟩

Share

Metrics

Record views

539

Files downloads

713