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

Journal of Discrete Mathematical Sciences and Cryptography

Efficient secure multiparty computation of sparse vector dot products

Michael J. Collins

Published Jul 4, 2018• 1 citation
Publisher

Abstract

We give a protocol for secure multi-party computation of the scalar product of two sparse vectors of length n with O(log(log n)) rounds and polylogarithmic communication.
DOI
10.1080/09720529.2018.1453623

Related papers

Secure Dot-product Protocol Using Trace Functions

Behzad Malek, Ali Miri

In a secure dot-product protocol, two parties jointly compute the dot-product of two vectors of their inputs. In our protocol, the result of a secure dot-product is known only to one party while each input in known only to its owner. This protocol is the first non-interactive secure dot-product protocol that only requires one round of interaction with O(n) communication overhead, where n is the size of the input vectors. The computation overhead of this scheme is negligible as it requires few integer multiplications and additions. In our construction, the sender and the receiver are information theoretically secure over sets E and S* respectively, where E and S* are subsets of the vector space. In our protocol, the security of the sender and the receiver can be increased by choosing large fields

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•8 citations

Scalar-product based secure two-party computation

Chih-Hao Shen, Justin Z. Zhan, Tsan‐sheng Hsu +2 more

Secure multiparty computation is a very important research topic in cryptography. The sub-problem of secure multiparty computation that has received special attention by researchers because of its close relation to many cryptographic tasks is secure two-party computation. This area of research is concerned with the question: ldquoCan two party computation be achieved more efficiently and under weaker security assumptions than general multiparty computation?rdquo Yaopsilas protocol provided security against passive adversaries, while Lindell and Pinkas proposed secure two party protocols that are secure against active adversaries. In this paper, we would like to propose a set of information theoretically secure protocols based on scalar product protocol. The detailed complexity analysis is also provided.

IEEE International Conference on Granular Computing (GrC)•Aug 1, 2008•10 citations

Secure multi-party computation made simple

MaurerUeli

Known secure multi-party computation protocols are quite complex, involving non-trivial mathematical structures and sub-protocols. The purpose of this paper is to present a very simple approach to ...

Discrete Applied Mathematics•Feb 1, 2006•5 citations

Secure Merge with O(n log log n) Secure Operations

Brett Hemenway, Rafail Ostrovsky

Data-oblivious algorithms are a key component of many secure computation protocols. In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools. The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require O(n log n), operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only O(n) communication. Leveraging the efficiency of secure multiparty shuffling, we give novel, information-theoretic algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists. Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of n elements require O(n log n) comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length n with t ≪ n nonzero elements with communication O(t log² n + n), which beats the best oblivious algorithms when the number of nonzero elements, t, satisfies t < n/log² n. Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in O(n)-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give an information-theoretic stable compaction algorithm with only O(n) communication. Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required O(n log n) secure operations. Using black-box access to an O(n)-communication secure shuffle, we give the first multi-party secure merge algorithm that requires only O(n log log n) communication. Our algorithm takes as input n secret-shared values, and outputs a secret-sharing of the sorted list. All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle. Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency. These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols.

Leibniz international proceedings in informatics•Jan 1, 2021•5 citations

Unconditionally Secure Multiparty Computation for Symmetric Functions with Low Bottleneck Complexity

Reo Eriguchi

Lecture notes in computer science•Jan 1, 2023•3 citations

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

Yehuda Lindell, Benny Pinkas B

Lecture notes in computer science•Jan 1, 2007•431 citations
In a secure dot-product protocol, two parties jointly compute the dot-product of two vectors of their inputs. In our protocol, the result of a secure dot-product is known only to one party while each input in known only to its owner. This protocol is the first non-interactive secure dot-product protocol that only requires one round of interaction with O(n) communication overhead, where n is the size of the input vectors. The computation overhead of this scheme is negligible as it requires few integer multiplications and additions. In our construction, the sender and the receiver are information theoretically secure over sets E and S* respectively, where E and S* are subsets of the vector space. In our protocol, the security of the sender and the receiver can be increased by choosing large fields
Secure multiparty computation is a very important research topic in cryptography. The sub-problem of secure multiparty computation that has received special attention by researchers because of its close relation to many cryptographic tasks is secure two-party computation. This area of research is concerned with the question: ldquoCan two party computation be achieved more efficiently and under weaker security assumptions than general multiparty computation?rdquo Yaopsilas protocol provided security against passive adversaries, while Lindell and Pinkas proposed secure two party protocols that are secure against active adversaries. In this paper, we would like to propose a set of information theoretically secure protocols based on scalar product protocol. The detailed complexity analysis is also provided.
Data-oblivious algorithms are a key component of many secure computation protocols. In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools. The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require O(n log n), operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only O(n) communication. Leveraging the efficiency of secure multiparty shuffling, we give novel, information-theoretic algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists. Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of n elements require O(n log n) comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length n with t ≪ n nonzero elements with communication O(t log² n + n), which beats the best oblivious algorithms when the number of nonzero elements, t, satisfies t < n/log² n. Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in O(n)-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give an information-theoretic stable compaction algorithm with only O(n) communication. Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required O(n log n) secure operations. Using black-box access to an O(n)-communication secure shuffle, we give the first multi-party secure merge algorithm that requires only O(n log log n) communication. Our algorithm takes as input n secret-shared values, and outputs a secret-sharing of the sorted list. All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle. Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency. These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols.