Short answer

• If the two moduli come from the same prime and one field is a subfield of the other (GF(p^m) ⊆ GF(p^k) with m | k), then conversion is trivial and non‑interactive: just re‑interpret the shares in the larger field.

• In all other cases (different primes, no subfield relation, or rings Zp vs Zq), there is no purely local, linear, black‑box way to convert an LSSS sharing over Zp (or GF(p^m)) into an LSSS sharing over Zq that preserves the secret for all inputs. You need interaction and some correlated randomness. A standard, perfectly secure way uses one public opening of a masked value and a single secure comparison bit to correct wraparound.

A general perfectly secure conversion protocol

Goal: given an LSSS sharing of x ∈ {0,…,p−1} modulo p, produce an LSSS sharing of the same integer x modulo q (if q < p this is necessarily x mod q).

Assumptions:

• Any linear secret sharing scheme (Shamir, additive, etc.) over Zp and Zq.
• Preprocessing provides a pair of sharings of the same random integer r ∈ {0,…,p−1}, one over Zp and one over Zq. (This can be done once per conversion by any standard MPC/VSS mechanism, or by a dealer; it is independent of x.)
• Parties can do a single secure comparison of a public value with a secret (perfectly secure comparisons can be done in honest‑majority information‑theoretic MPC; computationally secure comparisons can be done via garbled circuits, etc.).

Protocol:

1. Mask-and-open modulo p.

   • Locally add the Zp-sharing of r to the Zp-sharing of x to obtain a sharing of x+r (mod p).
   • Open c := (x + r) mod p to the parties (public).

   Since r is uniform in Zp and independent of x, c is uniform in Zp and reveals nothing about x (perfect privacy).

2. Move to modulus q.

   • Using the Zq-sharing of r, locally compute a Zq-sharing of y := c − r (mod q).

   At this point y ≡ x − k p (mod q), where k ∈ {0,1} is the carry/overflow bit indicating whether x+r ≥ p.

3. Correct the wraparound.

   • Compute the (secret) bit k := [c < r] via a single secure comparison between public c and secret r (interpreted as integers in {0,…,p−1}).
   • Locally add k·p (as a public constant times a secret bit) to y over Zq: y := y + k·p (mod q).

Output: y is now an LSSS sharing of x over Zq.

Correctness:

• Write x+r = c + k p with k ∈ {0,1}. Then y ≡ c − r + k p ≡ x (mod q), always.

Security (perfect):

• The only opened value is c, which is uniform in Zp and independent of x. The comparison is run securely and reveals nothing (its output k stays secret). All other steps are local linear operations on secret shares.

Notes and special cases

• If q | p (e.g., p = p0^m and q = p0^n with the same prime p0 and n ≤ m), then p ≡ 0 (mod q), so the correction term k·p vanishes modulo q. In that case, Step 3 (comparison) is unnecessary: y := c − r (mod q) already equals x (mod q). This gives a one‑open, no‑comparison, perfectly secure conversion.

• If the fields share a subfield: When GF(p^m) ⊆ GF(p^k) (same base prime and m | k), you can non‑interactively “convert” by just reinterpreting the shares in the larger field. Any LSSS defined over GF(p^m) remains an LSSS over GF(p^k), and the secret is preserved exactly. The reverse direction (from larger to smaller field) only works if the shared values are guaranteed to lie in the subfield.

• If you accept statistical (not perfect) security: You can eliminate the comparison by choosing r from a larger range so that wraparound is negligible, and proceed with y := c − r (mod q). This is the standard “mask large enough to avoid carry with high probability” trick; it yields a negligible failure probability but not perfect security.

• Impossibility of “purely local” conversion in general: Without some interaction (e.g., opening a masked value and/or computing a carry bit) or a field embedding, there is no general way to transform shares over Zp into shares over Zq for arbitrary p, q while preserving the secret for all inputs. Intuitively, when p and q are unrelated, the wraparound information (the carry k) is essential to map residues mod p to residues mod q; extracting it requires interaction.

References (pointers to related techniques)

• General perfect MPC (e.g., BGW) lets you compute the above comparison perfectly with honest majority.
• If computational security is acceptable, the comparison can be implemented by a small garbled circuit or HE-based subprotocol; this is the approach in mixed-protocol frameworks.
• For special conversions (e.g., between Z2^k and Zp, or bit-decomposition and comparisons), see: Catrina and de Hoogh, Improved Primitives for Secure Multiparty Integer Computation (2010); Nishide and Ohta, Multiparty computation for interval, equality, and comparison without bit-decomposition (PKC 2007); and mixed-protocol frameworks like ABY/ABY3 for practical instantiations.

Summary

• Trivial and non-interactive if there is a field embedding (same prime, subfield relation).
• Otherwise, perfectly secure conversion is possible and simple: one public opening of x+r mod p plus a single secure comparison to correct the carry, given correlated sharings of the same random r in both moduli.