Divesh AGGARWALAssistant Professor
Ph.D. (Computer Science, ETH Zurich)
M.Sc. (Integrated Mathematics & Scientific Computing, Indian Institute of Technology, Kanpur)
- Algorithms & Theory
- Lattices: Algorithms and Complexity
- Coding Theory
- Algorithms for Hard Problems
Divesh Aggarwal has received Ph.D. degree in Computer Science from ETH Zurich in 2012. From 2012 to 2016, he spent two years each as a postdoctoral researcher at New York University and at EPFL. Since 2016, he is an Assistant Professor in the Department of Computer Science, and a Principal Investigator in the Centre for Quantum Technologies at the National University of Singapore. His current research revolves around the following two themes. 1. Post-quantum cryptography has recently gained interest since people are now really fearing that quantum computers could be a reality. There have been several cryptosystems that have been constructed and their security is based on the hardness of different problems like LWE, Ring-LWE, solving multivariate polynomial equations. While these cryptosystems have so far resisted any classical or quantum attacks, it cannot be excluded that such attacks are possible in the future. In particular, there is no unifying complexity-theoretic assumption (like NP-hardness) that relates the difficulty of breaking all these cryptosystems. Thus, it is desirable to both come up with promising new proposals for public-key cryptosystems, and to study whether there are other classical/quantum attacks on the existing cryptosystems. His research aims to make progress in both these directions. 2. Randomization has proved to play a very important role in many areas of computer science. Randomized algorithms are designed under the assumption that the computer has access to perfectly random and independent bits (i.e., a sequence of unbiased coin tosses). In practice this sequence is generated from some physical source of randomness like electromagnetic noise or biometrics. While these sources have some inherent randomness in the sense that they have entropy, a sample from such sources does not contain independent random bits. The goal of transforming these imperfect random sources into perfectly random bits has, over the last few decades, led to a large body of research on the theory of randomness extractors. Also, more recently, other extractors have been introduced and constructed in the literature which satisfy enhanced properties. An example of such an extractor is a non-malleable extractor, which are seeded or multi-source extractors with the additional property that the output has limited or no relation to the output of the extractor for a related source/seed. These extractors have found applications in classical areas like privacy amplification, and tamper-resilient cryptography. Some of my recent research centers around improving construction of such non-malleable extractors in various settings that are useful in practice.
Inception makes non-malleable codes stronger
Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski.
Affine-malleable extractors, spectrum doubling, and application to privacy amplification
Divesh Aggarwal, Kaave Hosseini, and Shachar Lovett.
Solving the Closest Vector Problem in 2^n Time --- the discrete Gaussian strikes again!
Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz.
Solving the Shortest Vector Problem in 2^n time via discrete Gaussian sampling
Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz.
Non-malleable reductions and applications
Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski.
Affine-evasive sets modulo a prime
Information Processing Letters 2015.
Amplifying privacy in privacy amplification
Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, and Leonid Reyzin.
Non-malleable codes from additive combinatorics
Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett.
STOC 2014; Journal version: Siam Journal of Computing, 2018.
Breaking RSA generically is equivalent to factoring
Divesh Aggarwal and Ueli Maurer.
EUROCRYPT 2009; Journal version: IEEE Transactions on Information Theory, 2017.
Awards & Honours
- CS3230: Design and Analysis of Algorithms