A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod $p$, where $a_{0, 1} = a_{1,0}$ and $p$ is a large prime number.

  • From the origional polynomial $ F(x, y)$, the server generates $n$ univariate polynomial shares as $f_{x_i}(y)=F(x_i,y)$ , where 1 ≤ $i$$n$, and $x_i$ is private (noboday knows it except the server) and distinct number for each node $i$.

  • Each node $i$ has a distinct public number $r_i$, where 1 ≤ $i$$n$ and every node else knows this number as it's public

Now, Let's say $node$ $i$ has got its own share $f_{x_i}(y)$ and $node$ $j$ has got $f_{x_j}(y)$ , where $x_i \neq x_j$, as said earlier.

The question is:

Utilizing the symmetric property of the original bivariate polynomial and Using their own polynomial shares together with other's public numbers, how can $node$ $i$ and $node$ $j$ ,$i \neq j$, establish a pairwise shared key/value such that: $ k = f_{x_i}(r_j)$ =$f_{x_j}(r_i)$ holds???

$Hint$: node $i$ evaluates its own polynomial share using node $j$'s public number and node $j$ evaluates its own polynomial share using node $i$'s public number. Is there any trick to make them get the same value? and How?

I appreciate your help

  • 1
    $\begingroup$ This looks like homework. What have you tried / where are you stuck? $\endgroup$ – puzzlepalace Mar 14 at 16:43
  • $\begingroup$ Actually, I got stuck in making $ f_{x_i}(r_j)$ =$f_{x_j}(r_i)$ holds. I couldn't make it hold with pure algebra since they are both generated using private value. So, I tried adding and using the approach of homomorphism property $(f + g)r = f(r) + g(r)$. However, it still doesn't solve the problem and moreover, the node becomes vulnerable to node capture attack $\endgroup$ – A. AZEMi Mar 18 at 9:35

Your Answer

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

Browse other questions tagged or ask your own question.