Copy Link
Add to Bookmark
Report

CGC Bulletin 8

eZine's profile picture
Published in 
CGC Bulletin
 · 1 year ago

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

  1. Imprimitive permutations groups generated by the round functions of key-alternating block ciphers and truncated differential cryptanalsys
  2. A simple generalization of El-Gamal cryptosystem to non-abelian groups
  3. Hard Instances of the Constrained Discrete Logarithm Problem
  4. Length-based cryptanalysis: The case of Thompson's Group
  5. The Shpilrain-Ushakov Protocol for Thompson's Group F is always breakable
  6. The Simultaneous Conjugacy Problem in Thompson's Group F
  7. Forest diagrams for elements of Thompson's group F
  8. 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.

http://arxiv.org/abs/math.GR/0301141

← previous
next →
loading
sending ...
New to Neperos ? Sign Up for free
download Neperos App from Google Play
install Neperos as PWA

Let's discover also

Recent Articles

Recent Comments

Neperos cookies
This website uses cookies to store your preferences and improve the service. Cookies authorization will allow me and / or my partners to process personal data such as browsing behaviour.

By pressing OK you agree to the Terms of Service and acknowledge the Privacy Policy

By pressing REJECT you will be able to continue to use Neperos (like read articles or write comments) but some important cookies will not be set. This may affect certain features and functions of the platform.
OK
REJECT