DOC PREVIEW
Purdue CS 59000 - How to Play Any Mental Game

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

What Is a Mental Game?Games as State MachinesAdversary ModelGame ModelsFinding a Game ModelProblemTm-GamesComputational ModelCommunications ModelConstraintsHandling Passive AdversariesOblivious TransferOT Using Trapdoor PermutationsOT: Step 1OT: Step 2OT: Step 3OT: Step 4OT ObservationsCombined Oblivious TransferCOT Boolean FunctionsCOT AND: Step 1COT AND: Step 2COT AND: Step 3COT AND: Step 4COT AND: Step 5COT ChainingTransforming GamesCrash Course in $S_5$Computing in $S_5$Multiply by ConstantInversesMultiply Two VariablesSwapping SharesPrivacy Against Passive AdversariesMalicious AdversariesHandling Malicious AdversariesEngagement ProtocolPlaying Despite MaliceContributionsHow to Play Any MentalGamePaper by Oded Goldreich, Silvio Micali, and Avi WigdersonPresentation by Paul KuliniewiczCS 590T - Fall 2004 – p. 1What Is a MentalGame?Another way to look at secure multipartycomputation.Common input CI.Each player i has private input xi.Each player should receive resultf(CI, x1, . . . , xn) without learning about otherplayers’ private inputs.CS 590T - Fall 2004 – p. 2Games as StateMachinesSet S = {σ1, σ2, . . .} of possible states.Each player i has a knowledge functionKi(σ) that represents i’s knowledge at stateσ.Each action is a state transition.At the final state, each player i receivespayoff pi(σ).CS 590T - Fall 2004 – p. 3Adversary ModelPassive AdversariesFollow the rules of the game.Try to learn more information than given byKi(σ).Work alone.Malicious AdversariesMay violate the rules arbitrarily.Essentially a Byzantine player.May cooperate with other maliciousadversaries.CS 590T - Fall 2004 – p. 4Game ModelsGame theory tells us how to select moveswell, but not how to actually play!A game must be played within some gamemodel.Example: n people playing poker:Sitting around a table with a deck of cards.Over a network with public-keycryptography.CS 590T - Fall 2004 – p. 5Finding a GameModelAny n-player game can be played with n + 1people by using a trusted third party:Knows exactly what state the game is in.Privately communicates Ki(σ) to eachplayer.Executes moves on behalf of the players.But requiring n + 1 people for an n-playergame is a somewhat “grotesque” result!How would you play NEWPOKER with nplayers with a deck of cards?CS 590T - Fall 2004 – p. 6ProblemIs there a model (physical or mathematical)which makes all n-player games playable byn players?Yes!Even with passive adversaries?Yes!Even with malicious adversaries?Yes, if fewer than half the players aremalicious.CS 590T - Fall 2004 – p. 7Tm-GamesConsider a special class of games: Turingmachine games:Turing machine M.Private inputs x1, . . . , xn.Players want to compute y = M(x1, . . . , xn)without revealing xivalues to other players.The solution for playing Tm-gamesgeneralizes to all games.CS 590T - Fall 2004 – p. 8Computational ModelEach player i is a probabilisticpolynomial-time Turing machine runningprogram Si.Each Turing machine has:A private read-only input tape.A private write-only output tape.A private read/write work tape.CS 590T - Fall 2004 – p. 9CommunicationsModelThe Turing machines share:A common read-only input tape.A common write-only output tape.Between each pair of machines i and j is atape that i writes and j reads.All machines share a common clock.Messages sent in a particular time intervalarrive at that same interval.CS 590T - Fall 2004 – p. 10ConstraintsAgreementAt the end of execution, for all i and j, i’sprivate output matches j’s private output.CorrectnessThe result of running (S1, . . . , Sn) should bethe same as the result of running M.PrivacyFor all T ⊂ {1, . . . , n}, T ’s combined privateoutputs are indistinguishable from theinformation computable from the privateinputs xiknown by T .CS 590T - Fall 2004 – p. 11Handling PassiveAdversariesFor now, assume that all adversaries arepassive.Malicious adversaries will be introducedlater.As long as trapdoor functions are available,Tm-games can be played despite passiveadversaries.In particular, we need encryption andtrapdoor permutations.Two oblivious transfer protocols will beconstructed.CS 590T - Fall 2004 – p. 12Oblivious TransferAlice starts with bits b0and b1.Bob chooses α ∈ {0, 1} and receives bα.Alice learns nothing about α.Bob learns nothing about b1−α.By repeating the single-bit protocol, data ofarbitary size can be transfered obliviously.CS 590T - Fall 2004 – p. 13OT Using TrapdoorPermutationsLet f be a trapdoor permutation with arandom bit. Then:It is infeasible to compute f−1given f.Any input x produces a “random bit” Bf(x)that can be computed in polynomial timegiven f and x.Given only f(x), the probability of correctlydetermining Bf(x) is approximately 1/2.A trapdoor permutation without a random bitcan be transformed into one that has arandom bit.CS 590T - Fall 2004 – p. 14OT: Step 1Alice generates trapdoor function with arandom bit f and its inverse f−1.Alice sends f to Bob and keeps f−1private.CS 590T - Fall 2004 – p. 15OT: Step 2Bob picks random x0and x1in f’s domain.Bob sends (u, v) to Alice, such that:(u, v) =(f(x0), x1) if α = 0(x0, f(x1)) if α = 1CS 590T - Fall 2004 – p. 16OT: Step 3Alice computes c0= Bf(f−1(u)) andc1= Bf(f−1(v)).Alice computes d0= b0⊕ c0and d1= b1⊕ c1.Alice sends (d0, d1) to Bob.CS 590T - Fall 2004 – p. 17OT: Step 4Bob computes bα= dα⊕ Bf(xα).CS 590T - Fall 2004 – p. 18OT ObservationsThis protocol works for passive adversaries:Alice never receives any information aboutα.Bob can’t compute b1−αbecause c1−αisessentially random to him.For malicious adversaries, steps need to betaken to prevent Bob from just sending(f(x0), f(x1)) in Step 2.The solution to this isn’t mentioned in thepaper.CS 590T - Fall 2004 – p. 19Combined ObliviousTransferCombined oblivious transfer is a Booleansecure two-party computation algorithm.Alice has private value a.Bob has private value b.Alice learns g(a, b) without learning b.Bob learns neither a nor g(a, b).CS 590T - Fall 2004 – p. 20COT BooleanFunctionsIdea: represent each input or output bit with aunique encryption key.Alice receives the decryption key associatedwith the output bit.NOT gates are trivial – flip the mapping usedfor one bit.AND gates can be constructed.Any other Boolean function can be built bycomposing AND and NOT gates.CS 590T - Fall 2004 – p. 21COT AND: Step 1Bob generates six encryption/decryption keypairs.Bob randomly associates an encryption


View Full Document

Purdue CS 59000 - How to Play Any Mental Game

Documents in this Course
Lecture 4

Lecture 4

42 pages

Lecture 6

Lecture 6

38 pages

Load more
Download How to Play Any Mental Game
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view How to Play Any Mental Game and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view How to Play Any Mental Game 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?