Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/staff/vnosov/latin_squares.pdf Дата изменения: Mon Mar 16 02:14:05 2009 Дата индексирования: Mon Oct 1 22:26:24 2012 Кодировка:

Nosov Valentin A. (Moscow State University) Constructing a Parametrical Families of Latin Squares in the Bo olean Database. Abstract.
In this article the construction of parametric classes of Latin Squares over Bo n-vectors is demonstrated so that these Latin Squares are represented in analytical by families of Boolean functions. This construction leads to the new property of Bo functions which is named property. We deduce some classifying results about these ilies of functions. olean form olean fam-

Intro duction.
Latin Squares are important ob ject of Mathematics and Cryptology and have numerous applications in cryptographic practice. Ciphers on Latin Squares according to theory of C. Shannon [4] are so called perfect. But in most ciphering standards Latin Squares are not changeable and changeability of Latin Squares in ciphering system may raise the level of information security. There are many directions of research in the theory of Latin Squares and the main part of it is the modes of constructing classes of Latin Squares under some conditions. Practical adaptation of Latin Squares in computer ciphering systems requires them to have large dimension and to be changeable. Therefore there is necessity to determine Latin Square analytically and parametrically by functions of two variables, that determines element of square by number of row and column. Latin Square over set S is the table of dimension n в n, where n = S , consisting from elements of S, so that in each row and column all elements are different. There are many applications of Latin Squares in coding theory and cryptology ([4], [5]). In the literature there are many modes of constructing of Latin Squares in table form and this detail is an obstacle to the applications in the case of large n = |S |. The aim of this paper is the presentation some results relating to parametric families of Latin Squares over set S where S is set of Bo analytic form. When element of square is determined by function on column. Also we have some classifying results relating to the form of the construction of olean n--vectors in number of row and these functions.

Let En -- the set of binary vectors of dimension n. In this case Latin Square over set En may be determined by family of n Boolean functions f1 (x1 , . . . , xn , y1 , . . . , yn ) f2 (x1 , . . . , xn , y1 , . . . , yn ) ... fn (x1 , . . . , xn , y1 , . . . , yn )

(1)

of 2n variables, where x1 , . . . , xn determins the number of row, y1 , . . . , yn -- the number of column, meaning of functions f1 , . . . , fn determines corresponding element of square. By using results about the regularity of families boolean functions [6] it is easy to prove 1


Theorem 1 The family of n Boolean functions f1 , . . . , fn with 2n variables x1 , . . . , xn , y1 , . . . , yn determines the Latin Square if and only if, when in al l products fi1 , . . . , fik , 1 i1 < . . . < ik n, k < n canonical polynome don't contains terms, including x1 . . . xn or y1 . . . yn , but product f1 . . . fn contains both this terms and no other terms containing them. This proposition does not give the effective mode of constructing necessary functions but may be useful for finding sufficient conditions for solving this question. Let us consider the mode of introduction the parameter in the family of Latin Square. Let we have the family of Boolean functions g = (g1 (z1 , . . . , zn ), . . . , gn (z1 , . . . , zn )) with n variables z1 , . . . , zn . Let 1 (x1 , y1 ), . . . , n (xn , yn ) (3) (2)

-- system of Boolean functions with two variables. Let system of Boolean functions f1 , . . . , fn with 2n variables x1 , . . . , xn , y1 , . . . , yn is defined by relations: f1 = x1 + y1 + g1 (1 (x1 , y1 ), . . . , n (xn , yn )) f2 = x2 + y2 + g2 (1 (x1 , y1 ), . . . , n (xn , yn )) ... fn = xn + yn + gn (1 (x1 , y1 ), . . . , n (xn , yn )) (4)

Let us remind the definition from the article [1]. The family of Boolean functions g = (g1 , . . . , gn ) is named proper, if for all distinct n--collections of variables z = z1 , . . . , zn and z = z1 , . . . , zn exists 1, n such that next relation is hold z = z , g (z1 , . . . , zn ) = g (z1 , . . . , zn ) (5)

Theorem 2 The system of Boolean functions f1 , . . . , fn as (4) determines the Latin Square for any functions of two variables 1 , . . . , n if and only if when the family of functions g = (g1 , . . . , gn ) is proper. Proof.Let the functions 1 , . . . , n with two variables exist and family of functions f1 , . . . , fn , defined by (4), does not determine the Latin Square. Then we have f f
1

x1 , . . . , x n , y 1 , . . . , y x1 , . . . , x n , y 1 , . . . , y

n

n

n

=f ... =f

1

x1 , . . . , x n , y 1 , . . . , y

n

(6)
n

n

x1 , . . . , x n , y 1 , . . . , y
n

for certain x1 , . . . , xn , x1 , . . . , xn , y1 , . . . , yn , where x1 , . . . , x f
1

= x1 , . . . , xn , or
n

x1 , . . . , x n , y 1 , . . . , y

n

fn x1 , . . . , xn , y1 , . . . , y

n

=f ... =f

1

x1 , . . . , x n , y 1 , . . . , y

(7)

n

x1 , . . . , x n , y1 , . . . , y
n

n

for certain x1 , . . . , xn , y1 , . . . , yn , y1 , . . . , yn , where y1 , . . . , y hold, then using (4) we get equations

= y1 , . . . , yn . Let (6) is

x1 + g1 (1 (x1 , y1 ), . . . , n (xn , yn )) = x1 + g1 (1 (x1 , y1 ), . . . , n (xn , yn )) ... xn + gn (1 (x1 , y1 ), . . . , n (xn , yn )) = xn + gn (1 (x1 , y1 ), . . . , n (xn , yn )) 2

(8)


Let us put the signings z = z1 , . . . , zn , where zi = i xi , yi , i = 1, n and z z1 , . . . , zn , where zi = i xi , yi , i = 1, n and consider the pair gz gz =g
1

=

z

,...,g

n

z z

= g1 z

,...,g

n

If for all 1, n is hold g z = g z , then the condition of property for family g = (g1 , . . . , gn ) is not hold on pair z and z . If exists 1, n, such, that g z = g z is hold then from relation (8) we get x = x . And then x , y = x , y so we have z = z . Consequently in this case the condition of property of family g1 , . . . , gn is not hold on pair z and z " . The case (7) is proved by similar way. So we have if system of functions (4) does not determine the Latin Square for any functions 1 , . . . , n then the family g1 , . . . , gn is not proper. Let now the family g1 , . . . , gn is not proper. This means that exists pair of variables z = z1 , . . . , zn and z = z1 , . . . , zn , such that for all 1, n with condition z = z we have g z = g z . Let us consider any x1 , . . . , xn and y1 , . . . , yn . Consider the pair x1 , . . . , xn and x1 , . . . , xn , where xi = xi + gi z , i 1, n ... xi = xi + gi z , i 1, n Now determine the functions 1 , . . . , n so that is hold i xi , y
i

(9)

i xi , yi

= zi , i 1, n ... = zi , i 1, n

(10)

This is impossible only in the case when xi = xi , but zi = zi" for some i 1, n. But if xi = xi , then from (9) we have gi z = gi (z ) and with condition on z and z we have zi = zi . Now it is easy to see from (4), that elements of the square corresponding x1 , . . . , xn , y1 , . . . , yn and x1 , . . . , xn , y1 , . . . , yn equal (x1 , . . . , xn ), and the square (4) is not Latin for given functions 1 , . . . , n . Remark 1 The notion of property for family Boolean functions was introduced in [1] in connection of study regularity (substitution property) of boolean automata. There it is proved fol lowing criteria. Theorem 3 A family of Boolean functions f1 , . . . , fn with variables x1 , . . . , xn is proper if and only if when in al l products fi1 . . . fik there are not terms xi1 . . . xik in corresponding canonical polynoms. Let us consider the connection of proper and regular families of Boolean functions. It is easy to prove Theorem 4 A family of Boolean functions f = (f1 , . . . , fn ) is proper if and only if when the family g1 , . . . , gn , where gi = ai fi + xi for al l constant ai , is regular, i = 1, n.

3


Now we give some classifying results about the proper families functions. For effective application of this construction of Latin Squares we need to describe some classes of proper families of Boolean functions. For any families functions f = (f1 , . . . , fn ) of variables x1 , . . . , xn define the oriented graph Gf of essential variable as Gf = (V , E ), where V = {1, . . . , n}, (i, j ) E when variable xi is essential for fj . It is easy to see that if Gf = (V , E ) has no cycles then the family f = (f1 , . . . , fn ) is proper. Inverse assertion is not true. Let us consider the family f = (f1 , . . . , fn ) where f1 = (x2 + 1)x3 . . . xn ... fn = (x1 + 1)x2 . . . xn-1 (11)

It is easy to see that graph Gf , is complete but the family f = (f1 , . . . , fn ) is proper. Let M be class multyaffine functions. That is every function f M is conjunction of lineal functions. Let f is the family of multyaffine functions. This means that f = (fi i 1, n) may be presented as f1 = f2 =
k
1

i=1 k2 i=1 k
n

1 li (x1 . . . xn ) 2 li (x1 . . . xn )

...
n li (x1 . . . xn )

(12)

fn =

i=1

t where ki i 1, n -- number of linear functions in fi , and li = at x1 + . . . + at xn + bt -- 1 n lineal function over the field F2 , 1 t n. Define oriented graph G0 of entering variables f in family f , by putting

G0 = (V , E ) f

(13)

j where V = {1, 2, . . . , n}, (i, j ) E s | the function ls contains xi (that is aj = 1). s

Remark 2 The graph G0 of entering variables contains as subgraph graph Gf of essenf tiality variables of family f . Designing of graph G0 is simple, designing of graph Gf is f N P --hard problem for many classes of functions ([2]). The cycle for which no proper subset of vertexes do not contain cycle we will name as simple. Theorem 5 The family of multyaffine functions f = (fi ) i 1, n, is proper if and only if when for every simple cycle C of the graph of entering variables G0 of family f is hold f fi (x1 , . . . , xn ) 0
iC

(14)

Proof.Let the simple cycle C of the graph Gf exists and condition (14)is not hold, that is fi (x1 , . . . , xn ) = 0 (15)
iC

4


Let C = i1 , . . . , is , ik 1, n. This means that function fi1 contains entering variable xi2 and does not contain entering variables xi1 , xi3 , . . . , xis Similarly it is true about functions fi2 , . . . , fis . The functions fi1 , . . . , fis may be presented as fi1 = (. . . + xi2 + . . .) . . . (. . . + xi2 + . . .)i1 (x1 , . . . , xn ) ... fis = (. . . + xi1 + . . .) . . . (. . . + xi1 + . . .)is (x1 , . . . , xn )

(16)

here i1 --multyaffine function, not containing the entering xi2 . Similarly, is --multyaffine function, not containing the entering xi1 , multipliers by i1 are linear functions, containing entering xi2 , multipliers by is are linear functions, containing entering xi1 . According to fi (x0 , . . . , x0 ) = 1. Consequently (15) there is n--collection x = (x0 , . . . , x0 ), such that n 1 n 1 we have f
i1 iC

x0 , . . . , x 1

0 n

= ... = f

is

x0 , . . . , x 1

0 n

=1

(17)

Let us consider collection x = x0 , . . . , x01 , . . . , x0s , . . . , x0 , which is took from x = ~ Їi Їi 1 n (x0 , . . . , x0 ) by negotiating of variables with indexes from C . 1 n Then from (16) we conclude that it is hold fi1 (x) = fi2 (x) = . . . = fis (x) = 0 ~ ~ ~ (18)

From (17) and (18) we see that family f is not proper if we take two collections x = (x0 , . . . , x0 ) and x = x0 , . . . , x01 , . . . , x0s , . . . , x0 . Conversely, let for any simple cycle C ~ Їi Їi 1 n 1 n 0 of graph Gf the relation (14) is hold. For family f = (fi ) i 1, n let us consider the family f = fi i 1, n, where f (x1 , . . . , xn ) = xi + fi (x1 , . . . , xn ), i 1, n. (19)

Let I i 1, n -- the set of indexes, I = ( ), I , {0, 1} -- family of constants. For any function g = (g1 , . . . , gn ) we put g I (xi , i C I ) = g( x1 , . . . , xn ) |
x = ,I

That is the variables with indexes from I are substituted by constants I , C I --the complement I in i 1, n. It is proved (see.[1], Lemma 2), that f is proper family if and only if when the family f I = fiI , i C I is regular for all I = 1, n and all I . For proving regularity any family of Boolean functions g = (g1 , g2 , . . . , gn ) with variables x1 , x2 , . . . , xn we will use criteria of Huffman (see. [6]), according to which the family g = (g1 , g2 , . . . , gn ) is regular if and only if when for any indexes i1 , i2 , . . . , ik , k n - 1 the product gi1 gi2 . . . gik does not contain term x1 x2 . . . xn in canonical polynom, but the product g1 g2 . . . gk contain this term. Let the set I is empty. Prove the regularity of family f = fi i 1, n We have f1 . . . fn = x1 . . . xk +
ip1

x

i j p2

f

j

(20)

Summation over all partitions (p1 , p2 ) the set i 1, n, where p2 = 0. Prove that xi fj for all (p1 , p2 ), p2 = 0 does not contain the term x1 x2 . . . xn . If on the
ip1 j p
2

5


contrary for any (p1 , p2 ), p2 = 0 there is the term x1 x2 . . . xn , then it is hold fj = 0 if j p2 and fj (x1 . . . xn ) contains term xj .
j p2 j p2

Let us consider subgraph Hf (p2 ) of the graph Gf , which contains the vertexes of the set p2 . By the definition we have that from every vertex goes out at least one edge. It is easy to see that in this case Hf (p2 ) contains the simple cycle C and by the condition we must have fj (x1 . . . xn ) = 0
j C

But the set p2 contains the vertexes C as subset. Consequently we have
j p
2

fj (x1 . . . xn )

0. Then the term
ip1

x

i j p2

fj if p2 = 0 does not contain the term x1 x2 . . . xn and there-

fore, by (20) the product f1 . . . fn contains such term. Let now such k < n and indexes 1 i1 < . . . < ik n exist that product fi1 . . . fik contains the term x1 x2 . . . xn . We have fi1 . . . fik = xi1 xi2 . . . xin +
ip1

x

i j p2

f

j

(21)

Summation over all partitions (p1 , p2 ), p2 = 0 the set i1 , i2 , . . . , ik . This means that exists the partition (p1 , p2 ), p2 = 0, such that the term xi fj contains the term x1 x2 . . . xn .
ip1 j p2

Consequently the term
j p2

fj contains the term
iC p
1

xi , where C p1 is the complement

of the set p1 in 1, n. Consider the subgraph Hf (p2 ) on vertexes of the set p2 . Since the functions with indexes from the set p2 give the term xi then by the definition of the
iC p

graph Gf from each vertex of C p1 at least one edge goes out with the end in p2 . By the condition we have p2 C p1 and therefore the graph Hf (p2 ) contains the cycle. Then we have the consequence fj (x1 . . . xn ) 0 and the term x1 x2 . . . xn does not appear in (21). Hence it is proved that the family f1 . . . fn is regular according to Huffman's criteria. Let I 1, n--strictly subset, I --arbitrary family of the constants. Regularity of the family f I = (f I ) , i C I (with variables xi , i C I ) may be proved by the similar arguments. This is possible because by the substitution the variables by the constants the multyaffine function is also multyaffine and the condition (19) is hold by substitution of variables with the constants. Now we give recursive mode constructing the proper families of functions. Let there is the family f functions with variables zi0 , . . . , zin . Define family of n + s1 + . . . + sn functions f = (fij ) with variables zij , i = 1, . . . , n, j = 1, . . . , si (s1 , . . . , sn --any natural numbers 0) by relations fi1 = i1 (fi0 , xi0 ) fi2 = i2 (fi0 , xi0 , zi1 ) ... fist = ist (fi0 , xi0 , zi1 , . . . , zist-1 ) fi0 = i0 (fi0 , xi0 , zi1 , . . . , zist ) i0 , i1 , . . . , ist --any functions with corresponding (22) variables. Theorem 6 If the family f is proper, then the family f is proper also for any functions ij , i 1, n, j 0, st . 6
j p
2

1

(22)


Pro of. Let the family f is not proper. Hence there is the pair of distinct collections z = zij , i 1, n, j 0, st , and z = zij , i 1, n, j 0, st such that for all , , when z = z we have f (z ) = f (z ). There are two events: 1. z0 = z0 , where z0 = z10 , . . . , zn0 , z0 = z10 , . . . , zn0 By the definition for family f0 = f10 , . . . , fn0 there is 1, n, such that z0 = z0 and f0 (z ) = f0 (z ). From relations (22) we get that f1 (z ) = f1 (z ) and accordingly the presumption about family f we get z1 = z1 . Again from relations (22) we get f2 (z ) = f2 (z ) and therefore we have z2 = z2 . The prolongation gives to us the relation zst = zst and from (22) we get the relation f0 (z ) = f0 (z ) and hence z0 = z0 , what contradicts the condition of . 2. z0 = z0 . In this case from relations (22) we have fi1 (z ) = fi1 (z ) for all i 1, n. By the presumption about family f we have zi1 = zi1 for all i 1, n. Now from (22) we have fi2 (z ) = fi2 (z ) for all i 1, n. This implies zi2 = zi2 for all i 1, n. The prolongation gives to us that zist = zist for all i 1, n and consequently z = z . This contradicts the choice the pair z , z . This proves that the family f is proper.

Remark 3 Some generalizations of demonstrated facts for families functions over Abelian groups are presented in paper [3].

Conclusion.
The construction of parametric family of Latin Squares in analytic form and arbitrary large size is presented. This construction is based on some property of families functions named proper family. For this property some classifying and constructing results are demonstrated. Application of these results to the ciphering system may get the changeable Latin Square in them and to be fit for long data. These applications may guarantee more high level of information security.

References
[1] Nosov V.A. Criterion of regularity of nonautonomous boolen automat with separate input. Intellectual Systems. v-3, n. 3-4,1998,269-280 p. [2] Alekseev V. B., Nosov V.A. NP-full problems and their polynomial versions. Review. Review of industry and applied math., 1997, v. 4, n. 2, 165-193 p. [3] Nosov V.A., Pankratiev A.E. Latin squares over abbelian groups. Fundamental and applied math., v. 12, n. 3, 2006, 65-71 p. [4] Shannon C. Communication theory of secrecy system, Bell System Techn. J.,28,Number 4,(1949),656-715 p. [5] Denes J., Keedwell A.D. Latin squares and their applications, Budapest,1974, 547 p. [6] Huffman D.A. Canonical forms for information lossless finite-state logical machines. IRE Trans. Circ. Theory, 1959, v.6, p.41-59. 7


[7] Kloss B.M., Malishev V.A. Determination of regularity of automat using his canonical equations. Report. The Academy of Science Of The USSR. 1967., v. 172, n. 3, 543-546 p.

8