Paper 2015/038

Aggregate Pseudorandom Functions and Connections to Learning

Aloni Cohen, 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.