Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they have (in order to prevent the other people from recovering the correct secret). Show that in the ordinary secret sharing scheme based on polynomials, any group of k+2 people can recover the secret even if one of them is dishonest.
*I am confused about how to approach this proof. Maybe proof by induction? But I don't know what to write for the inductive step thereafter.
Just a hint:
The shared secret is a polynomial with order k, so you need just k distinct points on it find the answer. With k+2 people, how many sets of k people can you make? Of those sets, what shared secret does each set compute?