Evolving Quasigroups by Genetic Algorithms

Václav Snásel, Jiri Dvorský, Eliska Ochodkova, Pavel Krömer, Jan Platos, Ajith AbrahamDATESO 2010

TL;DR

This paper introduces a novel genetic algorithm approach to discover "analytic quasigroups" with desirable cryptographic properties, specifically low associativity and commutativity. By encoding permutations as random keys and employing a fitness function that penalizes these properties, the authors demonstrate that their genetic algorithm can evolve quasigroups superior to randomly generated ones. This work offers a promising avenue for designing more robust cryptographic primitives without relying on traditional lookup tables.

What Problem Does This Paper Address?

The paper tackles the challenge of finding suitable quasigroups for cryptographic applications, particularly for generating pseudorandom sequences (keystreams) in stream ciphers. While quasigroups offer attractive properties like uniform element distribution, their sheer number and the computational cost of evaluating their cryptographic strength are significant hurdles. Traditional implementations often rely on lookup tables, which become infeasible for large quasigroups. The concept of "analytic quasigroups" aims to overcome this by defining quasigroups through mathematical formulas and permutations, avoiding explicit storage. However, efficiently searching for analytic quasigroups with optimal cryptographic properties (like low associativity and commutativity, which are desirable for security) remains an open problem.

Methods

The core of this paper is the development of a genetic algorithm (GA) designed to search for "good" analytic quasigroups. The process involves:

  • Encoding: Candidate solutions (analytic quasigroups) are encoded using a "random key" (RK) encoding strategy. Since analytic quasigroups are defined by three permutations, the GA chromosome represents these permutations as concatenated strings of real numbers. This encoding allows for standard GA operators.
  • Fitness Function: A novel fitness function is proposed, which quantifies the "badness" of a quasigroup in terms of its associativity and commutativity. The function is a weighted sum of penalties for deviations from perfect associativity and commutativity. A coefficient α allows prioritizing one property over the other. The goal is to find quasigroups with low associativity and commutativity.
  • Genetic Operators: Standard GA operators like crossover (n-point) and mutation (uniform random replacement) are used. Selection is performed using an elitist strategy.
  • Optimization Goal: The GA aims to minimize the fitness function, effectively searching for quasigroups that exhibit low associativity and commutativity.

Datasets

Not discussed in the paper. The paper focuses on generating and evaluating quasigroups based on their mathematical properties rather than using pre-existing datasets.

Key Insights and Ideas

  • Analytic Quasigroups as a Solution: The paper highlights analytic quasigroups as a practical way to handle large quasigroups without memory-intensive lookup tables, making them suitable for cryptographic applications.
  • Random Key Encoding for Permutations: Using random key encoding for permutations within the GA is an effective strategy that bridges the gap between permutation optimization and standard GA implementations.
  • Fitness Function for Cryptographic Desirability: The proposed fitness function, which directly penalizes associativity and commutativity, is a clever way to guide the search towards quasigroups with properties beneficial for cryptographic security. The idea is that "low associativity" and "low commutativity" are desirable.
  • GA's Efficacy: The experiments demonstrate that the genetic algorithm can indeed evolve quasigroups with better (lower) associativity and commutativity scores compared to randomly generated ones.

Key Results

The paper presents experimental results for quasigroups of orders 32, 64, and 128.

  • Improved Properties: In all tested dimensions, the genetic algorithm successfully evolved quasigroups that exhibited lower average associativity (na) and commutativity (nc) values compared to randomly generated quasigroups.
  • Fitness Improvement: Consequently, the average fitness values of the evolved quasigroups were also improved (lower, indicating better properties) compared to random ones. For instance, for order 128, the average fitness of evolved quasigroups was 0.995, while random quasigroups had an average fitness of 0.952.
  • Computational Cost: The authors acknowledge that evaluating the fitness function is computationally expensive, as it requires checking all combinations of 2 and 3 elements for the given quasigroup dimension.

Limitations and Future Work

  • Computational Expensiveness: The primary limitation identified is the computational cost of evaluating the fitness function, which scales poorly with the quasigroup dimension.
  • Future Work: The authors propose several directions for future research:
  • Investigating other properties of generated quasigroups.
  • Exploring alternative fitness functions.
  • Focusing on efficient implementation of the GA, potentially using GPGPU.
  • Investigating other computational intelligence methods for quasigroup optimization, such as differential evolution and ant colony optimization.

Summary updated

BibTeX
@inproceedings{snasel2010evolving,
  author = {Václav Snásel and Jiri Dvorský and Eliska Ochodkova and Pavel Krömer and Jan Platos and Ajith Abraham},
  title = {{Evolving Quasigroups by Genetic Algorithms}},
  booktitle = {DATESO},
  year = {2010},
}
Figure