NP again Re Chelsea Manning on the far right, state surveillance and their lessons for Australia | US news | The Guardian

["Dave Farber" <farber () gmail com>]

> Begin forwarded message:
>
> From: Geoff Kuenning <geoff () cs hmc edu>
> Subject: Re: [IP] Re Chelsea Manning on the far right, state surveillance and their lessons for Australia | US news | 
> The Guardian
> Date: August 9, 2018 15:48:30 JST
> To: dave () farber net
>
> The essence of NP-hardness is that you can guess the answer to a problem that (as far as we know) can only be solved 
> by exhaustive search, and verify that the answer is correct in polynomial time.
>
> This summary applies to the known-plaintext problem for *all* forms of encryption: given plaintext and ciphertext, if 
> you can guess the key you can easily verify that your guess is correct (assuming that the encryption process itself 
> is polynomial, which is true for all practical encryption methods).
>
> So yes, if quantum computing can solve any NP-hard problem in polynomial time, then it will break all known forms of 
> encryption (with the exception of one-time pads).  But there is a lot of evidence to suggest that quantum computing 
> is just a speedup and that it can't actually solve NP-hardness.




-------------------------------------------
Archives: https://www.listbox.com/member/archive/247/=now
Modify Your Subscription: https://www.listbox.com/member/?member_id=18849915
Unsubscribe Now: 
https://www.listbox.com/unsubscribe/?member_id=18849915&id_secret=18849915-a538de84&post_id=20180809025101:9193AE92-9BA0-11E8-B851-C830E7C5F351
Powered by Listbox: https://www.listbox.com