Paper 2024/470

Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations

Pascal Giorgi, University of Montpellier
Fabien Laguillaumie, University of Montpellier
Lucas Ottow, University of Montpellier
Damien Vergnaud, Sorbonne University

Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or shared using a threshold linear secret-sharing scheme. Our protocols terminate after a constant number of rounds and minimize the number of secure multiplications. In their seminal article at PKC 2006, Mohassel and Franklin proposed constant-rounds protocols for the main operations on (shared) polynomials. In this work, we improve the fan-in multiplication of nonzero polynomials, the multi-point polynomial evaluation and the polynomial interpolation (on secret points) to reach a quasi-linear complexity (instead of quadratic in Mohassel and Franklin's work) in the degree of shared input/output polynomials. Computing with shared polynomials is a core component of designing multi-party protocols for privacy-preserving operations on private sets, like private disjointness test or private set intersection. Using our new protocols, we are able to improve the complexity of such protocols and to design the first variant which always returns a correct result.

Available format(s)
Cryptographic protocols
Publication info
multi-party computationpolynomial operationsprivacy-preserving set operations
Contact author(s)
giorgi @ lirmm fr
Fabien Laguillaumie @ lirmm fr
lucas ottow @ lirmm fr
damien vergnaud @ lip6 fr
2024-05-29: last of 2 revisions
2024-03-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pascal Giorgi and Fabien Laguillaumie and Lucas Ottow and Damien Vergnaud},
      title = {Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations},
      howpublished = {Cryptology ePrint Archive, Paper 2024/470},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.