MyOPE - Malicious securitY for Oblivious Polynomial Evaluation

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 communication 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.