I am going over the paper https://verifiable-timed-signatures.github.io/web/assets/paper.pdf and on page 5, it says the following:

Suppose I have a t-out-of-n threshold sharing scheme for the secret $\sigma=H(m)^\alpha$. The first $t-1$ shares are defined as $\sigma_i = H(m)^{\alpha_i}$, where $\alpha_i$ are sampled randomly in the field.

Then, for $i \in \{ t, t+1, \dots, n \}$, we defined the shares as follows: $\sigma_i = \left(\frac{\sigma}{\prod_{1\leq j \leq t-1} \sigma_j^{l_j(0)}}\right)^{l_i(0)^{-1}}$

where $l_i()$ is the i-th Lagrange polynomial basis.

My question is: what are the $l_i$ exactly? Because to calculate each $l_i$, wouldn't I need to know at least $t$ $\sigma_i$? It seems like I am using information I don't have it to calculate each $\sigma_i$.


1 Answer 1


Let $L$ be a Vector Space of Polynomials of $x$ of degree $\leq n-1$ with coefficients in some field $\mathbb{K}$.

Normally we define $$l_i(x) :=\prod _ {{j=1},{j\neq i}}^n \frac{x-a_j}{a_i-a_j}$$ as the Lagrange polynomial basis. Note that

$$l_i(0) :=\prod _ {{j=1},{j\neq i}}^n \frac{-a_j}{a_i-a_j}= (-1)^{n-1}\prod _ {{j=1},{j\neq i}}^n \frac{a_j}{a_i-a_j} $$ is a constant and it suffices to compute the expression in the question given only the first $t-1$ $\sigma_i$'s.

  • $\begingroup$ That makes sense. So from what I understand, the coefficients of the polynomial (or the $l_i(0)$) would be part of the public parameters of the protocol? $\endgroup$
    – sadtroll
    Apr 15 at 0:43
  • 1
    $\begingroup$ yes they would be $\endgroup$
    – kodlu
    Apr 15 at 1:03

Your Answer

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

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