e, Who Must Not Be Named: Cryptanalysis of LCG-Based Randomness in Guillou-Quisquater

This work presents a lattice and polynomial-based attack on the Guillou–Quisquater identification protocol when its ephemeral randomizers are generated by a known-parameter LCG. The attack exploits short integer relations among challenges to eliminate the secret-dependent term, recover the initial LCG state through polynomial GCD computation, and subsequently recover the secret, without requiring the public exponent(e) during the recovery procedure.