Cryptology ePrint Archive: Report 2015/038

Aggregate Pseudorandom Functions and Connections to Learning

Aloni Cohen and Shafi Goldwasser and Vinod Vaikuntanathan

Abstract: In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. We show how to use algebraic properties of underlying classical pseudo random functions, to construct such ``aggregate pseudo-random functions'' for a number of classes of aggregation queries under cryptographic hardness assumptions. For example, one aggregate query we achieve is the product of all function values accepted by a polynomial-sized read-once boolean formula. On the flip side, we show that certain aggregate queries are impossible to support. Aggregate pseudo-random functions fall within the framework of the work of Goldreich, Goldwasser, and Nussboim on the ``Implementation of Huge Random Objects,'' providing truthful implementations of pseudo-random functions for which aggregate queries can be answered.

In the second part of this work, we show how various extensions of pseudo-random functions considered recently in the cryptographic literature, yield impossibility results for various extensions of machine learning models, continuing a line of investigation originated by Valiant and Kearns in the 1980s. The extended pseudo-random functions we address include constrained pseudo random functions, aggregatable pseudo random functions, and pseudo random functions secure under related-key attacks.

Category / Keywords: foundations / pseudorandom functions, learning theory

Original Publication (with minor differences): IACR-TCC-2015

Date: received 15 Jan 2015, last revised 19 Jan 2015

Contact author: aloni at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20150119:092249 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]