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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Zahyun Koo, Yongwoo Lee, Joon-Woo Lee, Jong-Seon No, Young-Sik Kim
Formato:	article
Lenguaje:	EN
Publicado:	IEEE 2021
Materias:	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 Electrical engineering. Electronics. Nuclear engineering TK1-9971
Acceso en línea:	https://doaj.org/article/94daf2a2d4064d24a8a2ccc2c8f275dd
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:94daf2a2d4064d24a8a2ccc2c8f275dd
record_format	dspace
spelling	oai:doaj.org-article:94daf2a2d4064d24a8a2ccc2c8f275dd2021-12-02T00:00:22ZImproved Reduction Between SIS Problems Over Structured Lattices2169-353610.1109/ACCESS.2021.3128139https://doaj.org/article/94daf2a2d4064d24a8a2ccc2c8f275dd2021-01-01T00:00:00Zhttps://ieeexplore.ieee.org/document/9615083/https://doaj.org/toc/2169-3536Many 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>.Zahyun KooYongwoo LeeJoon-Woo LeeJong-Seon NoYoung-Sik KimIEEEarticleLattice-based cryptographylearning with error (LWE)module-short integer solution (M-SIS) problemring-short integer solution (R-SIS) problemshort integer solution~(SIS) problemElectrical engineering. Electronics. Nuclear engineeringTK1-9971ENIEEE Access, Vol 9, Pp 157083-157092 (2021)
institution	DOAJ
collection	DOAJ
language	EN
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 Electrical engineering. Electronics. Nuclear engineering TK1-9971
spellingShingle	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 Electrical engineering. Electronics. Nuclear engineering TK1-9971 Zahyun Koo Yongwoo Lee Joon-Woo Lee Jong-Seon No Young-Sik Kim Improved Reduction Between SIS Problems Over Structured Lattices
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>.
format	article
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
title	Improved Reduction Between SIS Problems Over Structured Lattices
title_short	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_sort	improved reduction between sis problems over structured lattices
publisher	IEEE
publishDate	2021
url	https://doaj.org/article/94daf2a2d4064d24a8a2ccc2c8f275dd
work_keys_str_mv	AT zahyunkoo improvedreductionbetweensisproblemsoverstructuredlattices AT yongwoolee improvedreductionbetweensisproblemsoverstructuredlattices AT joonwoolee improvedreductionbetweensisproblemsoverstructuredlattices AT jongseonno improvedreductionbetweensisproblemsoverstructuredlattices AT youngsikkim improvedreductionbetweensisproblemsoverstructuredlattices
_version_	1718404000333692928

Improved Reduction Between SIS Problems Over Structured Lattices

Ejemplares similares