# Latin Squares in Cryptography

## A Ciphers By Ritter Page

So how are Latin squares used in cryptography?

### Contents

```
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?

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?

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
===========
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?
> Thanks

Subject: Re: Latin Squares
Date: Sun, 18 Mar 2001 22:16:25 +0100
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?

"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,

* "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