Evaluation of Polynomial Reconstruction Problem using Lagrange Interpolation Method
Sattar B. Sadkhan, K.H. Ruma · 2006
The polynomial reconstruction problem (PRP) has been introduced in 1999 as a new hard problem. Several cryptographic primitives established on this problem have been constructed. Then it has been studied from the point of view of robustness, and several important properties have been discovered and proved. Furthermore many asymmetric cipher based on the PRP has been constructed. This paper provides an evaluation analysis of the application of Lagrange interpolation method in Augot's cryptosystem that is based on the polynomial reconstruction problem. It was clear that the Lagrange interpolation can be considered as a suitable method for PRP in comparison with Berelkamp-Welsh algorithm or with the direct method