Cryptology ePrint Archive: Report 2021/473

Cryptonomial: A Framework for Private Time-Series Polynomial Calculations

Ryan Karl and Jonathan Takeshita and Alamin Mohammed and Aaron Striegel and and Taeho Jung

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.

Category / Keywords: cryptographic protocols / Private Multivariate Polynomial Evaluation, Trusted Execution Environment, Secure Aggregation

Original Publication (with minor differences): SecureComm 2021

Date: received 12 Apr 2021, last revised 13 Jun 2021

Contact author: tjung at nd edu, rkarl at nd edu

Available format(s): PDF | BibTeX Citation

Note: Full version of a paper that is accepted at the conference SecureComm 2021.

Version: 20210613:155147 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]