Reduction From Module-SIS to Ring-SIS Under Norm Constraint of Ring-SIS
| Autor: | Young-Sik Kim, Jong-Seon No, Zahyun Koo |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
ring-short integer solution (R-SIS) problem short integer solution (SIS) problem General Computer Science business.industry module-short integer solution (M-SIS) problem Polynomial ring General Engineering Word error rate Cryptography learning with error (LWE) Upper and lower bounds Lattice (order) General Materials Science lcsh:Electrical engineering. Electronics. Nuclear engineering Security level business lcsh:TK1-9971 Mathematics Lattice-based cryptography |
| Zdroj: | IEEE Access, Vol 8, Pp 140998-141006 (2020) |
| ISSN: | 2169-3536 |
| Popis: | Lattice-based cryptographic scheme is constructed based on hard problems on a lattice such as the short integer solution (SIS) problem and the learning with error (LWE). However, the cryptographic scheme based on SIS or LWE is inefficient since the size of the key is too large. Thus, most cryptographic schemes use the variants of LWE and SIS with ring and module structures. Albrecht and Deo showed that there is a reduction from module-LWE (M-LWE) to ring-LWE (R-LWE) in the polynomial ring by handling the error rate and modulus. However, unlike the LWE problem, the SIS problem does not have an error rate, but there is the upper bound β on the norm of the solution of the SIS problem. In this paper, we propose the two novel reductions related to module-SIS (M-SIS) and ring-SIS (R-SIS) on a polynomial ring. We propose (i) the reduction from R-SIS qk,mk,βk to R-SISq,m,β and (ii) the reduction from M-SIS to R-SIS under norm constraint of R-SIS. Combining these two results implies that R-SIS for a specified modulus and number samples is more difficult than M-SIS under norm constraints of R-SIS, which provides the range of possible module ranks for M-SIS. From the reduction we propose, contrary to the widely known belief, our result shows that there is a possibility that the security parameters of M-SIS may be less secure when it reduces to R-SIS for the theoretical reasons presented in this paper. Therefore, when generating parameters on an M-SIS structure, the theoretical security level over R-SIS also should also be checked at the same time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|