Welcome to the resource topic for 2015/038
Title:
Aggregate Pseudorandom Functions and Connections to Learning
Authors: Aloni Cohen, Shafi Goldwasser, 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.
ePrint: https://eprint.iacr.org/2015/038
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .