Hello and welcome to the fundamentals of cryptography course.
So far in this course, we've been focused on the fundamentals of cryptography, talking about building
blocks of cryptography, different classes of cryptographic algorithms, and how those different types
of cryptographic algorithms are applied in the real world.
In this video and the remain in videos of this section, we're going to discuss some advanced cryptographic
concepts.
So things a little bit beyond symmetric asymmetric cryptography and hash functions that are designed
to solve very specific and more complicated use cases.
So we're not going to dive too far into the weeds with these.
But the goal is to provide an understanding of what's out there and how it works in advance.
Cryptography.
And so in this video, we're going to be talking about secure multi-party computation.
And we're going to have four main sections.
We're going to start out by talking about secret sharing and multi-party computation, sort of the what
and the why.
Then we'll dive a little bit more into the details of Shamir's secret sharing and how secure multiple
copy party computation work.
Finally, we'll close out by discussing a few concrete applications of multiparty computation.
And so secret sharing and secure multi-party computation are designed to allow mutually distrusting
parties to work together.
Essentially, no one in the group trusts one another, but they're willing to work together to accomplish
a shared result.
And so in these schemes, each party is going to have a value that they keep secret.
And so this might be the equivalent of a personal private key in the cryptographic schemes we've talked
about so far.
And so using the secret value, each party in this group performs some type of computation.
And by doing so, they allow the group as a whole to compute a final result.
And theoretically, as this is going on, no party learns any of the other party's secret input, what
they're using in their computation.
And a really strong, secure protocol should be able to overcome collusion between parties.
So if multiple parties work together, they still should not be able to compute the secret input of
another party.
And so let's talk about Shamir's secret sharing.
So some Shamir's secret sharing is based off of the concept of a polynomials order.
So, for example, if you've got a line, it requires two points to uniquely define a line.
If you only have a single point, there's an infinite number of potential lines that go through that
point.
If you go up a level two parabolas, you need three points to uniquely define them, and that's what
we're seeing on the right here.
So if you only have two different points on a parabola, there are an infinite number of potential parabolas.
And they go through every other possible point at each X value.
And so Shamir's secret sharing takes advantage of this to create an M event scheme.
So, for example, I might have a scheme where we have a group of five people and we want to ensure
that three of them have to agree on something in order to accomplish a shared goal.
And we want to be sure that no one can cheat the system.
And so what Shamir's secret sharing will do will have a shared secret that's encoded as the value at
the Y intercept of the polynomial.
So where we intersect the Y axis at X equals zero.
And so with this polynomial, with that shared secret, each party is given a point on the curb as their
particular secret value.
So everyone knows that.
Say Bob has the value X equals three.
However, theoretically, nobody knows what that Y value is, because after those points have been distributed
by a trusted party, then the polynomial is destroyed.
And so all that remains are those collection of points.
And so if you've got a group of five people each with a point on the polynomial, then if we say have
a parabola like we have on the right side of the screen here, we need three of those people, five
people working together to reconstruct the polynomial.
We've only got to hear that parabola.
We don't know which of the three that we see here in the infinite number that we don't see is the correct
one.
And so we do not know what that y intercept value is.
However, if three people work together, we can uniquely define and that polynomial we can identify
which parabola it is and thereby extract that secret y value.
That would be necessary for some other operation.
And so Shamir's secret sharing is one example of a basis for secure multi-party computation.
And so this was Shamir's secret sharing.
We have essentially a one time secret.
If three of our five people work together, they can reconstruct the polynomial, extract the secret
that it's hiding.
And then that secrets known, the pollit nominals known, et cetera.
And so if we do things that way, as soon as three people work together, the secret is extracted with
secure multi-party computation.
You're building on Shamir's secret sharing or some other model to allow a group of individuals to perform
a computation together.
And so, for example, using their point on the curve, they might perform some particular problem that
everyone performs.
And by combining the results, they get a shared result.
That is the results that would be calculated if someone knew all of their points on the curve, the
shared secret, and use that to perform that same calculation.
And this is useful because it allows you to achieve that shared result.
However, no one's data is revealed by the process or the result.
So everyone knows this is what endpoint we've reached.
But I don't know what the point that Bob has is, which allows us to do repeated calculations.
So if at some other point some other computation is required, it's possible to do so.
And so why do we care about secure multi-party computation?
It's useful in cases where a individual's private data should be kept secret.
So one example of this is elections.
For example, you might want to have a completely anonymous election.
However, you want to ensure that the results are accurate.
And so you could you implement this election process using cryptography?
Everyone has some secret value.
And then at the day perform some computation.
And at the end, you know, whether that final vote is positive or negative.
Another example could be corporate partnerships, if you have a group of organizations in an industry
that need to achieve some shared goal but mutually distrust each other.
Maybe they need to perform some computation based off of their customers data.
And they don't want to share that data.
They don't want to share Internal Revenue values, et cetera.
But they want to know something based off of that data.
Industry wide.
They could potentially implement a secure multi-party computation scheme to achieve that goal.
Alternatively, secure multiparty computation can be used for processing of personal data.
So, for example, imagine the case where everyone from the office is out to drinks and they want to
know the average salary of the department.
But nobody wants to reveal their personal salary.
So one way to do this would be that everyone tells the bartender or the server what their salary is
and that person does the math.
However, you might not want to reveal your salary data to a random person either.
And so we use multi-party computation.
So maybe the first person at the table picks a completely random value and then adds that value to their
salary and tells it secretly to the next person at the table.
So they go off for a moment.
They share that information.
That second person adds their salary to that.
Some calls over the third person at the table.
They secretly speak without the first person there, et cetera.
So only two people talking at a time securely.
Each person adds their salary to the total.
At the end of the process, the last person has the sum of all of the salary data, plus this random
value provided by the first person.
They tell that number to the first person who subtracts out the random value that they added and then
divides by the number of people at the table.
End result.
They have the average salary, however, nobody in the group knows anyone else's salary because the
first person salary was concealed by that random number that only they know.
And then everyone else's.
They don't have enough information to determine what the salary of everyone else was because they lose
track of the number after it passes them.
And they don't know the values added in later.
And so this scheme isn't secure against collusion.
If most if enough people work together, say everyone.
But the first person share their salary data.
They can learn the first person salary.
However, there are more efficient and more effective schemes for accomplishing this.
And so these are why multiparty computation can be useful.
And so, just as a quick recap, Shamir's secret sharing multi party computation are designed for contexts
where you've got mutually Trump distrusting individuals or groups that want to work together.
Shamir's secret sharing allows a secret to be partition into multiple pieces.
Maybe this could be used to implement a trust and legal trust where multiple parties have to agree to
come together to unlock the password to a certain account.
You have secure multiparty computation, which is our example, where the salary data, they want to
know everyone's salary data but don't want to reveal their own.
And then we also saw other applications, so corporate partnerships, elections, processing of sensitive
data, et cetera.
And so this concludes our discussion of secure multiparty computation.
Thank you very much.