An improvement of a key exchange protocol relying on polynomial maps

DOI10.1142/S2661335222500022MaRDI QIDQ5042559zbMATH OpenOpenAlexFDO

Authors Keita Suzuki, Koji Nuida

Publication date 20 October 2022

Published in International Journal of Mathematics for Industry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.05924

zbMATH Keywords

key exchange protocolmultivariate cryptographypost-quantum cryptography

Mathematics Subject Classification ID

Arithmetic theory of polynomial rings over finite fields (11T55) Data encryption (aspects in computer science) (68P25) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Abstract: Akiyama et al. (Int. J. Math. Indust., 2019) proposed a post-quantum key exchange protocol that is based on the hardness of solving a system of multivariate non-linear 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 non-zero 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.

Recommendations

• A key exchange protocol relying on polynomial maps
• New public-key cryptosystem based on the morphism of polynomials problem
• Key Exchange and Encryption Schemes Based on Non-commutative Skew Polynomials
• Two-message key exchange with strong security from ideal lattices
• On new key exchange multivariate protocols based on pseudorandom walks on incidence structures

Cites work

• A key exchange protocol relying on polynomial maps
• A method for obtaining digital signatures and public-key cryptosystems
• A new efficient algorithm for computing Gröbner bases (F₄)
• A public-key encryption scheme based on non-linear indeterminate equations
• Elliptic Curve Cryptosystems
• scientific article; zbMATH DE number 3948147 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• New directions in cryptography
• Using Algebraic Geometry

Cited in

(4)

• Security of polynomial transformations of the Diffie-Hellman key.
• Polly Two: a new algebraic polynomial-based public-key scheme
• Post-quantum no-key protocol
• A key exchange protocol relying on polynomial maps

This page was built for publication: An improvement of a key exchange protocol relying on polynomial maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5042559)