Re: Constructing mxm binary matrix with optimal branch number

On Aug 16, 2:23 pm, Maaartin <grajc...@xxxxxxxxx> wrote:
On Aug 15, 2:40 pm, Tom St Denis <t...@xxxxxxx> wrote:

paper:http://eprint.iacr.org/2004/010.pdf

Here you claim that an MDS has the complexity O(n*n), is it impossible
to use a fast transform there? The multiplication by a circulant
matrix looks like a convolution, so I'd (naively) expect to be able to
transform it to multiplication.

Most MDS multiplications I've seen focus on the values for a source of
optimization, not that they're circulant. It still amounts to O(n^2)
work.

Could you point me to some paper on construction of MDS matrices? I'd
like to know something about the existence of such matrices containing
only coefficients from a given set, etc.

Honestly, I don't have anything handy, when I was working on the paper
in 2004 I had a nice archive of crypto papers.

From what I recall a sufficient condition for a matrix to be MDS is
all square sub-matrices must be non-singular. It happens that
circulant matrices tend to be MDS more than purely random ones. There
are probably better construction techniques I imagine...

AFAIU, your proof (as written) works for linear functions only, right?

Well yeah and no. The 2x2 can be non-linear provided it still has a
branch of 3 which is what the entire proof is based on, e.g. the 4x4
formed from 4 2x2s with branch of 3 [in this fasion] has a known
branch, the 8x8 and so on...

In Lemma 6 you state that "Any non-singular complete H will do" and
define
a complete function as a tuple of non-null function of every input
coordinate.
Either I misunderstood you, or I missed the meaning of "will do", or
there's something wrong with it.
Pls, consider the following function (written in C-like notation):

(x, y) -> (x ^ (y&1), (x&2) ^ y)

It is invertible (even self-inverse) and each output coordinate is a
non-null function of every input coordinate.
So it's complete, right? But it's surely a "bad function", since e.g.,
f(4, 0) = (4, 0), f(8, 0) = (8, 0).
I just don't see what good property such a function should have
according to Lemma 6.

It needs a branch of 3 [denoted by the example of a (2,3)-
multipermutation] to be considered. Your transform doesn't have a
branch of 3.

Probably I'm completelly wrong (again), but I' say you can apply the
sboxes even during the FPHT,
as long as sbox(0) = 0 (and of course the sbox is bijective).
Could you provide me a counterexample?

You can apply sboxes at every H1 composition provided H1 remains a 2,3
multipermutation the branch is known. Theorem 7 shows how to count
the branch of this transform and the analysis seems to match up with
Vaudenay's "brute force" counting of CS-Cipher.

Tom
.

Relevant Pages

  • Re: Formulae for Latin squares of size 2^n
    ... > you said something not unfavourably about Blowfish. ... From byte transform, which is of small size, we ... requirements of an MDS]. ... matrix math uses NxN and so do lookup-tables [like sboxes]. ...
    (sci.crypt)
  • Re: Formulae for Latin squares of size 2^n
    ... >> considering use of MDS. ... >> that could also serve the purpose of a transform but ... My main point is that a random transform gets closer ... There is no requirement of being circulant. ...
    (sci.crypt)
  • Re: Formulae for Latin squares of size 2^n
    ... But vastly it implies a linear function. ... Transform is a generic term, ... >> I was suggesting to use a MDS to replace a latin square. ...
    (sci.crypt)
  • Re: Formulae for Latin squares of size 2^n
    ... Make a circulant matrix out of it ... > A smarter way would be to study properties of circulant matrices to derive ... MDS for large n that is the 'real' trouble? ... why a randomly generation of transforms (one can afford ...
    (sci.crypt)
  • Re: Formulae for Latin squares of size 2^n
    ... > design consideration. ... when you say a NxN transform it means N input-coordinates. ... In the context of 32*32 S-box, ... MDS in the case of transforming 32 bits to 32 bits. ...
    (sci.crypt)
Quantcast