Skip to content

Cryptography

This section explores the process of multi-party computation (MPC) of DSAs used within bridging system: secp256k1, secp256k1-schnorr, and ed25519.

The ellipsis ... indicates that the computation continues with the result of the expression in another participant's environment, highlighting the collaborative nature of MPC.

secp256k1

P = G·d₁+...+G·dₙ mod q
R = G·k₁·...·kᵤ mod q
I = eₚ(m·n⁻¹+Rₓ·d₁ mod q)+...+eₚ(m·n⁻¹+Rₓ·dₙ mod q)
S = dₚ(I·k₁⁻¹·...·kᵤ₋₁⁻¹)·kᵤ mod q
Overall MPC signature complexity: from O(n+2u) to O(3n)

The secp256k1 curve employs a multiplicative aggregation of private keys to generate the aggregated public key P. This is achieved by multiplying the group generator G with each participant's private key d₁, d₂, ..., dₙ and reducing the result modulo q, the group order. Similarly, the main signature component R is generated by multiplying G with each participant's nonce scalar k₁, k₂, ..., kᵤ and reducing modulo q.

The intermediate signature component I involves a more complex process using Paillier encryption. Each participant contributes to I by encrypting a value that includes the message hash scalar m, scaled by the inverse of the participant count n⁻¹, and combined with the x-coordinate of R (Rₓ) multiplied by their private key dᵢ. The Paillier encryption function eₚ ensures that these contributions can be aggregated homomorphically.

Finally, the main signature component S is derived by decrypting the aggregated intermediate value I, scaled by the inverses of each participant's nonce scalars k₁⁻¹, k₂⁻¹, ..., kᵤ⁻¹, and reducing modulo q. This step leverages the Paillier decryption function dₚ to reveal the final signature component.

To ensure that the addition of partial S and multiplication by k remains within the range of Paillier modulus, it is important to note that u may be less than n. Current implementation of computation of possibly reduced count of participants u contributing nonces to final signature, followed by computation of Paillier key size b (bits) in range of [2048, 8192] is as follows: 

let additions = participants;
let min_bits = 2048;
let max_bits = 8192;
let step_bits = 256;
let nonce_participants = Math.min(additions, 1 + Math.floor((max_bits - step_bits - additions - 1) / step_bits));
let key_bits = Math.ceil(Math.max(min_bits, Math.min(max_bits, 1 + additions + step_bits + step_bits * (nonce_participants - 1))) / 8.0) * 8.0;

[nonce_participants, key_bits]

Key Variables and Functions

  • P: Aggregated public key generated through multiplicative aggregation of private keys.
  • R: Main signature component 1, derived from nonce scalars.
  • I: Intermediate signature component, encrypted using Paillier encryption.
  • S: Main signature component 2, obtained through decryption and scaling.
  • G: Group generator used as a base point for elliptic curve operations.
  • q: Group order, ensuring the results of elliptic curve operations remain within a finite field.
  • m: Message hash scalar or message bytes, incorporated into the signature generation process.
  • n: Count of participants involved in the MPC protocol.
  • u: Possibly reduced count of participants, used in the generation of R.
  • k₁₋ₙ: Participant nonce scalar array of n elements (scheme-specific nonce generation)
  • k₁₋ᵤ: Participant nonce scalar array of u elements
  • d₁₋ₙ: Participant private key scalar array of n elements
  • eₚ: Paillier encryption function (homomorphic operations on the result of eₚ are non-modulo based)
  • dₚ: Paillier decryption function (operations on the result of dₚ are following standard modulo reduction)

secp256k1-schnorr

P = G·d₁+...+G·dₙ mod q
R = G·k₁+...+G·kₙ mod q
S = (k₁+hₚ(R||P||m)·d₁·p)+...+(kₙ+hₚ(R||P||m)·(dₙ+t)·p) mod q
Overall MPC signature complexity: O(2n)

The secp256k1-schnorr variant uses an additive aggregation of private keys to generate the aggregated public key P. This is achieved by adding the results of multiplying the group generator G with each participant's private key dᵢ and reducing modulo q.

Similarly, the main signature component R is generated by adding the results of multiplying G with each participant's nonce scalar kᵢ and reducing modulo q. This step ensures that each participant contributes uniquely to R.

The main signature component S involves a more complex process using a scheme-specific hash function hₚ. Each participant contributes to S by adding their nonce scalar kᵢ to the product of the hash of the concatenated values of R, P, and m (hₚ(R||P||m)), their private key dᵢ, and the y-coordinate parity p. Additionally, a public key tweak scalar t is incorporated into the last term of the summation. This ensures that the signature component S is uniquely determined by the contributions of all participants.

The tweak t is a Bitcoin-specific option designed to ensure compliance with Taproot signatures. This adjustment helps in achieving enhanced privacy and security features specific to the Bitcoin network.

Key Variables and Functions

  • P: Aggregated public key generated through additive aggregation of private keys.
  • R: Main signature component 1, derived from nonce scalars.
  • S: Main signature component 2, incorporating a hash function and parity information.
  • G: Group generator used as a base point for elliptic curve operations.
  • q: Group order, ensuring the results of elliptic curve operations remain within a finite field.
  • p: y-coordinate parity of P (1 if even, -1 if odd), incorporated into the signature generation process.
  • t: Public key tweak scalar or zero, added to the last term of the summation in S.
  • m: Message hash scalar or message bytes, incorporated into the signature generation process.
  • n: Count of participants involved in the MPC protocol.
  • k₁₋ₙ: Participant nonce scalar array of n elements, ensuring unique contributions to the signature.
  • d₁₋ₙ: Participant private key scalar array of n elements, aggregated to form the public key.
  • hₚ: Scheme-specific hash function

ed25519

P = G·d₁+...+G·dₙ mod q
R = G·k₁+...+G·kₙ mod q
S = (k₁+hₚ(R||P||m)·d₁)+...+(kₙ+hₚ(R||P||m)·dₙ) mod q
Overall MPC signature complexity: O(2n)

The ed25519 curve also employs an additive aggregation of private keys to generate the aggregated public key P. This is similar to the secp256k1-schnorr variant, achieved by adding the results of multiplying the group generator G with each participant's private key dᵢ and reducing modulo q.

The main signature component R is generated by adding the results of multiplying G with each participant's nonce scalar kᵢ and reducing modulo q. This ensures that each participant contributes uniquely to R.

The main signature component S involves a process using a scheme-specific hash function hₚ. Each participant contributes to S by adding their nonce scalar kᵢ to the product of the hash of the concatenated values of R, P, and m (hₚ(R||P||m)) and their private key dᵢ. This ensures that the signature component S is uniquely determined by the contributions of all participants.

Key Variables and Functions

  • P: Aggregated public key generated through additive aggregation of private keys.
  • R: Main signature component 1, derived from nonce scalars.
  • S: Main signature component 2, incorporating a hash function.
  • G: Group generator used as a base point for elliptic curve operations.
  • q: Group order, ensuring the results of elliptic curve operations remain within a finite field.
  • m: Message hash scalar or message bytes, incorporated into the signature generation process.
  • n: Count of participants involved in the MPC protocol.
  • k₁₋ₙ: Participant nonce scalar array of n elements, ensuring unique contributions to the signature.
  • d₁₋ₙ: Participant private key scalar array of n elements, aggregated to form the public key.
  • hₚ: Scheme-specific hash function