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) Security proofs for Identification and Signature schemes
Designing cryptographic primitives that are efficient to implement in practice as well as provably secure (under some hardness assumptions) is a major goal of cryptography. We are interested in studying the security of identification and signature schemes in particular and the models used to study their security. In an earlier work, we showed that the well-known Schnorr signatures cannot have a tight reduction to the Discrete-Log problem in the Random Oracle Model (ROM). Currently, we are studying the security of the Fischlin transform, which converts any interactive proof of knowledge into a NIZK-PoK with online extractors. We are also working on variants of the ROM, which are weaker (make fewer assumptions) in nature and thus are “closer” to the Standard model.
- 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, 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.
- 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.