Entropic Hardness of Module-LWE from Module-NTRU

Katharina Boudgoust; Corentin Jeudy; Adeline Roux-Langlois; Weiqiang Wen

doi:10.1007/978-3-031-22912-1_4

Entropic Hardness of Module-LWE from Module-NTRU

Katharina Boudgoust, Corentin Jeudy^*, Adeline Roux-Langlois, Weiqiang Wen

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

4 Citations (Scopus)

Abstract

The Module Learning With Errors problem () has gained popularity in recent years for its security-efficiency balance,and its hardness has been established for a number of variants. In this paper, we focus on proving the hardness of (search) for general secret distributions, provided they carry sufficient min-entropy. This is called entropic hardness of. First, we adapt the line of proof of Brakerski and Döttling on (TCC’20) to prove that the existence of certain distributions implies the entropic hardness of. Then, we provide one such distribution whose required properties rely on the hardness of the decisional Module- NTRU problem.

Original language	English
Title of host publication	Progress in Cryptology – INDOCRYPT 2022 : 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings
Editors	Takanori Isobe, Santanu Sarkar
Number of pages	22
Place of publication	Cham
Publisher	Springer
Publication date	Jan 2023
Pages	78-99
ISBN (Print)	978-3-031-22911-4
ISBN (Electronic)	978-3-031-22912-1
DOIs	https://doi.org/10.1007/978-3-031-22912-1_4
Publication status	Published - Jan 2023

Series	Lecture Notes in Computer Science
Volume	13774
ISSN	0302-9743

Keywords

Entropic hardness
Lattice-based cryptography
Module learning with errors
Module-NTRU

Access to Document

10.1007/978-3-031-22912-1_4

Cite this

Boudgoust, Katharina ; Jeudy, Corentin ; Roux-Langlois, Adeline et al. / Entropic Hardness of Module-LWE from Module-NTRU. Progress in Cryptology – INDOCRYPT 2022: 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings. editor / Takanori Isobe ; Santanu Sarkar. Cham : Springer, 2023. pp. 78-99 (Lecture Notes in Computer Science, Vol. 13774).

@inproceedings{0415a53160874d82a58860a1f3b1713d,

title = "Entropic Hardness of Module-LWE from Module-NTRU",

abstract = "The Module Learning With Errors problem () has gained popularity in recent years for its security-efficiency balance,and its hardness has been established for a number of variants. In this paper, we focus on proving the hardness of (search) for general secret distributions, provided they carry sufficient min-entropy. This is called entropic hardness of. First, we adapt the line of proof of Brakerski and D{\"o}ttling on (TCC{\textquoteright}20) to prove that the existence of certain distributions implies the entropic hardness of. Then, we provide one such distribution whose required properties rely on the hardness of the decisional Module- NTRU problem.",

keywords = "Entropic hardness, Lattice-based cryptography, Module learning with errors, Module-NTRU",

author = "Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen",

year = "2023",

month = jan,

doi = "10.1007/978-3-031-22912-1_4",

language = "English",

isbn = "978-3-031-22911-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "78--99",

editor = "Takanori Isobe and Santanu Sarkar",

booktitle = "Progress in Cryptology – INDOCRYPT 2022",

address = "Netherlands",

}

Boudgoust, K, Jeudy, C, Roux-Langlois, A & Wen, W 2023, Entropic Hardness of Module-LWE from Module-NTRU. in T Isobe & S Sarkar (eds), Progress in Cryptology – INDOCRYPT 2022: 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings. Springer, Cham, Lecture Notes in Computer Science, vol. 13774, pp. 78-99. https://doi.org/10.1007/978-3-031-22912-1_4

Entropic Hardness of Module-LWE from Module-NTRU. / Boudgoust, Katharina; Jeudy, Corentin; Roux-Langlois, Adeline et al.
Progress in Cryptology – INDOCRYPT 2022: 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings. ed. / Takanori Isobe; Santanu Sarkar. Cham: Springer, 2023. p. 78-99 (Lecture Notes in Computer Science, Vol. 13774).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Entropic Hardness of Module-LWE from Module-NTRU

AU - Boudgoust, Katharina

AU - Jeudy, Corentin

AU - Roux-Langlois, Adeline

AU - Wen, Weiqiang

PY - 2023/1

Y1 - 2023/1

N2 - The Module Learning With Errors problem () has gained popularity in recent years for its security-efficiency balance,and its hardness has been established for a number of variants. In this paper, we focus on proving the hardness of (search) for general secret distributions, provided they carry sufficient min-entropy. This is called entropic hardness of. First, we adapt the line of proof of Brakerski and Döttling on (TCC’20) to prove that the existence of certain distributions implies the entropic hardness of. Then, we provide one such distribution whose required properties rely on the hardness of the decisional Module- NTRU problem.

AB - The Module Learning With Errors problem () has gained popularity in recent years for its security-efficiency balance,and its hardness has been established for a number of variants. In this paper, we focus on proving the hardness of (search) for general secret distributions, provided they carry sufficient min-entropy. This is called entropic hardness of. First, we adapt the line of proof of Brakerski and Döttling on (TCC’20) to prove that the existence of certain distributions implies the entropic hardness of. Then, we provide one such distribution whose required properties rely on the hardness of the decisional Module- NTRU problem.

KW - Entropic hardness

KW - Lattice-based cryptography

KW - Module learning with errors

KW - Module-NTRU

U2 - 10.1007/978-3-031-22912-1_4

DO - 10.1007/978-3-031-22912-1_4

M3 - Article in proceedings

SN - 978-3-031-22911-4

T3 - Lecture Notes in Computer Science

SP - 78

EP - 99

BT - Progress in Cryptology – INDOCRYPT 2022

A2 - Isobe, Takanori

A2 - Sarkar, Santanu

PB - Springer

CY - Cham

ER -

Boudgoust K, Jeudy C, Roux-Langlois A, Wen W. Entropic Hardness of Module-LWE from Module-NTRU. In Isobe T, Sarkar S, editors, Progress in Cryptology – INDOCRYPT 2022: 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings. Cham: Springer. 2023. p. 78-99. (Lecture Notes in Computer Science, Vol. 13774). doi: 10.1007/978-3-031-22912-1_4

Entropic Hardness of Module-LWE from Module-NTRU

Abstract

Keywords

Access to Document

Fingerprint

Cite this