Paper 2024/675

Succinctly Verifiable Computation over Additively-Homomorphically Encrypted Data: Making Privacy-Preserving Blueprints Practical

Abstract

With additively homomorphic encryption (AHE), one can compute, from input ciphertexts $$, and additional inputs $$, a ciphertext $$ for any polynomial $$ in which each monomial has total degree at most $$ in the $$-variables (but with arbitrary degree in the known $$-variables). For AHE that satisfies a set of natural requirements, we give a zero-knowledge proof system for showing that a ciphertext $$ is the result of homomorphically evaluating $$ on ciphertexts $$ = $$ and private inputs $$ that correspond to commitments $$ where the encrypted values, $$ are unknown to the prover. Our proofs are succinct, i.e., their size is independent of the number of ciphertexts $$, and is instead $$ where $$ is the number of private inputs, and $$ is the maximum degree of any variable in $$. We give two ways of instantiating this framework: with ElGamal-based encryption (under the DDH assumption) and with a variant of the Camenisch-Shoup cryptosystem (under the DCR and Strong RSA assumptions). Both yield proof systems where computing and verifying the proof takes a comparable amount of time to homomorphically evaluating $$. Next, we show that our framework yields a dramatically improved privacy-preserving blueprint (PPB) system. Introduced by Kohlweiss, Lysyanskaya, and Nguyen (Eurocrypt'23), an $$-PPB system allows an auditor with secret input $$ to create a public encoding $$ of the function $$ that reveals nothing about $$. Yet, it allows a user to compute an encoding, or escrow $$, of the value $$ on input the user's private data $$ corresponding to a commitment $$; $$ will verifiably correspond to the commitment $$. The auditor will be able to recover $$ from $$, but will learn no other information about $$. For example, if $$ is the watchlist function where $$ outputs $$ only in the event that $$ is on the list $$, then an $$-PPB allows the auditor to trace watchlisted users in an otherwise anonymous system. Using our succinct zero-knowledge proof system for additively homomorphic computation we achieve the following results: (1) We provide efficient schemes for a bigger class of functions $$; for example, we show how to realize $$ that would allow the auditor to trace private payment transactions of a criminal suspect which was previously not efficient. (2) For the watchlist and related functions, we reduce the size of the escrow $$ from linear in the size of the auditor's input $$, to logarithmic. Additionally, we define and satisfy a stronger notion of security for $$-PPBs, where a malicious auditor cannot frame a user in a transaction in which the user was not involved in.