Paper 2010/540

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).