MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

Malika Izabachène; Anca Nitulescu; Paola de Perthuis; David Pointcheval

Paper 2021/1291

MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

Malika Izabachène, Anca Nitulescu, Paola de Perthuis, and David Pointcheval

Abstract

Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a sender with a private polynomial and a receiver with a private evaluation point where the receiver learns the evaluation of the polynomial in their point and no additional information. They are used in Private Set Intersection (PSI) protocols. We introduce MyOPE, a "short-sighted'' polynomial evaluation scheme in the presence of malicious senders. In addition to strong privacy guarantees, MyOPE enforces honest sender behavior and consistency by adding verifiability to the calculations. The main tools are Verifiable Computation (VC) of inner products between committed vectors for honest behavior enforcement and Fully Homomorphic Encryption (FHE) for input privacy. While classical techniques in pairing-based settings allow generic succinct proofs for such evaluations, they require large prime order subgroups which highly impact the computation complexity, and prevent the use of FHE with practical parameters. MyOPE builds on generic secure encoding techniques for succinct commitments, that allow real-world FHE parameters and Residue Number System (RNS) optimizations, suitable for very high-degree polynomials.

Metadata

Available format(s): PDF
Publication info: Preprint. Minor revision.
Contact author(s): paola de perthuis @ ens fr
david pointcheval @ ens fr
malika izabachene @ cosmian com
anca nitulescu @ protocol ai
History: 2022-02-15: last of 2 revisions; 2021-09-24: received; See all versions
Short URL: https://ia.cr/2021/1291
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1291,
      author = {Malika Izabachène and Anca Nitulescu and Paola de Perthuis and David Pointcheval},
      title = {MyOPE: Malicious securitY for Oblivious Polynomial Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1291},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1291}},
      url = {https://eprint.iacr.org/2021/1291}
}