**Rational Secret Sharing with Side Information in Point-to-Point Networks via Time-Delayed Encryption**

*Anna Lysyanskaya and Aaron Segal*

**Abstract: **In this paper, we give the first construction of a rational secret
sharing protocol that is strict Nash (or Nash with respect to
trembles) in the computational sense, works in a standard
point-to-point network with loose synchronization (i.e. does not rely
on the availability of a broadcast channel), and can tolerate
players with arbitrary side information about the secret. Since this
has been proved impossible in the plain model, our protocol requires
us to make assumptions about upper and lower bounds on the
computational resources of the participants, and also to assume that
they are out of sync with each other by at most a known quantity
$\tau$ and that their network latency is at most some known quantity
$\Delta$. Specifically, we define and realize (in the random-oracle
model, and assuming so-called standard architecture) time-delayed
encryption, a primitive that allows a sender to create a ciphertext
such that, for some parameter $h$, it will take $\Omega(2^h)$ time for
the recipient to recover the plaintext, where, following the work on
memory-bound functions, time is measured in memory accesses.

Rational parties will prefer to follow our protocol for reconstructing the secret even given a lot of side information about this secret. This was not true of any of the previously proposed strict Nash protocols for this task: In fact access to side information gave players in those protocols an incentive to deviate. As a result, for the first time, we have a rational secret reconstruction protocol that can be used in applications where the secret can be useful in the outside world (e.g. it can give players access to a valuable resource, or decrypt a file).

**Category / Keywords: **secret sharing, game theory, rational cryptography, time release cryptography

**Publication Info: **Submitted to TCC 2011

**Date: **received 21 Oct 2010

**Contact author: **aaronak at cs brown edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20101025:151021 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]