3
$\begingroup$

I am trying to build a cryptographic system that has several components and ran into a problem with a secret sharing scheme.

Let $v$ be a value we are interested committing to. I generate a commitment $P = aG + vH$ where $a\in \mathbb{Z}_q$ , $G$ and $H$ are generators of that group (Pedersen commitment scheme, if given $a$ someone can derive the value $v$).

Now lets assume I want to break $a$ (lets call it the blinding key) to $n$ shares using shamir secret sharing scheme where $k$ shares can produce $a$ ($k,n$ sharing scheme). so if $P$ is publicly known, is there a way where players who received a share can verify that the share they got actually produce $a$ without uncovering $a$? meaning that they know the combined shares can generate the blinding key.

I know that there exist a scheme for verifying that all shares are derived from the same polynomial (Paul Feldman's scheme) but what can prevent the possibility of an adversary calculating and distributing shares derived from some randomly generated and unrelated polynomial (where the secret is $c\neq a$)?

$\endgroup$
  • $\begingroup$ I think that would be a contradictory property: only one share (assuming $k>1$) cannot reveal anything about the particular value $a$. Put differently, a particular share should be a possible share of any value. $\endgroup$ – Daniel Jan 4 '18 at 13:53
  • $\begingroup$ if that is true. then there are no secured secret sharing in the malicious adversary model? or am i missing some point? $\endgroup$ – Shak Jan 4 '18 at 15:04
  • $\begingroup$ 'Pedersen commitment scheme, if given $a$ someone can derive the value $v$'; actually, that's not how Pedersen commitments work. And, it would appear to be nontrivial to modify it to include that property (and still be secure); in the current Pedersen scheme, if you can rederive $v$ given $P - aG$, you can compute the discrete log of $G$ to the base $H$ (and the whole binding aspect of Pedersen falls apart) $\endgroup$ – poncho Jan 7 '18 at 18:10
5
$\begingroup$

The obvious way to do this is to do a secret derivation on committed values, and have the dealer show that derived committed value is the same as the value he originally committed to.

For this, I'll assume that the secret sharing scheme is over the prime field $GF(q)$.

The dealer publishes the commitment $P$, and remembers the commitment value $v$.

And, when the dealer generates the share $i$ (for participant $i$), it generates the share id (which we'll assume is $i$), actual share value $a_i$ (which is the value of the secret polynomial evaluated at the share id $i$) and a commitment value $v_i$. It then gives the values $a_i, v_i$ to share holder $i$ secretly, and publishes the commitment $P_i = a_iG + v_iH$, as well as the share id $i$. The dealer also remembers all the $v_i$ values. When a shareholder gets his share, he can verify that his public commitment is consistent with the secret values he got.

Then, we select $k$ participants (you've already proved that the shareholders hold a consistent secret, and so it doesn't matter which set we pick).

Then, the actual secret value is $a = f_1a_1 + f_2a_2 + ... + f_ka_k \bmod q$, for some publicly computable values $f_1, f_2, ..., f_k$ (which depends on the actual set of shares). Hence someone, possibly the dealer, computes the value:

$$Q = f_1P_1 + f_2P_2 + ... + f_kP_k - P$$

which everyone can verify, as all the parameters are public.

The dealer can express this as:

$$Q = \sum f_i(a_iG + v_iH) \ - (aG + vH) = (\sum f_ia_i - a)G + (\sum f_iv_i - v)H$$

Where the dealer knows the values $f_i, v_i, v$. Hence, if $a = f_1a_1 + f_2a_2 + ... + f_ka_k$, then the dealer can generate a ZKP that he knows the discrete log of $Q$ to the base $H$; if not, then he cannot generate such a proof (because, if it knew that discrete log, it could (assuming it also remembered $a, a_i$) compute the discrete log of $G$ to the base $H$, which we assume was a hard problem.

$\endgroup$
  • $\begingroup$ Maybe I didn't understand your solution completely, it seems that this solution solves the shares verification problem but not the fact that the dealer needs to prove that the shares he had distributed are actual shares for the commitment's blinding key ($a$). I will edit the main question for clarification. $\endgroup$ – Shak Jan 7 '18 at 14:21
  • $\begingroup$ @Shak: actually, the dealer does prove that the shares that he published commitments to would combine to form the value ($a$) that he committed to (and each person can individually verify that the commitment that was published for him actually does correspond to the share he received). Where you maybe looking for something where the dealer needn't get involved? $\endgroup$ – poncho Jan 7 '18 at 19:18
  • $\begingroup$ It is ok for the dealer to be involved in the process (if there is any other scheme where the involvement of the dealer is not needed i would be happy to have a look at it). in the above scheme, is the function $f$ just some irreversible function or a function that is needed for the calculation (of getting the secret out of the shares?) $\endgroup$ – Shak Jan 11 '18 at 11:52
  • 1
    $\begingroup$ @Shak: $f_i = \prod_{j=1, j\ne i}^{k}\frac{x_j}{x_j - x_i}$ $\endgroup$ – poncho Jan 11 '18 at 15:32

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.