An Improved Security Analysis on an Indeterminate Equation Public Key Cryptosystem by Evaluation Attacks

Akiyama, Goto, Okumura, Takagi, Nuida and Hanaoka introduced an indeterminate equation analogue of learning with errors (IE-LWE) problem as a new computationally hard problem and constructed a candidate of post-quantum cryptosystem, called “Giophantus”. Giophantus satisfies the indistinguishability under chosen plaintext attack (IND-CPA) if IE-LWE problem is computationally infeasible. Akiyama et al., Shimizu and Ikematsu proposed improved Giophantus to the post-quantum standardization project. Beullens, Castryck and Vercauteren proposed an evaluation at one attack against IND-CPA security of Giophantus. However, Akiyama et al. assert that recommended parameters can resist Vercauteren et al.’s attack. Therefore, the security analysis on Giophantus is still needed. In this paper, we propose a new kind of evaluation attack against IND-CPA security of Giophantus. Our attack solves IE-LWE problem by combining a part of Vercauteren et al.’s attack with a lattice attack on low rank lattices, e.g., 6-rank lattices for recommended parameters. Moreover, we investigate a way to avoid our attack and some variants of our attack. We give some remarks on modification of the IE-LWE problem. Our experimental analysis shows that our attack can solve IE-LWE problem efficiently, and that Giophantus does not satisfy IND-CPA security unless IE-LWE problem is modified appropriately.Selected Areas in Cryptography – SAC 2019, 26th International Conference, Waterloo, ON, Canada, August 12–16, 201