CGC Bulletin 8
The current issue is mostly dedicated to the cryptanalysis of the Shpilrain-Ushakov public-key cryptosystem based on Thompson's group. See items 4 and 5 below. 6, 7, 8 are related to 5.
The CGC Bulletin now has a homepage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
issues will be loaded to it only after a reasonable delay allowing corrections according to feedback I get from those subscribed to its mailing list.
CONTENTS
- Imprimitive permutations groups generated by the round functions of key-alternating block ciphers and truncated differential cryptanalsys
- A simple generalization of El-Gamal cryptosystem to non-abelian groups
- Hard Instances of the Constrained Discrete Logarithm Problem
- Length-based cryptanalysis: The case of Thompson's Group
- The Shpilrain-Ushakov Protocol for Thompson's Group F is always breakable
- The Simultaneous Conjugacy Problem in Thompson's Group F
- Forest diagrams for elements of Thompson's group F
- Thompson's Group F is not Minimally Almost Convex
Best regards,
Boaz Tsaban
1. Imprimitive permutations groups generated by the round functions of key-alternating block ciphers and truncated differential cryptanalsys
A. Caranti, F. Dalla Volta, M. Sala, F. Villani
We answer a question of Paterson, showing that all block systems for the group generated by the round functions of a key-alternating block cipher are the translates of a linear subspace. Following up remarks of Paterson and Shamir, we exhibit a connection to truncated differential cryptanalysis.
We also give a condition that guarantees that the group generated by the round functions of a key-alternating block cipher is primitive. This applies in particular to AES.
http://arXiv.org/abs/math/0606022
2. A simple generalization of El-Gamal cryptosystem to non-abelian groups
Ayan Mahalanobis
In this paper we propose the group of unitriangular matrices over a finite field as a non-abelian group and composition of inner, diagonal and central automorphism as a group of automorphisms for the MOR cryptosystem.
http://arXiv.org/abs/cs/0607011
3. Hard Instances of the Constrained Discrete Logarithm Problem
Ilya Mironov, Anton Mityagin, Kobbi Nissim
The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the constrained DLP depends on the choice of the set. Motivated by cryptographic applications, we study explicit construction of sets for which the constrained DLP is hard. We draw on earlier results due to Erd'os et al. and Schnorr, develop geometric tools such as generalized Menelaus' theorem for proving lower bounds on the complexity of the constrained DLP, and construct explicit sets with provable non-trivial lower bounds.
http://arXiv.org/abs/math/0606771
4. Length-based cryptanalysis: The case of Thompson's Group
Dima Ruinskiy, Adi Shamir, and Boaz Tsaban
The length-based approach is a heuristic for solving randomly generated equations in groups which possess a reasonably behaved length function. We describe several improvements of the previously suggested length-based algorithms, that make them applicable to Thompson's group with significant success rates. In particular, this shows that the Shpilrain-Ushakov public key cryptosystem based on Thompson's group is insecure, and suggests that no practical public key cryptosystem based on this group can be secure.
http://arXiv.org/abs/cs/0607079
5. The Shpilrain-Ushakov Protocol for Thompson's Group F is always breakable
Francesco Matucci
This paper shows that an eavesdropper can always recover precisely the private key of one of the two parts of the public key cryptography protocol introduced by Shpilrain and Ushakov in \cite{su}. Thus an eavesdropper can always recover the shared secret key making the protocol insecure.
http://arxiv.org/abs/math.GR/0607184
6. The Simultaneous Conjugacy Problem in Thompson's Group F
Martin Kassabov, Francesco Matucci
Guba and Sapir asked, in their joint paper, if the simultaneous conjugacy problem was solvable in Diagram Groups or, at least, for Thompson's group F. We give an elementary proof for the solution of the latter question. This relies purely on the description of F as the group of piecewise linear orientation-preserving homeomorphisms of the unit interval with dyadic breakpoints and slopes that are powers of 2. We show that, with the techniques we develop, we can solve the ordinary conjugacy problem as well, and we can compute roots and centralizers. Moreover, these techniques can be generalized to solve the same questions in larger groups of piecewise-linear homeomorphisms.
http://arxiv.org/abs/math.GR/0607167
7. Forest diagrams for elements of Thompson's group F
James Belk, Kenneth Brown
We introduce forest diagrams to represent elements of Thompson's group F. These diagrams relate to a certain action of F on the real line in the same way that tree diagrams relate to the standard action of F on the unit interval. Using forest diagrams, we give a conceptually simple length formula for elements of F with respect to the {x_0,x_1} generating set, and we discuss the construction of minimum-length words for positive elements. Finally, we use forest diagrams and the length formula to examine the structure of the Cayley graph of F.
http://arxiv.org/abs/math.GR/0305412
8. Thompson's Group F is not Minimally Almost Convex
James Belk, Kai-Uwe Bux
We prove that Richard Thompson's group F is not minimally almost convex with respect to the two standard generators. This improves upon a recent result of S. Cleary and J. Taback. We make use of the forest diagrams for elements of F introduced by J. Belk and K. Brown. These diagrams seem particularly well-suited for understanding the Cayley graph for the two standard generators.
