|
We develop a new multi-party generalization of
Naor-Nissim indirect indexing, making it possible for many
participants to simulate a RAM machine with only poly-logarithmic
blow-up. Our most efficient instantiation (built from length-flexible
additively homomorphic public key encryption) improves the communication
complexity of secure multi-party computation for a number of problems
in the literature. Underlying our approach is a new multi-party variant
of oblivious transfer which may be of independent interest.[ Full Version ]
|