*10:17* [Pub][ePrint]
Aggregate Pseudorandom Functions and Connections to Learning, by Aloni Cohen and 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. 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.

*19:17* [Pub][ePrint]
Aggregatable Pseudorandom Functions and Connections to Learning, by Aloni Cohen and 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. 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.

*22:17* [Pub][ePrint]
Constrained Key-Homomorphic PRFs from Standard Lattice Assumptions Or: How to Secretly Embed a Circuit in Your PRF, by Zvika Brakerski and Vinod Vaikuntanathan
Boneh et al. (Crypto 13) and Banerjee and Peikert (Crypto 14) constructed pseudorandom functions (PRFs) from the Learning with Errors (LWE) assumption by embedding combinatorial objects, a path and a tree respectively, in instances of the LWE problem. In this work, we show how to generalize this approach to embed circuits, inspired by recent progress in the study of Attribute Based Encryption.Embedding a universal circuit for some class of functions allows us to produce constrained keys for functions in this class, which gives us the first standard-lattice-assumption-based constrained PRF (CPRF) for general bounded-description bounded-depth functions, for arbitrary polynomial bounds on the description size and the depth. (A constrained key w.r.t a circuit $C$ enables one to evaluate the PRF on all $x$ for which $C(x)=1$, but reveals nothing on the PRF values at other points.) We rely on the LWE assumption and on the one-dimensional SIS (Short Integer Solution) assumption, which are both related to the worst case hardness of general lattice problems. Previous constructions for similar function classes relied on such exotic assumptions as the existence of multilinear maps or secure program obfuscation. The main drawback of our construction is that it does not allow collusion (i.e. to provide more than a single constrained key to an adversary).

Similarly to the aforementioned previous works, our PRF family is also key homomorphic.

Interestingly, our constrained keys are very short. Their length does not depend directly either on the size of the constraint circuit or on the input length.

We are not aware of any prior construction achieving this property, even relying on strong assumptions such as indistinguishability obfuscation.