Ankit Kumar Misra

Hello! I am a second-year doctoral student in the Computer Science department at UCLA, where I am fortunate to be advised by Prof. Rafi Ostrovsky.

My research interests lie in theoretical and applied cryptography, and in particular, secure multi-party computation (MPC). I am also broadly interested in algorithms and theoretical computer science.

Previously, I completed my Bachelors degree in Computer Science and Engineering at IIT Bombay, where I worked on some fascinating problems with Prof. Manoj Prabhakaran at the Trust Lab, IIT Bombay. During my undergraduate studies, I had the fantastic opportunity to visit Microsoft Research for a summer internship, where I was able to work with Dr. Nishanth Chandran and Dr. Divya Gupta. Prior to that, I also collaborated remotely with Prof. Sándor Fekete and his amazing group at TU Braunschweig.

In my spare time, you will find me reading a book (usually thrillers or psychology), playing the keyboard (check this out!), listening to rock music, or watching a movie or an anime.

Email  |  CV  |  ORCID  |  GitHub  |  LinkedIn

Adaptive Security, Erasures, and Network Assumptions in Communication-Local MPC

We proved the impossibility of adaptively secure reliable message transmission (RMT) over a polylogarithmic-locality network using high-expansion store-and-forward (SF) protocols, which describes all previously known gossiping protocols, in a model without erasures. In the presence of erasures, we presented an SF RMT protocol for an honest majority, and proved impossibility for a dishonest majority. Further, under stronger assumptions (i.e., trapdoor permutations with a reverse domain sampler, and compact and malicious circuit-private FHE), we proposed a (non-SF) sublinear output-set (SOS) RMT protocol for an adaptive adversary corrupting a constant fraction of parties, with only polylogarithmically many receivers. Finally, we showed how to realize MPC and SOS-MPC using RMT and SOS-RMT, respectively.

Dishonest Majority Constant-Round MPC with Linear Communication from DDH

We designed the first concretely efficient n-party garbling protocol with O(n|C|) communication, secure against a malicious adversary corrupting up to n-1 parties. Our construction used a public key encryption scheme based on the DDH assumption, along with preprocessing techniques from Rachuri and Scholl (CRYPTO 2022). We demonstrated the concrete efficiency of our protocol by implementing and showing significant improvements over the previous state-of-the-art protocol of Wang et al. (CCS 2017). Even compared with the more recent breakthrough of Beck et al. (CCS 2023), which achieved only O(|C|) total communication, our protocol had lower concrete costs for n < 3500 parties.

A Gale-Shapley View of Unique Stable Marriages

We proposed two novel sufficient conditions, MaxProp and MaxRou, for the uniqueness of stable matchings, based on a maximal number of proposals and rounds, respectively, required for an execution of the Gale-Shapley algorithm. We gave a complete structural characterization of preference profiles satisfying MaxProp and MaxRou, and we determined their relative position in the space of all profiles with unique stable matchings, with respect to the previously known No-Crossing Condition (NCC) and Sequential Preference Condition (SPC).

Secure Non-Interactive Reducibility is Decidable

We derived a generalized junta theorem for Fourier transforms of Boolean functions over generalized domains, and used it along with cryptographic techniques to prove that, given a pair of two-party correlations, the existence of a statistical SNIR implies the existence of a perfect SNIR between them. This in turn was used to design an algorithm for deciding the existence of a statistical SNIR between two correlations.

Page design source: Jon Barron Last updated: October 6, 2024