Secure communication puzzle# JobHunting - 待字闺中
j*x
1 楼
我老板想到的问题：
I came up an interesting problem after a student presentation: 12 of my
students want to find out their highest pay (but not other pay values).
The Gatech security group came up an elegant solution: students form a cycle
and they are all good citizens to follow the given rule. Upon receiving a
value v from its right neighbor, node i passes to its left neighbor a value
between i+1 and vi (inclusive) at his/her choice if vi > i otherwise passes
i. vi is node i's private value. The initiator starts with a number between
0 and vi. When a node sees the same number twice in two rounds, that value
is the highest pay among 12 students.
In fact, I can revise the algorithm to allow any number of initiators to
start and at any time while still generate the right answer. (If you want to
learn, take my Distributed System Design course in Spring 2012.)
Show that even each node only sees its right neighbor's message. The above
protocol is unfortunately not "secured". That is, more than the largest
value could be revealed if there is a smart student among 12 students.
One more question, if a "server" sees all messages passed around. Can the
server guess the private values if each node selects the value uniformly
random within the range specified in the rule at each round?
I came up an interesting problem after a student presentation: 12 of my
students want to find out their highest pay (but not other pay values).
The Gatech security group came up an elegant solution: students form a cycle
and they are all good citizens to follow the given rule. Upon receiving a
value v from its right neighbor, node i passes to its left neighbor a value
between i+1 and vi (inclusive) at his/her choice if vi > i otherwise passes
i. vi is node i's private value. The initiator starts with a number between
0 and vi. When a node sees the same number twice in two rounds, that value
is the highest pay among 12 students.
In fact, I can revise the algorithm to allow any number of initiators to
start and at any time while still generate the right answer. (If you want to
learn, take my Distributed System Design course in Spring 2012.)
Show that even each node only sees its right neighbor's message. The above
protocol is unfortunately not "secured". That is, more than the largest
value could be revealed if there is a smart student among 12 students.
One more question, if a "server" sees all messages passed around. Can the
server guess the private values if each node selects the value uniformly
random within the range specified in the rule at each round?
