Lagrange interpolation in the exponent

leonero

4/13/24, 5:52 AM

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 + 0

fiat-shamir

secret-sharing

verifiable-encryption

Score:1

Crypto

kodlu

4/14/24, 2:54 AM

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.

+ 2

leonero

4/15/24, 12:43 AM

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?

kodlu

4/15/24, 1:03 AM

yes they would be

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Lagrange interpolation in the exponent

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.