We provide a toolbox based on \emph{analytic combinatorics} for these studies. It uses the structure of the considered polynomials to derive their generating functions and applies complex analysis techniques to get asymptotics. The toolbox is versatile and can be used for many different applications, including multivariate polynomial systems with arbitrarily many unknowns (of possibly different sizes) and simultaneous modular equations over different moduli. To demonstrate the power of this approach, we apply it to recent cryptanalytic results on number-theoretic pseudorandom generators for which we easily derive precise and formal analysis. We also present new theoretical applications to two problems on RSA key generation and randomness generation used in padding functions for encryption.
Category / Keywords: Coppersmith Methods, Analytic Combinatorics, Cryptanalysis, Pseudorandom Generators, RSA Key Generation, Encryption Padding Original Publication (with major differences): IACR-PKC-2016 Date: received 4 Jan 2016 Contact author: fabrice ben hamouda at ens fr Available format(s): PDF | BibTeX Citation Version: 20160104:224259 (All versions of this report) Short URL: ia.cr/2016/007