Kevin Lewi

Stanford Cryptography Ph.D. Student

klewi at cs.stanford.edu

I'm currently a fifth-year PhD student in computer science at Stanford University. My PhD focus is in cryptography and security, and I am advised by Dan Boneh. I will soon be joining Facebook as a full-time research scientist in Summer 2016.

Most of my recent research has been on the constructions of this new, exciting cryptographic primitive called "order-revealing encryption", and also more generally, multi-input functional encryption. Learn more about our ORE research efforts here.

I have also implemented a few of my research projects that have produced cryptographic primitives. These are all released on GitHub under an open source license.

Fall 2011 - Spring 2016

Ph.D. in Cryptography from Stanford University

Advised by Dan Boneh.

Summer 2015

With Facebook as a security software engineer intern

Contributed to improving the state of searchable symmetric
encryption techniques used for storing sensitive data on
Facebook servers.

Summer 2014

With Google as a research scientist intern

Worked with the Market Research and Algorithms team on
recommender systems to improve user suggestions.

Fall 2008 - Spring 2011

Bachelors in Computer Science from Carnegie Mellon University

5Gen: A Framework for Prototyping Applications Using Multilinear Maps and Matrix Branching Programs

We initiate a systematic study of mmap-based constructions, building a general framework, called 5Gen, to experiment with program obfuscation and multi-input functional encryption.

Joint work with Alex Malozemoff, Daniel Apon, Brent Carmer, Adam Foltzer, Daniel Wagner, David Archer, Dan Boneh, Jonathan Katz, and Mariana Raykova.

Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds

We give new constructions of order-revealing encryption with improved security guarantees and also show how to perform range queries efficiently in a manner that is robust against inference attacks.

Joint work with David J. Wu.

Function-Hiding Inner Product Encryption is Practical

We construct inner product encryption with the function-hiding property, and we validate the practicality of our encryption scheme through implementation.

Joint work with Sam Kim, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J. Wu.

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 is also practical.

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.

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.

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 pseudorandom functions that are secure against a large class of related-key attacks.

Joint work with Hart Montgomery and Ananth Raghunathan.

Key Homomorphic PRFs and Their Applications

We construct the first provably secure key homomorphic pseudorandom functions in the standard model.

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.

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.

Joint work with Anupam Gupta.

Iterating Invertible Binary Transducers

We study iterated transductions defined by a class of invertible transducers over the binary alphabet.

Joint work with Klaus Sutner.

5Gen

A framework for applications of multilinear maps, including obfuscation and multi-input functional encryption.

FastORE

A practical implementation of order-revealing encryption, as described by our publication here.

FHIPE

An implementation of function-hiding inner product encryption.