2
$\begingroup$

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$.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Apr 15, 2023 at 0:43
  • 1
    $\begingroup$ yes they would be $\endgroup$
    – kodlu
    Commented Apr 15, 2023 at 1:03

Your Answer

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

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