AAAnanya Appan

Ananya Appan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Ananya Appan has a total of 7 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Consensus in Multi Party Computation

    by Ananya Appan, David Heath, Ling Ren

    Secure Multi-Party Computation (MPC) protocols allow mutually distrusting parties to compute a function of their inputs without revealing their inputs. Consensus protocols allow mutually distrusting parties to agree on a common output. This article surveys how consensus can help to build MPC protocols that tolerate more corruptions and provide improved security. We describe what MPC results can be achieved with and without consensus, and give intuitions behind these results.

  • Open Access

    Oblivious Single Access Machines - A New Model for Oblivious Computation

    by Ananya Appan, David Heath, Ling Ren

    Oblivious RAM (ORAM) allows a client to securely outsource memory storage to an untrusted server. It has been shown that no ORAM can simultaneously achieve small bandwidth blow-up, small client storage, and a single roundtrip of latency. We consider a weakening of the RAM model, which we call the Single Access Machine (SAM) model. In the SAM model, each memory slot can be written to at most once and read from at most once. We adapt existing tree-based ORAM to obtain an oblivious SAM (OSAM) that has O(log n) bandwidth blow-up (which we show is optimal), small client storage, and a single roundtrip. OSAM unlocks improvements to oblivious data structures/algorithms. For instance, we achieve oblivious unbalanced binary trees (e.g. tries, splay trees). By leveraging splay trees, we obtain a notion of caching ORAM, where an access in the worst case incurs amortized O(log2 n) bandwidth blow-up and O(log n) roundtrips, but in many common cases (e.g. sequential scans) incurs only amortized O(log n) bandwidth blow-up and O(1) roundtrips. We also give new oblivious graph algorithms, including computing minimum spanning trees and single source shortest paths, in which the OSAM client reads/writes O(|E| ⋅ log |E|) words using O(|E|) roundtrips, where |E| is the number of edges. This improves over prior custom solutions by a log factor. At a higher level, OSAM provides a general model for oblivious computation. We construct a programming interface around OSAM that supports arbitrary pointer-manipulating programs such that dereferencing a pointer to an object incurs O(log d log n) bandwidth blowup and O(log d) roundtrips, where d is the number of pointers to that object. This new interface captures a wide variety of data structures and algorithms (e.g., trees, tries, doubly-linked lists) while matching or exceeding prior best asymptotic results. It both unifies much of our understanding of oblivious computation and allows the programmer to write oblivious algorithms combining various common data structures/algorithms and beyond.


  • Network Agnostic Perfectly Secure Multiparty Computation Against General Adversaries

    by Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

    In this work, we initiate the study of network-agnostic perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries, where the corruption capacity of the adversary is specified through an adversary structure, which is a set of potentially corrupt subsets of parties. Known MPC protocols are designed either assuming a synchronous network where every sent message is guaranteed to be delivered within some known time or assuming an asynchronous network where no timing assumptions are made and every sent message is eventually delivered. Perfectly-secure MPC protocols in the synchronous network can be designed as long as the underlying adversary structure satisfies the $ {{\mathcal {Q}}}^{(3)}$ condition, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only against $ {{\mathcal {Q}}}^{(4)}$ adversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against any $ {{\mathcal {Q}}}^{(3)}$ adversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against any $ {{\mathcal {Q}}}^{(4)}$ adversary structure. We answer the above question affirmatively. Fix any adversary structure ${\mathcal {Z}}_{s}$ and ${\mathcal {Z}}_{a}$ satisfying $ {{\mathcal {Q}}}^{(3)}$ and $ {{\mathcal {Q}}}^{(4)}$ conditions respectively, such that ${\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}$ . We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating ${\mathcal {Z}}_{s}$ and ${\mathcal {Z}}_{a}$ in synchronous and asynchronous networks respectively as long as the $ {{\mathcal {Q}}}^{(3, 1)}$ condition is satisfied, meaning that the union of no three subsets from ${\mathcal {Z}}_{s}$ and one subset from ${\mathcal {Z}}_{a}$ covers the entire set of parties. Our result generalizes the result of Appan, Chandramouli and Choudhury (IEEE Transactions on IT, 2023), which presents the only known perfectly-secure network-agnostic MPC protocol against threshold adversaries.


  • Perfectly-Secure Synchronous MPC With Asynchronous Fallback Guarantees

    by Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

    Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of n mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with information-theoretic security (also called unconditional security ) provides the strongest security guarantees and remains secure even against computationally unbounded adversaries. Perfectly-secure MPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in an error-free fashion. The focus of this work is perfectly-secure MPC. Known protocols are designed assuming either a synchronous or asynchronous communication network. It is well known that perfectly-secure synchronous MPC is possible as long as the adversary can corrupt any ts < n /3 parties. On the other hand, perfectly-secure asynchronous MPC protocols can tolerate up to ta < n /4 corrupt parties. A natural question is does there exist a single MPC protocol for the setting where the parties are not aware of the exact network type and which can tolerate up to ts < n /3 corruptions in a synchronous network and up to ta < n /4 corruptions in an asynchronous network. We design such a best-of-both-worlds perfectly-secure MPC protocol, provided 3 ts + ta < n holds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worlds Byzantine agreement (BA) protocol tolerating t < n /3 corruptions which remains secure both in a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worlds verifiable secret-sharing (VSS) protocol, which can tolerate up to ts and ta corruptions in a synchronous and in an asynchronous network respectively.