I wrote this blogpost on an 18 hour trip :) that I take once or twice a year to go home . I’ve been lately spending more time studying the mathematical foundations of cryptography, and a blog was deemed necessary to move from the theoretical to the intuitive.

Cryptography started as a casual reading and puzzles,then it became a target and now a passion .

In a series of blogpost I’ll try to explain in an intuitive way what I find the most interesting parts in cryptography I have no idea how long the series will span but let’s just say that it would be at least 3 blogposts long .

Secret Sharing

Secret Sharing is exactly how it sounds like , how do you share a secret among a group without any participant knowing the secret as a whole . It was invented by Adi Shamir (The S in RSA) and George Blakley independently in 1979 invented mean the creation of a viable scheme for the process. Both schemes Shamir Secret Sharing and Blakley’s are based on mathematical intuition . We will do the same start from the intuitive explanation moving to explaining both schemes .

Secret Sharing enables you (for ex) to split your Ethereum private key between n persons and set a threshold t of necessary parts to reconstruct it back . And from this principle we can think of multiple applications in the field of MPC or even Blockchains .

Intuition

• How many straight lines pass trough one point ? :

  • an infinity

• How many straight lines pass trough more than one point ? 2 points or 3 ?:

  • one a unique point

  

Emm do you see it ? Suppose your secret is 5 the straight line above has a parametric equation y = x+5 And to evaluate your secret you need to compute f(0) = 5 .

So if a person knows one point for example f(4) = 9 he can’t compute f(0) it can be anything . Now we can share the secret which is 5 into two parts :

• f(4) = 9
• f(7) = 12

And give each one to a different person .

What we did here is pick a straight line such as f(0) is equal to our secret we pick two random numbers from the line and give them to two other parties . Now you may ask me but how do I reconstruct the secret from those two ? And I’ll tell you to plot the points on a graph :) or find the slope because the secret is actually the y-intercept .

Now that we have an intuition let’s make things harder for our adversary,let’s make it more complex . What if instead of choosing a straight line you want to use something more difficult , more curved ? :

The graph above is of a quadratic function and f(x) = 5

The equation of the above function is :

• f(x)=x^2+3x+5

A Quadratic function is also refeered to as a second degree polynomial , and to find the secret you need at least 3 points (since 3 points determine one quadratic line).

Remember our secret is f(0) let’s split it among 3 participants we can do even four or more but the least number of shares required , is always the degree of our polynomial + 1 . Why ? Well because to reconstruct it we will use polynomial interpolation and it’s proven that you always need n+1 point to interpolate a polynomial of degree n at most .

Now a polynomial is defined as such :

• P(X) = a0 + a1 * X + a2 * X^2 + … + an * X^n

  • n is the degree of the polynomial
  • a0 is the secret

And for each order or degree k you need k+1 shares at least to retrieve the secret using polynomial interpolation (Lagrange or Hermite depending on the efficiency and complexity of the problem).

I won’t delve into the computational stuff such as the error or the noise or efficiency of which interpolation to use .

Shamir Secret Sharing

The scheme we described above was invented by Adi Shamir let’s describe it in a series of steps :

• A Dealer secretly picks coefficients Aj such as Aj belongs to the set of integers modulo p where p is a prime .

• Let S our secret the the final polynomial is :

  

• A Share Yi = a(Xi)

Shamir scheme is both ideal and efficient and also extendable :

• Ideal : The size of share is the size of the secret a no information is given besides this .
• Secure : Knowing any of the k-1 shares doesn’t give information about the secret .
• Extendable : You can add more people by computing more values

Blakley Scheme

Blakley intuition was beyond the idea of lines but of planes and hyperplanes . A Hyperplane is the vector space K-1 for example :

The hyperplane of the 3D Space is the plane (2D) , the hyperplane of the 2D space is the straight line (1D) .

• The secret is located on the intersection of hyperplanes

I won’t go into much detail here because the scheme is rarely used it’s not space efficient (apparently) .

I hope this small intro made you think intuitively about the problem and maybe invent your own scheme :)