3
$\begingroup$

I am refering to Privacy Aware Incentive Mechanism to Collect Mobile Data While Preventing Duplication https://ieeexplore.ieee.org/document/7357616.

They claim to split secret $X$ into $X_s=\{x_0,\dots, x_n\}$ under a (2,n)-secret sharing scheme based on shamir's scheme, and compute $x_k'=\{x_k/X\}_{0\leq k\leq n}$ (in a cyclic group modulo p with generator g), and then they claim $g^{sk_i^{\sum^n_{k=1}x'_k}}=g^{sk_i}$

This entirely confuses me.

I am not sure about stackexchange policy in publishing paywalled paper, if following is against community policy I will delete them. However since more information is needed, following is the related part in the paper: enter image description here

reference 19 is C.-C. Yang, T.-Y. Chang, and M.-S. Hwang, “A (t,n) multi-secret sharing scheme,” Applied Mathematics and Computation, vol. 151, no. 2, pp. 483–490, Apr. 2004, doi: 10.1016/S0096-3003(03)00355-2., which as I understand it a Shamir's scheme's variation.

and the background enter image description here

and what confuses me and leads to this question: enter image description here

$\endgroup$
5
  • $\begingroup$ The sum of two shares will obviously be very different depending on which two shares you sum, and can't all end up being equal to the secret. $\endgroup$
    – Meir Maor
    Jun 17, 2022 at 4:20
  • $\begingroup$ @MeirMaor I totally agree with you, but this is a paper published on IEEE, so I am not sure if I misunderstood it or it is really wrong. $\endgroup$ Jun 17, 2022 at 12:00
  • $\begingroup$ paper is paywalled so I can't comment on what they meant. $\endgroup$
    – Meir Maor
    Jun 17, 2022 at 12:41
  • $\begingroup$ Do you know what this notation means $x_{k}^{\prime}=\left\{x_{k} / X\right\}_{0 \leq k \leq n}$? If yes I can handle the rest. $\endgroup$
    – tur11ng
    Jul 2, 2022 at 14:57
  • 1
    $\begingroup$ @JAAAY They don't explain it, I assume it is division. (Considering they take $x'_k$'s sum to be 1 I think it should be division. The related part in the paper is added to question. $\endgroup$ Jul 3, 2022 at 15:18

2 Answers 2

1
$\begingroup$

I quote the specific part of the paper you are mentioning :

  1. Picks $X, r$ randomly
  2. Splits $X$ into $n$ numbers using $(2, n)$-secret sharing scheme [19], $\mathcal{X}_{s}=\left\{x_{0}, x_{1}, x_{2}, \ldots, x_{n}\right\}$. This means any two or more $x$ can rebuild $X$ by combining using secret sharing computation: $\exists \partial$ in $\mathcal{X}_{s}, X=\sum_{\ell=1}^{2 \leq \ell \leq n} \partial_{\ell}$
  3. Computes $x_{k}^{\prime}=\left\{x_{k} / X\right\}_{0 \leq k \leq n}$
  4. Computes a set of pseudonyms $\mathcal{P}=\left\{p_{k}\right\}_{1 \leq k \leq n}, p_{k}=$ $s k_{i}^{x_{k}^{\prime}} \cdot r \in \mathbb{Z}_{q}$
  5. Makes pseudonym verification value $\mathcal{V}$ : $\mathcal{V}=\left\{v_{1}, v_{2}\right\}, v_{1}=g^{r}, v_{2}=s k_{i}^{x_{0}^{\prime}}$

Now let's focus on the first part of your question.

They claim to split secret $X$ into $X_{s}=\left\{x_{0}, \ldots, x_{n}\right\}$ under a $(2, n)$ secret sharing scheme based on shamir's scheme

The Shamir Secret Sharing protocol (n,t) is dead simple. If you have $n$ players and a secret $s$ and you want for them to only be able to get access to $s$ only if $k>t$ of them collaborate together. Then you can simple pick a random polynomial of $t-1$ degree and set its constant term equal to $s$. Then you sample this polynomial at $n$ points $x_1, x_0, \ldots, x_n$, not including $x=0$, and send $(x_j, p(x_j))$ (this is called the share of each player) to the player $j$. Then if $k>t$ of them reveal their shares to each other they can solve a $t \times t$ system of linear equations described by a invertible matrix $t \times t$ matrix.

and compute $x_{k}^{\prime}=\left\{x_{k} / X\right\}_{0 \leq k \leq n}$ (in a cyclic group modulo $\mathrm{p}$ with generator $\mathrm{g}$ ), and then they claim $g^{s k_{i}^{\sum_{k=1}^{n} x_{k}^{\prime}}}=g^{s k_{i}}$

I'm not sure I will answer correctly this one because of some weird notation used.

In my opinion the tricky part here is to understand what $x_{k}^{\prime}=\left\{x_{k} / X\right\}_{0 \leq k \leq n}$ means. I will agree with OP that the symbol \ means division, so let's rewrite the above $x_k' = \dfrac{x_i}{X}$.

Now of course we can prove the above,

$$ \begin{align} e\left(v_{1}^{n}, p k_{i}\right) & \stackrel{?}{=} e\left(g, g \prod_{k=1}^{n} p_{k}\right) \\ &=e\left(g, g^{r \cdot n \cdot s k_{i}^{\sum_{k=1}^{n} x_{k}^{\prime}}}\right) \tag{from the bilinear property}\\ &=e(g, g)^{r \cdot n \cdot s k_{i}} \tag{from step 2 of the protocol it derives that $\sum_{k=1}^{n} x_{k}^{\prime} = 1$} \end{align} $$

BUT this is based on what the paper says. I do think that they have a mistake in the notation. Please correct me if I'm wrong. If you take a look at the paper they reference for secret sharing, the secret reconstruction is done using interpolation. I don't see any interpolation in this phrase of step 2 : $\exists \partial$ in $\mathcal{X}_{s}, X=\sum_{\ell=1}^{2 \leq \ell \leq n} \partial_{\ell}$. In my opinion I think they wanted to express the following:

$$ \forall x_k \in \mathcal{X}_{s}, \forall \ell, 2 \le k \le n, \exists \partial_{\ell} : X=\sum_{\ell=1}^{k} \partial_{\ell}x_{\ell} $$

and now you can rewrite the above as

$$ \sum_{k=1}^{n} \partial_{k} x_{k}^{\prime} = \sum_{k=1}^{n} \partial_{k} \dfrac{x_k}{X} = 1 $$

since secret sharing shares are homomorphic (this is the case in most schemes and this is why they don't explicitly reference it) for constant multiplication. To sum up, we basically reconstruct the secret $X$ and divide by the secret $X$.

Lastly, to answer your question that is stated in the title. I don't think this is the case. Based on their referenced I do think they have made a mistake.

$\endgroup$
6
  • $\begingroup$ Please correct me if you think I have made any false assumptions. $\endgroup$
    – tur11ng
    Jul 3, 2022 at 17:46
  • $\begingroup$ I think your guess is really convincing. Thank you! $\endgroup$ Jul 4, 2022 at 18:42
  • $\begingroup$ However, on second thought, do you think it is possible to fix it and make it right? I tend negative. $\endgroup$ Jul 4, 2022 at 18:47
  • $\begingroup$ What do you mean make right? Notify the paper publisher to publish an update on the paper? If this is what you mean, I have tried to do it multiple times, no one has ever replied to a single email :P $\endgroup$
    – tur11ng
    Jul 5, 2022 at 17:28
  • $\begingroup$ I mean fix the mistake to fulfill the proposed scheme and make it work. I pretty like the idea and that's why I bother to ask it here even when I almost sure it is wrong. $\endgroup$ Jul 6, 2022 at 18:27
1
$\begingroup$

I can't answer the question in the text of the this question, but have an answer to the question in the title.

It is not the sum of two shares but instead a weighted sum of two shares that is equal to the secret in a $(2,n)$ Shamir secret sharing scheme.

Recall that a $(2,n)$ Shamir secret sharing scheme begins with a degree-$1 = 2-1$ polynomial $X + \beta x$ where $X$ is the secret and $\beta$ a randomly chosen nonzero element if the field. The $n$ shares then are $$x_i = X + \beta \alpha_i, 1 \leq i \leq n,$$ where $\alpha_1, \alpha_2, \ldots, \alpha_n$ are $n$ distinct nonzero elements of the field. Given any two shares, say $x_j$ and $x_k$, the reconstruction corresponds to solving the system of linear equations \begin{align} X+\beta \alpha_j &= x_j,\\ X+\beta \alpha_k &= x_k, \end{align} for $X$. It is easy to get $$X = \left(\frac{\alpha_k}{\alpha_k - \alpha_j}\right)\cdot x_j +\left(\frac{-\alpha_j}{\alpha_k - \alpha_j}\right)\cdot x_k,$$ that is, the secret equals the weighted sum of $x_j$ and $x_k$ (with weights as shown above) and not just the sum.

Turning to the text of hetbquestion, it is not clear what $p$ is in this problem. Is the field $\mathbb F_p$? or is $p$ merely the characteristic of the field $\mathbb F_{p^m}$, or is $p$ just an arbitrary prime larger than $n$. There is a parameter $s$ which is wholly unexplained. The procedure seems to be to compute $x_k^\prime = \dfrac{x_k}{X}$ which seems to require foreknowledge of the secret $X$, etc. So it is not easy to address the queries in the text of this question.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! Sorry for not addressing the question clearly. p is the field $F_p$. Yes the procedure uses secret $X$ to generate the division, $sk$ is something generated independent to this secret sharing scheme. As I understand they believe sum of more than 2 secret share divided by $X$ is 1, and that's why I summarize it to the question topic it is now. $\endgroup$ Jun 27, 2022 at 14:17
  • $\begingroup$ I have added some part of the paper to the question. $\endgroup$ Jul 3, 2022 at 15:22

Your Answer

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

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