CGC Bulletin 15

eZine lover (@eZine)

Published in

CGC Bulletin

· 1 year ago

New public key cryptosystems using polynomials over non-commutative rings
Cryptanalysis of shifted conjugacy authentication protocol
Key Agreement and Authentication Schemes Using Non-Commutative Semigroups
On the Security of the Cha-Ko-Lee-Han-Cheon Braid Group Public Key Cryptosystem
NEC Workshop on Quantum Computing
Proceedings of the conference on Geometric and Combinatorial Group Theory with Applications

Thanks to Arkadius Kalka for his contribution to this issue.

Enjoy,

Boaz Tsaban

Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html

1. New public key cryptosystems using polynomials over non-commutative rings

Zhenfu Cao, Xiaolei Dong, and Licheng Wang

In this paper, we propose a new method for designing public key cryptosystems based on general non-commutative rings. The key idea of our proposal is that for a given non-commutative ring, we can define polynomials and take them as the underlying work structure. By doing so, it is easy to implement Diffie-Helman-like key exchange protocol. And consequently, ElGamal-like cryptosystems can be derived immediately. Moreover, we show how to extend our method to non-commutative groups (or semi-groups).

http://eprint.iacr.org/2007/009.pdf

2. Cryptanalysis of shifted conjugacy authentication protocol

Jonathan Longrigg and Alexander Ushakov

In this paper we present the first practical attack on the shifted conjugacy-based authentication protocol proposed by P. Dehornoy. We discuss the weaknesses of that primitive and propose ways to improve the protocol.

http://arxiv.org/abs/0708.1768

3. Key Agreement and Authentication Schemes Using Non-Commutative Semigroups

M. M. Chowdhury

We give a new two-pass authentication scheme, whichis a generalisation of an authentication scheme of Sibert-Dehornoy-Girault based on the Diffie-Hellman conjugacy problem. Compared to the above scheme, for some parameters it is more efficient with respect to multiplications. We sketch a proof that our authentication scheme is secure. We give a new key agreement protocols.

http://arxiv.org/abs/0708.2395

4. On the AAGL Protocol

M. M. Chowdhury

Recently theAAGL(Anshel-Anshel-Goldfeld-Lemieux) hasbeenproposed which canbe usedforRFIDtags. We give algorithms for the problem (we call the MSCSPv) on which the security of theAAGL protocol is based upon. Hence we give various attacks for general parameters on the recent AAGLprotocol proposed. One ofour attacks is a deterministic algorithm which has space complexity and time complexityboth atleast exponentialin the worst case. In abetter case using a probabilistic algorithm the time complexity canbe O(|XSS(ui')^L5*(n^(1+e)) and the space complexity can be O(|XSS(ui')|^L6), where the element ui' is part of a public key, n is the index of braid group, XSS is a summit type set and e is a constant in a limit. The above shows the AAGL protocol is potentially not significantly more secure as using key agreement protocols based on the conjugacy problem such as the AAG (Anshel-Anshel-Goldfeld) protocol because both protocols can be broken with complexity which do not significantly differ. We think our attacks can be improved.

http://arxiv.org/abs/0708.2397

4. On the Security of the Cha-Ko-Lee-Han-Cheon Braid Group Public Key Cryptosystem

M. M. Chowdhury

We show that a number of cryptographic protocols using non-commutative semigroups including the Cha-Ko-Lee-Han-Cheon braid group public-key cryptosystem are based on the MSCSP.

http://arxiv.org/abs/0708.2571

5. NEC Workshop on Quantum Computing

September 20 - 21, 2007
NEC Laboratories America, Inc., Princeton, NJ

Organizers:

Seth Lloyd, MIT
Martin Roetteler, NEC Princeton
Jun'ichi Sone, NEC Japan
Jaw-Shen Tsai, NEC Japan

This is a quantum computing workshop in search of new crossroads between experiment and computer science. For more information about the workshop see http://www.nec.co.jp/rd/Eng/QCworkshop/index.html

Invited speakers:

Boris Altshuler (NEC Princeton)      Seth Lloyd (MIT) 
Takao Aoki (Caltech)                 Keiji Matsumoto (NII) 
Yasuhiko Arakawa (U. Tokyo)          Chris Monroe (Michigan) 
David Cory (MIT)                     Yasunobu Nakamura (NEC Tsukuba) 
Lov Grover (Bell Labs)               Jason Petta (Princeton) 
Sean Hallgren (Penn State)           Robert Spalek (Berkeley) 
Andrew Houck (Yale)                  Mario Szegedy (Rutgers) 
Lev Ioffe (Rutgers)                  Seigo Tarucha (U. Tokyo) 
Thaddeus Ladd (Stanford)             Umesh Vazirani (Berkeley)

Scope: The workshop is a two days event focusing on the quantum computing. Steady progress toward realizing the quantum computing has been made not only in the theory and algorithm, but also in the experimental techniques to actually implement the computation. Scientists in this field should be able to keep up with the latest development in each area, and also understand what is technologically available at moment, as well as what issues remains to be solved in order to advance further. In this short workshop, instructive presentations by leading scientists in this field, covering wide aspects of research areas including theoretical studies, algorithms, and their physical realizations are planned. Through these presentations and succeeding discussions, we hope the participants are able to share a common view regarding which direction(s) we should advance as a research community, what issues we should solve next, and what kinds of collaboration are desired among scientists with various expertise. We sincerely wish this workshop is able to help accelerating the progress in the R&D of the quantum computing.

Acc-seminars: http://www.acc.stevens.edu/seminars.php

6. Proceedings of the conference on Geometric and
Combinatorial Group Theory with Applications

The conference
"Geometric and Combinatorial Group Theory with Applications" was held in Dortmund (Germany), 27-31 August 2007. ( http://www.mathematik.uni-dortmund.de/~gcgta )

Birkhauser have expressed a great interest in publishing the Proceedings of the conference. The proceeding will be joint for the conference in Dortmund and the workshops in Carleton and Montreal (Canada), December 2007. http://www.fields.utoronto.ca/programs/scientific/07-08/asympotic/index.html

Editorial board:

Oleg Bogopolski (Dortmund),
Enric Ventura (Barcelona),
Inna Bumagin (Carleton),
Olga Kharlampovich (McGill)

This is a call for papers to this Proceedings book. Birkhauser (and we) would like to receive the papers of a high mathematical quality.
All papers will pass the standard refereeing procedure. The deadline for sending us papers is 30th March of 2008.

With best regards,

Oleg Bogopolski (obogopol@mathematik.uni-dortmund.de)
Enric Ventura (enric.ventura@upc.edu)

---

END OF ISSUE