NDLI: Worst-case to average-case reductions for module lattices

Content Provider	Springer Nature Link
Author	Langlois, Adeline Stehlé, Damien
Copyright Year	2014
Abstract	Most lattice-based cryptographic schemes are built upon the assumed hardness of the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. Their efficiencies can be drastically improved by switching the hardness assumptions to the more compact Ring-SIS and Ring-LWE problems. However, this change of hardness assumptions comes along with a possible security weakening: SIS and LWE are known to be at least as hard as standard (worst-case) problems on euclidean lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard as their restrictions to special classes of ideal lattices, corresponding to ideals of some polynomial rings. In this work, we define the Module-SIS and Module-LWE problems, which bridge SIS with Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these average-case problems are at least as hard as standard lattice problems restricted to module lattices (which themselves bridge arbitrary and ideal lattices). As these new problems enlarge the toolbox of the lattice-based cryptographer, they could prove useful for designing new schemes. Importantly, the worst-case to average-case reductions for the module problems are (qualitatively) sharp, in the sense that there exist converse reductions. This property is not known to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE.
Ending Page	599
Page Count	35
Starting Page	565
File Format	PDF
ISSN	09251022
e-ISSN	15737586
Journal	Designs, Codes and Cryptography
Issue Number	3
Volume Number	75
Language	English
Publisher	Springer US
Publisher Date	2014-02-26
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Information and Communication, Circuits Worst-case to average-case reductions Data Structures, Cryptology and Information Theory Lattice-based cryptography Discrete Mathematics in Computer Science Data Encryption Coding and Information Theory Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Combinatorics Module lattices Ideal lattices
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Polly Cracker, revisited

Hardness of learning problems over Burnside groups of exponent 3

A note on the security of MST 3

Minimum Guesswork with an Unreliable Oracle

New Lower Bounds for Matching Vector Codes

Trifferent codes with small lengths

LLL for ideal lattices: re-evaluation of the security of Gentry–Halevi’s FHE scheme

Adaptive Greedy Rejection Sampling

On the geometry of cyclic lattices

Worst-case to average-case reductions for module lattices

Similar Documents

Polly Cracker, revisited

Hardness of learning problems over Burnside groups of exponent 3

A note on the security of MST 3

Minimum Guesswork with an Unreliable Oracle

New Lower Bounds for Matching Vector Codes

Trifferent codes with small lengths

LLL for ideal lattices: re-evaluation of the security of Gentry–Halevi’s FHE scheme

Adaptive Greedy Rejection Sampling

On the geometry of cyclic lattices

Worst-case to average-case reductions for module lattices