Security protocols 曹天杰 Tianjie Cao ticao(cumt. edu. cn College of Computer science and echnology, China University of Mining and Technology Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.9
1 Security Protocols 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.9
secret splitting Problem You are the ceo of coca-cola, you are esponsible for bringing a refreshing taste to zillions of people all over the world, but want to keep the recipe secret from Pepsis industrial spies. You could tell your most trusted employees they could defect to the opposition they could fall to rubber hose cryptanalysis How can we split a secret among two parties where each piece by itself is useless?
2 secret splitting Problem: • You are the CEO of Coca-Cola. You are responsible for bringing a refreshing taste to zillions of people all over the world, but want to keep the recipe secret from Pepsi’s industrial spies. • You could tell your most trusted employees – they could defect to the opposition – they could fall to rubber hose cryptanalysis • How can we split a secret among two parties where each piece by itself is useless?
secret splitting Algorithm: Assume Trent wishes to protect the message m Trent generates a random bit string r, the same length m Trent computes m=s Trent gives Alice r Trent gives Bob s Each of the pieces is called a shadow To reconstruct m, alice and bob xor their shadows together. If r is truly random the system is perfectly secure OTP) To extend the scheme to n people generate n random bit strings e. g.m⊕rs⊕t=u
3 secret splitting Algorithm: Assume Trent wishes to protect the message m: Trent generates a random bit string r, the same length m. Trent computes m r = s Trent gives Alice r Trent gives Bob s • Each of the pieces is called a shadow. • To reconstruct m, Alice and Bob XOR their shadows together. • If r is truly random, the system is perfectly secure (OTP). • To extend the scheme to n people, generate n random bit strings e.g. m r s t = u
secret sharing Problem You are responsible for a small third world country's nuclear weapons program You want to ensure that no single lunatic can launch a missile You want to ensure that no two lunatics can collude to launch a missille You want at least three of five officers to be lunatics before a missile can be launched We call this a 35 threshold scheme
4 secret sharing Problem: • You are responsible for a small third world country’s nuclear weapons program. • You want to ensure that no single lunatic can launch a missile. • You want to ensure that no two lunatics can collude to launch a missile. • You want at least three of five officers to be lunatics before a missile can be launched. • We call this a (3,5) threshold scheme
Threshold Scheme Users and a threshold d Any group of d or more users can jointly obtain the secret Any group of d-1 or less users can not jointly obtain any information about the secret assume we have a dealer here who has the secret
5 Threshold Scheme • N users and a threshold d • Any group of d or more users can jointly obtain the secret • Any group of d-1 or less users can not jointly obtain any information about the secret • Assume we have a dealer here who has the secret
(N, 1)-(N, M scheme (N, 1: Make N copies of the secret and give each user a copy (N, M: Let s be the secret, let M be a large number Let s,, s,., sx be n random numbers such that S +S2+.+SN=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 polynomial f(x)=adrdl+ ad-xxd-2+.+ ao mod p f(0) User i receive si-f(i)mod p Any d users can interpolate to obtain f and he ence s any d-1 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 Vandermonde system is full rank and hence has 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 wont 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:{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 imi==tmy k2 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