Kevin Lewi

Stanford Cryptography Ph.D. Student

klewi at cs.stanford.edu

Practical Order-Revealing Encryption with Limited Leakage

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.

Joint work with Nathan Chenette, Stephen A. Weis, and David J. Wu.

Constraining Pseudorandom Functions Privately

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.

Joint work with Dan Boneh, and David J. Wu.

Semantically Secure Order-Revealing Encryption: Multi-Input Functional Encryption Without Obfuscation

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.

Joint work with Dan Boneh, Mariana Raykova, Amit Sahai, Mark Zhandry, and Joe Zimmerman.

Losing Weight By Gaining Edges

We present a new way to encode weighted sums into unweighted pairwise constraints, with implications to the k-SUM problem, and also with finding cliques in node-weighted graphs.

Joint work with Amir Abboud, and Ryan Williams.

Improved Constructions of PRFs Secure Against Related-Key Attacks

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 and Their Applications

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).

Joint work with Dan Boneh, Kevin Lewi, Hart Montgomery, and Ananth Raghunathan.

Exact Weight Subgraphs and the k-Sum Conjecture

We connect natural subgraph finding problems on edge-weighted graphs with the infamous k-Sum Conjecture, establishing tight reductions between graph problems and decision problems on sums.

Joint work with Amir Abboud, and Kevin Lewi.

Preventing Unraveling in Social Networks: The Anchored k-Core Problem

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.

Joint work with Kshipra Bhawalkar, Jon Kleinberg, Tim Roughgarden, and Aneesh Sharma.

The Online Metric Matching Problem for Doubling Metrics

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.

Iterating Invertible Binary Transducers

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.