# Problem with applying threshold scheme

For a report on threshold signature schemes, I have to explain a threshold signature scheme and give a simple example with numbers.

A threshold signature scheme is a scheme in which a network of n nodes can only sign a message when at least t of the n nodes agree to sign the message.

I'm trying to understand the scheme presented in A Length-Flexible Threshold Cryptosystem with Applications by Ivan B. Damgård and Mads J. Jurik. I'm especially interested in the scheme they present on page 9 (this is from page 9 in pdf I linked, slightly edited to be clearer):

I'm trying to follow the procedure with small numbers to see it in action. Everything goes well, until I try to recover $d$ from the $d_i$. I understand that some variation of Shamir's Secret Sharing algorithm is used (use $k$ known pairs of the form $(x_i, f(x_i))$ to find $f$, or more specifically $f(0)$, where $f$ is a polynomial of degree $k - 1$). $f$ can be found using Lagrange interpolation polynomials. I understand the general idea of Lagrange interpolation polynomials, but I don't see how exactly this idea is applied in this scheme.

What I have so far: I choose $w = 4$, $t = 3$, so we look at a system with 4 nodes and a threshold of 3. I take the message m to be 81409. Further, I choose $p' = 5, q' = 11$, so $p = 11, q = 23$ and $n = pq = 253$, $\tau = p'q' = 55$. I pick $\alpha = a_0 = 0$ and the other coefficients of the polynomial $f$ are $a_1 = 1, a_2 = 2, a_3 = 3$. We find the 'secret shares':
$\alpha_1 \equiv f(1) \equiv 48$
$\alpha_2 \equiv f(2) \equiv 76 \equiv 21$
$\alpha_3 \equiv f(3) \equiv 144 \equiv 34$
$\alpha_4 \equiv f(4) \equiv 270 \equiv 55$
(I am pretty sure these need to be reduced modulo $\tau = 55$, though this is not explicitly mentioned in the paper: it may be implied by choosing the coefficients of $f$ in $\mathbb{Z}_\tau$). Further, we can find $h_i$, but they are only used for a proof, and I want to skip these for now (the purpose of the proof is not entirely clear to me). We also need to pick a square $g$ from $\mathbb{Z_n^*}$. I pick $g \equiv 49^2 \equiv 124$. We also have $h = g^\alpha \equiv 124^{42} \equiv 163\ (\text{mod } 253)$.

For the public key PK we have: $PK = (n, g, h) = (253, 124, 163)$.

So far, so good. Moving on to the encryption:

Since $m = 81409$, this means that s needs to be at least 3 (I assume $m \in \mathbb{Z}_{n^s}$ means $m < n^s$), and I take $r = 25$. The ciphertext is pretty straightforward to compute. The only weird thing here is a $\delta$ that isn't defined before. Later, it is stated that $\delta$ is chosen to make $\lambda_i^S$ an integer. For $w = 4$ it seems that $\lambda_i^S$ is integer anyway, so I chose $\delta = 1$ (which may or may not be correct). Just calculating the expressions I find: c = (G, H) = (177, 1454334069)

Moving on to the decryption, this is were things start to get confusing. I find:
$d_1 \equiv 177^{2 \cdot 48} \equiv 12$
$d_2 \equiv 177^{2 \cdot 21} \equiv 100$
$d_3 \equiv 177^{2 \cdot 34} \equiv 210$
$d_4 \equiv 177^{2 \cdot 50} \equiv 177\ (\text{mod}\ 253)$

Let's say S = { 1, 2, 3 }. Then for the $\lambda_i$'s I find:
$\lambda_1^S = \frac{2}{2-1} \frac{3}{3-1} = \frac{2}{1} \frac{3}{2} = 3$
$\lambda_2^S = \frac{1}{1-2} \frac{3}{3-2} = \frac{1}{-1} \frac{3}{1} = -3$
$\lambda_3^S = \frac{1}{1-3} \frac{2}{2-3} = \frac{1}{-2} \frac{2}{-1} = 1$

The wording in the paper suggests that $\prod d_i^{2\lambda_i^S}$ means $\prod_{i \in S} d_i^{2\lambda_i^S}$

So I find $d \equiv d_1^{2\lambda_i^s} \cdot d_2^{2\lambda_2^S} \cdot d_3^{2\lambda_3^S} \equiv 12^6 \cdot 100^{-6} \cdot 210^2 \equiv 12^6 \cdot (100^{-1})^6 \cdot 210^2 \equiv 12^6 \cdot 210^6 \cdot 210^2 \equiv 100\ (\text{mod}\ 253)$. But this should be equal to $G^{4\cdot \alpha} \equiv 177^{168} \equiv 232$ and $h^{4r} \equiv 163^{100} \equiv 232$ and it's not...

EDIT: The paper was obviously based on Practical Threshold Signatures by Victor Shoup. The explanations there are clearer. For example, there $\delta$ is defined to be $n!$. This may be the error. Additionally, the $\lambda$'s are defined differently, and I think this may be a problem as well.

• Does not the first paper mention that the (polynomial) values of of $F(X)$ are taken modulo $n^s m$ resulting in: $F(X) = \sum\limits^{k-1}_{i=0} a_i X_i \pmod{n^s m}$? (line 5 of Key generation in the paper) – Fleeep Oct 6 '15 at 5:12
• I am sorry, I linked the wrong paper. In the paper I linked it does indeed say that. Link is fixed now. – Ruben Oct 6 '15 at 11:58