Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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)$. –  Arturo Magidin Mar 13 '11 at 5:10
    
Sorry about being un-clear. Thanks for pointing out. I have edited the question to a better form. –  bala maverick Mar 13 '11 at 5:18

1 Answer 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$.

share|improve this answer
    
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)). –  bala maverick Mar 13 '11 at 5:54
    
@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. –  Arturo Magidin Mar 13 '11 at 20:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.