Secret sharing scheme verifiability

Question

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.

Answer 1

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.

Answer 2

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)$.