Cryptography is defined as the art of writing or solving codes. But this definition does not capture the current breadth of the field or its present-day scientific foundations.  Beginning in the 1970s and 1980s, modern cryptography was developed. Modern cryptography involves the study of mathematical techniques for securing digital information, systems, and distributed computations against adversarial attacks. It deals with mechanisms for ensuring integrity, protocols for authenticating users, electronic auctions and elections, digital cash, and more. 

I’ll introduce an interesting concept in cryptography called secret sharing in this article.

Secret Sharing

Let us consider a situation where you and your four friends discovered a map that would lead to an island full of treasure and decided to look for it the next day.  Anyone with the map can take the treasure for themselves. So, no one trusts each other.  How will you resolve it?

A trivial solution would be to split the map into five pieces and make sure that all the pieces are required to find the treasure.  Each person is given a piece of the map. 

Secret sharing is an old cryptographic primitive which can be used in such scenarios. It has applications in existing real-world problems like secure computation and bitcoin signatures.  Secret sharing was invented by both Adi Shamir[1] and George Blakley[2] independently in 1979.

Secret sharing refers to the method of distributing a secret among a group of individuals (players), where each player is allocated some information (share) of the secret. The secret can only be revealed when an authorized group of players combine their shares. There can be several authorized groups. For any other group of players, these shares reveal absolutely no information about the secret.

Fig 1. Secret Sharing 

Among a total of n players, if any group of t (threshold) or more players can combine their shares to reconstruct the secret, but no group of size less than t can recover it,  then the scheme is called threshold secret sharing scheme (t-out-of-n).

Additive Sharing

Assume that there’s a fixed field to which all the secrets and shares of the players belong, and in which all the computation takes place. For instance, integers modulo a prime number, i.e. {0,1,…,q-1} where q is a prime number. 

Let’s construct a 3-out-of-3 scheme.

An easy way to share a secret x from the field would be to pick x1 and x2 at random and set x3= x – ( x1 + x2) where x1, x2, x3 corresponds to shares of the first player, second player and third player respectively. In this case, even if two players come together, they won’t be able to guess the third share. Therefore, no information about the secret is revealed to them. 

The same approach can be generalized to construct an n-out-of-n scheme where n-1 shares are picked at random, and the last share is set by calculating the difference between the secret and the sum of n-1 shares.

Shamir Secret Sharing

Shamir secret sharing scheme is a threshold secret sharing scheme based on Lagrange’s interpolation formula.  

To define a  straight line in a plane, two points lying on the line are required. Similarly, three points are required to define a quadratic. This generalizes to polynomials of degree d, i.e. d+1 points lying on the polynomial are required to define the polynomial. 

To construct a t-out-of-n scheme, pick a polynomial p of degree t-1 with constant as the secret. Then, polynomial evaluated at 0 gives the secret.  Assign the shares p(1), p(2),…, p(n) to players 1, 2,…, n respectively.

The point corresponding to the kth share is (k,p(k)). Given any t shares,  the polynomial can be determined using Lagrange’s interpolation formula. Evaluating the polynomial at 0 gives back the secret.

Applications

Few practical applications include secure multi-party computation and multi-server storage.

The dealer stores the secret on multiple servers. Each share may be stored on a different server.  When t-out-of-n secret sharing is used, the dealer can recover the secret as long as t shares are recoverable from the servers despite several server failures.  For a cracker who can recover less than t shares, the secret remains hidden. 

Secure multi-party computation is a cryptographic primitive where a function is computed across multiple parties where no individual party can see the other parties’ data. Secret sharing is used to build several secure multi-party computation constructions.

Research Opportunities

Learning about the concept gives insight into different areas of cryptography.  There are several institutes/industries inside India and abroad which focuses on research in cryptography. Since research is usually collaborative, finding people who share similar interests is the key. Anyone interested, having a good grip over mathematics and computer science can pursue their research and career in Cryptography.

References

1. Shamir, Adi (1979). “How to share a secret”. Communications of the ACM. 22 (11): 612–613. doi:10.1145/359168.359176.

2. Blakley, G.R. (1979). “Safeguarding Cryptographic Keys”. Managing Requirements Knowledge, International Workshop on (AFIPS). 48:313–317. doi:10.1109/AFIPS.1979.98.

3. CS 513 System Security — Secret Sharing

4. Lecture Notes on Secret Sharing 1 Definition

5. Katz, J., Lindell, Y. (2007). Introduction to Modern Cryptography: Principles and Protocols. United States: CRC Press.

Jenit Tomy

Studied B.Tech in Computer Science from Government Engineering College, Thrissur.

Currently doing M.Tech (Research), Department of CSA, IISc Bengaluru.

Works in Cryptography.

Email id: jenittomy@gmail.com 

Linked-in: www.linkedin.com/in/jenit-tomy