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 [7] , well known combinatorial designs with a lot of theoretical results concerning them, too. Many cryptographic algorithms based on quasigroups primitives have been published. Proposed cryptographic algorithms are used for ciphering [15], for constructing pseudorandom generators [9], hash functions [12], for zero knowledge protocols [2], etc. Majority of published algorithms can be seen as rather simple experimental algorithms. As a representative of the ambitious proposals include the stream cipher Edon80 [5] published as an eSTREAM3 candidate, and the NIST's SHA-3 4 competition candidate, hash function EdonR [4].
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. 2 16 , 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
The situation differs when we work with non-group (i.e. non-associative) structure: a
We have made experiments with powers a k 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.
Definition 1. Let A = {a 1 , a 2 , . . . , a n } be a finite alphabet, n × n Latin square L of order n is a matrix with entries l ij ∈ 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 [14]. Number of distinct Latin squares5 of a given order grows exceedingly quickly with the order. Latin squares are equivalent to quasigroups. The multiplication table of a quasigroup of order n is a Latin square of order n, and conversely every Latin square of order n is the multiplication table of a quasigroup of order n [3]. Definition 2. 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. We say that quasigroup
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.
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 [3].
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 Q 1 , while α and β operate on the elements of the row and column borders of this table, respectively.
Design of many of the existing algorithms is based on quasigroup string transformations [7,11]. The following concepts are taken from [7].
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 = q 1 q 2 . . . q n ∈ Q + , q i ∈ Q and l ∈ Q is a fixed element called leader. For each l ∈ Q we define two functions e l• and d l• : Q + → Q + as follows:
where b 0 = l, and
i.e. c i+1 = q i • q i+1 for each i = 0, 1, . . . , n − 1, where q 0 = l.
The functions e l• and d l• 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 l 1 , l 2 , . . . l k ∈ Q (not necessarily distinct), and then the compositions • of mappings
and
are said to be E− and D−transformations of Q + respectively. In the last notation, we use e l1 for the clarity, but formally we should use e l1 • 1 .
The experiments with the length of a period of a string generated by etransformations are mentioned in [6] and in [10]. Quasigroups are divided into two groups, to linear and exponential quasigroups. What algebraic properties must quasigroups of order 4 have to be linear resp. exponential? The quasigroups are of a small order (order 4), it is therefore impossible to say whether (besides identities) it is their structure, which affects the resulting period of the transformed string. Quasigroups of larger order are more convenient for analogical tests described in Sec. 3.
Let • be the binary operation. Consider the finite sequence A of elements a 1 , . . . , a n , a i ∈ A, i = 1, 2, . . . , n, n ≥ 2. What does mean a product of this sequence? Clearly, for n = 2 we have a 1 • a 2 , by juxtaposition a 1 a 2 . For n = 3 a product of the sequence a 1 , a 2 , a 3 is defined as a set consisting of product elements a 1 (a 2 a 3 ) and (a 1 a 2 )a 3 . The product is denoted as {a 1 a 2 a 3 } and symbol a 1 a 2 a 3 means any product element. Generally, we can define a product of a sequence of n elements of the set A as follows [1]. Definition 4. The product of a sequence a 1 , a 2 , . . . , a n of elements a i ∈ A, i = 1, 2, . . . , n is the set {a 1 a 2 . . . a n } defined by:
for n = 2 the set {a 1 a 2 } consist of only one element a 1 a 2 , -for n ≥ 2 the set {a 1 a 2 . . . a n } is defined as
The n elements can be joined, without changing their order, in (2n−2)! n!(n−1)! 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 [8]. The mth Catalan number, for m ≥ 0 is given by:
If the operation • on the set A does not hold an associativity law, we can generally obtain distinct values a 1 a 2 . . . a n (not one common value) for all C m (m = n − 1, because Catalan numbers are numbered from 0) possible product elements of the product set {a 1 a 2 . . . a n } of the sequence a 1 , a 2 , . . . , a n .
We have tested product {q 1 q 2 . . . q k } of the sequence q 1 , q 2 , . . . , q k , where all q i ∈ 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 k } of the sequence a, a, . . . , a k . This product consists of all C k−1 product elements. Questions is, how many distinct values q 1 q 2 . . . q k = aa . . . a k = a k for all a ∈ Q we obtain. In the ideal 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 a k .
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 b 1 . . . b 8 , see Fig. 1, obtained during evaluation of product elements of a k (for k = 8, a 8 = b 8 , Fig. 1) were stored. The experiment:
-Generate a quasigroups Q of order n.
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 (Z 8 , +) 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 (Z 8 , +), of six well described quasigroups published in [13], etc.
Results are shown on the highest (8th) power of element a. There are C 7 = 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 a 8 ∈ Q. -For each a ∈ Q we obtain all 429 distinct strings b 1 . . . b 8 .
-Finally, for each quasigroup (Q, •) we ideally obtain all together 429 × 8 = 3432 distinct strings b 1 . . . b 8 for all a ∈ Q.
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 L 24 . The second quasigroup, obtained by nonaffine isotopy [13], is represented by corresponding LS L 103 . The third quasigroup is quasigroup 104 obtained by complete mapping [13] Results of the process evaluating the strings b 1 . . . b 8 : 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 b 1 . . . b 8 for each a 8 , see Figs. 2 and 3.
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.