Cryptography Reference
In-Depth Information
Table 1.
equilibrium
channel
coalition resilience
security
KN-[10]
strict Nash
simultaneous
1-resilient
unconditional
-Nash
non-simultaneous
1-resilient
unconditional
ADGH-[1]
-Nash
simultaneous
k -resilient
computational/
unconditional
FKN-[5]
strict Nash non-simultaneous
( t − 1)-resilient
computational
This paper
-Nash
non-simultaneous
( t − 1)-resilient
unconditional
Kol and Naor [10] provided constructions in both simultaneous and non-
simultaneous channels in the information theoretic setting. Our constructions
are similar to theirs in that shares are both in the form of lists with different
length and the recovering is accomplished by revealing the lists cell by cell. But
our 2-out-of-2 protocol is more ecient because shorter lists are involved and
simpler cells are contained. Details will be found in the remarks after Theorem 1.
General k -resilience was discussed in [1] where it achieved unconditional security
for k< 3 and computational security for k<n . But the protocols in [1] relied
on simultaneous channels. Ecient protocols with optimal coalition resilience
in standard communication networks were designed in [5]. Most importantly, it
achieved equilibria with appealing properties, such as strict Nash, and stability
with respect to trembles. But only computational security was guaranteed from
the beginning of the recovering process.
2 Preliminaries
In this section it introduces notions about rational secret sharing and information-
theoretic MACs, as well as concepts of the equilibrium to be achieved in this work.
2.1 Secret Sharing and Players' Utilities
In a t -out-of- n secret sharing scheme, a dealer (denoted as Dealer hereafter)
holding a secret distributes shares among n players such that the following two
conditions are satisfied:
1. Recoverability. Any group of t or more players puting their shares together
can uniquely determine the secret.
2. Secrecy. Any group of fewer than t players cannot recover the secret.
It usually assumes that Dealer is the trusted third party and each player is either
honest or malicious. In a game theoretic view, it is more realistic to view each
player as a rational party who acts only in his interest. To model rationality, we
define for each player P i a real-valued utility function u i such that everyone's
interest is to maximize his utility. The commonly used assumptions for defining
utilities in rational secret sharing are as follows [8]:
 
Search WWH ::




Custom Search