CGC Bulletin 5
CONTENTS
- Wreath Products in Stream Cipher Design
- On the Unsolvability of the Conjugacy Problem for Subgroups of the Group R_5
- Group Signature Schemes Using Braid Groups
- Diffie-Hellman Key Exchange Protocol and non-abelian nilpotent groups
- Topological Chaos in Spatially Periodic Mixers
- Topology, Braids, and Mixing in Fluids
- A substantial improvement on the decomposition problem in Thompson's group
Thanks to Mike Anshel for his contributions.
Boaz Tsaban
1. Wreath Products in Stream Cipher Design
Vladimir Anashin
The paper develops a novel approach to stream cipher design: Both the state update function and the output function of the corresponding pseudorandom generators are compositions of arithmetic and bitwise logical operations, which are standard instructions of modern microprocessors. Moreover, both the state update function and the output function are being modified dynamically during the encryption. Also, these compositions could be keyed, so the only information available to an attacker is that these functions belong to some exponentially large class.
The paper shows that under rather loose conditions the output sequence is uniformly distributed, achieves maximum period length and has high linear complexity and high $\ell$-error linear complexity. Ciphers of this kind are flexible: One could choose a suitable combination of instructions to obtain due performance without affecting the quality of the output sequence. Finally, some evidence is given that a key recovery problem for (reasonably designed) stream ciphers of this kind is intractable up to plausible conjectures.
http://arXiv.org/abs/cs/0602012
2. On the Unsolvability of the Conjugacy Problem for Subgroups of the Group R_5 of Pure Braids
V. N. Bezverkhnii and I. V. Dobrynina
Mathematical Notes 65 (1999)
(translation from Math Zametki Vol 65 No. 1 pp 15-22 January 1999).
3. Group Signature Schemes Using Braid Groups
Tony Thomas, Arbind Kumar Lal
Artin's braid groups have been recently suggested as a new source for public-key cryptography. In this paper we propose the first group signature schemes based on the conjugacy problem, decomposition problem and root problem in the braid groups which are believed to be hard problems.
http://arXiv.org/abs/cs/0602063
4. Diffie-Hellman Key Exchange Protocol and non-abelian nilpotent groups
Ayan Mahalanobis
We study a key exchange protocol similar to Diffie-Hellman key exchange protocol using abelian subgroups of the automorphism group of a non-abelian nilpotent group. We also generalize group no.92 of Hall-Senior table, for arbitrary prime p and show that for those groups, the group of central automorphisms commute. We use these for the key exchange we are studying.
http://arXiv.org/abs/math/0602282
5. Topological Chaos in Spatially Periodic Mixers
Matthew D. Finn, Jean-Luc Thiffeault, Emmanuelle Gouillart
Topologically chaotic fluid advection is examined in two-dimensional flows with either or both directions spatially periodic. Topological chaos is created by driving flow with moving stirrers whose trajectories are chosen to form various braids. In a nonperiodic domain, it is already known how to obtain topological entropy lower bounds for such flows using a train-track algorithm. However, for spatially periodic flows, in addition to the usual stirrer-exchange braiding motions, there are additional topologically- nontrivial motions corresponding to stirrers traversing the periodic directions. This leads to a study of the braid group on the cylinder and the torus. Methods for finding topological entropy lower bounds for such flows are examined. These bounds are then compared to numerical stirring simulations of Stokes flow to evaluate their sharpness. The sine flow is also examined from a topological perspective.
http://www.arxiv.org/abs/nlin.CD/0507023
6. Topology, Braids, and Mixing in Fluids
Jean-Luc Thiffeault, Matthew D. Finn
Stirring of fluid with moving rods is necessary in many practical applications to achieve homogeneity. These rods are topological obstacles that force stretching of fluid elements. The resulting stretching and folding is commonly observed as filaments and striations, and is a precursor to mixing. In a space-time diagram, the trajectories of the rods form a braid, and the properties of thi braid impose a minimal complexity in the flow. We review the topological viewpoint of fluid mixing, and discuss how braids can be used to diagnose mixing and construct efficient mixing devices. We introduce a new, realisable design for a mixing device, the silver mixer, based on these principles.
http://www.arxiv.org/abs/nlin.CD/0603003
7. A substantial improvement on the decomposition problem in Thompson's group
Boaz Tsaban
This is an intermediate report on our work with Dima Ruinsky and Adi Shamir initially reported in the last Bochum Workshop, see Section 1 of CGC Bulletin 1 and the link http://homepage.ruhr-uni-bochum.de/Arkadius.Kalka/workshop05/articles/researchannouncement.pdf All notation below is as in the link.
Following Shpilrain and Ushakov's observation in their paper The conjugacy search problem in public key cryptography: unnecessary and insufficient (to appear in: Applicable Algebra in Engineering, Communication and Computing), we have changed the search so that given awb with a in A, b in B, we look for any a' in A and b' in B such that a'wb' = awb. This is the so-called Decomposition Problem, and is sufficient for breaking the suggested PKC.
Using the method reported in the above link and some initial improvements like avoiding repetitions, the success probability in breaking the PKC suggested by Shpilrain and Ushakov grew from 0.7% to about 55% (!).
Since the PKC can be easily iterated, we are trying to improve the success rates further.
END OF ISSUE
