Re: Formulae for Latin squares of size 2^n

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 12/21/03 

Date: Sun, 21 Dec 2003 20:45:03 GMT

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message
news:3FE60064.53A13883@t-online.de...
> We were even on the issue of 128*128 transform, which
> evidently is to be understood on the basis of 128 bits
> (cf. size of most current block ciphers.)

Since when? The original thread started off talking about making latin
squares. It had nothing todo with specific sized block ciphers.

> > The 32x32 sbox was to show that yes big can be better [isn't always] but
> > this infers a cost. A 32x32 linear transform [unless it's reducible]
will
> > be very inefficient.
>
> In the context of 32*32 S-box, a 32*32 transform
> clearly implies transforming 32 bits to 32 bits
> and not in terms of other units (also there has
> been no alternate units (groups of bits) mentioned
> ever).

You ought to brush up on your high school algebra then. You clearly don't
know what you are talking about.

The 32x32 for sboxes comes from hardware engineering [e.g. ROM tables].
32x32 transform implies a linear transform which would imply 32 input
co-ordinates and 32 output co-ordinates.

> > > But a random 32 bit to 32 bit linear transform can be via
> > > a 32*32 matrix with entries of one bit.
> >
> > Yes it can. So what? That's not what we were talking about. Even
still
> > random 32x32s are not efficient for say hardware and embedded platforms.
> > They're likely to have low branch, diffusion, etc..
>
> We have always been talking about alternatives to
> MDS in the case of transforming 32 bits to 32 bits.
> (I mean by alternatives random linear transforms.)

That's just it. No we haven't. When I posted

http://groups.google.ca/groups?dq=&hl=en&lr=&ie=UTF-8&oe=UTF-8&frame=right&rnum=31&thl=995973575,995973082,995540697,995525525,994019880,993922345,993747179,993722536,993184907,993064814,944687428,944677878&seekm=CbwBb.939%24kr2.404%40news01.bloor.is.net.cable.rogers.com#link31

[long I know...]

I was suggesting to use a MDS to replace a latin square.

> > Because ROM and RAM are different things? Because fixed transforms are
more
> > efficient in hardware [hint: Why doesn't MPEG specify a KL transform?].
>
> But it is the size that is the issue! Where does the
> figue 1KB come from? I don't yet see clearly.

I was under the impression the elements were GF(2^8). A 32x32 over GF(2)
would require 128 bytes of ram which is still excessive when you consider
that ciphers like AES can be implemented in roughly 50 bytes of ram
[including the input block, key and temporaries required].

> How many bits are there in total in your 4*4 MDS
> and how many bits are there in my 32*32 matrix with
> 1-bit entries? Aren't they equal?

A 4x4 over GF(2^8) requires exactly 16 bytes [or octets if you prefer]. A
32x32 has 64 times more entries but they are 1/8th the size [16*8 = 128].

Even still I'm talking about fixed transforms so my 16 byte 4x4 can be in
code ROM and not waste RAM.

> > First off, MDS matrices don't exist over GF(2) at all. So if you are
saying
> > 32x32 matrix you must mean GF(2^w) for w > 1. So what do you truly
mean by
> > 32x32? [Where did 32x32 come from anyways?]
>
> I think you are pretending to not to know the context.
> See above for the 32-bit context.

Ok, question. Why are you doing transforms over GF(2) at all? Your
approach is not hardware friendly and much better techniques already exist.
If you want to mix 32-bits why not use a 4x4 over GF(2^8)? It's easier to
implement in software, can be done 4 times faster [even if the 4x4 is
random], etc, etc, repeat....

> > Or we could do it your way. Make a random NxN, take N^2 time to
implement
> > [as opposed to NlogN for the FFT] be inefficient in software/hardware
and
> > have no bounded properties concerning security. I guess I can see how
your
> > idea is a good one. If say, the goal was complete and utter lack of
> > security.
>
> Ah, you yourself said something about the difficulty
> of computing large MDS matrices, didn't you? If you
> could tell that an MDS to transform 32 bits to 32 bits
> is doable with moderate resources, then we could
> end our debate.

Um over what word size? Want a 4x4 MDS over GF(2^8)? That's trivial use
this

[1 1 2 3]
[1 2 3 1]
[2 3 1 1]
[3 1 1 2]

Over any GF(2^8)[x]/v(x) [using cannonical [sp?] notation] for any
irreducible v(x).

Voila. That's not hard.

Furthermore I said FINDING large MDS transforms is hard. Computing them is
a n^2 process [or if you use tables much quicker]. For example, a 32x32 MDS
can be computed [over GF(2^8)] with an x86 [using SSE] by using a circulant
MDS and two 16x16 MDS tables [each table has 16 arrays each with 256
elements of 16 bytes or 16*16*256 = 64KB so the entire table takes 128KB].
Such a MDS would take 64 lookups and 60 XORs to compute.

Though for such a huge size I'd use a FFT like network [wicked fast in
hardware].

> > One thing I've gathered from this is that you're not a CS student at
all.
> > If you were you'd know that a lot of pre-computation to save time at
runtime
> > is time well spent. [hint: this is why compilers have optimizers and
why
> > Athlon cpus consume 70W of power].
>
> Nothing against precomputation in this context, if
> a 32-bit to 32-bit MDS could be practically done.
> I said previously that what you argued is that a random
> matrix isn't likely to be the (theoretically) optimal
> one, which is trivial in almost all computating
> situations where optimization is required (right?).

Is finding a random non-singular transform easy? In fact you can use an LR
computation and find one in constant time [hint make all 1's in the
diagonals and multiply]. Is finding a random non-singular and
cryptographically usefull transform easy? Not really, at least not in
constant time.

> As to my thought about random transforms could compare
> favourably with optimal ones when the size is large,
> that comes from something I once read (but I admit
> I don't understand much of it) claiming that in coding
> theory a random code is about as good as the best
> codes when the block size is large.

I don't think this is true at all. It's quite easy to imagine random
transforms [specially over GF(2)] being particularly weak. For instance,
you have about a 2^-27 chance of making a random 32x32 over GF(2) where at
least one bit is disjoint. In fact if you enumerate all the matrices of 5x5
over GF(2) that fails one of the following condition you will probably be
surprised

- Disjoint bits [e.g. doesn't affect other bits]
- Sparse rows [less than half bits set]
- Low branch [branch less than N for NxN is bad]

Tom

Relevant Pages