Non-Interactive Verifiable Aggregation (NIVA)

Abstract: Consider a weak analyst that wishes to outsource data collection and computation of aggregate statistics over a potentially large population of (also weak) clients to a powerful server. For flexibility and efficiency, we consider public-key and non-interactive protocols, meaning the clients know the analyst’s public key but do not share secrets, and each client sends at most one message. Furthermore, the final step should be silent, whereby the analyst simply downloads the (encrypted) result from the server when needed. To capture this setting, we define a new primitive we call Non-Interactive Verifiable Aggregation (NIVA). We require both privacy and robustness for a NIVA protocol to be deemed secure. Namely, our security notion for NIVA ensures that the clients’ data remains private to both the server and the analyst, while also ensuring that malicious clients cannot skew the results by providing faulty data.

We propose a secure NIVA protocol, which we call PEAR (for Private, Efficient, Accurate, Robust), which can validate inputs according to any NP validity rule. PEAR is based on a novel combination of functional encryption for inner-products (Abdalla et al., PKC 2015) and fully-linear probabilistically-checkable proofs (Boneh et al., Crypto 2019). We emphasize that PEAR is non-interactive, public-key, and makes black-box use of the underlying cryptographic primitives. Additionally, we implement PEAR and conduct a thorough performance evaluation showing improvement over prior work for practically-relevant validity rules.

Bio: Arkady Yerukhimovich is an associate professor of Computer Science at George Washington University. His research interests span theoretical and applied cryptography with a focus on building provably-secure protocols to enable people to communicate, search, and compute over their personal data while preserving their privacy. In particular, his recent research focuses on “large-scale” secure computation looking to perform secure computation with a large number of parties or on very large inputs. Prior to joining George Washington University, professor Yerukhimovich received his PhD from the University of Maryland where his research focused on black-box separations.