Semaev's Lecture

RSNT-ML に流れていた情報より。あの Semaev さんが東工大で講演会をなさるそうです。ウェブで同じ情報を見つけられなかったため、ちょっと長いのですが丸ごと転送します。

日時：11月5日、14:00～

場所：東京工業大学大岡山キャンパス、本館2階、230号室

Speaker: Igor Semaev 氏 (Bergen University)

Title: Solving sparse algebraic equations over finite fields

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. Several methods  are know to solve such equations:
1. Via computing the Groebner basis  of  the multivariate polynomials representing equations;
2. Represent( at least in characteristic 2) each equation and the whole system by a Conjunctive Normal Form(CNF) and apply SAT solving algorithms mostly based on Unit Clause Propagation and Clauses Resolution.

In the talk another approach to solving sparse algebraic equations is presented. Each equation of the system is represented by the list of its solutions. Then  deterministic Agreeing-Gluing algorithm due to Raddum-Semaev is applied. The expected running time of the Agreeing-Gluing algorithm on uniformly random instances  is rigorously estimated. This estimate is at present the best theoretical bound on the complexity of solving average instances of the problem.

In characteristic 2 we observe an exciting difference with  the worst case complexity provided by SAT solving algorithms. The reason for that is Agreeing is a more general technique than Unit Clause Propagation and Gluing is more general than  Clauses Resolution. Agreeing-Gluing is more powerful on equation systems as average equation in k variables has 2^{k-1} solutions while every clause has 2^k-1 satisfying assignments. So average CNF is harder than average system of sparse equations.

Then a more general and useful method  for representing and solving equations common in cryptanalysis will be explained. The new representation combines our previous representation of sparse equations and Linear Algebra. It is called  Multiple Right Hand Sides(MRHS) linear equations. Generalized Agreeing and Gluing are developed in order to solve MRHS linear equations. Experimental comparisons of this approach and F4 algorithm implemented in Magma is provided.

世話人・問い合わせ先：東工大数学専攻 佐藤孝和