Paper 2015/038

Aggregate Pseudorandom Functions and Connections to Learning

Aloni Cohen, Shafi Goldwasser, and Vinod Vaikuntanathan


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.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2015
pseudorandom functionslearning theory
Contact author(s)
aloni @ mit edu
2015-01-19: last of 4 revisions
2015-01-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aloni Cohen and Shafi Goldwasser and Vinod Vaikuntanathan},
      title = {Aggregate Pseudorandom Functions and Connections to Learning},
      howpublished = {Cryptology ePrint Archive, Paper 2015/038},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.