Paper 2017/1241

A Public-key Encryption Scheme Based on Non-linear Indeterminate Equations (Giophantus)

Koichiro Akiyama, Yasuhiro Goto, Shinya Okumura, Tsuyoshi Takagi, Koji Nuida, Goichiro Hanaoka, Hideo Shimizu, and Yasuhiko Ikematsu


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 under the linear condition. This paper is a revised version of SAC2017.

Note: We reconsidered the resistant against the evaluating at one attack by using an indicator called "distinguishing advantage". And we re-evaluate the security strength for appropriate parameters.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.The preproceeding of SAC2017
Public-key CryptosystemPost-Quantum CryptosystemIndeterminate EquationSmallest Solution Problem
Contact author(s)
koichiro akiyama @ toshiba co jp
2018-07-30: revised
2017-12-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Koichiro Akiyama and Yasuhiro Goto and Shinya Okumura and Tsuyoshi Takagi and Koji Nuida and Goichiro Hanaoka and Hideo Shimizu and Yasuhiko Ikematsu},
      title = {A Public-key Encryption Scheme Based on Non-linear Indeterminate Equations (Giophantus)},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1241},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.