[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,

    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, Oct 23, 2008
    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
    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.boztas, Oct 29, 2008
    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.