MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

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

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2021/1291

MyOPE: Malicious securitY for Oblivious Polynomial Evaluation

Malika Izabachène

, Cosmian

Anca Nitulescu

, Protocol Labs

Paola de Perthuis

, Cosmian, DIENS, École Normale Supérieure, CNRS, Inria, PSL University

David Pointcheval

, DIENS, École Normale Supérieure, CNRS, Inria, PSL University

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. In this work, we introduce MyOPE, a ``short-sighted'' non-interactive polynomial evaluation scheme with a poly-logarithmic communication complexity 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 building block for this new verifiable OPE is an inner product argument (IPA) over rings that guarantees an inner product relation holds between committed vectors. Our IPA works for vectors with elements from generic rings of polynomials and has constant-size proofs that consist in one commitment only while the verification, once the validity of the vector-commitments has been checked, consists is one quadratic equation only. We further demonstrate the applications of our IPA for verifiable OPE using Fully Homomorphic Encryption (FHE) over rings of polynomials: we prove the correctness of an inner product between the vector of powers of the evaluation point and the vector of polynomial coefficients, along with other inner-products necessary in this application's proof. MyOPE builds on generic secure encoding techniques for succinct commitments, that allow real-world FHE parameters and Residue Number System (RNS) optimizations, suitable for high-degree polynomials.

Note: full version of the conference paper

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. SCN 2022
Keywords: SNARK Verifiable Computations FHE PSI OPE Malicious Security Inner-Product Argument
Contact author(s): malika izabachene @ cosmian com
anca @ protocol ai
paola de perthuis @ ens fr
david pointcheval @ ens fr
History: 2022-07-06: last of 4 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}
}