On compressibility of random permutations
in [Cryptography]
|
From: Herbert Paulis on 22 Jan 2010 01:53 "Peter Fairbrother" <zenadsl6186(a)zen.co.uk> schrieb im Newsbeitrag news:4b579f55$0$2479$db0fefd9(a)news.zen.co.uk... > [snip] > Statistically, some actual numbers may not be be so defineable - but then > we can define them as the first non-Kolgogorov-random number, and so on. > > It's a pretty concept - but in real life there is no such thing as a > Kolmogorov-random number. Can you explain that statement in detail, please? I'd like to know the arguments why you thimk in RL there is no Kolmogorov random numer. regards Herbert
From: WTShaw on 22 Jan 2010 08:36 On Jan 21, 12:26 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote: > In article <TaY5n.7308$ZN1.5...(a)newsfe05.iad>, > > Joseph Ashwood <ashw...(a)msn.com> wrote: > >"Peter Fairbrother" <zenadsl6...(a)zen.co.uk> wrote in message > >news:4b576ab4$0$2532$da0feed9(a)news.zen.co.uk... > >> In general there is the idea that random permutations, or sequences, are > >> not compressible. > > >Actually permutations are compressible. Labeling each permutation with an > >integer, significantly abbreviated the permutation. As an example take AES, > >the key can be trivially converted to an integer, and serves as such an > >index. Using that index as the key to AES in CTR mode will restore the > >permutation. For a complete permutation set of all 128-bit blocks would > >require (2^128)! as an upper limit, not a small number. > > Indeed, it is not a small number, but it is significantly less than > (2^128)^(2^128), which is how many 128->128 bit mappings there are. > So yes, permutations are compressible. > > Greg. > -- > Greg Rose > 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C You are confusing permutations of a set of characters in which each is used once with combinations of where characters may be redundantly used. Considering a standard case of letters, permutations<combinations...26! < 26^26.
From: WTShaw on 22 Jan 2010 08:40 On Jan 20, 11:26 pm, David Eather <eat...(a)tpg.com.au> wrote: > unruh wrote: > > On 2010-01-21, David Eather <eat...(a)tpg.com.au> wrote: > >> Peter Fairbrother wrote: > >>> In general there is the idea that random permutations, or sequences, are > >>> not compressible. > >> Random permutations are always compressible. > > > Since there are fewer numbers less than the size, and compression means > > a one to one mapping, random permutations are not compressible in > > general. There are not enough compressed outputs. > > I am assuming a permutation with a defined range eg elements in the > range of 0 - 255 etc. They are compressible unless I have missed > something about the context in the thread (not impossible) > > > > >>> While this may be true, it need not be true of a particular permutation. > > >>> Suppose that, by random chance, the particular randomly-generated > >>> permutation is the sequence 1,2,3,4 ... etc. > > >>> That's compressible. It won't occur often, but it can occur. > > >>> Cartoon at: > > >>>http://www.google.com/imgres?imgurl=http://www.random.org/analysis/di... > > >>> Referring to the recent encrypting twice thread etc, the "magic > >>> permutation" (where a chosen plaintext outputs the key, or something > >>> close to that - or even some permutation which is sufficiently close to > >>> that to give an advantage over brute force) may be compressible. > > >>> It's unlikely, but it's not impossible. And there are usually lots of > >>> chosen plaintexts (and suitable permutations) to choose from. > > >>> If we don't know what it is, or they are, does that weaken the cipher? > > >>> -- Peter Fairbrother Give an example.
From: WTShaw on 22 Jan 2010 08:53 On Jan 21, 6:27 am, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote: > WTShaw wrote: > > On Jan 20, 10:33 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: > >> On 2010-01-21, David Eather <eat...(a)tpg.com.au> wrote: > > >>> Peter Fairbrother wrote: > >>>> In general there is the idea that random permutations, or sequences, are > >>>> not compressible. > >>> Random permutations are always compressible. > >> Since there are fewer numbers less than the size, and compression means > >> a one to one mapping, random permutations are not compressible in > >> general. There are not enough compressed outputs. > > Indeed, in general - ie using one compressor. > > (but let's call them random strings from now, as that's what we are > really talking about, my bad for that confusion) > > > > > Unruh is absolutely correct. It's not just an idea, it's the > > definition of an order of n different elements. > > yes, though mangled a bit > > Hash something down > > > to a permutation and you can go not further in reducing it. > > see below > > Capture a > > > random permutation and you are done with the task of defining it. > > You have defined it, but there may be more to the task. > > > Of > > course, a secret parent sequence of the elements need not be defined > > but can be a essential separate key to the use of any selected > > permutation from the available domain of them. > > If you can find the secret parent sequence and define it, it may well > break a cipher. > > -- Peter Fairbrother You are dreaming. The idea is that any part of the data is so mangled that it cannot be recovered. I have a permutation of letters in a secret parent sequence. The new permutation is abcdefghijklmnopqrstuvwxyz. Please solve for the parent sequence. Hint(Ha): The parent sequence and the one hashed may or may not be the same. The above could just as well be anything. Series of permutations can build on previous sequences, and their are probably almost endless ways to do this. Time won't help you if a proper algorithm is in play for you will never see or be able to recover even the permutations, much less their source. This is simple and practical stuff.
From: Kristian Gj�steen on 22 Jan 2010 08:56
Simon Johnson <simon.johnson(a)gmail.com> wrote: >> It is "easy" to find. Just run each of the finite number of shorter >> programs and see if it produces the string. While a bit tedious, this is >> defines the shortest program. > >The point is, such a "stepper" programmer would generate the string >would it not, since it constructs and runs each program in passing? This is not the point. The "obvious" enumeration program that runs every short program isn't an algorithm. It might never terminate. -- Kristian Gj�steen |