Raghav Malik

My Research

TL;DR: I'm interested in building compilers specifically to optimize Fully Homomorphic Encryption programs.

Fully Homomorphic Encryption refers to any number of encryption schemes that preserve the ring structure of their plaintext (i.e. if you encrypt two numbers and add or multiply the ciphertexts, you get back an encryption of the sum or product of the original numbers). FHE is a powerful tool for for implementing arbitrary fixed-size arithmetic circuits over encrypted data, but the underlying computational model is very different from the one you're used to. Taking these pecularities into account when compiling arithmetic FHE circuits is often challenging, and my research is interested in building compilers that automatically factor in all the FHE weirdness to produce efficient arithmetic circuits while letting the programmer concentrate on writing their programs.

At the moment, I'm specifically interested in developing vectorization techniques for FHE programs. While normal FHE computation is very slow (like, several orders of magnitude slower than normal), it does provide the ability to vectorize, or pack multiple identical operations into a single step. We have to be careful when vectorizing FHE programs, though, since at every step, all the data has to line up perfectly, and shuffling data around in FHE vectors is very expensive. I'm currently working on building a compiler that automatically figures out both data placement and how to group together operations to convert a scalar arithmetic circuit into an efficient vector program.

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 →

Experience

Education

• PhD, Computer Engineering
  2019-2024 (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.';