Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2024

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

Pascal Giorgi
Fabien Laguillaumie
Lucas Ottow
Damien Vergnaud

Abstract

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.
Fichier principal
Vignette du fichier
2024-470.pdf (552.91 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Licence

Dates and versions

lirmm-04593144 , version 1 (29-05-2024)

Licence

Identifiers

  • HAL Id : lirmm-04593144 , version 1

Cite

Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, Damien Vergnaud. Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations. ITC 2024 - 5th Information-Theoretic Cryptography Conference, Aug 2024, Stanford, CA, United States. ⟨lirmm-04593144⟩
99 View
74 Download

Share

More