Kevin Lewi
Facebook Research Scientist
klewi at fb.com

Biography

I'm a research scientist / software engineer at Facebook. In 2016, I graduated with a PhD in computer science at Stanford University. My PhD focus was in cryptography and security, advised by Dan Boneh.

Research

Recently, I have been working on some Rust libraries for implementing various cryptographic primitives, including OPAQUE, VOPRF, and AKD (key transparency). Check out my Github for more projects!

Here are a couple of blog posts that cover some of the work I have been doing with Meta in recent years:

Some of my past research has focused on the constructions of a cryptographic primitive called "order-revealing encryption", and also more generally, multi-input functional encryption. Learn more about the ORE research efforts here.

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

Summer 2016 - present
Research Scientist at Facebook
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

Libraries

akd

A Rust implementation of an Auditable Key Directory for key transparency protocols.

winterfell

A Rust implementation of a STARK prover and verifier for arbitrary computations.

voprf

A Rust implementation of the (Verifiable) Oblivious Pseudorandom Function protocol.

opaque-ke

A Rust implementation of the OPAQUE key exchange protocol.

Ristretto255.js

A pure-JS implementation of the Ristretto255 group operations, built on top of the popular TweetNaCl.js crypto library.

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.

Publications

Parakeet: Practical Key Transparency for End-to-End Encrypted Messaging
NDSS 2023

Key transparency has been presented as an efficient solution for detecting a server that attempts to dishonestly serve keys. We design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store.

Joint work with Harjasleen Malvai, Lefteris Kokoris-Kogias, Alberto Sonnino, Esha Ghosh, Ercan Ozturk, and Sean Lawlor.

Oblivious Revocable Functions and Encrypted Indexing
ePrint 2022

We present a new primitive, called the Oblivious Revocable Function (ORF), which allows identifiers to be obliviously mapped to a consistent value across multiple devices, while enabling the server to permanently remove an individual device’s ability to map values.

Joint work with Jon Millican, Ananth Raghunathan, and Arnab Roy.

Aggregating and thresholdizing hash-based signatures using STARKs
AsiaCCS 2022

This work presents an approach for compressing hash-based signatures using STARKs. We focus on constructing a hash-based t-of-n threshold signature scheme, as well as an aggregate signature scheme.

Joint work with Irakliy Khaburzaniya, Kostas Chalkias, and Harjasleen Malvai.

HashWires: Hyperefficient Credential-Based Range Proofs
PETS 2021

This paper presents HashWires, a hash-based range proof protocol that is applicable in settings for which there is a trusted third party (typically a credential issuer) that can generate commitments.

Joint work with Kostas Chalkias, Shir Cohen, Fredric Moezinia, and Yolan Romailler.

Single-Message Credential-Hiding Login
ePrint 2020

We introduce the notion of credential-hiding login, which enables a client to authenticate itself by sending a single message to the server, while ensuring the correct verification of credentials and maintaining credential privacy in the same strong sense as guaranteed by asymmetric PAKEs.

Joint work with Payman Mohassel and Arnab Roy.

Securing Update Propagation with Homomorphic Hashing
ePrint 2019

We describe how Facebook handles the large-scale propagation of updates securely, using a lattice-based homomorphic hash function to help provide integrity without sacrificing efficiency.

Joint work with Wonho Kim, Ilya Maykov, and Stephen Weis.

Scaling Backend Authentication at Facebook
RWC 2018

We describe two token-based methods for authentication within Facebook to provide secure authorization within Facebook's infrastructure.

Joint work with Callen Rain, Stephen Weis, Yueting Lee, Haozhi Xiong, and Benjamin Yang.

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

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
CCS 2016

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
ArcticCrypt 2016

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
FSE 2016

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 Weis, and David J. Wu.

Constraining Pseudorandom Functions Privately
PKC 2017

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
EUROCRYPT 2015

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
ESA 2014

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
ACNS 2014

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
CRYPTO 2013

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

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

Exact Weight Subgraphs and the k-Sum Conjecture
ICALP 2013

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.

Preventing Unraveling in Social Networks: The Anchored k-Core Problem
ICALP 2012 / SIDMA 2015

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
ICALP 2012

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
DCFS 2012 / JALC 2012

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

Joint work with Klaus Sutner.