Unconditionally Secure Rational Secret Sharing in Standard Communication Networks - Information Security and Cryptology-ICISC 2010 - page 365

= 1. Then he quits and sets s = s 1 −δ

- Find some index I j

j− 1+ δ .
- Find someone cheats in recovering s j . Then he quits and sets s = s j− 1 .
- Find someone cheats in recovering I j . Then he quits and sets s = s j− 1 with
probability 1 q and s = s j with probability q .

- Find someone cheats in recovering s j . Then he quits and sets s = s j .
- Find someone cheats in recovering I j . Then he quits and sets s = s j

−

with

probability q and s = s j with probability 1 − q .
- Find someone cheats in recovering π j . Then he quits and sets s = s j .
Now we give some analysis to explain why the recovering process of Π induces an
-Nash equilibrium with ( t 1)-resilience. For simplicity, we neglect the negligible

part of caused by successfully forging the MAC. As a warm-up, we first show
that any single player has no incentive to deviate from the protocol. For a single
player P i , there are two cases:

−

(a) P i holds a list of length l .
It is important to note that P i cannot know he is holding the long list until
the protocol ends or it comes to his last cell (i.e. the l -th cell). Therefore,
for 1 j<l , P i guesses l ∗ = j anddeviatesinthe j -th iteration, then he

can get utility at most p a +(1

≤

p ) U random . P i has no incentive to deviate −

if it holds

p a +(1 p ) U random <b. − (3)

When it comes to the last cell (i.e. the l -th cell) and P i is not the first one to
send messages according to π l− 1 ,then P i knows that l ∗ = l

1and s = s l− 1 .
Actually, every other player can also conclude s = s l− 1 no matter what P i
does in the l -th iteration. Thus P i has no incentive to deviate.
(b) P i holds a list of length l ∗ .
Similarly, it can see that P i has no incentive to deviate in the j -th iteration
for 1

−

1, if the inequality (3) holds. When it comes to the l ∗ -
th iteration P i knows he is holding the short list because he is the first to
send messages in that iteration. Since P i is the first one to talk in the l ∗ -th
iteration, when P i determines for sure what the secret is, so do the other
players. Thus P i has no incentive to deviate.

l ∗ − ≤ j ≤

Then we give some intuition as to why the recovering process of Π is ( t

−

1)-

C

with 1 <

|C| ≤ t −

resilient. For any coalition 1, there are two cases:

(c) The short list holder is contained in .

Since the lists are of different length, players in

C

can easily determine l ∗
in advance. Thus ignoring the negligible probability of forging the MAC
successfully, the best option for players in

C

C is to get as much information

s l ∗ ,s l ∗ ,I l ∗ } about { as possible and secondarily, to make players outside C

know as little as possible. It is easy to see that if the inequality (3) holds C

has no incentive to deviate before the l ∗ -th iteration. In the l ∗ -th iteration,
•

deviates in recovering s l ∗ , the best result for is that they get s l ∗ If C C

guesses s = s l ∗ while no one else does. Thus C and the other players set