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...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
IEEE
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/94daf2a2d4064d24a8a2ccc2c8f275dd |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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>. |
|---|