# Baek and Zheng’s Threshold Cryptosystem - limit on threshold?

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:

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?

• This appears to be a precision problem. Need to figure out how to solve this with PBC. – sumo Jan 21 '18 at 8:01
• 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. – Ido May 15 '18 at 12:09

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.