I have a problem in my study of cryptography:
We know that if a polynomial f(x) has a degree of k, given a set of k
+1 data points (x_0,f(x_0)),...,(x_k,f(x_k)), we can know the
evaluation of f(x) at any value x, by the polynomial interpolation.
The method of polynomial interpolation is: Given the Lagrange
coefficients Delta_i for i=0,...,k,
f(x)=Delta_0*f(x_0)+...+Delta_k*f(x_k).
If the k+1 data points are (x_0,d_0=g^{ f(x_0) } ),...,
(x_k,d_k=g^{ f(x_k) } ), then we can get d=g^{ f(x) } at any value x,
by the similar method, without computing the discrete log of each
d_i=g^{ f(x_i) } for i=0,...,k.
The method is: g^{ f(x) }=d_0^{ \Delta_0 } * ... * d_k^{ \Delta_k }.
Now my problem is: f(x) has a degree of k, and its leading coefficient
is 1, i.e.
f(x)=x^{k} + c_{k-1}*x^{k-1} + ... + c_0, its other coefficients
{c_{k-1},...,c_0} are unknown. If we have
k data points (x_0,d_0=g^{ f(x_0) } ),...,
(x_{k-1},d_{k-1}=g^{ f(x_{k-1}) } ), can we get g^{f(x)} at any value
x, without computing the discrete log of each d_i for i=0,...,k-1?
Maybe this problem is relevant to the Diffie-Hellman problem, but I
don't know how to relate them? Are there any academic papers on
explaining this problem?
Thank you very much for any of your information!
Simon
|
