Divesh AGGARWAL

Assistant Professor
Ph.D. (Computer Science, ETH Zurich)
M.Sc. (Integrated Mathematics & Scientific Computing, Indian Institute of Technology, Kanpur)
COM2-02-02
651 62911

Research Areas

  • Algorithms & Theory
  • Security

Research Interests

  • Lattices: Algorithms and Complexity
  • Pseudorandomness
  • Cryptography
  • Coding Theory
  • Algorithms for Hard Problems

Profile

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.

Current Projects

Selected Publications

  • Inception makes non-malleable codes stronger 
    Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski.
    TCC 2017. 

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

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

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

  • Non-malleable reductions and applications
    Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski. 
    STOC 2015.  

  • Affine-evasive sets modulo a prime 
    Divesh Aggarwal. 
    Information Processing Letters 2015.

  • Amplifying privacy in privacy amplification 
    Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, and Leonid Reyzin. 
    CRYPTO 2014. 

  • 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

Teaching (2019/2020)

  • CS3230: Design and Analysis of Algorithms