Introduction to Threshold Signature

While working on our cross-chain communication protocol, we come across the fact that in the world of cryptocurrencies, there is a number of cryptography primitives and tools that are heavily used, and still, only a few people really understand the underlying principles of their work.

Others either understand very vaguely or simply do not know about the existence of such tools. So we decided to start a series of articles to cover all those cryptography-related topics in a friendly manner.

Introduction
We begin with one of the main mechanisms used in our protocol: MPC (Multi-Party Computation). MPC allows a group of parties to create a digital signature in such a way that:

1. None of the parties has access to the secret needed to create the signature.
2. Only a quorum (a part of parties) participates in signing.

In the case of MPC, the parties create a signature off-chain that makes it possible to sign any data, including transactions. For the protocol, such a signature is indistinguishable from a signature created by a single user.

The MPC is a very young mechanism by the standards of cryptography. However, it is based on cryptographic algorithms that have been tested for decades.

In a series of articles we will explain how MPC works. We will talk about what a digital signature is, how to share secret keys between parties, and how to sign data without having an entire secret key in one place.

In the first article, we’ll start with the basics: a digital signature.

Digital Signature Standard Scheme
What problems does a common signature or a digital signature solve? Historically, there are two problems:

1. Signer authenticity: to ensure that the message is signed by exactly that person who introduced themselves as the signer.
2. Document integrity: to ensure that the message has not changed since the signature was created.

And historically, every time you sign, you draw the same symbol: your common signature. The security of such a system is based on the fact that no one but you can reproduce this symbol in the right way. Consequently, one just has to look at the signature to insure its veracity. Thus, the signed document contains the following information: the document itself, the public identifier of the signer (usually it’s a name) and the signature itself. There are weak points of the common signature. The signature looks always the same, and it doesn’t change whatever you sign with it. Additionally, anyone who has a signature sample can reproduce the signature.

So, the common signature does not solve the problems perfectly.

The digital signature is a way to solve the problems using modern computing technology.

A different approach is used in the case of digital signatures. The message, the signature, and the public identifier of the signer are numbers¹ linked by a mathematical formula². The formula allows to unambiguously establish that for the given message, only the one who possesses the given public identifier created the given signature. And there is no other way. Please note that a digital signature changes depending on the message signed with it.

We should have one more number to have the mathematical formula mentioned above working. Only the one who creates the signature knows this number. This secret number allows the owner to create a digital signature which guarantees the connection between the message and the signer’s public identifier. Asymmetric Cryptography (also called Public-Key Cryptography) studies such mathematical formulas.

Thus, when you create a digital signature, two positive numbers are associated with you as the signer. One is called the secret key (or private key, thus public-key cryptography), and the other is called the public key. There is a one-way bond between these numbers: you can derive the public key from the secret key using a mathematical formula, but never vice versa.

The public key is a semblance of your name in a document signed with a common signature. This information about you is publicly known. On the other hand, only you should know the secret key.

A secret key is used to create a digital signature, so the digital signature shows the signer’s authenticity. In its turn, the authentication is based on whether or not the correct secret key was used. For authentication, one should have the signer’s public key, the signed message, the signature, and the formula binding the signed message and the secret key.

Thus, a digital signature routing consists of three parts:

1. The KeyGen algorithm is used to create a pair of numbers: a public key and a secret key,
2. The Sig algorithm is used to create a signature, using a message and the secret key,
3. The Ver algorithm is used to verify the signature using the signature, the signed message, and the public key. Next, we will look at all three parts in detail.

Key generation with KeyGen algorithm
The key generation algorithm creates a pair of keys (sk, pk)=KeyGen_( ), where sk stands for the secret key (private key), and pk stands for the public key. Whenever you use the algorithm, you get a new pair of keys.

A secret key is just a random number. A public key can be easily obtained by applying a pre-defined one-way compression function to the secret key. The one-way compression function does not allow recovery of the input parameters by output results. So, we can safely share our public key without risking compromising our secret key.

Modular exponentiation is a classic example of a one-way transformation.

Common exponentiation is reversible (a is a fixed number). If we know pk and a, we can derive that

Figure 1 illustrates this one to one correspondence: each value of sk corresponds to a single value of pk and vice versa.

You will get a one-way transformation if you expand exponentiation with a modulo operation. The resulting algorithm would be

where q is a positive integer number. Modulo (denoted by mod in the formula above) is an operation that returns the remainder when divided by q. For example, 25 mod 10=5. This operation is irreversible, which is illustrated by Figure 2.

Let us consider an example where pk=4, a=2, q=7.

If we try to solve the equation

we will realize that it has multiple solutions. sk can be equal to 2, because 2²=4, 4 mod 7=4. But it also can be equal to 5, because 2⁵=32

32 mod 7 = (28 + 4) mod 7 = (4∙7 + 4) mod 7 = 4 (Figure 2).

Another example is a clock face. We measure hours by modulo 12, and seconds by modulo 60. Imagine someone saying, “when I looked at my clock, it was 1 PM, and the next time it was 3 PM”. Can you derive how much time exactly passed between these two events? It could be two hours, 14 hours (2+12=14), 26 hours (14+12=26), or infinitely more. Operation mod 12 erases this information.

Modulo operation is the simplest computational operation that effectively screens the initial parameters. It is widely used in all common one-way transformations combined with other functions. In the example above, we combined it with a power function. We will get more complicated and interesting examples when covering the ECDSA algorithm.

Signature generation with Sig algorithm
The signature generation requires two components: the secret key sk and the message we want to sign. The message can be of arbitrary length, and this might be inconvenient. Cryptographic hash functions can help us with this.

A cryptographic hash function transforms a sequence of symbols into a number within some range. For example, it can be a number that can be encoded with only 256 bits. This number is called a hash, and the transformation process is called hashing. The hash function always returns the same output for the same input sequence. However, the slightest change in the message changes its hash so much that it becomes impossible to associate changes in the message with changes in the hash. The usage of hash functions not only simplifies the process but also guarantees the integrity of the signed message that the message has not been changed since the signature creation.

For example, the cryptographic hash function sha256 returns numbers in the range from 0 to 2²⁵⁶-1,. For the input string, “I promise to give you $5,000”, sha256 will return

be657fcad7933b87869835c571b60ff1444f68179326e7754c3d99babf919995

(this is a number in hex format). If we add an extra 0 to the message like this: “I promise to give you $50,000”, the hash will change to

90222db12a4a59f8d083e3cf88bf22dab15385c9946f4526a67855e6a5ff0737

To sum it up: the signature creation algorithm takes a secret key sk and a number m (the message hash) for input and returns a number s.

This number is a signature s=Sig(sk, m). In the following chapters, we will continue covering the details of the cornerstone of cryptocurrencies — the ECDSA signature algorithm.

Signature verification with Ver algorithm
Algorithms KeyGen and Sig generate digital signatures. Algorithm Ver is used for signature validation.

This algorithm requires the public key pk of the signer, the message hash m that was signed, and the signature s.

The Ver algorithm returns 1 (TRUE) if the signature is correct and 0 (FALSE) otherwise.

Successful verification can guarantee that

1. The public key pk matches the secret key sk used for the signature generation. This means that the person claiming to be the signer is the actual signer of the transaction.
2. The message that was signed (the hash) was not changed.

Correspondingly, failed signature verification means that at least one of the following two facts comes true:

1. The secret key sk does not match the public key pk. Someone is impersonating the message signer.
2. The message does not match. The signer did not sign this exact message.

There is no way to figure out what exactly is invalidating the signature with the Ver algorithm.

The algorithm does not determine which of these conditions caused the invalidity of the signature.

In our next article, we will talk about the algorithm ECDSA and elliptic curves.

---

Numbers¹, formula²: we will explore these concepts further in our articles.

---

Authors:

Alexey Troshichev Main Concept

Artem Fomichev Math Expert

Inga Pashentseva Editor

Alexander Polovian Fact Checking

---

Catch up with us on social media

Twitter | Telegram | Discord | Facebook | Instagram | Linkedin