Revision #1 Authors: Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

Accepted on: 19th January 2015 10:15

Downloads: 1184

Keywords:

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.

TR15-009 Authors: Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

Publication: 16th January 2015 20:56

Downloads: 1295

Keywords:

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. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all function values on points for which a polynomial time predicate holds. We show how to use algebraic properties of underlying classical pseudo random functions, to construct aggregatable pseudo random functions for a number of classes of aggregation queries under cryptographic hardness assumptions. On the flip side, we show that certain aggregate queries are impossible to support.

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 and 1990s. 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.