Paper 2021/1291

MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

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


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.

Available format(s)
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
2022-02-15: last of 2 revisions
2021-09-24: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.