
KryFoVe: Computeralgebra
Project Topic
Applications of advanced algebraicsymbolic 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
Participating Research Groups
Scientific Personnel
PhD Students:
External Cooperation
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: "NonCommutative Polly Cracker Cryptosystem Security Issues"
 18. January 2006: Ruud Pellikaan: "Decoding cyclic codes with Groebner bases"
 18. January 2006: Stanislav Bulygin: "Decoding algebraicgeometric codes with Groebner bases"
 3. May 2006: Stanislav Bulygin: "Finding Minimum Distance and Decoding Linear Errorcorrecting 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 errorcorrecting codes with Groebner bases", DIAMANT/EIDMA symposium, Vught, Netherlands
 18. January 2007: Martin Albrecht: "Algebraische Attacken auf Kryptosysteme"
 22. January 2007: GertMartin 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 errorcorrecting 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 ZeroDivisors", ComputeralgebraTagung
 25. June 2007: Stanislav Bulygin:"On decoding up to error correcting capacity of linear errorcorrecting codes with Gröbner bases", MEGA2007, Strobl, Austria
 25. June 2007: Diego Ruano: "Metric structure of linear codes and algebraicgeometry 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: GertMartin Greuel:"New Groebner bases for formal verification and cryptography", DIAMANT/EIDMA Symposium, Soesterberg, Netherlands
 1. March 2008: Ruud Pellikaan:"Decoding errorcorrecting 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:"Algebraicgeometry 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
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
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
Michael Brickenstein, Stanislav Bulygin. In: First International Conference on Symbolic Computation and Cryptography, Beijing, China. P. 118123, April, 2008
Stanislav Bulygin, Ruud Pellikaan. In: Selected Topics in Information and Coding Theory. World Scientific, 2008
Maria BrasAmoros, Stanislav Bulygin. In: Discrete Mathematics. Submitted, 2008
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
Stanislav Bulygin, Ruud Pellikaan. In: Proceedings of the 28th Symposium on Information Theory in the Benelux, Enschede, The Netherlands. P. 310, May, 2007
Diego Ruano. In: Special Issue of JSC EACA'06. 2007
E. MartinezMoro, C. Munuera, Diego Ruano. Instituto Venezolano de Investigaciones Cientificas, 125 pages. ISBN: 9789802610877, 2007
Diego Ruano. In: Finite Fields and their Applications. Volume 13, Number 4, Elsevier, P. 962976, 2007
T. Rai, Stanislav Bulygin. In: Preprint. Available online: http://eprint.iacr.org/2008/514, 2007
Stanislav Bulygin. In: IEEE Transactions on Information Theory. 2006
A. Campillo, GertMartin Greuel, C. Lossen. In: Proceedings of MEGA 2003. 2006
r31  01 Dec 2008  StanislavBulygin 
