2026-07-22T11:56:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18557 2024-03-06T11:02:07Z ddc:004 open_access

Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator Bouillaguet, Charles Martinez, Florette Vergnaud, Damien Cryptography pseudo-random generator subset-sum problem 3SUM problem cryptanalysis We present attacks on a generalized subset-sum pseudorandom generator, which was proposed by von zur Gathen and Shparlinski in 2004. Our attacks rely on a sub-quadratic algorithm for solving a vectorial variant of the 3SUM problem, which is of independent interest. The attacks presented have complexities well below the brute-force attack, making the generators vulnerable. We provide a thorough analysis of the attacks and their complexities and demonstrate their practicality through implementations and experiments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Charles Bouillaguet and Florette Martinez and Damien Vergnaud 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.23 urn:nbn:de:0030-drops-185579 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.23 eng https://creativecommons.org/licenses/by/4.0/legalcode