The complexity of Grigorchuk groups with application to cryptography

DOI10.1016/0304-3975(91)90074-CzbMath0749.68040MaRDI QIDQ1177176

Yechezkel Zalcstein, Max H. Garzon

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Grigorchuk groupsword problemspublic key cryptoschemes

Mathematics Subject Classification ID

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

Related Items (17)

Attacking a public key cryptosystem based on tree replacement ⋮ FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY ⋮ Key agreement based on automaton groups ⋮ The concept of duality for automata over a changing alphabet and generation of a free group by such automata ⋮ Cayley automata ⋮ Log-space conjugacy problem in the Grigorchuk group ⋮ The conjugacy problem in the Grigorchuk group is polynomial time decidable. ⋮ THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ Linear time algorithm for the conjugacy problem in the first Grigorchuk group ⋮ Public-key cryptography and invariant theory ⋮ SOLENOIDAL MAPS, AUTOMATIC SEQUENCES, VAN DER PUT SERIES, AND MEALY AUTOMATA ⋮ Clouds over a public key cryptosystem based on Lyndon words ⋮ Ramification structures for quotients of the Grigorchuk groups

Cites Work

• Groups, the theory of ends, and context-free languages
• The accessibility of finitely presented groups
• Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Relationships between nondeterministic and deterministic tape complexities
• Free subgroups in linear groups
• DEGREES OF GROWTH OF FINITELY GENERATED GROUPS, AND THE THEORY OF INVARIANT MEANS
• The Notion of Security for Probabilistic Cryptosystems
• A FINITELY PRESENTED SOLVABLE GROUP WITH UNSOLVABLE WORD PROBLEM
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Word Problems Solvable in Logspace
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of Grigorchuk groups with application to cryptography