A message recovery attack on multivariate polynomial trapdoor function

Rashid Ali; Muhammad Mubashar Hussain; Shamsa Kanwal; Fahima Hajjej; Saba Inam

doi:10.7717/peerj-cs.1521

A message recovery attack on multivariate polynomial trapdoor function

PeerJ Comput Sci. 2023 Aug 28:9:e1521. doi: 10.7717/peerj-cs.1521. eCollection 2023.

Authors

Rashid Ali¹, Muhammad Mubashar Hussain², Shamsa Kanwal³, Fahima Hajjej⁴, Saba Inam³

Affiliations

¹ Department of Mathematics, Capital University of Science and Technology, Islamabad, Pakistan.
² Department of Mathematics, University of Punjab, Jhelum, Pakistan.
³ Department of Mathematical Sciences, Fatima Jinnah Women University, Rawalpindi, Rawalpindi, Pakistan.
⁴ Department of Information Systems, College of Computer and Information Sciences, Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia.

Abstract

Cybersecurity guarantees the exchange of information through a public channel in a secure way. That is the data must be protected from unauthorized parties and transmitted to the intended parties with confidentiality and integrity. In this work, we mount an attack on a cryptosystem based on multivariate polynomial trapdoor function over the field of rational numbers Q. The developers claim that the security of their proposed scheme depends on the fact that a polynomial system consisting of 2n (where n is a natural number) equations and 3n unknowns constructed by using quasigroup string transformations, has infinitely many solutions and finding exact solution is not possible. We explain that the proposed trapdoor function is vulnerable to a Gröbner basis attack. Selected polynomials in the corresponding Gröbner basis can be used to recover the plaintext against a given ciphertext without the knowledge of the secret key.

Keywords: Algebraic cryptanalysis; Gröbner basis; Multivariate polynomial system; Public key cryptosystem.

Grants and funding

This study was funded by the Princess Nourah bint Abdulrahman University Researchers Supporting Project number (PNURSP2023R236), Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.