Quasigroups are a well-known combinatorial design equivalent to more familiar Latin squares. Because all possible elements of a quasigroup occur with equal probability, it makes it an interesting tool for the application in computer security and for production of pseudorandom sequences. Most implementations of quasigroups are based on look-up table of the quasigroup, on system of distinct representatives etc. Such representations are infeasible for large quasigroups. An analytic quasigroup is a recent concept that allows usage of certain quasigroups without the need of look-up table. The concept of isotopy enables consideration of many quasigroups and genetic algorithms allow efficient search for good ones. In this paper we describe analytic quasigroup and genetic algorithms for its optimization.
1 Introduction Random and pseudorandom sequences can be used in many applications, e.g. in modeling, simulations, and of course in cryptography. Pseudorandom sequences are the core of stream ciphers. The design goal in stream ciphers is to efficiently produce pseudorandom sequences - keystreams (i.e. sequences that possess properties common to truly random sequences and in some sense are ”indistinguishable” from these sequences).
The use of quasigroups and quasigroup string transformations is a recent
but successful tendency in cryptography and coding [
Quasigroups and its applications in computer security were studied e. g. in [
Genetic algorithms are probably the most popular and wide spread
member of the class of evolutionary algorithms (EA). EAs operate with a
population of artificial individuals (chromosomes) encoding potential problem solutions.
Encoded individuals are evaluated using a carefully selected objective function
which assigns a fitness value to each individual. The fitness value represents the
quality (relative ranking) of each individual as a solution to given problem.
Competing individuals explore in a highly parallel manner problem domain towards
an optimal solution [
Quasigroups Definition 1. A quasigroup is a pair (Q, ◦), where ◦ is a binary operation on (finite) set Q such that for all not necessarily distinct a, b ∈ Q, the equations a ◦ x = b and y ◦ a = b. have unique solutions.
The fact that the solutions are unique guarantees that no element occurs twice in any row or column of the table for (◦). However, in general, the operation (◦) is neither a commutative nor an associative operation.
Quasigroups are equivalent to more familiar Latin squares. The
multiplication table of a quasigroup of order q is a Latin square of order q, and conversely,
as it was indicated in [
Definition 2. Let A = {a1, a2, . . . , an} be a finite alphabet, a n × n Latin square L is a matrix with entries lij ∈ A, i, j = 1, 2, . . . , n, such that each row and each column consists of different elements of A.
For i, j, k ∈ A the ordered triple (i, j; k) is used to represent the occurrence of element k in cell (i, j) of the Latin square. So a Latin square may be represented by the set {(i, j; k)| entry k occurs in cell (i, j) of the Latin square L.}
All reduced Latin squares of order n are enumerated for n ≤ 11 [
Ln = n!(n − 1)!Rn.
Number of distinct Latin squares of a given order grows exceedingly quickly with the order and there is no known easily-computable formula for the number of distinct Latin squares. The problem of classification and exact enumeration of Latin squares of order greater than 11 probably still remains unsolved. Thus, there are more than 1090 quasigroups of order 16 and if we take an alphabet L = {0 . . . 255} (i.e. data are represented by 8 bits) there are at least 256!255! . . . 2! > 1058000 quasigroups.
Multiplication in quasigroups has an important property; it is proven that
each element occurs exactly q times among the products of two elements of Q,
q2 times among the products of three elements of Q and, generally qt−1 among
the products of t elements of Q. Since there are qt possible ordered products of
t elements of Q, this shows that each element occurs equally often among these
qt products (see [
Isotopism of quasigroups Definition 3. Let (G, ·), (H, ◦) be two quasigroups. An ordered triple (π, ρ, ω) of bijections π, ρ, ω of the set G onto set H is called an isotopism of (G, ·) upon (H, ◦) if ∀u, v ∈ G, π(u) ◦ ρ(v) = ω(u · v). Quasigroups (G, ·), (H, ◦) are said to be isotopic.
We can imagine an isotopism of quasigroups as a permutation of rows and columns of quasigroup’s multiplication table.
Example 1. Consider a multiplication table for a quasigroup isotopic to the quasigroup of modular subtraction, with operation ◦ defined as a ◦ b = (a + n − b) mod n): The table was created from table of modular subtraction. The second and the third rows were exchanged. Permutations π, ρ were identities and ω = [0213]. A multiplication in this quasigroup can be illustrated by e.g. 1 ◦ 0 = ω(1) ◦ 0 = 2 ◦ 0 = 2.
Starting with the quasigroup of modular subtraction, we can explore a large
class of quasigroups isotopic to the quasigroup of modular subtraction [
We call the quasigroup defined by its multiplication formula and three
selected permutations an analytic quasigroup [
The notion of analytic quasigroup enables efficient work with large
quasigroups. Previos studies in this field used mostly quasigroups of small order [
The properties of one analytic quasigroup isotopic to the quasigroup of
modular subtraction were studied in [
Constructing quasigroups isotopic to the quasigroup of modular subtraction Consider a quasigroup on the length n defined by multiplication a ◦ b = (a + n − b) mod n). Then three permutations π, ρ, ω must be chosen in order to implement isotopic quasigroup, whose multiplication will be defined by (1).
Obviously, there is n! different permutations of n elements. Because three independent permutations are used to define any isotopic quasigroup, there are n!n!n! possible choices of π, ρ and ω. Permutations of elements cannot be sought for an analytic quasigroup directly, because its elements are not stored in memory. Instead, the permutation needs to be implemented as a function of an element of Q. One way to achieve this goal is the use of bit permutation.
A quasigroup over a set of n elements requires log2(n) bits to express each element. Each permutation of bits in the element representation represents also a permutation of all elements of the quasigroup (if n is a power of 2). Bit permutation can be implemented easily as a function of q ∈ Q.
The bit permutation is an elegant way of implementing permutations over n elements of Q. Although it enables us to explore only a fragment (log2(n)!log2(n)! log2(n)!) of all possible permutation triples over the quasigroup of n elements, it is useful because it does not require all n elements in main memory and therefore fits into the framework of analytic quasigroups.
Bit permutations are computationaly more expensive than the static
functions used to implement permutation in [
The emulated evolution is driven by iterative application of genetic operators. Genetic operators algoritmize principles observed in natural evolution. The crossover operator defines a strategy for the exchange of genetic information between parents (sexual reproduction of haploid organisms) while the mutation operator introduces the effect of environment and randomness (random perturbation of genetic information). The basic workflow of the standard generational GA is shown in algorithm 1.
Algorithm 1: A summary of genetic algorithm 1 Define objective (fitness) function and problem encoding 2 Encode initial population P of possible solutions as fixed length strings 3 Evaluate chromosomes in initial population using objective function 4 while Termination criteria not satisfied do 5 Apply selection operator to select parent chromosomes for
reproduction: sel(Pi) → parent1, sel(Pi) → parent2 6 7 8
Apply crossover operator on parents with respect to crossover probability to produce new chromosomes: cross(pC, parent1, parent2) → {of f spring1, of f spring2} Apply mutation operator on offspring chromosomes with respect to mutation probability: mut(pM, of f spring1) → of f spring1, mut(pM, of f spring2) → of f spring2 Create new population from current population and offspring chromosomes: migrate(of f spring1, of f sprig2, Pi) → Pi+1 9 end
Many variants of the standard generational GAs have been proposed. The
differences are mostly in particular selection, crossover, mutation and
replacement strategy [
In the next section, we present genetic algorithm for the search for good
analytic quasigroups. It is an extended version of the initial GA for quasigroup
evolution introduced in [
Genetic search for analytic quasigroups The genetic algorithm for the search for analytic quasigroup is defined by encoding of the candidate solutions and fitness function to evaluate chromosomes. As noted in subsection 2.2, any analytic quasigroup isotopic to quasigroup of modular subtraction is defined by three permutations. Such permutation triple represents a problem solution and should be mapped to one GA chromosome. Permutations can be for the purpose of genetic algorithms encoded using several strategies. In this study, we use random key encoding.
Random key (RK) encoding is an encoding strategy suitable for problems
involving permutation optimization [
To encode a quasigroup (isotopic to the quasigroup of modular subtraction) of the length n = 2l, we use a vector of 3l real numbers v = (v1, . . . , vl−1, vl, . . . v2l−1, v2l, . . . , v3l). The vector is interpreted as three concatenated RK encoded permutations of the length l.
This encoding allows us to use traditional implementations of genetic
operators, such as n-point crossover and mutation. Crossover was implemented
as mutual exchange of genes between selected parents and mutation was
implemented as a replacement of gene with a uniform random number from the
interval [
Fitness function The fitness function f we propose in this work is based on commutativity and associativity in quasigroup.
f (n, na, nc, α) = α n2 − nc + (1 − α) n3 − na
n2 n3
In (3), n stands for the order of the quasigroup, n2 stands for the number
of all combinations of 2 elements out of n, n3 represents all combinations of
3 elements out of n, nc stands for the number of element pairs that have the
commutativity property and na represents the number of element triples that
have the associativity property. The coefficient α ∈ [
(c) Average fitness in random quasigroups. f 1 corresponds to n2−nc , f 2 to n3−na and
n2 n3 f = 0.5f 1 + 0.5f 2
In the next step, we have performed genetic search for better (in terms of low associativity and low commutativity) quasigroups isotopic to the quasigroups of modular subtraction with the dimensions 32, 64 and 128 respectively. We have implemented genetic algorithm with permutation encoding and fitness function as defined above. The parameters of the algorithm (α, PM , PC etc.) were selected after initial tuning of the algorithm. The paramteres are summarized in Table 1.
Beacuse genetic algorithm is a stochastic method, every experiment was repeated 10 times and presented results are average values after 10 independent runs. The values of optimized fitness, nc and na are shown in Table 2. A comparison of optimized values with na, nc and fitness in random quasigroups isotopic to the quasigroups of modular subtraction are illustrated in Figure 2. We can see that in every experiment (for every quasigroup dimension), the genetic optimization process delivered a quasigroup better than random one. 6
Conclusions In this paper was described a genetic algorithm for optimization of an analytic quasigroup. The genetic algorithm performs a search for good bit permutations that are then used to construct analytic quasigroups with desired properties. Both, the analytic quasigroup and bit permutation, do not rely on the lookup table of the quasigroup stored in memory.
The fitness function we use in this paper is based on associativity and commutativity in quasigroups. It triggers a search for quasigroups that have “low associativity“ and “low commutativity“. In a numerical experiment, we have been able to find quasigroups with better properties than random ones have. The drawback of this method is at this point its computational expensiveness. In order to evaluate the fitness function, all combinations of 2 elements out of n and all combinations of 3 elements out of n (quasigroup dimension) have to be found and evaluated using quasigroup operation ◦. However, the main aim of this work was to verify that genetic algorithm can evolve quasigroups with above average properties. (a) Average na in optimized quasigroups. (b) Average nc in optimized quasigroups. Lower is better. Lower is better.
(c) Average fitness in optimized quasigroups. Higher is better.
Fig. 2. Average values of na, nc and fitness in optimized quasigroups of order 32, 64 and 128 compared with na, nc and fitness in random quasigroups.
In our future work, we want to investigate the properties of generated quasigroups, study the fitness function and look for alternative fitness functions. We want to focus on efficient implementation of used genetic algorithms with the utilization of GPGPU. Moreover, we will investigate other successful computational intelligence methods for quasigroup optimization (e.g. differential evolution, ant colony optimization).