0
$\begingroup$

I have read SPDZ family protocol, the domain of the spdz_1 in 2012 is $\mathbb F_{p^k}$. Later mascot'16 supports both $\mathbb F_p$ and $\mathbb F_{2^k}$, where $p=2^k+u$.

I want to know the difference between the protocol in $\mathbb F_p$ and in $\mathbb F_{2^k}$. The reason maybe that spdz_1 use SHE, which only supports the characteristic of prime $p$, but the OT used in mascot support both $\mathbb F_p$ and $\mathbb F_{2^k}$.

What's more, what does $\mathbb F_{p^k}$ mean, I have seen field $\mathbb F_p$ mostly.

And, what's the difference between the field $\mathbb F_{2^k}$ and the ring $\mathbb Z_{2^k}$ ?

$\endgroup$
2
  • $\begingroup$ The last two parts of the question should be dealt with first: "what does $\mathbb F_{p^k}$ mean" and (paraphrasing) "what's a field versus a ring". Any text on Galois Field will tell. $\endgroup$
    – fgrieu
    Jul 30, 2022 at 8:18
  • $\begingroup$ Aside from ring vs field, the reason why you can't use a ring in SPDZ is due to existence of zero divisors which gives the adversary a higher probability of cheating during the MAC check protocol. $\endgroup$
    – lamba
    Jul 30, 2022 at 20:16

2 Answers 2

1
$\begingroup$

Ring is defined as a mathematical structure where the elements of its set are equipped with the operations addition and multiplication, as well as an additive inverse (for subtraction), but not necessarily division.

Field has multiplicative inverse and division, so technically, field is a special case of ring.

Link to Citizendium

The superscript on the subscript (that is, the $k$ in $\mathbb{F}_{p^k}$ and $\mathbb{Z}_{p^k}$) indicates the number of terms of an element. In this context, fields and rings work quite like polynomials. The value of the element is the sum of the each term multiplied by $x^i$ where $x$ is an abstract symbol, and $i$ is the 0-based index of the term with $x^0 = 1$.

It can be shown that the number of elements in any finite field is of the form $p^k$ where $p$ is prime and $k$ is a strictly positive integer.

$\endgroup$
4
  • $\begingroup$ I apologize for the hasty and clumsy merge process, such that this answer now is about only the last item of the question, when it did answer the original question in full. $\endgroup$
    – fgrieu
    Jul 30, 2022 at 8:19
  • $\begingroup$ Is there anything that I should or can do now? @fgrieu $\endgroup$
    – DannyNiu
    Jul 30, 2022 at 10:49
  • $\begingroup$ I don't think I can undo the mess I created. Again, sorry. Perhaps, make the answer more complete by discussing $\mathbb F_{p^k}$ (or let me do that as expiation!). Note: subtraction between any two elements of a ring is well-defined. $\endgroup$
    – fgrieu
    Jul 30, 2022 at 13:39
  • $\begingroup$ @fgrieu I'm not good at explaining maths concepts (since I rarely formally learn them if I can use them without obstacle), I hope you can help me with the contents of the answer. $\endgroup$
    – DannyNiu
    Jul 30, 2022 at 13:53
0
$\begingroup$

About answering the question: "And, what's the difference between the field $\mathbb{F}_{2^k}$ and the ring $\mathbb{Z}_{2^k}$ ?"

You can think as an example for $k=2$.

Then, $\mathbb{F}_4$ can be defined as $\mathbb{F}_4 = \{0,1,x,x+1\}$. This definition comes from the fact that we get $\mathbb{F}_2$ (that is basically $\mathbb{Z}_2$) and we demand $x^2+x+1 = 0$.

So, for example $x^2+x+1=0 \iff x^2=-x-1=x+1$

$\mathbb{Z}_4$ however is defined as $\mathbb{Z}_4 = \{0,1,2,3\}$, the integers modulo 4.

We can see that $\mathbb{F}_4$ is a finite field of order(size) 4 and it "obeys" all the rules that a field demands, while $\mathbb{Z}_4$ is not a field because for example, not all elements of the ring have an inverse.

It is easy to get confused from those two because when $n$ is prime, $\mathbb{F}_n$ and $\mathbb{Z}_n$ "are the same" but generally these two are very different.

$\endgroup$

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.