On compressibility of random permutations
in [Cryptography]
|
From: Greg Rose on 22 Jan 2010 13:25 In article <9b046deb-ac32-4093-ab8f-14c9bd44eff2(a)b10g2000yqa.googlegroups.com>, WTShaw <lurens1(a)gmail.com> wrote: >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. I think you just agreed with me. For any positive N, N! < N^N. There are N! permutations of N elements, and there are N^N random mappings from a set of N elements into itself. Therefore, if you know that your blob of data is a permutation, it has less entropy than a random mapping and must be compressible. You use N=26, someone (Joseph?) used N=2^128. Still true, either way. Where do you think my confusion is? Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: Peter Fairbrother on 22 Jan 2010 16:39 Herbert Paulis wrote: > "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. The problem lies in the computer language and the instruction set used. Ray Solomonoff, on whose work Kolmogorov and Chaitin's work rests, postulated the existence of an "absolute-minimum-language", (sort-of, if I may use the term) but he neither stated what it is nor proved that one exists - and no-one since has done either. So we can't use any particular language to get an absolute, defined value of Kolmogorov complexity. For some language a minimum size program for a particular string may be larger than it's representation, which in other languages the minimum size for that string may be larger - it depends on the language used. For a particular language, you can use counting proofs to show that for eg all 128-bit binary strings the minimum program to describe some of them must take at least 128 bits - but exactly which of the strings this is true for will depend on the language used. In fact, you can develop a language in which the minimum program for any particular 128-bit string (though not for all 128-bit strings) is less than 128 bits. So you can't ever point to any (finite, well-defined, real-life) string and say "this is Kolmogorov complex (or -random), for all languages". -- Peter Fairbrother
From: Peter Fairbrother on 22 Jan 2010 17:07 Kristian Gj�steen wrote: > 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. > You could tell it to stop after say 128! (or busy beaver 9) steps, which would cover the numbers up to 128! or (BB9). This can be fixed though, by saying a valid program *only* outputs the string in question. But it doesn't solve the language problem. -- Peter Fairbrother
From: Peter Fairbrother on 22 Jan 2010 19:26 Peter Fairbrother wrote: > Herbert Paulis wrote: >> "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. > > The problem lies in the computer language and the instruction set used. > > Ray Solomonoff, on whose work Kolmogorov and Chaitin's work rests, > postulated the existence of an "absolute-minimum-language", (sort-of, if > I may use the term) but he neither stated what it is nor proved that one > exists - and no-one since has done either. > > So we can't use any particular language to get an absolute, defined > value of Kolmogorov complexity. > > For some language a minimum size program for a particular string may be > larger than it's representation, which in other languages the minimum > size for that string may be larger ^H^H^H^H while in another language the minimum size for that string may be smaller. Whether a string is Kolmogorov-complex or not > depends on the language used. > > > > For a particular language, you can use counting proofs to show that for > eg all 128-bit binary strings the minimum program to describe some of > them must take at least 128 bits - but exactly which of the strings this > is true for will depend on the language used. > > > In fact, you can develop a language in which the minimum program for any > particular 128-bit string (though not for all 128-bit strings) is less > than 128 bits. > > So you can't ever point to any (finite, well-defined, real-life) string > and say "this is Kolmogorov complex (or -random), for all languages". > > > -- Peter Fairbrother
From: Herbert Paulis on 25 Jan 2010 02:35
"Peter Fairbrother" <zenadsl6186(a)zen.co.uk> schrieb im Newsbeitrag news:4b5a4249$0$2536$da0feed9(a)news.zen.co.uk... > Peter Fairbrother wrote: >> Herbert Paulis wrote: >>> "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. >> >> The problem lies in the computer language and the instruction set used. >> >> Ray Solomonoff, on whose work Kolmogorov and Chaitin's work rests, >> postulated the existence of an "absolute-minimum-language", (sort-of, if >> I may use the term) but he neither stated what it is nor proved that one >> exists - and no-one since has done either. >> >> So we can't use any particular language to get an absolute, defined value >> of Kolmogorov complexity. >> >> For some language a minimum size program for a particular string may be >> larger than it's representation, which in other languages the minimum >> size for that string may be larger > > ^H^H^H^H > > while in another language the minimum size for that string may be smaller. > Whether a string is Kolmogorov-complex or not > >> depends on the language used. >> >> >> >> For a particular language, you can use counting proofs to show that for >> eg all 128-bit binary strings the minimum program to describe some of >> them must take at least 128 bits - but exactly which of the strings this >> is true for will depend on the language used. >> >> >> In fact, you can develop a language in which the minimum program for any >> particular 128-bit string (though not for all 128-bit strings) is less >> than 128 bits. >> >> So you can't ever point to any (finite, well-defined, real-life) string >> and say "this is Kolmogorov complex (or -random), for all languages". >> >> >> -- Peter Fairbrother Thanks, understood (and agreed). Herbert |