Assume $c$ is a secret number in $Z_p$ and $c = a + b$. Alice has $a$ and Bob has $b$. Is there any methods to convert the modulo $p$ to some $q$, ($c<q$, $c<p$)? That is to say, $c = a' + b'$ in $Z_q$ and $a'$, $b'$ are known by Alice and Bob respectively.

  • $\begingroup$ Let $c = a + b \bmod p$ then we have $$c = a + b + p \cdot k$$ for some $k \in \mathbb Z$. Now, you want to keep $c$ in the new modulus $q$ with adjustment of $a$ and $b$ such that $$c = a' + b' + q\cdot k'$$ if you let the new $c' = c \cdot p$ it is easy... $\endgroup$
    – kelalaka
    Commented Dec 20, 2021 at 9:07

1 Answer 1


Assume that $p$ and $q$ are different primes (if $q$ divides $p$, for instance, the problem is trivial). Modulus conversion is usually not a simple task in the context of secret-sharing. The most common use-case for this type of primitives is, for example, taking a bit $b\in\{0,1\}$ that is secret-shared over a large prime $p$ as $b = a+b\bmod p$, and turning it into binary additive shares $b = a'+b'\bmod 2$ (which is ultimately $b = a'\oplus b'$. This has many applications, for instance, when you want to deal with non-arithmetic operations in Secure Multiparty Computation (e.g. secure comparisons, truncations, mathematical functions, etc.)

Most approaches to the task of secure conversion follow this technique. Let us denote $[x]_p$ when a value $x$ is secret-shared modulo $p$. Our goal is to obtain $[x\bmod q]_q$. Assume the parties already have shares of a random value $r$, unknown to either party, using both moduli $p$ and $q$. In other words, assume the parties have $[r]_p$ and $[r]_q$. Then the parties can proceed as follows:

  1. Compute locally shares of $x-r$ modulo $p$ by subtracting locally their shares of $x$ with their shares of $r$.
  2. Send their shares of $x-r$ to each other so that each party learns $x-r$. This keeps $x$ hidden because it is being masked by $r$, which is uniformly random and unknown to any party.
  3. One of the parties adds $(x-r\bmod q)$ to his/her share of $r$ modulo $q$, which leads to $[r]_q + (x-r) = [x\bmod q]_q$.

This assumes the parties have access to the pair $([r]_p, [r]_q)$, but in many cases this is not easy to get. For example, if $q=2$, some techniques that might be useful can be found here. All of this gets even trickier when active security gets into the picture.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.