A Polynomial Public-Key Cryptosystem Based on Jacobian-Preserving Composition

Saimon Ahmed, Lavinia Ciungu

Abstract


We propose a public-key cryptosystem based on Jacobian-preserving polynomial compositions, utilizing algebraically invertible polynomial maps with hard-to-invert composition. The construction employs polynomial maps over the finite field Z_p, where p is a prime number, with Jacobian determinant equal to 1 to ensure invertibility. The public key function H: (Z_p)^n → (Z_p)^n is defined as the composition of invertible polynomial maps f₁, f₂, …, fₖ, each with Jacobian determinant 1, while the private key consists of the individual components used in the composition. Although inverting the composition is possible in principle, doing so without knowledge of the factors is computationally infeasible. This system incorporates both triangular and affine polynomial maps. We discuss the construction, provide formal correctness proofs, analyze hardness assumptions, and present a Python-based prototype with benchmark results.


Full Text:

PDF

References


H. Bass, E.H. Connell, D. Wright, The Jacobian Conjecture: Reduction of Degree and Formal Expansion of the Inverse, Bulletin of the American Mathematical Society 7 (1982), no. 2, 287-330.

A. van den Essen, Polynomial Automorphisms and the Jacobian Conjecture, Progress in Mathematics 190, Birkhäuser, 2000.

B.A. Dubrovin, Modern Geometry - Methods and Applications Part III: Introduction to Homology Theory, Springer, 2018.

J. Ding et al., Multivariate Public Key Cryptosystems, In: Post-Quantum Cryptography, Springer, 2004.

N. Koblitz, A Course in Number Theory and Cryptography, 2nd ed., Springer-Verlag, 1994.

D. Cox, J. Little, D. O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 2007.

J. Patarin, Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): Two new families of asymmetric algorithms, EUROCRYPT 1996, Springer, 33-48.

J. Ding, D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, ACNS 2005, Springer, 164-175, 2005.

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC), ACM, 2002.

W. Beullens, Breaking Rainbow Takes a Weekend on a Laptop, In: Advances in Cryptology - EUROCRYPT 2022, 507-536.




DOI: https://doi.org/10.52846/ami.v53i1.2247