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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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, 2022, Proceedings
Editors	Takanori Isobe, Santanu Sarkar
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	78-99
Number of pages	22
ISBN (Print)	9783031229114
DOIs	https://doi.org/10.1007/978-3-031-22912-1_4
Publication status	Published - 1 Jan 2022
Externally published	Yes
Event	23rd International Conference on Cryptology, INDOCRYPT 2022 - Kolkata, India Duration: 11 Dec 2022 → 14 Dec 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13774 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Cryptology, INDOCRYPT 2022
Country/Territory	India
City	Kolkata
Period	11/12/22 → 14/12/22

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, K., Jeudy, C., Roux-Langlois, A., & Wen, W. (2022). 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, 2022, Proceedings (pp. 78-99). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13774 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-22912-1_4

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, 2022, Proceedings. editor / Takanori Isobe ; Santanu Sarkar. Springer Science and Business Media Deutschland GmbH, 2022. pp. 78-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9e8771f689914e6f9642d827f1d4b2fd,

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",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 23rd International Conference on Cryptology, INDOCRYPT 2022 ; Conference date: 11-12-2022 Through 14-12-2022",

year = "2022",

month = jan,

day = "1",

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

language = "English",

isbn = "9783031229114",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "78--99",

editor = "Takanori Isobe and Santanu Sarkar",

booktitle = "Progress in Cryptology – INDOCRYPT 2022 - 23rd International Conference on Cryptology in India, 2022, Proceedings",

}

Boudgoust, K, Jeudy, C, Roux-Langlois, A & Wen, W 2022, 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, 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13774 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 78-99, 23rd International Conference on Cryptology, INDOCRYPT 2022, Kolkata, India, 11/12/22. 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, 2022, Proceedings. ed. / Takanori Isobe; Santanu Sarkar. Springer Science and Business Media Deutschland GmbH, 2022. p. 78-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13774 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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 - 2022/1/1

Y1 - 2022/1/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 - Conference contribution

AN - SCOPUS:85147853103

SN - 9783031229114

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 78

EP - 99

BT - Progress in Cryptology – INDOCRYPT 2022 - 23rd International Conference on Cryptology in India, 2022, Proceedings

A2 - Isobe, Takanori

A2 - Sarkar, Santanu

PB - Springer Science and Business Media Deutschland GmbH

T2 - 23rd International Conference on Cryptology, INDOCRYPT 2022

Y2 - 11 December 2022 through 14 December 2022

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, 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 78-99. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-22912-1_4