A failure in decryption process for bivariate polynomial reconstruction problem cryptosystem.

Area of Science:

• Cryptography
• Number Theory
• Computer Science

Background:

• The Polynomial Reconstruction Problem (PRP) was introduced in 1999 as a challenging mathematical problem.
• Early univariate and later bivariate PRP cryptosystems were developed, building upon prior work.
• Previous cryptanalysis demonstrated vulnerabilities in earlier univariate schemes.

Purpose of the Study:

• To describe a specific decryption failure in both univariate and bivariate PRP cryptosystems.
• To identify the precise condition under which this decryption failure occurs.
• To establish an upper bound for error weight to ensure successful decryption.

Main Methods:

• Analysis of the mathematical structure of the PRP cryptosystems.
• Demonstration of decryption failure based on error weight and polynomial properties.
• Derivation of an upper bound for error weight to prevent decryption failure.

Main Results:

• Decryption failure is shown to occur when the error weight surpasses the number of monomials in the secret polynomial.
• A clear condition for decryption failure in both studied PRP schemes has been identified.
• An explicit upper bound is determined to avoid decryption failure.

Conclusions:

• The security and reliability of PRP cryptosystems are contingent on managing error weights.
• Understanding these failure conditions is crucial for the practical application of PRP.
• The derived upper bound provides a guideline for secure parameter selection in PRP implementations.