Abstract
We have continued our exploration of secure multiparty computation by showing how the secret-sharing schemes presented in the previous lecture enable private keys to be shared between several trusted third parties and then jointly decrypted, without ever fully revealing the private key. This makes it possible to integrate computational steps on homomorphic ciphers into multi-party computation protocols.
Next, we looked at two other basic tools for secure multiparty computation : garbled circuits and unconscious transfer protocols.
Garbledcircuits, introduced by A. Yao in 1982, are a secure bipartite computation protocol that is still very popular today, as it requires little communication and relies on low-cost symmetric encryption. The calculation is represented by a Boolean circuit which is " scrambled " (to mask the bit values on the circuit wires) by one of the participants, then executed by the other. An unconscious transfer protocol is used to scramble the secrets of the second participant. We have presented several optimizations that reduce execution time, and sketched out how to make the approach resistant to active attacks using the cut-and-choose technique .
Oblivioustransfer is a basic building block of many cryptographic protocols, including the BGW scheme presented in the previous lecture and the scrambled circuits studied in this course. An oblivious transfer protocol allows participant B to choose one of the N values proposed by participant A, without learning anything about the other values proposed by A, and without A learning B's choice. We have described the EGL oblivious transfer protocol " 1 among 2 ", then its extension to " 1 among N ", then Naor and Pinkas' approach to making EGL resistant to active attacks by participant B.
Finally, we discussed the problem of extending an unconscious transfer protocol to produce a large number of cheap transfers following a small number of expensive transfers. As shown by D. Beaver in 1996, it is possible to derive the unconscious transfer from the random unconscious transfer, and to realize the latter using a scrambled circuit for a pseudo-random generator.
