• 2024- Assistant Professor at IIT Bombay
• 2021-2023 Post-doc at Tel Aviv University, hosted by Nir Bitansky and Omer Paneth
  • I was 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 IISc Bangalore, under the supervision 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).

SHORT-TERM VISITS

• Simons Institute - Summer 2015
  
• FACT Center - Summer 2017, hosted by Alon Rosen
  
• Charles University, Prague - October 2017, 2019, July 2022, hosted by Pavel Hubáček
  

---

1. Titan: Efficient Polynomial Commitments from IOPs over Groups

   with Ravi Prakash, Samipa Samanta, Sruthi Sekar and Nitin Singh

   CCS 2026, to appear

   [+] Synopsis [↗] Paper [↗] Code
   

   • Problem: Polynomial Commitment Scheme (PCS) is a key ingredient to constructing efficient SNARKs. While hash-based PCSs (e.g., WHIR) have low prover and verifier complexity, their proof size is usually large. On the other hand, pairing-based SNARKs (e.g., Dory) have short proofs, but their prover and verifier complexity is high. Can we get a PCS that is the best of both worlds?
   • Result: In this work, we propose Titan which achieves this.




2. Separating Verifiable Delay Functions and Time-Lock Puzzles

   with Hamza Abusalah, Nivesh Aggarwal, Karen Azari, and Maximilian von Consbruch

   Eurocrypt 2026

   [+] Synopsis [↗] Paper [↓] Slides by Max and Nivesh
   

   • Problem: We continue with the problem posed in [26], where we showed that a weak form of VDF can be constructed from TLP using heavy machinery.
   • Result: In this work, we show that (oracle-aided) VDFs cannot be constructed from TLPs and vice versa, and thus the limitations of [26] is inherent. To this end, we rely on the techniques from [27].




3. Impossibility of VDFs in the ROM: The Complete Picture

   with Hamza Abusalah, Karen Azari, Erkan Tairi and Maximilian von Consbruch

   Eurocrypt 2026

   [+] Synopsis [↗] Paper [↓] Slides [↓] Slides by Max
   

   • Problem: Can Verifiable Delay Function (VDF) be constructed in the Random-Oracle Model) (ROM)?
   • Result: Prior works [MSW20,GRY25] ruled out ROM-based computationally-unique VDFs with public setup. We complete the picture set forth by these works by ruling out ROM-based computationally-unique VDFs even with expensive private setup.




4. On Verifiable Delay Functions from Time-Lock Puzzles

   with Hamza Abusalah, Karen Azari, Dario Fiore and Erkan Tairi

   PKC 2026

   [+] Synopsis [↗] Paper [↓] Slides by Erkan
   

   • Problem: Time-Lock Puzzles (TLPs) and verifiable delay functions (VDFs) are two central objects in timed cryptography. Constructions of TLP and VDF out there show superficial similarities: e.g., Pietrzak's and Wesolowski's constructions of VDF are essentially the Rivest-Shamir-Wagner TLP made publicly-verifiable. This begs the natural question: can one object be constructed from the other in a black-box manner?
   • Result: The problem turns out highly non-trivial! In this work, we are able to construct a one-time VDF from TLP, but using the heavy hammer of indistinguishability obfuscation.




5. Securely Instantiating 'Half Gates' Garbling in the Standard Model

   with Anasuya Acharya, Karen Azari, Mirza Ahad Baig and Dennis Hofheinz

   PKC 2025

   [+] Synopsis [↗] Paper [↓] Slides by Anu
   

   • Problem: The problem statement is related to that in [24]. Even though we showed that Half Gates cannot be adaptively secure in the plain model, can it be shown selective secure there? Prior results show selective security in idealised model, and this boils down constructing so-called "circular and correlation-robust" (CCR) hash function.
   • Result: In this work, we show how to instantiate CCR hash function in the plain model using indistinguishability obfucation and injective one-way functions.




6. On the Adaptive Security of Free-XOR-based Garbling Schemes in the Plain Model

   with Anasuya Acharya and Karen Azari

   Eurocrypt 2025

   [+] Synopsis [↗] Paper [↓] Slides by Karen [↗] Talk by Karen
   

   • Problem: A common optimisation applied to Yao's garbling scheme is the so-called FreeXOR technique, which allows skipping the garbling table for XOR gates. While selective security of FreeXOR-based schemes is well-studied (e.g., here) in the plain model (i.e., no idealised assumptions), not much is known about its adaptive security (where the adversary gets to see a garbled circuit before choosing its input).
   • Result: Building on [18], we show barriers against adaptive security of FreeXOR based schemes in the plain model. In particular, we show it is not possible to lift selective security of several popular schemes (such as Two Halves garbling) to adaptive security while avoiding an exponential loss in security.




7. Batch Proofs are Statistically Hiding

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

   STOC 2024

   [+] 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.




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




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




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




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




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




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




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




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




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




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




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




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




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




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




22. Private Set-Intersection with Common Set-up

    with Sanjit Chatterjee and Vikas Kumar

    AIMC 2018, 12(1)

    [+] Synopsis [↗] Paper

    • Problem: TBF
    • Result: TBF




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




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




25. On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model

    with Joël Alwen, Binyi Chen, Vladimir Kolmogorov, Krzysztof Pietrzak and Stefano Tessaro

    Eurocrypt 2016

    [+] Synopsis [↗] Paper [↗] Talk by Binyi

    • Problem: TBF
    • Result: TBF




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




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

    with Sanjit Chatterjee

    SPACE 2013

    [+] Synopsis [↗] Paper [↓] Slides

    • Problem: TBF
    • Result: TBF




28. Galindo-Garcia IBS, Improved

    with Sanjit Chatterjee

    Preprint, 2012

    [+] Synopsis [↓] Paper

    • Problem: TBF
    • Result: TBF




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

---

PC

• AsiaCCS 2026
• Asiacrypt 2025, 2026
• ICISS 2024
• Indocrypt 2026
• MARBLE 2025
• TCC 2023

EXTERNAL REVIEW

• ACNS 2017
• Asiacrypt 2014, 2016, 2024
• Crypto 2017-21, 2023-26
• Eurocrypt 2016-18, 2021, 2023-25
• FOCS 2026
• ICITS 2017
• ITCS 2020, 2022-24, 2026
• IWSEC 2012
• MFCS 2020
• PKC 2026
• ProvSec 2014
• STOC 2020, 2023
• TCC 2016-B, 2017, 2020, 2022, 2024-25

ORGANISING

• With Venkata Koppula and on behalf of Trust Lab, I co-organised the school Introduction to Cryptography, as part of ACM India Summer School 2025.
• With Manoj Prabhakaran and Sruthi Sekar, and on behalf of Trust Lab, I co-organised the school Theoretical Foundations of Cryptography, as part of ACM India Summer School 2024.

TALKS

1. Impossibility of VDFs in the ROM: The Complete Picture

   IITM CyStar Crypto Meet 2025 and IITH CCS Conclave 2026

   [↓] Slides

2. Timed Cryptography. Or: How Skynet Rescued ChatGPT and All Her Friends

   Faculty Unplugged Seminar Series, April 2024

   [↓] Slides

3. Cryptographic Hardness in TFNP: Recent Advances

   Advances in Total Search Workshop, ICALP 2022

   [↓] Slides

4. Total Puzzles and Cryptography

   Azrieli Postdoc and Faculty Fellows 1st Conference

   [↓] Slides

5. Time-Lock Puzzles

   Think and Drink, IST Austria, 2019

   [↓] Slides

6. Adaptively-Secure Secret Sharing

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

   [↓] Slides

7. Space-Time Trade-offs

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

   [↓] Notes

8. Learning with Errors

   Presented in CS-509, 2015

   [↓] Slides

9. The PCP Theorem or How to Catch a Cheat, Efficiently

   Presented in Scientific Presentation and Conduct, 2015

   [↓] Slides

10. Multiple Forking: Deconstructed, Unified

    Presented in Asiacrypt 2013 rump session

    [↓] Slides

11. Schnorr Signature Scheme

    Tutorial in E0-335, 2012

    [↓] Slides

---

CURRENT/PAST STUDENTS
Following is the list of students I have worked with, usually co-guided with Manoj Prabhakaran and/or Sruthi Sekar.

PhD

• Bhavadharini V, 2025s-
• Samipa Samanta, 2024a-

MS(R)

• Ragav R, 2025s-
• Ravi Prakash, 2024s-
• Priyanshu Singh, 2024s-

Pre-Doc

• Agni Dutta, 2025a-2026s → PhD@University of Edinburgh
• Adwaiya Srivastav, 2024a-
• Bhavadharini V, 2024a-2025a → PhD@IIT Bombay
• Archisman Dutta, 2024s-25s → PhD@Aarhus University

PROSPECTIVE STUDENTS

I am keen to work with undergrads and interns. We, at Trust Lab, are also hiring MS/PhD students and post-docs. If you are one of the above, please read the following carefully and then drop me an e-mail. If you are:

• a non-IITB undergrad looking for short-term internship, consider applying to Trust Lab's summer internship program.
• a recent graduate looking for a long-term research internship, consider applying to Trust Lab's pre-doctoral program.
• looking to apply for MS/PhD positions, please apply via CSE PG admission page.
• looking to do a post-doc, write to me directly.

When writing me an e-mail, make sure to prefix (exactly) the subject line with the text in this picture (I won't read the e-mail otherwise). Also, please keep your e-mail terse -- don't include machine-generated content (I have learned from the master himself to identify such e-mails).

Openings

• Our group is actively looking for MS and PhD students. If you are interested, please drop me an e-mail and apply in the next cycle
• Application for Trust Lab pre-doc positions are rolling. Drop me an e-mail before you apply

---

The following is the list of courses I have offered at IITB. I maintain the course material on CSE GitLab. Feel free to contribute/provide feedback.

• CS409m -- Introduction to Cryptography (Minor): Autumn'26, Autumn'25
• CS758 -- Advanced Tools from Modern Cryptography: Spring'26 (Lattices and Lattice-Based Cryptography)
• CS789 -- Introduction to Probabilistic Proof Systems: Spring'27, Spring'25
• CS783 -- Theoretical Foundations of Cryptography: Autumn'24

TA

• Undergraduate Cryptography (TU Wien): Fall 2018 and 2019

---

• The code I use for batch-defining \(\LaTeX\) macros is maintined here. The code is useful for writing TCS papers. An MWE and source code can be found below.
  • Minimal working example
  • Source code
• Python code for finding the space-complexity of (small) DAGs
  

  • Black Pebbling: Code, Sample Input (Skiplist) and Output
  • Reversible Pebbling: Code, Sample Input (Chain) and 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 as LaTeX editor
• Other FOSS I use: Debian 13, Signal, Firefox and Thunderbird.
• The design of this website is inspired by Yashwanth Kondi's and Cure53's. You can download a minimal template (with instructions) here.

---

• E-mail: ckamath at cse dot iitb dot ac dot in
• Warning: I don't use GMail/WhatsApp: if you receive an e-mail/text claiming it is me, beware!
• Office: Room 305, New CSE Building, CSE Department, IIT Bombay
  
  
  View Larger Map