Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU
The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice-based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed di...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | IET Information Security |
| Online Access: | http://dx.doi.org/10.1049/2023/2969432 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850160246651092992 |
|---|---|
| author | Wenjuan Jia Jiang Zhang Baocang Wang |
| author_facet | Wenjuan Jia Jiang Zhang Baocang Wang |
| author_sort | Wenjuan Jia |
| collection | DOAJ |
| description | The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice-based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A) to be the uniform distribution. In this paper, we show that under the Module-N-th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank-preserving. |
| format | Article |
| id | doaj-art-b47888ddf67a4edbb10bdb7b9095cb30 |
| institution | OA Journals |
| issn | 1751-8717 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-b47888ddf67a4edbb10bdb7b9095cb302025-08-20T02:23:12ZengWileyIET Information Security1751-87172023-01-01202310.1049/2023/2969432Hardness of Module-LWE with Semiuniform Seeds from Module-NTRUWenjuan Jia0Jiang Zhang1Baocang Wang2School of Telecommunications EngineeringState Key Laboratory of CryptologyState Key Laboratory of Integrated Service NetworksThe module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice-based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A) to be the uniform distribution. In this paper, we show that under the Module-N-th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank-preserving.http://dx.doi.org/10.1049/2023/2969432 |
| spellingShingle | Wenjuan Jia Jiang Zhang Baocang Wang Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU IET Information Security |
| title | Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU |
| title_full | Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU |
| title_fullStr | Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU |
| title_full_unstemmed | Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU |
| title_short | Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU |
| title_sort | hardness of module lwe with semiuniform seeds from module ntru |
| url | http://dx.doi.org/10.1049/2023/2969432 |
| work_keys_str_mv | AT wenjuanjia hardnessofmodulelwewithsemiuniformseedsfrommodulentru AT jiangzhang hardnessofmodulelwewithsemiuniformseedsfrommodulentru AT baocangwang hardnessofmodulelwewithsemiuniformseedsfrommodulentru |