An improvement of a key exchange protocol relying on polynomial maps

Keita Suzuki, Koji Nuida

Research output: Contribution to journalArticlepeer-review


Akiyama et al. [A key exchange protocol relying on polynomial maps, Int. J. Math. Ind. 11 (2019) 195003] proposed a post-quantum key exchange protocol that is based on the hardness of solving a system of multivariate nonlinear polynomial equations but has a design strategy different from ordinary multivariate cryptography. Their protocol has two versions, an original one and a modified one, where the modified one has a trade-off that its security is strengthened while it has nonzero error probability in establishing a common key. In fact, the evaluation in their paper suggests that the probability of failing to establish a common key by the modified protocol with the proposed parameter set is impractically high. In this paper, we improve the success probability of Akiyama et al.'s modified key exchange protocol significantly while keeping the security, by restricting each component of the correct common key from the whole of the coefficient field to its small subset. We give theoretical and experimental evaluations showing that our proposed parameter set for our protocol is expected to achieve both failure probability 2-120 and 128-bit security level.

Original languageEnglish
Article number2250002
JournalInternational Journal of Mathematics for Industry
Issue number1
Publication statusPublished - Dec 1 2021

All Science Journal Classification (ASJC) codes

  • Computational Mechanics
  • Applied Mathematics
  • Modelling and Simulation
  • Numerical Analysis


Dive into the research topics of 'An improvement of a key exchange protocol relying on polynomial maps'. Together they form a unique fingerprint.

Cite this