Introduction Greetings! At Symbiosis, we come across the fact that in the world of cryptocurrencies, where lots of cryptographic primitives and tools are heavily used, there is a limited number of really tech-savvy people who understand the underlying principles of how it’s all working. Others either understand very vaguely or simply do not know about the existence of such tools. And so here we start a series of articles where we’re making an endeavor to explain those concepts in a friendly manner. We begin with one of the main mechanisms used in our protocol: . MPC allows a group of parties to create a digital signature in such a way that . Only a quorum (a part of parties) participates in signing. MPC (Multi-party Computation) none of the parties have access to the secret needed to create the signature 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 private keys between parties, and how to sign data without having an entire private 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: : to ensure that the message is signed by exactly that person who introduced themselves as the signer.Document integrity: to ensure that the message has not changed since the signature was created. Signer authenticity : 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. And historically, every time you sign, you draw the same symbol Consequently, one just has to look at the signature to ensure 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 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 that guarantees the connection between the message and the signer’s public identifier. Public-Key Cryptography (or sometimes called Asymmetric Cryptography) studies such mathematical primitives. Thus, when you create a digital signature, two positive numbers are associated with you as the signer. One is called the private key*** (or secret key), 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 private 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 private key. A private 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 private 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 private key. Thus, a digital signature routing consists of three parts: The algorithm is used to create a pair of numbers: a public key and a private key; the algorithm is used to create a signature, using a message and the private key; and the algorithm is used to verify the signature using the signature, the signed message, and the public key. KeyGen Sig Ver Next, we will look at all three parts in detail. Key Generation With the KeyGen Algorithm The key generation algorithm creates a pair of keys sk, pk=KeyGen( ). where sk stands for the private key (secret key), and pk stands for the public key. Whenever you use the algorithm, you get a new pair of keys. A private key is just a random number. A public key can be easily obtained by applying a pre-defined one-way compression function to the private key. The one-way compression function does not allow recovery of the input parameters by output results. So, we can safely share our without risking compromising our . public key private key Modular exponentiation is a classic example of a one-way transformation. Common exponentiation pk=askis reversible (a is a fixed number). If we know pk and a, we can derive that sk=loga pk. 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 pk=ask mod q, 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 4=2sk mod 7 we will realize that it has multiple solutions. sk can be equal to 2, because 22=4, 4 mod 7=4. But it also can be equal to 5, because 25=32 32 mod 7=(28+4) mod 7=(47+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 private 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 2256–1. For the input string, “I promise to give you $5,000”, sha256 will return (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 be657fcad7933b87869835c571b60ff1444f68179326e7754c3d99babf919995 90222db12a4a59f8d083e3cf88bf22dab15385c9946f4526a67855e6a5ff0737 . To sum it up: the signature creation algorithm takes a private key sk and a number m (the message hash) for input and returns a number s. This number is a signature s=Sigsk, 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 and generate digital signatures. Algorithm is used for signature validation. KeyGen Sig Ver This algorithm requires the public key pk of the signer, the message hash m that was signed, and the signature s. The algorithm returns 1 (TRUE) if the signature is correct and 0 (FALSE) otherwise. Ver Successful verification can guarantee that The public key pk matches the private key sk used for the signature generation. This means that the person claiming to be the signer is the actual signer of the transaction.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: The private key sk does not match the public key pk. Someone is impersonating the message signer.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 algorithm. Ver 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. Authors: Alexey Troshichev — Main concept Artem Fomichev — Mathematician Inga Pashentseva — Editor Alexander Polovian — Fact Checking — — — — — — — — — — — — — — — - [1],[2]: we will explore these concepts further in our publications. Catch up with us on social media | | | | | Twitter Telegram Discord Facebook Instagram Linkedin

Chain

Facebook

Introduction to Threshold Signatures

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

01/06/2018: Biggest Stories in the Cryptosphere

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

01/06/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps