A new quantum-safe multivariate polynomial public key digital signature algorithm

Area of Science:

• Cryptography
• Quantum Computing Security
• Number Theory

Background:

• The advent of quantum computing poses a significant threat to current public-key cryptography.
• Existing digital signature algorithms are vulnerable to quantum attacks, necessitating the development of quantum-safe alternatives.

Purpose of the Study:

• To propose a novel quantum-safe digital signature algorithm named Multivariate Polynomial Public Key Digital Signature (MPPK/DS).
• To ensure the algorithm provides robust security against known classical and potential quantum attacks.

Main Methods:

• The algorithm leverages modular arithmetic properties within a prime Galois field GF(p).
• It utilizes multivariate polynomials and a specific prime number construction (p = q * 2^x + 1) for enhanced security.
• Security is based on the difficulty of solving multivariate equations and lifting solutions modulo q to modulo p-1.

Main Results:

• MPPK/DS is designed to withstand key-only, chosen-message, and known-message attacks.
• The algorithm's security is rooted in the hardness of the discrete logarithm problem for quantum computers and NP-hard problems for classical computers.
• The time complexity for key recovery and spoofing attacks is exponential, ensuring a high level of security.

Conclusions:

• MPPK/DS offers a promising quantum-safe solution for digital signatures.
• The algorithm can achieve NIST security levels by optimizing polynomial choices and the prime field parameters.
• This work contributes to the field of post-quantum cryptography by introducing a new, secure, and efficient signature scheme.