Paper 2024/675

Privacy-Preserving Blueprints via Succinctly Verifiable Computation over Additively-Homomorphically Encrypted Data

Abstract

Introduced by Kohlweiss, Lysyanskaya, and Nguyen (Eurocrypt'23), an $f$-privacy-preserving blueprint (PPB) system allows an auditor with secret input $x$ to create a public encoding of the function $f(x,\cdot)$ that verifiably corresponds to a commitment $C_x$ to $x$. The auditor will then be able to derive $f(x,y)$ from an escrow $Z$ computed by a user on input the user's private data $y$ corresponding to a commitment $C_y$. $Z$ verifiably corresponds to the commitment $C_y$ and reveals no other information about $y$. PPBs provide an abuse-resistant escrow mechanism: 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. Yet, the auditor's $x$ must correspond to a publicly available $C_x$ (authorized by a transparent, lawful process), and the auditor will learn nothing except $f(x,y)$. In this paper, we build on the original PPB results in three ways: (1) We define and satisfy a stronger notion of security where a malicious auditor cannot frame a user in a transaction to which this user was not a party. (2) We provide efficient schemes for a bigger class of functions $f$; for example, for the first time, we show how to realize $f$ that would allow the auditor to trace e-cash transactions of a criminal suspect. (3) 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. Of independent interest, we develop a new framework for succinctly verifiable computation over additively-homomorphically encrypted data.