ECDSA Signing Process

The Process of ECDSA Signing in a Two-Party System

The Elliptic Curve Digital Signature Algorithm (ECDSA) involves a two-party process where neither party knows the private key $x$, yet they can jointly create a signature on a message $m$. Here's an overview of the ECDSA signing function:

1. Nonce Generation and Computation:

   • A random nonce $k$ is chosen, and $R=k⋅G$ is computed.

   • The "x-coordinate" of the elliptic-curve point $R$ is denoted as $r$.

2. Signature Computation:

   • The signature component $s$ is calculated as $s=k−1⋅(H(m)+r⋅x)modq$.

3. Signature Output:

   • The signature is output as a pair $(r,s)$.

Additively Homomorphic Encryption in ECDSA

• Encryption Type: The process uses additively homomorphic encryption, which allows for encrypted values to be efficiently added or multiplied by a scalar without decryption. Paillier encryption, a common form of this encryption, is often used.

Two-Party Computation Steps

• Key Generation:

  • Parties choose random $1x1$ and $2x2$ and exchange $Q1=x1⋅G$ and $Q2=x2⋅G$. Commitment schemes are used for security.

  • $1P1$ generates a Paillier key-pair $(pk,sk)$ and sends $ckey​=Encpk​(x1)$ to $2P2$, along with a zero-knowledge proof.

• Signature Generation on Message $m$:

  • Parties independently generate $1k1$ and $2k2$, and exchange $R1=k1⋅G$ and $R2=k2⋅G$.

  • The nonce $k$ and $R$ are set as $k=k1⋅k2$ and $R=k1⋅R2=k2⋅R1$.

  • $2P2$ computes a "partial signature" using the homomorphic properties of the encryption, performing a series of encrypted operations.

  • $1P1$ decrypts the received ciphertext, multiplies it by $1−1k1−1​$ to obtain $s$, and verifies the signature $(r,s)$.

Security Considerations

• Protection Against Private Key Exposure: The protocol ensures neither party knows $k$ or the private key $x$.
• Handling Corrupt Parties: If $2P2$ is corrupt, it can provide incorrect encryption, but since $1P1$ verifies the signature first, no advantage is gained by $2P2$ from this.