Score:0

Multi party computation over ring and fields

ma flag

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.

gb flag
It's the same problem for non MPC computations using machine words, such as 32 or 64 bit integers.
Sumana bagchi avatar
ma flag
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?
Score:0
br flag

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.

Sumana bagchi avatar
ma flag
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?
rozbb avatar
br flag
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](https://arxiv.org/abs/1907.06381) might be a good starting point. They mention MPC twice in their Applications section, and have refs.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.