Cryptography Reference
In-Depth Information
players have the incentive for participation. Furthermore, it is more desirable
to design a protocol where no player has an incentive to deviate as long as the
other players follow the protocol. This requirement is captured by the notion
of
equilibrium
in game theory. Although many rational secret sharing schemes
[1,14,12,13,15,5,7,8,9,10,11,20] have been developed achieving kinds of equilibria,
they are less satisfactory in some of the following aspects:
Notions of Equilibria.
Halpern and Teague [8] first proposed achieving a Nash
equilibrium
surviving iterated deletion of weakly dominated strategies
.ButKol
and Naor [10] later pointed out that some “intuitively bad” strategies cannot
be deleted anyway, then they proposed the notion of
strict Nash equilibrium
re-
quiring that each player's strategy is his unique best response to other players'
strategies. Although strict Nash equilibrium is a more appealing notion, it is too
restrictive to be achieved in many cases. Kol and Naor only achieved strict Nash
equilibrium in the two-party case assuming the existence of simultaneous broad-
cast channels
1
. In non-simultaneous channels, only an approximate equilibrium
(i.e.
-Nash equilibrium
) was achieved. Recently, Fuchsbauer et al. [5] proposed
computational strict Nash equilibrium
and
computational Nash equilibrium that
is stable with respect to trembles
. Ecient schemes achieving these equilibria
were built in standard communication networks, but only computational secu-
rity was guaranteed during the protocols. Moreover, equilibria concerning about
sequential rationality, such as
everlasting Nash equilibrium
[10] and
sequential
equilibrium
[20], were also achieved in the simultaneous channel.
Communication Models.
Halpern and Teague [8] first assumed private chan-
nels, the simultaneous broadcast channel as well as an on-line dealer. Gordon
and Katz [7] removed the on-line dealer by using a secure multi-party compu-
tation protocol among players, but the simultaneous broadcast channel was still
necessary. Actually, many rational secret sharing protocols [1,14,15,20] rely on
the assumption of simultaneous channels. Besides, some protocols [9,12,13] use
even stronger assumptions such as secure envelopes and ballot boxes.
Coalition-Resilience.
The main drawback of Kol and Naor's construction [10]
is that it cannot resist the collusion attack of even two players. But coalition-
resilience is an important requirement for
t
-out-of-
n
secret sharing. Previous
protocols achieved good resilience in either simultaneous broadcast channels [1]
or in the computational setting [5,11].
Unconditional/Computational Security.
In the computational setting, equi-
libria with good properties (e.g. coalition-resilience [11]) could be achieved and
more ecient protocols could run in standard communication networks [5], but
it works in the condition that all players are computationally bounded. When
higher security is required or players' computing power is unclear, a rational secret
1
When using simultaneous broadcast channels, players must decide on what value (if
any) to broadcast in a given round before observing the values broadcast by other
players.
Search WWH ::
Custom Search