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

Lecture notes in computer science

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

María Naya‐Plasencia, André Schrottenloher

Published Jan 1, 2020• 25 citations
Publisher
DOI
10.1007/978-3-030-45724-2_11

Related papers

Quantum Algorithms for the kkk-xor Problem

Lorenzo Grassi, María Naya‐Plasencia, André Schrottenloher

Lecture notes in computer science•Jan 1, 2018•31 citations

Improved Quantum Algorithms for the k-XOR Problem

André Schrottenloher

Lecture notes in computer science•Jan 1, 2022•7 citations

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

María Naya‐Plasencia, André Schrottenloher

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.

•Jan 1, 2019•0 citations

Margin Propagation Based XOR-SAT Solvers for Decoding of LDPC Codes

Ankita Nandi, Shantanu Chakrabartty, Chetan Singh Thakur

Decoding of Low-Density Parity Check (LDPC) codes can be viewed as a special case of XOR-SAT problems, for which low-computational complexity bit-flipping algorithms have been proposed in the literature. However, a performance gap exists between the bit-flipping LDPC decoding algorithms and the benchmark LDPC decoding algorithms, such as the Sum-Product Algorithm (SPA). In this paper, we propose an XOR-SAT solver using log-sum-exponential functions and demonstrate its advantages for LDPC decoding. This is then approximated using the Margin Propagation formulation to attain a low-complexity LDPC decoder. The proposed algorithm uses soft information to decide the bit-flips that maximize the number of parity check constraints satisfied over an optimization function. The proposed solver can achieve results that are within 0.1dB of the Sum-Product Algorithm for the same number of code iterations. It is also at least$10 \times $lower than other Gradient-Descent Bit Flipping decoding algorithms, which are also bit-flipping algorithms based on optimization functions. The approximation using the Margin Propagation formulation does not require any multipliers, resulting in significantly lower computational complexity than other soft-decision Bit-Flipping LDPC decoders.

arXiv:2402.04959•IEEE Transactions on Communications•Dec 18, 2024•3 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.

•May 19, 2019•0 citations

Quantum Merging Algorithms

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

•Oct 13, 2019•0 citations
Decoding of Low-Density Parity Check (LDPC) codes can be viewed as a special case of XOR-SAT problems, for which low-computational complexity bit-flipping algorithms have been proposed in the literature. However, a performance gap exists between the bit-flipping LDPC decoding algorithms and the benchmark LDPC decoding algorithms, such as the Sum-Product Algorithm (SPA). In this paper, we propose an XOR-SAT solver using log-sum-exponential functions and demonstrate its advantages for LDPC decoding. This is then approximated using the Margin Propagation formulation to attain a low-complexity LDPC decoder. The proposed algorithm uses soft information to decide the bit-flips that maximize the number of parity check constraints satisfied over an optimization function. The proposed solver can achieve results that are within 0.1dB of the Sum-Product Algorithm for the same number of code iterations. It is also at least$10 \times $lower than other Gradient-Descent Bit Flipping decoding algorithms, which are also bit-flipping algorithms based on optimization functions. The approximation using the Margin Propagation formulation does not require any multipliers, resulting in significantly lower computational complexity than other soft-decision Bit-Flipping LDPC decoders.
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.