Please use this identifier to cite or link to this item: http://hdl.handle.net/10263/7405
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSingha, Subhadip-
dc.date.accessioned2023-09-12T11:21:36Z-
dc.date.available2023-09-12T11:21:36Z-
dc.date.issued2023-03-
dc.identifier.citation194p.en_US
dc.identifier.urihttp://hdl.handle.net/10263/7405-
dc.descriptionThis thesis is under the supervision of Prof Palash Sarkaren_US
dc.description.abstractLattice-based cryptography is a highly regarded contender for post-quantum standard- ization by NIST. NIST has already chosen “CRYSTALS-KYBER” a lattice-based public-key encryption and key-establishment algorithm and “CRYSTALS-DILITHIUM”, a lattice-based digital signature algorithm. The current lattice-based schemes are based on Oded Regev’s original construction, which sparked significant interest in the cryptographic community due to its post-quantum security and the equivalence between worst-case and average-case hardness. Oded Regev’s cryptographic scheme is built upon a problem called “Learning with Error” (LWE), which is a generalization of the “Learning Parity with Noise” (LPN) problem. This scheme is straightforward to implement and has gained attention for its simplicity. Previ- ously, Mikolas Ajtai demonstrated the worst-case to average-case equivalence for a set of hard lattice problems. Regev’s seminal paper demonstrated that the security of LWE-based cryptosystems could rely on the hardness of worst-case lattice problems. While this result is theoretically groundbreaking, the reduction from hard lattice problems to LWE is not tightly bound, which limits its practical applicability. The tightness of a reduction is a critical factor often underestimated. The tightness gap of a reduction quantifies the concreteness of the reduction, and a tight reduction is valuable for translating theoretical hardness guarantees into practical scenarios. Cryptography, as a field, prioritizes practical applicability. Non-tight reductions lead to less efficient systems but they have practical applications. Regev’s work has prompted numerous follow-up studies. One significant effort aimed to make the reduction classical, as the original reduction was quantum-based. Additionally, subsequent research has focused on enhancing the efficiency of LWE-based cryptosystems by utilizing various algebraic variants of lattices, such as ideal and module lattices. We thoroughly investigate these major reductions to unveil their true significance in terms of reduction tightness. Furthermore, we conduct a concrete security analysis of these reductions and identify several areas for improvement.en_US
dc.language.isoenen_US
dc.publisherIndian Statistical Institute, Kolkataen_US
dc.relation.ispartofseriesISI Ph. D Thesis;TH587-
dc.subjectLattice, Ideal latticesen_US
dc.subjectShortest vector problemen_US
dc.subjectLattice problemsen_US
dc.subjectLearning with error problemen_US
dc.titleOn the Tightness Gap Analysis of Reductions of some Lattice problems to the Learning with Error problemen_US
dc.typeThesisen_US
Appears in Collections:Theses

Files in This Item:
File Description SizeFormat 
Thesis_Subhadip Singha-30-8-23.pdfThesis1.05 MBAdobe PDFView/Open
17_Form-Subhadip Singha-30-8-23.pdfForm-17734.02 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.