International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Ilya Mironov

Affiliation: Google

Publications

Year
Venue
Title
2018
JOFC
2017
TCC
2016
CRYPTO
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2015
EUROCRYPT
2013
CRYPTO
2013
CRYPTO
2012
EUROCRYPT
2012
CRYPTO
2010
FSE
2009
CRYPTO
2006
CHES
2006
EUROCRYPT
2006
PKC
2006
EPRINT
Hard Instances of the Constrained Discrete Logarithm Problem
The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the constrained DLP depends on the choice of the set. Motivated by cryptographic applications, we study sets with succinct representation for which the constrained DLP is hard. We draw on earlier results due to Erd\"os et~al. and Schnorr, develop geometric tools such as generalized Menelaus' theorem for proving lower bounds on the complexity of the constrained DLP, and construct sets with succinct representation with provable non-trivial lower bounds.
2006
EPRINT
Applications of SAT Solvers to Cryptanalysis of Hash Functions
Ilya Mironov Lintao Zhang
Several standard cryptographic hash functions were broken in 2005. Some essential building blocks of these attacks lend themselves well to automation by encoding them as CNF formulas, which are within reach of modern SAT solvers. In this paper we demonstrate effectiveness of this approach. In particular, we are able to generate full collisions for MD4 and MD5 given only the differential path and applying a (minimally modified) off-the-shelf SAT solver. To the best of our knowledge, this is the first example of a SAT-solver-aided cryptanalysis of a non-trivial cryptographic primitive. We expect SAT solvers to find new applications as a validation and testing tool of practicing cryptanalysts.
2006
EPRINT
MV3: A new word based stream cipher using rapid mixing and revolving buffers
MV3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as RC4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like RC4's, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast --- it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size < 256 bits.
2002
CRYPTO
2002
EPRINT
(Not So) Random Shuffles of RC4
Ilya Mironov
Most guidelines for implementation of the RC4 stream cipher recommend discarding the first 256 bytes of its output. This recommendation is based on the empirical fact that known attacks can either cryptanalyze RC4 starting at any point, or become harmless after these initial bytes are dumped. The motivation for this paper is to find a conservative estimate for the number of bytes that should be discarded in order to be safe. To this end we propose an idealized model of RC4 and analyze it applying the theory of random shuffles. Based on our analysis of the model we recommend dumping at least 512 bytes.
2001
EUROCRYPT
2001
EPRINT
A Note on Cryptanalysis of the Preliminary Version of the NTRU Signature Scheme
Ilya Mironov
In this paper a preliminary version of the NTRU signature scheme is cryptanalyzed. The attack exploits a correlation between some bits of a signature and coefficients of a secret random polynomial. The attack does not apply to the next version of the signature scheme.

Program Committees

Crypto 2019
Eurocrypt 2017
Crypto 2014
Eurocrypt 2014
PKC 2014
TCC 2013
Crypto 2010
Crypto 2005