CGC Bulletin 10

eZine lover (@eZine)

Published in

CGC Bulletin

· 11 months ago

Cryptanalysis of a homomorphic public-key cryptosystem over a finite group
Betti numbers of finitely presented groups and very rapidly growing functions
On the security of new key exchange protocols based on the triple decomposition problem
A better length function for Artin's braid groups
Call for Papers: Discrete Applied Mathematics -- Special Issue on "Applications of Algebra to Cryptography"

Enjoy,

Boaz Tsaban

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

1. Cryptanalysis of a homomorphic public-key cryptosystem over a finite group

The paper cryptanalyses a public-key cryptosystem recently proposed by Grigoriev and Ponomarenko, which encrypts an element from a fixed finite group defined in terms of generators and relations to produce a ciphertext from SL(2,Z). The paper presents a heuristic method for recovering the secret key from the public key, and so this cryptosystem should not be used in practice.

http://eprint.iacr.org/2006/357

Simon Blackburn, Su-Jeong Choi, and Peter Wild

2. Betti numbers of finitely presented groups and very rapidly growing functions

Alexander Nabutovsky and Shmuel Weinberger

Define the length of a finite presentation of a group $G$ as the sum of lengths of all relators plus the number of generators. How large can be the $k$th Betti number $b_k(G)=$ rank $H_k(G)$ providing that $G$ has length $\leq N$ and $b_k(G)$ is finite? We prove that for every $k\geq 3$ the maximum $b_k(N)$ of $k$th Betti numbers of all such groups is an extremely rapidly growing function of $N$. It grows faster that all functions previously encountered in Mathematics (outside of Logic) including non-computable functions (at least those that are known to us). More formally, $b_k$ grows as the third busy beaver function that measures the maximal productivity of Turing machines with $\leq N$ states that use the oracle for the halting problem of Turing machines using the oracle for the halting problem of usual Turing machines. We also describe the fastest possible growth of a sequence of finite Betti numbers of a finitely presented group. In particular, it cannot grow as fast as the third busy beaver function but can grow faster than the second busy beaver function that measures the maximal productivity of Turing machines using an oracle for the halting problem for usual Turing machines. We describe a natural problem about Betti numbers of finitely presented groups such that its answer is expressed by a function that grows as the fifth busy beaver function. Also, we outline a construction of a finitely presented group all of whose homology groups are either ${\bf Z}$ or trivial such that its Betti numbers form a random binary sequence.

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

3. On the security of new key exchange protocols based on the triple decomposition problem

M. Chowdhury

We show that two new key exchange protocols with security based on the triple DP may have security based on the MSCSP.

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

Editor's comment: This note refers to an interesting suggestion made in: A New Key Exchange Primitive Based on the Triple Decomposition Problem, Yesem Kurt, Cryptology eprint archive, http://eprint.iacr.org/2006/378. In that paper, the author tried to construct a protocol based on equations without known parameters.

Unfortunately, the present paper shows how to extract from the public key conjugations of known elements.

The question whether cryptosystems based on equations with no known parameters can be constructed remains open, and is very interesting.

4. A better length function for Artin's braid groups

http://arxiv.org/abs/math.GR/0611918

Having a good length function on a group is the main ingredient in a recent combined memory/length approach to solving random equations in that group. Currently, the groups of greatest interest in this respect are Artin's braid groups.

We demonstrate, by a series of experiments, that a length function based on the Birman-Ko-Lee presentation of the braid group is substantially better than the corresponding function based on the Artin presentation.

Martin Hock and Boaz Tsaban

5. Call for Papers: Discrete Applied Mathematics -- Special Issue on "Applications of Algebra to Cryptography"

Motivation & Scope:

Within cryptographic research, the importance of algebra has been increasing significantly throughout the years. This special issue of Discrete Applied Mathematics aims at further advancing the exchange of ideas between researchers in algebra and cryptography. Consequently, the main focus of this special issue is on original research relating algebra and cryptography. However, to facilitate discussion among different research communities, also articles with a more tutorial emphasis are welcome.

Submissions:

Manuscripts should be submitted as a PDF or PostScript file by email to one of the guest editors: