I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I am trying 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 $q=\lfloor \frac{a}{b} \rfloor$ by using 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 (i.e. something like $x^{-1} \mbox{ mod } p$)of an encrypted number as a building block for the GCD protocol.
Both
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.
