Researchers in the area of Cryptography and Complexity investigate theoretical and applied aspects of cryptography, computational complexity, and related areas of mathematics. Specific interests include complexity bounds in arithmetic and Boolean models of computation, coding theory, (in)approximability, foundations of cryptographic schemes and protocols, protocol composition, security aspects of signatures, and mathematical models for privacy.
Some of the ongoing projects are mentioned below:
a) Protocol Composition
General positive results for secure two-party and multi-party computation protocols were obtained more than two decades ago. These results were for the setting where each protocol execution is done in isolation. With the proliferation of the network setting (and especially the internet), an ambitious effort to generalize these results and obtain concurrently secure protocols was started. There are a number of sub problems in this general area which I am interested in. One problem relates to constructing efficient non-malleable cryptographic protocols (such as for commitments and zero-knowledge). There is the interesting direction of what type of concurrently secure protocols can be designed in the plain model (without trust assumptions). Or, what are the reasonable trust assumptions which allow us to design strongly secure protocols (such as satisfying the notion of universal composability).
b) Resettable Computation
Consider a cryptographic protocol. Can a party use a fixed random tape in multiple (or even all) executions and still preserve its security? This is the intriguing notion of resettable secure computation. We would like to design secure protocols in the setting where one or more parties would like to re-use the same random coins in multiple executions. One could ask for design of zero-knowledge as well as general secure computation in this direction. One could ask for protocols where one or all parties would like to re-use their random coins. This problem is connected to various other notions such as stateless computation, hardware based cryptography, black-box lower bounds, etc.
c) Leakage resilient cryptographic protocols
Traditional models of secure computation assume that the internal state of a (honest) party is completely hidden from the attacker. However this ``black-box” assumption might not always hold in practice. What if somehow adversary is able to get some leakage on the internal state of honest parties. Can we still preserve their security? There are various question in this direction. For example, one might assume a preprocessing phase (which can be either interactive or non-interactive). Or one might relax security definitions.
d) Noiseless Privacy and generalized notions of Differential Privacy
The notion of Differential Privacy (DP) has recently emerged as a gold standard in the field of database privacy. While this notion has the benefit of providing concrete theoretical privacy (compared to various previous ad-hoc approaches), the major drawback is that any mechanism satisfying this notion needs to inject noise in the output thereby limiting its applicability to many settings. In this project, we are working on privacy definitions that imply strong privacy guarantees while requiring addition of no or small external noise.
The idea we explore is to exploit the entropy already present in the database and substitute that in the place of external noise in the output. The privacy guarantee we provide is very similar to DP but where that guarantee “comes from" is very different. To achieve our privacy notions, we make assumptions about the dataset distribution and the auxiliary information that the adversary has.
In a recent work, we formalized the notion of noiseless privacy, introduced two definitions and showed that they are equivalent. We also provided examples of certain types of Boolean and real queries which can be answered in a noiseless private manner under natural (and well understood) conditions. We also showed how multiple queries (composability) can be answered in a noiseless private manner in dynamic data-sets.
We are currently working on developing generalized privacy definitions which can be achieved be a wider class of mechanisms. For instance, both noisy and noiseless mechanisms may possibly satisfy our privacy notion, albeit with different parameters.
e) Error-correcting codes and cryptographic applications
Can error-correcting codes be "updatable"? That is, can one encode a message m into a codeword c, and then change c to an encoding of m' (where m' and m differ only in 1 bit), by only changing a few bits of c? For what error models are such constructions possible? We formalize the notion of locally updatable codes and also provide cryptographic applications of such codes (in particular to the area of proofs of retrievability).
The recent notion of non-malleable codes have found interesting applications in cryptography. Informally, non-malleable codes allow an encoder to encode a message m, such that an adversary (in a specific tampering model) cannot tamper the codeword in such a way that it decodes to a message related to m in some way. In recent work, we introduce the notion of "block-wise" non-malleable codes that strengthen the adversarial model considered in previous works (namely that of a split-state tampering). We also provide interesting connections of this notion with non-malleable commitments.
f) Large-scale Secure computation
What are some of the challenges when running secure computation on a very large scale (millions of nodes)? An assumption made in most secure computation protocols is that every participant in the protocol can share a secure channel with every other participant (in other words, the communication graph is a clique). In many natural situations, this assumption is not realistic. In a series of works, we show how secure computation can be achieved even when parties are connected by sparse networks. We provide results with varying flavors - information-theoretic (almost-everywhere) security, computational (everywhere) security, node/edge corruptions, and so on.
- Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, and Vassilis Zikas, The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults, in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, ACM, January 2015.
- Nishanth Chandran and Sanjam Garg, Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions, in Progress in Cryptology - INDOCRYPT 2014 - 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings, Springer, December 2014.
- Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky, Position-Based Cryptography, in SIAM Journal on Computing, vol. 43, no. 4, pp. 1291–1341, SIAM – Society for Industrial and Applied Mathematics, August 2014.
- Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, and Leonid Reyzin, Privacy amplification with asymptotically optimal entropy loss, in Journal of ACM, vol. 61, no. 5, pp. 29, ACM – Association for Computing Machinery, August 2014.
- Nishanth Chandran, Srinivasan Raghuraman, and Dhinakaran Vinayagamurthy, Constrained Pseudorandom Functions: Verifiable and Delegatable, in IACR Cryptology ePrint Archive, vol. 2014, pp. 522, July 2014.
- Nishanth Chandran, Bhavana Kanukurthi, and Rafail Ostrovsky, Locally Updatable and Locally Decodable Codes, in Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, Springer, March 2014.
- Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, and Keita Xagawa, Re-encryption, Functional Re-encryption, and Multi-hop Re-encryption: A Framework for Achieving Obfuscation-Based Security and Instantiations from Lattices, in Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, Springer, March 2014.
- Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, and Rafail Ostrovsky, Achieving Privacy in Verifiable Computation with Multiple Servers - Without FHE and without Pre-processing, in Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, Springer, March 2014.
- Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner, Position-Based Quantum Cryptography: Impossibility and Constructions, in SIAM Journal on Computing, vol. 43, no. 1, pp. 150–178, SIAM – Society for Industrial and Applied Mathematics, January 2014.
- Nishanth Chandran, JuanA. Garay, and Rafail Ostrovsky, Almost-Everywhere Secure Computation with Edge Corruptions, in Journal of Cryptology, pp. 1-24, Springer US, December 2013.
- Prabhanjan Ananth, Raghav Bhaskar, Vipul Goyal, and Vanishree Rao, On The (In)security Of Fischlin’s Paradigm, in To appear in the Proceedings on Theory of Cryptography Conference 2013., 2013.
- Nishanth Chandran, Juan A. Garay, and Rafail Ostrovsky, Edge Fault Tolerance on Sparse Networks, in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, Springer, July 2012.
- Nishanth Chandran, Melissa Chase, and Vinod Vaikuntanathan, Functional Re-encryption and Collusion-Resistant Obfuscation, in Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, Springer, March 2012.
- Neeraj Kayal, Affine Projections of Polynomials, in Symposium on Theory of Computing (STOC), ACM, 2012.
- Raghav Bhaskar, Abhishek Bhowmick, Vipul Goyal, Srivatsan Laxman, and Abhradeep Guha Thakurta, Noiseless Database Privacy, in Proceedings of the Seventeenth International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2011, Lecture Notes in Computer Science, December 2011.