Paper 2021/1291

MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

Malika Izabachène and Anca Nitulescu and 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 a scheme for OPE in the presence of malicious senders, enforcing honest sender behavior and consistency by adding verifiability to the calculations. The main tools used are FHE for input privacy and arguments of knowledge for the verifiability property. MyOPE deploys sublinear communication costs in the sender's polynomial degree and one to five rounds of interaction. In other words, it can be used as a verifiable computation scheme for polynomial evaluation over FHE ciphertexts. 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 encodings techniques that allow composite integers and enable real-world FHE parameters and even RNS-based optimizations. It is best adapted for the unbalanced setting where the degree of the polynomial and the computing power of the sender are large. MyOPE can be used as a building block in specialized two-party protocols such as PSI (this use-case is hereafter described), oblivious keyword search, set membership and more using the OPE instantiation. As another contribution, our techniques are generalized to applications other than OPE, such as Symmetric Private Information Retrieval (SPIR), to make them secure against a malicious sender.