Improved Reduction Between SIS Problems Over Structured Lattices
Many lattice-based cryptographic schemes are constructed based on hard problems on an algebraic structured lattice, such as the short integer solution (SIS) problems. These problems are called ring-SIS (R-SIS) and its generalized version, module-SIS (M-SIS). Generally, it has been considered that pr...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9615083/ |
| _version_ | 1811210517894660096 |
|---|---|
| author | Zahyun Koo Yongwoo Lee Joon-Woo Lee Jong-Seon No Young-Sik Kim |
| author_facet | Zahyun Koo Yongwoo Lee Joon-Woo Lee Jong-Seon No Young-Sik Kim |
| author_sort | Zahyun Koo |
| collection | DOAJ |
| description | Many lattice-based cryptographic schemes are constructed based on hard problems on an algebraic structured lattice, such as the short integer solution (SIS) problems. These problems are called ring-SIS (R-SIS) and its generalized version, module-SIS (M-SIS). Generally, it has been considered that problems defined on the module lattice are more difficult than the problems defined on the ideal lattice. However, Koo, No, and Kim showed that R-SIS is more difficult than M-SIS under some norm constraints of R-SIS. However, this reduction has problems in that the rank of the module is limited to about half of the instances of R-SIS, and the comparison is not performed through the same modulus of R-SIS and M-SIS. In this paper, we propose the three reductions. First, we show that R-SIS is more difficult than M-SIS with the same modulus and ring dimension under some constraints of R-SIS. Also, we show that through the reduction from M-SIS to R-SIS with the same modulus, the rank of the module is extended as much as the number of instances of R-SIS from half of the number of instances of R-SIS compared to the previous work. Second, we show that R-SIS is more difficult than M-SIS under some constraints, which is tighter than the M-SIS in the previous work. Finally, we propose that M-SIS with the modulus prime <inline-formula> <tex-math notation="LaTeX">$q^{k}$ </tex-math></inline-formula> is more difficult than M-SIS with the composite modulus <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula>, such that <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula> is divided by <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>. Through the three reductions, we conclude that R-SIS with the modulus <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> is more difficult than M-SIS with the composite modulus <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula>. |
| first_indexed | 2024-04-12T04:55:56Z |
| format | Article |
| id | doaj.art-94daf2a2d4064d24a8a2ccc2c8f275dd |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T04:55:56Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-94daf2a2d4064d24a8a2ccc2c8f275dd2022-12-22T03:47:07ZengIEEEIEEE Access2169-35362021-01-01915708315709210.1109/ACCESS.2021.31281399615083Improved Reduction Between SIS Problems Over Structured LatticesZahyun Koo0https://orcid.org/0000-0003-4232-5279Yongwoo Lee1https://orcid.org/0000-0001-9424-6498Joon-Woo Lee2https://orcid.org/0000-0002-4125-6331Jong-Seon No3https://orcid.org/0000-0002-3946-0958Young-Sik Kim4https://orcid.org/0000-0003-4114-4935Department of Electrical and Computer Engineering, INMC, Seoul National University, Seoul, South KoreaDepartment of Electrical and Computer Engineering, INMC, Seoul National University, Seoul, South KoreaDepartment of Electrical and Computer Engineering, INMC, Seoul National University, Seoul, South KoreaDepartment of Electrical and Computer Engineering, INMC, Seoul National University, Seoul, South KoreaDepartment of Information and Communication Engineering, Chosun University, Gwangju, South KoreaMany lattice-based cryptographic schemes are constructed based on hard problems on an algebraic structured lattice, such as the short integer solution (SIS) problems. These problems are called ring-SIS (R-SIS) and its generalized version, module-SIS (M-SIS). Generally, it has been considered that problems defined on the module lattice are more difficult than the problems defined on the ideal lattice. However, Koo, No, and Kim showed that R-SIS is more difficult than M-SIS under some norm constraints of R-SIS. However, this reduction has problems in that the rank of the module is limited to about half of the instances of R-SIS, and the comparison is not performed through the same modulus of R-SIS and M-SIS. In this paper, we propose the three reductions. First, we show that R-SIS is more difficult than M-SIS with the same modulus and ring dimension under some constraints of R-SIS. Also, we show that through the reduction from M-SIS to R-SIS with the same modulus, the rank of the module is extended as much as the number of instances of R-SIS from half of the number of instances of R-SIS compared to the previous work. Second, we show that R-SIS is more difficult than M-SIS under some constraints, which is tighter than the M-SIS in the previous work. Finally, we propose that M-SIS with the modulus prime <inline-formula> <tex-math notation="LaTeX">$q^{k}$ </tex-math></inline-formula> is more difficult than M-SIS with the composite modulus <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula>, such that <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula> is divided by <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>. Through the three reductions, we conclude that R-SIS with the modulus <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> is more difficult than M-SIS with the composite modulus <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula>.https://ieeexplore.ieee.org/document/9615083/Lattice-based cryptographylearning with error (LWE)module-short integer solution (M-SIS) problemring-short integer solution (R-SIS) problemshort integer solution~(SIS) problem |
| spellingShingle | Zahyun Koo Yongwoo Lee Joon-Woo Lee Jong-Seon No Young-Sik Kim Improved Reduction Between SIS Problems Over Structured Lattices IEEE Access Lattice-based cryptography learning with error (LWE) module-short integer solution (M-SIS) problem ring-short integer solution (R-SIS) problem short integer solution~(SIS) problem |
| title | Improved Reduction Between SIS Problems Over Structured Lattices |
| title_full | Improved Reduction Between SIS Problems Over Structured Lattices |
| title_fullStr | Improved Reduction Between SIS Problems Over Structured Lattices |
| title_full_unstemmed | Improved Reduction Between SIS Problems Over Structured Lattices |
| title_short | Improved Reduction Between SIS Problems Over Structured Lattices |
| title_sort | improved reduction between sis problems over structured lattices |
| topic | Lattice-based cryptography learning with error (LWE) module-short integer solution (M-SIS) problem ring-short integer solution (R-SIS) problem short integer solution~(SIS) problem |
| url | https://ieeexplore.ieee.org/document/9615083/ |
| work_keys_str_mv | AT zahyunkoo improvedreductionbetweensisproblemsoverstructuredlattices AT yongwoolee improvedreductionbetweensisproblemsoverstructuredlattices AT joonwoolee improvedreductionbetweensisproblemsoverstructuredlattices AT jongseonno improvedreductionbetweensisproblemsoverstructuredlattices AT youngsikkim improvedreductionbetweensisproblemsoverstructuredlattices |