The complexity of Grigorchuk groups with application to cryptography (Q1177176)

The complexity of the word problems of a class of groups introduced by Grigorchuk is examined. The Grigorchuk groups are natural families of groups of automorphisms of a complete infinite binary tree defined by means of a special general construction to transform any one-way infinite sequence \(\gamma\) into a word problem of a 4-generator group \(G_ \gamma\) of level preserving permutations of the infinite complete binary tree. It is shown that the word problems in Grigorchuk groups yield natural complete sets that separate time and space complexity classes if they are distinct. New families of nonfinitely presented groups are shown to have word problems uniformly solvable in simultaneous logspace and quadratic time. An interesting application of the results is that a new family of public key cryptoschemes can be created. This is pointed out.