CGC Bulletin 11
CONTENTS
- Non-Archimedean analysis, T-functions, and cryptography
- Conjugacy in Garside groups II: Structure of the ultra summit set
- Conjugacy in Garside Groups III: Periodic braids
- Computational explorations in Thompsons group F
- Interpreting the arithmetic in Thompson's group F
- The Design, Analysis and Optimization of the REESSE1+ Public-key Cryptosystem
Bulletin's website: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
Boaz Tsaban
1. Non-Archimedean analysis, T-functions, and cryptography
Vladimir Anashin
These are lecture notes of a 20-hour course at the International Summer School \emph{Mathematical Methods and Technologies in Computer Security} at Lomonosov Moscow State University, July 9--23, 2006.
Loosely speaking, a $T$-function is a map of $n$-bit words into $n$-bit words such that each $i$-th bit of image depends only on low-order bits $0,..., i$ of the pre-image. For example, all arithmetic operations (addition, multiplication) are $T$-functions, all bitwise logical operations ($\XOR$, $\AND$, etc.) are $T$-functions. Any composition of $T$-functions is a $T$-function as well. Thus $T$-functions are natural computer word-oriented functions.
It turns out that $T$-functions are continuous (and often differentiable!) functions with respect to the so-called 2-adic distance. This observation gives a powerful tool to apply 2-adic analysis to construct wide classes of $T$-functions with provable cryptographic properties (long period, balance, uniform distribution, high linear complexity, etc.); these functions currently are being used in new generation of fast stream ciphers. We consider these ciphers as specific automata that could be associated to dynamical systems on the space of 2-adic integers. From this view the lectures could be considered as a course in cryptographic applications of the non-Archimedean dynamics; the latter has recently attracted significant attention in connection with applications to physics, biology and cognitive sciences.
During the course listeners study non-Archimedean machinery and its applications to stream cipher design.
http://arXiv.org/abs/cs/0612038
2. Conjugacy in Garside groups II: Structure of the ultra summit set
Joan S. Birman, Volker Gebhardt, Juan Gonzalez-Meneses
This paper is the second in a series in which the authors study the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in Garside groups. The ultra summit set USS(X) of an element X in a Garside group G is a finite set of elements in G, introduced by the second author, which is a complete invariant of the conjugacy class of X in G. A fundamental question, if one wishes to find bounds on the size of USS(X), is to understand its structure. In this paper we introduce two new operations on elements of USS(X), called `partial cycling' and `partial twisted decycling', and prove that if Y and Z belong to USS(X), then Y and Z are related by sequences of partial cyclings and partial twisted decyclings. These operations are a concrete way to understand the minimal simple elements which result from the convexity theorem in the mentioned paper by the second author. Using partial cycling and partial twisted decycling, we investigate the structure of a directed graph \Gamma_X which is determined by USS(X), and show that \Gamma_X can be decomposed into `black' and `grey' subgraphs. There are applications which relate to the program, outlined in the first paper in this series, for finding a polynomial solution to the CDP/CSP in the case of braids. A different application is to give a new algorithm for solving the CDP/CSP in Garside groups which is faster than all other known algorithms, even though its theoretical complexity is the same as that given by the second author. There are also applications to the theory of reductive groups.
http://arxiv.org/abs/math.GT/0606652
3. Conjugacy in Garside Groups III: Periodic braids
Joan S. Birman, Volker Gebhardt, Juan Gonzalez-Meneses
An element in Artin's braid group B_n is said to be periodic if some power of it lies in the center of B_n. In this paper we prove that all previously known algorithms for solving the conjugacy search problem in B_n are exponential in the braid index n for the special case of periodic braids. We overcome this difficulty by putting to work several known isomorphisms between Garside structures in the braid group B_n and other Garside groups. This allows us to obtain a polynomial solution to the original problem (for periodic braids) in the spirit of the previously known algorithms. This paper is the third in a series of papers by the same authors about the conjugacy problem in Garside groups. They have a unified goal: the development of a polynomial algorithm for the conjugacy decision and search problems in B_n, which generalizes to other Garside groups whenever possible. It is our hope that the methods introduced here will allow the generalization of the results in this paper to all Artin-Tits groups of spherical type.
http://arxiv.org/abs/math.GT/0609616
4. Computational explorations in Thompson's group F
Jose Burillo, Sean Cleary, and Bert Wiest
Here we describe the results of some computational explorations in Thompson's group F. We describe experiments to estimate the co-growth of F with respect to its standard finite generating set, designed to address the subtle and difficult question whether or not Thompson's group is amenable. We also describe experiments to estimate the exponential growth rate of F and the rate of escape of symmetric random walks with respect to the standard generating set.
http://perso.univ-rennes1.fr/bertold.wiest/fexplore3.pdf
5. Interpreting the arithmetic in Thompson's group F
Vladimir Tolstykh and Valery Bardakov
We prove that the elementary theory of Thompson's group $F$ is hereditarily undecidable.
http://arXiv.org/abs/math/0701748
6. The Design, Analysis and Optimization of the REESSE1+ Public-key Cryptosystem
Shenghui Su, and Shuwang Lv
This paper gives the definition of a coprime sequence and the concept of the lever function, describes the five algorithms and six characteristics of the REESSE1+ public-key cryptosystem based on three new hardnesses: the modular subset product problem, the multivariate arrangement problem, and the super logarithm problem in a prime field, shows the correctness of the decryption algorithm, and infers that the probability that a plaintext solution is not unique is nearly zeroth. The authors discuss a necessity for the lever function to prevent a continued fraction attack and an indeterministic reasoning, analyze the security of REESSE1+ against recovering a plaintext from a ciphertext, extracting a private key from a public key or a signature as well as faking a digital signature via a public key or a known signature with a public key, and believe that the security of REESSE1+ is at least equal to the time complexity of O(2^n) at present. The paper expounds the idea of optimizing REESSE1+ through binary compact sequences, elaborates the five optimized algorithms, compares REESSE1+ with RSA and ECC bearing equivalent security in lengths and speeds.
http://arXiv.org/abs/cs/0702046
Editor's addition: Soon after posting this issue, Michal Sramka has informed us that this PK system is cryptanalyzed in Shengli Liu and Fangguo Zhang, "Cryptanalysis of REESSE1+ Public Key Cryptosystem", http://eprint.iacr.org/2006/480 According to their abstract, they "show that the system is totally insecure. We show how to derive the private key from the public key. As the same time, we also show how to forge signatures for any messages, given two valid signatures."
END OF ISSUE
