Proposal: Simple modification for better anonymity

[urian]

Hello,
here is a proposal for a slight protocol modification, which could solve the follwing two issues related to anonymity:

1. In order make an anonymous transaction the receiver of the money must generate a new public/private key pair.
This can get cumbersome if the receiver is, for instance, a web shop merchant. Here it would be preferable if the merchant could post a fixed public key on his web site.       
But on the other hand, neither the merchant nor the buyer wants that everybody can see all transactions to the web shop.

2. It is a good idea to keep the secret keys in a secure, tamper-resistant wallet (e.g. a smart card). But it is unfortunate to store many secret keys on a resource limited device.
One solution would be to derive all private keys from a master secret. But than you have to maintain a database associating your private keys with their derivation data.

The solution to both issues stems from the following simple oberservation:
An ECC public(P)/private(s) key pair is related by the formula
P = G*s, where G is the fixed generator point of the curve.
The generator point G has been choosen by the curve constructor(CERTICOM). This point is only a random point on the curve. Any other point on the curve would be an equally well generator point.
If we multiply G and P by the same random number r, we get
P' = P*r
G' = G*r
and it follows that
P' = G'*s
With this trick we get a new public key P' an a new generator G' to the same secret key s.

Therefore we redefine a public key by the pair of points (G, P).   
(i.e. the generator of the curve is no longer fixed but part of the public key)

Due to the Decicional-Diffie-Hellman assumption, two public keys (G,P) and (G',P') for the same private key s cannot be associated.
(i.e. we get untraceability)

The basic protocol flow would be as follows:
1. The receiver posts some randomly choosen public key (G,P) for his fixed secret key s on his web page. 
2. The sender blinds the public key by multiplying it with a random number r and calculates (G',P')= (G*r, P*r)
3. The sender generates a transcript. (The hash of the public key must now consist of two points G', P')
4. The sender sends the transcript and the blinded public key (G', P') to the receiver.

I suppose the modifications to the bitcoin protocol would be moderate.
I can also see any security and performance impact.









 
 

       

 
 

[jackjack]

Hello,
here is a proposal for a slight protocol modification, which could solve the follwing two issues related to anonymity:

1. In order make an anonymous transaction the receiver of the money must generate a new public/private key pair.
This can get cumbersome if the receiver is, for instance, a web shop merchant. Here it would be preferable if the merchant could post a fixed public key on his web site.       
But on the other hand, neither the merchant nor the buyer wants that everybody can see all transactions to the web shop.

2. It is a good idea to keep the secret keys in a secure, tamper-resistant wallet (e.g. a smart card). But it is unfortunate to store many secret keys on a resource limited device.
One solution would be to derive all private keys from a master secret. But than you have to maintain a database associating your private keys with their derivation data.

The solution to both issues stems from the following simple oberservation:
An ECC public(P)/private(s) key pair is related by the formula
P = G*s, where G is the fixed generator point of the curve.
The generator point G has been choosen by the curve constructor(CERTICOM). This point is only a random point on the curve. Any other point on the curve would be an equally well generator point.
If we multiply G and P by the same random number r, we get
P' = P*r
G' = G*r
and it follows that
P' = G'*s
With this trick we get a new public key P' an a new generator G' to the same secret key s.

Therefore we redefine a public key by the pair of points (G, P).   
(i.e. the generator of the curve is no longer fixed but part of the public key)

Due to the Decicional-Diffie-Hellman assumption, two public keys (G,P) and (G',P') for the same private key s cannot be associated.
(i.e. we get untraceability)

The basic protocol flow would be as follows:
1. The receiver posts some randomly choosen public key (G,P) for his fixed secret key s on his web page. 
2. The sender blinds the public key by multiplying it with a random number r and calculates (G',P')= (G*r, P*r)
3. The sender generates a transcript. (The hash of the public key must now consist of two points G', P')
4. The sender sends the transcript and the blinded public key (G', P') to the receiver.

I suppose the modifications to the bitcoin protocol would be moderate.
I can also see any security and performance impact.

I don't see how this would increase anonymity
This would require OP_CONCATENATE which is deactivated
Also, https://bitcointalk.org/index.php?topic=232787.0

[Mike Hearn]

It's a neat observation (not a new one). There are already solutions to these problems in the works:

https://en.bitcoin.it/wiki/BIP_0032
https://github.com/bitcoin/bitcoin/pull/2539

[Sergio_Demian_Lerner]

Also check this 4 solutions for the same problem:


1- [PROPOSAL] Untrackable addresses: https://bitcointalk.org/index.php?topic=131243.msg1405288#msg1405288

2- Untraceable transactions which can contain a secure message are inevitable: https://bitcointalk.org/index.php?topic=5965.msg87757#msg87757

3- Mine: http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

4- Gavin's: Bitcoin Payment Messages https://gist.github.com/gavinandresen/4120476

Best regard, Sergio.

[urian]

Hello,
thank you for the links.
Here are my comments/answers.

It's a neat observation (not a new one). There are already solutions to these problems in the works:

https://en.bitcoin.it/wiki/BIP_0032

This BIP describes a key derivation scheme. This is certainly a better way than storing individual secret keys. However, one must still maintain a database associating the key derivation data with the keys.  My proposal does not need a key derivation scheme, because only one secret key is needed.

Also check this 4 solutions for the same problem:


1- [PROPOSAL] Untrackable addresses: https://bitcointalk.org/index.php?topic=131243.msg1405288#msg1405288

2- Untraceable transactions which can contain a secure message are inevitable: https://bitcointalk.org/index.php?topic=5965.msg87757#msg87757

3- Mine: http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

4- Gavin's: Bitcoin Payment Messages https://gist.github.com/gavinandresen/4120476

Best regard, Sergio.

to item 1:
This proposal has one drawback, as the thread starter already noticed:

... However, if someone sends money twice from the same normal address to the same proposed address, then destination normal address will also be the same...

(Please note that proposed solution to this issue by user "thanke" in the same thread does not work. An attacker can simply calculate E*(txin^(-1)) for any transcation and compare the public keys)
Contrary to this, my solution does not have this drawback.     

to item 2:
This is essentially  the same as item 1

to item 3:
Let's compare your proposal(4) with mine:

system complexity:
Your proposal needs an additional private/public key pair for encryption.

mathematical complexity:
Lets assume you're using Elgamal encryption. For simplicity, lets count only ECC operations.
For sending you have to perform one scalar multiplication to get the new point k*QA and than do an Elgamal Encryption, which costs two scalar multiplications plus one addition:
My proposal needs only two scalar multiplications for the blinding of the public key
For checking the transactions you have to perform an Elgamal decrytion to get the anonymity key (1 scalar mult and one add) and than do a scalar multiplication with this key. 
My proposal need only one scalar multiplication. One only has to check if P' = f*G', where f is the fixed secret key. 

In summary:
              yours                 mine
SEND       3 mult, 1 add      2 mult
CHECK     2 mult, 1 add      1 mult

to item 4:
I cannot see how this proposal is related with mine.