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} }