NSA and ECC

[TierNolan]

Deterministic wallets are presumably also broken if ECC is broken?

[gmaxwell]

Deterministic wallets are presumably also broken if ECC is broken?

Huh? What do you mean by determinstic wallets there?

[TierNolan]

Huh? What do you mean by determinstic wallets there?

The system that deterministic wallets use is inherently linked to the elliptic curves.

If an alternative system is used (or a different curve), then deterministic wallets would no long work.  All funds would have to be moved to a new root.

[natb]

Lamport signatures - cool I never heard of that until today. However, one property (I think) is that a keypair can only be used to sign something once (http://en.wikipedia.org/wiki/Lamport_signature#Signing_the_message). Is this another reason you favor Lamport - to essentially mandate the single use of addresses to enhance privacy?

I suppose should mention that I have (now couple year old) half finished implementation of the above, along with lamport that I've been sort of sitting on in case of cryptographic doomsday.

I'd like to go even further with a new checksig and totally replace the sighash type with the ability to include operators inside the pubkey and/or signature which instruct the node to PUSH various values from the transaction to be signed onto a tagged stack, and then the stack is signed instead of the masked transaction.  This would allow you to do things like "I sign any transaction that pays >=3 BTC to XYZ -- love, pubkey Q", or even just the equal of SIGHASH_SINGLE_AND_ALSO_OUTPUT_N...  but everyone has a pet design, I guess.

[gmaxwell]

Lamport signatures - cool I never heard of that until today. However, one property (I think) is that a keypair can only be used to sign something once (http://en.wikipedia.org/wiki/Lamport_signature#Signing_the_message). Is this another reason you favor Lamport - to essentially mandate the single use of addresses to enhance privacy?

No. While I prefer people behave in privacy maximizing ways, I think mandating it is unrealistic or at least too risky to be worth the benefit. Fortunately we don't have to.

What you can do is construct N lamport keys, where N is some reasonable number like say 1024 or 8192 (this is super fast, of course, since it's just hashes)... and then your public key is a hashtree over those lamport public keys. And in your signature you just provide the log2(N) additional hashes to connect the particular key you are using.  Alternatively the hashtree could be some other binary tree than a fully populated one, to give you different tradeoffs between reuse amount and signature size.  (google: merkle signature scheme)

The usage is still finite, but it's not just one use.  (and Lamport doesn't become completely insecure if you reuse it, it just starts losing its security... so if you had some extra unsolicited payments past your keys lifetime, it isn't the end of the world.)

Of course, the fact that privacy in Bitcoin calls for minimizing address reuse makes the finite lifetime even less of an issue then it would be in some other cases.

The system that deterministic wallets are inherently linked to the elliptic curves.

"The system that".

The concept of _deterministic_ wallets is general and works for just about any cryptographic system.  Are you talking specifically about derivation using the "public" type-2 homorphism? That works only with cryptosystems based on trapdoor permutation that have certain properties (the permutation must support composition), and obviously a single derivation chain only works with a single cryptosystem.

If you're asking about BIP32,  BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem.

[Mike Hearn]

Oops, yes, ed25519, thanks for the correction.

The reason I suggested it is simply that if we assume elliptic curve maths is basically sound modulo some unknown exotic attack that requires very specific parameters to work, then ed25519 is a good answer as it's the same core maths but without any magic NSA-originated numbers. It also doesn't change any performance characteristics of the system for the worse.

But I quite agree, postulating solutions to a problem we don't understand (or that may not even exist) is an excellent way to waste time

[markm]

Here is a potentially related potential problem...

If Joy Christian is correct that Bell made a trivial blunder right at the start of his "Bell's Theorem", which has led "everyone" for decades now to think there is something "spooky" as in non-classical (unable to be computed with a Turing machine) going on, then the whole "entanglement" thing is not afterall non-classical, it is simply the topology of space itself, fully classical if you use octonians for the math. (The apparent spookiness is really just the topology of the 7-sphere, in some cases not even needing 7-sphere math just uh hmm 3-sphere is it maybe, whatever, some sphere less than 7.)

What this should mean as far as I can see/figure is that if someone, NSA or otherwise, were to believe Joy Christian, then a so called "quantum computer" should be able to be fully simulated (emulated) using classical computing, that is to say, a Turing machine, of classical construction, that is to say, such as the NSA has lots of and even we ourselves have on our desks, in our phones etc.

This should mean that it is not necessary to build computers out of non-classical parts in order to run so called quantum algorithms, one should be able to run them on existing computers, such as the NSA has lots of, "simply" by using octonian math and not making the elementary blunder that Bell made at the start of his so called "Bell's Theorem".

Might the NSA, or other actors, be using such an approach and simply not bothering to acknowledge Joy Christian's work due to this very implication of that work?

-MarkM-

EDIT: The "elementary blunder" consists of "losing information" by means of using booleans (yes/no) to represent what in real life real space are actually "bivectors". It thus seems "spooky" that in real life, measuring what are actually "bivectors", you get different results than you get when you compute using booleans where you should be using bivectors. Or something like that anyway. Yes your "did the light turn on yes or no" is a boolean, but, your "polarisation" is not "is it polar yes or no" but rather is a bivector that will reduce to passing the filter yes or no depending on the bivector of the particle/photon and presumably something along the lines of a bivector or something of the filter.

[niko]

Might the NSA, or other actors, be using such an approach and simply not bothering to acknowledge Joy Christian's work due to this very implication of that work?

I've heard rumors that that's all D-Wave has been doing.

[markm]

Yes, all their little atoms in cold states etc could be mere theater to distract from the fact quantum algorithms can be done using classical computers.

On the other hand, I have also suspected too that it is only very small things like factoring the number 15 that can be done using actual so called quantum computers, because if Christian is right there is no spooky and thus those frozen atoms cannot really do anything we cannot do with octonians aka the topology of the 7-sphere.

(That is, maybe 15 is so trivial that it gets solved anyway, even though the whole quantum spookiness thing isn't real thus isn't really how it is doing it.)

Thus that it would turn out that the quantum algorithms will not even actually work since they depend upon a spookiness that does not actually exist, or, at best, they will simply be mechanically-faster at doing the octonian math that can perfectly well, albeit slower, be done by Turing machines.

I used to think that once we got to more qubits we would find oops they don't behave spooky afterall, quantum algorithms don't actually work. Now though I am also thinking hmm maybe qubits are merely a faster chip, maybe the algorithms will turn out to work, but if so, they should work on simulated (by Turing machines aka classical computers) "quantum" computers too. Just maybe slower.

Basically what the frozen atoms would be buying you is analog high-resolution floating-point numbers, in essence obfuscating how many bits your floating point registers actually effectively are. They might even amount to analog floating-point octonian registers. Maybe even more than one such register per atom!

Oh and also I guess maybe an analog floating point octonian arithmetic process (agency) too not just passive registers.

-MarkM-

[maaku]

Bell's argument doesn't apply to the many worlds interpretation, which also conveniently resolves all the spooky-action “paradoxes”. But regardless, under no consistent quantum theory is quantum computing with classical parts possible. Joy Christian is a crank.

[markm]

Unfortunately there doesn't seem to be any more reason to believe your claim that he is a crank than to believe others who say so.

The part about consistent quantum theory though does seem to offer a lead aka line of enquiry so thanks for that part.

Can you point to a proof of that part?

-MarkM-

EDIT: I have not seen anything in explicit quantum theory math yet that looks like classical computing cannot do it, except the sheer amount of computing it would take and of course the infinite size of the arrays/vectors implied in the event of an infinite number of items being involved in a particular universe or situation. (That is, the math in the abstract tends to be math that theoretically works even for infinite numbers of dimensions, particles etc, but in practice in a given problem the number actually of interest tends not to be infinite.)

[marcus_of_augustus]

And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible.

Ah, very interesting! I never bothered to check that (and I bet a lot of other people didn't, either). Wouldn't it be hilarious if Satoshi managed to choose one of the few standard curves that was not backdoored?

... or coincidental beyond implausible. He just used what they always use when they need it to be secure from themselves ...

Edit: more than a few reports speak of a "huge breakthrough" circa 2010(?), wonder if that is Riemann or similar or a hardware jump like quantum computer?

[maaku]

Unfortunately there doesn't seem to be any more reason to believe your claim that he is a crank than to believe others who say so.

The part about consistent quantum theory though does seem to offer a lead aka line of enquiry so thanks for that part.

Can you point to a proof of that part?

-MarkM-

EDIT: I have not seen anything in explicit quantum theory math yet that looks like classical computing cannot do it, except the sheer amount of computing it would take and of course the infinite size of the arrays/vectors implied in the event of an infinite number of items being involved in a particular universe or situation. (That is, the math in the abstract tends to be math that theoretically works even for infinite numbers of dimensions, particles etc, but in practice in a given problem the number actually of interest tends not to be infinite.)

Um, for credentials I'm a physicist, my undergraduate adviser does his research in quantum computing and I've actually done laboratory experiments demonstrating entanglement and (so-called) non-locality. Is that sufficient?

Joy Christian is of that category of people that looks at the data and says 'that can't be right!' and willfully ignores it. You can verify that something apparently spooky is going on with relatively simple experiments that have been replicated many, many times. It's like rejecting Einstein because the twin paradox is just too weird a concept. It doesn't stop the atom bomb from being possible.

Anyway I only bring up many worlds interpretation (MWI) because it's a simpler meta-theory that explains all observed quantum phenominon without resorting to the wave function collapse (and therefore without the EPR paradox of non-locality), or the privileged observer frame of reference. It still has all that quantum weirdness, but with very simple, easy to understand (albeit mind-blowing) explanation. The best long-winded introduction to MWI is this FAQ. In a couple of decades when we have atomic-scale reversible computers we'll be able to do actual experiments that will tell once and for all if the wave collapse is real or merely a belief resulting from our anthropic bias.

Regarding quantum computation, you can simulate it on a classical computer, sure. But then you only get a simulated “speedup”. It would definitely not be any faster than classical computation.

[markm]

Thanks.

Supposedly the topology of the 7-sphere reproduces all of the "spooky" results, and it does not require multiple worlds to do so, merely that this one world has 7-sphere topology.

So he is not looking at the results and claiming they cannot be right, he is looking at the theories as to how/why they are right and finding a simpler theory. Basically just wondering how the results can be right and finding a relatively simple mathematical explanation of how they come about, without resorting to multiple worlds.

That does not seem particularly - if at all - "cranky" to me.

I do agree though that hardware that naturally consults the topology of space directly is likely to be faster than software that simulates such space.

I am surprised that you agree you can simulate quantum computation on classical computers at all. Previously it had seemed the whole point with quantum computation was that it took advantage of spookiness that does not and cannot exist in classical. That classical computing could not even obtain the same results. That was part of what was spooky. "Look at this truth table! It is inconsistent! No way classical space could behave like that!"

He is basically pointing out (or claiming, anyway, it seems) that, actually, classical 7-sphere space behaves exactly like that.

-MarkM-

[keystroke]

Anyway I only bring up many worlds interpretation (MWI) because it's a simpler meta-theory that explains all observed quantum phenominon without resorting to the wave function collapse (and therefore without the EPR paradox of non-locality), or the privileged observer frame of reference. It still has all that quantum weirdness, but with very simple, easy to understand (albeit mind-blowing) explanation. The best long-winded introduction to MWI is this FAQ. In a couple of decades when we have atomic-scale reversible computers we'll be able to do actual experiments that will tell once and for all if the wave collapse is real or merely a belief resulting from our anthropic bias.

How would reversible computing allow us to determine if the wave function collapses? Unfortunately I don't have access to Deutsch's works. (Sorry to derail the thread - maybe this can be taken elsewhere. Getting Lamport signatures in bitcoin looks like a very important safeguard.)

[markm]

If you could reverse the arrow of time maybe it is as simple as having a three-dimensional past and a three-dimensional future and a one-dimensional arrow of time, adding up to seven dimensions?

if you only consider three dimensional objects, of course, and relate past and future with a one-dimensional arrow of time.

Things might have more dimensions than that of course but the layman's versions of Bell's paradox typically are looking at a simple macroscopic 3-D black box in the past and similarly a 3-D macroscopic black box in the present or future so maybe 7 dimensions is all you need to explain the experiment.

(Q: "How do we get from this 3-D situation to that 3-D situation?" A: "That adds up to 7-D so we use the 7-sphere.")

-MarkM-

[maaku]

Christian's math doesn't work out:

http://arxiv.org/abs/1109.0535

You can certainly simulate a quantum computer, just as you can simulate the core of a neutron star without actually creating one. There's nothing magical about a quantum computer. It's just capable of running an amazing number of calculations in parallel - literally in parallel if you subscribe to MWI. You can simulate that by running the calculations in series on a classical computer. Of course for the kinds of problems people usually want a quantum computer for, that simulation would take longer than the lifetime of the universe. But you could do it, in principle. There's nothing magical about quantum computation.

How would reversible computing allow us to determine if the wave function collapses?

It's in the FAQ that I linked to, but in summary you run a quantum computation requiring a wave function collapse forward and reversibly measure the result. If the wave function collapse is real then it would be resolved to a single state. When you run it in reverse the wave function maintains that single state. If, on the other hand, the MWI meta-theory is correct then the reversibility keeps the wave function coherent and it 'collapses' again as you reverse the operation possibly ending up in a different state. Of course there is no collapse, it's just an artifact of us ending up in one of many previously coherent worlds.

[markm]

Christian's math doesn't work out:

http://arxiv.org/abs/1109.0535

Yeah I have read that too, and huge threads where various such guys argue about it all. If I recall correctly Christian already shot that one down though I don't have a link offhand as to exactly where he did so and don't recall exactly what misconception(s) that specific "refutation" of Christian is (according to Christian) making.

Sites like that and online papers in general should have "pro" and "con" links on them so you can click through from any paper either to others that claim it is correct or to others that claim it is not.

(Maybe a citations-mapping site that colours citations according to whether the cited paper is being confirmed, or merely assumed correct (taken as an axiom?), or refuted would be useful?)

Since I still have no good grounds to determine which is right, I so far have to wait for the macroscopic splitting weighted balls experiment to be done that Christian proposes that will discover whether the exact same inequalities are found using macroscopic objects (particles) instead of subatomic ones, or someone beats the computer program challenge that is out there linked from the long thread in which those guys all argue with each other.

I did not find the computer program challenge reasonable though myself because it defines in advance the type of variables you have to use, like real numbers, integers, whereas it seemed to me from Christian's arguments that one should use octonians.

It is partly because of the computer program challenge that I still find it weird that you so blithely accept that a classical computer can reproduce Bell's inequality and similar inequalities, as the argument seems to be that unless Christian is right no such program can be written/executed; and similarly, the fact that no one can (aka has so far) produced such a computer-program Christian is proven wrong by the proven fact that such a program has (so far) not been created.

There is a reward of $10000 or some such thing for such a computer program so if you agree one can be written could it be commissioned for $10000 or less?

It might even have been $100,000 I am not sure offhand would have to track it down somehow (google-fu maybe).

-MarkM-

[maaku]

I don't even know how to respond to that. Quantum physics is governed by a wave equation. Quantum computers are just a neat arrangement of coherent waves and barriers that has computationally interesting properties. You simulate it by solving the wave equation, which is just math. How do you think Bell came up with his inequality? He solved a 'simulation' by hand, with pencil and paper. If someone actually has money on the line, then maybe you are misinterpreting what the challenge is?

Anyway, we're wandering deeply offtopic.

[markm]

I agree this isn't really the thread for this.

But he didn't run the simulation by hand and get the experimental results, that is the point. The inequality is between what one ought to get according to logic and what one actually gets in the experiments.

-MarkM-

EDIT: This thread inspired me to go post in my blog: http://markmetson.blogspot.ca/2013/09/the-lure-of-physics-raises-its.html