Divesh Aggarwal                             
      


                                                                                     
                                                                                                         
                                                                                                                     
                                                                                                        
                                                                                                                    
I am an Assistant Professor in the Department of Computer Science at NUS, and a Principal Investigaror at CQT since August, 2016. Before this, I was a post-doctoral researcher for two years each in the School of Computer and Communication Sciences at EPFL, and the Department of Computer Science at New York University. I completed my PhD under the guidance of Prof. Ueli Maurer at ETH Zurich in February, 2012. 

Recently, I have accepted some PhD students, and I am not looking for any new PhD students in the near future. So, unless you are truly exceptional, please don't consider applying for a PhD position. I am happy to invite exceptional graduate students for an internship position. If you are interested, write to me. I don't have internship positions for undergraduate students unless you are an undergraduate student from NUS, in which case write to me to schedule a meeting and discuss.


Contact Information:
   Address: 
   1. Centre of Quantum Technologies
       S15 #04-12
       National University of Singapore
       Block S15, 3 Science Drive 2
       Singapore 117543
   2. School of Computing
       COM2 #02-02
       15 Computing Drive
       Singapore 117418
   Phone:   +65 6516 5628 (office)
               +65 6516 2911 (office)
               +65 9272 9378 (mobile)
   Email:   divesh@comp.nus.edu.sg
                divesh.aggarwal@gmail.com

Research Interests:
Broadly speaking, I am interested in discrete structures and their applications in theoretical computer science. In particular, I am interested in the following:
  •  Information-theoretic Cryptography
  •  Randomness Extractors and Applications
  •  Lattices in Computer Science
  •  Coding Theory
  •  Computational number theory

Group Members:

I am extremely proud of my awesome group members.

Research group:
  • Eldon Chung, PhD student
  • Zeyong Li, PhD student
  • Rajendra Kumar, PhD student, joint with Manindra Agrawal
  • Maciej Obremski, Senior Research Fellow

Regular visitors:
  • Noah Stephens-Davidowitz (Visiting Senior Research Fellow)
  • Siyao Guo (Visiting Senior Research Fellow)
  • Joao Ribeiro (Visiting Student)

Alumni:
  • Priyanka Mukhopadhyay, PhD student, joint with Rahul Jain (2016-2019)
  • Erick Purwanto, PhD student (2016-2019)
  • Jianwei Li, postdoc (2019-2020)

Publications:


  1. Two-Source Non-Malleable Extractors and Applications to Privacy Amplification with Tamperable Memory. [link]
    Divesh AggarwalMaciej ObremskiJoao RibeiroMark Simkin, and Luisa Siniscalchi
    In submission. 

  2. An Improved Time-Approximation Factor tradeoff for (H)SVP. [link]
    Divesh Aggarwal, Zeyong Li, and Noah Stephens-Davidowitz.
    EUROCRYPT 2021. 

  3. Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. [link]
    Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen.
    STACS 2021. 

  4. An improved constant in Banaszczyk's transference theorem. [link]
    Divesh Aggarwal and Noah Stephens-Davidowitz.
    Manuscript. 

  5. A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices. [link]
    Divesh Aggarwal and Eldon Chung.
    Information Processing Letters, 2021.

  6. Dimension preserving reductions between SVP and CVP in Different p-Norms. [link]
    Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz.
    SODA 2021.

  7. Fine-grained hardness of CVP(P)-- Everything that we can prove (and nothing else). [link]
    Divesh Aggarwal, Huck BennettAlexander Golovnev, and Noah Stephens-Davidowitz.
    SODA 2021.

  8. A constant rate non-malleable code in the split-state model. [link]
    Divesh Aggarwal and Maciej Obremski.
    FOCS 2020.

  9. Extractor Lower Bounds, Revisited. [link] 
    Divesh Aggarwal, Siyao GuoMaciej ObremskiJoao Ribeiro, and Noah Stephens-Davidowitz.
    RANDOM 2020.

  10. Slide reduction, revisited–Filling the gaps in SVP approximation. [link]
    Divesh Aggarwal, Jianwei Li, Phong Nguyen, and Noah Stephens-Davidowitz.
    CRYPTO 2020.

  11. How to extract useful randomness from unreliable sources. [link]
    Divesh Aggarwal
    Maciej ObremskiJoao Ribeiro, Luisa Siniscalchi, and Ivan Visconti.
    EUROCRYPT 2020.

  12. Faster Sieving Algorithm for Approximate SVP with Constant Approximation Factors. [link]
    Divesh Aggarwal, Bogdan Ursu, and Serge Vaudenay.
    Manuscript.

  13. Stronger Leakage-Resilient and Non-Malleable Secret-Sharing Schemes for General Access Structures. [link]
    Divesh Aggarwal, Ivan DamgardJesper Buus NielsenMaciej Obremski, Erick Purwanto, Joao Ribeiro, and Mark Simkin.
    CRYPTO 2019.

  14. Continuous Non-Malleable Codes in the 8-Split State Model. [link]
    Divesh Aggarwal, Nico Döttling, Jesper Buus NielsenMaciej Obremski, and Erick Purwanto.
    EUROCRYPT 2019.

  15. A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Quantum Adversaries. [link]
    Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, and Thomas Vidick.
    EUROCRYPT 2019.

  16. Quantum Attacks on Bitcoin, and How to Protect Against Them. [link]
    Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel.
    Ledger 2018. 

  17. Faster Algorithms for SVP and (Approx)-CVP in the Infinity Norm. [link]
    Divesh Aggarwal and Priyanka Mukhopadhyay.
    ISAAC 2018.

  18. A New Public-Key Cryptosystem via Mersenne Numbers. [link]
    Divesh Aggarwal, Antoine JouxAnupam Parkash, and Miklos Santha.
    CRYPTO 2018.

  19. Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters. [link]
    Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski.
    ISIT 2018.

  20. (Gap/S)ETH Hardness of SVP. [link]
    Divesh Aggarwal and Noah Stephens-Davidowitz.
    STOC 2018.

  21. Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP) [link]
    Divesh Aggarwal and Noah Stephens-Davidowitz.
    SOSA 2018.

  22. Inception makes non-malleable codes stronger [link]
    Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski.
    TCC 2017. 

  23. A note on discrete Gaussian combinations of lattice vectors [link]
    Divesh Aggarwal and Oded Regev.  
    In Chicago Journal of Theoretical Computer Science, 2016

  24. Improved hardness results for unique shortest vector problem [link]
    Divesh Aggarwal and Chandan Dubey.
     
    In Information Processing Letters 2016.

  25. Revisiting the Sanders-Bogolyubov-Ruzsa Theorem in F_p^n and its Application to Non-malleable Codes [link]
    Divesh Aggarwal and Jop Briët.
    ISIT 2016.

  26. Affine-malleable extractors, spectrum doubling, and application to privacy amplification [link]
    Divesh Aggarwal, Kaave Hosseini, and Shachar Lovett.
    ISIT 2016. 

  27. Optimal computational split-state non-malleable codes [link]
    Divesh Aggarwal, Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran.
    TCC 2016-A. 

  28. Solving the Closest Vector Problem in 2^n Time --- the discrete Gaussian strikes again! [link]
    Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz
    FOCS 2015

  29. A Note on lower bounds for non-interactive message authentication using weak keys [link]
    Divesh Aggarwal and Alexander Golovnev.
    ITW 2015. 

  30. Solving the Shortest Vector Problem in 2^n time via discrete Gaussian sampling [link] 
    Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz.
    STOC 2015. 

  31. Non-malleable reductions and applications [link] 
    Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski.
    STOC 2015. 

  32. Leakage-resilient non-malleable codes [link] 
    Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski.
    TCC 2015 

  33. Affine-evasive sets modulo a prime [link]
    Divesh Aggarwal.
    Information Processing Letters 2015.

  34. Amplifying privacy in privacy amplification [link]
    Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, and Leonid Reyzin.
    CRYPTO 2014. 

  35. Non-malleable codes from additive combinatorics [link
    Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett.
    STOC 2014; Journal version: Siam Journal of Computing, 2018.

  36. The leakage-resilience limit of a computational problem is equal to its unpredictability entropy [link]
    Divesh Aggarwal and Ueli Maurer.
     
    ASIACRYPT 2011. 

  37. The equivalence of strong RSA and factoring in the generic ring model of computation [link]
    Divesh Aggarwal, Ueli Maurer, and Igor Shparlinski
    WCC 2011. 

  38. Breaking RSA generically is equivalent to factoring  [link]
    Divesh Aggarwal and Ueli Maurer.
    EUROCRYPT 2009
    ; Journal version: IEEE Transactions on Information Theory, 2017.

  39. Algorithms on graphs with small dominating targets [link]
    Divesh Aggarwal, Chandan Dubey
    , and Shashank K. Mehta.
    ISAAC 2006


  40. Domination search on graphs with low dominating-target-number [link]
    Divesh Aggarwal, Shashank Mehta, and Jitender Deogun
    WG 2005

Teaching experience:

Instructor:
  • Design and Analysis of Algorithms           2019                       
  • Computational Complexity                      2018, 2019              
  • Pseudorandomness                                2018                       
  • Introduction to Information Theory          2017                      

Professional Activities:
Program Committee: TCC 2016-B, SCN 2016, ICITS 2016, ICITS 2017, TCC 2018, SPACE 2018, NuTMIC 2019, Indocrypt 2019, Eurocrypt 2020, SCN 2020, CRYPTO 2021, ITC 2021. 
Reviewed several papers for: STOC, FOCS, SODA, CCC, ICALP, Crypto, Eurocrypt, FSTTCS, ISAAC, TCC, Asiacrypt, Africacrypt, PKC, CT-RSA, SCN, Discrete Mathematics, Theoretical Computer Science, Journal of Cryptology, Designs Codes and Cryptography, IEEE Transactions of Information Theory