Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Optimal Merging in Quantum k-xor and k-sum Algorithms.

María Naya‐Plasencia, André Schrottenloher

Published Jan 1, 2019• 0 citations
OpenAlex

Abstract

The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner’s CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle.

Related papers

Dedicated Quantum Attacks on XOR-Type Function With Applications to Beyond-Birthday- Bound MACs

Tairong Shi, Wenling Wu, Bin Hu +4 more

A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form of$\mathcal {O}$, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by$2^{t}(t\gt 0)$, the depth decreases by a factor of$\sqrt {2^{t}}$. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, includingSUM-ECBCand its variants (2K-SUM-ECBC,2K-ECBC_Plus), andGCM-SIV2. In the typical case whereSUM-ECBCis based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.

IEEE Transactions on Information Forensics and Security•Jan 1, 2024•3 citations

A Classical Quadratic Speedup for Planted kkk xor

Meghal Gupta, William He, Ryan O’Donnell +1 more

A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted \(k\)xor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant \(k\). Thus for such \(k\), the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.

arXiv:2508.09422•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•7 citations

Improved Quantum Algorithms for Subset Sum and kkk-SUM

Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii +1 more

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where $$ Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{Ψ_k})$, where $$ Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

arXiv:2608.07309•Aug 7, 2026•1 citation

Optimal Merging in Quantum kkk-xor and k-sum Algorithms

María Naya‐Plasencia, André Schrottenloher

Lecture notes in computer science•Jan 1, 2020•29 citations

General Quantum Meet-in-the-Middle Search Algorithm Based on Target Solution of Fixed Weight*

Xiang-Qun Fu, Wan‐Su Bao, Xiang 翔 Wang 汪 +1 more

Abstract Similar to the classical meet-in-the-middle algorithm, the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm. Aiming at the target vector of fixed weight, based on the quantum meet-in-the-middle algorithm, the algorithm for searching all n-product vectors with the same weight is presented, whose complexity is better than the exhaustive search algorithm. And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm. Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d, we present a general quantum meet-in-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight, the computational complexity of the algorithm is lower. And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.

Communications in Theoretical Physics•Oct 1, 2016•1 citation

Improved Quantum Algorithms for the k-XOR Problem

André Schrottenloher

Lecture notes in computer science•Jan 1, 2022•8 citations
The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner’s CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle.
A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form ofO\mathcal {O}O, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by2t(t>0)2^{t}(t\gt 0)2t(t>0), the depth decreases by a factor of2t\sqrt {2^{t}}2t​. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, includingSUM-ECBCand its variants (2K-SUM-ECBC,2K-ECBC_Plus), andGCM-SIV2. In the typical case whereSUM-ECBCis based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.
A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted kkkxor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant kkk. Thus for such kkk, the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.
The Subset Sum problem asks whether, given nnn integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is O∗(2n/2)O^*(2^{n/2})O∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/3)O^*(2^{n/3})O∗(2n/3) (Bernstein, Jeffery, Lange, and Meurer, 2013). The kkk-SUM problem is a parameterized version of Subset Sum asking whether there are kkk integers that sum to the target. The best classical upper bound for it is O~(n⌈k/2⌉)\widetilde O(n^{\lceil k/2\rceil})O(n⌈k/2⌉), whereas the best quantum running time is O~(nk/3)\widetilde O(n^{k/3})O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O~(nΦk)\widetilde O(n^{Φ_k})O(nΦk​) is known, where Φk=2k−⌊k/7⌋−⌊(k+3)/7⌋6 Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} Φk​=62k−⌊k/7⌋−⌊(k+3)/7⌋​ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case kkk-SUM in time O~(nΨk)\widetilde O(n^{Ψ_k})O(nΨk​), where Ψk=Φk−[k≡3 mod 7]9−[k≡6 mod 7]18. Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. Ψk​=Φk​−9[k≡3mod7]​−18[k≡6mod7]​. The algorithm is not only faster for all kkk congruent to 333 or 666 modulo 777, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for 777-SUM with the standard block reduction technique yields an O∗(22n/7)O^*(2^{2n/7})O∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3)O^*(2^{n/3})O∗(2n/3) algorithm.
Abstract Similar to the classical meet-in-the-middle algorithm, the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm. Aiming at the target vector of fixed weight, based on the quantum meet-in-the-middle algorithm, the algorithm for searching all n-product vectors with the same weight is presented, whose complexity is better than the exhaustive search algorithm. And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm. Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d, we present a general quantum meet-in-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight, the computational complexity of the algorithm is lower. And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.