Evolution of group-theoretic cryptology attacks using hyper-heuristics
From MaRDI portal
Publication:2059940
Abstract: In previous work, we developed a single Evolutionary Algorithm (EA) to solve random instances of the Anshel-Anshel-Goldfeld (AAG) key exchange protocol over polycyclic groups. The EA consisted of six simple heuristics which manipulated strings. The present work extends this by exploring the use of hyper-heuristics in group-theoretic cryptology for the first time. Hyper-heuristics are a way to generate new algorithms from existing algorithm components (in this case the simple heuristics), with the EAs being one example of the type of algorithm which can be generated by our hyper-heuristic framework. We take as a starting point the above EA and allow hyper-heuristics to build on it by making small tweaks to it. This adaptation is through a process of taking the EA and injecting chains of heuristics built from the simple heuristics. We demonstrate we can create novel heuristic chains, which when placed in the EA create algorithms which out-perform the existing EA. The new algorithms solve a markedly greater number of random AAG instances than the EA for harder instances. This suggests the approach could be applied to many of the same kinds of problems, providing a framework for the solution of cryptology problems over groups. The contribution of this paper is thus a framework to automatically build algorithms to attack cryptology problems.
Recommendations
- A parallel evolutionary approach to solving systems of equations in polycyclic groups
- Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography
- Length-based attacks in polycyclic groups
- Random subgroups and analysis of the length-based and quotient attacks
- The status of polycyclic group-based cryptography: a survey and open problems
Cites work
- A linear decomposition attack
- A model for fresh produce shelf-space allocation and inventory management with freshness-condition-dependent demand
- A nonlinear decomposition attack
- A parallel evolutionary approach to solving systems of equations in polycyclic groups
- A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups
- Algorithmic problems in Engel groups and cryptographic applications
- An algebraic method for public-key cryptography
- Analysis of a certain polycyclic-group-based cryptosystem
- Conjugacy problem for braid groups and Garside groups.
- Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography
- Exploring hyper-heuristic methodologies with genetic programming
- Group-based cryptography
- scientific article; zbMATH DE number 1617914 (Why is no real title available?)
- scientific article; zbMATH DE number 5380256 (Why is no real title available?)
- scientific article; zbMATH DE number 1759777 (Why is no real title available?)
- HyFlex: a benchmark framework for cross-domain heuristic search
- Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol
- Length-based attacks in polycyclic groups
- Length-based cryptanalysis: the case of Thompson's group
- ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS
- Probabilistic solutions of equations in the braid group.
- Solving the conjugacy decision problem via machine learning
- The status of polycyclic group-based cryptography: a survey and open problems
- Using Decision Problems in Public Key Cryptography
This page was built for publication: Evolution of group-theoretic cryptology attacks using hyper-heuristics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2059940)
