Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Computing and Networking Workshops (CANDARW)

Square Table Lookup Multiparty Computation Protocol

Zhongqi Wang, Keita Fuse, Takashi Nishide

Published Nov 1, 2022• 1 citation
Publisher

Abstract

A secure interval test protocol is a powerful and useful tool to check whether a shared secret value is within a particular interval without revealing any information about the secret value, and therefore it has important applications in secure multi-party computation, machine learning, privacy-preserving location services, and many other areas. The secure inerval test protocol can be used as a building block in larger or more complex systems. A secure table lookup protocol based on the secure interval test can be used to implement approximate calculations of certain functions. In this work, we propose a square table lookup protocol based on the secure interval test protocol, which improves the efficiency in a certain setting compared to the state-of-the-art secure table lookup protocol proposed by Morita el al. (CANS'19). We reduce the computational complexity of the table lookup protocol from$O(N)$to$O(\sqrt{N})$where$N$is the number of elements in the lookup table by changing the dimension of the lookup table from a one-dimensional array to a two-dimensional array, arranging it as a square matrix, and redesigning the procedure of secure table lookup protocol.

DOI
10.1109/candarw57323.2022.00048

Related papers

Constant-Round Multiparty Computation for Interval Test, Equality Test, and Comparison

Takashi Nishide, Kazuo Ohta

We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgard et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field p into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets via p/2 indirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 1, 2007•10 citations

Batch Logical Protocols for Efficient Multi-Party Computation

Naoto Kiribuchi, Ryo KATO, Tsukasa Endo +2 more

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•0 citations

Implementation of a Secure Multiparty Computation Protocol

Tahsin C. M. Dönmez

Secure multiparty computation (SMC) allows a set of parties to jointly compute a function on private inputs such that, they learn only the output of the function, and the correctness of the output is guaranteed even when a subset of the parties is controlled by an adversary. SMC allows data to be kept in an uncompromisable form and still be useful, and it also gives new meaning to data ownership, allowing data to be shared in a useful way while retaining its privacy. Thus, applications of SMC hold promise for addressing some of the security issues information-driven societies struggle with. In this thesis, we implement two SMC protocols. Our primary objective is to gain a solid understanding of the basic concepts related to SMC. We present a brief survey of the field, with focus on SMC based on secret sharing. In addition to the protocol im- plementations, we implement circuit randomization, a common technique for efficiency improvement. The implemented protocols are run on a simulator to securely evaluate some simple arithmetic functions, and the round complexities of the implemented protocols are compared. Finally, we attempt to extend the implementation to support more general computations.

•Dec 20, 2017•0 citations

Performance Analysis of Secure Multiparty Computation Protocol

Samiksha Shukla, Durgesh Kumar Mishra

In this paper we address the issue related to privacy, security, complexity and Implementation, various adversaries exist which hamper the secure multiparty computation. In the secure multiparty computation, a set of parties wishes to jointly compute some function of their inputs. Such a computation must preserve certain security properties, like privacy and correctness, even if some of the participating parties or an external adversary colludes to attack the honest parties.

Mapana Journal of Sciences•May 31, 2009•0 citations

A Privacy Preserved Two-Party Equality Testing Protocol

Shih-Fong Ciou, Raylin Tso

Secure multiparty computation was firstly introduced by Yao in 1982. Two-party equality testing is a special case of secure multiparty computation. It enables two entities to compare the equality of their secret data without revealing the data to the other party. This kind of protocols has been wildly investigated in the literature. However, in most of the existing protocols, the testing result is known by only one entity (informer). The other entity is informed about the testing result by the informer so she must fully trust the informer about the result she received. In this paper, we propose a new two-party equality testing protocol. In our protocol, although the final result is still informed by the informer, we allow the entity being informed to verify the correctness of the final result. In this way, the two entities can make sure whether the secret information they preserved are equivalent or not without revealing it. We will also give the security analysis and show that this protocol does not leak any information about the secret value.

International Conference on Genetic and Evolutionary Computing•Aug 1, 2011•2 citations

A Taxonomy of Secure Two-Party Comparison Protocols and Efficient Constructions

Nuttapong Attrapadung, Goichiro Hanaoka, Shinsaku Kiyomoto +2 more

Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols.We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.

Conference on Privacy, Security and Trust•Aug 1, 2017•10 citations
A secure interval test protocol is a powerful and useful tool to check whether a shared secret value is within a particular interval without revealing any information about the secret value, and therefore it has important applications in secure multi-party computation, machine learning, privacy-preserving location services, and many other areas. The secure inerval test protocol can be used as a building block in larger or more complex systems. A secure table lookup protocol based on the secure interval test can be used to implement approximate calculations of certain functions. In this work, we propose a square table lookup protocol based on the secure interval test protocol, which improves the efficiency in a certain setting compared to the state-of-the-art secure table lookup protocol proposed by Morita el al. (CANS'19). We reduce the computational complexity of the table lookup protocol fromO(N)O(N)O(N)toO(N)O(\sqrt{N})O(N​)whereNNNis the number of elements in the lookup table by changing the dimension of the lookup table from a one-dimensional array to a two-dimensional array, arranging it as a square matrix, and redesigning the procedure of secure table lookup protocol.
We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgard et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field p into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets via p/2 indirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.
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.
Secure multiparty computation (SMC) allows a set of parties to jointly compute a function on private inputs such that, they learn only the output of the function, and the correctness of the output is guaranteed even when a subset of the parties is controlled by an adversary. SMC allows data to be kept in an uncompromisable form and still be useful, and it also gives new meaning to data ownership, allowing data to be shared in a useful way while retaining its privacy. Thus, applications of SMC hold promise for addressing some of the security issues information-driven societies struggle with. In this thesis, we implement two SMC protocols. Our primary objective is to gain a solid understanding of the basic concepts related to SMC. We present a brief survey of the field, with focus on SMC based on secret sharing. In addition to the protocol im- plementations, we implement circuit randomization, a common technique for efficiency improvement. The implemented protocols are run on a simulator to securely evaluate some simple arithmetic functions, and the round complexities of the implemented protocols are compared. Finally, we attempt to extend the implementation to support more general computations.
Secure multiparty computation was firstly introduced by Yao in 1982. Two-party equality testing is a special case of secure multiparty computation. It enables two entities to compare the equality of their secret data without revealing the data to the other party. This kind of protocols has been wildly investigated in the literature. However, in most of the existing protocols, the testing result is known by only one entity (informer). The other entity is informed about the testing result by the informer so she must fully trust the informer about the result she received. In this paper, we propose a new two-party equality testing protocol. In our protocol, although the final result is still informed by the informer, we allow the entity being informed to verify the correctness of the final result. In this way, the two entities can make sure whether the secret information they preserved are equivalent or not without revealing it. We will also give the security analysis and show that this protocol does not leak any information about the secret value.
Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols.We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.