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.
- 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
- 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
- Ankit Gupta, neeraj kayal, and satya lokam, Efficient Reconstruction of Random Multilinear Formulas, in Foundations of Computer Science (FOCS), IEEE, October 2011
- Neeraj Kayal, Efficient algorithms for some special cases of the polynomial equivalence problem, in Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2011
- Raghav Bhaskar, Karthekeyan Chandrasekaran, Satyanaryana V. Lokam, Peter L. Montgomery, Ramarathnam Venkatesan, and Yacov Yacobi, An observation about variations of the Diffie-Hellman assumption, in Serdica Journal of Computing, 2009
- Neeraj Kayal and Shubhangi Saraf, Blackbox Polynomial Identity Testing for Depth 3 Circuits, in Foundations of Computer Science (FOCS), IEEE, 2009
- Raghav Bhaskar, K. Chandrasekaran, Satyanarayana V. Lokam, P. L. Montgomery, R. Venkatesan, and Yacov Yacobi, Vulnerabilities in Anonymous Credential Systems, in Electr. Notes Theor. Comput. Sci., vol. 197, no. 2, pp. 141-148, Elsevier , 2008
- Sanjam Garg, Raghav Bhaskar, and Satyanarayana V. Lokam, Improved Bounds on Security Reductions for Discrete Log Based Signatures, in CRYPTO, Springer, 2008