整数环上乘法噪声多项式插值算法的研究与改进

Study and Improvement of the Multiplicative Noisy Polynomial Interpolation Algorithm on Integral Ring

乘法噪声多项式插值问题在密码理论和编码理论研究中有着重要的应用。本文对Gathen和Shp-arlinski提出的整数环上乘法噪声多项式插值算法进行了分析,提出了改进算法。采用Babai的最近向量格归约技术得到更精确的估计向量,再计算出插值多项式的倍式多项式的系数,从而计算出原插值多项式的系数。改进算法降低了乘法近似黑盒的询问初值,提高了算法初始化阶段的效率。

The multiplicative noisy polynomial interpolation has important applications in cryptography and coding theory. This paper analyzes this algorithm on integral ring presented by Gathen and Shparlinski and presents an improved algorithm. By the lattice reduction technique on the nearest vector presented by Babai, a more accurate estimate vector can be obtained and the coefficients of the multiple polynomial of the interpolation polynomial can be computed. Then the coefficients of the original interpolation polynomial can be computed. The improved algorithm reduces the initial query value input to the approximate multiplicative black box and enhances the algorithm efficiency.