STUDY OF QUASIGROUPS WITH CRYPTOGRAPHIC SIGNIFICANCE

Abstract

In this thesis, we study quasigroups with minimum number of associative triples. It is known the number of associative triples are connected to the security criteria of quasigroups based hash function. With the help of the permutations we implement the existing quasigroups and derive the counts on associative triples. We further evolve quasigroups with relatively small number of associative triples by using Genetic algorithm. Dr apel and Kepka [46] have shown that upper bound for associative triples of quasigroup Q isotopic to group A(Q) jQj3􀀀4jQj2+6jQj, when jQj 3 and A(Q) jQj3􀀀4jQj2+8jQj, when jQj is even, where A(Q) is the set of associative triples of quasigroup Q. Gro sek and Hor ak [64] state that best known upper bound for associative triples of any quasigroup Q is less than or equal to 2jQj2. We set a(Q) for minimum value of A(Q), they also proved that for any quasigroup a(Q) 2jQj 􀀀 jI(Q)j, where I(Q) is the set of all idempotent elements of Q. Only Kotzig and Reischer [87] provided the in nite class of quasigroups with less than jQj2. Gligoroski et al. [61] represented quasigroups as vectorial Boolean functions also called substitution boxes (S-boxes). In vectorial Boolean functions, each coordinate function is a Boolean function. First we evolve the balanced Boolean functions by Simulated annealing with best pro le (n; d; nl; ac) [31]. Markovski and Mileva [104] generated huge quasigroups from small nonlinear bijections by extended Feistel functions. Sn a sel et al. [154] also evolved huge quasigroups by Genetic algorithm which are isotopic to modular subtraction quasigroups. For given a quasigroup Q along with three bijections (i.e., permutations) on Q, we can de ne the isotopic quasigroup. We proposed a new cost function and nd the optimized permutations (i.e., isotopy) via Genetic algorithm which give the quasigroups with low number of associative triples. Markovski and Mileva [104] de ned the quasigroups via Feistel network and shown the i outcomes of Feistel network especially as relative to bijection from Fn 2 to Fn 2 . They indenti ed that Feistel network based quasigroup is highly non-associative with respective to the governing equations obtained from the associativity condition. We solve these equations for di erent kinds of permutations, i.e., linear permutations, quadratic permutations, APN (almost perfect nonlinear) permutations, di erentially 4-uniform permutations and di erentially -uniform permutations over Fn 2 and derive the counts on associative triples. Further we identify the relation between the cryptographic characterstics, i.e., nonlinearity, di erential uniformity and Strict Avalanche Criteria (SAC), of bijection mapping and Feistel network based quasigroup. Kotzig and Reischer [87] proposed the construction of quasigroups by nite commutative ring, but not necessarily associative or unitary. We implement this construction by two di erent permutations over F2n and derive the counts on associative triples which is satisfy the best known upper bound. Further we also examine how the cryptographic characterstics, i.e., nonlinearity and di erential uniformity, a ect the quasigroups and using permutations. Complete mapping permutations are used to construct quasigroups (equivalently, latin squares) which in turn show promise of being applied to design hash functions and block ciphers. Construction of complete mapping permutations by using Feistel structure has been proposed by Markovski and Mileva [104], they used the complete mapping permutations to construct huge quasigroups. Complete mapping permutations have been extensively studied in [8, 34, 93, 123, 162]. St anic a et al. [158] also used the complete mapping permutations to construct a new class of bent-negabent functions. We construct complete mapping permutations by using XS-circuits and give the total counts for particular order. We also construct K-complete mapping permutation which can be used to de ne uniformly distributed sequences. We nd a recursive constrictions that extend a complete mapping of dimension r to a complete mapping of dimension n, where r n.