Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.