Recover a shared secret
Cryptographic protocols, Autumn 2009, 5th home exercise
A dealer used Shamir's secret sharing scheme to share a secret v
among ten parties, such that any four of them could recover it. The
secret value, as well as the shares of parties belong to the field
Z13. At the recovery time, the parties reported the
following shares:
| P1 | 12 |
| P2 | 8 |
| P3 | 2 |
| P4 | 11 |
| P5 | 0 |
| P6 | 7 |
| P7 | 9 |
| P8 | 4 |
| P9 | 5 |
| P10 | 10
|
(the value reported by Pi is the value of the sharing
polynomial at the point i).
It is known that up to three parties may have lied when reporting the value of
their share. Find v.