Paper 2016/007

Easing Coppersmith Methods using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness

Fabrice Benhamouda, Céline Chevalier, Adrian Thillard, and Damien Vergnaud

Abstract

The \emph{Coppersmith methods} is a family of lattice-based techniques to find small integer roots of polynomial equations. They have found numerous applications in cryptanalysis and, in recent developments, we have seen applications where the number of unknowns and the number of equations are non-constant. In these cases, the combinatorial analysis required to settle the complexity and the success condition of the method becomes very intricate. 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.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in PKC 2016
Keywords
Coppersmith MethodsAnalytic CombinatoricsCryptanalysisPseudorandom GeneratorsRSA Key GenerationEncryption Padding
Contact author(s)
fabrice ben hamouda @ ens fr
History
2016-01-04: received
Short URL
https://ia.cr/2016/007
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/007,
      author = {Fabrice Benhamouda and Céline Chevalier and Adrian Thillard and Damien Vergnaud},
      title = {Easing Coppersmith Methods using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness},
      howpublished = {Cryptology ePrint Archive, Paper 2016/007},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/007}},
      url = {https://eprint.iacr.org/2016/007}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.