TY - GEN
T1 - An Improvement on the Linear Algebraic Attack for the Indeterminate Equation Encryption Scheme
AU - Ikematsu, Yasuhiko
AU - Akiyama, Koichiro
AU - Takagi, Tsuyoshi
N1 - Publisher Copyright:
© 2018 IEICE.
PY - 2019/3/8
Y1 - 2019/3/8
N2 - At SAC2017, Akiyama et al. proposed the indeterminate equation encryption scheme whose security is based on a solution problem of indeterminate equation. It is an extension of algebraic surface encryption scheme. A public key X for this scheme is a polynomial in two variables over a finite ring. Akiyama et al. also proposed two attacks, the linear algebraic attack (LAA) and the key recovery attack (KRA), by using the lattice structure associated with this scheme. In this paper, we give an improvement on LAA. Also we explain the relation between our improvement and the improvement on LAA proposed by Xagawa and examine parameters that those attacks fail by experiments. As a result, we conclude that if the total degree of the public key X is one, then KRA is more efficient than LAA and if that of X is two, then LAA is more efficient than KRA.
AB - At SAC2017, Akiyama et al. proposed the indeterminate equation encryption scheme whose security is based on a solution problem of indeterminate equation. It is an extension of algebraic surface encryption scheme. A public key X for this scheme is a polynomial in two variables over a finite ring. Akiyama et al. also proposed two attacks, the linear algebraic attack (LAA) and the key recovery attack (KRA), by using the lattice structure associated with this scheme. In this paper, we give an improvement on LAA. Also we explain the relation between our improvement and the improvement on LAA proposed by Xagawa and examine parameters that those attacks fail by experiments. As a result, we conclude that if the total degree of the public key X is one, then KRA is more efficient than LAA and if that of X is two, then LAA is more efficient than KRA.
UR - http://www.scopus.com/inward/record.url?scp=85063873116&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85063873116&partnerID=8YFLogxK
U2 - 10.23919/ISITA.2018.8664254
DO - 10.23919/ISITA.2018.8664254
M3 - Conference contribution
AN - SCOPUS:85063873116
T3 - Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018
SP - 389
EP - 393
BT - Proceedings of 2018 International Symposium on Information Theory and Its Applications, ISITA 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 15th International Symposium on Information Theory and Its Applications, ISITA 2018
Y2 - 28 October 2018 through 31 October 2018
ER -