Sharing a secret

Each fraction of a secret is a plane, and the secret is the intersection point of three planes. Two fractions of a secret allow you to get the line on which the secret point lies.

Secret sharing is a term in cryptography that refers to any of the methods for distributing a secret among a group of participants, each of which has its own share. The secret can be recreated only by a coalition of participants from the original group, and the number of members of the coalition must be at least some of them initially known.

Secret sharing schemes are used in cases where there is a significant probability of compromising one or more secret keepers, but the probability of unfair conspiracy of a significant part of the participants is considered negligible.

Existing schemes have two components: separation and restoration of secret. Separation includes the formation of parts of a secret and their distribution between members of a group, which allows you to share responsibility for the secret between its members. The reverse scheme should ensure its restoration, subject to the availability of its custodians in some necessary quantity ^[1] .

Usage example: secret ballot protocol based on the separation of secret ^[2] .

Content

1 The simplest example of a secret sharing scheme
2 Threshold circuit
- 2.1 Shamir scheme
- 2.2 Blackley circuit
- 2.3 Schemes based on the Chinese remainder theorem
- 2.4 Schemes based on the solution of systems of equations
- 2.5 Methods of cheating the threshold scheme
3 See also
4 notes
5 Literature

The simplest example of a secret sharing scheme

Let there be a group of $t$ ${\ displaystyle t}$ person and message $s$ ${\ displaystyle s}$ lengths $n$ ${\ displaystyle n}$ consisting of binary characters. If you select randomly such binary messages $s_{1},\ldots ,s_{t}$ ${\ displaystyle s_ {1}, \ ldots, s_ {t}}$ that in total they will equal $s$ ${\ displaystyle s}$ , and distribute these messages among all members of the group, it turns out that it will be possible to read the message only if all members of the group come together ^[1] .

There is a significant problem in such a scheme: if at least one of the members of the group is lost, the secret will be lost for the whole group irretrievably.

Threshold Scheme

In contrast to the procedure for breaking the secret, where $t=n$ ${\ displaystyle t = n}$ , in the procedure for sharing a secret, the number of shares that are needed to restore the secret may differ from how many shares the secret is divided. Such a scheme is called a threshold scheme. $\left(t,n\right)$ ${\ displaystyle \ left (t, n \ right)}$ where $n$ ${\ displaystyle n}$ - the number of shares into which the secret was divided, and $t$ ${\ displaystyle t}$ - the number of shares that are needed to restore the secret. Circuit ideas $t\neq n$ ${\ displaystyle t \ neq n}$ were independently proposed in 1979 by Adi Shamir and George Blackley . In addition, similar procedures were investigated by Gus Simmons ^[3] ^[4] ^[5] .

If the coalition of participants is such that they have enough shares to restore the secret, then the coalition is called allowed. Secret sharing schemes, in which permitted coalitions of participants can uniquely restore a secret, and unauthorized ones do not receive any posterior information about the possible value of a secret, are called perfect ^[6] .

Shamir's scheme

An unlimited number of polynomials of degree 2 can be drawn through two points. To choose the only one, you need a third point

The idea of the scheme is that two points are enough for defining a straight line , three points for defining a parabola , four points for a cubic parabola , and so on. To set a polynomial degree $k$ ${\ displaystyle k}$ required $k+1$ ${\ displaystyle k + 1}$ points.

So that after separation, the secret can only be restored $k$ ${\ displaystyle k}$ participants, it is "hidden" in the formula of a polynomial of degree $(k-1)$ ${\ displaystyle (k-1)}$ over the final field $G$ ${\ displaystyle G}$ . To uniquely restore this polynomial, it is necessary to know its values in $k$ ${\ displaystyle k}$ points, and, using a smaller number of points, it is not possible to uniquely restore the original polynomial. The number of different points of the polynomial is not limited (in practice, it is limited by the size of the number field $G$ ${\ displaystyle G}$ in which the calculations are made).

Briefly, this algorithm can be described as follows. Let a finite field be given $G$ ${\ displaystyle G}$ . Fix $n$ ${\ displaystyle n}$ various nonzero unclassified elements of this field. Each of these elements is assigned to a specific member of the group. Next, an arbitrary set of $t$ ${\ displaystyle t}$ field elements $G$ ${\ displaystyle G}$ of which the polynomial is composed $f(x)$ ${\ displaystyle f (x)}$ over the field $G$ ${\ displaystyle G}$ degrees of $t-1,1<t\leq n$ ${\ displaystyle t-1,1 <t \ leq n}$ . After receiving the polynomial, we calculate its value at unclassified points and report the results to the appropriate members of the group ^[1] .

To restore the secret, you can use the interpolation formula, for example, the Lagrange formula.

An important advantage of the Shamir scheme is that it is easily scalable ^[5] . To increase the number of users in a group, you only need to add the corresponding number of unclassified elements to existing ones, while the condition $r_{i}\neq r_{j}$ ${\ displaystyle r_ {i} \ neq r_ {j}}$ at $i\neq j$ ${\ displaystyle i \ neq j}$ . At the same time, the compromise of one part of the secret translates the scheme from $(n,t)$ ${\ displaystyle (n, t)}$ threshold in $(n-1,t-1)$ ${\ displaystyle (n-1, t-1)}$ -threshold.

Blackley circuit

Two non-parallel lines in the plane intersect at one point. Any two non-coplanar planes intersect in one straight line, and three non-coplanar planes in space intersect at the same point. In general, n n -dimensional hyperplanes always intersect at one point. One of the coordinates of this point will be a secret. If you encode a secret as several coordinates of a point, then by one fraction of the secret (one hyperplane) you can get some information about the secret, that is, about the interdependence of the coordinates of the intersection point.


Blackley's scheme in three dimensions: each fraction of a secret is a plane , and the secret is one of the coordinates of the intersection point of the planes. Two planes are not enough to determine the intersection point.

Using the Blackley scheme ^[4], you can create a (t, n) -second secret sharing scheme for any t and n : to do this, use the dimension of space equal to t , and give each of the n players one hyperplane passing through the secret point. Then any t of n hyperplanes will uniquely intersect at a secret point.

The Blackley scheme is less effective than the Shamir scheme: in the Shamir scheme, each share is the same size as the secret, and in the Blackley scheme each share is t times larger. There are improvements to the Blackley scheme to improve its efficiency.

Schemes based on the Chinese remainder theorem

In 1983, , Asmouth, and Bloom proposed two secret sharing schemes based on the Chinese remainder theorem . For a certain number (in the Mignotte scheme this is the secret itself, in the Asmouth-Bloom scheme is some derived number), the remainders of division by a sequence of numbers that are distributed to the sides are calculated. Due to restrictions on the sequence of numbers, only a certain number of parties can restore a secret ^[7] ^[8] .

Let the number of users in the group equal $n$ ${\ displaystyle n}$ . In the Mignott scheme, a certain set of pairwise mutually prime numbers is selected $\{m_{1},m_{2},...,m_{n}\}$ ${\ displaystyle \ {m_ {1}, m_ {2}, ..., m_ {n} \}}$ such that the product $k-1$ ${\ displaystyle k-1}$ the largest numbers are less than the product $k$ ${\ displaystyle k}$ smallest of these numbers. Let these works be equal $M$ ${\ displaystyle M}$ and $N$ ${\ displaystyle N}$ , respectively. Number $k$ ${\ displaystyle k}$ called the threshold for the constructed circuit over the set $\{m_{1},m_{2},...,m_{n}\}$ ${\ displaystyle \ {m_ {1}, m_ {2}, ..., m_ {n} \}}$ . The number is selected as a secret. $S$ ${\ displaystyle S}$ one for which the relation holds $M<S<N$ ${\ displaystyle M <S <N}$ . Parts of the secret are distributed among the members of the group as follows: each member is given a pair of numbers $(r_{i},m_{i})$ ${\ displaystyle (r_ {i}, m_ {i})}$ where $r_{i}\equiv S{\pmod {m_{i}}}$ ${\ displaystyle r_ {i} \ equiv S {\ pmod {m_ {i}}}}$ .

To restore the secret, you need to combine $t\geq k$ ${\ displaystyle t \ geq k}$ fragments. In this case, we obtain a system of comparisons of the form $x\equiv r_{i}{\pmod {m_{i}}}$ ${\ displaystyle x \ equiv r_ {i} {\ pmod {m_ {i}}}}$ whose many solutions can be found using the Chinese remainder theorem . Secret number $S$ ${\ displaystyle S}$ belongs to this set and satisfies the condition $S<m_{1}\cdot m_{2}\cdot ...\cdot m_{t}$ ${\ displaystyle S <m_ {1} \ cdot m_ {2} \ cdot ... \ cdot m_ {t}}$ . It is also easy to show that if the number of fragments is less $k$ ${\ displaystyle k}$ , then, to find a secret $S$ ${\ displaystyle S}$ need to sort out the order ${\frac {N}{M}}$ ${\ displaystyle {\ frac {N} {M}}}$ integers. With the right choice of numbers $m_{i}$ ${\ displaystyle m_ {i}}$ this sorting is almost impossible to implement. For example, if bit depth $m_{i}$ ${\ displaystyle m_ {i}}$ will be from 129 to 130 bits, and $k<15$ ${\ displaystyle k <15}$ , then the ratio ${\frac {N}{M}}$ ${\ displaystyle {\ frac {N} {M}}}$ will have order $2^{100}$ ${\ displaystyle 2 ^ {100}}$ ^[9] .

The Asmouth-Bloom scheme is a modified Mignott scheme. Unlike the Mignott scheme, it can be built in such a way that it is perfect ^[10] .

Schemes based on solving systems of equations

In 1983, Karnin, Green, and Hellman proposed a secret sharing scheme based on the inability to solve the system with $m$ ${\ displaystyle m}$ unknown having less $m$ ${\ displaystyle m}$ equations ^[11] .

Within the framework of this scheme, $n+1$ ${\ displaystyle n + 1}$ $m$ ${\ displaystyle m}$ -dimensional vectors $V_{0},V_{1},...,V_{n}$ ${\ displaystyle V_ {0}, V_ {1}, ..., V_ {n}}$ so that any matrix sized $m\times m$ ${\ displaystyle m \ times m}$ made up of these vectors had the rank $m$ ${\ displaystyle m}$ . Let the vector $U$ ${\ displaystyle U}$ has dimension $m$ ${\ displaystyle m}$ .

The secret in the scheme is the matrix product $U^{T}\cdot V_{0}$ ${\ displaystyle U ^ {T} \ cdot V_ {0}}$ . The fractions of a secret are works $U^{T}\cdot V_{i},1\leq i\leq n$ ${\ displaystyle U ^ {T} \ cdot V_ {i}, 1 \ leq i \ leq n}$ .

Having any $m$ ${\ displaystyle m}$ shares, you can make a system of linear equations of dimension $m\times m$ ${\ displaystyle m \ times m}$ unknown in which are the coefficients $U$ ${\ displaystyle U}$ . Having solved this system, you can find $U$ ${\ displaystyle U}$ and having $U$ ${\ displaystyle U}$ You can find a secret. Moreover, the system of equations has no solution if the fractions are less than $m$ ${\ displaystyle m}$ ^[12] .

Ways to cheat a threshold circuit

There are several ways to violate the threshold circuit protocol:

the owner of one of the shares may interfere with the restoration of the general secret by giving back the wrong (random) share at the right time ^[13] ;
an attacker, without a share, may be present when restoring a secret. After waiting for the announcement of the required number of shares, he quickly restores the secret on his own and generates another share, after which he presents it to the other participants. As a result, he gains access to the secret and remains uncaught ^[14] .

There are also other possibilities of disruption that are not related to the features of the implementation of the scheme:

an attacker can simulate a situation in which disclosure of a secret is necessary, thereby deriving the shares of participants ^[14] .

Notes

↑ ¹ ² ³ Alferov, Teeth, Kuzmin et al., 2002 , p. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. An introduction to shared secret and / or shared control schemes and their application // Contemporary Cryptology. - IEEE Press, 1991 .-- P. 441-497 .
↑ ¹ ² Blakley, 1979 .
↑ ¹ ² Shamir, 1979 .
↑ Blackley, Kabatiansky, 1997 .
↑ Mignotte, 1982 .
↑ Asmuth, Bloom, 1983 .
↑ Moldovian, Moldovian, 2005 , p. 225.
↑ Shenets, 2011 .
↑ Karnin, Greene, Hellman, 1983 .
↑ Schneier B. Applied Cryptography. - 2nd ed. - Triumph, 2002 .-- S. 590. - 816 p. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ ¹ ² Schneier, 2002 , p. 69.

Literature

Schneier B. 3.7. Sharing a secret // Applied cryptography. Protocols, algorithms, C source code = Applied Cryptography. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002. - S. 93-96. - 816 s. - 3000 copies. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Secret sharing algorithms // Applied cryptography. Protocols, algorithms, C source code = Applied Cryptography. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002. - S. 588-591. - 816 s. - 3000 copies. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - P. 313-317. - doi: 10.1109 / AFIPS.1979.98
<a href=" https://wikidata.org/wiki/Track:Q21589199 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21589168 "> </a> <a href = " https://wikidata.org/wiki/Track:Q178277 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21589192 "> </a>
Shamir A. How to share a secret // Commun. ACM - New York City : ACM , 1979. - Vol. 22, Iss. 11. - P. 612-613. - ISSN 0001-0782 - doi: 10.1145 / 359168.359176
<a href=" https://wikidata.org/wiki/Track:Q127992 "> </a> <a href=" https://wikidata.org/wiki/Track:Q60 "> </a> <a href = " https://wikidata.org/wiki/Track:Q320624 "> </a> <a href=" https://wikidata.org/wiki/Track:Q1120519 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21588915 "> </a>
Mignotte M. How to Share a Secret // Cryptography : Proceedings of the Workshop on Cryptography Burg Feuerstein, Germany, March 29 – April 2, 1982 / T. Beth - Springer Berlin Heidelberg , 1983. - P. 371-375. - ( Lecture Notes in Computer Science ; Vol. 149) - ISBN 978-3-540-11993-7 - ISSN 0302-9743 - doi: 10.1007 / 3-540-39466-4_27
<a href=" https://wikidata.org/wiki/Track:Q27915506 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21587985 "</a> <a href = " https://wikidata.org/wiki/Track:Q924044 "> </a> <a href=" https://wikidata.org/wiki/Track:Q2422408 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27915505 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915498 "> </a>
Asmuth C. , Bloom J. A modular approach to key safeguarding // IEEE Trans. Inf. Theory / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 2. - P. 208–210. - ISSN 0018-9448 - doi: 10.1109 / TIT.1983.1056651
<a href=" https://wikidata.org/wiki/Track:Q16194641 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915587 "</a> <a href = " https://wikidata.org/wiki/Track:Q27915585 "> </a> <a href=" https://wikidata.org/wiki/Track:Q127793 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27915584 "> </a>
Karnin E. D. , Greene J. W. , Hellman M. E. On Secret Sharing Systems // IEEE Trans. Inf. Theory / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 1. - P. 35–41. - ISSN 0018-9448 - doi: 10.1109 / TIT.1983.1056621
<a href=" https://wikidata.org/wiki/Track:Q16194641 "> </a> <a href=" https://wikidata.org/wiki/Track:Q476466 "> </a> <a href = " https://wikidata.org/wiki/Track:Q28015695 "> </a> <a href=" https://wikidata.org/wiki/Track:Q127793 "> </a> <a href = " https://wikidata.org/wiki/Track:Q28015699 "> </a> <a href=" https://wikidata.org/wiki/Track:Q28015689 "> </a>
Blackley D. , Kabatyansky G. A. Generalized ideal schemes sharing a secret and matroids // Probl. transmission inform. - 1997. - T. 33, no. 3. - S. 102–110.
<a href=" https://wikidata.org/wiki/Track:Q21766851 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27867803 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27867807 "> </a> <a href=" https://wikidata.org/wiki/Track:Q5537041 "> </a>
Schoenmakers B. A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting // Advances in Cryptology - CRYPTO '99 : 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings / M. Wiener - Springer Berlin Heidelberg , 1999. - P. 148–164. - ISBN 978-3-540-66347-8 - doi: 10.1007 / 3-540-48405-1_10
<a href=" https://wikidata.org/wiki/Track:Q27915563 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915561 "</a> <a href = " https://wikidata.org/wiki/Track:Q27915547 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915533 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21587985 "> </a>
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. et al. Fundamentals of cryptography : Textbook - 2nd ed., Rev. and add. - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
<a href=" https://wikidata.org/wiki/Track:Q22304400 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27449776 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27449770 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27048435 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27449771 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27449773 "> </a>
Moldovyan N. A. , Moldovyan A. A. Introduction to public key cryptosystems - St. Petersburg. : BHV-Petersburg , 2005 .-- 288 p. - ( Study Guide ) - ISBN 978-5-94157-563-3
<a href=" https://wikidata.org/wiki/Track:Q27866511 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27866506 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27866508 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27866510 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27866512 "> </a>
Pasailă D. , Alexa V. , Iftene S. Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes // International Journal of Computing - 2010. - Vol. 9, Iss. 2. - P. 107–117. - ISSN 2312-5381
<a href=" https://wikidata.org/wiki/Track:Q27915845 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915849 "</a> <a href = " https://wikidata.org/wiki/Track:Q27915847 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915844 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27915842 "> </a>
Schenets N. N. On ideal modular secret sharing schemes in polynomial rings of several variables // International Congress on Informatics: Information Systems and Technologies : Materials of the International Scientific Congress 31 Oct. - Minsk : BSU , 2011. - T. 1. Articles of the faculty of applied mathematics and computer science. - S. 169–173. - ISBN 978-985-518-563-6
<a href=" https://wikidata.org/wiki/Track:Q27915595 "> </a> <a href=" https://wikidata.org/wiki/Track:Q2280 "> </a> <a href = " https://wikidata.org/wiki/Track:Q27915590 "> </a> <a href=" https://wikidata.org/wiki/Track:Q27915597 "> </a>

[_52a56531d405ea2a-1] ¹ ² ³ Alferov, Teeth, Kuzmin et al., 2002 , p. 401.

[_1c4d6415ce2e5950-2] Schoenmakers, 1999 .

[3] CJ Simmons. An introduction to shared secret and / or shared control schemes and their application // Contemporary Cryptology. - IEEE Press, 1991 .-- P. 441-497 .

[_2795d074f16fb28d-4] ¹ ² Blakley, 1979 .

[_1f79b02374652d5d-5] ¹ ² Shamir, 1979 .

[_38d0da61bfb0b566-6] Blackley, Kabatiansky, 1997 .

[_53ceeaaeadb50b96-7] Mignotte, 1982 .

[_bd4510b0df4219f7-8] Asmuth, Bloom, 1983 .

[_a56cbd89137b5b5b-9] Moldovian, Moldovian, 2005 , p. 225.

[_81829710071d0e49-10] Shenets, 2011 .

[_c4e5a29a1e96cb54-11] Karnin, Greene, Hellman, 1983 .

[:1-12] Schneier B. Applied Cryptography. - 2nd ed. - Triumph, 2002 .-- S. 590. - 816 p. - ISBN 5-89392-055-4 .

[_77706e233f2cb275-13] Pasailă, Alexa, Iftene, 2010 .

[_7e973d3e4017854c-14] ¹ ² Schneier, 2002 , p. 69.