Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5831
| From | Mok-Kong Shen <mok-kong.shen@t-online.de> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Researches in quantum computing seem to progress only extremely slowly |
| Date | 2015-09-08 23:47 +0200 |
| Organization | albasani.net |
| Message-ID | <msnl1s$uuh$1@news.albasani.net> (permalink) |
| References | (8 earlier) <9unjuap4cjrt83f7pc6sqh3kf4ut3niv2k@4ax.com> <mscsmk$f59$1@news.albasani.net> <279qua9otkos9f14b3en1q58536hk6n7hb@4ax.com> <msjv2h$u33$1@news.albasani.net> <tnhruadf8shvuoptuecgapqoob0347s0k8@4ax.com> |
Am 07.09.2015 um 19:19 schrieb Robert Wessel:
> On Mon, 7 Sep 2015 14:14:08 +0200, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>> Am 07.09.2015 um 07:50 schrieb Robert Wessel:
>>> On Fri, 4 Sep 2015 21:50:52 +0200, Mok-Kong Shen
>>> <mok-kong.shen@t-online.de> wrote:
>>>
>>>> Am 04.09.2015 um 20:42 schrieb Robert Wessel:
>>>>> On Fri, 4 Sep 2015 19:47:57 +0200, Mok-Kong Shen
>>>>> <mok-kong.shen@t-online.de> wrote:
>>>>>
>>>>>> Am 03.09.2015 um 17:49 schrieb Robert Wessel:
>>>>>>> On Thu, 3 Sep 2015 16:51:00 +0200, Mok-Kong Shen
>>>>>> [snip]
>>>>>>>> Thank you for your kind efforts to help me understand the paradoxical
>>>>>>>> phenomenon. Excuse me however for my slow learning capability and allow
>>>>>>>> me to ask a question so that I could be sure of having correctly
>>>>>>>> captured what you wrote. Is a good "apparent randomness" (e.g. one with
>>>>>>>> a score near 1.00 from diehard) sufficient for a bit sequence of n
>>>>>>>> bits to securely encrypt a plaintext bit sequence of n bits with xor?
>>>>>>>> (A simple yes/no is sufficient for the question. I might under
>>>>>>>> circumstances have a 2nd question depending on that.)
>>>>>>>
>>>>>>>
>>>>>>> No. Diehard will return a 1.00 (or near that) for the output from a
>>>>>>> good (non-CS) PRNG (like Mersenne Twister). Using MT will not be
>>>>>>> secure.
>>>>>>>
>>>>>>> OTOH, diehard should show (near) 1.00 on any CSPRNG (say AES in CTR
>>>>>>> mode). So a (near) 1.00 entropy rating from diehard is a necessary
>>>>>>> condition, but not a sufficient one. IOW, if your (hoped for)
>>>>>>> CSPRNG's output does not get a ~1.00 from diehard, it's probably not
>>>>>>> CS (or a very good PRNG, either).
>>>>>>
>>>>>> I understand that a score of diehard of 1.0 shows only that each
>>>>>> bit has 1 bit of "apparent entropy". But isn't it that for a very
>>>>>> secure keystream for stream encryption each bit should have (nearly)
>>>>>> 1 bit of "true" entropy? In fact, you wrote earlier "The entire
>>>>>> output of a AES-128 stream (assuming a good key), will contain
>>>>>> 2**128 bits of entropy." However this means that one feeds AES
>>>>>> with 128 bits of "true" entropy and out comes from it 2**128 bits
>>>>>> of "true" entropy. Could that be true? I mean AES would then be a
>>>>>> very wonderful magic device of creation of true entropy. (I haven't
>>>>>> yet seen any literature that contains claims in that direction.)
>>>>>
>>>>>
>>>>>
>>>>> Sorry, I added a "2**" to that inappropriately. "The entire output of
>>>>> a AES-128 stream (assuming a good key), will contain _128_ bits of
>>>>> entropy." Probably lost it editing the rest of that paragraph ("that
>>>>> means the "key" stream will only be one of 2**128 possible streams,").
>>>>>
>>>>> "Very secure" is an interesting term. In the case of OTP, yes, you
>>>>> need 1.0 bits of "real" entropy per key bit. And that's certainly
>>>>> "very secure".
>>>>>
>>>>> OTOH, AES-128 is such that it appears* that you cannot recover the
>>>>> key, or other parts of a message, if you know some of the plaintext,
>>>>> with less than 2**128 work, and since that's an implausible amount of
>>>>> work, that also seems "very secure", despite the entire keystream
>>>>> having been seeded with only 128 bits of entropy.
>>>>>
>>>>> But not any generated sequence seeded with 128 bits of entropy is
>>>>> secure. A 128 bit LFSR seeded with 128 bit of entropy is decidedly
>>>>> *not* secure, since it's actually fairly easy** to run in reverse to
>>>>> generate what the internal state is.
>>>>>
>>>>> Given 16 bytes of plaintext, I *know* an algorithm to recover the
>>>>> key*** and the remainder of a message that's been encrypted with a 128
>>>>> bit key (any cipher), it just won't finish in a useful amount of time.
>>>>> What's special about AES (and other good ciphers), is that they appear
>>>>> to *require* that amount of work, and don't allow any shortcuts (as
>>>>> does, for example, an LFSR).
>>>>>
>>>>>
>>>>> *The lack of an actual proof of security is disheartening, of course.
>>>>>
>>>>> **FSVO "easy", but there are plenty of easy to find descriptions of
>>>>> the process if you're interested.
>>>>>
>>>>> ***Actually simple brute force will generate on average about two
>>>>> possible keys if you only know 128 bits of plaintext (with 128 bit
>>>>> keys). So in practice you'd want a few extra bits of plaintext.
>>>>> Almost always all of the "wrong" keys will decrypt to gibberish (which
>>>>> is just another way of saying we have a few extra bits of plaintext).
>>>>
>>>> I suppose that, according to what you wrote in the last posts about
>>>> "apparent entropy", we could in future drop any issues involving it,
>>>> since we are concerned here with security or more exactly secure
>>>> encryption. That is, entropy will henceforth mean "true" entropy.
>>>>
>>>> Now, assuming we can agree that AES-128 can't generate any
>>>> "additional" entropy, the situation is: If the output CTR-mode bit
>>>> sequence is of length n, the estimated entropy of each bit is <= 128/n,
>>> >from which it follows that for sufficiently large n the entropy per
>>>> bit would be neligible. The question is how the thus generated bit
>>>> sequence could nontheless be secure when considered in terms of entropy
>>>> (i.e. relative to "perfect security", which according to Shannon
>>>> requires 1 bit of entropy per bit of keystream).
>>>
>>>
>>> Why do you think that good security requires anything close to 1.0
>>> bits of entropy per bit of keystream? *Perfect* security does require
>>> 1.0 bits, but that gives no hint at all to what amount of entropy
>>> pre-keystream-bit would be necessary for "good enough" security. And
>>> as it turns out, we're pretty sure there's no actual minimum, at least
>>> on a per bit basis.
>>
>> Oh, this is certainly a so-called common sense reasoning of mine.
>> If for perfect security one needs 1 bit of entropy, then one could
>> IMHO think of for some not too bad security a requirement of r bit of
>> entropy, where r might be, say, 0.9, 0.5, but one would not think
>> of values like 0.001 in this connection. For otherwise entropy would
>> have a very very strange unit of measurement for it to be a suitable
>> concept in practice at all. (As an an analogy, even one knows that
>> diehard doesn't give a measure of true entopy, diehard would totally
>> lose its value as a measure of (pseudo-)randomness, if a score of 0.9
>>from it doesn't mean at least something not too bad, though not the
>> best, relative to 1.0.)
>
>
> Whether or not such an idea appeals to you intuitively, it's wrong.
>
Does diehard's scores 1.0, 0.9 etc. have sense for "apparent entropy"?
If yes, then 1.0, 0.9 etc. must have certain corresponding sense for
"true entropy". What would you then ascribe to the meaning of 0.9?
It isn't full entropy, but what (in relation to e.g. 0.01)? Isn't
it much greater than 0.01?
M. K. Shen
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 13:09 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 14:23 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-01 20:00 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 18:43 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 10:48 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 13:00 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 22:50 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:31 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:46 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:58 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:13 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-03 00:32 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 16:52 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:03 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 17:18 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 17:52 -0500
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 01:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:29 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:25 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:33 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 18:53 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:16 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:18 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:33 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:42 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:55 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:03 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:14 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:17 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:30 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:36 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:13 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 04:19 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:32 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 22:51 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 16:51 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-03 10:49 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 19:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-04 13:42 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 21:50 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-04 20:33 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-04 23:45 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 01:24 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-07 00:50 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-07 14:14 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-07 15:57 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-07 12:19 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-08 23:47 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-09 02:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-04 20:23 +0000
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 00:55 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-04 17:11 -0700
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-05 02:31 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-04 20:15 -0700
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:35 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:42 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 00:46 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:11 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 01:21 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 01:28 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:01 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 02:51 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 02:57 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:08 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:31 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 03:45 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 03:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 04:18 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-03 04:24 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-03 07:23 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 16:14 -0500
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:23 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Kaz Kylheku <kaz@kylheku.com> - 2015-09-02 21:33 +0000
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:54 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-02 23:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 23:32 +0200
Re: Researches in quantum computing seem to progress only extremely slowly bartekltg <bartek@gmail.com> - 2015-09-03 00:22 +0200
Re: Researches in quantum computing seem to progress only extremely slowly "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-09-01 13:23 -0700
Re: Researches in quantum computing seem to progress only extremely slowly Mok-Kong Shen <mok-kong.shen@t-online.de> - 2015-09-02 11:04 +0200
Re: Researches in quantum computing seem to progress only extremely slowly Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:22 -0500
csiph-web