ralphmerridew

Mental Assassin

Mar 30th, 2012
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.49 KB | None | 0 0
  1. The assassin problem:
  2. A game has N players. Generate a permutation of them such that each player learns only the identity of the person after him/herself. Using an outside person to randomize is not permitted.
  3.  
  4. This method, while more complicated then the other methods, doesn't even require any physical objects to be exchange. Players could agree on a secret permutation using only public communication in a chatroom. It is based on techniques from RSA's "mental poker" paper: http://people.csail.mit.edu/rivest/ShamirRivestAdleman-MentalPoker.pdf
  5.  
  6. Notation: Let "string" be a numeric encoding of the string. For example, an ASCII-based encoding would represent "ALICE" as 6576736769.
  7.  
  8. Step 1: Generate a permutation. Each player will learn his/her own place in the permutation.
  9. 1a) Start with the strings "ONE", "TWO", "THREE", ... up to N as text.
  10. 1b) Each player generates a secret encryption key. (Call Alice's key A1, Bob's B1, ...)
  11. 1c) Alice shuffles the strings, and encrypts each one with her key. She then announces the result.
  12. (So with four players, she might say E(A1, "TWO"), E(A1, "FOUR"), E(A1, "ONE"), E(A1, "THREE"))
  13. 1d) Bob encrypts each number Alice announced with his key, shuffles them, and announces the result.
  14. (So he might say E(B1, E(A1, "THREE")), E(B1, E(A1, "FOUR")), E(B1, E(A1, "TWO")), E(B1, E(A1, "ONE"))
  15. 1e) This repeats for each person. At the end, each entry on the list will have been encrypted by each person once, and shuffled by each player.
  16. (So the list might be E(D1, E(C1, E(B1, E(A1, "FOUR")))), E(D1, E(C1, E(B1, E(A1, "ONE")))), E(D1, E(C1, E(B1, E(A1, "TWO")))), E(D1, E(C1, E(B1, E(A1, "THREE")))) )
  17.  
  18. 1f) Now, Alice may optionally switch any card after the first with the first one. She then decrypts every number other than the first with her key.
  19. (So the list might be E(D1, E(C1, E(B1, E(A1, "TWO")))), D(A1, E(D1, E(C1, E(B1, E(A1, "ONE"))))), D(A1, E(D1, E(C1, E(B1, E(A1, "FOUR"))))), D(A1, E(D1, E(C1, E(B1, E(A1, "THREE"))))). Since the encryption is commutative, this simplifies to (E(D1, E(C1, E(B1, E(A1, "TWO")))), E(D1, E(C1, E(B1, "ONE"))), E(D1, E(C1, E(B1, "FOUR"))), E(D1, E(C1, E(B1, "THREE"))))).
  20.  
  21. 1g) Bob may optionally switch any card after the second with the second card. He then decrypts every card other than the second with his key.
  22. (So the list might be (D(B1, E(D1, E(C1, E(B1, E(A1, "TWO"))))), E(D1, E(C1, E(B1, "ONE"))), D(B1, E(D1, E(C1, E(B1, "FOUR")))), D(B1, E(D1, E(C1, E(B1, "THREE"))))). This simplifies to (E(D1, E(C1, E(A1, "TWO"))), E(D1, E(C1, E(B1, "ONE"))), E(D1, E(C1, "FOUR")), E(D1, E(C1, "THREE"))))
  23.  
  24. 1h) And so on. The k-th player may optionally switch any card after the k-th with the k-th, then decrypts every card other than the k-th with his/her key.
  25. (After all that, the list might end up simplifying to (E(A1, "TWO"), E(B1, "ONE"), E(C1, "FOUR"), E(D1, "THREE"))
  26.  
  27. 1i) At this point, the k-th person decrypts the k-th entry with his/her key. They now have a random permutation, and each person knows his/her own place in that permutation.
  28. (Bob is first; Alice is second; Diane is third; Charles is fourth.)
  29.  
  30.  
  31.  
  32.  
  33. Step 2: Informing each person of which player follows him in the permutation.
  34. 2a) Each player chooses two more keys (Alice chooses A2 and A3, ...)
  35. 2b) Start with the list ("ONE", "TWO", ... )
  36. 2c) Each player gives the numeric encoding of his/her name.
  37. 2d) Suppose Alice learned she was at position i in the permutation. She will encrypt every entry with A2. She will then encrypt the i-th entry with A3, and the (i-1)st entry with the encoding of her name, then reveals the result.
  38. (E("ALICE", E(A2, "ONE")), E(A3, E(A2, "TWO")), E(A2, "THREE"), E(A2, "FOUR"))
  39. 2e) Bob encrypts every entry with B2. He encrypt the entry in his own position with B3, and the entry preceding it with his name, then reveals the result.
  40. (E(B3, E(B2, E("ALICE", E(A2, "ONE")))), E(B2, E(A3, E(A2, "TWO"))), E(B2, E(A2, "THREE")), E("BOB", E(B2, E(A2, "FOUR"))))
  41. 2f) And so on.
  42. (E(C2, E(B3, E(B2, E("ALICE", E(A2, "ONE"))))), E(C2, E(B2, E(A3, E(A2, "TWO")))), E("CHARLES", E(C2, E(B2, E(A2, "THREE")))), E(C3, E(C2, E("BOB", E(B2, E(A2, "FOUR"))))))
  43. (E(D2, E(C2, E(B3, E(B2, E("ALICE", E(A2, "ONE")))))), E("DIANE", E(D2, E(C2, E(B2, E(A3, E(A2, "TWO")))))), E(D3, E(D2, E("CHARLES", E(C2, E(B2, E(A2, "THREE")))))), E(D2, E(C3, E(C2, E("BOB", E(B2, E(A2, "FOUR")))))))
  44. 2g) Each player then successively decrypts each entry with his/her second key, and announces the result.
  45. (D(D2, D(C2, D(B2, D(A2, E(D2, E(C2, E(B3, E(B2, E("ALICE", E(A2, "ONE")))))))))), D(D2, D(C2, D(B2, D(A2, E("DIANE", E(D2, E(C2, E(B2, E(A3, E(A2, "TWO")))))))))), D(D2, D(C2, D(B2, D(A2, E(D3, E(D2, E("CHARLES", E(C2, E(B2, E(A2, "THREE")))))))))), D(D2, D(C2, D(B2, D(A2, E(D2, E(C3, E(C2, E("BOB", E(B2, E(A2, "FOUR")))))))))))
  46. Using commutativity, this will simplify:
  47. (E(B3, E("ALICE", "ONE")), E("DIANE", E(A3, "TWO")), E(D3, E("CHARLES", "THREE")), E(C3, E("BOB", "FOUR")))
  48. 2h) Each player takes the entry at his/her position, and decrypts it with his/her third key. He/she then attempts to decrypt the result with the name of each player until getting the appropriate text.
  49. (Alice calculates D(A3, E("DIANE", E(A3, "TWO"))) == E("DIANE", "TWO").
  50. She then calculates D("BOB", E("DIANE", "TWO")) == nonsense
  51. D("CHARLES", E("DIANE", "TWO")) == nonsense
  52. D("DIANE", E("DIANE", "TWO")) == "TWO".
  53. She then knows Diane is her target.)
Advertisement
Add Comment
Please, Sign In to add comment