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

Multi-party Distributed Point Functions, Revisited

Elaine Shi, 顾天瑶, Xuanye Zheng, Yue Yang, Yiping Liu, Youfa Fu

Published Nov 5, 2026• 0 citations
Publisher
DOI
10.1007/978-3-032-43588-0_5

Related papers

Network-Agnostic Multi-party Computation Revisited (Extended Abstract)

Nidhish Bhimrajka, Ashish Choudhury, Supreeth Varadarajan

Lecture notes in computer science•Jan 1, 2024•6 citations

SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra

Erki Külaots, Toomas Krips, Hendrik Eerikson +2 more

Multi-point function secret sharing (FSS) is a building block for pseudo-random correlation generators used in novel silent correlation generation methods for various secure multi-party computation applications. However, the main construction used so far is the naive approach to combining several point functions. In this paper, we propose an efficient and natural generalisation of the point function FSS scheme of Boyle et al. 2016 using a tree structure, a pseudorandom generator and systems of linear equations. We propose a new notion of distributed random multi-point function. Our construction splits the distributed multi-point function scheme into a random multi-point function scheme and an algorithm to transform a random output into the desired output value. The resulting scheme, which we call SLAMP-FSS, improves upon the state of the art in terms of calls to a pseudorandom generator (PRG).

IACR Communications in Cryptology•May 4, 2026•0 citations

Non-Interactive Distributed Point Functions

Elette Boyle, Lalita Devadas, Sacha Servan-Schreiber

Lecture notes in computer science•Jan 1, 2025•6 citations

The Exact Round Complexity of Secure Computation.

Sanjam Garg, Pratyay Mukherjee, Omkant Pandey +1 more

We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky CRYPTO '04 proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood. These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored. In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let $$k'=\max 4,k+1$$k'=max4,k+1; then,Two-party setting with simultaneous message transmission: there exists a $$k'$$k'-round protocol for securely realizing every two-party functionality;Multi-party setting: there exists a $$k'$$k'-round protocol for securely realizing the multi-party coin-flipping functionality. As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols from the literature, we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionalityfive rounds are sufficient. We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.

•Jan 1, 2016•0 citations

Programmable Distributed Point Functions

Elette Boyle, Niv Gilboa, Yuval Ishai +1 more

Lecture notes in computer science•Jan 1, 2022•20 citations

Exploring the Limits of Multi-Party Computation

Dominik Raub

•Jan 1, 2009•1 citation
Multi-point function secret sharing (FSS) is a building block for pseudo-random correlation generators used in novel silent correlation generation methods for various secure multi-party computation applications. However, the main construction used so far is the naive approach to combining several point functions. In this paper, we propose an efficient and natural generalisation of the point function FSS scheme of Boyle et al. 2016 using a tree structure, a pseudorandom generator and systems of linear equations. We propose a new notion of distributed random multi-point function. Our construction splits the distributed multi-point function scheme into a random multi-point function scheme and an algorithm to transform a random output into the desired output value. The resulting scheme, which we call SLAMP-FSS, improves upon the state of the art in terms of calls to a pseudorandom generator (PRG).
We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In particular, Katz and Ostrovsky CRYPTO '04 proved that 5 rounds are necessary and sufficient for securely realizing every two-party functionality where both parties receive the output. However, the exact round complexity of general multi-party computation, as well as two-party computation with a simultaneous message exchange channel, is not very well understood. These questions are intimately connected to the round complexity of non-malleable commitments. Indeed, the exact relationship between the round complexities of non-malleable commitments and secure multi-party computation has also not been explored. In this work, we revisit these questions and obtain several new results. First, we establish the following main results. Suppose that there exists a k-round non-malleable commitment scheme, and let k′=max⁡4,k+1k'=\max 4,k+1k′=max4,k+1k'=max4,k+1; then,Two-party setting with simultaneous message transmission: there exists a k′k'k′k'-round protocol for securely realizing every two-party functionality;Multi-party setting: there exists a k′k'k′k'-round protocol for securely realizing the multi-party coin-flipping functionality. As a corollary of the above results, by instantiating them with existing non-malleable commitment protocols from the literature, we establish that four rounds are both necessary and sufficient for both the results above. Furthermore, we establish that, for every multi-party functionalityfive rounds are sufficient. We actually obtain a variety of results offering trade-offs between rounds and the cryptographic assumptions used, depending upon the particular instantiations of underlying protocols.