Re: Is this problem relevant to the Diffie-Hellman problem?

On Oct 23, 9:45 pm, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:
In article <6e11232e-16a8-43d4-8045-334b1e729...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

simon  <Simon.SCh....@xxxxxxxxx> wrote:
Now my problem is: f(x) has a degree of k, and its leading coefficient
is 1, [...]. 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?

You have a polynomial with k unknown coefficients and one known
coefficient. Treat it as a sum of one known degree k polynomial and one
unknown degree k-1 polynomial.

--
Kristian Gjøsteen

Hi, dear Kristian,

I understand what you mean: we can make an interpolation as following:

g^{ f(x) }=g^{x^t} * (d_0-g^{x_0^t})^{ \Delta_0 } * ... * (d_{k-1}-
g^{ x_{k-1}^t }^{ \Delta_{k-1} }.

But I'm sorry that I dont say clearly one condition for the problem: g
is unknown, g=h^u for some known h and unknown u.

If g is unknown, g^{x^t}, g^{x_0^t},...., g^{ x_{k-1}^t } can not be
computed, then how can we compute g^{ f(x) }?

Are there any papers about this problem?

Thank you very much!

Simon Sang
.

Relevant Pages

  • Re: Help needed with a proof...
    ... > I am trying to prove that computing M requires the knowledge of K: ... > Let fbe a function, where V is known and K unknown. ... it is necessary to know K - even in the environment ... My attempt goes as following and I would really appraciate if ...
    (sci.crypt)
  • Help needed with a proof...
    ... I am trying to prove that computing M requires the knowledge of K: ... Let fbe a function, where V is known and K unknown. ... My attempt goes as following and I would really appraciate if ... Bartosz Zoltak ...
    (sci.crypt)
  • Re: OPPOSITE OF all coin sequences are computable to infinite length ?
    ... > the TM for computing the halting problem. ... then you assign that to a variable, an unknown so to speak? ... Herc ...
    (sci.math)
  • Re: Registry Editor
    ... "The Unknown P" wrote in message ... > What do you get if you try the regedt32 engine. ... There are three types of people in computing, ... those that can't and those who don't quote. ...
    (microsoft.public.windowsxp.general)
  • Re: Is this problem relevant to the Diffie-Hellman problem?
    ... simon wrote: ... You have a polynomial with k unknown coefficients and one known ...
    (sci.crypt)