Succinctly Verifiable Computation over Additively-Homomorphically Encrypted Data with Applications to Privacy-Preserving Blueprints
Scott Griffy, Brown University
Markulf Kohlweiss, University of Edinburgh and IOG
Anna Lysyanskaya, Brown University
Meghna Sengupta, University of Edinburgh
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 can be arbitrary in the -variables). For AHE that satisfies a set of natural requirements, we give a non-interactive zero-knowledge proof system (in the random-oracle model) for showing that a ciphertext is the result of homomorphically evaluating on ciphertexts and private inputs that correspond to commitments . Our proofs are , 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 assumption). 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 e-cash 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.
@misc{cryptoeprint:2024/675,
author = {Scott Griffy and Markulf Kohlweiss and Anna Lysyanskaya and Meghna Sengupta},
title = {Succinctly Verifiable Computation over Additively-Homomorphically Encrypted Data with Applications to Privacy-Preserving Blueprints},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/675},
year = {2024},
url = {https://eprint.iacr.org/2024/675}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.