2
$\begingroup$

In Maurer, Ueli. "Secure multi-party computation made simple." Discrete Applied Mathematics 154.2 (2006): 370-381. I have found the following technique for $k$-out-of-$k$ linear secret sharing:

scheme

And the note regarding the domain says this:

note

Is using as domain $\mathbb{Z}_p$ (additive group of integers modulo $p$) with $p$ non-prime secure? Does it make any difference if $p$ is prime or not? What is the most general definition for the domain (I do not get exactly the meaning of the note)? My guess is that $p$ can be any integer.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

What is the most general definition for the domain (I do not get exactly the meaning of the note)? My guess is that $p$ can be any integer.

In short, a domain is the input space. As said the input space can be any domain. Note that the secret $s$ is from the domain, too.

The note simply says that whatever the domain $\mathscr{D}$ is we can simply impose an addition operation on it. Order them, and number them starting from 0. Now, if the number of elements in the domain is $n = |\mathscr{D}|$ then it is equal to $\mathbb{Z}_n$ which is a cyclic group under addition.

Is using as domain $\mathbb{Z}_p$ (additive group of integers modulo $p$) with $p$ non-prime secure?

Yes.

Does it make any difference if $p$ is prime or not?

It doesn't make any difference. This secret-sharing doesn't need the multiplicative inverses. Any finite group can be safe. All we need is the group operations.

As Kodlu mentioned in the comments

This secret scheme can also be defined on the multiplicative groups where the inverse exists naturally. Take each $s_i$ for $1\leq i\leq k-1$ random from the domain and calculate $$s_k = s \cdot s_1^{-1} \cdot s_2^{-1} \cdots s_{k-1}^{-1}$$

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ And this domain can be any finite group, it can even be a multiplicative group, where you could use the multiplication operation to define the shares as $s_i$ for $1\leq i\leq k-1$ and $s_k=s \cdot s_1^{-1} \cdot s_2^{-1} \cdots s_{k-1}^{-1}$. $\endgroup$
    – kodlu
    Dec 12, 2020 at 21:32
  • 1
    $\begingroup$ @Lorenzo it seems one needs a ring there, I don't see the multiplicative inverse, since $s_i t_j$ is multiplied and shared with the 5.3. Next, all need is the Ring properties. $\endgroup$
    – kelalaka
    Dec 12, 2020 at 22:25
  • 1
    $\begingroup$ Thanks. So, requiring a ring allows to use for example $\mathbb{Z}_p$ with sum and multiplication as operations and $p$ being anything. Instead, requiring a field adds the constraint of $p$ beng a prime, since $\mathbb{Z}_p$ does not guarantee that multiplicative inverses exist when $p$ is not prime. However, since we do not use multiplicative inverses for secure multiplication, the less restrictive domain is a ring (moreover, it may be useful to do not restrict $p$ being a prime, but instead $2^{8l}$ for some integer $l$, if you work with bytes). Does it make sense? $\endgroup$
    – Lorenzo
    Dec 12, 2020 at 23:15
  • 1
    $\begingroup$ If you want to work on $Z_p$. For every prime power, there is also a field. 2^{8\ell} is an extension field of $\mathbb{F}_2$, more specifically binary extension field. Yes a ring seems enough. $\endgroup$
    – kelalaka
    Dec 12, 2020 at 23:28
  • 1
    $\begingroup$ Can you guarantee that every element has an inverse $\mathbb{R}_{2^{8l}}$? You should concentrate on the question. That makes another post! $\endgroup$
    – kelalaka
    Dec 12, 2020 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.