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

With additively homomorphic encryption (AHE), one can compute, from input ciphertexts Enc(x₁), ..., Enc(xₙ), and additional inputs y₁, ..., yₖ, a ciphertext c_f = Enc(f(x₁, ..., xₙ, y₁, ..., yₖ)) for any polynomial f in which each monomial has total degree at most 1 in the x-variables (but with arbitrary degree in the known y-variables). For AHE that satisfies a set of natural requirements, we give a zero-knowledge proof system for showing that a ciphertext c_f is the result of homomorphically evaluating f on ciphertexts (c1, . . . , cn) = (Enc(x1), . . . , Enc(xn)) and private inputs y₁, ..., yₖ that correspond to commitments C₁, ..., Cₖ where the encrypted values, x₁, ..., xₙ are unknown to the prover. Our proofs are succinct, i.e., their size is independent of the number of ciphertexts n, and is instead O(k log d) where k is the number of private inputs, and d is the maximum degree of any variable in f.

We give two ways of instantiating this framework: with ElGamalbased 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 f.

Next, we show that our framework yields a dramatically improved privacy-preserving blueprint (PPB) system. Introduced by Kohlweiss, Lysyanskaya, and Nguyen (Eurocrypt'23), an f-PPB system allows an auditor with secret input x to create a public encoding pk of the function f(x,·) that reveals nothing about x. Yet, it allows a user to compute an encoding, or escrow Z, of the value f(x, y) on input the user's private data y corresponding to a commitment C_y; Z will verifiably correspond to the commitment C_y. The auditor will be able to recover f(x,y) from Z, but will learn no other information about y. For example, if f is the watchlist function where f(x, y) outputs y only in the event that y is on the list x, then an f-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 f; for example, we show how to realize f 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 Z from linear in the size of the auditor's input x, to logarithmic. Additionally, we define and satisfy a stronger notion of security for f-PPBs, where a malicious auditor cannot frame a user in a transaction in which the user was not involved in.