Straight to the point.
In this article, you will learn:
What are secret sharing schemes and why are they needed?
I will begin my story with an example described in the book "Gent und seine Schönheiten" by an unknown Belgian author. In the city of Ghent, a town hall tower was built, in one of the rooms of which very important documents were stored. These documents were in a three-lock cabinet, the cabinet in an egg, the egg in a duck, and the duck in a hare... One key to the cabinet was kept by Vogt, and the other two were kept by Chief Scheffen. The secret room had two doors, each with three locks. The keys to these locks were in the possession of various workshops.
In this vivid example, you can understand the main meaning of secret sharing schemes. To get access to encrypted data, you need to have several trusted persons present, each of whom will have a part of the secret. By putting all the pieces together, users can be content with the decrypted information.
Such protocols are used if one or more participants in the secret sharing scheme can be compromised. The more keepers of various "keys to cabinets and doors", the more likely it is that the secret will be restored in an honest way and the information will not end up in the hands of intruders.
Basic concepts
In my article, I will use the following established terms:
Secret share - some unique information for each participant in the process that helps to restore the secret
Dealer - a trusted person who distributes shares of the secret between participants
Secret sharing - the phase of counting and distributing secret shares
Secret recovery - the phase of collecting secret shares and counting the secret itself
Threshold secret sharing schemes
In the city of Ghent, the presence of all keepers of the key was a prerequisite for obtaining access to documents. But what if Vogt gets sick and a representative of one of the workshops loses the key? Will the secrets of the city of Ghent be lost forever?
History is silent about what happened to city documents, but understanding the consequences of such secret sharing protocols, people came up with threshold (t, n) schemes. Having n parts of the secret, you can recover it using only t of them. If any group of t-1 or fewer parties cannot recover the secret, then such a scheme is called perfect. If the size of the secret shares is the same as that of the secret itself, then the scheme is called ideal.
If employees of the Ghent city administration knew about this method, they would choose n key keepers, but they would build a security system in such a way that it would take at least t out of n participants in the process to gain access to the secret. However, in the case of a conspiracy, several keepers of the key, the number of which would be less than t, would not be able to open the doors and steal the documents.
Let's look further at several threshold schemes that are not as popular as, for example, the Blackley scheme and the Shamir scheme.
Mignotte scheme
This method is based on the Chinese remainder theorem. It sounds like this:
In other words, the theorem allows us to assert that the solution of the system is unique:
The Mignotte scheme uses so-called Mignotte sequences – sequences of mutually prime positive integers.
Finally, we describe the algorithm of the secret sharing scheme. There is an open Mignotte sequence, from which the secret S is randomly selected. Let's denote.
Obviously, the Mignotte secret sharing scheme does not have high cryptographic strength, since in the worst case, it can be cracked by brute-force, that is, it is not perfect. Moreover, in many cases, this method can be inconvenient due to the requirements of limiting the secret and generating large Mignotte sequences, which is quite a resource-intensive task. Since the size of the secret coincides with its share, the scheme is perfect.
The following scheme is based on the fact that it is impossible to uniquely solve a system with t unknowns with less than t equations. All actions occur in the final field. At the secret sharing stage, n+2 different vectors are randomly selected of dimension t so that the rank of any matrix of size t x t made up of these vectors is equal to t (that is, all vectors are chosen linearly independent in pairs). In this case, the values are they are public. The secret of S will be the scalar product and the secret shares are scalar products
The secret is recovered by solving a system of linear algebraic equations consisting of t equations and t unknowns with respect to the components of the vector U:
The system has a unique solution, since linearly independent vectors were selected at the stage of secret distribution, which means that the determinant of the matrix is not zero. Having found the vector U, it is easy to recover the secret by calculating the dot product
If the attacker gets less than t values, the system will have an infinite number of solutions, and any of them is equally likely to be the secret being searched for. This means that the Karnin-Green-Hellman scheme is perfect. However, the size of each fraction of the secret is t times larger than the secret itself, which makes the scheme not ideal.
Applying secret sharing schemes
Threshold (t, n) secret sharing schemes are used in threshold cryptosystems. Such cryptosystems allow you to decrypt a message by some group of at least t participants, among whom the secret is distributed. Threshold cryptosystems use the decryption key as a secret, while the encryption key is shared and public.
To create threshold cryptosystems, open encryption systems such as:
Threshold cryptosystems are used in many areas, for example, for storing the secret key of a certificate authority, in the government and military spheres, in cloud environments, and in electronic voting schemes.
In this article, you will learn:
- What are secret sharing schemes and what are they eaten with
- What are good threshold schemes?
- The idea of the Mignotte scheme
- The idea of the Karnin-Green-Hellman scheme
- Where are such schemes used?
What are secret sharing schemes and why are they needed?
I will begin my story with an example described in the book "Gent und seine Schönheiten" by an unknown Belgian author. In the city of Ghent, a town hall tower was built, in one of the rooms of which very important documents were stored. These documents were in a three-lock cabinet, the cabinet in an egg, the egg in a duck, and the duck in a hare... One key to the cabinet was kept by Vogt, and the other two were kept by Chief Scheffen. The secret room had two doors, each with three locks. The keys to these locks were in the possession of various workshops.
In this vivid example, you can understand the main meaning of secret sharing schemes. To get access to encrypted data, you need to have several trusted persons present, each of whom will have a part of the secret. By putting all the pieces together, users can be content with the decrypted information.
Such protocols are used if one or more participants in the secret sharing scheme can be compromised. The more keepers of various "keys to cabinets and doors", the more likely it is that the secret will be restored in an honest way and the information will not end up in the hands of intruders.
Basic concepts
In my article, I will use the following established terms:
Secret share - some unique information for each participant in the process that helps to restore the secret
Dealer - a trusted person who distributes shares of the secret between participants
Secret sharing - the phase of counting and distributing secret shares
Secret recovery - the phase of collecting secret shares and counting the secret itself
Threshold secret sharing schemes
In the city of Ghent, the presence of all keepers of the key was a prerequisite for obtaining access to documents. But what if Vogt gets sick and a representative of one of the workshops loses the key? Will the secrets of the city of Ghent be lost forever?
History is silent about what happened to city documents, but understanding the consequences of such secret sharing protocols, people came up with threshold (t, n) schemes. Having n parts of the secret, you can recover it using only t of them. If any group of t-1 or fewer parties cannot recover the secret, then such a scheme is called perfect. If the size of the secret shares is the same as that of the secret itself, then the scheme is called ideal.
If employees of the Ghent city administration knew about this method, they would choose n key keepers, but they would build a security system in such a way that it would take at least t out of n participants in the process to gain access to the secret. However, in the case of a conspiracy, several keepers of the key, the number of which would be less than t, would not be able to open the doors and steal the documents.
Let's look further at several threshold schemes that are not as popular as, for example, the Blackley scheme and the Shamir scheme.
Mignotte scheme
This method is based on the Chinese remainder theorem. It sounds like this:
In other words, the theorem allows us to assert that the solution of the system is unique:
The Mignotte scheme uses so-called Mignotte sequences – sequences of mutually prime positive integers.
Finally, we describe the algorithm of the secret sharing scheme. There is an open Mignotte sequence, from which the secret S is randomly selected. Let's denote.
Obviously, the Mignotte secret sharing scheme does not have high cryptographic strength, since in the worst case, it can be cracked by brute-force, that is, it is not perfect. Moreover, in many cases, this method can be inconvenient due to the requirements of limiting the secret and generating large Mignotte sequences, which is quite a resource-intensive task. Since the size of the secret coincides with its share, the scheme is perfect.
The following scheme is based on the fact that it is impossible to uniquely solve a system with t unknowns with less than t equations. All actions occur in the final field. At the secret sharing stage, n+2 different vectors are randomly selected of dimension t so that the rank of any matrix of size t x t made up of these vectors is equal to t (that is, all vectors are chosen linearly independent in pairs). In this case, the values are they are public. The secret of S will be the scalar product and the secret shares are scalar products
The secret is recovered by solving a system of linear algebraic equations consisting of t equations and t unknowns with respect to the components of the vector U:
The system has a unique solution, since linearly independent vectors were selected at the stage of secret distribution, which means that the determinant of the matrix is not zero. Having found the vector U, it is easy to recover the secret by calculating the dot product
If the attacker gets less than t values, the system will have an infinite number of solutions, and any of them is equally likely to be the secret being searched for. This means that the Karnin-Green-Hellman scheme is perfect. However, the size of each fraction of the secret is t times larger than the secret itself, which makes the scheme not ideal.
Applying secret sharing schemes
Threshold (t, n) secret sharing schemes are used in threshold cryptosystems. Such cryptosystems allow you to decrypt a message by some group of at least t participants, among whom the secret is distributed. Threshold cryptosystems use the decryption key as a secret, while the encryption key is shared and public.
To create threshold cryptosystems, open encryption systems such as:
- RSA Cryptosystem
- El Gamal Cryptosystem
Threshold cryptosystems are used in many areas, for example, for storing the secret key of a certificate authority, in the government and military spheres, in cloud environments, and in electronic voting schemes.
