Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography

DOI10.1007/978-981-99-8739-9_9MaRDI QIDQ6595926zbMATH OpenFDO

Authors Maxime Bombar, Alain Couvreur, Thomas Debris-Alazard

Publication date 30 August 2024

Full work available at URL https://doi.org/10.1007/978-981-99-8739-9_9

zbMATH Keywords

decoding problemOHCPsearch-to-decision reductionsworst-case to average-case

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60) Linear codes (general theory) (94B05) Decoding (94B35)

Recommendations

• On codes and learning with errors over function fields
• Reduction from sparse LPN to LPN, dual attack 3.0
• Statistical decoding 2.0: reducing decoding to LPN
• Worst-case hardness for LPN and cryptographic hashing via code smoothing
• Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)

Cites work

• A direct key recovery attack on SIDH
• An efficient key recovery attack on SIDH
• An efficient pseudo-random generator provably as secure as syndrome decoding
• Analysis of information set decoding for a sub-linear error weight
• Asymptotic Improvement of the Gilbert–Varshamov Bound for Linear Codes
• Breaking SIDH in polynomial time
• Correlated pseudorandomness from the hardness of quasi-abelian decoding
• Decoding one out of many
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• Efficient pseudorandom correlation generators from ring-LPN
• Efficient public key encryption based on ideal lattices (extended abstract)
• scientific article; zbMATH DE number 4112524 (Why is no real title available?)
• Leftover Hash Lemma, Revisited
• Making NTRU as secure as worst-case problems over ideal lattices
• On codes and learning with errors over function fields
• On computing nearest neighbors with applications to decoding of binary linear codes
• On ideal lattices and learning with errors over rings
• On lattices, learning with errors, random linear codes, and cryptography
• On the hardness of the NTRU problem
• On the inherent intractability of certain coding problems (Corresp.)
• On the ring-LWE and polynomial-LWE problems
• Pseudorandomness of ring-LWE for any ring and modulus
• Random codes: minimum distances and error exponents
• Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
• Statistical decoding 2.0: reducing decoding to LPN
• Towards classical hardness of module-LWE: the linear rank case
• Wave: a new family of trapdoor one-way preimage sampleable functions based on codes
• Worst-case hardness for LPN and cryptographic hashing via code smoothing
• Worst-case to average-case reductions for module lattices

Cited in

(5)

• On codes and learning with errors over function fields
• Limitations of the decoding-to-LPN reduction via code smoothing
• Worst and average case hardness of decoding via smoothing bounds
• A minrank-based encryption scheme à la Alekhnovich-Regev
• The syndrome weight distribution in quasi-cyclic codes, applications to BIKE and HQC

This page was built for publication: Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6595926)