# [Released] Is this problem relevant to the Diffie-Hellman problem?

Discussion in 'Math Research' started by simon, Oct 23, 2008.

1. ### simonGuest

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

simon, Oct 23, 2008

2. ### serdar.boztasGuest

You have to be a little careful, but I think the answer is yes, unless

I presume you are talking about finite fields, and polynomials defined
over
finite fields--since you asked the question in relation to
cryptography. For
concreteness, let us assume f is in F_p[x] and that g is a generator
for F_p^* the multiplicative group of F_p.

Now the operations in the exponent happen in Z_{p-1}, the integers
modulo p-1, which is only a ring not a field. So, provided you have no
problems with divisibility, i.e., all the (x_i-x_j)'s in the
denominator of your Lagrange coefficients are relatively prime to p-1,
why can't you just define

h(x) = g(x) - x^k

and since deg(h) = k-1, use Lagrange interpolation like you suggested
above, without using discrete logs, to obtain g^{ h(x) } at any value
x and then
multiply by g^{x^k} to obtain g^{ f(x) }.

Serdar

serdar.boztas, Oct 29, 2008