Advertisement
Guest User

ECC revocable anonymous signing

a guest
Apr 14th, 2015
18
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.62 KB | None | 0 0
  1. This started with the following Reddit thread: http://www.reddit.com/r/crypto/comments/32gh1v/looking_for_signing_algorithm_that_keeps_signee/
  2.  
  3. 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. 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!
  4.  
  5. Bonus features:
  6. 1: To be able to publish multiple messages without revealing at that time that they're signed by the same person.
  7. 2: To be able to selectively link together multiple sets of arbitarily chosen messages at a later point in time.
  8. 3: Not needing to store any state, so you don't need to store anything beyond your original private key. The random numbers needed is derived from values you already have at the point in time when you need them.
  9. Here's the most recent version of it that I'm considering;
  10.  
  11. 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;
  12. 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).
  13.  
  14. To derive the new keypair (note that we are using the ECC versions of multiplication/division, 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.
  15. 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.
  16.  
  17. Thus anybody can compute g^x_p * HMAC(H_ci, m_i) = g^x_p * H_di = g^x_i to confirm that the message was known at the time of signing by the holder of the original keypair, and that the signing keypair was derived from the original keypair using a value derived from that message (the origin of H_ci is irrelevant for verification, it just acts as a committed nonce/salt, H_di is the important value), and that both public keys represent *valid* keypairs which you *simultaneously* hold the private keys for, and you directly prove you "approve of this message" with both the signing keypair and your main keypair (you intend to prove authorship).
  18.  
  19. It is also possible to link together multiple pairs of messages to the same identity without revealing at that time that that they're related to your main keypair (and you can create a chain of these proofs for multiple messages, which in turn can be linked to your main keypair at will);
  20.  
  21. You compute l_ij = x_i/x_j = x*H_di / x*H_dj (j represents the second message, l means linking value), 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, 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.
  22.  
  23. This 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, but you probably don't need to do that either in this case.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement