Not Just Regular Decoding: Asymptotics and Improvements of Regular Syndrome Decoding Attacks

ePrint Report: Not Just Regular Decoding: Asymptotics and Improvements of Regular Syndrome Decoding Attacks

Andre Esser, Paolo Santini

Cryptographic constructions often base security on structured problem variants to enhance efficiency or to enable advanced functionalities. This led to the introduction of the Regular Syndrome Decoding (RSD) problem, which guarantees that a solution to the Syndrome Decoding (SD) problem follows a particular block-wise structure. Despite recent attacks exploiting that structure by Briaud and Øygarden (Eurocrypt ’23) and Carozza, Couteau and Joux …

advanced attacks base cryptographic decoding efficiency enable eprint report introduction led problem report security syndrome