Chethan Kamath

E-mail: ckamath at protonmail dot com

I will be joining the CSE department at IITB as an assistant professor in Spring'24!

My primary field of research is cryptography, particularly its foundations. But my interests extend beyond to computational complexity theory and theoretical computer science in general.

BIO RESEARCH TALKS ETC.

Prior positions

2021-2023: Post-doc at Tel Aviv University, hosted by Nir Bitansky and Omer Paneth, and supported by an Azrieli fellowship.
2020-21: Post-doc at Charles University hosted by Pavel Hubáček
2020: Post-doc at Northeastern university hosted by Daniel Wichs
2014-2020: PhD from IST Austria under the supervision of Krzysztof Pietrzak. My PhD thesis was titled On the Average-Case Hardness of Total Search Problems.
2010-2013: Master's in CS from Indian Institute of Science, Bangalore under the guidance of Sanjit Chatterjee. My master's thesis was titled Constructing Provably Secure Identity-Based Signature Schemes.
2005-2009: Bachelor's in CS from University of Kerala (at TKM College of Engineering, Kollam).

Internships/Short-term visits

Simons Institute - Summer 2015
FACT Center - Summer 2017
Charles University, Prague - October 2017, 2019, July 2022

Publications

(Verifiable) Delay Functions from Lucas Sequences

with Charlotte Hoffmann, Pavel Hubáček and Tomáš Krňák

TCC 2023, to appear

[Synopsis] [Paper]
- Problem: A delay function is, loosely speaking, a function whose output cannot be computed faster even given parallelism. A verifiable delay function (VDF) is a delay function whose output can be "publicly certified" so that it can be verified by any party. Can we construct VDFs from weaker assumptions that those currently known?
- Result: We design (V)DFs assuming hardness of computing Lucas sequences in RSA group. Furthermore, we conjecture that this assumption is a weaker than the Rivest-Shamir-Wagner assumption, on which several current VDF candidates (Pietrzak's and Wesolowski's) are based on.

Batch Proofs are Statistically Hiding

with Nir Bitansky, Omer Paneth, Ron Rothblum and Prashant Nalini Vasudevan

Preprint, 2023

[Synopsis] [Paper] [Slides] [Talk by Prashant]
- Problem: Given \(t\) instances of SAT, the trivial way for an efficient prover to convince a verifier that all \(t\) instances are satisfiable is to send all the \(t\) satisfying assignments. Is it possible to do better in terms of communication? This is the problem of batch verification for \(\mathbf{NP}\).
- Result: We show (among other results) that this is unlikely by proving that such an interactive protocol can be used to construct a protocol that is (statistically) hides information about the assignments, which is believed to be unlikely.

Certifying Giant Nonprimes

with Charlotte Hoffman, Pavel Hubáček and Krzysztof Pietrzak

PKC 2023

[Synopsis] [Paper] [Slides by Charlotte] [Talk by Charlotte]
- Problem: GIMPS and PrimeGrid are large-scale volunteer projects dedicated to searching giant prime numbers of special forms like Mersenne and Proth primes. The numbers in the current search-space are millions of digits large and a participating volunteer needs to run resource-consuming primality tests. Once a candidate prime \(N\) has been found, the only way for another party to independently verify the primality of \(N\) used to be by repeating the expensive primality test. Can we do better?
- Result: We propose a practical mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can – parallel to running the primality test for \(N\) – generate an efficiently verifiable proof at a little extra cost certifying that \(N\) is not prime. The proof is obtained by applying the Fiat-Shamir heuristic to our interactive protocol, which has statistical soundness.

PPAD is as Hard as LWE and Iterated Squaring

with Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Alex Lombardi, Omer Paneth and Ron Rothblum

TCC 2022

[Synopsis] [Paper] [Slides] [Talk]
- Problem: In [11,12], we showed hardness of the class \(\mathbf{PPAD}\) in the random-oracle model (additionally assuming worst-case hardness of \(\#\)SAT). Follow-up works [JKKZ20,LV20] weakened the assumptions, but still rely on non-standard cryptographic assumptions. Is it possible to show \(\mathbf{PPAD}\)-hardness from polynomial hardness of standard cryptographic assumptions?
- Result: We use the recent results of Holmgren, Lombardi and Rothblum [HLR21] to derandomise the proof of exponentiation protocol of Block et al. [BHR+21], which yields hardness in \(\mathbf{PPAD}\) from polynomial hardness of iterated squaring (in any group) and learning with errors. Furthermore, we strengthen this to show hardness of \(\mathbf{UEOPL}\subseteq\mathbf{PPAD}\), which is one of the lowest sub-classes of \(\mathbf{TFNP}\).

Practical Statistically-Sound Proofs of Exponentiation in Any Group

with Charlotte Hoffman, Pavel Hubáček, Karen Klein and Krzysztof Pietrzak

Crypto 2022

[Synopsis] [Paper] [Slides by Charlotte] [Talk by Charlotte]
- Problem: For a group \(\mathbb{G}\), a proof of exponentiation allows a prover to convince a verifier that \(y=x^{q^T}\) for \((y,x,q,T)\in\mathbb{G}^2\times\mathbb{N}^2\). The existing constructions are either impractical [BHK+12] or guarantee weak soundness [Pie19,Wes20]. Can we have the best of both worlds?
- Result: Building upon [BHK+12], we show that this is indeed possible for `structured' \(q\). Moreover, we show that for applications, such structured \(q\) suffices.

Limits on the Adaptive Security of Yao’s Garbling

with Karen Klein, Krzysztof Pietrzak and Daniel Wichs

Crypto 2021

[Synopsis] [Paper] [Slides by Karen] [Talk by Karen]
- Problem: Can the upper bounds for loss in security of Yao's garbling shown in [7,18] improved?
- Result: We show that this is not possible using black-box reductions by building upon the result in [16]. As in [16], we use pebbling lower bounds and oracle separations.

On Treewidth, Separators and Yao’s Garbling

with Karen Klein and Krzysztof Pietrzak

TCC 2021

[Synopsis] [Paper] [Slides] [Talk]
- Problem: In the 80s, Yao proposed an elegant way to securely evaluate functions using garbled circuits. Is his garbling scheme fully secure?
- Result: Although security in a simulation-based model is known to be unattainable [AIKW13], we show that it is secure in the -- next-best -- indistinguishability-based model for some circuit classes. To this end, we use tools from algorithmic graph theory (e.g., treewidth) and circuit complexity

On the Cost of Adaptivity in Security Games on Graphs

with Karen Klein, Krzysztof Pietrzak and Michael Walter

TCC 2021

[Synopsis] [Paper] [Slides by Karen] [Talk by Karen]
- Problem: Are the upper bounds for loss in security established in [7,10] optimal?
- Result: We show that for certain cryptographic primitives whose security model involves the adversary constructing a dynamic graph -- like, e.g., constrained PRF and group key agreement -- this is indeed the case when restricted to 'oblivious' reductions. In particular, we use pebbling lower bounds and oracle separations to show fine-grained lower bounds on loss in security for these primitives.
https://ykondi.net/

Keep the Dirt: Tainted TreeKEM, an Efficient and Provably Secure Group Key Agreement Protocol

with Joël Alwen, Margarita Capretto, Miguel Cueto, Karen Klein, Guillermo Pascual-Perez, Krzysztof Pietrzak and Michael Walter

S&P 2021

[Synopsis] [Paper] [Slides by Guillermo] [Talk by Guillermo]
- Problem: Is TreeKEM, a continuous group key-agreement messaging protocol (currently being standardised by IETF), secure?
- Result: We propose Tainted TreeKEM, a slight variant of TreeKEM, and show that it is secure in a passive setting with only quadratic loss in security (in the random oracle model).

On Average-Case Hardness in TFNP from One-Way Functions

with Pavel Hubáček, Karel Král and Veronika Slívová

TCC 2020

[Synopsis] [Paper] [Slides by Veronika] [Talk by Veronika]
- Problem: In [12,13] we showed the existence of hard problems in lower sub-classes of TFNP under some cryptographic assumptions. But can we construct hard problems in TFNP from one-way functions, the weakest assumption in cryptography?
- Result: For a restricted class of black-box reductions, we show that this is not possible.F

Finding a Nash Equilibrium is no Easier than Breaking Fiat-Shamir

with Arka Rai Choudhuri, Pavel Hubáček, Krzysztof Pietrzak, Alon Rosen and Guy Rothblum

STOC 2019

[Synopsis] [Paper] [Slides] [Talk by Alon]
- Problem: How hard is it to find a Nash equilibrium?
- Result: We show that the complexity class \(\mathbf{PPAD}\), for which Nash equilibrium is complete, is (average-case) hard as long as the Fiat-Shamir transform is sound. Furthermore we extend this hardness to the class \(\mathbf{CLS}\) \(\subseteq\mathbf{PPAD}\).

PPAD-Hardness via Iterated Squaring Modulo a Composite

with Arka Rai Choudhuri, Pavel Hubáček, Krzysztof Pietrzak, Alon Rosen and Guy Rothblum

Preprint 2019

[Synopsis] [Paper]
- Problem: How hard is the complexity class \(\mathbf{PPAD}\)?
- Result: We show (average-case) hardness in PPAD under the assumption that the problem of repeated squaring in the RSA modulus is hard. Furthermore we extend this hardness to the class \(\mathbf{CLS}\) \(\subseteq\mathbf{PPAD}\).
- Remark: The results in the paper are superseded by [12].

Reversible Proofs of Sequential Work

with Hamza Abusalah, Karen Klein, Krzysztof Pietrzak and Michael Walter

Eurocrypt 2019

[Synopsis] [Paper] [Talk by Hamza]
- Problem: A proof of sequential work (also known as proof of time), defined by Mahmoody, Moran and Vadhan , allows a prover to convince a verifier that it has done a certain amount of sequential computation. Can we have a proof of sequential work where the computation is reversible?
- Result: We show this to be possible in the random oracle model by exploiting the Skip list data structure.

Adaptively-Secure Proxy Re-encryption

with Georg Fuchsbauer, Karen Klein and Krzysztof Pietrzak

PKC 2019

[Synopsis] [Paper]
- Problem: A proxy re-encryption (PRE) is a public-key encryption scheme that allows the holder of a key \(pk\) to derive a re-encryption key for any other key \(pk'\). This re-encryption key lets anyone transform ciphertexts under \(pk\) into ciphertexts under \(pk'\) without having to know the underlying message. Can we have secure PRE in the setting where the adversary gets to corrupt users in arbitrary, adaptive manner?
- Result: We show that in case the graph constructed by the adversary is restricted, then some of the constructions already achieve adaptive security. We make use of the framework from [7].

On the Memory-Hardness of Data-Independent Password-Hashing Functions

with Joël Alwen, Peter Gaži, Karen Klein, Georg Osang, Krzysztof Pietrzak, Leonid Reyzin, Michal Rolínek and Michal Rybár

AsiaCCS 2018

[Synopsis] [Paper]
- Problem: TBF
- Result: TBF

Private Set-Intersection with Common Set-up

with Sanjit Chatterjee and Vikas Kumar

AIMC 2018, 12(1)

[Synopsis] [Paper]
- Problem: TBF
- Result: TBF

Be Adaptive, Avoid Overcommitting

with Zahra Jafargholi, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak and Daniel Wichs

Crypto 2017

[Synopsis] [Paper] [Slides by Ilan] [Talk by Ilan]
- Problem: TBF
- Result: TBF

Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions

with Georg Fuchsbauer, Christian Hanser and Daniel Slamanig

SCN 2016

[Synopsis] [Paper] [Slides]
- Problem: TBF
- Result: TBF

A Closer Look at Multiple-Forking: Leveraging (In)dependence for a Tighter Bound

with Sanjit Chatterjee

Algorithmica 2016, 74(4)

[Synopsis] [Paper] [Slides]
- Problem: TBF
- Result: TBF

From Selective-ID to Full-ID IBS without Random Oracles

with Sanjit Chatterjee

SPACE 2013

[Synopsis] [Paper] [Slides]
- Problem: TBF
- Result: TBF

Galindo-Garcia IBS, Improved

with Sanjit Chatterjee

Preprint, 2012

[Synopsis] [Paper]
- Problem: TBF
- Result: TBF

Galindo-Garcia IBS, Revisited

with Sanjit Chatterjee and Vikas Kumar

ICISC 2012

[Synopsis] [Paper] [Slides]
- Problem: TBF
- Result: TBF

Theses

On the Average-Case Hardness of Total Search Problems

PhD Thesis, 2020

[PDF] [Slides]
Constructing Provably Secure Identity-Based Signature Schemes

Master's Thesis, 2015

[PDF] [Slides]

PCs

TCC 2023

External Reviews

ACNS 2017
Asiacrypt 2014, 2016
Crypto 2017-21, 2023
Eurocrypt 2016-18, 2021, 2023-24
ICITS 2017
ITCS 2020, 2022-23
IWSEC 2012
MFCS 2020
ProvSec 2014
STOC 2020, 2023
TCC 2016-B, 2017, 2020, 2022

Teaching

Undergraduate Cryptography (TU Wien), TA: Fall 2018 and 2019

Cryptographic Hardness in TFNP: Recent Advances

Advances in Total Search Workshop, ICALP 2022

[Slides]
Time-Lock Puzzles

Think and Drink, IST Austria, 2019

[Slides]
Adaptively-Secure Secret Sharing

Czech Academy of Sciences, Prague (Complexity Seminar), 2017

[Slides]
Space-Time Trade-offs

Lecture given as part of a course at IDC, Herzliya, 2017

[Notes]
Learning with Errors

Presented in CS-509 , 2015

[Slides]
The PCP Theorem or How to Catch a Cheat, Efficiently

Presented in Scientific Presentation and Conduct, 2015

[Slides]
Multiple Forking: Deconstructed, Unified

Presented in Asiacrypt 2013 rump session

[Slides]
Schnorr Signature Scheme

Tutorial in E0-335, 2012

[Slides]

Python code for finding the space-complexity of (small) DAGs
- Black Pebbling: Code Sample Input (Skiplist) Output
- Reversible Pebbling:Code Sample Input (Chain) Output
Challenge me on Lichess!
F(O)SS I found useful for work. Drop me an e-mail me if you are aware of better alternatives!
- Xournal++ for taking notes and making slides
  - Sample slides
  - Set-up optimised for me. To use this set-up, add toolbar.ini and palette.gpl files to your local configuration folder.
- Obsidian to keep track of my research (current graph-view)
- Texstudio with MikTeX for writing papers
- qpdfview as a pdf-viewer
Other FOSS I use: Debian 12, Signal, Firefox and Thunderbird.