A family of polycyclic groups over which the uniform conjugacy problem is NP-complete

DOI10.1142/S0218196714500234zbMath1298.20048arXiv1403.4153MaRDI QIDQ2876614

Delaram Kahrobaei, Bren Cavallo

Publication date: 19 August 2014

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.4153

zbMATH Keywords

NP-completenesspolycyclic groupsuniform conjugacy problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Solvable groups, supersolvable groups (20F16) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

A nonlinear decomposition attack ⋮ Cryptanalysis of a combinatorial public key cryptosystem ⋮ GENERAL ALGEBRAIC CRYPTOGRAPHIC KEY EXCHANGE SCHEME AND ITS CRYPTANALYSIS ⋮ A NONLINEAR DECOMPOSITION METHOD IN ANALYSIS OF SOME ENCRYPTION SCHEMES USING GROUP AUTOMORPHISMS ⋮ Two general schemes of algebraic cryptography ⋮ Erratum: A family of polycyclic groups over which the uniform conjugacy problem is NP-complete

Cites Work

• Unnamed Item
• Group-based cryptography
• Conjugacy in polycyclic groups
• Conjugate separability in polycyclic groups
• An algebraic method for public-key cryptography
• Non-commutative digital signatures
• Polynomial time conjugacy in wreath products and free solvable groups
• The Conjugacy Problem and Subgroups of Finite Index
• On the orbit-stabilizer problem for integral matrix actions of polycyclic groups
• Decision and Search in Non-Abelian Cramer-Shoup Public Key Cryptosystem

This page was built for publication: A family of polycyclic groups over which the uniform conjugacy problem is NP-complete