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

Lecture notes in computer science

Scalable Multiparty Computation from Non-linear Secret Sharing

Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Mingyuan Wang

Published Jan 1, 2024• 3 citations
Publisher
DOI
10.1007/978-3-031-68397-8_12

Related papers

Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation

Arpita Patra, Ashish Choudhury, Chandrasekharan Pandu Rangan

Journal of Cryptology•Dec 10, 2013•43 citations

Secret Sharing Based Multiparty Quantum Computation for Multiplication

Kartick Sutradhar, Hari Om

International Journal of Theoretical Physics•Jul 31, 2021•20 citations

Scalable Secure Multiparty Computation

Ivan Damgård, Yuval Ishai

Lecture notes in computer science•Jan 1, 2006•143 citations

SLIDE: Shuffle Shamir secret shares uniformly with linear online communication and guaranteed output delivery

Jiacheng Gao, Moyang Xie, Yuan Zhang +1 more

We revisit shuffle protocols for Shamir secret sharing. Existing constructions either produce non-uniform shuffles or incur high communication and round complexity, sometimes exponential in the number of parties. We propose two new shuffle protocols that achieve uniform shuffling with communication complexity O ( k + l log k n 2 m log m ) for an m × l matrix shared among n parties, where k ≤ m is a tunable parameter. The first protocol is concretely efficient, while the second achieves the best-known O ( n m l ) online communication and O ( n ) rounds. Experiments show significant improvements in online efficiency and total cost over prior work. Our key technical ingredient is a novel permutation sharing technique that represents permutations via smaller permutation matrices, making their application significantly more efficient. The first protocol applies independent secret permutations sequentially, while the second builds on shuffle correlation to achieve optimal online complexity. We further extend shuffle correlation to support guaranteed output delivery with linear online communication, yielding SLIDE (shuffle Shamir secret shares uniformly with linear online communication and guaranteed output delivery), the first protocol achieving both O ( n m l ) online communication and guaranteed output delivery. Our constructions rely only on basic Shamir secret sharing over any field F with | F | > n . As shuffling is a fundamental primitive for multiparty computation tasks such as sorting and oblivious data structures, our results enable more efficient and scalable secure computation in practice.

arXiv:2608.27129•Journal of Computer Security•Sep 23, 2026•0 citations

A non-interactive multiparty computation protocol

Hossein Ghodosi, Rahim Zaare-Nahandi

Multiparty computation considers the design of protocols such that a set of n users U] ... lim each with their own secret input Xi, can compute a function Y =F(x], ... , x/J. In this paper, we study a requirement for devising non-interactive multiparty computation protocols and present the first non-interactive multiparty computation protocol, which has the following advantages: a) The amount of computation required by each participant is equal to the amount of computation in an ideal model (i.e. the proposed scheme is optimal). b) In the presence of passive adversaries, no set of less than n users can leam more than what is allowed in the underlying secret sharing scheme (other than the function value), c) In the presence of active adversaries (i.e, Byzantine faults are allowed), no set of less than nl2 users can either leam more than what is allowed in the underlying secret sharing scheme, nor can they dismpt the computation. d) The partial security provided in our scheme is unconditional. That is, the proposed scheme does not rely on any non-proven cryptographic assumption.

•Jan 1, 2007•0 citations

Scalable and Unconditionally Secure Multiparty Computation

Ivan Damgård, Jesper Buus Nielsen

Springer eBooks•Aug 9, 2007•287 citations
We revisit shuffle protocols for Shamir secret sharing. Existing constructions either produce non-uniform shuffles or incur high communication and round complexity, sometimes exponential in the number of parties. We propose two new shuffle protocols that achieve uniform shuffling with communication complexity O ( k + l log k n 2 m log m ) for an m × l matrix shared among n parties, where k ≤ m is a tunable parameter. The first protocol is concretely efficient, while the second achieves the best-known O ( n m l ) online communication and O ( n ) rounds. Experiments show significant improvements in online efficiency and total cost over prior work. Our key technical ingredient is a novel permutation sharing technique that represents permutations via smaller permutation matrices, making their application significantly more efficient. The first protocol applies independent secret permutations sequentially, while the second builds on shuffle correlation to achieve optimal online complexity. We further extend shuffle correlation to support guaranteed output delivery with linear online communication, yielding SLIDE (shuffle Shamir secret shares uniformly with linear online communication and guaranteed output delivery), the first protocol achieving both O ( n m l ) online communication and guaranteed output delivery. Our constructions rely only on basic Shamir secret sharing over any field F with | F | > n . As shuffling is a fundamental primitive for multiparty computation tasks such as sorting and oblivious data structures, our results enable more efficient and scalable secure computation in practice.
Multiparty computation considers the design of protocols such that a set of n users U] ... lim each with their own secret input Xi, can compute a function Y =F(x], ... , x/J. In this paper, we study a requirement for devising non-interactive multiparty computation protocols and present the first non-interactive multiparty computation protocol, which has the following advantages: a) The amount of computation required by each participant is equal to the amount of computation in an ideal model (i.e. the proposed scheme is optimal). b) In the presence of passive adversaries, no set of less than n users can leam more than what is allowed in the underlying secret sharing scheme (other than the function value), c) In the presence of active adversaries (i.e, Byzantine faults are allowed), no set of less than nl2 users can either leam more than what is allowed in the underlying secret sharing scheme, nor can they dismpt the computation. d) The partial security provided in our scheme is unconditional. That is, the proposed scheme does not rely on any non-proven cryptographic assumption.