2
$\begingroup$

I have just completed an implementation of Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group by Baek and Zheng and am hitting a problem with high values of the threshold. Please forgive any mistakes below, I have minimal relevant math and notation knowledge and am learning as I go.

I am using a Haskell wrapper around PBC and so far I have been successful with the implementation on small value of $t <= 8$ and $n <= 100$. Unfortunately though anything with a larger $t$ means shares recombination fails. Taking the idea from a python implementation I found and given the dealer mechanism from the paper:

enter image description here

I've tried to reconstruct $x_0$ which fails for $length(a)>8$. Works great for $length(a)<=8$

Even a simple, non PBC version of $x_0$ reconstruction fails using simple values of $a$ e.g. $[10,20,30,40...150]$. Given the list of $x_0..x_n$ from the application of the polynomial on $a_0..a_{t-1}$ I used the Lagrange interpolation

$$\phi_i(xcoord)=\prod_{j\neq i}\frac{xcoord-xcoord_j}{xcoord_i-xcoord_j}$$

and summed the values of $\phi_i * x_i$ to get $x_0$. The shares I've selected are a subset of size $t$ of the list of numbers from the application of the polynomial above. The polynomial validates i.e. $a_0 == x_0$.

I've also tried the method specified in this explanation of Shamir's Secret Sharing but both seem to have the $t>8$ reconstruction problem (in fact the latter had a sign problem, for odd values of t that I could not resolve).

Does anyone have any thoughts on how to investigate further or even resolve? Could the use of the Barycentric form help fix this as per this answer?

$\endgroup$
  • $\begingroup$ This appears to be a precision problem. Need to figure out how to solve this with PBC. $\endgroup$ – sumo Jan 21 '18 at 8:01
  • $\begingroup$ Any luck so far? I haven't reviewed it yet, but you can take a look at the Honey Badger implementation of this crypto system - here. Please let me know if you solved your problem or if you even found out what it was - I'm also starting to work on implementing some variant of this scheme these days. $\endgroup$ – Ido May 15 '18 at 12:09
0
$\begingroup$

The problem (thanks for the prompt Ido) was the use of PBC's element_mul_si instead of element_mul. This caused the polynomial calculation to loose precision(by rolling over I think) on larger values of t.

I now use element_mul during polynomial calculation in this commit and it works perfectly. Python Charm does not use element_mul_si hence the issue does not show up in the HoneyBadger implementation of TCG.

$\endgroup$

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.