We show how to construct an order-revealing encryption scheme which is not only more secure than all other existing order-preserving encryption schemes, but also very practical. In particular, our construction relies only on one-way function evaluations and maintains a fairly small ciphertext size.
We introduce the notion of key privacy for a constrained PRF, which captures the intuition that an adversary, given two constrained keys, cannot distinguish their constraints. This primitive is applicable in numerous symmetric-key settings including deniable encryption and private keyword search, and we also show how to construct constrained PRFs from multilinear maps.
We show how to construct the first implementable functional encryption scheme on multiple inputs using multilinear maps. Our construction only requires a low degree of multilinearity by avoiding indistinguishability obfuscation and interpreting functions as short branching programs. Our main application is an order-revealing encryption scheme that can compare 16-bit values using only a 9-way multilinear map.
We show how to construct PRFs that are secure against a large class of related-key attacks. We use the Bellare-Cash framework and rely on the Learning with Errors and Decision Linear assumptions in multilinear maps.
Joint work with Hart Montgomery, and Ananth Raghunathan.
Key homomorphic PRFs are natural objects to study and have a number of interesting applications, including simplifying the process of rotating encryption keys for encrypted data stored in the cloud. We construct the first provably secure key homomorphic PRFs in the standard model (without random oracles).
We consider a model of user engagement in social networks, where each player incurs a cost to remain engaged but derives a benefit proportional to the number of engaged neighbors. We classify the computational complexity of this problem, showing efficient algorithms for small parameters and strong impossibility results for larger parameters.
We analyze the online version of the min-cost metric matching problem on k servers and k requests, and show how a simple randomized algorithm obtains an O(log k)-competitive solution on the line metric, which beats the previous upper bound of O(log^2 k). This result can also be extended to metrics with constant doubling dimension.
Joint work with Anupam Gupta.
We study iterated transductions defined by a class of invertible transducers over the binary alphabet. The transduction semigroups of these automata turn out to be free Abelian groups and the orbits of finite words can be described as affine subspaces in a suitable geometry defined by the generators of these groups. We show that iterated transductions are rational for a subclass of our automata.
Joint work with Klaus Sutner.