Time-memory tradeoffs for large-weight syndrome decoding in ternary codes

DOI10.1007/978-3-030-97121-2_4MaRDI QIDQ5087252zbMATH OpenOpenAlexFDO

Authors Pierre Karpman, Charlotte Lefevre

Publication date 8 July 2022

Published in Public-Key Cryptography – PKC 2022 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-97121-2_4

zbMATH Keywords

lattice-based cryptographytrapdoor functions

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Recommendations

• Ternary Syndrome Decoding with large weight
• Improved information set decoding for code-based cryptosystems with constrained memory
• Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
• An algorithm for generalized syndrome decoding problem
• Smaller decoding exponents: ball-collision decoding

Cites work

• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• An algorithmic framework for the generalized birthday problem
• Dissection-BKW
• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• Information-set decoding for linear codes over \(\mathbb F_q\)
• New generic algorithms for hard knapsacks
• Ternary Syndrome Decoding with large weight
• The complexity of information set decoding
• The extended \(k\)-tree algorithm
• Time-memory tradeoffs for large-weight syndrome decoding in ternary codes
• Wave: a new family of trapdoor one-way preimage sampleable functions based on codes

Cited in

(5)

• Time-memory tradeoffs for large-weight syndrome decoding in ternary codes
• Concrete time/memory trade-offs in generalised Stern's ISD algorithm
• New time-memory trade-offs for subset sum -- improving ISD in theory and practice
• Ternary Syndrome Decoding with large weight
• Wave Parameter Selection

This page was built for publication: Time-memory tradeoffs for large-weight syndrome decoding in ternary codes

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