Paper 2021/473 Original: eprint.iacr.org/2021/473 ↗

Cryptonomial: A Framework for Private Time-Series Polynomial Calculations

Abstract

In modern times, data collected from multi-user distributed applications must be analyzed on a massive scale to support critical business objectives. While analytics often requires the use of personal data, it may compromise user privacy expectations if this analysis is conducted over plaintext data. Private Stream Aggregation (PSA) allows for the aggregation of time-series data, while still providing strong privacy guarantees, and is significantly more efficient over a network than related techniques (e.g. homomorphic encryption, secure multiparty computation, etc.) due to its asynchronous and efficient protocols. However, PSA protocols face limitations and can only compute basic functions, such as sum, average, etc.. We present Cryptonomial, a framework for converting any PSA scheme amenable to a complex canonical embedding into a secure computation protocol that can compute any function over time-series data that can be written as a multivariate polynomial, by combining PSA and a Trusted Execution Environment. This design allows us to compute the parallelizable sections of our protocol outside the TEE using advanced hardware, that can take better advantage of parallelism. We show that Cryptonomial inherits the security requirements of PSA, and supports fully malicious security. We simulate our scheme, and show that our techniques enable performance that is orders of magnitude faster than similar work supporting polynomial calculations.