International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Actively Secure Polynomial Evaluation from Shared Polynomial Encodings

Authors:
Pascal Reisert , University of Stuttgart, Germany
Marc Rivinius , University of Stuttgart, Germany
Toomas Krips , University of Tartu, Estonia
Sebastian Hasler , University of Stuttgart, Germany
Ralf Küsters , University of Stuttgart, Germany
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2024
Abstract: Many of the currently best actively secure Multi-Party Computation (MPC) protocols like SPDZ (Damgård et al., CRYPTO 2012) and improvements thereof use correlated randomness to speed up the time-critical online phase. Although many of these protocols still rely on classical Beaver triples, recent results show that more complex correlations like matrix or convolution triples lead to more efficient evaluations of the corresponding operations, i.e. matrix multiplications or tensor convolutions. In this paper, we address the evaluation of multivariate polynomials with a new form of randomness: polytuples. We use the polytuples to construct a new family of randomized encodings which then allow us to evaluate the given multivariate polynomial. Our approach can be fine-tuned in various ways to the constraints of applications at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups, a polytuples-based online phase outperforms state-of-the-art protocols based on Beaver triples.
BibTeX
@inproceedings{asiacrypt-2024-34588,
  title={Actively Secure Polynomial Evaluation from Shared Polynomial Encodings},
  publisher={Springer-Verlag},
  author={Pascal Reisert and Marc Rivinius and Toomas Krips and Sebastian Hasler and Ralf Küsters},
  year=2024
}