International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Igor Semaev

Publications

Year
Venue
Title
2018
TOSC
Separable Statistics and Multidimensional Linear Cryptanalysis 📺
Stian Fauskanger Igor Semaev
Multidimensional linear cryptanalysis of block ciphers is improved in this work by introducing a number of new ideas. Firstly, formulae is given to compute approximate multidimensional distributions of the encryption algorithm internal bits. Conventional statistics like LLR (Logarithmic Likelihood Ratio) do not fit to work in Matsui’s Algorithm 2 for large dimension data, as the observation may depend on too many cipher key bits. So, secondly, a new statistic which reflects the structure of the cipher round is constructed instead. Thirdly, computing the statistic values that will fall into a critical region is presented as an optimisation problem for which an efficient algorithm is suggested. The algorithm works much faster than brute forcing all relevant key bits to compute the statistic. An attack for 16-round DES was implemented. We got an improvement over Matsui’s attack on DES in data and time complexity keeping success probability the same. With 241.81 plaintext blocks and success rate 0.83 (computed theoretically) we found 241.46 (which is close to the theoretically predicted number 241.81) key-candidates to 56-bit DES key. Search tree to compute the statistic values which fall into the critical region incorporated 245.45 nodes in the experiment and that is at least theoretically inferior in comparison with the final brute force. To get success probability 0.85, which is a fairer comparison to Matsui’s results, we would need 241.85 data and to brute force 241.85 key-candidates. That compares favourably with 243 achieved by Matsui.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
EPRINT
2014
EPRINT
2010
EPRINT
Improved Agreeing-Gluing Algorithm
Igor Semaev
A system of algebraic equations over a finite field is called sparse if each equation depends on a low number of variables. Finding efficiently solutions to the system is an underlying hard problem in the cryptanalysis of modern ciphers. In this paper a deterministic Improved Agreeing-Gluing Algorithm is introduced. The expected running time of the new Algorithm on uniformly random instances of the problem is rigorously estimated. The estimate is at present the best theoretical bound on the complexity of solving average instances of the problem. In particular, this is a significant improvement over those in our earlier papers [10, 11]. In sparse Boolean equations a gap between the worst case and the average time complexity of the problem has significantly increased.
2007
EPRINT
On solving sparse algebraic equations over finite fields II
Igor Semaev
A system of algebraic equations over a finite field is called sparse if each equation depends on a small number of variables. Finding efficiently solutions to the system is an underlying hard problem in the cryptanalysis of modern ciphers. In this paper deterministic Agreeing-Gluing algorithm introduced earlier by Raddum and Semaev for solving such equations is studied. Its expected running time on uniformly random instances of the problem is rigorously estimated. This estimate is at present the best theoretical bound on the complexity of solving average instances of the above problem. In particular, it significantly overcomes our previous results. In characteristic 2 we observe an exciting difference with the worst case complexity provided by SAT solving algorithms.
2007
EPRINT
Solving MRHS linear equations
Håvard Raddum Igor Semaev
A new method for solving algebraic equation systems common in cryptanalysis is proposed. Our method differs from the others in that the equations are not represented as multivariate polynomials, but as a system of Multiple Right Hand Sides linear equations. The method was tested on scaled versions of the AES. The results overcome significantly what was previously achieved with Gr\"{o}bner Basis related algorithms.
2006
PKC
2006
EPRINT
New Technique for Solving Sparse Equation Systems
HÃ¥vard Raddum Igor Semaev
Most of the recent cryptanalysis on symmetric key ciphers have focused on algebraic attacks. The cipher being attacked is represented as a non-linear equation system, and various techniques (Buchberger, F4/F5, XL, XSL) can be tried in order to solve the system, thus breaking the cipher. The success of these attacks has been limited so far. In this paper we take a different approach to the problem of solving non-linear equation systems, and propose a new method for solving them. Our method differs from the others in that the equations are not represented as multivariate polynomials, and that the core of the algorithm for finding the solution can be seen as message-passing on a graph. Bounds on the complexities for the main algorithms are presented and they compare favorably with the known bounds. The methods have also been tested on reduced-round versions of DES with good results. This paper was posted on ECRYPT's STVL website on January 16th 2006.
2005
FSE
2004
EPRINT
Summation polynomials and the discrete logarithm problem on elliptic curves
Igor Semaev
The aim of the paper is the construction of the index calculus algorithm for the discrete logarithm problem on elliptic curves. The construction presented here is based on the problem of finding bounded solutions to some explicit modular multivariate polynomial equations. These equations arise from the elliptic curve summation polynomials introduced here and may be computed easily. Roughly speaking, we show that given the algorithm for solving such equations, which works in polynomial or low exponential time in the size of the input, one finds discrete logarithms faster than by means of Pollard's methods.
2003
EPRINT
A reduction of the space for the parallelized Pollard lambda search on elliptic curves over prime finite fields and on anomalous binary elliptic curves
Igor Semaev
Let $E$ be an elliptic curve defined over a prime finite field $F_p$ by a Weierstrass equation. In this paper we introduce a new partition of $E(F_p)$ into classes which are generally larger than $\{\pm R\}$. We give an effective procedure to compute representatives of such classes. So one can iterate the pseudorandom function, related to a discrete logarithm problem in $E(F_p)$, on the set of representatives of classes and get probably some speed up in computing discrete logarithms. The underlying idea how to enlarge known classes on anomalous binary elliptic curves is given.