So how are Latin squares used in cryptography?
Subject: Re: Latin Squares Date: Sun, 18 Mar 2001 13:05:05 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <5o2t6.71117$p66.20596031@news3.rdc1.on.home.com> References: <992i2g$ij7$1@news.sovam.com> Newsgroups: sci.crypt Lines: 23 "MarinaP" <maripa@online.ru> wrote in message news:992i2g$ij7$1@news.sovam.com... > Hi, > I am not a crypto specialist, so I hope somebody here can help me. > Latin Squares are known to be widely used in cryptography. > Where are Latin Squares used in cryptography? > Where can I read about Latin Squares? Correction Latin squares are NOT known to be widely used in crypto. They are used in homebrew stuff mainly. A latin square (2d for example) is a matrix where all the rows and columns are unique such as ABCD BCDA CDAB DABC Tom
Subject: Re: Latin Squares Date: Sun, 18 Mar 2001 05:10:11 -0800 From: Jim Gillogly <jim@acm.org> Message-ID: <3AB4B3B3.EFE73A97@acm.org> References: <992i2g$ij7$1@news.sovam.com> Newsgroups: sci.crypt Lines: 10 MarinaP wrote: > Where are Latin Squares used in cryptography? > Where can I read about Latin Squares? Try Terry Ritter's treatment: http://www.io.com/~ritter/GLOSSARY.HTM#LatinSquareCombiner -- Jim Gillogly 26 Rethe S.R. 2001, 13:09 12.19.8.1.2, 9 Ik 5 Cumku, Fourth Lord of Night
Subject: Re: Latin Squares Date: Sun, 18 Mar 2001 14:26:22 -0500 From: Jim Steuert <pjsteuert@rcn.com> Message-ID: <3AB50BDE.84DC1488@rcn.com> References: <992i2g$ij7$1@news.sovam.com> Newsgroups: sci.crypt Lines: 80 Latin squares are a special case of the multipermutation idea which is pervasive in cryptography. If you consider the row as one input, and the column as another input, then by holding a row constant and varying the column, then each possible output symbol is produced. But this is also true for a lot of other tables, such as addition, bitwise xor, etc. The multipermutation idea is key in the design of good hash functions. In fact an attack on MD4 is due to the fact that the round 2 bitwise mixing function g(x,y,z) = (x and y) or (x and z) or (y and z) is not a multipermutation, so keeping two of these values (say y,z=0) at 0, makes the result g always 0, no matter what the other value x is. Because of this, the majority bitwise function was not included in MD5. (See "On the Need for Multipermutations: Cryptanalysis of MD4 and Safer" by Serge Vaudenay) In a multipermutation mixing, by setting all but one input to constant values, all output values are still possible, ie. the output is a permutation of the remaing input. Simple addition and subtraction, xor, and rotations are multipermutations. So is multiplication modulo a prime (any Galois Field), which provides a two-input multipermutation mixer of p-1 symbols (0 must be excluded). Thus multiplication works well when (2^m)+1 is prime. Addition works whether or not the modulus is prime, so addition mod 2^m is always a multipermutation. Note that multipermutations do not provide any security of themselves. They are, however, necessary to make sure that the output is a balanced function of the inputs to a cryptographic primitive function. This is a pervasive theme in cryptography. Orthogonal Latin squares, however, can provide a way of defining a keyed output nonlinear mixing functions of output 2n bits, based on two inputs of n bits each. Consider the two latin squares, and the combined square as follows: column: A B C D =========== a aD bA cB dC b cC dB aA bD c dA cD bC aB d bB aC dD cA Then the operation: mix(c,B) = (c,D) (i.e. the intersection of row c of the first table with col B of the second orthogonal table, would be a 4-bit value c,D , which would be a multipermutation. (Keeping the row constant, the output would depend on all inputs). The advantage of this over just concatenating the two input symbols (c,B) is that the output is nonlinear and keyed based on the inputs. Any Galois field of order p (p is prime) generates p-1 different orthogonal latin squares of p symbols. For example if k is a non-zero from 1 to p-1, and i is a row from 0 to p-1, and j is a column from 0 to p-1, then then L(x,y) = ((k*i)+j) mod p defines a latin square of p rows and p columns. Every different value of k defines a different orthogonal latin square. Any two of these latin squares are orthogonal, and can be used as a keyed mixer in the above sense. MarinaP wrote: > Hi, > I am not a crypto specialist, so I hope somebody here can help me. > Latin Squares are known to be widely used in cryptography. > Where are Latin Squares used in cryptography? > Where can I read about Latin Squares? > Thanks
Subject: Re: Latin Squares Date: Sun, 18 Mar 2001 22:16:25 +0100 From: "Kostadin Bajalcaliev" <kbajalc@freemail.org.mk> Message-ID: <3ab5253f@news.mt.net.mk> References: <992i2g$ij7$1@news.sovam.com> Newsgroups: sci.crypt Lines: 17 here is a link to an extensive study of Latine Sqares and their cryptographic use. http://ii.pmf.ukim.edu.mk/crypto KB MarinaP wrote in message <992i2g$ij7$1@news.sovam.com>... >Hi, >I am not a crypto specialist, so I hope somebody here can help me. >Latin Squares are known to be widely used in cryptography. > > > >
Subject: Re: Latin Squares Date: 23 Mar 2001 07:17:15 GMT From: rwb@maths.uq.edu.au (Richard Bean) Message-ID: <99et9r$i4q$1@bunyip.cc.uq.edu.au> References: <992i2g$ij7$1@news.sovam.com> Newsgroups: sci.crypt Lines: 46 "MarinaP" <maripa@online.ru> writes: >I am not a crypto specialist, so I hope somebody here can help me. >Latin Squares are known to be widely used in cryptography. >Where are Latin Squares used in cryptography? >Where can I read about Latin Squares? "Discrete Mathematics Using Latin Squares" by Laywine and Mullen, Chapter 14, covers: 14.2 encryption based upon the theory of sets of MOLS 14.3 secret sharing schemes based on critical sets 14.4 Diffie-Hellman key exchange and RSA in the group of row-Latin squares Some other crypto-related Latin squares ideas which aren't covered in the above book are found in the papers: * "DESV: A Latin square variation of DES" by Carter, Dawson, and Nielsen (Proceedings of the Workshop on Selected Areas in Cryptography, Ottawa, Canada, 1995) * "Black box cryptanalysis of hash networks based on multipermutations" by Schnorr and Vaudenay (Eurocrypt '94 pp47-57) * "Strongbox secured secret sharing schemes", by Seberry and Street (Util. Math. 57, pp147-163) * "Cryptosystems based on Latin rectangles and generalized affine spaces" by Angelo Sonnino (Radovi Matematicki 9, pp177-186) * "A new authentication scheme based on Latin squares" by Denes & Keedwell (Discrete Math. v106/107, pp157-161) * "On Golomb-Posner codes and a remark of W. W. Wu about secret-sharing schemes" (IEEE Trans. Comm. 38, pp261-262) * "Resolvable designs applicable to cryptographic authentication schemes" by Martin, Seberry and Wild (JCMCC v12, pp153-160) You can read about Latin squares in the two Denes & Keedwell books and in the Laywine & Mullen book but neither of them cover critical sets in any depth - try MathSciNet for later papers. For another angle on Latin squares try Sachkov, "Combinatorial Methods in Discrete Mathematics". There's a 1967 book by Vajda but I don't think it will have anything not in Denes & Keedwell.
Terry Ritter, his current address, and his top page.
Last updated: 2001-07-07