On compressibility of random permutations
in [Cryptography]
|
From: Peter Fairbrother on 20 Jan 2010 19:27 Phoenix wrote: > On 20 Jan, 19:42, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote: >> In general there is the idea that random permutations, or sequences, are >> not compressible. >> >> 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. > > > "Algorithmic information theory studies, among other topics, what > constitutes a random sequence. The central idea is that a string of > bits is random if and only if it is shorter than any computer program > that can produce that string (Kolmogorov randomness)�this means that > random strings are those that cannot be compressed. Pioneers of this > field include Andrey Kolmogorov and his student Per Martin-L�f, Ray > Solomonoff, and Gregory Chaitin." from Randomness wikipedia A nice idea, and useful for some purposes - though it's defined backwards from another idea. The problem is that, for finite random numbers above about 2^8, the number of possible ways of defining them in ways shorter than the number is greater than the number itself. 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. --Peter Fairbrother > > But I agree with you, some sequences can be like 1,2,3,... or > 1,1,1,1.... > > Like in the real world, good algorithms can, some times, (very > little), generate that kind of sequences. > > I think that's why George Marsaglia on his Diehard tests, say 'p > happens". > > Alvo
From: Phoenix on 20 Jan 2010 20:05 On 20 Jan, 23:27, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote: > Phoenix wrote: > > On 20 Jan, 19:42, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote: > >> In general there is the idea that random permutations, or sequences, are > >> not compressible. > > >> 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. > > > "Algorithmic information theory studies, among other topics, what > > constitutes a random sequence. The central idea is that a string of > > bits is random if and only if it is shorter than any computer program > > that can produce that string (Kolmogorov randomness)this means that > > random strings are those that cannot be compressed. Pioneers of this > > field include Andrey Kolmogorov and his student Per Martin-Löf, Ray > > Solomonoff, and Gregory Chaitin." from Randomness wikipedia > > A nice idea, and useful for some purposes - though it's defined > backwards from another idea. > > The problem is that, for finite random numbers above about 2^8, the > number of possible ways of defining them in ways shorter than the number > is greater than the number itself. > > 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. > > --Peter Fairbrother > Now the question is: How many sequences are defineable and how many are not, in a field of permutations with i.e. 2^128. Alvo
From: David Eather on 20 Jan 2010 20:46 Peter Fairbrother wrote: > In general there is the idea that random permutations, or sequences, are > not compressible. Random permutations are always compressible. > > 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/dilbert.jpg&imgrefurl=http://www.random.org/analysis/&h=257&w=680&sz=65&tbnid=nstbI3k78X1MrM:&tbnh=53&tbnw=139&prev=/images%3Fq%3Ddilbert%2Brandom&usg=__eOy0f5JovE_JsEMpRRNUbfUa-vM=&ei=H2hXS-iyJJ380wSsvYnzBA&sa=X&oi=image_result&resnum=4&ct=image&ved=0CBMQ9QEwAw > > > > 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
From: unruh on 20 Jan 2010 23:33 On 2010-01-21, David Eather <eather(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. > >> >> 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/dilbert.jpg&imgrefurl=http://www.random.org/analysis/&h=257&w=680&sz=65&tbnid=nstbI3k78X1MrM:&tbnh=53&tbnw=139&prev=/images%3Fq%3Ddilbert%2Brandom&usg=__eOy0f5JovE_JsEMpRRNUbfUa-vM=&ei=H2hXS-iyJJ380wSsvYnzBA&sa=X&oi=image_result&resnum=4&ct=image&ved=0CBMQ9QEwAw >> >> >> >> 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
From: WTShaw on 20 Jan 2010 23:42
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. > Unruh is absolutely correct. It's not just an idea, it's the definition of an order of n different elements. Hash something down to a permutation and you can go not further in reducing it. Capture a random permutation and you are done with the task of defining it. 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. |