Currently, there is significant growth in the use of and research into secret-sharing mechanisms. This involves being able to retrieve (provided at least a minimum number or threshold of entities is present) a specific secret (key, file, data, code, etc.) from within a group of entities (people, machines, computers, animals, vehicles, etc.) after distributing a fragment of that secret to each authorized entity. For example, to access a certain resource, activate a device, or launch a nuclear device, such as an intercontinental ballistic missile, the presence of a pre-established minimum number of authorized entities is required.
Typification of Threshold Secret Sharing Schemes. Phase Identification.
A threshold secret sharing scheme (t, N) can be defined as a method of sharing a secret S among a set of N participants such that any group of t of them can determine the secret S, but no group of (t – 1) or fewer can do so. Likewise, no group of (t – 1) participants can learn any information about the secret S. A secret sharing scheme consists of two phases: (1) Sharing Phase. In a threshold secret sharing mechanism (4, 4), a distribution entity D initially possesses a secret S and wishes to establish a group of four authorized participants P1, P2, P3, P4 to share S, such that none of them knows the secret. The objective of the sharing phase is to fragment S and give enough information to each Pi (a fragment of S) so that, by working together, the four participants can determine S, but none has enough information to determine the secret S. (2) Reconstruction Phase. The idea is that a group of four participants can determine secret S. They cannot do so if there are three, two, or one of them.
A nuclear weapon launch code could be a threshold secret-sharing scheme (2,3), such that any two entities in the group of three are sufficient to launch the nuclear device. The three possible entities could be the president of the nation, the minister of defense, and the foreign minister. Is it prudent to increase the number of people who can come together to launch a nuclear weapon? Or is it perhaps more prudent to increase the number of people who must come together to launch such a weapon?
Clipper Chip and Key Custody. Threshold
Secret Sharing Mechanisms (2, 2) and (n, n). It all stemmed from the fact that the US government was convinced that cryptographic tools were vital for business development in the electronic age, but at the same time, it did not want to give companies or individuals the ability to circumvent its surveillance mechanisms for encrypted communications. For this reason, it created the Clipper Chip. The initial proposal held that the government would supply manufacturers of electronic devices with encryption capabilities (telephones, computers, communication machines, etc.) with Clipper Chips that would allow the encryption of messages from the devices. The government would keep a copy of each Clipper Chip's secret key so that, when deemed necessary, it could easily decrypt the messages for reasons of national security and/or compliance with the law. This initial proposal was unpopular and sparked numerous protests. To address the criticism that it would make it too easy for the government to illegally spy on individuals and businesses, the government proposed splitting each key into two parts and establishing two national agencies to safeguard each fragment. This way, if the FBI, CIA, DoD, DEA, NSA, etc., needed to obtain a Clipper chip key for any reason, they would have to present a court order to both custodian agencies.
The US government's Clipper chip key escrow proposal was a (2, 2) secret-sharing scheme. The implementation was as follows: the Clipper chip key K, a 64-bit string, was split into two 32-bit strings, K1 and K2, such that K = (K1 x OR K2). K1 and K2 were stored in separate custodian agencies. Suppose K = 0110, K1 = 1010 is chosen randomly, and K2 = K xor K1 = 1100 is calculated, then K = (K1 xor K2) = 0110. This scheme satisfies the requirements of a threshold secret-sharing scheme, such that either agency without the other could not reconstruct K, but by combining K1 and K2, it can obtain K.
Let us examine another (2, 2) secret-sharing scheme, in this case a defective one. Suppose we have a ten-bit secret key: K = 0010101011, and we divide it into two five-bit strings, each of which is a halve, K1 = 00101 and K2 = 01011, and distribute them to each participant, P1 and P2. Each participant knows half of the secret string K. This violates the definition of a threshold (t, N) secret-sharing scheme, which states that (t – 1) participants should not learn any information about the secret K to be shared. Here, each participant has two to the power of K divided by two fewer chances when attempting to find the secret key by brute force. Another example of such a flawed mechanism is the following: to share K = 0110 into two parts, suppose we take two strings corresponding to the first two and last two bits of K, that is, K1 = 01 and K2 = 10. This scheme is flawed because it leaks information about K and makes a brute-force attack much easier.
Let's consider another (n, n) secret-sharing mechanism, in this case, not flawed. Given a secret S to be shared, (n – 1) fragments of the secret S are chosen randomly and represented as: S1, . . . , Sn-1, the nth fragment is calculated as the difference between the secret S and the sum of all the n – 1 fragments:
Shamir sharing mechanism (3, 8)
Let a secret S = 190503180520 and let the modulus of the finite modular arithmetic p = 1234567890113. A polynomial of degree t – 1 = 3 – 1 = 2 is constructed with random coefficients of x and independent term being the secret S, the result is: f (x) = (S + a1.x + a2.x2) mod p = (190503180520 + 482943028839.x + 1206749628665. x2) mod p. Eight possible points to use as fragments of secret S are: {(1, 645627947891), (2,1045116192326), (3, 154400023692), (4, 442615222255), (5, 675193897882), (6, 852136050573), (7, 973441680328), (8, 1039110787147)}.
Verifiable (t, N) threshold secret sharing schemes.
Verifiable threshold secret sharing schemes satisfy the two properties: (1) The reconstruction of secret S does not depend on t parts performing the reconstruction; this prevents participants from cheating. Fraudulent behavior by participants or carriers of fragments of the secret should result in their own S, different from the S that was distributed. Thus, in the case of scheme (2, 3), two honest parties may distribute real fragments, while a dishonest carrier may contribute an incorrect fragment. There are three possible reconstructions of S depending on which pair of participants collaborated (violating the definition). (2) If the distributor D of fragments of the secret S is honest, then the recovered secret must be exactly identical to the shared secret.
Let's select p a raised prime number and q a large prime number, such that q divided by p minus one (q / (p – 1)) is a large prime factor. We choose g such that the order of g is q (ord(g) = q), meaning that the first, second, third, up to q-th powers of g modulo p are always distinct (g, g² mod p, ..., gq mod p). In a verifiable secret sharing scheme (2, 3) we choose S between 0 and (p – 1), we randomly select A between 0 and (p – 1), then f(x) = (Ax + S) mod q, obtaining S1= f(1) = (A + S) mod q , S2= f(2) = (2.A + S) mod q , S3= f(3) = (3.A + S) mod q , in addition the distributor D distributes to some public notice board three values: (Z1= gS1 mod p , Z2= gS2 mod p , Z3= gS3 mod p). This mechanism is similar to a certain type of commitment scheme by entity D that the fragments given to participants belong to the same secret S. The participants want to ensure that the distributor D is not cheating, and that Z1, Z2, and Z3 will help ensure that all secret fragments belong to the same secret S. These values Z1, Z2, and Z3 will also help prevent participants from cheating by revealing fragments not provided by D. The procedure for each party to accept or reject their key fragments is: (1) For all i belonging to the set {1, 2, 3}, P checks if Zi = gS1 mod p and Z1 . Z3 = (Z2)2 mod py, then accepts or rejects. If there are more than two complaints from the three participants, then the distributor D cheated. If there is only one complaint, it means that the distributor D cheated a little, but not enough to make the secret unrecognizable, or that one of the participants is making a false complaint. For the reconstruction phase, any Si that does not satisfy Zi (gS1 mod p = Zi) is rejected. Then, any pair of fragments that were not rejected are interpolated using simple reconstruction. If only one complaint occurred, there are enough points to reconstruct S. (2) The second check is to verify linearity. If three points are on the same line, the reconstruction was successful. When D is honest, it is necessary to ensure that these three published values are consistent with three collinear points. For example, if: Z1 . Z3 = (Zi)2 mod p, it means that: (gS1 mod p). (gS3 mod p) = (gS2 mod p)2, that is, gS1+S3mod p = g2.S2, that is, S1 + S3 = 2.S2 mod q, that is: (1, S1), (2, S2), and (3, S3) are collinear modulo q, which is the condition for linearity.
Final Considerations
Our research group has been working for many years in the field of secret-sharing mechanisms and their combination with other mechanisms such as commitment schemes. Their field of applications is incredibly large and currently expanding rapidly.
This article is part of the activities carried out within the LEFIS-APTICE (funded by Socrates, European Commission ).
Bibliography
- Areitio, J. “Information Security: Networks, Computing and Information Systems”. Cengage Learning-Paraninfo. 2009.
- Areitio, J. “Analysis of Spam”. Conectrónica Magazine. No. 104. February 2007.
- Areitio, J. “Analysis of Technologies for Information Concealment”. Conectrónica Magazine. No. 109. July-August 2007.
- Areitio, J. “Analysis of Forensic Security, Anti-Forensic Techniques, Incident Response and Digital Evidence Management”. Conectrónica Magazine. No. 125. March 2009.
- Senior, A. “Protecting Privacy in Video Surveillance”. Springer. 2009.
- Gutwirth, S., Poullet, Y., De Hert, P., Terwangne, C. and Nouwt, S. “Reinventing Data Protection”. Springer. 2009.
- Ferguson, N. et al. “Cryptography Engineering: Design Principles and Practical Applications.” Wiley. 2010.
- Flegel, U. “Privacy Respecting Intrusion Detection”. Springer. 2007.
Author:
Prof. Dr. Javier Areitio Bertolín – E.Mail:
Professor at the Faculty of Engineering. ESIDE.
Director of the Networks and Systems Research Group. University of Deusto.
