I am a computer scientist interested in cryptography and security. BS from Iowa State University ↝ PhD from University of Illinois ↝ Assistant Prof at University of Montana (2009-2013) ↝ Assistant Prof at Oregon State (2013-2019) ↝ Associate Prof at Oregon State (2019-present). I am the only faculty member at Oregon State University whose name contains the substring "OSU".
Congrats to Ni Trieu
for defending her PhD and starting a postdoc at UC Berkeley!
I have been promoted to Associate Professor with indefinite tenure!
I will be area chair for cryptography at CCS 2019
, so please submit your coolest results! We will have 3 submission deadlines: in Feburary, May, and September.
Together with David Evans and Vlad Kolesnikov, we wrote a book about MPC
. It gives an overview of the current state of the art and main constructions.
Paper on thumbnail-preserving encryption accepted to NDSS 2019.
Paper on post-quantum signatures accepted to CCS 2018, and paper on UC hybrid protocols
accepted to TCC 2018. Also find me featured in this Oregonion article
where I offer some skepticism about bunk cryptanalysis.
I will be delivering a lecture series on 2PC techniques at the crypt@b-it summer school
. Come to Germany for a week in July and learn 2PC!
OSU takeover of ACM CCS 2017 has been successful: 3 papers for me (malicious PSI
, multi-party PSI
), 5 for my group members, 6 for Oregon State! Addendum Sep 2017: plus 1 paper at a CCS-affiliated workshop
I will be on the program committee for Eurocrypt 2018
, so get your best results in order for the Sep 19 deadline!
Typically I teach CS 321 (Theory of Computation) in fall, CS 427 (Intro to Cryptography) in winter, and CS 517 (Computational Complexity) in spring.
I am writing an undergraduate textbook on cryptography called The Joy of Cryptography. The book is free and will continue to be free, thanks to support from Oregon State's open textbook initiative.
- Gayathri Garimella (PhD)
- Lawrence Roy (PhD)
- Jaspal Singh (PhD)
- Ian McQuoid (PhD)
- Perry Hooker (MS, 2012) → Oracle
- Zhangxiang Hu (MS, 2015) → PhD program U Oregon
- Morgan Shirley (MS, 2017) → PhD program Toronto
- Peter Rindal (PhD, 2018) → Visa Research
- Brent Carmer (PhD, 2018) → Galois
- Naimisha Saireddy (MS, 2019)
- Tommy Hollenberg (MS, 2019)
- Ni Trieu (PhD, 2019) → Berkeley postdoc → ASU faculty
I have started collecting some materials for new grad students (and their mentors) related to graduate study, so that I can refer to it easily for new students. The materials are biased towards my area of research, but there is also plenty of advice about grad school in general.
In Summer 2018 I was an invited lecturer at the crypt@b-it summer school in Bonn, Germany. I delivered a week-long course on efficient secure computation techniques. The focus was on things that I actually know about: 2PC based on garbled circuits, and PSI.
- Day 1: Overview of secure computation (applications and definitions) and textbook Yao's protocol. slides
- Day 2: Optimizations to garbled circuits (point-permute, free-XOR, half-gates, arithmetic garbling). slides
- Day 3: Optimizations to oblivious transfer (Beaver precomputation, OT extension, IKNP protocol and variants). slides
- Day 4: Protecting Yao's protocol from malicious attacks (cut-and-choose & its subtleties, cheating punishment, dual execution variants, batch cut-and-choose) slides
- Day 5: Private set intersection (classic DH protocol, OT-based equality tests, hashing techniques) slides
- Homework problems for all days
My main research focus is on cryptographic protocols for secure computation. These tools allow parties to perform computations on private data, so that they learn the outcome of the computation but nothing else. I am interested in both theoretical and practical aspects of secure computation techniques.
More specifically, my recent research has focused on:
- Private set intersection: Two parties each hold a set of items, and wish to learn which items they have in common, without revealing anything else about their sets. This special case of secure computation has many real-world applications.
- Garbled circuits: Garbled circuits are one of the few ways to achieve general-purpose secure computation protocols with just a few rounds of communication. I'm interested in making this core technique more efficient.
- Secure computation against malicious adversaries: My group has developed new techniques for hardening secure computation protocols against malicious participants, who may deviate arbitrarily from the protocol.
My research is supported by the NSF, including an NSF CAREER award, and faculty research awards from Google and Visa Research.
Various bean counting can be found on my Google scholar page and DBLP page. Below I include a link to a free version of almost all articles. Send me email or take advantage of sci-hub if you would like a copy of any paywalled publications.
On the (Im)Practicality of Adversarial Perturbation for Image Privacy
Minimal Symmetric PAKE and 1-out-of-N OT
from Programmable-Once Public Functions
Fast Database Joins and PSI for Secret Shared Data
Practical Privacy-Preserving K-means Clustering
PSI from PaXoS: Fast, Malicious Private Set Intersection
Scalable Private Set Union from Symmetric-Key Techniques
Characterizing Collision and Second-Preimage Resistance in Linicrypt
Secure Data Exchange: A Marketplace in the Cloud
SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension
Cheaper Private Set Intersection via Differentially Private Leakage
Balancing Image Privacy and Usability with Thumbnail-Preserving Encryption
A Pragmatic Introduction to Secure Multi-Party Computation
On the Structure of Unconditional UC Hybrid Protocols
TACHYON: Fast Signatures from Compact Knapsack
Optimizing Authenticated Garbling for Faster Secure Two-Party Computation
PIR-PSI: Scaling Private Contact Discovery
SWiM: Secure Wildcard Pattern Matching From OT Extension
Improvements for Gate-Hiding Garbled Circuits
Approximate Thumbnail Preserving Encryption
Workshop on Multimedia Privacy and Security 2017 article
Malicious-Secure Private Set Intersection via Dual Execution
Practical Multi-party Private Set Intersection from Symmetric-Key Techniques
DUPLO: Unifying Cut-and-Choose for Garbled Circuits
Improved Private Set Intersection against Malicious Adversaries
Non-Interactive Secure 2PC in the Offline/Online and Batch Settings
Sublinear Zero-Knowledge Arguments for RAM Programs
Reconciling Non-malleability with Homomorphic Encryption
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
Garbling Gadgets for Boolean and Arithmetic Circuits
Linicrypt: A Model for Practical Cryptography
Faster Malicious 2-party Secure Computation with Online/Offline Dual Execution
Fast and Secure Three-party Computation: The Garbled Circuit Approach
Efficient Zero-Knowledge Proofs of Non-Algebraic Statements with Sublinear Amortized Cost
Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates
How to Efficiently Evaluate RAM Programs with Malicious Security
Richer Efficiency/Security Tradeoffs in 2PC
FleXOR: Flexible garbling for XOR gates that beats free-XOR
Multi-Party Computation for Polynomials and Branching Programs without Simultaneous Interaction
Characterizing the Cryptographic Properties of Reactive 2-Party Functionalities
A Unified Characterization of Completeness and Triviality for Secure Function Evaluation
Must you know the code of f to securely compute f?
Universal Composability from Essentially Any Trusted Setup
Complexity of Multi-Party Computation Functionalities
Exploring the Limits of Common Coins Using Frontier Analysis of Protocols
A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security
Cryptographic Complexity Classes and Computational Intractability Assumptions
Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation
Towards Robust Computation on Encrypted Data
Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations
Homomorphic Encryption with CCA Security
Harvesting Credentials in Trust Negotiation as an Honest-But-Curious Adversary
Rerandomizable RCCA Encryption
Unpublished manuscripts & other writings
Garbled Neural Networks are Practical
Efficient Maliciously Secure Two Party Computation for Mixed Programs
Secure Your Data and Compute on It, Too
XRDS: Crossroads, the ACM Magazine for Students, 2015 article
Correspondences regarding cryptography between John Nash and the NSA
The Structure of Secure Multi-Party Computation
University of Illinois PhD dissertation, 2009 pdf
Garbled Circuits for Secure Computation
Indocrypt Tutorial, December 2017 slides
Towards Optimal Garbled Circuit Constructions
Allerton Conference, October 2015 slides
A Brief History of Practical Garbled Circuit Optimizations
Simons Institute workshop on Securing Computation, June 2015 slides video
Zero-Knowledge Proofs, with Applications to Sudoku and Where's Waldo
Educational talk, University of Montana, December 2008 slides
An Annotated Bibliography of Practical Secure Computation
A reference for researchers in secure computationwebsite
A browser-based platform for algorithm visualizationwebsite
I have served on the following program committees (reverse chronological):
CCS 2019 (cryptography area chair),
S&P (Oakland) 2019,
I am on the organizing committee for TPMPC: Theory and Practice of Multi-Party Computation Workshops and for CFAIL: Conference for Failed Approaches and Insightful Losses in Cryptology.
From 2014 to 2019 I served as communications secretary for the International Association for Cryptologic Research.
I have a personal website (never updated), a Flickr page, a Github page, and a few Youtube videos.