I am an Associate Professor in the Department of Computer Science at NUS, and a Principal Investigaror at CQT. Before joining NUS/CQT, 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.
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
Cryptographers think of me as a theorist, and theorists think of me as a cryptographer. I like to think of myself as a theorist. Perhaps that makes me a cryptographer :)
Open positions:
I am looking for highly motivated PhD students and postdocs interested in all aspects of computational complexity, discrete mathematics, and algorithms. If you are interested, send me an email. These positions come with internationally competitive salaries and generous travel support.
I am always happy to host very strong PhD students for a 2-3 month internship. If you are interested, please write to me. I don't invite undergraduate students for an internship. Undergraduates at NUS interested in research in theoretical computer science are always welcome.
Link to our group research seminar
https://sites.google.com/view/seminar-divesh
Group Members (present and past):
Graduate Students:
Zeyong Li, 2020-present
Rishav Gupta, 2024-present
Saswata Mukherjee, 2024-present
Aditya Morolia, 2024-present
Postdoc:
Pranjal Dutta, 2023-present
Rajeev Raghunath, 2024 - present
Rucha Kulkarni, 2024 - present
Senior Research fellow:
Maciej Obremski, 2018-present
Regular visitors:
Alexander Golovnev
Noah Stephens-Davidowitz
Siyao Guo
Alumni:
Eldon Chung: PhD student, 2020-2024 --> Lecturer, NUS
Rajendra Kumar: PhD student and postdoc, 2019-2022 --> Assistant Professor, IIT Delhi.
Erick Purwanto, PhD student, 2016-2019 --> Teaching fellow, XJTLU
Priyanka Mukhopadhyay, PhD student, 2016-2018 --> postdoc, UToronto
Jianwei Li: Postdoc, 2018-2019
Publications:
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime. [link]
Divesh Aggarwal, Antoine Joux, Miklos Santha, Karol Węgrzycki.
Manuscript.
Improved Lower Bounds for 3-Query Matching Vector Codes. [link]
Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi.
ITCS 2025.Recursive lattice reduction -- A framework for finding short lattice vectors. [link]
Divesh Aggarwal, Thomas Espitau, Spencer Peters, Noah Stephens-Davidowitz.
SOSA 2025.Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. [link]
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen.
In QIP 2022, SICOMP 2024.Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective. [link]
Divesh Aggarwal, Leong Jin Ming, Alexandra Veliche.
TCC 2024.
Quantum Secure Non-malleable codes in the split-state model. [link]
Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain.
In IEEE Transactions of Information Theory, 2024.Quantum Measurement Adversary. [link]
Divesh Aggarwal, Naresh Boddu, Rahul Jain, and Maciej Obremski.
IEEE Transactions of Information Theory, 2024.Unforgeability in Stochastic Gradient Descent. [link]
Teodora Baluta, Ivica Nikolikj, Racchit Jain, Divesh Aggarwal and Prateek Saxena.
ACM CCS 2023.Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms! [link]
Divesh Aggarwal and Rajendra Kumar.
FOCS 2023.Engineering an Efficient Approximate DNF-Counter. [link]
Mate Soos, Divesh Aggarwal, Sourav Chakraborty, Kuldeep S. Meel, Maciej Obremski.
IJCAI 2023.Extractors: Low Entropy Requirements Colliding with Non-malleability. [link]
Divesh Aggarwal, Eldon Chung, Maciej Obremski.
CRYPTO 2023.Lattice Problems Beyond Polynomial Time. [link]
Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan.
STOC 2023.Survey: Non-malleable codes in the split-state model. [link]
Divesh Aggarwal, Marshall Ball, Maciej Obremski.
Entropy 2022.On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing. [link]
Divesh Aggarwal, Eldon Chung, Maciej Obremski, and Joao Ribeiro.
TCC 2022.Privacy Amplification with Tamperable Memory via Non-malleable Two-source Extractors. [link]
Divesh Aggarwal, Maciej Obremski, Joao Ribeiro, Mark Simkin, and Luisa Siniscalchi.
In IEEE Transactions on Information Theory, 2022.Rate One-Third Non-Malleable Codes. [link]
Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, Sruthi Sekar.
STOC 2022.Algebraic Restriction Codes and their Applications. [link]
Divesh Aggarwal, Nico Dottling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, Maciej Obremski.
In ITCS 2022.An Improved Time-Approximation Factor tradeoff for (H)SVP. [link]
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz.
In EUROCRYPT 2021.Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. [link]
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen.
In STACS 2021.A Note on the Concrete Hardness of the Shortest Independent Vectors Problem in Lattices. [link]
Divesh Aggarwal, Eldon Chung.
In Information Processing Letters 2021.Dimension preserving reductions between SVP and CVP in Different p-Norms. [link]
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz.
In SODA 2021.Fine-grained hardness of CVP(P)– Everything that we can prove (and nothing else). [link]
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz.
In SODA 2021.A constant rate non-malleable code in the split-state model. [link]
Divesh Aggarwal, Maciej Obremski.
In FOCS 2020.Extractor Lower Bounds, Revisited. [link]
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz.
In RANDOM 2020.Slide reduction, revisited–Filling the gaps in SVP approximation. [link]
Divesh Aggarwal, Jianwei Li, Phong Nguyen, Noah Stephens-Davidowitz.
In CRYPTO 2020.How to extract useful randomness from unreliable sources. [link]
Divesh Aggarwal, Maciej Obremski, Joao Ribeiro, Luisa Siniscalchi, Ivan Visconti.
In EUROCRYPT 2020.An improved constant in Banaszczyk’s transference theorem. [link]
Divesh Aggarwal and Noah Stephens-Davidowitz.
Manuscript.Stronger Leakage-Resilient and Non-Malleable Secret-Sharing Schemes for General Access Structures.[link]
Divesh Aggarwal, Ivan Damgard, Jesper Buus Nielsen, Maciej Obremski, Erick Purwanto, Joao Ribeiro, and Mark Simkin.
CRYPTO 2019.Continuous Non-Malleable Codes in the 8-Split State Model. [link]
Divesh Aggarwal, Nico Dottling, Jesper Buus Nielsen, Maciej Obremski, and Erick Purwanto.
EUROCRYPT 2019.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.A New Public-Key Cryptosystem via Mersenne Numbers. [link]
Divesh Aggarwal, Antoine Joux, Anupam Parkash, and Miklos Santha.
CRYPTO 2018.Faster Algorithms for SVP and (Approx)-CVP in the Infinity Norm. [link]
Divesh Aggarwal and Priyanka Mukhopadhyay.
ISAAC 2018.Quantum Attacks on Bitcoin, and How to Protect Against Them. [link]
Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel.
Ledger 2018.Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters. [link]
Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski.
ISIT 2018.(Gap/S)ETH Hardness of SVP. [link]
Divesh Aggarwal and Noah Stephens-Davidowitz.
STOC 2018.Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP) [link]
Divesh Aggarwal and Noah Stephens-Davidowitz.
SOSA 2018.Inception makes non-malleable codes stronger [link]
Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski.
TCC 2017.A note on discrete Gaussian combinations of lattice vectors [link]
Divesh Aggarwal and Oded Regev.
In Chicago Journal of Theoretical Computer Science, 2016.Improved hardness results for unique shortest vector problem [link]
Divesh Aggarwal and Chandan Dubey.
In Information Processing Letters 2016.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.Affine-malleable extractors, spectrum doubling, and application to privacy amplification [link]
Divesh Aggarwal, Kaave Hosseini, and Shachar Lovett.
ISIT 2016.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.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.A Note on lower bounds for non-interactive message authentication using weak keys [link]
Divesh Aggarwal and Alexander Golovnev.
ITW 2015.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.Non-malleable reductions and applications [link]
Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski. STOC 2015.Leakage-resilient non-malleable codes [link]
Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski.
TCC 2015.Affine-evasive sets modulo a prime [link]
Divesh Aggarwal.
Information Processing Letters 2015.Amplifying privacy in privacy amplification [link]
Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, and Leonid Reyzin.
CRYPTO 2014.Non-malleable codes from additive combinatorics [link]
Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett.
STOC 2014; Journal version: Siam Journal of Computing, 2018.The leakage-resilience limit of a computational problem is equal to its unpredictability entropy [link]
Divesh Aggarwal and Ueli Maurer.
ASIACRYPT 2011.The equivalence of strong RSA and factoring in the generic ring model of computation [link]
Divesh Aggarwal, Ueli Maurer, and Igor Shparlinski.
WCC 2011.Breaking RSA generically is equivalent to factoring [link]
Divesh Aggarwal and Ueli Maurer.
EUROCRYPT 2009; Journal version: IEEE Transactions on Information Theory, 2017.Algorithms on graphs with small dominating targets [link]
Divesh Aggarwal, Chandan Dubey, and Shashank K. Mehta.
ISAAC 2006.Domination search on graphs with low dominating-target-number [link]
Divesh Aggarwal, Shashank Mehta, and Jitender Deogun.
WG 2005.
Teaching:
Computational Complexity Sem 2, 2017-18, 2018-19, 2022-23
Introduction to Information Theory Sem 2, 2016-17, 2021-22
Pseudorandomness Sem 1, 2018-19
Design and Analysis of Algorithms Sem 1, Sem 4, 2019-20, Sem 1, 2020-21
Analysis of Boolean Functions. Sem 2, 2022-23
Introduction to Quantum Computing Sem 2, 2023-24, 2024-25
Advanced Algorithms Sem 1, 2024-25
Professional Activities:
Program Committee: TCC 2016-B, SCN 2016, ICITS 2016, ICITS 2017, TCC 2018, SPACE 2018, Indocrypt 2019, NuTMIC 2019, Eurocrypt 2020, SCN 2020, ITC 2021, CRYPTO 2021, ANTS 2022, Asiacrypt 2022, FSTTCS 2022, AQIS 2023, PKC 2024, ITC 2024 (chair), EUROCRYPT 2025.
Editorial Board: Information Processing Letters (February 2021-present)
Organizing Committee: TCC 2010, AQIS 2018.
Contact Information:
1. Centre of Quantum Technologies
S15 #04-12
National University of Singapore
Block S15, 3 Science Drive 2
Singapore 117543
2. School of Computing
COM3 #02-09
11 Research Link
Singapore 119391
Phone: +65 6516 5628 (office)
+65 6516 2911 (office)
Email: divesh@comp.nus.edu.sg
divesh.aggarwal@gmail.com