Cryptography and Complexity

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.

Publications