Batch Logical Protocols for Efficient Multi-Party Computation

スポンサーリンク

概要

• 論文の詳細を見る

• 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(lt), where l is the bit length of the secrets. Our batched versions of these protocols reduce it to O(l+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.

著者

• YOSHIURA Hiroshi

  University of Electro-Communications

• Nishide Takashi

  Kyushu University

• Endo Tsukasa

  Toshiba Corporation

• KIRIBUCHI Naoto

  University of Electro-Communications

• KATO Ryo

  University of Electro-Communications

関連論文

• Digitally Signed Document Sanitizing Scheme with Disclosure Condition Control(Application)(Cryptography and Information Security)
• Batch Logical Protocols for Efficient Multi-Party Computation
• Reducing Communication Complexity of Random Number Bitwise-Sharing for Efficient Multi-party Computation
• Reducing Communication Complexity of Random Number Bitwise-Sharing for Efficient Multi-party Computation
• A Recommendation System for Anonymous Fingerprinting of Text Posted on Social Networks
• Batch Logical Protocols for Efficient Multi-Party Computation

スポンサーリンク