Dinning Cryptographers Problem

1 collaborator

Gonzalo Etse (Author)

WHAT IS IT?

This model tries to replicate the dinning cryptographers problem made by David Chaum in the early 1980s.

"Three cryptographers gather around a table for dinner. The waiter informs them that the meal has been paid for by someone, who could be one of the cryptographers or the National Security Agency (NSA). The cryptographers respect each other's right to make an anonymous payment, but want to find out whether the NSA paid. So they decide to execute a two-stage protocol."

Despite the similar name, the dining cryptographers problem is unrelated to the dining philosophers problem.

HOW IT WORKS

Three cryptographers are initiated and one NSA agent is on the middle. One of all 4 is randomly selected to be the person paying dinner.
Next the cryptographers form couples with all others (in this case 3 couples are formed) and toss a coin which result only them can see.

Heads is = 0 Tails is = 1

Once this is done, they inform the result computing both the coins each one can see based on the XOR function. If one of the cryptographers actually paid, he will announce the inverse of the XOR function.

Once all members have announced the result, again a XOR function is computed over the 3 results.

If the final results is 1 => it means one of them paid the Dinner (but only the one that pays knows whom).
If the final results is 0 => it means the NSA agent paid the Dinner.

This way they can communicate annonimously.

But, if one of them lies, then there's a collision and the result is null.

HOW TO USE IT

Go slow will allow to view how the mechanism works.
We can select the number of cryptographers, but due to the coding right now it can't be selected (would have to update a lot of the code) We can select the probability of them lying, which will increase the chances of the prediction colluding. The probability of them lying is divided in equal parts to each them.

THINGS TO NOTICE

Check how with 0% lying chance, they can communicate who the paying person is with 100% accuarecy, without ever divulging who actually paid the dinner!

THINGS TO TRY

Play with lying probability too se how it affects the success ratio

EXTENDING THE MODEL

1) Number of cryptographers should be extended 2) Add chances of one cryptographer being 100% malicious 3) Add chances of attack in the middle

Much is without finish (due to personal problems I had 1 day only to do this, despite wanting to spend more time on it and it being the most fun I had in some weeks). For that I excuse for myself for missing things that would be easily fixed and added. I'll try to complete it regardless of the end-line being over.

NETLOGO FEATURES

XOR function, ownership, no patches.

RELATED MODELS

Although I had decided to use this idea previously (for my interest on cypherpunks mailing lists), I later found the dinning philosophers model in netLogo. Despite it being different, the architecture helped me figure out how to set the ownership of coins.

CREDITS AND REFERENCES

Professor Georgiy Bobashev Dinning philosophers model author Uri Wilensky

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

breed [cryptographers cryptographer]
breed [nsas nsa]
breed [coins coin]

globals [
  final_result
  correct_predictions ;; times cryptographers correctly predict who paid dinner (if them or NSA agent)
  incorrect_predictions ;; times cryptographers inccorectly predicted who paid dinner (if them or NSA agent)
  ratio
]

cryptographers-own [
  state                   ;; my current state: "PAID", "NOT PAID", "EATING"
  dishonesty                 ;; honesty level of the cryptographer
  left-coin right-coin    ;; the coin to their left, the coin to their right
  result                  ;; result
]

coins-own [
  home-xpos home-ypos home-heading     ;; where I belong when I'm on the table
  owners                                ;; the cryptographers that currently owns me
  tossed?                               ;; whether I'm currently tossed
  flip                                ;; 0 or 1
]

nsas-own [
  state
]

to setup
  clear-all
  make-turtles
  reset-ticks
end 

to make-turtles
  set-default-shape cryptographers "person"
  set-default-shape coins "circle"
  set-default-shape nsas "person"
  set correct_predictions 0
  set incorrect_predictions 0
  ;; create-ordered- equally spaces the headings of the turtles,
  ;; in who number order
  create-ordered-cryptographers num-cryptographers [
    set size 0.1
    jump 0.35
    set state "EATING"
    set color yellow
    set result "-"
    set dishonesty lying-probability / num-cryptographers
  ]
  create-ordered-coins num-cryptographers [
    rt 180 / num-cryptographers
    jump 0.25
    rt 180
    set size 0.1
    set color white
    set tossed? false
    set owners nobody
    set home-xpos xcor
    set home-ypos ycor
    set home-heading heading
    set flip 3
  ]
  ask cryptographers [
    set left-coin coin (who + num-cryptographers)
    ifelse who = 0
      [ set right-coin coin (2 * num-cryptographers - 1) ]
      [ set right-coin coin (who + num-cryptographers - 1) ]
  ]

  create-nsas 1 [
    ;jump 0.3
    set state "WATCHING"
    set size 0.1
    set ycor max-pycor
    set color blue
  ]
end 

to go
  restart
  wait 0.3
  ask one-of cryptographers [ update ]
  wait 0.3
  ask coins [ tossing ]
  ask cryptographers [ decision ]
  final-result
  reporting
  ;if incorrect_predictions = 1 [stop]
  if correct_predictions > 0 [
    set ratio (correct_predictions / (incorrect_predictions + correct_predictions))
  ]
  tick
end 

;; everybody gets a new color.

to restart
  ask cryptographers [
    ;; look up the color in the colors list indexed by our current state
    if state = "PAID" [
      set color yellow
      set state "EATING"
    ]
  ]
  ask nsas [
    if state = "PAID" [
      set color blue
      set state "WATCHING"
    ]
  ]
  ask coins [
    set shape "circle"
    set flip 3
    set color white
  ]
end 

;; cryptographers and NSA agent are updated to which one paid

to update
  let var random 100
  if var <= nsa-vs-cryp-prob-to-pay [
    ask one-of cryptographers [
      set state "PAID"
      set color red
    ]
  ]
  ;; Changes color of the NSA agent to red if he paid the dinner
  if var > nsa-vs-cryp-prob-to-pay [
    ask NSA 6 [
      set state "PAID"
      set color red
    ]
  ]
end 



;; 2 cryptographers select a coin that only they can see it's result

to acquire-coins-naive  ;; cryptographer procedure
  if [owners] of left-coin = nobody
    [ acquire-left ]
  if [owners] of right-coin = nobody
    [ acquire-right ]
end 

;; this is one of the coin only him and a partner can see

to acquire-left  ;; cryptographers coin ownership
  ask left-coin [
    set owners myself
  ]
end 

;; this is one of the coin only him and a partner can see

to acquire-right  ;; cryptographers coin ownership
  ask right-coin [
    set owners myself
  ]
end 

to tossing
  if any? coins with [shape = "circle"] [
    ask coins [
      ;let a random-float 1
      ifelse (flip = 3) and (random-float 1 > 0.5) [
        ;print "hi"
        set shape "coin tails"
        set color lime
        set flip 1
        ]
      [
        set shape "coin heads"
        set flip 0
        set color pink
        set tossed? true

      ]
      wait 0.2
    ]
  ]
end 

to decision
  let a 3
  let b 3
  ask left-coin [
    if flip = 0 [
      set  a 0
    ]
    if flip = 1 [
      set a 1
    ]
  ]
  ask right-coin [
    if flip = 0 [
      set  b 0
    ]
    if flip = 1 [
      set b 1
    ]
  ]

  ;; XOR Operation
  if color = yellow [
    if (a = 0) and (b = 0) [
      set result 0
    ]
    if (a = 0) and (b = 1) [
      set result 1
    ]
    if (a = 1) and (b = 0) [
      set result 1
    ]
    if (a = 1) and (b = 1) [
      set result 0
    ]
  ]
  if color = red [
    ;; XOR Operation
    if (a = 0) and (b = 0) [
      set result 1
    ]
    if (a = 0) and (b = 1) [
      set result 0
    ]
    if (a = 1) and (b = 0) [
      set result 0
    ]
    if (a = 1) and (b = 1) [
      set result 1
    ]
  ]
  ;; If the cryptographers is dishonest, he might lie = collusion
  if random-float 1 < dishonesty [
    ifelse (result = 1) [
      set result 0
    ]
    [
      set result 1
    ]
  ]
end 

to final-result
  let var1 1
  let var2 1
  let var3 1
  ;let final_result 1
  ask cryptographer 0 [
    if (result = 0)[
      set var1 0
    ]
    if (result = 1)[
      set var1 1
    ]
  ]
  ask cryptographer 1 [
    if (result = 0)[
      set var2 0
    ]
    if (result = 1)[
      set var2 1
    ]
  ]
    ask cryptographer 2 [
    if (result = 0)[
      set var3 0
    ]
    if (result = 1)[
      set var3 1
    ]
  ]
  if (var1 = 0) and (var2 = 0) and (var3 = 0)[
      set final_result 0
  ]
  if (var1 = 0) and (var2 = 0) and (var3 = 1)[
      set final_result 1
  ]
  if (var1 = 0) and (var2 = 1) and (var3 = 0)[
      set final_result 1
  ]
  if (var1 = 0) and (var2 = 1) and (var3 = 1)[
      set final_result 0
  ]
  if (var1 = 1) and (var2 = 0) and (var3 = 0)[
      set final_result 1
  ]
  if (var1 = 1) and (var2 = 0) and (var3 = 1)[
      set final_result 0
  ]
  if (var1 = 1) and (var2 = 1) and (var3 = 0)[
      set final_result 0
  ]
  if (var1 = 1) and (var2 = 1) and (var3 = 1)[
      set final_result 1
  ]
  print final_result
end 

to reporting
  ask nsa 6 [
    if (final_result = 0) and (color = red)[
      print "Correctly predicted NSA paid"
      set correct_predictions ( correct_predictions + 1 )
    ]
    if (final_result = 0) and (color = blue)[
      print "Incorrectly predicted NSA paid - there was collusion"
      set incorrect_predictions ( incorrect_predictions + 1 )
    ]
    if (final_result = 1) and (color = red)[
      print "Incorrectly predicted an anonymous Cryptographer paid - there was collusion"
      set incorrect_predictions ( incorrect_predictions + 1 )
    ]
    if (final_result = 1) and (color = blue)[
      print "Correctly predicted an anonymous Cryptographer paid"
      set correct_predictions ( correct_predictions + 1 )
    ]
]
end

There is only one version of this model, created over 3 years ago by Gonzalo Etse.

Attached files

File	Type	Description	Last updated
Dinning Cryptographers Problem.png	preview	Preview for 'Dinning Cryptographers Problem'	over 3 years ago, by Gonzalo Etse	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo