Secure Multiparty Computation for the case of dishonest majority
has previously been known as the case where no efficient solution
was possible, since here one cannot avoid using expensive public-key
machinery. However, in a recent of line of research it has been shown
that all the hard work can be pushed into a preprocessing phase
that is independent of the function to be computed. Then, in an
on-line phase, one can compute the function very efficiently
using only cheap information theoretic primitives.
In this talk we survey some of the latest results in this line on research.
For instance, we now have optimal protocols in the preprocessing model
that have complexity linear in both size of circuit to compute and the number
of players, yet tolerate corruption of all but one player.
Joint work with Rikke Bendlin, Claudio Orlandi, Valerio Pastro, Nigel
Smart and Sarah Zakarias.