Non-associative quasigroups are well known combinatorial designs with many different applications. Many cryptographic algorithms based on quasigroups primitives have been published. There are several classifications of quasigroups based on their algebraic properties. In this paper we propose a new classification of quasigroups based upon strings (product elements) obtained by a product of a sequence. It is shown in this paper that the more various results of the product elements, the less associative quasigroup.
1 Introduction
Almost all known constructions of cryptographic algorithms have made use of
associative algebraic structures such as groups and fields. There is a possibility
to use non-associative quasigroups [
If a quasigroup is a base of some cryptographic primitive, it is necessary to examine whether its algebraic properties, structure or other features possess a security risk to the whole cryptographic algorithm. From all existing quasigroups of a given order we have to select those, which do not have various identities (as associativity is) and in which various identities appears rarely, or rather not at all. Properties of small quasigroups (e.g. of order 4), represented as a lookup table only, may be examined by the exhaustive search. But examination of identities of the quasigroups of a large order, e.g. 216, may not be easy.
Testing of all possible identities at once may be expensive, both in terms of time and in terms of space. Therefore we have focused on associativity only. If associativity holds, then for each element a, b, c ∈ Q : a ◦ (b ◦ c) = (a ◦ b) ◦ c. The situation differs when we work with non-group (i.e. non-associative) structure: a ◦ (b ◦ c) 6= (a ◦ b) ◦ c. We have made experiments with powers ak of all elements a ∈ Q, where k = 2, 3, . . . , n, n = |Q|, obtained by a product of a sequence. Obtained results were evaluated and compared to the number of associative triples identified for each quasigroup used in experiments. Tested set of quasigroups was the subset of all distinct quasigroups of order 8. For better representation of the results, we have used their visualization.
The paper is organized as follows. Motivation of our work is introduced in Section 2, some necessary concepts are given here too. Concept of a product of sequence, experiments and their results are described in Section 3. Finally, Section 4 comprise conclusion and some ideas of future works. 2 2.1
Preliminaries
Basic Concepts Definition 1. Let A = {a1, a2, . . . , an} be a finite alphabet, n × n Latin square L of order n 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.
The numbers of all LSs of order ≤ 11 are known [
In general, the operation ◦ is neither a commutative nor an associative operation.
Every quasigroup satisfying the associative law has an identity element and is,
hence, a group. There is, for example, 576 distinct quasigroups of order 4, but
only 16 are associative. So non-associative quasigroups dominate heavily.
5 We abbreviate ’Latin square’ to LS.
Isotopism. Various methods of generating a practically unlimited number of
quasigroups of a (theoretically) arbitrary order are known and shown in various
publications. One common way of creating quasigroups is through isotopism [
One can prove that the set of all isotopisms of a quasigroup of order n forms a group of order (n!)3. It should be noted that the mapping γ permutes the elements in the table of operations in a quasigroup Q1, while α and β operate on the elements of the row and column borders of this table, respectively. 2.2
Motivation
Design of many of the existing algorithms is based on quasigroup string
transformations [
Consider an alphabet (i.e. a finite set) Q, and denote by Q+ the set of all nonempty words (i.e. finite strings) formed by the elements of Q. Let (Q, ◦) is a quasigroup. Let q = q1q2 . . . qn ∈ Q+, qi ∈ Q and l ∈ Q is a fixed element called leader. For each l ∈ Q we define two functions el◦ and dl◦ : Q+ → Q+ as follows: el◦ (q) = b1b2 . . . bn ⇐⇒ b1 = l ◦ q1, b2 = b1 ◦ q2, . . . , bn = bn−1 ◦ qn (1) i.e. bi+1 = bi ◦ qi+1 for each i = 0, 1, . . . , n − 1, where b0 = l, and dl◦ (q) = c1c2 . . . cn ⇐⇒ c1 = l ◦ q1, c2 = q1 ◦ q2, . . . , cn = qn−1 ◦ qn (2) i.e. ci+1 = qi ◦ qi+1 for each i = 0, 1, . . . , n − 1, where q0 = l.
The functions el◦ and dl◦ are called e− and d−transformation of Q+ based on the operation ◦ with leader l. In general, several quasigroup operations on the set Q can be used for defining quasigroup transformations. Let, ◦1, ◦2, . . . , ◦k be such a sequence of (not necessarily distinct) quasigroup transformations. We may also choose leaders l1, l2, . . . lk ∈ Q (not necessarily distinct), and then the compositions • of mappings
Ek = El1l2...lk = el1 • el2 • . . . • elk (3) and
Dk = Dl1l2...lk = dl1 • dl2 • . . . • dlk (4) are said to be E− and D−transformations of Q+ respectively. In the last notation, we use el1 for the clarity, but formally we should use el1◦1 .
The experiments with the length of a period of a string generated by
etransformations are mentioned in [
Experiment with Product of Sequence
Let ◦ be the binary operation. Consider the finite sequence A of elements
a1, . . . , an, ai ∈ A, i = 1, 2, . . . , n, n ≥ 2. What does mean a product of this
sequence? Clearly, for n = 2 we have a1 ◦ a2, by juxtaposition a1a2. For n = 3
a product of the sequence a1, a2, a3 is defined as a set consisting of product
elements a1(a2a3) and (a1a2)a3. The product is denoted as {a1a2a3} and
symbol a1a2a3 means any product element. Generally, we can define a product of a
sequence of n elements of the set A as follows [
Definition 4. The product of a sequence a1, a2, . . . , an of elements ai ∈ A, i = 1, 2, . . . , n is the set {a1a2 . . . an} defined by: – for n = 2 the set {a1a2} consist of only one element a1a2, – for n ≥ 2 the set {a1a2 . . . an} is defined as {a1a2 . . . an} = {a1}{a2 . . . an} ∪ {a1a2}{a3 . . . an} ∪ . . . ∪ {a1 . . . an−1} ∪ {an}.
The n elements can be joined, without changing their order, in n(2!(nn−−21))!! ways.
For e.g. n = 1, 2 . . . , 10 we obtain 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 ways of
joining n elements. These numbers are called Catalan numbers [
1 2m Cm = m+1 m
= m(2!(mm−−21))!! .
If the operation ◦ on the set A does not hold an associativity law, we can generally obtain distinct values a1a2 . . . an (not one common value) for all Cm (m = n − 1, because Catalan numbers are numbered from 0) possible product elements of the product set {a1a2 . . . an} of the sequence a1, a2, . . . , an . 3.1
Experiment We have tested product {q1q2 . . . qk} of the sequence q1, q2, . . . , qk, where all qi ∈ Q, i = 1, 2, . . . , k are equal. So, if all elements are equal, each element is denoted as a and we will compute a product {aa . . . a} of the sequence a, a, . . . , a. | {kz } | {kz } This product consists of all Ck−1 product elements. Questions is, how many distinct values q1q2 . . . qk = aa . . . a = ak for all a ∈ Q we obtain. In the ideal | {z }
k case we can obtain all possible values as a result; the set of possible values has only max. n values from Q (of order n) for all powers ak.
Better information about the identities in the given quasigroup gain from the evaluation of particular product elements by the e-transformation defined in Eq. (2). Therefore all strings b1 . . . b8, see Fig. 1, obtained during evaluation of product elements of ak (for k = 8, a8 = b8, Fig. 1) were stored. The experiment: – Generate a quasigroups Q of order n. – For each element a ∈ Q and for each k, 2 ≤ k ≤ n create the product {aa . . . a} of the sequence a, a, . . . , a, evaluate all Ck−1 product elements ak. – Store strings b1 . . . bk and compute the number of their occurrence during evaluation of all product elements ak.
a a ? b1 a ? b2 . . . . . .
a b7 ? a
?
b8 = a8
Quasigroups were represented by corresponding Latin squares. We decided to
use a subset of quasigroups of order 8. We have tested:
– all n! = 40320 distinct quasigroups isotopic to additive group (Z8, +) when
only permutation α was not an identity permutation,
– a set of one million randomly generated quasigroups,
– a set of special quasigroups that consist of e.g. additive group (Z8, +), of six
well described quasigroups published in [
Results are shown on the highest (8th) power of element a. There are C7 = 429 distinct ways how to obtain it.
– Ideally, for each a ∈ Q, i.e. for each a = 0, 1, . . . , 7, we obtain all 8 possible values of a8 ∈ Q. – For each a ∈ Q we obtain all 429 distinct strings b1 . . . b8. – Finally, for each quasigroup (Q, ◦) we ideally obtain all together 429 × 8 = 3432 distinct strings b1 . . . b8 for all a ∈ Q. 3.4
Results of experiments are shown on the set of five chosen quasigroups
represented by their corresponding LSs. The first quasigroup is randomly generated
quasigroup No. 24 represented by L24. The second quasigroup, obtained by
nonaffine isotopy [
Numbers of distinct values a8 for each a ∈ Q for five chosen quasigroups are shown in Table 1. Only quasigroups No. 24 and 104 have ideal results. Conversely, quasigroup’s No. 107 results are always the same; a8 is always 0.
Results of the process evaluating the strings b1 . . . b8: the best results have quasigroups No. 24 and 104. Number of all distinct strings is higher comparing the remaining three quasigroups. This fact is evident from Table 2 (sums of distinct strings for each quasigroup and all a ∈ Q are shown). The higher number of associative triples, the lower the sum of all strings. Results were also visualized, Sec. 3.5. The greater number of subsquares of different brightness in the image corresponds with the greater number of distinct strings b1 . . . b8 for each a8, see Figs. 2 and 3. We have focused only on the 8th power of quasigroups elements. For each quasigroup (Q, ◦) and for each a8, a ∈ Q, we have generated 512 × 512 pixels images where each subsquare (64 × 64 pixels) represents one element lij of tested quasigroup represented by corresponding Latin square L, lij ∈ L. The more visits of particular element, the brighter subsquare. The brightness of the subsquares is calculated relatively to the number C7 × ir = 429 × 6 = 2574, where ir = 6 is number of strings from a2 to a8 when computing a8. The greater the sum of distinct strings b1 . . . bn, the greater the number of subsquares of different brightness in the image.
Conclusion Our goal is to find a new way of testing the properties of large quasigroups and to explore the interpretation of experimental results. We have reported a new classification of quasigroups based upon strings (product elements) obtained by a product of a sequence. As is shown, the more various results of the product elements, the less associative quasigroup. More precisely, values of all possible product elements from the product set of a sequence of elements from a given quasigroup were examined and relationships between experiment results and associativity of tested quasigroup have been tested. Testing of quasigroup’s identities through the product of a sequence is an appropriate method with good results. Experiments will be repeated with quasigroups of larger order. Several consecutive applications of a quasigroup transformations on the sequences will be tested, too.