0
$\begingroup$

I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I want to implement a secure protocol to compute the GCD of two encrypted numbers.

To calculate the GCD, I particularly need to be able to securely calculate the quotient of the division of two numbers. There is a secure protocol for that but is too expensive. Instead, I thought that I might use the much cheaper protocol for computing the modular inversion of an encrypted number as a building block for the GCD protocol.

Since both problems (quotient and modular inversion) can be reduced to solving a linear Diophantine equation then perhaps we can reduce one to the other:

Modular inversion $y=x^{-1} \mbox{ mod } p$:

$x y + p m = 1$

Quotient division $q=\lfloor \frac{a}{b} \rfloor$:

$ q b + (a \mbox{ mod } b) t = a$

The question is whether we can rephrase this equation such that the right hand side is 1 (and still be a linear Diophantine), so we are able to use an existing modular inversion protocol to calculate the quotient division.

P.S.: I can't use the extended euclidean algorithm directly on any of them. The only allowed (secure) protocols to be used as building blocks are modular inversion, multiplication, modular division, and addition.

$\endgroup$
7
  • 1
    $\begingroup$ Both equations have infinitely many solution, and computing the quotient from an arbitrary solution to the latter equation will involve division. In general, we would have $t\equiv 1\pmod{b}$ but not necessarily $t=1$. And for $t\ne 1$, a division by $b$ will be required to reduce it to 1, which is not any better then simply dividing $a$ by $b$. $\endgroup$ Jul 23, 2010 at 17:11
  • 1
    $\begingroup$ @Speiser: No it is not elementary. I do not want to use extended GCD. In fact, I am in the field of secure multiparty comptuation and I want to implement the GCD algorithm itself in a secure form, given only a secure protocol for modular inversion (Using homomorphic encryption or secret-sharing). It would have been trivial to use extended GCD to solve these equations, but I don't have a secure sub-protocol for that. $\endgroup$ Jul 24, 2010 at 0:48
  • $\begingroup$ @Alekseyev: Thanks for your useful comment. So since it is not possible I'll try another research direction. $\endgroup$ Jul 24, 2010 at 0:49
  • $\begingroup$ In the future, you should probably include that kind of information with the original question. It looked a lot like an elementary question. $\endgroup$ Jul 24, 2010 at 1:08
  • 1
    $\begingroup$ @Yuan: Thanks for the hint. I do apologize for the readers who were mislead by this mistake; I am new to online community discussion and the line between not too long and too less information was still a bit fuzzy to me. I just was trying to be nice and write as short as I can so as not to waste the time of the reader. $\endgroup$ Jul 24, 2010 at 1:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.