Introduction to Threshold Signing (TSS) and other cryptographic primitives

Introduction

Hello! Working in DeFi, we often come across the fact that in the world of cryptocurrencies, tools are actively used, the principle of which is understood by a few users. Everyone else either understands very vaguely, or simply does not know that such tools exist. In order to change the status quo, we, the Symbiosis team, will be popularly explaining how and what our protocol works on and why we think it’s so cool!

We will start with one of the main mechanisms that is used in our protocol – MPC (multi-party computation). This mechanism makes it possible for a group of participants to create a digital signature in such a way that

  1. Neither participant has access to the secret that allows the signature to be created.

  2. To create a signature, not all participants are needed, but only part of a group of participants – a quorum.

In the case of MPC, the creation of a signature by participants occurs off-chain, which allows you to sign any kind of data, including transactions. For the protocol, such a signature is indistinguishable from a normal signature created by a single user.

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

We decided to write a series of articles in which we will explain how MPC works. In these articles, we will consistently talk about what a digital signature is, how to securely share secret keys between participants, and how you can sign data without collecting the secret key in one place.

In the first article, we will start with the simplest – we will figure out what a digital signature consists of and why it is needed.

Standard Digital Signature Scheme

What tasks are digital signatures used for? Historically, these are 2 tasks:

  1. Ensure authenticity – ensure that the message is signed by the person who identified himself as the author.

  2. Ensure integrity – ensure that the message has not changed since the signature was created.

And just like historically, every time you need to put a regular signature, you draw the same character. The security of such a system is based on the fact that no one except you can reproduce this symbol as it should be. Accordingly, to check that the signature was put by you, just look at it. And the signature does not change in any way from what it signs. In total, a signed document carries the following information: the document itself, the public identifier of the signatory (most often the name) and the signature itself. Anyone who has a sample signature can reproduce such a signature.

Thus, the usual signature solves the tasks set not ideally.

A digital signature is a way to solve tasks with the help of modern computing technologies.

In the case of digital signatures, a different approach is used. The message to be signed*, the signature and the public identifier are numbers** linked by a mathematical formula***, which makes it possible to unambiguously establish that for this message, this signature was created only by the person who has the given public identifier. And nothing else. That is, the signature changes depending on the message for which it is created.

——————————-
Numbers**, formula*** – we will reveal these concepts further in our publications
——————————-

In order for the mathematical formula mentioned above to work, one more number is needed, which only the one who creates the signature knows. It is this secret number that allows the owner to create a digital signature that guarantees the link between the message and the owner’s public identifier. Asymmetric Cryptography deals with the study of such mathematical formulas.

Thus, two positive integers are associated with you. One is called the secret key and the other is called the public key. These numbers are interconnected by a one-way relationship, that is, there is a mathematical formula that can be used to derive a public key from a secret key, but never vice versa.

The public key is the likeness of your name in a document signed with a regular signature. It is public information about you. Only you should know the secret key.

In order for the signature to reflect your identity (authenticity), a secret key is used when creating it (because only you know it). In turn, authentication is based on determining whether the correct secret key has been used or not. To carry out this verification, the public key, the signed message, the signature, and the relation that links it to the private key are sufficient.

Thus, the work of a digital signature consists of three parts:

  1. The KeyGen algorithm is used to generate a pair of numbers: public and private keys,

  2. The Sig algorithm is used to create a signature, using a message and a 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 3 parts in detail.

KeyGen Key Generation Algorithm

Each time the key generation algorithm produces a new pair of numbers sk, pk=KeyGen( ), where sk is the secret key and pk is the public key.

The number sk is chosen randomly, and the key pk is obtained by applying some predetermined one-way transformation to sk. One-way transformation is a mathematical operation that does not allow you to restore the input parameters from the results. As a result, the resulting number pk cannot be used to determine the original sk, so there is no danger in making pk a public value.

A classic example of a one-way conversion is exponentiation modulo. The usual exponentiation pk=ask, where a is some fixed number, is one-to-one: knowing pk, one can recover sk in a unique way. For example, if a=2, pk=16, then sk=4, because 16=24. This mutual uniqueness is visible on the graph: each value of sk corresponds to a single value of pk and vice versa (Fig. 1).

fig.1
fig.1

To achieve a one-sided transformation from the operation of raising to a power, you can additional operations by taking the module: pk=ask mod q, where q is another positive integer. This operation returns the remainder after division by the number q. For example, 25 mod 10=5. Taking “mod” immediately kills the mutual uniqueness, because knowing the remainder, the dividend cannot be restored.

fig.2

If, for example, we take pk=4, a=2, q=7, then from the relation 4=2sk mod 7 the number sk cannot be uniquely restored. It can be equal to 2, because

22=4, 4 mod 7=4.

Or maybe 5, because

25=32,

32 mod 7=(28+4) mod 7=(47+4) mod 7=4 (Fig. 2).

You can consider this on the example of a watch. We measure hours modulo 12, minutes and seconds modulo 60. Imagine that someone said to you: “The first time I looked at the clock when it was 1:00, and the second time when it was it was 3:00. How much time has passed between?” You cannot give a guaranteed correct answer because it could have been 2 hours, 2+12=14 hours, 14+12=26 or more. The “mod 12” operation erases this information.

Taking “mod” is the simplest and most easily computed operation, effectively hiding the original value. Therefore, it is used in one way or another in all standard one-way transformations. It is usually combined with other functions, such as the power function discussed above, or with more complex methods, as will be shown later in the description of the ECDSA algorithm.

Sig Signature Creation Algorithm

The signature itself is calculated based on two parameters: the secret key sk and the message on which it is currently attached. However, the message can be completely arbitrary, so passing it directly to the algorithm is not very convenient. To solve this problem, cryptographically strong hashing is used.

A cryptographically secure hash function is any function that takes an arbitrary set of characters as an argument and outputs a number in a fixed range, for example, 256 bits. This number is called a hash, and the process itself is called hashing. On the same input message, the hash is always the same. However, with the slightest change in the message, the returned number (hash) changes so much that it becomes impossible to associate changes in the message with changes in the hash. In addition to usability, a cryptographically strong hash also guarantees the integrity of the message, i.e. that the message has not changed since the signature was created.

For example, the cryptographically strong hash function sha256 produces numbers in the range 0 to 2256-1. The line “I promise to give you $5,000” gives a number

be657fcad7933b87869835c571b60ff1444f68179326e7754c3d99babf919995. And if you now change $5,000 to $50,000, adding just one extra 0: “I promise to give you $50,000”, then the hash will change to 90222db12a4a59f8d083e3cf88bf22dab15385c9946f4526a67855e6a5ff0737.

Thus, as input, the signature creation algorithm receives the secret key sk and the number m, the hash of the message to be signed.

At the output, the signature creation algorithm produces the signature number s=Sigsk, m. A more detailed analysis of the ECDSA signature algorithm, which is used in cryptocurrencies, will be described in the corresponding section.

Signature Verification Algorithm Ver

The KeyGen and Sig algorithms are for those who want to create their own digital signature. The Ver algorithm is used by those who need to verify the authenticity of someone else’s signature.

As input, this algorithm receives the public key pk of the one who left the signature, the hash m of the message on which this signature is, and the signature itself s.

The output of the algorithm is 1 (TRUE) if the signature passed verification, and 0 (FALSE) if it did not.

A successful test means:

  1. The public key pk and the secret key sk used to create the signature match. That is, the one who left the signature has the secret key sk.

  2. The signed message (hash) itself has not changed since the signature was created.

Accordingly, the signature will fail verification if at least one of the following circumstances occurs:

  1. The private key sk used to create the signature does not match the public key pk. That is, the one who pretends to be the author, in fact, is not, and someone else left the signature.

  2. After the signature was given, the message was changed.

Which of these conditions affected the invalidity of the signature, the algorithm does not determine.

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

The authors:

Alexey Troshichev mastermind
Artyom Fomichev Mathematician
Inga Pashentseva Editor
Alexander Polovyan Fact Check

Similar Posts

Leave a Reply Cancel reply