Re: Good enough for crypto?
From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 12/04/03
- Next message: Mok-Kong Shen: "Re: Formulae for Latin squares of size 2^n"
- Previous message: Scott Wilber: "Re: Good enough for crypto?"
- In reply to: Scott Wilber: "Re: Good enough for crypto?"
- Next in thread: R3769: "Re: Good enough for crypto?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Thu, 04 Dec 2003 22:43:14 +0100
On Thu, 04 Dec 2003 10:32:04 +0000, Scott Wilber wrote:
> "Ernst Lippe" <ernstl-at-planet-dot-nl@ignore.this> wrote in message news:<3fcdd1c5$0$26962$ba620dc5@nova.planet.nl>...
>> On Tue, 02 Dec 2003 09:52:12 +0000, Scott Wilber wrote:
>>
>> > "Ernst Lippe" <ernstl-at-planet-dot-nl@ignore.this> wrote in message news:<bqg9lc$7mp$1@reader10.wxs.nl>...
>> >> In general, your statement that physical chaotic systems do not
>> >> contain real entropy is wrong. A fundamental characteristic of all
>> >> chaotic systems is that infinitesimal changes in the initial
>> >> conditions will eventually lead to macroscopic differences. When the
>> >> system does not contain any entropy, as you claimed, it should be
>> >> possible to fully predict all outputs. But because the system is
>> >> chaotic this is only possible when the initial state (plus all other
>> >> external inputs) is completely known. But for virtually all relevant
>> >> physical systems it is fundamentally impossible to know the initial
>> >> state completely, because of Heisenberg's uncertainty relation. Any
>> >> advances in mathematics or physics can only reduce our estimation of
>> >> the actual entropy in a given sample of such a physical chaotic
>> >> system, but they will never be able to reduce the entropy to zero.
>> >>
>> >> greetings,
>> >>
>> >> Ernst Lippe
>> >
>> > It is not necessary to reduce the entropy to zero in order to be able
>> > to predict the next bit with greater than 50% probability. This is a
>> > trivial problem. Only a slight edge is needed to weaken any
>> > cryptographic function.
>>
>> When you are able to predict the next bit with greater than 50%
>> probability, this simply means that that bit contains less than 1 bit
>> of entropy (and vice versa).
>>
>> But you claimed that chaotic systems contain zero entropy, by
>> definition this means that you must be able to predict the next bit
>> with 100% certainty. If you can't do this, by definition the system
>> must contain a non-zero amount of entropy.
>>
>>
>> > The exact initial state, within the limits of the Uncertainty
>> > Principal, is also not required since we are allowed to see all the
>> > bits as they are generated (or as they are used), and make adjustments
>> > using a sufficiently accurate model of the chaotic system.
>>
>> But when you are making adjustments, you are in fact using information
>> that you have obtained by observing the stream. Obviously, if you ever
>> have to make any adjustments at all, then the stream must contain at
>> least some entropy, because without these adjustments you are not able
>> to make perfect predictions.
>>
>> When a system only contains a finite amount of entropy, you will
>> only have to make a finite number of adjustments in order to predict
>> future outputs with 100% certainty. You can stop making adjustments
>> when the amount of information in the outputs is equal to the
>> entropy of the system (this is fairly obvious because entropy
>> is a measure of the information that you don't know).
>>
>> But with any realistic physical chaotic system there is no limit
>> to the number of adjustments that you will have to make. In
>> other words these systems effectively contain an infinite amount
>> of entropy.
>>
>> You probably implicitly assume that you will only need to make a
>> finite number of adjustments. In general, this will not be the
>> case. Take the case where you have a closed chaotic system (this is
>> not very realistic, all physical chaotic systems interact with their
>> environment, but for my proof this is the worst case). Now the outputs
>> from this system are completely determined by the initial state of the
>> system. Because the system is chaotic it means by definition that if
>> you make any error in the initial state, at some point in time the
>> outputs must be different from your predictions. If you are able to
>> predict the outputs with 100% certainty, you must know the initial
>> state exactly. But any realistic physical chaotic system has a very
>> large number of state variables that each must be known exactly. So
>> in order to determine the state of the system you need an infinite
>> amount of information, and by making a finite number of finite
>> precision measurements you will never be able to specify the state
>> completely.
>
> OK, every physical chaotic system contains some quantum entropy due to
> the uncertainty principal. (This of course does not include
> mathematical chaotic functions, which may be described exactly.)
>
> This does not mean that we cannot predict each next bit (or outcome)
> with 100% accuracy for most chaotic systems. We ARE allowed to know
> the state of every bit from the beginning of the sequence, and we ARE
> allowed to make corrections based on these observations. Just ask any
> cryptographer.
I did not tell you that you were not allowed to make adjustments, I
just pointed out that when you are forced to make any adjustments at
all this implies that the source must contain some entropy.
> The amount of true or quantum entropy contained in a plastic or rubber
> ball in a lottery picking machine is infinitesimal and is not enough
> to change the outcome of the drawing, even if it mixes for a very long
> time. This is simple to illustrate by computing the error
> distribution around the classically predicted outcome of colliding
> balls when quantum effects are included; something that has been done
> in many variations by others.
If I try to translate your statement into slightly more mathematical
terms, you claim that there is some minimal difference d, such that
any two initial states that differ by no more than d will always
lead to the same outcome. If you can prove this for any physical system
you have just proved that it is not a chaotic system (in the
usual mathematical sense).
> Arguments based on the level of complexity do not preclude the
> ultimate possibility of being able to make the necessary measurements
> and predictions. Super computers running recently developed
> algorithms now calculate multi-body problems, which were totally
> intractable not many years ago.
But what do you expect from these techniques? The only thing that a
better techniques can do is to lower our estimate of the entropy of
the outputs. Still they never can reduce the entropy of the system to
some finite amount. As I have argued it requires an infinite amount of
information to specify the initial state of any realistic physical
chaotic system, so the entropy in the system is infinite. When you
make observations of the system the entropy of the system is reduced
with the amount of information that you gain from these observations.
But you can only get a finite amount of information from a finite
number of observations with a finite precision. This means that
you will never be able to reduce the remaining entropy of the system
to a finite amount (not to mention zero).
greetings,
Ernst Lippe
- Next message: Mok-Kong Shen: "Re: Formulae for Latin squares of size 2^n"
- Previous message: Scott Wilber: "Re: Good enough for crypto?"
- In reply to: Scott Wilber: "Re: Good enough for crypto?"
- Next in thread: R3769: "Re: Good enough for crypto?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
