Reducing two variable linear Diophantine equation to modular inversion

2010-07-23T15:41:31Z

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.

Reducing two variable linear Diophantine equation to modular inversion - MathOverflow

Reducing two variable linear Diophantine equation to modular inversion