# How to convert the secret sharing modulus?

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, $$c)? That is to say, $$c = a' + b'$$ in $$Z_q$$ and $$a'$$, $$b'$$ are known by Alice and Bob respectively.

• 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... Commented Dec 20, 2021 at 9:07

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.