<div dir="ltr"><div><div><div><div><div><div><div><div>This started with the following Reddit thread: <a href="http://www.reddit.com/r/crypto/comments/32gh1v/looking_for_signing_algorithm_that_keeps_signee/">http://www.reddit.com/r/crypto/comments/32gh1v/looking_for_signing_algorithm_that_keeps_signee/</a><br><br></div><div>The goal is to be able to publish signed messages anonymously and then later on prove it was you who signed them, at a time of your choosing.<br><br>NOTE: I'm not a professional cryptographer, just a hobbyist, but I think I've got a good grip of how things work. I'm willing to learn, feel free to point out errors or flawed assumptions! It might be complete crap, or it might be useful. I'm trying to keep it reasonably formal, but there's probably some ambiguity left. I'm happy to answer questions.<br><br>Bonus features:<br>1: To be able to publish multiple messages without revealing at that time that they're signed by the same person.<br>2: To be able to selectively link together multiple sets of arbitarily chosen messages at a later point in time.<br>3: Not needing to store any state, so you don't need to store any data beyond your original private key. The random numbers needed are derived from values you already have whenever you need them.<br></div><div><br></div>Here's the most recent version of it that I'm considering;<br><br></div>You start off with a preexisting ECC keypair publicly associated with you, with private key x_p and public key g^x_p (p means known publicly). You have a message m_i (there may multiple messages, i is a variable that identifies the current message). To sign a message anonymously, you create a new keypair. To be able to prove it was created by you at a later point in time, without allowing others to claim authorship, this is how it is created;<br></div></div><br></div>You first compute a unique per-message committed value H_ci = HMAC(m_i, x_p). From that you compute a per-message value from that used for derivation of a new ECC keypair, H_di = HMAC(H_ci, m_i).<br><br>To derive the new keypair (note that we are using the ECC versions of multiplication/division, etc, not arithmetic), you compute the derived private key x_i = x_p * H_di and the derived public key g^x_i = g^x_p + H_di (deriving new valid keypairs is a neat feature of many ECC implementations; also deriving nonces from the the private key + the message has precedence in deterministic signatures). This keypair is used to sign m_i.<br></div><br></div>To later on prove that you were the signer of the original message, you compute and publish H_ci, signed with both keypairs x_p;g^x_p and x_i;g^x_i (you probably should also include m_i and g^x_p and g^x_i in the signed message). Thus anybody can compute g^x_p + HMAC(H_ci, m_i) = g^x_p + H_di = g^x_i and validate both signatures to confirm the following;<br><br>1: That the signing keypair was derived from the original keypair, using a 
value derived from that message (thanks to the hash commitment, it isn't merely random), so the keypairs are related (the exact origin of H_ci is irrelevant for 
verification, it just acts as a committed nonce/salt, H_di is the 
important value; H_ci is derived from the message + main private key in order to keep things stateless).<br>2: That as a result of 1, the message must have been known to the holder of the original keypair at the time of signing, as the signature can't be created before the keypair is created (this binds the message to your keypair such that nobody else can claim authorship in contradiction to you - assuming your original signature of the message was preserved when the message was published and known by the verifying parties). Timestamping a hash of the signed message before publishing can assist you in your claim of authorship as you can prove your signature is the earliest timestamped one.<br>3: That both public keys represent *valid* keypairs which you hold and can sign messages with.<br>4: That you hold the private keys of both keypairs *simultaneously* (decreases risk of collusion between the signer and another party).<br>5: That you "approve of this message" with both the signing keypair and your main keypair (you intend to prove authorship and link the keys).<br><br></div><div>It is also possible to link together pairs of messages to the same pseudonymous identity without revealing at that time that that they're related to your main keypair, and you can even create a chain of these proofs for multiple messages, which in turn can be linked to your main keypair at will;<br><br></div><div>You compute l_ij = x_i/x_j = x_p * H_di / x_p * H_dj (where l means linking value, j represents the second message), where g^x_i + (x_i/x_j) = g^x_i + l_ij = g^x_j. l_ij here has the same function as H_di above, and you sign l_ij with both keypairs x_i;g^x_i and x_j;g^x_j, thus proving you hold both keypairs simultaneously and intend to link them (again, you should include g^x_i, g^x_j, m_i and m_j in the signed message).<br><br>This version do not show that you already knew one message while signing the other like it does with showing the tie between x_p;g^x_p and x_i;g^x_i, so this proves nothing about the origins of the keypairs, but you probably don't need to do that either in this case. You can however later on decide to link the messages to your main keypair by revealing the committed values H_ci, H_cj as above, which then *does* prove the origin of the keypairs.<br><br></div><div>References:<br><br><a class="" href="http://sourceforge.net/p/bitcoin/mailman/message/31813471/" rel="nofollow">http://sourceforge.net/p/bitcoin/mailman/message/31813471/</a><br>
<a class="" href="https://wiki.unsystem.net/en/index.php/DarkWallet/Stealth" rel="nofollow">https://wiki.unsystem.net/en/index.php/DarkWallet/Stealth</a><br>
Graphic: <a name="img6" type="IMAGE" class="" href="http://i.imgur.com/rHhNKL6.jpg" rel="nofollow">http://i.imgur.com/rHhNKL6.jpg</a></div></div>