Chethan Kamath

Short Bio

I am a post-doc at Tel Aviv University, hosted by Nir Bitansky and Omer Paneth and supported by an Azrieli fellowship.

• Nov 2020-Mar 2021: Post-doc with Pavel Hubáček at Charles University
• Mar-Aug 2020: Post-doc with Daniel Wichs at Northeastern university
• 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. The 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).

Research Interests

Publications

1. On Treewidth, Separators and Yao’s Garbling
   with Karen Klein and Krzysztof Pietrzak
   TCC 2021, to appear
   [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, we show that it is secure in the -- next-best -- indistinguishability-based model for some circuit classes like \(\mathbf{NC}^1\). To this end, we use tools from algorithmic graph theory (e.g., treewidth) and circuit complexity.
   
   
   
2. Limits on the Adaptive Security of Yao’s Garbling
   with Karen Klein, Krzysztof Pietrzak and Daniel Wichs
   Crypto 2021
   [Synopsis] [Paper] [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.
   
   
   
3. On the Cost of Adaptivity in Security Games on Graphs
   with Karen Klein, Krzysztof Pietrzak and Michael Walter
   TCC 2021, to appear
   [Synopsis] [Paper] [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.
   
   
   
4. 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] [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).
   
   
   
5. 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] [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 simplest assumption in cryptography?
   Result: For a restricted class of black-box reductions, we show that this is not possible.
   
   
   
6. Finding a Nash Equilibrium is no Easier than Breaking Fiat-Shamir
   with Arka Rai Choudhary, 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 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 CLS \(\subseteq\) PPAD.
   
   
   
7. PPAD-Hardness via Iterated Squaring Modulo a Composite
   with Arka Rai Choudhary, Pavel Hubáček, Krzysztof Pietrzak, Alon Rosen and Guy Rothblum
   Eprint 2019
   [Synopsis] [Paper]
   
   
   Problem: How hard is the complexity class 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 CLS \(\subseteq\) PPAD.
   Remark: The results in the paper are superseded by [13].
   
   
   
8. 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) 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.
   
   
   
9. 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].
   
   
   
10. 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
    
    
    
11. Private Set-Intersection with Common Set-up
    with Sanjit Chatterjee and Vikas Kumar
    AIMC 2018, 12(1)
    [Synopsis] [Paper]
    
    
    Problem: TBF
    Result: TBF
    
    
    
12. Be Adaptive, Avoid Overcommitting
    with Zahra Jafargholi, Karen Klein, Ilan Komargodski, Krzysztof Pietrzak and Daniel Wichs
    Crypto 2017
    [Synopsis] [Paper] [Talk by Ilan]
    
    
    Problem: TBF
    Result: TBF
    
    
    
13. 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
    
    
    
14. 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
    
    
    
15. 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
    
    
    
16. From Selective-ID to Full-ID IBS without Random Oracles
    with Sanjit Chatterjee
    SPACE 2013
    [Synopsis] [Paper] [Slides]
    
    
    Problem: TBF
    Result: TBF
    
    
    
17. Galindo-Garcia IBS, Improved
    with Sanjit Chatterjee
    Preprint
    [Synopsis] [Paper]
    
    
    Problem: TBF
    Result: TBF
    
    
    
18. Galindo-Garcia IBS, Revisited
    with Sanjit Chatterjee and Vikas Kumar
    ICISC 2012
    [Synopsis] [Paper]
    
    
    Problem: TBF
    Result: TBF
    
    
    

External Reviews

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

Internships/Visits

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

Misc.

• On the Average-Case Hardness of Total Search Problems (PDF Slides)
  PhD Thesis
  
  
• Python code for finding the space-complexity of (small) DAGs
  Black Pebbling: Code Sample Input (Skiplist) Output
  Revsersible Pebbling:Code Sample Input (Chain) Output
  
  
• Time-Lock Puzzles (Slides)
  Think and Drink, IST Austria
  
  
• Adaptively-Secure Secret Sharing (Slides)
  Talk given at Czech Academy of Sciences, Prague (Complexity Seminar)
  
  
• Space-Time Trade-offs (Notes)
  Lecture given as part of a course at IDC, Herzliya
  
  
• Schnorr Signature Scheme (Slides)
  Tutorial in E0-335
  
  
• Learning with Errors (Slides)
  Presented in CS-509
  
  
• The PCP Theorem or How to Catch a Cheat, Efficiently (Slides)
  Presented in Scientific Presentation and Conduct
  
  
• Constructing Provably Secure Identity-Based Signature Schemes (PDF Slides)
  Master's Thesis
  
  
• Multiple Forking: Deconstructed, Unified (Slides)
  Presented in Asiacrypt'13 rump session