Theory of Cryptography Conference (TCC) 2022 gets underway in Chicago on Monday, November 7, and 60 papers on a range of important problems in theoretical cryptography will be presented over fours days. TCC, organized by the International Association of Cryptology Research (IACR) is a leading conference in the area of theoretical cryptography.

This year’s TCC features three papers involving IITB Trust Lab members. Trust Lab’s Manoj Prabhakaran explained the context behind these papers.

“One of these is a collaboration with researchers at Bar-Ilan University and Georgia Tech. This work introduces a new model for secure multi-party computation (MPC) called SCALES. MPC is a powerful tool from modern cryptography which allows mutually distrusting parties to collaborate with each other without compromising on their privacy requirements. Over the last decade or so, MPC has been steadily transitioning from theory to practice. Part of this is driven by the development of MPC protocols that are suitable for deployment in settings with a variety of constraints on the participants. The SCALES model, which stands for ‘Small Clients and Larger Ephemeral Servers,’ is the latest in this line of work. The model presents several attractive features. While these features are challenging to realise, we do present a fairly efficient protocol in this model for computing arbitrary functions.”

This paper, titled “SCALES: MPC with Small Clients and Larger Ephemeral Servers,” was co-authored by Anasuya Acharya and Carmit Hazay of Bar-Ilan University, Vlad Kolesnikov of Georgia Tech and Manoj Prabhakaran. Incidentally, Acharya who is currently a Ph.D. student under the guidance of Hazay at Bar-Ilan University, completed her M.Tech. project at IIT Bombay, under Prabhakaran. On a virtual visit back to IITB, she presented this work at the Trust Lab colloquium. “We are continuing our work in the SCALES model as there are several potential improvements possible, both in terms of security and efficiency, and these improvements are essential before the protocol can be used in practical applications,” she added.

The other two papers investigate the complexity of functions, measured using the amount of cryptographic resources needed to securely compute a function by two mutually distrusting parties. This kind of “cryptographic complexity” of functions is closely related to their computational complexity. One of these papers, titled “Oblivious-Transfer Complexity of Noisy Coin-Toss via Secure Zero Communication Reductions,” started off as a B.Tech. Project by Saumya Goyal, under the guidance of Prabhakaran, and in collaboration with Varun Narayanan, a postdoctoral scholar at Tel Aviv University. “This result, for the first time established that there are randomised functions whose cryptographic complexity can arbitrarily grow even as the input and output lengths of the function remain constant. While this was perhaps what one would have suspected, no previously available analysis tools could break the barrier of the input length.” What proved vital for this breakthrough was an earlier result, in a paper titled “Zero-Communication Reductions,” co-authored by Narayanan and Prabhakaran with the former’s then Ph.D. advisor, Vinod Prabhakaran of TIFR and published at TCC 2020. “Zero-Communication Reductions, which can be used to define another seemingly abstruse notion of cryptographic complexity, provided us with a surprisingly effective tool for this problem. While we still do not fully understand the complexity measure arising from Zero-Communication Reductions, in the current work we managed to strengthen its connection with the standard notion of cryptographic complexity on the one hand, while on the other hand developed a way to analyse it directly.” For his B.Tech. Project, Goyal, who is currently pursuing a Masters degree at Stanford University, was awarded IIT Bombay’s “Undergraduate Research Award 2.”

The third paper “Secure Non-Interactive Reducibility is Decidable,” co-authored by Narayanan and Prabhakaran, along with Trust Lab student members Kaartik Bhushan and Ankit Misra, deals with a different measure of cryptographic complexity of functions. Prabhakaran explained: “In a recent line of work, including a work from our group, a notion of ‘Secure Non-Interactive Reduction’ has been proposed as a means of studying the cryptographic complexity of correlated random variables. This complexity notion could be considered a simplification of the traditional cryptographic complexity notion, making it more amenable to analysis. But a priori, this new notion leaves us with even more open problems than it helps to answer. Indeed, it is not even clear for which functions this new complexity notion is well-defined. What we do in this work is to fully answer this fundamental question. Along the way, we sharpen a so-called ‘Junta theorem,’ a general purpose tool from Fourier Analysis used in complexity theory. This may be of independent interest.”

“While we are happy to have made some progress, there are several deep problems here that remain wide open,” added Prabhakaran, “and we are looking forward to tackling some of them in follow up works.”