Problem D
Feldman Verifiable Secret Sharing
Recover a secret from a set of candidate shares. Let $p$ be a prime such that $q=(p-1)/2$ is prime and let $G_ q$ be the unique subgroup of order $q$ in $\mathsf{Z}_ p^*$ with a generator $g$. Let $f(x)=\sum _{i=0}^ da_ ix^ i$ be a polynomial in $\mathsf{Z}_ q[x]$ and define $A_ i=g^{a_ i}$ for $i=0,\ldots ,d$ and $s_ j=f(j)$ for $j=1,\ldots ,k$. You are given $s_1’,\ldots ,s_ k’$ with $k>d$ such that for at least $d+1$ distinct $i$ we have $s_ i’=s_ i$. You job is to recover $a_0$.
Input
Each line of the input consists of a space-separated list of: $p$, $g$, $d$, $A_0,\ldots ,A_ d$, $k$, $s_1’,\ldots ,s_ k’$. All integers are positive and given in decimal with at most 2000 digits.
Output
For each input line, output a line containing the corresponding $a_0$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1907 507 2 910 114 1803 5 925 798 370 947 606 2027 1329 3 856 1877 1574 1407 7 317 256 600 28 663 1427 211 |
151 527 |
