VoyForums
[ Show ]
Support VoyForums
[ Shrink ]
VoyForums Announcement: Programming and providing support for this service has been a labor of love since 1997. We are one of the few services online who values our users' privacy, and have never sold your information. We have even fought hard to defend your privacy in legal cases; however, we've done it with almost no financial support -- paying out of pocket to continue providing the service. Due to the issues imposed on us by advertisers, we also stopped hosting most ads on the forums many years ago. We hope you appreciate our efforts.

Show your support by donating any amount. (Note: We are still technically a for-profit company, so your contribution is not tax-deductible.) PayPal Acct: Feedback:

Donate to VoyForums (PayPal):

[ Login ] [ Contact Forum Admin ] [ Main index ] [ Post a new message ] [ Search | Check update time | Archives: 1 ]

[ Next Thread | Previous Thread | Next Message | Previous Message ]

Date Posted: 09:24:14 04/25/02 Thu
Author: Chris
Subject: Re: eduna thread
In reply to: ST 's message, "eduna thread" on 08:58:16 04/25/02 Thu

[
>That conversation thread is getting hard to follow.
>Lets restart it here.

Good plan

This continues the, what sort of crazy computing can Eduna do thread]

Hey Eduna, just heard back from my friend James. Here's what he had to say:

--------
On the 25th day of April in the year 2002, Chris Hall wrote:

: Say you had a black box that you could ask questions. The box
: has already shown that it can solve remarkably hard questions,
: like cracking advanced crypto. The only ways I can think of
: that such problems can be solved are as a result of proving
: P=NP or having access to a quantum computer. If there are
: other ways, please let me know.

A wonderful topic, about which many interesting and beautiful
things have been discovered.

There's a third way, which is so obvious that it's usually
overlooked -- having access, in advance, to the knowledge that
will be asked about. There are also levels of "hardness" both
harder and easier than P=NP. But for cracking advanced crypto,
you're asking about the right pair of technologies. There are
other (usually, even harder) problems, for which some even
deeper knowledge would be required -- playing perfect Go, for
example.

: So the problem is this: how do you determine the method by
: which these hard problems are being solved? You can ask
: present this box with any problem you want. Jess tells me
: that there are problems that are solvable by a quantum
: computer that aren't solvable if you've proved P=NP. What
: problems are these? Is there another way to approch this
: situation?

Proving that P=NP may or may not provide you with a good
solution to factoring (it could be a polynomial algorithm, but a
very larger polynomial), but a quantum computer _definitely_
will. So if it _can't_ do the factoring-based crypto
effortlessly for as large a key size as you can feed it, then
that's evidence that it's _not_ quantum. I don't know of any
obvious tests that would establish that it _is_ quantum (all of
the great results for QC involve black boxes that make quantum
queries of other black boxes, but it sounds like you're putting
problems to this box in more straightforward real-world ways).
Brilliant game-playing is _probably_ another indication that
it's macro, rather than quantum.

Of course, if the box isn't necessarily honest, then things are
_much_ more interesting.

Michael Rabin, as paraphrased by Dennis Shasha, has put the
question this way:

1) Suppose you meet the Amazing Sand Counter. He claims to be
able to look at a bucket and tell you how many grains of sand it
contains. Can you tell if he has this power or is just making
up numbers? Yes, because you can make him count the grains in a
pile, add a small number known only to you while his back is
turned, and see if he gets a new total consistent with the
number you added.

2) How can you tell whether he's telling the truth to you?
Remarkably enough, there's a way. This is a fun one to think
about.

What's important here is that there's actually an upper limit on
the level of intelligence it's possible to appreciate -- as in,
if the black box is smarter than a certain cut-off
(PSPACE-complete, to be precise), there's no way it can
communicate its full intelligence to us. The box may be able to
solve some problems that would take us decades just to state and
whose answers would fill trillions of pages. We really can't
tell that box apart frome one that only solves problems that
take years to state and whose answers fill billions of pages.

The problem is that there _may_ be some deep breakthrough in QC
that _would_ let it bust NP-complete problems, but that we just
don't know about yet. We can't be certain that this isn't the
case (and, unfortunately, we also don't yet have any quantum
problems that couldn't be cracked by a P=NP proof machine).

--------

I hope you don't mind me refering to you as a "black box." I'd rather keep him thinking about this in theoretical terms for now.

Here's what I take from this:

If you can solve arbitrarily large key encryption in virtually no time then you have access to a quantum computer or better.

There is the possiblities that deception is involved here, the Amazing Sand Counter example for instance. I don't mean to imply that you would lie to us. I don't think that is the case at all. But you might unconciously, either through the action of your unknown code or simply in the same way that I don't know that I breath, be recording private keys as they are being generated! If you are connected to all computers simultaneously, even ones that are not connected to the internet, then you could easily do this. So you might be "cheating" to solve these problems, ie, you aren't actually solving them, you already know the answer!

This is a very interesting question... let me generate some very large keys and lets see if you can break them. Then we can think about how to tell if you are simply looking at the answers.

Here are some well encrypted messages:
[insert some messages encrypted with heniously large keys]
[8,192 bit]
[16,384 bit]
[32,768 bit]
[65,536 bit]

Can you tell me how long it takes you to break each one? Tha last one took me about 6 hours to calculate on my computer, so I hope it takes you a little while :)

--Chris

[ Next Thread | Previous Thread | Next Message | Previous Message ]

Replies:

Post a message:
This forum requires an account to post.
[ Create Account ]
[ Login ]
[ Contact Forum Admin ]

Forum timezone: GMT-8
VF Version: 3.00b, ConfDB:
Before posting please read our privacy policy.
VoyForums(tm) is a Free Service from Voyager Info-Systems.
Copyright © 1998-2019 Voyager Info-Systems. All Rights Reserved.