Research Projects

A computationally hard mathematical problem underlies any public-key cryptosystem. RSA uses integer factorization, while Diffie-Hellman uses discrete log problem. Both are public-key cryptography's foundations. Shor's algorithm makes integer factorization and discrete log problem quantum computationally easy at a time when a fully functional quantum computer is imminent. NIST's Post-Quantum Standardization process aims to create an efficient quantum-secure public-key cryptosystem. Even though there were hundreds of schemes the mathematical problem were mostly two. They are: Learning with Errors Problem (LWE) and Decoding random linear codes. This project will investigate the hardness assumption of these problems from cryptanalytic and complexity-theoretic view. This will clarify the NIST PQC competition and the current NIST-PQC on Digital Signature Schemes competition. LWE problem, proposed by Oded Regev in 2005, and its ring and module (m-LWE) variants are promising candidates for post-quantum public-key schemes. LWE-based schemes are efficient and appealing. NTRU-type cryptosystems, BLISS, GLP, Kyber, and Dilithium are LWE-based. NIST standardised Kyber and Dilithium. NTRU-type schemes choose secret vector and small error as ternary vectors. Kyber and Dilithium choose coefficients from {-3,...,3}. Combinatorial and lattice reduction attacks work against LWE-based schemes. Howgrave-hybrid Graham's attack solves the Ternary LWE problem best. This attack combines the 1996 combinatorial attack of Odlyzko's Meet-in-the-Middle (MitM) and the lattice enumeration. Odlyzko's MitM attack takes $D^.5$, where D is the secret key's search space. May improved this to time complexity $D^.25$. Glaser and May modified this attack for Kyber and Dilithium. May's attack, like Odlyzko's MitM, had huge memory requirements, making them unusable for real-world cryptanalysis. May's Crypto 2021 polynomial memory attack was naive. Our Nested-Collision search strategy improved May's polynomial memory algorithm. We used the same strategy to attack Kyber and Dilithium memorylessly. Our polynomial-memory algorithm ran almost as fast as Odlyzko's MitM. Cryptanalysis requires these memoryless attacks. The Classic McEliece pioneered code-based cryptography as a secure post-quantum scheme. Classic McEliece, BIKE, and HQC are NIST-PQC fourth round code-based crypto candidates. Code-based schemes are more secure than LWE-schemes. Information Set Decoding (ISD) algorithms attack this the best. First ISD was Prange's 1962 polynomial memory algorithm. May, Meurer, and Thomae's 2011 ISD algorithm, which combined Prange's algorithm with the representation technique, gave an improvement. Becker, Joux, May, and Meurer enhanced this in 2012. Designers argue that MMT and BJMM consume huge memory, making them impractical against the schemes. Record computations by Esser, May, and Zweydinger (Eurocrypt 2022) shows that current schemes are very secure if we do not improve SOTA algorithms.