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 ?


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$).

  • $\begingroup$ What ring are those polynomials over? $\;$ $\endgroup$ – user991 Dec 23 '14 at 18:54
  • $\begingroup$ @RickyDemer can be a field e.g. $\mathbb{Z}_p$ $\endgroup$ – user13676 Dec 25 '14 at 13:04
  • $\begingroup$ Why not FHE? You could do a secure 2-party computation. $\endgroup$ – mikeazo Dec 28 '14 at 1:53
  • $\begingroup$ @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) $\endgroup$ – user13676 Jan 5 '15 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.