Cryptography and Complexity

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.