ORCID

Abstract

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, simple heuristics), with 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 that out perform the existing EA. The new algorithms solve a greater number of random AAG instances than the EA. This suggests the approach may 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 article is thus a framework to automatically build algorithms to attack cryptology problems given an applicable group.

DOI

10.1515/jmc-2021-0017

Publication Date

2021-09-28

Publication Title

Journal of Mathematical Cryptology

Volume

16

Issue

1

First Page

49

Last Page

63

ISSN

1862-2976

Embargo Period

2021-10-30

Organisational Unit

School of Engineering, Computing and Mathematics

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Share

COinS