(N,1)-(N, N scheme (N, 1: Make N copies of the secret and give each user a copy (N, N): Let s be the secret, let M be a large number Let s, s,,, sx be n random numbers such that s;+S2+…S= s mod m Assign s; to the ith user
6 (N,1) - (N,N) scheme • (N,1) :Make N copies of the secret and give each user a copy • (N,N) :Let s be the secret, let M be a large number Let s1 , s2 ,…, sN be N random numbers such that s1+ s2+…+ sN = s mod M Assign si to the ith user
Adi shamir (N, d )-Scheme Pick a prime p ● and a random polynomia f(r)=ad-axd-l+ adxd-i +.+ ao mod p ao=f(0)=s User i receive s, f(i) mod p Any d users can interpolate to obtain and ence s any d-I users can not obtain any information about s
7 Adi Shamir (N,d)-Scheme • Pick a prime p • and a random polynomial f (x) = ad-1 x d-1 + ad-2 x d-2 +…+ a0mod p a0 = f (0) = s • User i receive si = f (i) mod p • Any d users can interpolate to obtain f and hence s • Any d-1 users can not obtain any information about s
Vandermonde system a1 Vandermonde system is full rank and hence as a unique solution
8 Vandermonde System • Vandermonde System is full rank and hence has a unique solution = − − − − d i i i d d d d d d s s s a a a i i i i i i 2 1 1 1 0 1 1 2 2 1 1 1 1 ... 1 ... 1
bit commitment Problem: Alice wants to sell Bob information regarding police informants within his Mafia empire. Alice doesnt trust Bob enough to tell him the rats without getting paid first they might suddenly disappear). Bob thinks that the deal is a police setup and won' t give her the money until she commits to names
9 bit commitment Problem: • Alice wants to sell Bob information regarding police informants within his Mafia empire. • Alice doesn’t trust Bob enough to tell him the rats without getting paid first (they might suddenly disappear). • Bob thinks that the deal is a police setup, and won’t give her the money until she commits to names
bit commitment Commitment Bob→ Alice: random r Aice→Bob:{rm}k Revelation Aice→Bob;k Bob decrypts the message and verifies r Discussion The random value r is used for freshness and to stop Alice from finding two messages where im]ki== tm'Jk2 i.e. forcing alice to commit Bob does not know k until revelation so cannot brute force the message space
10 bit commitment Commitment: • Bob → Alice: random r • Alice → Bob: {r|m}k Revelation: • Alice → Bob: k • Bob decrypts the message and verifies r Discussion: • The random value r is used for freshness and to stop Alice from finding two messages where {m}k1 == {m’}k2 – i.e. forcing Alice to commit • Bob does not know k until revelation so cannot brute force the message space