Chethan Kamath

Display Picture

I am an assistant professor at the CSE department at IIT Bombay, where I am a member of the Theory Group and Trust Lab. My primary field of research is cryptography, particularly its foundations. But my interests extend beyond to theoretical computer science

[+]

BIO


[+]

RESEARCH


Publications

  1. Batch Proofs are Statistically Hiding
    with Nir Bitansky, Omer Paneth, Ron Rothblum and Prashant Nalini Vasudevan
    STOC 2024, to appear
    [+] 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.

  2. (Verifiable) Delay Functions from Lucas Sequences
    with Charlotte Hoffmann, Pavel Hubáček and Tomáš Krňák
    TCC 2023
    [+] Synopsis [↗] Paper [↓] Slides by Tomáš [↗] Talk by Tomáš
    • 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.

  3. 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.

  4. 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}\).

  5. 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.

  6. 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.

  7. 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

  8. 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.

  9. 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).

  10. 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

  11. 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}\).

  12. 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].

  13. 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.

  14. 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].

  15. 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

  16. Private Set-Intersection with Common Set-up
    with Sanjit Chatterjee and Vikas Kumar
    AIMC 2018, 12(1)
    [+] Synopsis [↗] Paper
    • Problem: TBF
    • Result: TBF

  17. 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

  18. 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

  19. 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

  20. From Selective-ID to Full-ID IBS without Random Oracles
    with Sanjit Chatterjee
    SPACE 2013
    [+] Synopsis [↗] Paper [↓] Slides
    • Problem: TBF
    • Result: TBF

  21. Galindo-Garcia IBS, Improved
    with Sanjit Chatterjee
    Preprint, 2012
    [+] Synopsis [↗] Paper
    • Problem: TBF
    • Result: TBF

  22. 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

Internships/Short-term visits

PCs

External Reviews

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

TALKS


[+]

TEACHING


  • Undergraduate Cryptography (TU Wien), TA: Fall 2018 and 2019
[+]

ETC.


[+]

CONTACT


  • E-mail: ckamath at cse dot iitb dot ac dot in
  • Office: Room 305, New CSE Building, CSE Department, IIT Bombay


    View Larger Map