## CryptoDB

### Igor Semaev

#### Publications

**Year**

**Venue**

**Title**

2018

TOSC

Separable Statistics and Multidimensional Linear Cryptanalysis
📺
Abstract

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.

2010

EPRINT

Improved Agreeing-Gluing Algorithm
Abstract

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
Abstract

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
Abstract

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

EPRINT

New Technique for Solving Sparse Equation Systems
Abstract

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
Abstract

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
Abstract

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.

#### Coauthors

- An Braeken (1)
- An Commeine (1)
- Stian Fauskanger (2)
- Håvard Raddum (2)