×

The complexity of Grigorchuk groups with application to cryptography. (English) Zbl 0749.68040

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.

MSC:

68Q25 Analysis of algorithms and problem complexity
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
94A60 Cryptography
68Q45 Formal languages and automata
68P25 Data encryption (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anisimov, A. V., Group languages, Kibernetika, 4, 18-24 (1971)
[2] Avenhaus, J.; Madlener, K., Subrekursive komplexität bei gruppen, Acta Inform., 9, 87-104 (1977) · Zbl 0371.02019
[3] Baker, T.; Gill, J.; Solovay, R., Relativizations of the \(P = NP \)? question, SIAM J. Comput., 4, 4, 431-444 (1975) · Zbl 0323.68033
[4] Barrington, D. A., Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^1\), Proc. 18th STOC, 1-5 (1986)
[5] Boone, W. W., Word problems and recursively enumerable degrees of unsolvability, Ann. of Math., 84, 49-84 (1966) · Zbl 0173.01301
[6] Denning, D. E., Digital signatures with RSA and other PKCs, Comm. ACM, 27, 4, 388-392 (1984)
[7] Dunwoody, M. J., The accessibility of finitely presented groups, Invent. Math., 81, 449-457 (1985) · Zbl 0572.20025
[8] Grigorchuk, R., Degrees of growth of finitely generated groups and the theory of invariant means, Math. USSR-Izv., 25, 259-300 (1985) · Zbl 0583.20023
[9] Hopcroft, J.; Ullman, J., Introduction to Automata theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[10] Kharlampovich, O. G., A finitely presented group with unsolvable word problem, Math. USSR-Izv., 19, 151-169 (1982) · Zbl 0494.20021
[11] Lipton, J.; Zalcstein, Y., Word problems solvable in logspace, J. Assoc. Comput. Mach., 24, 522-526 (1977) · Zbl 0359.68049
[12] Lyndon, R.; Schupp, P. E., Combinatorial Group Theory (1977), Springer: Springer Berlin, Heidelberg, New York · Zbl 0368.20023
[13] Micali, S.; Rackoff, C.; Sloan, B., The notion of security for probabilistic cryptosystems, Proc. CRYPTO’86. Proc. CRYPTO’86, Siam J. Comput., 17, 2, 412-426 (1988) · Zbl 0644.94013
[14] Milnor, J., Advanced Problem 3603, Amer. Math. Monthly, 75, 685-686 (1968)
[15] Muller, D. E.; Schupp, P. E., Groups, the theory of ends and context-free languages, J. Comput. System. Sci., 26, 295-310 (1983) · Zbl 0537.20011
[16] Sakarovitch, J., Syntaxe des Langages de Chomsky, (Ph.D thesis (1979), Univ. de Paris)
[17] Savitch, W., Relationship between deterministic and nondeterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[18] Simon, H. U., Word problems for groups and context-free languages, (Foundations of Computation Theory. Foundations of Computation Theory, Lecture Notes in Computer Science (1979), Springer: Springer New York), 417-422
[19] Tits, J., Free subgroups in linear groups, J. Algebra, 20, 250-270 (1972) · Zbl 0236.20032
[20] Trofimov, V. I., Growth function of some classes of languages, Cybernetics, 17, 727-731 (1981) · Zbl 0512.68054
[21] Valiev, M. K., On polynomial reducibility of word problems under embedding of recursively presented groups in finitely presented groups, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 32 (1975), Springer: Springer New York), 432-438 · Zbl 0323.02055
[22] Waack, S., Tape complexity of word problems (extended abstract), (Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 117 (1981), Springer: Springer New York), 467-471 · Zbl 0498.03038
[23] Waack, S., Tape Complexity of Word Problems (1981), Akademie der Wissenschaften der DDR, (Tech. Report-MATH-04/8) · Zbl 0498.03038
[24] Wagner, N. R.; Magyarik, M. R., A public-key cryptosystem based on the word problem, (Proc. CRYPTO’84. Proc. CRYPTO’84, Lecture Notes in Computer Science, Vol. 196 (1985), Springer: Springer Berlin), 19-36 · Zbl 0569.94010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.