ECDHE and AES

[darioAnongba]

Hi,

Sorry to bother you again. Sadly I am not able to fully understand how do you plan on adding the blinding factor and the value on-chain as part of a transaction just by reading your code.

If I understand correctly, you are encrypting the bf and the value into a message using AES and then you embed those values into an event along with the IV, so you have something like that.

TxEvent(...other_values, message = encrypted(value, bf), iv)

In order to decrypt the message the parties need a shared key that is generated and communicated off-chain using ECDHE. Now the problem is, what is one of the parties lose the shared key, or if they reinstall the app at some point and need to resync? How can I recover the values? I'm missing something I think.

Thanks again for your time, Dario

[solidblu1992]

Hi Dario,

So, if you want put as much of the process and security as possible on chain, I think that each send tx should store a Diffie-Hellman (DHE) point with each corresponding UTXO. Note that all elliptic curve math below should use Secp256k1 (NOT alt_bn_128) as this will leverage existing Ethereum public and private key pairs.

1. Sender picks a random number r (mod Ncurve)
2. Sender computes DHE point R = rG. This will be published along with the sender's tx.
3. Sender computes shared secret ss = keccak256(rP), where P is the receiver's Ethereum public key
4. Sender encrypts the value and blinding factor using AES with shared secret ss.
5. Sender sends tokens while including the DHE point from step 2 and encrypted data from step 4.

If this scheme is used, the receiver doesn't need to keep track of any information except their Ethereum private key. In order to recover the encrypted data they do the following:

1. Retrieve DHE point R from their utxo
2. Compute shared secret ss = keccak256(pR) where p is their Ethereum private key
3. Decrypt value and blinding factor using AES with shared secret ss.

The only discussion point left to figure out how to communicate the receiver's Ethereum public key to the sender as the sender only knows the hash of the receiver's public key by default. I suppose could be handled bluntly by just having each token user publish their Ethereum public key.

What do you think?

[solidblu1992]

Oh, and as another small detail: the DHE point and the encrypted data don't need to be stored in a mapping. It suffices to just emit them as an event since the contract will never need to access the data.

[darioAnongba]

Hi!

Brilliant! I spent all day trying to understand this and I guess your answer is more or less what Monero does. I didn't know it was possible to use the Ethereum public key for this.

Quoting:

There is a transaction public key R. The sender knows the transaction private key r.

The sender computes the shared secret as rA, where A is your public view key (A is told to the sender because it's the first half of your wallet address).

When you receive the transaction, you don't know r, but you do know your private view key a. You can thus compute aR, which is the same as rA. This is called the shared secret.

It works because A = aG, and R = rG, and so aR == arG == rA.

With your solution we have R = rG, ss = rP == Rp. Is that what you implemented in your RingCTToken.sol ?

It seems that in earlier implementations of Ethereum it was possible to compute the public key P by calling eth_getTransactionReceipt and retrieving the v, r, s values. Apparently this has been removed so the only way I can think of is to create an initial transaction to store P before being able to use the platform.

Thank you again!

[darioAnongba]

Also, a more technical question. I don't understand why you define encrypted_data as an array of size 3. Is the third element the IV ? If so, is it necessary to encrypt it ? In your .py files, you define a function to_scalar():

def to_scalars(self):
    from Crypto import Random
    rand = Random.new();
    return [bytes_to_int(rand.read(1) + self.message[:31]) % Ncurve,
            bytes_to_int(rand.read(1) + self.message[31:62]) % Ncurve,
            bytes_to_int(rand.read(14) + self.message[62:] + self.iv) % Ncurve]

Is that the function you use to generate the encrypted_data array ?

[solidblu1992]

With your solution we have R = rG, ss = rP == Rp. Is that what you implemented in your RingCTToken.sol ?

It's close. So in RingCT, the receiver has two key pairs: spend (S=sG1) and view (V=vG1). I use two shared secrets in RingCT, one for picking the stealth address and one for the AES key. Both are generated from the same DHE point (R=rG).

ss_aes = keccak256(rS) = keccak256(sR)

ss_stealth = keccak256(rV) = keccak256(vR)
DestPubKey = (ss_stealth)(G1) + S
DestPrivKey = (ss_stealth + s) mod Ncurve

Feel free to ignore ss_stealth as you won't need it, but I included it for clarity and for fun :-)

Also, a more technical question. I don't understand why you define encrypted_data as an array of size 3. Is the third element the IV ? If so, is it necessary to encrypt it ?

The IV is the initialization vector for the particular form of AES that I'm using. It's just a random bit string, but it's needed in order to decrypt the AES data.

Is that the function you use to generate the encrypted_data array ?

Actually, I don't think I ever use to_scalars(). I created that function in order to experiment embedding the encrypted data into the pedersen commitment range proof. But, I never actually used it anywhere. Converting the AES data into uint256's is much more straight forward:

encrypted_data[0] = message[:32]
encrypted_data[1] = message[32:]
encrypted_data[2] = iv

I do this in RingCT.Print_MEW(), for example.

[darioAnongba]

Hi, again!

I have some questions about your encryption method.

1. In order for a third party to be able to see the amounts, what solutions do I have apart sending them my private key or directly the value and blinding factor off-chain?
2. If r is a random number, then I have to store it right? If I lose it then I am not able to see the amounts I myself sent, or do I have to create a shared secret for myself (the remaining value) and encrypt the data using my own public key?. What if I use my private key as r? Would that harm security? Sorry for all those questions, I am fairly new in cryptography.
3. If I directly use your implementation of RingCTToken, what would be the differences with my system? I'm starting to think that everything I want to do is possible using your RingCTToken implementation. I guess it would be possible to identity individuals with their S and V (public spend and public view).

Thank you for all your help !

[solidblu1992]

In order for a third party to be able to see the amounts, what solutions do I have apart sending them my private key or directly the value and blinding factor off-chain?

You could modify the above solution to use a multi-party cyclical Diffie-Hellman exchange. Picture parties with public keys A=aG, B=bG, and C=cG. The cycle will go A->B->C->A (though the sequence is arbitrary):

1. A calculates aC and stores the value on chain (to be used by B)
2. B calculates bA and sends the value on chain (to be used by C)
3. C calculates cB and sends the value on chain (to be used by A)
4. A, B, and C then multiply the relevant values by their private key (a[cB] = b[aC] = c[bA] = [abc]G) and hash the point to get the shared secret.

Note that in this case no party has to remember any data except for their private key as the relevant information to retrieve the shared secret is one of the points stored in steps 1-3.

An alternative way to do this which minimizes interaction between the parties is to not pass the keys in a cyclical manner. Assume A is a third party which needs to know the secret key but ideally doesn't need to be involved in ever transfer.

1. B calculates bA and stores the value on chain (to be used by C)
2. B calculates bC and stores the value on chain (to be used by A). Alternatively, C could accomplish the same task by storing cB.
3. C calculates cA and stores the value on chain (to be used by B)
4. Each party can now recover the shared secret point (A, B, C respectively): a(bC) = b(cA) = c(bA).

If r is a random number, then I have to store it right? If I lose it then I am not able to see the amounts I myself sent, or do I have to create a shared secret for myself (the remaining value) and encrypt the data using my own public key?. What if I use my private key as r? Would that harm security? Sorry for all those questions, I am fairly new in cryptography.

In the above solution, r won't be stored, it is ephemeral. The assumption here is that the sender won't ever need to retrieve the sent value and blinding factor as only the receiver can use them. On the other side, the receiver only needs to know their private key to retrieve the shared secret.

If the sender wants to maintain the shared secret, you could do the following, which now that I think about it is much simpler:

1. A calculates aB.
2. B calculates bA.
3. A and B then hash their points to retrieve the shared secret. In this case A and B just need to remember their own private keys and the public key of who they transacted with.

If I directly use your implementation of RingCTToken, what would be the differences with my system? I'm starting to think that everything I want to do is possible using your RingCTToken implementation. I guess it would be possible to identity individuals with their S and V (public spend and public view).

I think the biggest difference is that RingCTToken doesn't have a mechanism for sharing secrets among 3 or more parties. There's probably other differences, but I think you can work through them yourself.

Two things from my end:

1. Did you see Vitalik's comment on RingCTToken? His 2nd point is pretty relevant for minimizing gas costs.
2. I'm currently working on implementing Bulletproofs for RingCT. These will also reduce gas costs for proving positive commitments, especially if commitments can be batched together.

[solidblu1992]

Another option for the 3 party shared secret:

1. B and C create a shared secret.
2. A and B create a shared secret.
3. Secret from step 1 is encrypted from step 2 and sent to A by B.

[darioAnongba]

Wow what an answer! Thanks!

I guess that a 3-party shared secret won't be possible for me because of the involvement needed and the lost in performances that this would cause.

If the sender wants to maintain the shared secret, you could do the following, which now that I think about it is much simpler:

1. A calculates aB.
2. B calculates bA.
3. A and B then hash their points to retrieve the shared secret. In this case A and B just need to remember their own private keys and the public key of who they transacted with.

Yes, with this approach, every transaction between two parties will always use the same shared secret. Finding the shared secret would be similar to finding the private key so it's okay.

1. Did you see Vitalik's comment on RingCTToken? His 2nd point is pretty relevant for minimizing gas costs.
2. I'm currently working on implementing Bulletproofs for RingCT. These will also reduce gas costs for proving positive commitments, especially if commitments can be batched together.

Oh I wasn't aware of that post! I read it and learnt a lot of things about your code that I didn't understand earlier. Nice!

1. Yes it's always a good idea to think about game theory when facing a technical problem as sometimes, even though the system has some flaws, we can incentivize people not to exploit them because of risks or penalties. This is a good example of that.
2. Having an efficient implementation of a token with confidential transactions open the door for so many new ideas! And Bulletproofs are the key to doing it so I hope you succeed! I will keep an eye on your repo.

Cheers

[solidblu1992]

I guess that a 3-party shared secret won't be possible for me because of the involvement needed and the lost in performances that this would cause.

Is this true even with the last solution I posted? See below:

Another option for the 3 party shared secret:

1. B and C create a shared secret.
2. A and B create a shared secret.
3. Secret from step 1 is encrypted from step 2 and sent to A by B.

Or were you saying that this isn't a true 3-party shared secret, though 3 parties do all have the same secret?

I would think this solution is quite viable since the secrets generated in steps 1 and 2 are very ad-hoc and simple:

1. Step 1's shared secret is generated from bC = cB. No data is really shared between B or C
2. Step 2's shared secret is generated from aB = bA. Again, no data is really shared between A and B
3. B creates ss1_encrypted with ss2 and stores it on chain for A to retrieve later.

Also, I think have the python side working for Bulletproofs now.

[darioAnongba]

Nice for the bulletproof implementation! That was quick

[solidblu1992]

FYI, Bullet Proofs are now functional on Rinkeby. But the code is still dirty (especially the Python).

I'm sure the gas costs can be improved further, but right now there is definitely substantial improvement ranging from a 12% to 59% reduction depending on the number of commitments and proofs batched together.

8 Bit Tests (256 possible values)

• TX01: Standard Borromean Range Proof, 4-base4 bits, 2.020MGas
• TX02: 1-Commitment Bullet Proof, 8-base2 bits, 1.771MGas
• TX03: 2-Commitment Bullet Proof, 8-base2 bits, 2.831MGas (1.415MGas per commitment)
• TX04: 4-Commitment Bullet Proof, 8-base2 bits, 4.865MGas (1.216MGas per commitment)
• TX05: 2x 1-Commitment Bullet Proofs, 8-base2 bits, 3.071MGas (1.536MGas per proof and commitment)
• TX06: 4x 1-Commitment Bullet Proofs, 8-base2 bits, 5.161MGas (1.290MGas per proof and commitment)
• TX07: 2x 2-Commitment Bullet Proofs, 8-base2 bits, 4.489MGas (2.245MGas per proof, 1.122MGas per commitment)

16 Bit Tests (65,536 possible values)

• TX08: Standard Borromean Range Proof, 8-base4 bits, 3.965MGas
• TX09: 1-Commitment Bullet Proof, 16-base2 bits, 2.708MGas
• TX10: 2-Commitment Bullet Proof, 16-base2 bits, 4.609MGas (2.305MGas per commitment)
• TX11: 2x 1-Commitment Bullet Proofs, 16-base2 bits, 4.252MGas (2.126MGas per proof or commitment)
• TX12: 2x 2-Commitment Bullet Proofs, 16-base2 bits, 6.650MGas (3.325MGas per proof, 1.662MGas per commitment)

32 Bit Test (4,294,967,296 possible values)

• TX13: Standard Borromean Range Proof, 16-base4 bits, FAIL (exceeds 7.200MGas)
• TX14: 1-Commitment Bullet Proof, 32-base2 bits, 4.478MGas

[solidblu1992]

I probably should have just waited to tell you until I put it into Excel, but if you are interested in the data it's here.

[darioAnongba]

Good job ! I'll try and use your implementation to replace range proofs, thanks !

BTW, are you doing this as a job, for fun, for research?

[solidblu1992]

For fun!