KryFoVe: Computeralgebra

Project Topic

Applications of advanced algebraic-symbolic methods of computer algebra to crypto analysis, to coding theory and to formal verification of microelectronic systems.

Project Description

The notion of the Groebner basis emerged in the 1960s in the works of Bruno Buchberger, where this notion was introduced along with some algorithmic means to compute it. Soon the notion of the Groebner basis became an important tool for mathematicians, in particular for those working in algebraic geometry and singularity theory. Recently, Groebner bases drew a lot of attention from researchers working in applied mathematics. This is mainly due to applications of Groebner bases in solving systems of polynomial equations. The Groebner bases found their applications in solving systems, where classical numerical methods are unstable or false, also in coding theory, cryptography, control and system theory, biology and other areas. KryFoVe aims at further research of applications of Groebner bases in coding theory and cryptanalysis. We investigate and propose new methods of how the problem of decoding a message, which has been transmitted via a noisy channel, can be reduced to solving a system of polynomial equations over a finite field and can then efficiently be solved. In the frame of this project we also investigate algebraic attacks on block/stream ciphers.

Project Members

Project Chair

• Prof. Dr. Gert-Martin Greuel in cooperation with
• Prof. Dr. Gerhard Pfister, Department of Mathematics, University of Kaiserslautern

Participating Research Groups

• Algebra, Geometry and Computer Algebra Group (Department of Mathematics)
• Sect. System Analysis, Prognosis and Control (formerly Sect. Adaptive Systems) (Fraunhofer Institute for Industrial Mathematics (ITWM))
• Electronic Design Automation Group (Department of Electrical Engineering and Information Technology)

Scientific Personnel

PhD Students:

• M.Sc. Stanislav Bulygin
• Dipl.-Math. Oliver Wienand

External Cooperation

• Dr. Ruud Pellikaan (Department of Mathematics, Technical University of Eindhoven, The Netherlands)
• Prof. Dr. Antonio Campillo (Departamento de Algebra, Universidad de Valladolid, Spain)
• Dr. Sergiy Ovsienko (Department of Mechanics and Mathematics, Kyiv Shevchenko University)
• Dr. Diego Ruano
• Dipl.-Math. Michael Brickenstein (Mathematisches Forschungsinstitut Oberwolfach)
• Project VerSiS

Project Events and Achievements

Project start: 01.03.2006 with a duration until the middle of 2008

Visits by external researchers:

• 8. December 2005: Le Van Schroeer (Bundesamt fuer Sicherheit in der Informationstechnik, Bonn)
• 16. - 20. January 2006: Ruud Pellikaan (Department of Mathematics, Technical University of Eindhoven, Netherlands)
• 22. - 24. May 2006: Christopher Hillar (Texas A&M and RICAM)
• 12. - 25. June 2006: Sergiy Ovsienko (Department of Mechanics and Mathematics, Kyiv Shevchenko University)
• 17. - 18. January 2007: Martin Albrecht (University of Bremen)
• 17. January - 14. February 2007: Sergiy Ovsienko (Department of Mechanics and Mathematics, Kyiv Shevchenko University)
• 26. May - 2. June 2007: José Ignacio Farrán (Universidad de Valladolid, Spain)

Talks:

• 8. December 2005: Le Van Schroeer: "Kryptographie im Staatsdienst";
• 8. December 2005: Stanislav Bulygin: "Non-Commutative Polly Cracker Cryptosystem Security Issues"
• 18. January 2006: Ruud Pellikaan: "Decoding cyclic codes with Groebner bases"
• 18. January 2006: Stanislav Bulygin: "Decoding algebraic-geometric codes with Groebner bases"
• 3. May 2006: Stanislav Bulygin: "Finding Minimum Distance and Decoding Linear Error-correcting Codes with Groebner Bases", Special Semester on Groebner Bases, Linz, Austria
• 24. May 2006: Christopher Hillar: "Finite Generation of Symmetric Ideals in Infinite Dimensional Polynomial Rings"
• 23. June 2006: Sergiy Ovsienko: "Representation Theory and Commutative Algebra"
• 27. October 2006: Stanislav Bulygin: "Decoding of linear codes with the use of Groebner bases", Seminaire Cryptographie, Codes et Algorithmique, ENSTA, Paris, France
• 9. November 2006: Michael Brickenstein: "SymmgbF2: "Gröbner bases calculation over GF(2) using symmetries"
• 30. November 2006: Stanislav Bulygin: "Decoding and finding the minimum distance of error-correcting codes with Groebner bases", DIAMANT/EIDMA symposium, Vught, Netherlands
• 18. January 2007: Martin Albrecht: "Algebraische Attacken auf Kryptosysteme"
• 22. January 2007: Gert-Martin Greuel: "Some new developments in the theory of Gröbner bases and applications to formal verification and cryptography", RIMS International Conference on Theoretical Effectivity and Practical Effectivity of Gröbner Bases, Kyoto, Japan
• 28. February 2007: Stanislav Bulygin and Oliver Wienand: "New developments in the theory of Gröbner bases to formal verification, cryptography, and coding theory"
• 26. March 2007: Stanislav Bulygin: "Some Problems from Coding Theory and Cryptography", DMV Studierendenkonferenz, Berlin
• 26. March 2007: Oliver Wienand: Some new developments in the theory of Groebner bases and applications to formal verification and cryptography, Segovia, Spain
• 16. April 2007: Stanislav Bulygin: "Decoding linear codes via solving systems of polynomial equations", IMA Workshop "Coding, Complexity, and Communications", Minneapolis, USA
• 16. April 2007: Diego Ruano: "Metric structure of linear codes", IMA Workshop "Coding, Complexity, and Communications", Minneapolis, USA
• 24. May 2007: Ruud Pellikaan: "Decoding error-correcting codes with Groebner bases", 28th Symposium on Information Theory in the Benelux, Enschede, The Netherlands
• 30. May 2007: Oliver Wienand: "Standard Bases over Rings with Zero-Divisors", Computeralgebra-Tagung
• 25. June 2007: Stanislav Bulygin:"On decoding up to error correcting capacity of linear error-correcting codes with Gröbner bases", MEGA2007, Strobl, Austria
• 25. June 2007: Diego Ruano: "Metric structure of linear codes and algebraic-geometry codes", MEGA2007, Strobl, Austria
• 9. October 2007: Ruud Pellikaan: "Decoding linear codes with Gröbner bases", Thematic Seminar "Algebraic Geometry, Coding and Computing", University of Valladolid, Segovia, Spain
• 9. October 2007: Stanislav Bulygin: "Decoding linear codes with Groebner bases. Part II: Experimental results and comparison of methods", Thematic Seminar "Algebraic Geometry, Coding and Computing", University of Valladolid, Segovia, Spain
• 10. October 2007: Diego Ruano: "Conway polynomials and Singular", Thematic Seminar "Algebraic Geometry, Coding and Computing", University of Valladolid, Segovia, Spain
• 29. November 2007: Gert-Martin Greuel:"New Groebner bases for formal verification and cryptography", DIAMANT/EIDMA Symposium, Soesterberg, Netherlands
• 1. March 2008: Ruud Pellikaan:"Decoding error-correcting codes with Groebner bases", European Mathematical Society Joint Mathematical Weekend, Coppenhagen, Denmark
• 14. March 2008: Stanislav Bulygin:"Decoding linear codes via systems solving: complexity issues and generalized Newton identities", SINGACOM Seminar on Algebraic Geometry and Singularities, Valladolid, Spain
• 29. April 2008: Stanislav Bulygin: "Attacking AES via Solving Systems in the Key Variables Only", First International Conference on Symbolic Computation and Cryptography, Beijing, China
• 3. July 2008: Stanislav Bulygin:"Algebraic-geometry codes in SINGULAR", Soria School on Computational Mathematics, Soria, Spain
• 4.July 2008: Stanislav Bulygin: "Decoding and finding the minimum distance of codes with Gröbner bases", Soria School on Computational Mathematics, Soria, Spain
• 5. July 2008: Stanislav Bulygin: "Decoding linear codes via polynomial systems solving. Generalized Newton identities for linear codes", Soria School on Computational Mathematics, Soria, Spain
• 27. July 2008: Stanislav Bulygin: "Obtaining and solving systems of equations in key variables only for the small variants of AES", Applications of Computer Algebra, Hagenberg, Austria
• 28. July 2008: Stanislav Bulygin: "Complexity issues in decoding linear codes via polynomial systems solving", Applications of Computer Algebra, Hagenberg, Austria

Project Publications

Bounded distance decoding of linear error-correcting codes with Gröbner bases

Stanislav Bulygin, Ruud Pellikaan. In: Journal of Symbolic Computation Special Issue Gröbner Bases Techniques in Cryptography and Coding Theory, to appear. Available online: http://dx.doi.org/10.1016/j.jsc.2007.12.003, 2009

Decoding linear error-correcting codes up to half the minimum distance with Gröbner bases

Stanislav Bulygin, Ruud Pellikaan. In: T. Mora and L. Perret and S. Sakata and M. Sala and C. Traverso ed., Working Title: "Gröbner Bases, Coding, and Cryptography". Proceedings of the Special Semester on Gröbner Bases, to appear, Volume 4, RISC Book Series (Springer, Heidelberg), 2009

Attacking AES via Solving Systems in the Key Variables Only

Michael Brickenstein, Stanislav Bulygin. In: First International Conference on Symbolic Computation and Cryptography, Beijing, China. P. 118--123, April, 2008

Decoding and finding the minimum distance with Gröbner bases: history and new insights

Stanislav Bulygin, Ruud Pellikaan. In: Selected Topics in Information and Coding Theory. World Scientific, 2008

Towards a Better Understanding of the Semigroup Tree

Maria Bras-Amoros, Stanislav Bulygin. In: Discrete Mathematics. Submitted, 2008

Obtaining and solving systems of equations in key variables only for the small variants of AES

Stanislav Bulygin, Michael Brickenstein. In: Mathematics in Computer Science, Special Issue "Symbolic Computation and Cryptography". Available online: http://eprint.iacr.org/2008/435, Submitted, 2008

Decoding error-correcting codes with Groebner bases

Stanislav Bulygin, Ruud Pellikaan. In: Proceedings of the 28th Symposium on Information Theory in the Benelux, Enschede, The Netherlands. P. 3--10, May, 2007

On the structure of generalized toric codes

Diego Ruano. In: Special Issue of JSC EACA'06. 2007

Groebner basis: applications to algebraic coding theory (in Spanish)

E. Martinez-Moro, C. Munuera, Diego Ruano. Instituto Venezolano de Investigaciones Cientificas, 125 pages. ISBN: 978-980-261-087-7, 2007

On the Parameters of r-dimensional Toric Codes

Diego Ruano. In: Finite Fields and their Applications. Volume 13, Number 4, Elsevier, P. 962--976, 2007

Noncommutative Polly Cracker-type cryptosystems and chosen-ciphertext security

T. Rai, Stanislav Bulygin. In: Preprint. Available online: http://eprint.iacr.org/2008/514, 2007

Generalized Hermitian Codes over GF(2^r)

Stanislav Bulygin. In: IEEE Transactions on Information Theory. 2006

Equisingular Calculations for Plane Curve Singularities

A. Campillo, Gert-Martin Greuel, C. Lossen. In: Proceedings of MEGA 2003. 2006