As more and more sensitive data gets digitized, there is a need to ensure privacy and reliability of the data, especially in the face of adversarial parties who attempt to corrupt or unwanted access to sensitive secrets.

In many instances such as online gambling, bidding, and even Google's targeted advertisements, a client wants to be able to take inputs from multiple sources (for example, auction bids) and produce an output (for example, the highest bidder) without revealing any information about the other inputs. We will use such scenarios as well as more cryptography related ones in order to motivate Multi-Party Computation as a method to compute on encrypted data. With MPC, we will quickly see it's limitations with unsecure channels and first develop secret sharing schemes (specifically linear secret sharing schemes) such as Shamir's scheme, and soon after, verifiable secret sharing schemes.

We will introduce the different types of adversarial structures and explore both the robustness and limitations of secret sharing schemes against them.

Finally, we will show that all Linear Secret Sharing Schemes can be constructed to be verifiable. We will explore the consequences of this and discuss techniques in their construction.

Prereqs: Math136 used in proofs

Encrypted data requires a key to be accessed again yet storing that key in one place is very insecure. The server storing the key could be shutdown, and lost forever, thus preventing us from ever decrypting our data and using it in a meaningful way. In order to prevent this, we could store multiple copies of the key. However, with more servers, the more likely one of them is to being attacked, leading to unwanted party gaining access to one of our keys and thus being able to decrypt our data. Thus instead of storing copies of our key, we should store fragments of our key that could be recombined to form the original. This is an example of Multi-Party Computation, a process in which multiple parties give an input to a process to compute a final value. Another simple example of a Multi-Party Computation would be in an online auction, each player sends a bid to a central server that computes the winner by finding the max bid.

The problem now becomes that of figuring out how to break up our secret into parts that individually give no information about our secret but combined reveal our original secret. One famous implementation of such a scheme is "Sharmir's Secret Sharing Scheme". In this Secret Sharing Scheme, we have an extra party, a dealer, who knows the secret and constructs a degree $t$ polynomial of the form $a + c_1x^1+ \dots + c_t x^t$ where our secret is $a$. First note that in this scheme, our secret must be a number but we can always use this number to represent ASCII/Unicode value(s) to convert it to any string. Furthermore, each individual point alone tells us nothing about the polynomial. In fact, even having $t$ points tells us nothing about the actual polynomial. However, having $t+1$ or more points would allow one to use a Lagrange Interpolation to recreate the original polynomial and thus tell us the value of $a$. Then the dealer distributes at least $t+1$ unique points, $1$ to each party such that none of the points are $(0,a)$ as then the holder of that point will bypass the entire scheme and know the secret.

This is a great process as we can now distribute shares of our key to as many people as we want by choosing a larger enough $t$ and have each of the share holders send their share back to us when we want to reconstruct the secret. However, this scheme makes one big assumption, that the players and dealer are trustworthy. What if one of the players were compromised and reported a point different from what they were given. Or, what if the dealer was compromised? We would then need verifiable secret sharing, the ability to detect when a dishonest action has been made, how/when to report it and how to proceed. An example of such a scheme can be found here.

Note that Sharmir's Secret Sharing Scheme was a linear secret sharing scheme which is when the shares are computed as a fixed linear function of the secret and some random field elements chosen by the dealer where the secret is also in the field and the field is finite. It is shown here that we can convert linear secret sharing schemes into verifiable secret sharing schemes.