=Paper=
{{Paper
|id=None
|storemode=property
|title=Testing Quasigroup Identities using Product of Sequence
|pdfUrl=https://ceur-ws.org/Vol-567/poster24.pdf
|volume=Vol-567
|dblpUrl=https://dblp.org/rec/conf/dateso/OchodkovaDSA10
}}
==Testing Quasigroup Identities using Product of Sequence==
https://ceur-ws.org/Vol-567/poster24.pdf
Testing Quasigroup Identities using Product of
Sequence
Testing Quasigroup Identities using
Product of Sequence?
Eliška Ochodková1 , Jiřı́ Dvorský1 , Václav Snášel1 , Ajith Abraham2
Eliška Ochodková1 ,1 Jiř ı́ Dvorský1of, Václav
Department ComputerSnášel1
Scienceand Ajith Abraham2
Faculty of Electrical Engineering and Computer Science
1
VŠBDepartment
– TechnicalofUniversity
ComputerofScience
Ostrava
FEECS,15,
17. listopadu VŠB
708– 33
Technical
OstravaUniversity
– Poruba, of Ostrava
Czech Republic
17. listopadu 15, 708
{eliska.ochodkova, 33 Ostrava – Poruba,
jiri.dvorsky, Czech Republic
vaclav.snasel,}@vsb.cz
{eliska.ochodkova,
2 jiri.dvorsky,
Center of Excellence forvaclav.snasel,}@vsb.cz
Quantifiable
Quality of Service, Norwegian
2 University of Science and Technology
Center of Excellence for Quantifiable,
O.S. Bragstads
Quality plass 2E,
of Service,
NorwegianN-7491 Trondheim,
University Norway
of Science and Technology
ajith.abraham@ieee.org
O.S. Bragstads plass 2E,
N-7491 Trondheim, Norway
ajith.abraham@ieee.org
Abstract. 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 [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 genera-
tors [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-34 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
3
http://www.ecrypt.eu.org/stream/
4
http://csrc.nist.gov/groups/ST/hash/sha-3/
?
This paper was partially supported by GACR 205/09/1079 grant.
J. Pokorný, V. Snášel, K. Richta (Eds.): Dateso 2010, pp. 155–162, ISBN 978-80-7378-116-3.
156 Eliška Ochodková, Jiřı́ Dvorský, Václav Snášel, Ajith Abraham
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 look-
up 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 Preliminaries
2.1 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 [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 (Q, ◦) is
of order n if |Q| = n.
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.
Testing Quasigroup Identities using Product of Sequence 157
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].
Definition 3. Let (Q1 , ·) and (Q2 , ◦) be two quasigroups with |Q1 | = |Q2 |. An
ordered triple (α, β, γ) of one-to-one mappings α, β, γ of the set Q1 onto the set
Q2 is called an isotopism of Q1 upon Q2 if α(x)◦β(y) = γ(x·y) for all x, y ∈ Q1 .
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 trans-
formations [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 = q1 q2 . . . 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) = b1 b2 . . . 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) = c1 c2 . . . 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 = El1 l2 ...lk = el1 • el2 • . . . • elk (3)
and
Dk = Dl1 l2 ...lk = dl1 • dl2 • . . . • dlk (4)
are said to be E− and D−transformations of Q respectively. In the last nota-
+
tion, 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 e-
transformations 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 quasi-
groups 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 analog-
ical tests described in Sec. 3.
158 Eliška Ochodková, Jiřı́ Dvorský, Václav Snášel, Ajith Abraham
3 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 a1 a2 . For n = 3
a product of the sequence a1 , a2 , a3 is defined as a set consisting of product
elements a1 (a2 a3 ) and (a1 a2 )a3 . The product is denoted as {a1 a2 a3 } and sym-
bol a1 a2 a3 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 a1 , a2 , . . . , an of elements ai ∈ A, i =
1, 2, . . . , n is the set {a1 a2 . . . an } defined by:
– for n = 2 the set {a1 a2 } consist of only one element a1 a2 ,
– for n ≥ 2 the set {a1 a2 . . . an } is defined as
{a1 a2 . . . an } = {a1 }{a2 . . . an } ∪ {a1 a2 }{a3 . . . an } ∪ . . . ∪ {a1 . . . an−1 } ∪ {an }.
(2n−2)!
The n elements can be joined, without changing their order, in 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:
(2m−2)!
Cm = m+11
m = m!(m−1)! .
2m
If the operation ◦ on the set A does not hold an associativity law, we can
generally obtain distinct values a1 a2 . . . 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 {a1 a2 . . . an } of the sequence a1 , a2 , . . . , an .
3.1 Experiment
We have tested product {q1 q2 . . . 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.
| {z | {z }
k k
This product consists of all Ck−1 product elements. Questions is, how many
distinct values q1 q2 . . . 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.
Testing Quasigroup Identities using Product of Sequence 159
– 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 ... a a
? ? ? ?
a b1 b2 ... b7 b8 = a8
Fig. 1. e-transformation used for valuing the product elements ak , k = 8
3.2 Quasigroups used in tests
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 [13], etc.
3.3 Ideal results
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 Experimental results
Results of experiments are shown on the set of five chosen quasigroups repre-
sented by their corresponding LSs. The first quasigroup is randomly generated
quasigroup No. 24 represented by L24 . The second quasigroup, obtained by non-
affine isotopy [13], is represented by corresponding LS L103 . The third quasi-
group is quasigroup 104 obtained by complete mapping [13] and represented
160 Eliška Ochodková, Jiřı́ Dvorský, Václav Snášel, Ajith Abraham
by LS L104 . The fourth quasigroup is quasigroup No. 106, from [13], is repre-
sented by LS L106 . The last quasigroup (Q1 , ◦) with No. 107 is represented by
corresponding LS L107 (this quasigroup is the additive group (Z8 , +)).
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.
Table 1. Number of obtained distinct values of a8 for each a ∈ Q
L24 L103 L104 L106 L107
8
0 8 8 8 8 1(08 = 0)
8
1 8 8 8 1 1(18 = 0)
28 8 8 8 2 1(28 = 0)
8 8
3 8 1(3 = 3) 8 3 1(38 = 0)
8
4 8 8 8 4 1(48 = 0)
8
5 8 8 8 2 1(58 = 0)
8
6 8 8 8 2 1(68 = 0)
8
7 8 8 8 2 1(78 = 0)
Table 2. Number of obtained strings b1 , . . . , b8 for all a ∈ Q
L24 L103 L104 L106 L107
number of strings 2426 2019 2666 664 307
number of AT 72 70 60 304 512
3.5 Visualization of strings b1 , ..., bn valuation
We have focused only on the 8th power of quasigroups elements. For each quasi-
group (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 quasi-
group 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
Testing Quasigroup Identities using Product of Sequence 161
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.
(a) 08 (b) 18 (c) 28 (d) 38
(e) 48 (f) 58 (g) 68 (h) 78
Fig. 2. Quasigroup No. 104
4 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 possi-
ble 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.
References
1. O. Borůvka. Foundations of the theory of groupoids and groups. Wiley, 1976.
2. J. Dénes, and T. Dénes. Non-associative algebraic system in cryptology. Protection
against ”meet in the middle” attack. Q. and Related Systems 8 (2001): 7–14.
162 Eliška Ochodková, Jiřı́ Dvorský, Václav Snášel, Ajith Abraham
(a) 08 (b) 18 (c) 28 (d) 38
(e) 48 (f) 58 (g) 68 (h) 78
Fig. 3. Quasigroup No. 107
3. J. Dénes, and A. Keedwell. Latin Squares and their Applications. New York:
Akadémiai Kiadó, Budapest, Academic Press, 1974.
4. D. Gligoroski, et al. EdonR cryptographic hash function. NIST’s SHA-3 hash func-
tion competition, 2008, http://csrc.nist.gov/groups/ST/hash/sha-3/index.html
5. D. Gligoroski, S. Markovski, L. Kocarev, and J. Svein. The Stream Cipher Edon80.
The eSTREAM Finalists, LNCS 4986 (2008): 152–169.
6. D. Gligoroski. One-Way Functions and One-Way Permutations Based on Quasi-
group String Transformations. Cryptology ePrint Archive. Report 2005/352.
7. D. Gligoroski, and S. Markovski. Cryptographic potentials of quasigroup transfor-
mations. Talk at EIDMA Cryptography Working Group, Utrecht, 2003.
8. P. Hilton, and J. Pedersen. Catalan Numbers, Their Generalization, and Their
Uses. Journal The Mathematical Intelligencer, 13, no. 2 (1991): 64–75.
9. C. Kościelny. NLPN Sequences over GF(q). Quasigroups an Related Systems 4
(1997): 89–102.
10. S. Markovski, D. Gligoroski, and J. Markovski. Classification of quasigroups by
random walk on torus. J. of Appl. Math. and Comp. 19, no. 1-2 (2005): 57–75.
11. S. Markovski, D. Gligoroski, and L. Kocarev. Unbiased Random Sequences from
Quasigroup String Transformations. in 12th International Workshop FSE, Paris,
LNCS 3557 (2005): 163.
12. S. Markovski, D. Gligoroski, and V. Bakeva. Quasigroup and Hash Functions.
Disc. Math. and Appl., In Proceedings of the 6th ICDMA, Bansko, 2001.
13. K. A. Meyer. A new message authentication code based on the non-associativity
of quasigroups. Ph.D Thesis, 2006,
http://orion.math.iastate.edu/dept/thesisarchive/PHD/KMeyerPhDSp06.pdf
14. B. D. McKay, and I. M. Wanless. On the Number of Latin Squares. Journal Annals
of Combinatorics 9, no. 3 (2005): 335–344.
15. E. Ochodková, and V. Snášel. Cryptographic Algorithms with Uniform Statistics.
In NATO Regional Conference on Military Communications and Informations Sys-
tems Zegrze, Poland: 165–172, 2001.
16. K. Toyoda. On axioms of linear functions. P roc. Imp. Acad. Tokyo, 17 (1941):
221–227.