Secret Sharing using Chinese Remainder Theorem (CRT)

In this video, Professor Bill Buchanan OBE, Blockpass ID lab, talks about the concept of Secret Sharing with ‘Chinese Remainder Theorem (CRT)’. The speaker begins the session by defining the process of secret sharing. At 1:05, he defines secret sharing to be methods that are for the purpose of distributing a secret among a group of people. Everyone in the group will be allocated a share of the secret. Secret sharing is also referred to as secret splitting. In the secret-sharing method, a secret, say S is recovered from a set of shares. Each of the shares will contain some information about the secret. At 3:06, the speaker defined the famous ‘Chinese Remainder Theorem’. The theorem states that for any system of concurrent congruence equations, the solution will be unique in some Z/nZ where n > 0. Thereby secret sharing can use this theorem to produce the shares that are available on these congruence equations. Remember the secret can be recovered by solving these equations to get the unique answer. This unique answer will be the secret that is to be recovered.

Secret sharing schemes

The speaker then briefs on the purpose of secret sharing schemes. These secret sharing schemes are best for storing information that is very sensitive and critical. Some of the sensitive information may include encryption keys, bank account numbers. Using basic traditional methods of encryption for this confidential information is never suited well. With the basic method, we might need to keep several copies of the key in various locations to achieve reliability. Doing this will also increase the probability of this information getting stolen or eavesdropped on by the attackers. A secret sharing scheme was introduced to resolve the stated issue. The secret sharing schemes are critical in cloud computing. A single key will be distributed over plenty of servers via the threshold secret sharing method. We will have the ability to reconstruct this key whenever required. In addition, these schemes can be used at places where the links can be tapped by attackers.

Shamir’s secret sharing

At 4:56, the speaker talks about a popular secret sharing method, Shamir’s Secret Sharing (SSS). This method is to protect a specific secret in a distributed fashion. The first step here is to split the secret into several parts. The parts that are split are referred to as shares. These shares are then reconstructed in order to get the secret. Remember that you will need a minimum number of shares in order to recover the secret. That minimum number is referred to as threshold. This SSS scheme can be used in encrypting the vault’s password, generating N number of shares, where some amount N can be allocated to every participant. The vault can be recovered only if all the shares are pooled. Password can never be recovered even if one share is missing

Asmuth-Bloom threshold secret sharing

At 7:15, the speaker mentions that the ‘Chinese Remainder Theorem (CRT)’ can be used to perform secret sharing. One common method is using the Asmuth-Bloom threshold secret share scheme. Here, we need to create coprime integers for the number of shares (n), we will require (m0, m1…. m2). Where m0 < m1 < m2 ….. < Mn. It is important to remember that for co-prime, none of the values of m(i) will be sharing a factor. He adds that if all of them are prime numbers, there will not be any factors shared. At 11:22, the speaker states there is one major theoretical difference between the two schemes. (Shamir’s scheme and Asmuth-Bloom). The former can be done in a secure way provided the non-constant polynomial coefficients are picked in a completely random manner. In this case, a person with a number of shares that’s less than the threshold would not gain any sort of information about the shared secret. On the contrary, Asmuth and Bloom’s scheme leaks some amount of information.
At 14:17, the speaker talks about a few limitations associated with this ‘Secret Sharing’ method. He adds that the final share should be containing as much information as the actual secret. Though this is a limitation, there is a workaround for this limitation. Compressing the secret even before sharing it would be a good workaround, but this might not be always possible as many secrets are usually random data where compressing becomes a pain. The speaker mentions that the schemes in this method use random bits. If there is a need to distribute a single-bit secret among t people, then nearly t-1 random bits are required which is difficult in most cases.