Create a FHE ECDSA signature tutorial

[aquint-zama]

Winners

🥇 1st place: A submission by Tetration-Lab

---

Overview

Create a tutorial demonstrating how to generate a ECDSA signature on clear data with an FHE-encrypted private key

Description

The goal of this bounty is to implement the ECDSA signature algorithm, used on the Ethereum blockchain, in FHE.
It uses the curve secp256k1. From an FHE encrypted private key and a clear message, the provided algorithm should
be able to return a signature that (potentially after being decrypted by the FHE private key) can be verified in clear with the EC public key.

This bounty does not expect EC key generation, or Signature validation function.

We expect your PR to comply with the following:

• Input size is fixed to 32 bytes
• Private Key size is fixed to 32 bytes

Your PR should comply with the following:

• Create the script tfhe/examples/secp256k1-signature.rs
• Create the tutorial tfhe/docs/tutorial/secp256k1-signature.md

Prizes

🥇 1st place: €10,000
🥈 2nd place: €3,500
🥉 3rd place: €1,500

Rewards are attributed based on code quality and speed performance on the Amazon EC2 M6i instances.

Related links and references

• TFHE-rs documentation
• TFHE-rs contribution guide
• secp256k1 implementation example
• secp256k1 unofficial test vectors

Application

Are you interested to work on this bounty? Apply directly to this bounty by opening an application here.

Questions?

Do you have a specific question about this bounty? Join the live conversation on the FHE.org discord server here. You can also send us an email at: [email protected]

[mortendahl]

Note that neither s nor r making up the signature need to be encrypted. In fact, if they are then we’ll next want to decrypt them to obtain a plaintext signature. However, both the private key and the randomness sampled for the signature should be encrypted.

In summary, the inputs are:

• the message in the clear
• an encrypted private signature key
• an encrypted nonce

Note also that we do not need deterministic ECDSA (RFC 6979), so applying a hash function to the private key is not required (which would be expensive).

[georgio]

I think this comment is misleading, because it's impossible that $s$ would not need to be an FHE ciphertext...

Note that neither s nor r making up the signature need to be encrypted. In fact, if they are then we’ll next want to decrypt them to obtain a plaintext signature. However, both the private key and the randomness sampled for the signature should be encrypted.

In summary, the inputs are:

• the message in the clear
• an encrypted private signature key
• an encrypted nonce

Note also that we do not need deterministic ECDSA (RFC 6979), so applying a hash function to the private key is not required (which would be expensive).

[mortendahl]

I think this comment is misleading, because it's impossible that s would not need to be an FHE ciphertext...

To clarify, it is not a requirement from our side that s is a ciphertext, but there may be technical reasons for this, which is also acceptable.

[yoyoismee]

is it ok if we take both encrypted $nonce$ and $nonce^{-1}$ as input to speed up the compute?
I don't think this effect any security and user would be able to easily compute $nonce^{-1}$ from their plaintext $nonce$.

[mortendahl]

is it ok if we take both encrypted $nonce$ and $nonce^{−1}$ as input to speed up the compute?

Such a solution would still be interesting to us, but we would consider it partial and not subject to the full bounty.

[JoseSK999]

is it ok if we take both encrypted nonce and nonce−1 as input to speed up the compute?

Such a solution would still be interesting to us, but we would consider it partial and not subject to the full bounty.

Hi, I have researched a bit but it seems that computing the multiplicative modular inverse homomorphically is not practical. If we use the fast exponentiation method to get nonce^p-2 mod p which appears to be one of the fastest ways of computing the modular inverse (thanks to Fermat's little theorem), it will require 256 ciphertext squarings (i.e. ciphertext multiplications) plus the modular reduction for each, plus 196 more multiplications and reductions. This means that >99% of the signing time will be spent in the nonce inverse computation.

An alternative method is the extended euclidean algorithm but again it would require many ciphertext divisions and multiplications.

[mortendahl]

Hi @JoseSK999,

Computing the random curve point ($R = k * G$ in this description) is also an expensive operation, and a solution to that (e.g. binary exponentiation over an elliptic curve) can also be used to compute the inverse (as $k^{-1}$ = $k^{n-2}$ mod $n$).

[JoseSK999]

@mortendahl I don’t understand, in this bounty it’s specified that EC key generation is not required 🤨. My point is that computing the modular inverse in FHE seems to be extremely slow simply because of the available algorithms (e.g. the exponentiation method) and I believe the best option is pre-computing it in the client side

[georgio]

Why does the nonce need to be encrypted? Can't we just have a scalar-ciphertext operations?

[mortendahl]

I don’t understand, in this bounty it’s specified that EC key generation is not required

Not sure I follow @JoseSK999. What do you mean by key generation? Above I was referring to step 3 in ECDSA Sign.

[mortendahl]

Why does the nonce need to be encrypted?

@georgio the nonce needs to be kept secret since otherwise there are attacks exposing the secret key.

[JoseSK999]

Not sure I follow @JoseSK999. What do you mean by key generation? Above I was referring to step 3 in ECDSA Sign.

@mortendahl computing the nonce point R is the same as computing a public key. In this bounty it’s specified that Elliptic Curve key generation is not required. R should be pre-computed then.

[mortendahl]

R should be pre-computed then

$R$ is derived from the random nonce so I don't see how it can be precomputed: a new values needs to be sampled for every signature.

[JoseSK999]

It’s pre-computed in the client side, instead of computed homomorphically I mean (using an external impl of EC public key generation)

[RasoulAM]

Is there any restriction on how the inputs are encoded?

[mortendahl]

It’s pre-computed in the client side, instead of computed homomorphically I mean (using an external impl of EC public key generation)

There isn't always a traditional client side in some of the interesting applications, which is why we're pushing back on this direction.

[mortendahl]

Is there any restriction on how the inputs are encoded?

@RasoulAM I think we can be flexible here. Ideally using parameters MESSAGE_2_CARRY_2. Do you have something specific in mind?