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

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

  1. simon

    simon Guest

    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
    #1
    1. Advertisements

  2. You have to be a little careful, but I think the answer is yes, unless
    I missed something major about your question.

    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
    #2
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.