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.
Category / Keywords: OPE and PSI and FHE and active security and SNARKs Date: received 24 Sep 2021 Contact author: paola de perthuis at ens fr, david pointcheval at ens fr, malika izabachene at cosmian com, anca nitulescu at protocol ai Available format(s): PDF | BibTeX Citation Version: 20210924:175746 (All versions of this report) Short URL: ia.cr/2021/1291