Shamir's secret sharing

Imagine the situation - you need to ensure the safety of the contents of the bank cell. For its part, the bank has already done everything possible so that no outsider can reach it. Therefore, it provided you with the only key that provides access to the content. But this key can be stolen from you, you can lose it, and if it is improperly used, for example, it can be damaged on its own. And you have to go through a long procedure for restoring access. Not to mention the fact that in order to get the contents at your disposal, you, as the sole owner of the key, will have to personally attend each time you visit the bank.

A possible option is to make a copy of the key and transfer it to an authorized person. Now the chance of losing access is reduced, but the risk is increased in case of theft. Also not a good solution.

Another option is to split the initial key into 2 parts. Now the thief will have to steal both in order to gain access. But if you lose any of these parts, you will have to go through the procedure for restoring access again.

Therefore, the best option is to create a storage scheme for the key or its fragments so that its functionality does not change due to the incapacity of one of the participants in this scheme. It is precisely this problem that the method called “Shamir’s Secret Sharing” solves.

What is it?

The author of the idea is the Israeli cryptographer Adi Shamir. In 1970, he published the scientific work "How to Share a Secret", which described a threshold scheme that allows access to information divided into n parts, possessing only k parts. k by itself is less than n. Moreover, even the presence of k-1 parts does not give any idea of the key and does not facilitate its selection. That means - also semantic security.

What, in fact, is the main point. Knowing the coordinates of two points on the plane - you can build a line through them. Knowing the coordinates of three points in space - draw a plane through them. Knowing a certain number of points - k, describing the graph of a complex function - you can recreate this function.

Specifically, in the situation with the distribution of Shamir's secret, the so-called Lagrange interpolation polynomial is used. It allows you to determine the very number of points k that is needed to determine the entire function.

In practical terms, it looks like this. There is a dealer who offers storage services. He also provides a private key, which is then divided into a certain number of parts. Each part is given to one of the participants. Now, in order to access information, k such people must join forces. Moreover, they do not have to be present in the same place for everyone - the point of failure will be created remotely, after the exchange of information.

The method is a bit like a multi-sig wallet (a wallet with several electronic signatures), but there are also significant differences. SSS works offline, and multisig - exclusively within the framework of a working network. In addition, for multisig, simultaneous access of participants is required, and in the situation of SSS it can be extended in time. It is believed that SSS is more convenient for individuals, and a multi-signature wallet is for large enterprises.

Specific Benefits of SSS

• Possibility of multidimensional access control. For each of the single and useless by themselves parts of the secret, controlled storage can be provided. This eliminates the need to trust specific people.
• This method is suitable for storing absolutely any information (private keys, server root keys, various certificates, such as PGP / GPG), while multisig is more limited in this regard.
• The ability to work with any blockchain. Alas, the multisig system is not supported in all cases, and with the help of SSS you can safely break any seed phrases into parts. In addition, there is no need for a single access point (failure).
• Maintaining the confidentiality of information even in the case of settling of individual fragments into the hands of attackers.
• Only one private key is used, therefore there are fewer transactions and related fees.
• Simplified change of access scheme. If one fragment is compromised, you simply create the same number of new fragments and distribute them to proxies again, deleting the "old" ones.
• Increased stability in terms of information theory. If the attacker does not have all the necessary fragments, even unlimited computing power will not allow him to pick up the key.

DSS problems and their solutions

• Standard size. The length of any fragment of a secret corresponds to the length of the secret itself, so knowing one fragment, we can make some assumptions about the size of the encrypted data. It can be solved by prefilling the encrypted information with arbitrary numbers.
• Lack of verifiable circuits. In fact, knowing one fragment of a secret, an attacker will be able to reproduce the same length in hardware. They will not give the right to use the information, but make it difficult to restore the correct secret. Therefore, very often in these algorithms, additional verifiable secret sharing schemes are used, for example, the Felman scheme.

Shamir’s secret sharing is an extremely convenient way to provide access to protected information. However, do not forget that it is better to combine it with additional protection methods, such as checking the constant execution time, the lack of saving the entered data on disk, rational storage of each individual fragment, and much more.