Raghav Malik

My Research

TL;DR: I'm interested in building compilers and PLs for privacy-preserving computation.

The style of privacy-preserving computation I'm interested in is Multiparty Computation (MPC): a class of cryptographic techniques in which mutually distrustful parties collaborate to compute a function without revealing their private inputs to the function. More specifically, a lot of my work deals with Fully Homomorphic Encryption (FHE), a particular MPC protocol that works by encrypting inputs and then performing computations on the ciphertexts. People care a lot about MPC—at least, I do—because it enables privacy-preserving computation, and has some really cool applications like secure machine learning or offloading analyses over sensitive data. Unfortunately, actually writing programs that use MPC in practice is really hard: even in the current state of the art, the cryptographic overhead is insane (like, several orders of magnitude slower than normal), and the programming model can be highly counterintuitive for non-cryptographers.

I'm a compiler person, and with compilers as my hammer, the world of MPC looks a lot like a nail: a compiler can abstract away all the messy details about the MPC programming model, and allow you to write programs in a comfortable, familiar language. A lot of classic MPC compilers take a very…80's-esque…approach to compilation (mechanically translating operations into their secure equivalents and doing very little optimization on top of this). My research focuses on building compilers that are MPC-aware: By knowing something about the MPC scheme we're targeting, we're able to automatically apply some really cool tricks from the depths of crypto literature! For example, in Coyote, I showed how, by considering the subtleties of the cost model for vectorization in some FHE schemes we can avoid a lot of the pitfalls that classic, SLP-style vectorizers run into (and, as an added benefit, automatically find really good data layouts!) In COIL, I demonstrated that because of the way branches work in MPC (they don't), we have to be really careful when translating programs with control flow. By playing some clever tricks involving remembering branching conditions, we can sometimes avoid doing unnecessary computation altogether!

Of course, we can take all this a step further. Instead of just designing compilers that target particular cryptosystems, we can make cryptosystems that are better compilation targets and then build the compilers (I'm calling this "compiler-cryptosystem codesign" because it sounds like "hardware-software codesign"). I started working towards this goal with COATL, where I showed that by replacing the fundamental unit of computation in CGGI (a particular style of FHE scheme) with a thing I called arithmetic lookup tables instead of the usual Boolean gates, we can build compilers that manage to express the same programs using fewer CGGI operations overall!

My research barely scratches the surface of what I think is possible in this space! A question I've been thinking about recently is, what features should a cryptosystem support to make compiler writers' jobs easier? What are the right abstractions to use here at the protocol level? What about at the "language" level? Some really cool people have done some really cool work (like Viaduct, Taype) about designing better languages for MPC, but a lot of this is still pretty theoretical; how do we build actual, usable compilers for these languages?
People have recently been looking at running FHE on things like dedicated hardware accelerators; what would it take to write compilers that target these, instead of the usual FHE libraries?
Finally, cryptographers keep adding features to their FHE schemes that compilers don't really know how to use (my favorite examples of this are scheme switching and faster BFV bootstrapping). Someone should do something about that!!
If any of these questions sound interesting to you, or you have ideas or answers, please feel free to contact me!

Publications

• HACCLE: Metaprogramming for Secure Multi-Party Computation

  (GPCE 2021)

  Yuyan Bao, Kirshanthan Sundararajah, Raghav Malik, Qianchuan Ye, Christopher Wagner, Nouraldin Jaber, Fei Wang, Mohammad Hassan Ameri, Donghang Lu, Alexander Seto, Benjamin Delaware, Roopsha Samanta, Aniket Kate, Christina Garman, Jeremiah Blocki, Pierre-David Letourneau, Benoit Meister, Jonathan Springer, Tiark Rompf, Milind Kulkarni

  Abstract

  ← Back

  Cryptographic techniques have the potential to enable distrusting parties to collaborate in fundamentally new ways, but their practical implementation poses numerous challenges. An important class of such cryptographic techniques is known as Secure Multi-Party Computation (MPC). Developing Secure MPC applications in realistic scenarios requires extensive knowledge spanning multiple areas of cryptography and systems. And while the steps to arrive at a solution for a particular application are often straightforward, it remains difficult to make the implementation efficient, and tedious to apply those same steps to a slightly different application from scratch. Hence, it is an important problem to design platforms for implementing Secure MPC applications with minimum effort and using techniques accessible to non-experts in cryptography.

  In this paper, we present the HACCLE (High Assurance Compositional Cryptography: Languages and Environments) toolchain, specifically targeted to MPC applications. HACCLE contains an embedded domain-specific language Harpoon, for software developers without cryptographic expertise to write MPC-based programs, and uses Lightweight Modular Staging (LMS) for code generation. Harpoon programs are compiled into acyclic circuits represented in HACCLE's Intermediate Representation (HIR) that serves as an abstraction over different cryptographic protocols such as secret sharing, homomorphic encryption, or garbled circuits. Implementations of different cryptographic protocols serve as different backends of our toolchain. The extensible design of HIR allows cryptographic experts to plug in new primitives and protocols to realize computation. And the use of standard metaprogramming techniques lowers the development effort significantly.

  PDF on arXiv Abstract →

• Vectorized Secure Evaluation of Decision Forests

  (PLDI 2020)

  Raghav Malik, Vidush Singhal, Benjamin Gottfried, Milind Kulkarni

  Abstract

  ← Back

  As the demand for machine learning-based inference increases in tandem with concerns about privacy, there is a growing recognition of the need for secure machine learning, in which secret models can be used to classify private data without the model or data being leaked. Fully Homomorphic Encryption (FHE) allows arbitrary computation to be done over encrypted data, providing an attractive approach to providing such secure inference. While such computation is often orders of magnitude slower than its plaintext counterpart, the ability of FHE cryptosystems to do ciphertext packing — that is, encrypting an entire vector of plaintexts such that operations are evaluated elementwise on the vector — helps ameliorate this overhead, effectively creating a SIMD architecture where computation can be vectorized for more efficient evaluation. Most recent research in this area has targeted regular, easily vectorizable neural network models. Applying similar techniques to irregular ML models such as decision forests remains unexplored, due to their complex, hard-to-vectorize structures. In this paper we present COPSE, the first system that exploits ciphertext packing to perform decision-forest inference. COPSE consists of a staging compiler that automatically restructures and compiles decision forest models down to a new set of vectorizable primitives for secure inference. We find that COPSE's compiled models outperform the state of the art across a range of decision forest models, often by more than an order of magnitude, while still scaling well.

  ACM DL Page PDF on arXiv Code Abstract →

• Coyote: A Compiler for Vectorizing Encrypted Arithmetic Circuits

  (ASPLOS 2023)

  Raghav Malik, Kabir Sheth, Milind Kulkarni

  Abstract

  ← Back

  Fully Homomorphic Encryption (FHE) is a scheme that allows a computational circuit to operate on encrypted data and produce a result that, when decrypted, yields the result of the unencrypted computation. While FHE enables privacy-preserving computation, it is extremely slow. However, the mathematical formulation of FHE supports a SIMD-like execution style, so recent work has turned to vectorization to recover some of the missing performance. Unfortunately, these approaches do not work well for arbitrary computations: they do not account for the high cost of rotating vector operands to allow data to be used in multiple operations. Hence, the cost of rotation can outweigh the benefits of vectorization. This paper presents Coyote, a new approach to vectorizing encrypted circuits that specifically aims to optimize the use of rotations. It tackles the scheduling and data layout problems simultaneously, operating at the level of subcircuits that can be vectorized without incurring excessive data movement overhead. By jointly searching for good vectorization and lane placement, Coyote finds schedules that avoid sacrificing one for the other. This paper shows that Coyote is effective at vectorizing computational kernels while minimizing rotations, thus finding efficient vector schedules and smart rotation schemes to achieve substantial speedups.

  ACM DL Page Code Abstract →

• COIL: Compiling Homomorphic Circuits With Control Flow

  (Preprint)

  Raghav Malik, Milind Kulkarni

  Abstract

  ← Back

  Fully Homomorphic Encryption (FHE) enables evaluating computations over ciphertexts without revealing the encrypted data. A key challenge when compiling for FHE is dealing with control flow: the usual semantics require the party evaluating the program to learn something about each branch, which violates the basic premise of secure computations. Standard "multiplexer"-based compilers solve this problem by generating programs that require the evaluator to execute every possible path, obviating the need to know which path is correct. Thus, they provide oblivious semantics at the cost of producing unwieldy circuits that are difficult to effectively optimize.

  We present COIL, an FHE compiler that addresses the control flow challenge by restructuring how control flow in circuits is interpreted, replacing the use of multiplexers with path forests, and enabling a series of path-dependent optimizations that result in more efficient realizations of complex branching kernels. We demonstrate on a variety of benchmarks that COIL outperforms other state-of-the-art FHE compilation techniques, often by more than an order of magnitude.

  Download PDF Abstract →

• Circuit Optimization Using Arithmetic Table Lookups

  (Preprint)

  Raghav Malik, Vedant Paranjape, Milind Kulkarni

  Abstract

  ← Back

  Fully Homomorphic Encryption (FHE) is a cryptographic technique that enables privacy-preserving computation. State-of-the-art Boolean FHE implementations provide a very low-level interface, usually exposing a limited set of Boolean gates that programmers must use to write their FHE applications. This programming model is unnecessarily restrictive: many Boolean FHE schemes support programable bootstrapping, an operation that allows evaluation of an arbitrary fixed-size lookup table. However, most modern FHE compilers are only capable of reasoning about traditional Boolean circuits, and therefore struggle to take full advantage of programmable bootstrapping.

  We present COATL, an FHE compiler that makes use of programmable bootstrapping to produce circuits that are smaller and more efficient than their traditional Boolean counterparts. COATL generates circuits using arithmetic lookup tables, a novel abstraction we introduce for reasoning about computations in Boolean FHE programs. We demonstrate on a variety of benchmarks that COATL can generate circuits that run up to 1.5x faster than those generated by other state-of-the-art compilation strategies.

  Download PDF Abstract →

Experience

Education

• PhD, Computer Engineering
  2019-2025 (expected)
  Purdue University
• BS, Computer Engineering
  2016-2019
  Purdue University

Internships

• Microsoft Research (MSR)
  Summer 2022
  Seattle, WA
  Worked on developing better cost models and scheduling optimizations for the MSCCL GPU communication collective compiler.
• Amazon Robotics
  Summer 2021
  Austin, TX
  Developed a DSL for expressing complex data validation rules, and created a bot that ran at code review time to flag data records that broke as a result of any change pushed to a validation model.
• AWS Kinesis
  Summer 2020
  Palo Alto, CA
  Designed and developed a feature to add support to Kinesis Firehose for streaming and batching Avro records directly into S3.
• AWS Kinesis
  Summer 2019
  Palo Alto, CA
  Onboarded Kinesis Firehose with AWS Service Quotas to provide a streamlined interface for customers to request usage limit increases. Deployed a serverless Lambda function to monitor and report usage Firehose statistics.

Talks

• Coyote: A Compiler for Vectorizing Encrypted Arithmetic Circuits
  6 October 2023
  Midwestern PL Summit 2023
  
  
  17 April 2023
  Galois, Inc.
  
  
  27 March 2023
  ASPLOS 2023
• Vectorized Secure Evaluation of Decision Forests
  19 October 2022
  Cornell University
  
  
  21 October 2021
  Splash! 2021

Contact

• Twitter
• Facebook
• Instagram
• GitHub

Elements

i = 0;

while (!deck.isInOrder()) {
    print 'Iteration ' + i;
    deck.shuffle();
    i++;
}

print 'It took ' + i + ' iterations to sort the deck.';