CGC Bulletin 14
CONTENTS
- Non-commutative generalization of ElGamal using polycyclic group
- On the cycling operation in braid groups
- Towards Generating Secure Keys for Braid Cryptography
- Cryptanalysis of group-based key agreement protocols using subgroup distance functions
- Tutorial lecture notes on braid groups and cryptography
- General cycling operations in Garside groups
- Random subgroups and analysis of the length-based and quotient attacks
Thanks to Mike Anshel and David Garber, and Adi Shamir, for their contributions to this issue.
Enjoy,
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. Non-commutative generalization of ElGamal using polycyclic group
Delaram Kahrobaei and Bilal Khan, Proceeding of IEEE (Nov. 2006)
In this paper, we propose a non-commutative key-exchange scheme which generalizes the classical ElGamal Cipher to polycyclic groups. We will explore other classes of groups which would provide good candidates for these cryptosystems, we also examine the complexity of the decision problems related to these key exchange.
Delaram Kahrobaei
2. On the cycling operation in braid groups
Juan Gonzalez-Meneses, Volker Gebhardt
The cycling operation is a special kind of conjugation that can be applied to elements in Artin's braid groups, in order to reduce their length. It is a key ingredient of the usual solutions to the conjugacy problem in braid groups. In their seminal paper on braid-cryptography, Ko, Lee et al. proposed the _cycling problem_ as a hard problem in braid groups that could be interesting for cryptography. In this paper we give a polynomial solution to that problem, mainly by showing that cycling is surjective, and using a result by Maffre which shows that pre-images under cycling can be computed fast. This result also holds in every Artin-Tits group of spherical type. On the other hand, the conjugacy search problem in braid groups is usually solved by computing some finite sets called (left) ultra summit sets (left-USS), using left normal forms of braids. But one can equally use right normal forms and compute right-USS's. Hard instances of the conjugacy search problem correspond to elements having big (left and right) USS's. One may think that even if some element has a big left-USS, it could possibly have a small right-USS. We show that this is not the case in the important particular case of rigid braids. More precisely, we show that the left-USS and the right-USS of a given rigid braid determine isomorphic graphs, with the arrows reversed, the isomorphism being defined using iterated cycling. We conjecture that the same is true for every element, not necessarily rigid, in braid groups and Artin-Tits groups of spherical type.
http://arxiv.org/abs/0704.2600
3. Towards Generating Secure Keys for Braid Cryptography
Ki Hyoung Ko and Jang Won Lee and Tony Thomas
Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this paper, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.
http://eprint.iacr.org/2007/149
4. Cryptanalysis of group-based key agreement protocols using subgroup distance functions
Dima Ruinskiy, Adi Shamir, and Boaz Tsaban
We introduce a new approach for cryptanalysis of key agreement protocols based on noncommutative groups. This approach uses functions that estimate the distance of a group element to a given subgroup. We test it against the Shpilrain-Ushakov protocol, which is based on Thompson's group F.
Comments: This is an initial estimation of a new idea. The fact that the tested system can be cryptanalyzed is not new.
http://arxiv.org/abs/0705.2862
5. Tutorial lecture notes on braid group cryptography
A preliminary version of David Garber's lecture notes on the topic, given in the workshop on Braids (Singapore, 14 May--13 Jul 2007), is available at http://www.ims.nus.edu.sg/Programs/braids/files/david.pdf
A final version should be available at the arXiv by the end of September 2007.
Many more papers and presentations given at the conference are available at http://www.ims.nus.edu.sg/Programs/braids/activities_gen.htm
(as PDF links). Additional files are continuing to be uploaded there.
6. General cycling operations in Garside groups
Hao Zheng
In this article, we introduce the notion of cycling operations of arbitrary order in Garside groups, which is a full generalization of the cycling and decycling operations. Theoretically, this notion together with other related concepts provides a context in which various definitions and arguments concerning Garside groups are unified and simplified as well as improved. Practically, it yields a new algorithm which has a considerably improved performance on solving the conjugacy problem of reducible braids.
http://arxiv.org/abs/math/0605741
7. Random subgroups and analysis of the length-based and quotient attacks
Alexei G. Myasnikov, Alexander Ushakov
In this paper we discuss generic properties of "random subgroups" of a given group G. It turns out that in many groups G (even in most exotic of them) the random subgroups have a simple algebraic structure and they "sit" inside G in a very particular way. This gives a strong mathematical foundation for cryptanalysis of several group-based cryptosystems and indicates on how to chose "strong keys". To illustrate our technique we analyze the Anshel-Anshel-Goldfeld (AAG) cryptosystem and give a mathematical explanation of recent success of some heuristic length-based attacks on it. Furthermore, we design and analyze a new type of attacks, which we term the quotient attacks. Mathematical methods we develop here also indicate how one can try to choose "parameters" in AAG to foil the attacks.
http://arxiv.org/abs/0707.1501
8. Computer aided discovery of a fast algorithm for testing conjugacy in braid groups
Volker Gebhardt
This chapter describes how Magma was used to investigate and understand a phenomenon observed when implementing a conjugacy test for elements of a braid group. These investigations ultimately lead to the discovery of a new invariant of conjugacy classes in braid groups, to an efficient way of computing this invariant, and in particular to a much more powerful conjugacy test than the one which was originally to be implemented.
While at the end of this journey stood a purely theoretical result whose proof does not involve any computations, using Magma proved crucial both for recognising the new class invariant and its important properties and for getting ideas as to how to prove these results.
http://www.springerlink.com/content/w13v53405535140k/fulltext.pdf
---
END OF ISSUE
