CGC Bulletin 7

eZine lover (@eZine)

Published in

CGC Bulletin

· 1 Dec 2023

A New Cryptosystem Based On Hidden Order Groups
Conjugacy in Garside groups I: Cyclings, powers, and rigidity
Electronic publications of the Algebraic Cryptography Center (Stevens Institute of Technology)
CGC Day in Manresa

* Contributors to this issue: Mike Anshel, Vladimir Shpilrain.

Fruitful reading,

Boaz Tsaban

1. A New Cryptosystem Based On Hidden Order Groups

Amitabh Saxena and Ben Soh

Let G be a cyclic multiplicative group of order n. It is known that the Diffie-Hellman problem is random self-reducible in G with respect to a fixed generator g if phi(n) is known. That is, given g, g^x \in G and having oracle access to a `Diffie-Hellman Problem' solver with fixed generator g, it is possible to compute g^{1/x} \in G in polynomial time. On the other hand, it is not known if such a reduction exists when phi(n) is unknown. We exploit this "gap'' to construct a cryptosystem based on hidden order groups and present a practical implementation of a novel cryptographic primitive called an \textit \{Oracle \, Strong \, Associative \, One-Way \,Function\} (O-SAOWF). O-SAOWFs have applications in multiparty protocols. We demonstrate this by presenting a key agreement protocol for dynamic ad-hoc groups.

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

2. Conjugacy in Garside groups I: Cyclings, powers, and rigidity

Joan S. Birman, Volker Gebhardt, Juan Gonzalez-Meneses

In this paper a relation between iterated cyclings and iterated powers of elements in a Garside group is shown. This yields a characterization of elements in a Garside group having a rigid power, where 'rigid' means that the left normal form changes only in the obvious way under cycling and decycling. It is also shown that, given X in a Garside group, if some power X^m is conjugate to a rigid element, then m can be bounded above by ||\Delta||^3 . In the particular case of braid groups, this implies that a pseudo-Anosov braid has a small power whose ultra summit set consists of rigid elements. This solves one of the problems in the way of a polynomial solution to the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in braid groups. In addition to proving the rigidity theorem, it will be shown how this paper fits into the authors' program for finding a polynomial algorithm to the CDP/CSP, and what remains to be done.

http://www.arxiv.org/abs/math.GT/0605230

3. Electronic publications of the Algebraic Cryptography Center (Stevens Institute of Technology)

http://www.acc.stevens.edu/pubs.php

Contains selected publications, presentations, and links to reserachers, all in the category of CGC.

Following is the list of presentations available there:

Alexandra Boldyreva (Georgia Institute of Technology), Public-Key Encryption in a Multi-User Setting: Privacy, Anonymity and Efficiency.
Alexander N. Rybalov (Omsk State University), On the strongly generic undecidability of the halting problem.
Vladimir Shpilrain (The City College of New York) Random subgroups of braid groups: cryptanalysis of a braid group based cryptographic protocol. joint with Alexei G. Myasnikov and Alexander Ushakov
Rainer Steinwandt (Florida Atlantic University), Towards Provably Secure Asymmetric Encryption Building on Finite Non-Abelian Groups
Rainer Steinwandt (Florida Atlantic University), Non-Abelian Groups as Candidate Platform for Cryptographic Schemes: Strengths and Weaknesses
Yacov Yacobi (Microsoft), A New Related Message A\ttack on RSA

4. CGC Day in Manresa

The conference "Geometric and Asymptotic Group Theory Conference with Applications" (GAGTA), (August 31 -- September 4, 2006, Escola Politècnica Superior d'Enginyeria de Manresa, the Universitat Politècnica de Catalunya), is an official satellite activity of the ICM06. A whole day in this conference (September 4) is dedicated to Group Based Cryptography.

The current list of invited speakers in this day is: