For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Batch Logical Protocols for Efficient Multi-Party Computation
Naoto KIRIBUCHI Ryo KATO Tsukasa ENDO Takashi NISHIDE Hiroshi YOSHIURA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2012/10/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
multi-party computation, secret sharing, batch logical protocol, secret shared database,
Full Text: PDF>>
It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). It enables multiple parties, each given a snippet of a secret s, to compute a function f(s) by communicating with each other without revealing s. However, one of the biggest problems with MPC is that it requires a vast amount of communication. Much research has gone into making each protocol (equality testing, interval testing, etc.) more efficient. In this work, we make a set of multiple protocols more efficient by transforming them into their equivalent batch processing form and propose two protocols: “Batch Logical OR” and “Batch Logical AND.” Using proposed protocols recursively, we also propose “Batch Logical OR-AND” and “Batch Logical AND-OR,” and show arbitrary formula consisting of Boolean protocols, OR gates, and AND gates can be batched. Existing logical OR and logical AND protocols consisting of t equality testing invocations have a communication complexity of O(t), where is the bit length of the secrets. Our batched versions of these protocols reduce it to O( + t). For t interval testing invocations, they reduce both communication and round complexity. Thus they can make the queries on a secret shared database more efficient. For example, the use of the proposed protocols reduces the communication complexity for a query consisting of equality testing and interval testing by approximately 70% compared to the use of the corresponding existing protocols. The concept of the proposed protocols is versatile and can be applied to logical formulae consisting of protocols other than equality testing and interval testing, thereby making them more efficient as well.