1 of 8

SECRET SHARING SCHEME

BY

ISHITA PANDEY

1st YEAR

2 of 8

AIM

  • Our main is to divide our SECRET into say “n” pieces D1,D2,D3,……,Dn
  • Now these pieces are divided in such a way that knowledge of any “k” or more pieces of our SECRET will make our SECRET easily decoded.
  • BUT if we have KNOWLEDGE of “k-1” pieces or less then that then our SECRET is totally UNCOMPUTABLE.
  • (k,n) =THRESHOLD SCHEME

​

​

3 of 8

PROCEDURE

1)Choose how many parts you require to open any secret. Let say (k-1) coefficients a1,a2,a3,……….,ak-1

 2)f(x)=a0+a1*x+a2*x2+………+ak-1*xk-1

 

3)Let substitute a0 by secret “S”

 

4) f(x)=S+a1*x+a2*x2+………+ak-1*xk-1

 

5)Now we can construct [1,f(i)] where i=1,2,3,…..,n

 

​

4 of 8

EXAMPLE

  • Let S=6583
  • N=6 and k=3
  • Choose random integers a1=108 and a2=43
  • F(x)=6583+108*x+43*x2
  • Secret share points
  • (1,6734),(2,6971),(3,7294),(4,7703),(5,8198),(6,8779)
  • Now we give each participant a different single point [both “x” and f(x)]

5 of 8

RECONSTRUCTING THE SECRET

  • In order to reconstruct the original secret from any k-out-of-n parts, we need to recreate the polynomial that we defined in the beginning. This can be achieved with the Lagrange Polynomial Interpolation.

​

​

  • So now applying this in our example we randomly select 3 out of 6 parts.
  • We can easily reconstruct the secret.

​

​

                                        

                                        

6 of 8

Application

  • Yao’s Millionaire Problem-The Millionaires' Problem is an important problem in cryptography, the solution of which is used in e-commerce and data mining. Commercial applications sometimes have to compare numbers which are confidential and whose security is important.
  • A set of parties with private inputs wish to compute some joint function of their input.

7 of 8

References

8 of 8

THANK-YOU !!