0
$\begingroup$

I was working on a scheme in cryptography and came up with the following scenario.

To put it in proper words.

  1. We have an element $\frac{1}{x+m}$.
  2. The 2 elements $x$ and $x_1$ are known.
  3. We want to transform $\frac{1}{x+m}$ to $\frac{1}{x_1+m}$. I.e, we need a $k$ such that $\frac{k}{x+m} = \frac{1}{x1+m}$.

You can consider $x, x_1, m$ to be elements of $\mathbb Z_p^\ast$. You can introduce any extra dummy variables if you want for the conversion. It'd be of great of help if you can give me an idea with this.

Thanks!

  • 1
    What does "convert" mean? Do you know what $x$ and $x_1$ are to begin with? You seem to imply this when you say "Given $x,x_1$". But if so, it's trivial: given $y=\frac{1}{x+m}$, take $1/(\frac{1}{y}-x+x_1)$.2011-03-13
  • 0
    Sorry about being un-clear. Thanks for pointing out. I have edited the question to a better form.2011-03-13

1 Answers 1

1

You are given $y=\frac{1}{x+m}$. Then $\frac{1}{y}= x+m$, and $x_1+m = \frac{1}{y}-x+x_1$.

So $$\frac{1}{x_1+m} = \frac{y}{1-y(x-x_1)}.$$

Therefore, simply set $$k = \frac{1}{1-y(x-x_1)},\quad \text{where}\quad y = \frac{1}{1+m},$$ which can be done since you know $x$, $x_1$, and $y$.

  • 0
    Wow. Thanks a ton!! :) Just what i was looking for. Just an additional clarification to make the scheme more stronger.. with the same scenario as above: Given g^(1/(x+m)), instead of (1/(x+m)) (It is not possible to find (1/(x+m)) due to the Discrete log problem.) and finding a k such that g^(k/(x+m)) = g^(1/(x1+m)).2011-03-13
  • 0
    @bala: It's hard for me to figure out what it is you are going after. But it seems to me on first brush that if you could solve this problem, you would be able to solve the Diffie-Hellman problem through a suitable switch of variable, so I'm not sure if this can be done easily.2011-03-13