Digital Signature Scheme

Technical Summary For Cryptographers

We give a succinct summary of the cryptographic protocols used in the SDK:

• For ECDSA we use DKLs19.
  • We used SoftSpokenOT to realize the $\mathcal{F}^{\eta}_{\sf COTe}$ functionality.
  • We used MRR21 to realize the $\mathcal{F}^{2,kn_{\mathcal{C}},{\mathcal{L}}}_{\sf OT-\bar{1}}$ to realize endemic 1-out-of-2 base OT of batch size $k\cdot n_{\mathcal{C}}$.
• For EdDSA we use FROST.
• We use BLAKE3 official Rust crate as a pseudorandom generator/function.

What is a Digital Signature Scheme?

A digital signature scheme realizes, in a sense, classical (i.e. "non-digital", handwritten) signatures but with stronger security guarantees. Unlike classical signatures, we wish that only a certain entity who owns some secret key ($\sf sk$) to be able to authorize some message $\sf m$ by producing a signature $\sf s$ which can later be verified by any entity using a public key ($\sf pk$).

More explicitly, a signature scheme is a set of three algorithms: $\sf KeyGen, Sign, Verify$ such that:

• ${\sf KeyGen}$ outputs a pair $\sf (sk,pk)$ where $\sf sk$ is a secret key, held by the key generator while $\sf pk$ is a public key, that is, it is published to the public.
• ${\sf Sign(sk,m)}$ is a method taking a secret key $\sf sk$ and a message $\sf m$ and outputs a signature $\sf sig$.
• ${\sf Verify(pk,m, sig)}$ is a method taking a public $\sf pk$, a message $\sf m$ and a signature $\sf sig$ and verifies whether $\sf sig$ was created by the owner of $\sf sk$. If the verification succeeds it returns $\sf success$ and if it fails it returns $\sf fail$.

A signature scheme should be both correct and secure that is:

• Correctness means that a signature generated by an "honest" signer (i.e. a signer who knows the secret key $\sf sk$) should always be successfully verified. In mathmatical notation it means that for all $\sf (sk,pk)$ output by $\sf KeyGen$ and for all message $\sf m$ we have:
  $$\sf Verify(pk,m, Sign(sk,m)) = success$$
• Security means that a malicious entity who doesn't know the secret key $\sf sk$ and wishes to sign some predetermined message $\sf m^*$ should not be able to do this ¹ even if it is being given signatures of other messages of its choice.²

caution

Notice that the security guarantees do not hold against the scenario where the secret key falls into the hands of a malicious entity. This is a key reason to use Sodot MPC SDK.

Types of Digital Signature Schemes

Along the years a large number of digital signature schemes have been introduced and in the past few decades two main signature scheme have become prevalent in wide range of use cases:

• Elliptic Curve Digital Signature Algorithm (ECDSA)
• Edwards-curve Digital Signature Algorithm (EdDSA)

Indeed, each of these schemes has its own triple of $\sf KeyGen, Sign, Verify$ algorithms. We will not be elaborting on these two schemes here, the interested reader can follow the links above for futher reading.

note

While these two digital signature algorithms have similar names, they are very different from one another.

Feature

Sodot MPC SDK supports both the ECDSA and EdDSA schemes.

What is a Threshold Signature Scheme?

As we've seen, the security of the signature scheme holds as long as the secret key is stored securely. But what does it even mean "securely" in this context? Well, the private key should be both secret and persistent.

• Secret in the sense that no malicious entity should be able to retrieve the key.
• Persistent in the sense that the entity who is eligible to use the key is indeed able to use it.

One way to ensure these two properties is by storing the secret key in a Hardware Security Module (HSM). This, however, introduces a single point of failure, as in the case of a loss or corruption of the HSM, the key material stored inside of it is lost. Another, more engineering-oriented argument against HSMs is that they introduce a scalability bottleneck as they possess limited processing capacity.

To address the issues above, cryptographers have come up with threshold signature schemes (TSS). These signature schemes operate in a distributed manner, between a set of $N$ clients with respect to a predetermined threshold $T$ where $T \leq N$. Informally, the secret key is split between the $N$ clients such that any subset of at least $T$ of them is capable of signing any message.

Slightly more formally, we say a signature scheme is a threshold signature scheme if on top of the existing $\sf KeyGen, Sign, Verify$ two additional algorithms are introduced:

• $\sf DistributedKeyGen$ is a distributed algorithm between the $N$ clients resulting in a public key $\sf pk$ and $N$ secret key shares ${\sf sk_1,\ldots,sk}_N$ where client number $i$ holds $\sf sk_i$.
• $\sf DistributedSign(sk_{i_1},\ldots,sk_{i_T}, m)$ is a distributed algorithm taking place between $T$ clients with secret shared $\sf sk_{i_1},\ldots,sk_{i_T}$ resulting in a signature $\sf sig$ on a message $\sf m$.

Similarly, we require both correctness and security:

• Correctness for every $N$ and every $1\leq T\leq N$, and every public key $\sf pk$ and secret key shares $\sf sk_1,\ldots,sk_N$ generated by $\sf DistributedKeyGen$ and every subset of $T$ secret shared $\sf sk_{i_1},\ldots,sk_{i_T}$ and every message $m$ it holds that:
  $$\sf Verify(pk, m, DistributedSign(sk_{i_1},\ldots,sk_{i_T},m)) = success$$
• Security every malicious entity holding less than $T$ secret shares should not be able to sign a predetermined message $m^*$ even if being given signatures of other messages of its choice.

caution

The security guarantees of the TSS do not hold against the leakage of $T$ secret shares. Therefore, $T$ should be set sufficiently high.

caution

Generating a valid signature is impossible if $N-T$ shares have been lost. Therefore, $T$ should be set not too close to $N$.

How should $T$ be set with respect to $N$?

The above two notes result in a somewhat contradictory conclusion, that is:

• We want persistency, so we can't have $T=N$ as in this extreme case, the loss of a single key share implies inability to sign any message.
• We also want security, se we can't have $T=1$ as in this extreme case, the loss of a single key share implies loss of all security guarantees.

Therefore, setting $T$ somewhere in the middle makes most sense in practice.

Feature

Sodot MPC SDK supports both ECDSA and EdDSA TSS for all values of threshold $T$ and any number of participants $N$.

---

1. Cryptographers usually refer to this "inability" as being able to do this with very small probability.↩
2. This notion is known as "EUF-CMA" security.↩