# Obliviously computing the Least common multiple of two poylnomials

Consider I have two polynomials $f_1$ and $f_2$ of the same degree. I want to secure them (using any kind of encryption except FHE) and outsource them to an untrusted server. I want him to compute the least common multiple (LCM) of these two polynomials and return it to me.

• Question: Is there any protocol supporting above scenario ?

Or

Consider a more simpler scenario:

I have $C_1= a\cdot b \bmod p$ and $C_2=a \cdot d \bmod p$, where $p$ is a prime number. I want to outsource $C_1$ and $C_2$ using any form of encryption (other than FHE) and want to delegate GCD computation on these two values to a server without he knows the result (which is $a$).

-
What ring are those polynomials over? $\;$ – Ricky Demer Dec 23 '14 at 18:54
@RickyDemer can be a field e.g. $\mathbb{Z}_p$ – user13676 Dec 25 '14 at 13:04
Why not FHE? You could do a secure 2-party computation. – mikeazo Dec 28 '14 at 1:53
@mikeazo Yes, you're absolutely right; but I'd like to avoid using FHE or circuit based operation due to its inefficiency compared to the operation specific one (if I could have one) – user13676 Jan 5 '15 at 12:22