Polynomial reduction from syndrome decoding problem to regular decoding problem

DOI10.1007/S10623-025-01567-2MaRDI QIDQ6956600zbMATH OpenFDO

Authors Pavol Zajac

Publication date 18 July 2025

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10623-025-01567-2

zbMATH Keywords

reductioncode-based cryptographysyndrome decoding problemregular syndrome decoding problem

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Decoding (94B35)

Cites work

• A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
• Connecting the complexity of MQ- and code-based cryptosystems
• MRHS Equation Systems that can be Solved in Polynomial Time
• MRHS solver based on linear algebra and exhaustive search
• Not just regular decoding: asymptotics and improvements of regular syndrome decoding attacks
• On solving sparse MRHS equations with bit-flipping
• Progress in Cryptology – Mycrypt 2005
• Short signatures from regular syndrome decoding in the head
• Solving multiple right hand sides linear equations
• Sparse Boolean equations and circuit lattices
• Syndrome decoding in the head: shorter signatures from zero-knowledge proofs
• Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity
• \textsf{ReSolveD}: shorter signatures from regular syndrome decoding and VOLE-in-the-head

This page was built for publication: Polynomial reduction from syndrome decoding problem to regular decoding problem

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