CGC Bulletin 3
CONTENTS
- Slides for the Bochum Workshop talks
- A useful information resource for CGC
- A new key exchange protocol based on the decomposition problem
- A Practical Attack on the Root Problem in Braid Groups
- Recent doctoral dissertations in the field
1. Slides for the Bochum Workshop talks
The slides of most of that talks in the Bochum Workshop "Algebraic methods in cryptography" are now available at the workshop's web-page:
http://www.ruhr-uni-bochum.de/ffm/Lehrstuehle/Lehrstuhl-VI/Workshop05.htm
2. A useful information resource for CGC
We maintain here in New York a useful information resource, called Virtual Algebra Center:
Vladimir Shpilrain
3. A new key exchange protocol based on the decomposition problem
In this paper we present a new key establishment protocol based on the decomposition problem in non-commutative groups which is: given two elements w, w_1 of the platform group G and two subgroups A, B \subseteq G (not necessarily distinct), find elements a in A, b in B such that w_1 = a w b$. Here we introduce two new ideas that improve the security of key establishment protocols based on the decomposition problem. In particular, we conceal (i.e., do not publish explicitly) one of the subgroups A, B, thus introducing an additional computationally hard problem for the adversary, namely, finding the centralizer of a given finitely generated subgroup.
http://arXiv.org/abs/math/0512140
Vladimir Shpilrain and Alexander Ushakov
4. A Practical Attack on the Root Problem in Braid Groups
Cryptology ePrint Archive: Report 2005/459 http://eprint.iacr.org/2005/459
Anja Groch, Dennis Hofheinz, and Rainer Steinwandt
Using a simple heuristic approach to the root problem in braid groups, we show that cryptographic parameters proposed in this context must be considered as insecure. In our experiments we can, often within seconds, extract the secret key of an authentication system based on the root problem in braid groups.
5. Recent doctoral dissertations in the field
Xiaowei Xu, Cryptographic Systems Using Linear Groups
Abstract:
The objective of my thesis is to propose and discuss some new public-key encoding and zero-knowledge protocols based on matrix groups over polynomial rings. One of the key aspects of these protocols is the use of a rewriting system, known as the method of Reidemeister and Schreier, which is common in group theory but not used until now in cryptography. In this talk, we will explore how to use groups of matrices over polynomial rings in cryptography. This will involve solving various group-theoretic problems and the difficulty of solving various polynomial equations. This will allow us to propose various new public-key encoding and zero-knowledge protocols.
Instead of using protocols based on number theory, we will devise protocols based on groups of matrices, whose entries consist of polynomials in a number of variables. The groups involved will be free groups and we use the free generators as letters in an alphabet which permit the encoding of messages in terms of matrices. We then transform these matrices into 2X2 integral matrices of determinant 1. The Euclidean algorithm and the method of Reidemeister-Schreier alluded to above, and then enable us to decode the given messages.
We describe two cryptography schemes based on combinatorial group theory. We will discuss the underlying theory and provide some explicit examples. We suggest that combinatorial group theory could be the next generation platform in the development of cryptography because it is more general and more flexible to take advantage of dynamic algebraic structures instead of static arithmetic. Our various schemes are based on more than one secret element and break one doesn't break the whole scheme. We have developed some polynomial matrix software and utilize the software to investigate our protocols.
Related Publications:
- G. Baumslag, B. Fine and X.Xu, A Proposed Public Key Cryptosystem, to appear.
- G. Baumslag, B. Fine and X.Xu, Linear Group Cryptosystems, Proceedings of Algebraic Cryptography 2005.
- S. Shankar, S. Asa, V. Sipos and X. Xu, Reasoning about RealTime State charts in the Presence of Semantic Variations, ACM International Conference on Automated Software Engineering 2005.
- X. Xu, S. D. Dexter and A. M. Eskicioglu, A hybrid scheme for encryption and watermarking, Security, Steganography, and Watermarking of Multimedia Contents 2004, 725-736.
- S. Shankar and V. Sipos and X. Xu, Model Checking Concurrent Real-Time State charts, First Conference on the Principles of Software Engineering 2004.
- S. Shankar and X. Xu, Automating Object-Oriented Software Refactoring, Software Engineering Research and Practice 2003, 561-567.
http://web.gc.cuny.edu/Computerscience/EXAMS/DISSERTATIONS/2005-12-19XXui.htm
Michael Anshel
Dmitry Bormotov, Algorithms for Solving Hard Problems in Group Theory
Abstract:
In this thesis we developed some methods of a new emerging area of mathematics, which we call experimental algebra. We designed new algorithms, both deterministic and heuristic, aimed at hard problems in algebra. Using these algorithms we solved some open problems in groups and semigroups. These algorithms are implemented and organized in a package. In addition to implementations of stand-alone algorithms for solving particular problems, the package contains a variety of reusable components - tools that can be used to modify the behavior of existing algorithms, to form alternative strategies and to build new algorithms out of provided components.
The results of the package include:
- genetic algorithms for solving equations in free groups and free semigroups;
- effective deterministic algorithm for finding all solutions of one-variable equations in free groups;
- solving the Genus problem;
- classifying primitive elements in a free group;
- evaluating and attacking Dehornoy forms;
- key hiding system based on braid groups.
Related Publications:
- "Experimenting with Primitive Elements in F_2," Contemporary Mathematics, Volume 349, 2004.
- "Genetic algorithms and Equations in Free Groups and Semigroups" (with Richard F. Booth and Alexandre V. Borovik), Contemporary Mathematics, Volume 349, 2004.
- "Effective algorithm for finding all solutions of one-variable equations in free groups" (with Robert H. Gilman and Alexei G. Myasnikov), submitted.
http://web.gc.cuny.edu/Computerscience/EXAMS/DISSERTATIONS/DD-5-6-05_Bormotov.html
Michael Anshel
