2
$\begingroup$

This secret sharing scheme takes place in the polynomial ring over a finite field $F_p[x]$, $p$ being a large prime, in the following simplified way:

  1. The dealer chooses a private polynomial $f(x)$.

  2. Every participant $P_i, i \in N$, has a public polynomial $m_i(x)$, with $deg(m_i(x)) \leq deg(f(x))$.

  3. The dealer computes the private secret share of $P_i$ as $s_i(x) = f(x) \mod m_i(x)$ and sends it to $P_i$.

I need a way for $P_i$ to verify that the private secret share $s_i(x)$ was well calculated.

Suppose there is a polynomial commitment scheme that allows you to commit to a certain polynomial $p(x)$ as $p(\beta)G$.

$\beta$ is a value unknown to everyone (as well as $p(\beta)$), including the dealer, and $G$ is a point generator of an Elliptic Curve over $F_p$.

This polynomial commitment scheme also allows to produce a proof evaluation of a certain committed polynomial, i.e., you can prove that a certain point (a, b) belongs to the committed polynomial.

With this, my idea to verify the private secret share $s_i(x)$ is the following:

  1. Since $f(x) = m_i(x)k_i(x) + s_i(x)$, the dealer commits to $f(x)$ and $k_i(x)$ as $f(\beta)G$ and $k_i(\beta)G$, respectively, and sends them to $P_i$.

  2. $P_i$ asks for an evaluation of a random $z$.

  3. The dealer sends $f(z)$ and $k_i(z)$ to $P_i$, along with the proofs that they belong to the committed polynomials.

  4. $P_i$ verifies that $f(z) = k_i(z)m_i(z) + s_i(z)$.

My thinking was that two polynomials $p(x)$ and $p'(x)$, with degrees $n$ and $m$, can have at most $max(n, m)$ intersections, so if the dealer commits to polynomials $f'(x)$ and/or $k'(x)$ instead of $f(x)$ and/or $k(x)$, the probability that the equation holds for those committed polynomials, is negligible.

I don't know how to prove or disprove this, so I would appreciate if anyone can help me.

$\endgroup$
2
  • $\begingroup$ Instead of doing the above (which, as Tylo stated, leaks a lot of information about f), while don't you use Pedersen commitments; you give a Pedersen commitment for each coefficient of $f$, and then, for each $i$, a zero knowledge proof that $\forall x : f(x) = s(x) + c(x)*m_i(x)$ for some polynomial $c$ (by sending commitments for the coefficients of $c$, and sending a separate Schnorr proof for each coefficient of $f$). A tad more work, but it really doesn't leak anything about $f$ $\endgroup$
    – poncho
    Feb 2 '20 at 17:48
  • $\begingroup$ What if the dealer sends f(z)G and k_i(z)G instead, along with proofs of their correctness? The problem with your solution is that ir doesn't scale well. $\endgroup$
    – Fiono
    Feb 2 '20 at 18:45
2
$\begingroup$

I am fairly certain, that your proposed secret sharing scheme is actually not secure in any way:

If a party receives $s_i(x)$, then the secret polynomial is of the form $f(x)=s_i(x)+m_i(x) \cdot r(x)$ for some polynomial $r(x)$. And that is not equivalent to all possible polynomials. Even worse: If you allow the parties to choose $m_i$ themselves and of arbitrary degree, the parties can choose it do that they basically get $f(x)$ in the clear.

Example: $f(x)$ has degree $d$, then $m_i(x)=x^{d+1}$ gives back $f(x)$. Even if the degree is restricted, not all polynomials are possible.

But even if we assume, the secret sharing was secure, then your proposed algorithm would break it:

If the party can verify if their share was created properly, then the party can use this very procedure to learn something about $f$ instead. For any secret sharing scheme, giving the parties additional knowledge on top of their individual share will most likely break the information theoretic security (and otherwise it has to be proven). And since you have no computationally hard problem at all in your construction, it can't even have computational security.

$\endgroup$
2
  • $\begingroup$ Yes, the degree of $f(x)$ must be equal or greater than $m(x)$'s. "Even if the degree is restricted, not all polynomials are possible." What do you mean? "If the party can verify if their share was created properly, then the party can use this very procedure to learn something about f instead." How? The dealer only reveals a point of $f(x)$. $\endgroup$
    – Fiono
    Feb 2 '20 at 15:08
  • 1
    $\begingroup$ If the polynomials have equal length, then choosing $s_i(x)=x^d$ reveals all coefficients except the first one. And that is some information about the secret polynomial, which must be impossible for a secret sharing scheme. But in general, if you use a self-made secret sharing scheme, it is your task to prove it's security. Regarding "the dealer only reveals a point of $f(x)$", exactly this restricts $f$ to only those polynomials where this point is given. And that is some information, which the party learns from the protocol. But again: It's your task to show that this doesn't break security. $\endgroup$
    – tylo
    Feb 3 '20 at 11:29
1
$\begingroup$

The secret sharing scheme you described seems to utilize Chinese Remainder Theorm. Your question I think is How to prove the correctness of generating $s_i(x)$ for the dealer? If so, I have a rough idea to prove it.

As we all known, a polynomial $p$ is determined by its coefficients $\{c_0,...,c_d\}$ and degree $d$. Thus, we have the following steps to prove the correctness of $s_i(x)$. Assuming that a trusted party is agreed to participate in this scheme.

  1. A trusted party generates some public parameters $\{g^{z^i}\}_{i\in[d]}$,$\{g^{\alpha * z^i}\}_{i\in[d]}$ where $\alpha$, $z$ are random values, and a verification key $\Omega=g^\alpha$.
  2. As you described in step 3 of the orignal scheme, the dealer computes $s(x)$ and then generates the following proof values: $\pi =\{ A:=g^{f(z)}=g^{\sum_{i=0}^d{c_i * z^i}},B:=g^{\alpha*f(z)}=g^{\sum_{i=0}^d{c_i * \alpha * z^i}},C:=g^{k(z)}=g^{\sum_{i=0}^d{c'_i * z^i}},D:=g^{\alpha*k(z)}=g^{\sum_{i=0}^d{c'_i * \alpha * z^i}}\}$.
  3. The dealer forwards $\pi$ and $s(x)$ to the participant.
  4. Receiving $\pi$ and $s(x)$, the participant check if the following equations are hold. $e(A,\Omega)=e(B,g), e(C,\Omega)=e(D,g), e(A,g)=e(C,g^{m(z)})*e(g^{s(z)},g)$.
$\endgroup$
1
  • $\begingroup$ Hup? The question was asked 1 year, 4 months ago, the answer I hardly typed was in vain. $\endgroup$
    – ming alex
    Jun 28 '21 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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