109 citations · 112 across the 5 of their papers we have counts for
7 papers
Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms
André Schrottenloher
Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its co…
A Tight Quantum Algorithm for Multiple Collision Search
Xavier Bonnetain, Johanna Loyer, André Schrottenloher +1
Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a singl…
Finding many Collisions via Reusable Quantum Walks
Xavier Bonnetain, André Chailloux, André Schrottenloher +1
Given a random function with domain and codomain , with , a collision of is a pair of distinct inputs with the same image. Collision finding is an…
Beyond quadratic speedups in quantum attacks on symmetric schemes
Xavier Bonnetain, André Schrottenloher, Ferdinand Sibleyras
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…
Universal Horn Sentences and the Joint Embedding Property
Manuel Bodirsky, Jakub Rydval, André Schrottenloher
The finite models of a universal sentence in a finite relational signature are the age of a structure if and only if has the joint embedding property. We prove that the com…
Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm
Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia +2
In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon's period-findi…
Improved Classical and Quantum Algorithms for Subset-Sum
Xavier Bonnetain, Rémi Bricout, André Schrottenloher +1
We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from $\tilde{\mathc…