I guess the first step "publish the point" is critical. I don't see what stops Alice from simply running this protocol with herself, and then saying "Look, Bob agreed!". Then Bob says "I never heard of Alice" and we're back to step one.

If Bob has to publish his point for each transaction that takes place, how do we know it's Bob's point? It seems like we're back to square one ...

btw a simpler chameleon hash involving conventional crypto can be seen as part of this indistinguishable shortcut hashcash variant based on RSA.  https://bt.irlbtc.com/view/308009.msg3307636#msg3307636

Just replace the search for t =? h( s, i, a, m ) mod 2^k (where i is an iterator, s salt, a initial witness, m message to sign) with t=h(m).  Then make random c, chameleon hash a=c^t mod n. Chameleon hash is (c,t=H(m)a).  Bob has p & q so he can compute different t'-th root, for (c',t'=H(m'),a) from c'=a^(1/t') mod n where t'=H(m'), where as Alice can only go in the forward direction choose c, hash mesage to make t, raise c to power of t. 

I use it to create a hashcash variant with an indistinguishable short-cut which you could think of as a chamleon proof of work (a chameleon much repeated hash, or a single exercise of the trap door holders private key).

I am guessing no one has thought of that particular chameleon hash construct for some reason because people do not usually reach for the esoterics gap DH or bi-linear DH unless they run out of flexibility with conventional hardness assumptions and need the extra degree of freedom.  I could be off base, but this also does not leak the private key, and that seems to be the implication of the paper you referenced with the improved Chameleon hash.

Adam

How do you mean here? Normally, in most societies, its frowned upon presenting a forged contract. For example here in sweden, its illegal to present a forged contract, even if you do it in a response to a threat or coercion.
Even if a gangster member puts a pistol to your forehead, making up a forged contract and presenting it to the gangster member can get you in prison. The correct way to do it, is to present the original contract and then reporting the threat to the local authorities.


Normally, the safeguard when handling contracts, is that you should NEVER EVER put anything that you want to keep for yourself, into a legal contract.
In sweden, we handle secrets by referring to attachs.
For example: "This buy contract obligies Sebastian to pay XX SEK to a bank account number. This bank account number is referred to in attach #1".

attach #1 is then kept a secret, so if the contract gets into a Court, the attach #1 is never revealed to the public, only the contract and the judge's decision is revealed.
Same is done for example in a Court if someone here in sweden has a protected identity, for example a important witness.
Then they refer it to "Party A", "Party B" etc.

And then in a secret attachment which is only accessible to the police, it says like:
"Party A: name namesson, avenue street 12, 123-12 BigCity"
"Party B: Test Testsson, Home street 9, 999-12, SmallCity"


Of course, the attach's also needs to be a such way so they don't affect the outcome of the contract, eg you cannot keep a price or important parts of the agreement secret or something like that.




Same could be done here, eg put a reference mark, like "attach #1" in the contract to refer to secret data.

I think you maybe dont understand the concept of smart contracts and anarcho-capltalism (as embodied by crypto-anarchy where crypto means cryptography, and I guess not anarchy also, just an egalitarian society without a force monopoly form of government).  Basically the idea is using new crypto concepts its possible to contract without threat of violence/imprisonment as a disincentive to cheating, because the contracts are atomically self-enforcing.

You might find sci-fi "Snow Crash" by Neal Stephenson interesting, and "Cyphernomicon" by Tim May a kind of crypto-anarchist manifesto (online http://www.cypherpunks.to/faq/cyphernomicron/cyphernomicon.html) (not to be confused with "Cryptonomicon" another sci fi work by Neal Stephenson, also fun but long and somewhat related).

To quote Wei Dai from his motivation section intro to B-money (one of the main bitcoin precursors):

http://www.weidai.com/bmoney.txt


I am not sure if Satoshi had crypto-anarchy in mind but folks like Tim May (cypherpunks co-founder/cyphernomicon), most of the cypherpunks, and people working on ecash like myself (Hashcash, distributed mining), Wei Dai (b-money) Nick Szabo (bitgold), Hal Finney (RPOW), and most of the digicash tech guys (David Chaum long defunct payer anonymous ecash company), zero-knowledge systems guys (pre-Tor privacy networking) and others working on ecash 1995-2005 certainly did have that in mind as their burning motivation.  I am also guessing Chris Odom (open transactions) who seems to enjoy distributed Chaum servers, with voting pool backing, though I cant speak for him.

Since that time finally I also see some hope of political progress in the form of the meteoric rise of Rick Falkvinge & the pirate party (and the Libertarian party eg folks like Ron Paul to the extent the LP was slowly rising towards having a chance of being elected), but previously (eg back in 1995 - 2005) it seemed almost the only hope for humanity was a new wave of technological progress led shifts.  In the same way that the internet tends to topple undemocratic states, non-state controlled free money tends weaken the grip of to varying degrees systemically corrupt and difficult to reform governments.

[EDIT: btw other than the internet, another example of technological led power shift was the discovery of public key encryption and the ready availability of PGP, and later other communication security/privacy iike OTR, Tor etc.  The fact that many governments tried to control access to and restrict encryption, before giving up, should tell you that you need to be using it: they were worried they can less control a populace with cryptographic free speech and cryptographic freedom of association, even those are legal rights in most countries, cryptographic enforced rights are more strongly held than legal rights, because as we see from Snowden, legal rights arent worth the paper they are written on.  The reason they gave up is it became an untenable position for a notionally free democracy to enforce.  More restrictive regimes tend to have more restrictive crypto usage regulations.]

Anyway you can use bitcoin without caring about libertarian politics or its technical adjunct crypto-anarchy eg because its technically cool, or because you dislike governments doing money printing/quantitative easing to the benefit of connected banks, and detriment of individuals, or bank deposit seizures (like in Cyprus) or as a speculative investment, or because its faster and cheaper, or available in all countries, even without banking infrastructure and onwards  And by doing so, in a neutral non-political way, you are also helping build the crypto-anarchic future, in the same way that promoting internet use indirectly helps topple dictators.

But I do recommend anyone to read the Cyphernomicon and Snow Crash it might just open your mind to a new view point or even convert you.  [EDIT I guess Assange et al's book "Cypherpunks" is probably on the money though I havent read it myself.]

Circling back to why forge a contract, thats not the point: the point is the contracting parties should be free to contract without interference from outside parties (criminal or government) and the point of a chameleon hash based signature (or nearly equivalent designated verifier signature) is that the evidence evaporates because its intentionally non-transferable - they cant renege even if they wanted to.  Designated verifier is a bit different as that means it convinces the recipient (Bob), but neither Alice nor Bob can prove/transfer the signature as either party could forge; with chameleon hash signatures only Bob can forge.  

Also bear in mind that other than the fact of shaming a pseudonym (Bob) and tarnishing his reputation that's may not be much of a disincentive, and another model is for the parties to agree on an arbitrator who has 3rd vote in 2 of 3 multisig.  Probably you can use two designated verifier signatures so the the arbitrator could also have forged the contract.

Adam

Indeed, the provider of the public key used it the chameleon hash could be entirely independent of the parties making the transaction.  I don't doubt that it would even be possible to construct a threshold chameleon hash, where some N of M parties were required.

Thank you for the excellent explanation too.

One thing that I'd like to add is that the methods of crypto-anarchy are still useful in the context of a society which is largely politically dissimilar. For example, some contracts people form are _too low value_ to effectively use the kinds of tools to ensure honest dealing in wider western societies today (e.g. courts) or the easy centralized alternatives facilitate rent seeking (e.g. having to pay to use a game server in order to play a game with your friends, you all have network access and powerful computers, what do you need the server for?).  If mathematical tools exist that allow cheat proof interacting they are often inherently scalable— we can apply them to high value things and low value things alike, because once they're coded they're nearly free.

Having good tools at our disposal allow societies to pick appropriate tools for appropriate situations, and we can all only benefit from that.

Catching up the thread from #bitcoin-wizards (plus some fixes and new observations) gmaxwell posed the question if you could make a chameleon hash that is also a valid ECDSA signature (with the added benefit being its a bit more bitcoin integratable).  Curiously it seems that you can and here's how:

ECDSA: R=kG, r=R.x, s=k^-1(H(m)+rd) where d is private key Q is public key Q=dG, G is base point, k is random; signature is (r,s).  A verification relation is: sR =? H(m)*G+rQ

Alice is using the hash, Bob is the owner of the private key able to forge hashed values.

Work backwards, choose r' random, compute point R=[r',f(r')] from curve equation f(x), then calculate T=H(m)*G+rQ.  Choose random s, compute R=s^-1*T so that sR=T, then can write sR=H(m)*G+r'Q however now r=R.x and r != r' (because R is some random point) so the r value is inconsistent with point R, adjust for that by finding Q'=cQ such that sR=H(m)*G+rQ', so c=r'/r, ie Q'=r'/rQ (then rQ'=r'Q as required).

Now we have a standard completely forged by Alice signature but not on Bobs public key but on a different public key Q' which is a known multiple c=r'/r of Q: Q'=cQ.  This key is mismatched with The ECDSA signature is (r,s), and the chameleon hash is (r,s,c) the secret value which allow Bob to modify the chameleon hash is c (the factor for modifying the public key Q'=cQ).

To reveal the hash in event of dispute Alice shows c (Q is anyway computable from r,s; and Q'=cQ).  Then anyone can check r,s is a signature of m with public key Q'=cQ.  The signature is verifiable without revealing c, but meaningless as no one knows who's key Q' corresponds to, not even Bob.

To forge different hashes Bob finds m' and Q" such that sR=?H(m')*G+rQ" so he has to find Q" such that H(m)*G+rQ'=H(m')*G+rQ" and as he knows d this can be written [H(m)+dr'/r]*G = [H(m')+dc"]*G where Q"=c"Q.  So solve to find c"=[H(m)-H(m')+dr'/r]/d and therefore Q"=c"Q.  Bob can show (r,s,c") and anyone can check r,s is a signature of m' with public key Q"=c"Q.

One comment in the paper Greg referenced in OP is Bob forging reveals his private key in some protocols (which is obviously no good, its more than an inconvenience as it also destroys the non-transferability if his private key leaks people can check which hash the private key can be computed from to know which is the forgery).  In this case as c'=[H(m)-H(m')+dr'/r]/d = [H(m)-H(m')]/d+r'/r so d can be recovered d=[H(m)-H(m')]/(c"-r'/r).

However its rather easy to fix this, instead of revealing Bob revealing c" or Alice revealing c they can prove knowledge of a discrete log of Q" or Q' in base Q using... an ECDSA signature with base Q and public key Q" or Q' respectively.

However even that does not quite work the same way as the other chameleon hash because Alice can reveal c also to create a strong proof (where a signature involving c but not disclosing c is a weak proof) and it can be seen that it does not solve to d.  

While its different thats actually a feature, as if Alice reveals a strong proof, Bob's forgery is not plausible as he cant make strong proofs - if he does it reveals his private key which makes it obvious his messages are forgeries.  (In the paper and the above Schnorr related scheme, in fact even if Alice does reveal her proof, an arbitrator cant tell which message was Alice's and which was Bob's, so in theory Alice could falsely claim to have made one of Bob's forged messages, though it assumed this is not generally a threat).

Conversely Bob could be coerced into proving that a forgery he makes is not authentic, by showing c" (instead of a DL proof of knowledge of c") which then allows his private key to be recovered.  However Alice doesnt give Bob c, so Bob cant prove that Alice's message was not his, he could be lieing and actually have c.

So overall that seems like a slightly stronger chameleon hash property. So we get the new benefit of no forgery ability for Bob if Alice reveals a strong proof, and yet no ability for Bob in the normal case to transfer proof of what Alice said.  He could reveal weak forgeries, and Alice's message is indistinguishable from them.  He could make a strong forgery (reveal c") which reveals his private key, but that still doesnt prove that Alice's weak forgery was authentic - they could both be Bob's and he could be lieing about not knowing the secret value c (discrete log of Q' wrt to Q).

Adam

Need to update this - found a problem a week back, but lost part edited tab:


There is a flaw in the logic in the last para.  If Bob is coerced into revealing c" and hence d is recovered (or he is coerced to reveal d directly), then anyone can do n^2 analysis of the n signatures (one real and n-1 forged) pairwise and see that all the forgeries derive from Alice's deterministically with the private key, but Alice's key cant be derived from any, and hence Alice's is correct.  Also Bob's only deterence to doing that at any time without coercion is revealing his private key.  The root cause of the failure is there is no new randomness in the process of forging chameleon hashes by Bob.

To the extent its still interesting if we change this much more, I think that might be repairable by having Alice not publish s (send it out of band to Bob, dont commit to it in the spend).  Then the chameleon hash becomes (r,c).  Alice cant find a different s that signs commits to a different message because she doesnt know d.  And Bob can recover k as sR=H(m)G+rcQ => sk=H(m)+rd so k = s^-1(H(m)+rd), and armed with k Bob can create s' for any signature.  Whats more this time those are all symmetric.  With d he can as plausibly recover k from (r,c),s' so Alice's message is indistinguishable as desired.

Not sure that overall is ECDSA like enough to be interesting and the schnorr method in
https://bt.irlbtc.com/view/318279.msg3417729#msg3417729 seems a lot simpler!

Adam