Re: A Question of Permutations of Vectors of Bits

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 07/31/03 

Date: Thu, 31 Jul 2003 08:38:56 +0200

Simon G Best wrote:
>
> David Wagner wrote:
> > Simon G Best wrote:
> >
> >>P is a permutation of 2n-bit vectors. x and y are 2n-bit vectors, such that
> >> y = x + P(x)
> >>(where '+' is bitwise-xor). P is easily invertible.
> >>
> >>What I'm interested in right now are general approaches to solving for x
> >>when y and P are known. In particular, I'm interested in general
> >>solutions that take less than 2^n steps (a step being comparable to
> >>trying a single guess for x, and seeing if it works).
> >
> > By permutation, I assume you mean a re-ordering of the bits. Right?
> >
> > A big hint: permutations are linear.
> >
> > Solution follows:
> >
> >
> >
> > A solution:
> >
> > If P is known, you can just use linear algebra. y is a linear function
> > of x, hence given y you can write 2n linear equations in 2n unknowns (the
> > unknowns are the bits of x) and then solve using Gaussian elimination.
> > There are probably better ways, but this runs in O(n^3) time, which
> > ought to be good enough.
>
> Sorry, I worded it badly (horrendously badly). (How embarassing!) I
> meant a bijective mapping of 2n-bit vectors to 2n-bit vectors; a
> permutation such as a block cipher's encryption function with a
> particular key. But thanks for taking the time to answer :-)

In the first post you said that P is known and is
easily invertible. Your second post said that P is
like a block cipher with a particular key, implying
(in my understanding) that P is unknown to the person
solving the question, right? So, after all, is P 'known'
(i.e. a given particular permutation, fully written out)
or not? Please kindly clarify.

M. K. Shen