1
$\begingroup$

I am recently reading about multi party computation and its various existing protocols. From what I understand, all the arithmetic operations are performed over a field or a ring such that when two secret values, a and b, are used to perform secure computation c = f(a,b), the output of the MPC protocol is c mod P (for some modular P).

My question is, in real-life applications when we are performing MPC to get the desired output, this modulo operation may wrap multiple distinct shares into a single field/ring element. Such cases can occur when we are working with real-life applications. In such scenarios, how the accuracy of the original reconstructed output is ensured? The output c may exceed the value P, which will hamper the output as the original accepted output is c, not c mod P.

I am not sure but taking a higher/big P value may mitigate this issue. But in such scenarios what's the issue with directly working on original shares instead of the field elements after the secret sharing is performed?

I am very new to the concept of MPC and may have overlooked some crucial points while understanding the concept. Your help and clarifications are appreciated. Thank you.

$\endgroup$
2
  • 1
    $\begingroup$ It's the same problem for non MPC computations using machine words, such as 32 or 64 bit integers. $\endgroup$ Jul 4, 2023 at 16:34
  • $\begingroup$ yeah that's true. How to handle such situations mainly in the context of MPC to maintain the security as well as the accuracy of the MPC computation? $\endgroup$ Jul 4, 2023 at 17:02

1 Answer 1

0
$\begingroup$

Representing integers as field elements is something that comes up a lot in MPC and zero knowledge proofs. For example, zcash transactions have to show that the output amount doesn't exceed the input amount(s): $$ \mathsf{in}_1 + \ldots + \mathsf{in}_k \geq \mathsf{out} $$ where all the values are mod $p$ for some prime $p$.

So how does zcash make sure overflow doesn't happen? It just adds extra constraints requiring that $0 \leq \mathsf{in}_i < \lfloor p/k \rfloor$ for all $i$.

Adding these simple checks, often called "range proofs" is a common technique to ensure your values don't wrap around the modulus by accident. There's a good amount of research into optimizing range proofs, since they can be somewhat expensive in terms of constraints/gates.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. From what I understand wrapping occurs when a secret value exceeds the bounds of a finite field used in the computation and "range proofs" can be used to prevent secret values from wrapping. So, what if the secret value exceeds the value P? If the value is somewhat changed to a smaller value, then the accuracy of the output gets hampered. How accuracy can be handled in such scenarios? Can you please provide me with some supporting papers of documents that can clear this confusion of mine? $\endgroup$ Jul 4, 2023 at 17:03
  • $\begingroup$ Sure thing. The answer to "what about the initial values" is you simply bound the initial values too. Either by proof, or by definition in the system. As for supporting docs, this meta-paper might be a good starting point. They mention MPC twice in their Applications section, and have refs. $\endgroup$
    – rozbb
    Jul 12, 2023 at 4:07

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.