TY - JOUR

T1 - Duplication free public keys based on SIS-type problems

AU - Lee, Hyang Sook

AU - Lee, Juhee

AU - Lim, Seongan

N1 - Funding Information:
Hyang-Sook Lee, Juhee Lee and Seongan Lim were supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Science, ICT and Future Planning ( NRF-2015R1A2A1A15054564 ). Seongan Lim was also supported by Ministry of Science, ICT and Future Planning ( NRF-2016R1D1A1B01008562 ). Juhee Lee was also supported by the Ministry of Science, ICT and Future Planning ( NRF-2016R1A6A3A11933335 ).
Publisher Copyright:
© 2017 Elsevier Inc.

PY - 2017/11

Y1 - 2017/11

N2 - In the public key cryptography, we say that two public keys are duplicated if they share a private key in common. We point out that no duplicate public keys exist in the RSA public key scheme since there is a one-to-one correspondence between the set of problems and the set of solutions for integer factorization problem. Contrary to the integer factorization problem, there is no such one-to-one correspondence with Short Integer Solution (SIS)-type problems and this necessitates to study its effect on duplicate public keys of the schemes based on SIS. In this paper, we analyze the existence of duplicate public keys with four types of SIS problem: SIS, SIS with full rank solution set, basic Inhomogeneous SIS (ISIS), ISIS with the defining matrix A as a public parameter. As a result, we show that there is no provable way to exclude duplicate public keys of the schemes based on the basic SIS, basic ISIS, and SIS with a full rank solution set. However, we show that if A is given in the systematic form and the given set of solutions forms a matrix of rank (m−n) over Zq, then it guarantees duplication free public keys. We also prove that the schemes based on ISIS with the matrix A as a public parameter always guarantee duplication free public keys.

AB - In the public key cryptography, we say that two public keys are duplicated if they share a private key in common. We point out that no duplicate public keys exist in the RSA public key scheme since there is a one-to-one correspondence between the set of problems and the set of solutions for integer factorization problem. Contrary to the integer factorization problem, there is no such one-to-one correspondence with Short Integer Solution (SIS)-type problems and this necessitates to study its effect on duplicate public keys of the schemes based on SIS. In this paper, we analyze the existence of duplicate public keys with four types of SIS problem: SIS, SIS with full rank solution set, basic Inhomogeneous SIS (ISIS), ISIS with the defining matrix A as a public parameter. As a result, we show that there is no provable way to exclude duplicate public keys of the schemes based on the basic SIS, basic ISIS, and SIS with a full rank solution set. However, we show that if A is given in the systematic form and the given set of solutions forms a matrix of rank (m−n) over Zq, then it guarantees duplication free public keys. We also prove that the schemes based on ISIS with the matrix A as a public parameter always guarantee duplication free public keys.

KW - Lattices

KW - Public key authentication

KW - SIS problem

UR - http://www.scopus.com/inward/record.url?scp=85029419096&partnerID=8YFLogxK

U2 - 10.1016/j.ffa.2017.09.001

DO - 10.1016/j.ffa.2017.09.001

M3 - Article

AN - SCOPUS:85029419096

VL - 48

SP - 430

EP - 446

JO - Finite Fields and their Applications

JF - Finite Fields and their Applications

SN - 1071-5797

ER -