Cryptology ePrint Archive: Report 2007/341
Multi-Party Indirect Indexing and Applications
Matthew Franklin and Mark Gondree and Payman Mohassel
Abstract: 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.
Category / Keywords: communication complexity, oblivious RAM machine, privacy-preserving protocols, secure multiparty computation
Publication Info: This is the full version of an article to appear at Asiacrypt 2007.
Date: received 29 Aug 2007
Contact author: gondree at cs ucdavis edu
Available format(s): PDF | BibTeX Citation
Version: 20070905:062845 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]