Copy Link

Add to Bookmark

Report

CGC Bulletin 9

eZine lover (@eZine)

Published in

CGC Bulletin

· 11 months ago

Dear Friends and Colleagues,

The GAGTA meeting in Manresa resulted in an expansion of the Bulletin's mailing list. I would like to welcome all new subscribers to the Bulletin's list.

Please continue sending us announcements and other information that should be of interest to readers of this bulletin.

Thanks to Mike Anshel, David Garber, and Enric Ventura for their contributions to this issue.

Regards,
Boaz Tsaban

Attacking a public key cryptosystem based on tree replacement
A Minimal Non-solvable Group of Homeomorphisms
Journal of Mathematical Cryptology (First issue)
The Braid-Based Bit Commitment Protocol
Abstracts for the GAGTA conference
CRM Advanced Course on Group-Based Cryptography
Using shifted conjugacy in braid-based cryptography
Braids: School and conference
A Quasigroup Based Cryptographic System

CGC Bulletin homepage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html

1. Attacking a public key cryptosystem based on tree replacement

Maria Isabel Gonzalez Vasco and David Perez Garcia

We point out several security flaws in the cryptosystem based on tree replacement systems proposed by Samuel, Thomas, Abisha and Subramanian at INDOCRYPT 2002. Due to the success of (among others) very simple ciphertext-only attacks, we evidence that this system does not, in its present form, offer acceptable security guarantees for cryptographic applications.

Discrete Applied Mathematics, in press.

http://dx.doi.org/10.1016/j.dam.2006.05.009

2. A Minimal Non-solvable Group of Homeomorphisms

Collin Bleak

Let PL_0(I) represent the group of orientation-preserving piecewise-linear homeomorphisms of the unit interval which admit finitely many breaks in slope, under the operation of composition. We find a non-solvable group W and show that W embeds in every non-solvable subgroup of PL_0(I) . We find mild conditions under which other non-solvable subgroups ( B , (\wr\Z\wr)^{\infty} , (\Z\wr)^{\infty} , and ^{\infty}(\wr\Z) ) embed in subgroups of PL_0(I) . We show that all solvable subgroups of PL_0(I) embed in all non-solvable subgroups of PL_0(I). These results continue to apply if we replace PL_0(I) by any generalized R . Thompson group F_n .

http://arXiv.org/abs/math/0608182

3. Journal of Mathematical Cryptology (First issue)

Tomohiro Harayama and Donald K. Friesen: Weil Sum for Birthday Attack in Multivariate Quadratic Cryptosystem

Tanja Lange and Igor E. Shparlinski: Distribution of Some Sequences of Points on Elliptic Curves

Yuan Li and T. W. Cusick: Strict Avalanche Criterion Over Finite Fields

Keith Martin and Siaw-Lynn Ng: The Combinatorics of Generalized Cumulative Arrays

Alfred Menezes: Another Look at HMQV

D. R. Stinson and R. Wei: Some Results on Query Processes and Reconstruction Functions for Unconditionally Secure 2-server 1-round Binary Private Information Retrieval Protocols

Instructions for manuscript submission and subscription information can be found at http://www.degruyter.de/rs/278_8316_ENU_h.htm .

The Managing Editors

4. The Braid-Based Bit Commitment Protocol

WANG Li-cheng, CAO Zhen-fu, CAO Feng, and QIAN Hai-feng

With recent advances of quantum computation, new threats have closed in upon to the classical public key cryptosystems. In order to build more secure bit commitment schemes, this paper gave a survey of the new coming braid-based cryptography and then brought forward the first braid-based bit commitment protocol. The security proof manifests that the proposed protocol is computationally binding and information-theoretically hiding.Furthermore, the proposed protocol is also invulnerable to currently known quantum attacks. JOURNAL OF SHANGHAI JIAOTONG UNIVERSITY 2006 Vol.11 No.2 P.200-204

http://www.wanfangdata.com.cn/qikan/periodical.articles/shjtdxxb-e/shjt2006/0602/060215.htm

5. Abstracts for the GAGTA conference

The abstracts for the GAGTA (Geometric and Asymptotic Group Theory Conference with Applications) Conference are available at http://www.cs.biu.ac.il/~tsaban/CGC/Issues/GAGATA.pdf

Thanks to Enric Ventura and the other organizers for making them available to the benefit of our community.

6. CRM Advanced Course on Group-Based Cryptography

Centre de Recerca Matematica, 28 May to 2 June, 2007.

Speakers: Vladimir Shpilrain (The City College of New York), Alexei Miasnikov (McGill University).

Deadline for Registration: April 27, 2007.

Abstracts:

A. Vladimir Shpilrain: Noncommutative Cryptography

This is an interdisciplinary mini-course focused on cryptography, which is usually considered an area of computer science. However, there are areas of cryptography (most notably, public-key cryptography), where several different areas of mathematics find their important applications. Until recently, mathematics used in cryptography was "commutative", which means cryptographic primitives were based on commutative rings or commutative (finite) groups. This includes RSA, the most common public key cryptosystem in use today. It is employed, for instance, in the Netscape and Internet Explorer browsers.

Although the security of the internet does not appear to be threatened at this time because of the weaknesses of the existing protocols such as RSA, it seems prudent to explore possible enhancements and replacements of such protocols which depend on finite commutative groups. This is the basic objective of the present mini-course. Non-commutative groups were introduced into public-key cryptography by Wagner and Magyarik more than 20 years ago, but only relatively recently did this direction get serious attention of professional cryptographers worldwide, due to seminal work of Anshel and Goldfeld (1999). Since then, a very active research in non-commutative cryptography is going on, and we are going to describe these new promising research avenues, most of which employ classical as well as modern combinatorial group theory, with a focus on algorithmic problems and their complexity.

B. Alexei Miasnikov: Complexities of Algorithms.

In this course I am going to discuss some recent developments in asymptotic and computational algebra, and their applications to modern cryptanalysis. I begin with "Generic complexity of algorithms" describing the complexity of algorithms on "most" or "generic" inputs. This type of complexity differs from the well-known worst-case and average-case complexities. I will argue that the generic-case complexity is precisely the type of complexity required in cryptanalysis of modern cryptoschemes.

We shall continue with "Random van Kampen diagrams and algorithmic problems in groups". I am going to present some new "generically fast" algorithms for solving the word, conjugacy, and mebership problems in groups. The algorithms are based on some recent results on generic properties of van Kampen diagrams. For example, I will show that generic van Kampen diagrams of finitely presented groups are "hyperbolic". This sheds some light on security of cryptosystems based on the word and conjugacy problems.

Finally, we will study "Asymptotically dominant properties and subgroup attacks" focusing on asymptotic properties of subgroups of infinite groups.

It turns out "generic subgroups" quite often have very specific properties that provide a basis for various subgroup attacks. I will discuss on how one could avoid the attacks choosing the subgroups carefully.

For more details and registration: http://www.crm.es/ (under conferences and courses).

Enric Ventura

7. Using shifted conjugacy in braid-based cryptography

Patrick Dehornoy (LMNO)

Conjugacy is not the only possible primitive for designing braid-based protocols. To illustrate this principle, we describe a Fiat--Shamir-style authentication protocol that be can be implemented using any binary operation that satisfies the left self-distributive law. Conjugation is an example of such an operation, but there are other examples, in particular the shifted conjugation on Artin's braid group B_infinity, and the finite Laver tables. In both cases, the underlying structures have a high combinatorial complexity, and they lead to difficult problems.

http://arXiv.org/abs/cs/0609091

8. Braids: School and conference

14 May - 13 Jul 2007

Organizing Committee

Co-chairs

Jon Berrick (National University of Singapore)
Fred R. Cohen (University of Rochester)

Members

Mitch Berger (University College London)
Joan S. Birman (Columbia University)
Toshitake Kohno (University of Tokyo)
Yan-Loi Wong (National University of Singapore)
Jie Wu (National University of Singapore)

The main theme of the program is the mathematical structure of the braid group, together with applications arising from this structure both within mathematics, and outside of mathematics such as (a) magnetohydrodynamics, (b) robotics and (c) stereochemistry.

It is proposed to invite workers in these different areas with the intention of cross-fertilization.

The interests of the organizers lie mostly in topology. Therefore it is likely that most long-term visitors will be from that area. Reflecting the theme of the program, it is intended to have tutorials that would:

introduce outsiders (e.g. graduate students) to the mathematics of braid theory facilitate communication between those working in mathematical theory of braids and those who apply braids elsewhere, specifically in magnetohydrodynamics, robotics and stereochemistry.

A quote from the introduction:

"To date, most mathematical interest in braids has come from algebraists, topologists and mathematical physicists. As well, braids are also engaging the attention of computer scientists, as a basis for public-key cryptosystems. Probabilistic algorithms are being employed to search for solutions to word problems in the braid group. Relevance to robotics, stereochemistry and to magnetohydrodynamics is also to be explored during the program."

Activities

Tutorials:

Week 1 (4 - 8 Jun 2007)

(a) Braids - definitions and braid groups, by Joan Birman: 4 hours
(b) Simplicial objects, homotopy groups, by Jie Wu: Part 1; 2 hours

Week 2 (11 - 15 Jun 2007)

(a) Simplicial objects homotopy groups by Jie Wu: Part 2; 2 hours
(b) Stereochemistry, by Kurt Mislow: 2 hours
(c) Configuration spaces, by Fred Cohen: 2 hours

Week 3 (18 - 22 Jun 2007)

(a) Magnetohydrodynamics, by Mitch Berger: 4 hours
(b) Configuration spaces and robotics, by Robert Ghrist: 2 hours

Conference: 25 - 29 Jun 2007

Confirmed Principal Speakers

M Berger (London)
J Birman (Columbia)
T Brendle (Cornell)
R Budney (MPIM Bonn)
F Cohen (Rochester)
R Ghrist (UIUC)
J Gonzalez-Meneses (Seville)
T Kohno (Tokyo)
D Margalit (Utah)
S Morita (Tokyo)
L Paris (Bourgogne)
N Wahl (Chicago)
B Wajnryb (Technion Israel IT)
B Wiest (Rennes)

Public Lecture:
Braids and robotics by Robert Ghrist (University of Illinois, Urbana-Champaign).

http://www.ims.nus.edu.sg/Programs/braids/index.htm

9. A Quasigroup Based Cryptographic System

Maruti Satti

This paper presents a quasigroup encryptor that has very good scrambling properties. We show that the output of the encryptor maximizes the output entropy and the encrypted output for constant and random inputs is very similar. The system architecture of the quasigroup encryptor and the autocorrelation properties of the output sequences are provided.

http://arXiv.org/abs/cs/0610017

---

END OF ISSUE