I am a postdoctoral researcher in Weizmann Institute of Science, advised by Zvika Brakerski. My research primarily focuses on studying the lattice problems to analyze the security of lattice-based cryptosystems. I am broadly interested in theoretical computer science and cryptography.
I completed my Ph.D. under the Joint degree programme of Indian Institute of Technology, Kanpur and National University of Singapore, advised by Professors Manindra Agrawal and Divesh Aggarwal. Before coming to Weizmann Institute, I was a research fellow at Center for Quantum Technologies, NUS.
Email id: rajendra.kumar@weizmann.ac.il
Recent News:
Our paper on "Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms" is accepted to FOCS-23.
Our paper on "Lattice Problems Beyond Polynomial Time" is accepted to STOC-23.
Paper on Barrier for SETH-hardness of CVP in even norm is up on arXiv. Check out the draft.
D. Aggarwal, H. Bennett, A. Golovnev, N. Stephens-Davidowitz and I are organizing a workshop on "Fine-grained Cryptography" at IIT Madras (part of FSTTCS22 pre-conference workshops) on 17th Dec 2022.
Faster Quantum Algorithm for SVP in QRAM. Check out the draft. Presented at QIP 2022. [Video]
Research Papers:
QSETH strikes again: finer quantum lower bound for lattice problem, strong simulation, hitting set problem and more.
with Yanlin Chen, Yilei Chen, Subhasree Patro, Florian Speelman
In Submission
[PDF]
Lattice Problems in General Norms: Algorithms with Explicit Constants, Dimension-Preserving Reductions, and More.
with Huck Bennett, Yanlin Chen, Zeyong Li, and Spencer Peters.
In Submission.
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms, and of the Subset Sum Problem!
with Divesh Aggarwal.
64th Annual Symposium on Foundations of Computer Science, FOCS, 2023.
[PDF]
Lattice Problems Beyond Polynomial Time.
with Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz and Vinod Vaikuntanathan.
55th ACM Symposium on Theory of Computing, STOC, 2023.
[PDF]
Covert Authentication from Lattices.
with Khoa Nguyen.
20th International Conference on Applied Cryptography and Network Security, ACNS, 2022.
[PDF]
Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding.
with Divesh Aggarwal, Yanlin Chen and Yixin Shen.
Contributed talk at the 25th Conference on Quantum Information Processing, QIP, 2022.
Extended version of STACS 2021 paper with major differences.
Dimension-Preserving Reductions Between SVP and CVP in Different p-Norms.
with Divesh Aggarwal, Yanlin Chen, Zeyong Li and Noah Stephens-Davidowitz.
ACM-SIAM Symposium on Discrete Algorithms, SODA, 2021.
[PDF] [Video@CQT] [Video@SIGTACS, IITK]
- Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding.
with Divesh Aggarwal, Yanlin Chen and Yixin Shen.
38th International Symposium on Theoretical Aspects of Computer Science, STACS, 2021.
[PDF]
Invited to TOCS Special Issue for STACS 2021 (regretfully declined ).
Hardness of Approximation of (Multi-)LCS over Small Alphabet.
with Amey Bhangale and Diptarka Chakraborty.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, 2020.
Cryptanalysis of 2-round KECCAK-384.
with Nikhil Mittal and Shashank Singh.
19th International Conference on Cryptology in India, INDOCRYPT, 2018.
[PDF]
Cryptanalysis of 1-round KECCAK.
with Mahesh Sreekumar Rajasree and Hoda AlKhzaimi.
10th International Conference on Cryptology in Africa, AFRICACRYPT, 2018.
[PDF]
Maximum Distance Sub-Lattice Problem.
with Shashank K Mehta and Mahesh Sreekumar Rajasree.
[PDF]
Professional Service:
Reviewed papers for TCC-2018 , CCC-2020, ANTS-2020, EUROCRYPT-2021, ITC-2021, ISIT-2021, CRYPTO-2021, QIP-2022, STOC-2022, TQC-2022, ICALP-2022, ESA-2022, QCRYPT-2022, ASIACRYPT-2022, FSTTCS-2022, ICALP-2023, TQC-2023, STOC-2023, FOCS-2023, SODA-2024.