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)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]