The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and A. Schrottenloher), and new efficient quantum algorithms for solving the K-xor problem (joint work with L. Grassi and A. Schrottenloher). We will discuss some implications of these results in quantum-safe symmetric cryptography.The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and A. Schrottenloher), and new efficient quantum algorithms for solving the K-xor problem (joint work with L. Grassi and A. Schrottenloher). We will discuss some implications of these results in quantum-safe symmetric cryptography.

Oct 1, 20170 citations

New algorithms for quantum (symmetric) cryptanalysis

María Naya‐Plasencia, André Schrottenloher, André Chailloux +1 more

The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and M. Naya-Plasencia), and new efficient quantum algorithms for solving the K-xor problem (joint work with L. Grassi and M. Naya-Plasencia) and a very recent improvement that provides optimal merging algorithms. We will discuss some implications of these results in quantum-safe symmetric cryptography.The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and M. Naya-Plasencia), and new efficient quantum algorithms for solving the K-xor problem (joint work with L. Grassi and M. Naya-Plasencia) and a very recent improvement that provides optimal merging algorithms. We will discuss some implications of these results in quantum-safe symmetric cryptography.

May 19, 20190 citations

Study and analysis of quantum inspired algorithms in quantum cryptography

Aloy Anuja Mary G

Jan 3, 20150 citations

New results on symmetric quantum cryptanalysis (Keynote speaker)

María Naya‐Plasencia

Sep 26, 20180 citations

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

Frédéric Magniez, Sebastian Zur

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$ , the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$ 's output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$ For the setting where $M=N$ , these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search uses $O(\sqrt N)$ queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function $f$'s output labels as interchangeable. We prove that such algorithm that makes $T$ queries, uses $S$ qubits, and finds a collision in a uniformly random function $f:[M]\to [N]$ with constant probability satisfies $$T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).$$ For the setting where $M=N$, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on $f: [n] \to [n^2]$ must satisfy $$T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),$$ matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using $S$ qubits can effectively retain information about only $O(S/\log N)$ collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.

quant-pharXiv:2609.10808Sep 11, 20260 citations

How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function

f:[N]\to [N]

, the BHT algorithm finds a collision using

O(N^{1/3})

queries and a quantumly accessible classical table containing

O(N^{1/3})

input-output pairs, whereas a logarithmic-space Grover search uses

O(\sqrt N)

queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function

f

's output labels as interchangeable. We prove that such algorithm that makes

T

queries, uses

S

qubits, and finds a collision in a uniformly random function

f:[M]\to [N]

with constant probability satisfies

T=Ω(N^{1/3}) \qquad\text{and}\qquad T^2S=Ω(N\log N).

For the setting where

M=N

, these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on

f: [n] \to [n^2]

must satisfy

T=Ω(n^{2/3}) \qquad\text{and}\qquad T^2S=Ω(n^2\log n),

matching Ambainis's quantum walk. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using

S

qubits can effectively retain information about only

O(S/\log N)

collision-free database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs.