New time-memory trade-offs for subset sum -- improving ISD in theory and practice
From MaRDI portal
Publication:6083669
DOI10.1007/978-3-031-30589-4_13zbMath1528.94047MaRDI QIDQ6083669
Publication date: 8 December 2023
Published in: Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)
code-based cryptographyNIST PQCinformation set decodingrepresentation techniquesecurity estimatesrecord computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ternary Syndrome Decoding with large weight
- LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes
- Decoding linear codes with high error rate and its impact for LPN security
- LPN decoded
- Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
- Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
- Advanced lattice sieving on GPUs, with tensor cores
- How to meet ternary LWE keys
- McEliece needs a break -- solving McEliece-1284 and quasi-cyclic-2918 with modern ISD
- Improved low-memory subset sum and LPN algorithms via multiple collisions
- The general sieve kernel and new records in lattice reduction
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
- Improved classical and quantum algorithms for subset-sum
- Refinements of the k-tree Algorithm for the Generalized Birthday Problem
- Analysis of Information Set Decoding for a Sub-linear Error Weight
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
- On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
- Improved Generic Algorithms for Hard Knapsacks
- Decoding Random Linear Codes in $\tilde{\mathcal{O}}(2^{0.054n})$
- Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory
- Attacking and Defending the McEliece Cryptosystem
- New Generic Algorithms for Hard Knapsacks
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Computing Partitions with Applications to the Knapsack Problem
- New directions in nearest neighbor searching with applications to lattice sieving
- Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in Ternary Codes
- Syndrome Decoding Estimator
- Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
- Noise-tolerant learning, the parity problem, and the statistical query model
This page was built for publication: New time-memory trade-offs for subset sum -- improving ISD in theory and practice