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: bounty@zama.ai

[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$).