Non-interactive Secure Multiparty Computation for Symmetric Functions, Revisited: More Efficient Constructions and Extensions

Reo Eriguchi, Kazuma Ohara, Shota Yamada, Koji Nuida

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Non-interactive secure multiparty computation (NIMPC) is a variant of secure computation which allows each of n players to send only a single message depending on his input and correlated randomness. Abelian programs, which can realize any symmetric function, are defined as functions on the sum of the players’ inputs over an abelian group and provide useful functionalities for real-world applications. We improve and extend the previous results in the following ways: We present NIMPC protocols for abelian programs that improve the best known communication complexity. If inputs take any value of an abelian group G, our protocol achieves the communication complexity O(| G| (log | G| ) 2) improving O(| G| 2n2) of Beimel et al. (Crypto 2014). If players are limited to inputs from subsets of size at most d, our protocol achieves | G| (log | G| ) 2(max { n, d} ) (1+o(1))t where t is a corruption threshold. This result improves | G| 3(nd) (1+o(1))t of Beimel et al. (Crypto 2014), and even | G| logn+O(1)n of Benhamouda et al. (Crypto 2017) if t= o(log n) and | G| = nΘ(1).We propose for the first time NIMPC protocols for linear classifiers that are more efficient than those obtained from the generic construction.We revisit a known transformation of Benhamouda et al. (Crypto 2017) from Private Simultaneous Messages (PSM) to NIMPC, which we repeatedly use in the above results. We reveal that a sub-protocol used in the transformation does not satisfy the specified security. We also fix their protocol with only constant overhead in the communication complexity. As a byproduct, we obtain an NIMPC protocol for indicator functions with asymptotically optimal communication complexity with respect to the input length.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
EditorsTal Malkin, Chris Peikert
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages30
ISBN (Print)9783030842444
Publication statusPublished - 2021
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: Aug 16 2021Aug 20 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12826 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Non-interactive Secure Multiparty Computation for Symmetric Functions, Revisited: More Efficient Constructions and Extensions'. Together they form a unique fingerprint.

Cite this