Seminars

View all Seminars  |  Download ICal for this event

Applications of Dedekinds Index Theorem to Lattice-based Cryptography

Series: Department Seminar

Speaker: Charanjit S. Jutla IBM T. J. Watson Research Center Yorktown Heights, NY

Date/Time: Dec 14 15:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
Computationally hard problems on integer lattices, such as shortest vector problem (SVP), have become an important tool in designing modern cryptographic schemes, especially since these problems are considered post-quantum secure. For example, Shors quantum polynomial-time algorithm for integer factorization has rendered the famous RSA cryptosystem insecure, assuming existence of quantum computers.

Instead of basing hardness on worst-case integer lattices, to make the lattice-based encryption schemes more efficient, there has been a significant push to use ideal lattices in ring of integers of number fields, and such a scheme has even been standardized by NIST recently. However, it is not clear if the additional algebraic structure of such ideal lattices, which lie in well known Dedekind-domains, can withstand quantum attacks. In this work we show that we can base similar and natural cryptosystems on hardness of ideal lattices in non Dedekind-domains which have less algebraic structure. This allows the security of the efficient cryptosystems to be based on problems closer to the worst-case integer lattices. The main technical contribution of the work is a novel and generalized way to prove the ??ideal-clearing lemma? of Lyubashevsky et al (Eurocrypt 2010). This is joint work with Chengyu Lin.

Speaker Bio:
Charanjit S. Jutla obtained his BTech in Computer Science from IIT Kanpur in 1985 and PhD in Computer Science from the University of Texas at Austin in 1990. Since then he has been a research staff member at IBM T. J. Watson Research Center. He has published many papers in the fields of modal logics, coding theory and cryptography. His current research interests include complexity theory and cryptography.

Host Faculty: Prof. Chaya Ganesh