A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
DOI10.1007/978-3-031-30589-4_14zbMath1528.94037OpenAlexW4365810594MaRDI QIDQ6083670
Morten Øygarden, Pierre Briaud
Publication date: 8 December 2023
Published in: Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-30589-4_14
NP-completenessprovable securitycryptographic hash functionssyndrome decodingWagner's generalized birthday problem
Computational learning theory (68Q32) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
- Secure arithmetic computation with constant computational overhead
- LPN decoded
- On the complexity of solving quadratic Boolean systems
- Revisiting the hardness of binary error LWE
- Improved cryptanalysis of UOV and Rainbow
- Efficient pseudorandom correlation generators from ring-LPN
- Efficient pseudorandom correlation generators: silent OT extension and more
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
- New Algorithms for Learning in Presence of Errors
- Decoding Random Linear Codes in $\tilde{\mathcal{O}}(2^{0.054n})$
- Hybrid approach for solving multivariate systems over finite fields
- Powers of tensors and fast matrix multiplication
- Security Bounds for the Design of Code-Based Cryptosystems
- An inequality for Hilbert series of graded algebras.
- Solving sparse linear equations over finite fields
- Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
- A Statistical Decoding Algorithm for General Linear Block Codes
- Solving Quadratic Equations with XL on Parallel Architectures
- Smaller Decoding Exponents: Ball-Collision Decoding
- Efficient Encryption From Random Quasi-Cyclic Codes
- Progress in Cryptology – Mycrypt 2005
- TinyKeys: a new approach to efficient multi-party computation
- Moz\(\mathbb{Z}_{2^k}\)arella: efficient vector-OLE and zero-knowledge proofs over \(\mathbb{Z}_{2^k}\)
- Statistical decoding 2.0: reducing decoding to LPN
This page was built for publication: A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
