TY - GEN
T1 - A public-key encryption scheme based on non-linear indeterminate equations
AU - Akiyama, Koichiro
AU - Goto, Yasuhiro
AU - Okumura, Shinya
AU - Takagi, Tsuyoshi
AU - Nuida, Koji
AU - Hanaoka, Goichiro
N1 - Publisher Copyright:
© Springer International Publishing AG 2018.
PY - 2018
Y1 - 2018
N2 - In this paper, we propose a post-quantum public-key encryption scheme whose security depends on a problem arising from a multivariate non-linear indeterminate equation. The security of lattice cryptosystems, which are considered to be the most promising candidate for a post-quantum cryptosystem, is based on the shortest vector problem or the closest vector problem in the discrete linear solution spaces of simultaneous equations. However, several improved attacks for the underlying problems have recently been developed by using approximation methods, which result in requiring longer key sizes. As a scheme to avoid such attacks, we propose a public-key encryption scheme based on the “smallest” solution problem in the non-linear solution spaces of multivariate indeterminate equations that was developed from the algebraic surface cryptosystem. Since no efficient algorithm to find such a smallest solution is currently known, we introduce a new computational assumption under which proposed scheme is proven to be secure in the sense of IND-CPA. Then, we perform computational experiments based on known attack methods and evaluate that the key size of our scheme is able to be much shorter than those of previous lattice cryptosystems.
AB - In this paper, we propose a post-quantum public-key encryption scheme whose security depends on a problem arising from a multivariate non-linear indeterminate equation. The security of lattice cryptosystems, which are considered to be the most promising candidate for a post-quantum cryptosystem, is based on the shortest vector problem or the closest vector problem in the discrete linear solution spaces of simultaneous equations. However, several improved attacks for the underlying problems have recently been developed by using approximation methods, which result in requiring longer key sizes. As a scheme to avoid such attacks, we propose a public-key encryption scheme based on the “smallest” solution problem in the non-linear solution spaces of multivariate indeterminate equations that was developed from the algebraic surface cryptosystem. Since no efficient algorithm to find such a smallest solution is currently known, we introduce a new computational assumption under which proposed scheme is proven to be secure in the sense of IND-CPA. Then, we perform computational experiments based on known attack methods and evaluate that the key size of our scheme is able to be much shorter than those of previous lattice cryptosystems.
KW - Indeterminate equation
KW - Post-quantum cryptosystem
KW - Public-key cryptosystem
KW - Smallest solution problem
UR - http://www.scopus.com/inward/record.url?scp=85041819110&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041819110&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-72565-9_11
DO - 10.1007/978-3-319-72565-9_11
M3 - Conference contribution
AN - SCOPUS:85041819110
SN - 9783319725642
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 215
EP - 234
BT - Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers
A2 - Adams, Carlisle
A2 - Camenisch, Jan
PB - Springer Verlag
T2 - 24th International Conference on Selected Areas in Cryptography, SAC 2017
Y2 - 16 August 2017 through 18 August 2017
ER -