# How does the user check whether $y < M$ without knowing all shares?

CRT-based Verifiable Secret Sharing Scheme

In this paper, section 4 Verifiable Secret Sharing Scheme, the dealer phase and the combiner phase are as follows:

Dealer Phase

To share a secret $$d \in Z_{m_0}$$ among a group of $$n$$ users with verifiable shares, the dealer does the following:

1) The dealing procedure of the Asmuth-Bloom SSS to obtain the shares $$y_i = y \mod m_i$$ for each $$1 \le i \le n$$ where $$y = d+ Am_0 < M$$.

Note that the $$m_i$$'s are large primes where $$p_i = 2m_i + 1$$ is also a prime for $$1 \le i \le n$$.

2) Let $$N$$ be an integer whose prime factorization is not known by the users and the dealer.

Compute $$E(y) = g^ y mod P N$$ .Send $$y_ i$$ to the $$i^{th}$$ user secretly for all $$1 \le i \le n$$

3)The $$i^{th}$$ user checks $$g^ { y_{i} }≡ E(y) \mod p_i$$

to verify $$y_i = y \mod m_i$$ . Then he checks the validity of the range proof to verify $$y < M$$.

Combiner Phase

Let $$S$$ be a coalition gathered to construct the secret.

The share $$y_i$$ of user can be verified by the other users by the verification equation

$$g^ { y_{i}} ≡ E(y) \mod p_i$$

If all shares are valid then the coalition $$S$$ can obtain the secret $$d$$

In this scheme $$y$$ is private. So, after knowing all shares of $$y_i$$, users reconstruct the secret. But how to verify $$y_i = y \mod m_i$$ user checks the validity of the range proof to verify $$y < M$$ without knowing all shares of users.

Could you please explain how user can verify range

• As there are several schemes described in the linked paper, it would have been nice to write which one you are asking about. I assume it's the one of Fig. 4. In section 4.1 the authors say that they use Cao's non-interactive range-proof scheme as a black box, and refer their readers to the papers [4] by Boudot and [6] by Cao and Liu. Did you try reading these papers? – j.p. Feb 15 at 7:08