Share conversion, pseudorandom secret-sharing and applications to secure distributed computing

Abstrakt:

We present a method for converting shares of a secret into shares of the same secret in a different secret-sharing scheme using only local computation and no communication between players.

We show how this can be combined with any pseudorandom function to create, from initially distributed randomness, any number of Shamir secret-sharings of (pseudo)random values without communication. We apply this technique to obtain efficient non-interactive protocols for secure computation of low-degree polynomials, which in turn give rise to other applications in secure computation and threshold cryptography. For instance, we can make the Cramer-Shoup threshold cryptosystem by Canetti and Goldwasser fully non-interactive, or assuming initially distributed randomness, we can compute any function securely in 2 rounds of communication.

The solutions are practical only for a relatively small number of players. However, in our main applications the number of players is typically small, and furthermore it can be argued that no solution that makes a black-box use of a pseudorandom function can be more efficient.