Hello and welcome to the fundamentals of cryptography.
Course, in this section of the course, we're talking about advanced cryptographic concepts.
So going beyond the introduction to cryptography we've been focusing on so far and discussing how cryptography
can be used for particular use cases.
In this video, we're going to be talking about ring signatures.
We'll have three sections in this video.
We're going to start out with an introduction to ring signatures and discuss a discussion of how they
differ from traditional Dayglo digital signatures.
Then we'll look inside a Renton's signature and see how and why these algorithms work.
Finally, we'll close out with a discussion of some concrete applications or bring signatures.
And so we've discussed digital signatures before and our section on asymmetric cryptography.
So just as a recap, when we have asymmetric or public key cryptography, we have both a private key
and a public key where that public key is derived from the private key.
And this structure makes it possible to generate a digital signature or something that verifies the
integrity and authenticity of a piece of data.
This works because with the private key, we can perform the same operation we do with encryption,
with the public key on a hash of the message.
So we take that message, we hash it, and then we quote unquote, encrypt with the private key producing
a digital signature.
This digital signature can then be sent alongside the message and the user's public key to the recipient,
who then can use that public key to quote unquote, decrypt the hash value of the message.
And then they can compute the hash of the message sent alongside it, verify that those hashes match
and be confident that the data has not been modified in transit and was actually sent by the owner of
that private key.
And so this works really well.
But one limitation that it has in certain circumstances is the fact that it reveals the identity.
Or more specifically, the public key of the person who's sending the message.
And so while this is desirable in a lot of cases, in other cases it may not be.
And so rings signatures take a slightly different approach.
They verify that a message was sent by the owner of one of a set of public keys.
And so you can verify that the signer is a member of that group.
But you cannot determine which member of that group the signer is.
And so let's see how this works.
We'll take a look here at a ring signature that uses a single decoy.
And what we mean by a decoy is a nother member of that group, but not the person it's generating the
signature.
And so we've got a few different types of values in this example.
So we have capital case zero and lower case K zero, which are the users public key and private key,
respectively.
In this example, we're going to be using elliptic curve cryptography.
And so when we talked about the mathematical hard problems that public key cryptography is taught is
based on, we briefly touched on elliptic curve cryptography and the fact that it's possible to implement
the discrete logarithm problem with elliptic curves just instead of a exponentiation with integers.
We're going to use point multiplication.
And also we know that addition of two points is easy and elliptic curves as well, equivalent to multiplication
in the integers.
And so are hard problem here is going to be division.
And so we have our two public and private keys that are related to one another by this mathematically
hard problem, the elliptic curve, discrete logarithm problem.
We also have K one, which is the public key of the decoy.
And so notice that since this is a public key, we can get it easily.
And so theoretically, if someone's put out their public key in a public forum, it's possible for someone
else to collect it and use it in a ring signature, which would then imply that the message was signed
by either the actual signer or this other public key.
But there's no assumption of, like agreement or anything that's required to set this up.
Beyond these keys, we have you and one which are randomly selected values, and we're gonna be generating
a signature of the set C zero s zero and S1.
So s one is one of our random values.
We've already got that.
And we're going to be calculating C zero and S zero using the equations down here at the bottom of the
slide.
So let's take a look at this first equation.
So our goal here is to calculate C zero and moving across this equation from left to right.
We have a capital H with parentheses.
So anything inside that parentheses is going to be hashed using a chosen hash function.
Lowercase M is our message that we're signing.
The two vertical bars indicates concatenation.
So putting message followed by whatever else.
We have our random value as one multiplied by G.
And so G is going to be our generator or our public value and our public key cryptography.
So when we talk about the fact that K zero, K one are related, what we're saying is that K capital.
So when we said a capital case zero and lowercase K zero, our related capital K zero is calculated
as the multiplication of lowercase K zero, which is a random number and G, which is a point on the
elliptic curve that's known by everyone.
And so we'll have S1 multiplied by this point as well.
And then we'll add another hash.
The message concatenated with you.
Another one of our random values.
Times that point, G.
And then we'll multiply this all by the point K one, the public key of our decoy.
And so in this equation here, there's nothing that anyone could calculate.
So our values that we have here, the message M.
Which if you're trying to generate a signature, you know the message we have S-1, which is a random
value G, which is a public value.
M again.
U.
Public value.
G again.
And then K one, which is a public key that we're just getting from someone.
And so this calculation of C zero doesn't prove membership or anything.
That's the job of our second equation.
So down here we have equation you times g easy to calculate.
S zero times G.
S zero is what we're trying to calculate in this equation.
And then we're adding in C zero times K zero.
And this would also be easy to calculate.
However, we've got a problem here.
And our problem is that our end goal is to calculate s zero and S zero is multiplied by G, which is
a problem because we want to get s zero on our own.
And in elliptic curve, cryptography division is our hard problem.
And so we can't just get s zero times G on itself and divide by G.
That would be breaking the security of our crypto system.
And so the way that we're gonna have to do this is to get a G term in every part of the equation.
And we don't have that right now.
We've got one in the first term.
You times G.
We have one in the second term F zero times G.
We do not have one in our third term.
See zero times K zero.
And so this is where that proof of membership in the group comes in.
Because as I mentioned a little bit earlier.
Capital K zero is calculated as a lower case.
K zero times that generator G.
And so we can move from our first equation in this bullet to the second one by substituting in lowercase
K zero times G for capital K zero.
And so now that we have a G term and every part of the equation, we can cancel them all out, giving
us our bottom equation where we're able to solve four s zero.
And so this second equation here is what allows us to prove membership in the group, because only someone
who knows the private key associated with one of the public keys could generate this signature because
they're the only ones that could perform that substitution.
That gets us to the second form of this last equation.
And so by generating the signature, we can prove that we're associated with one of the public keys
without saying which one in particular.
And so why do we care about this?
So a ring signature is designed to prove that the author of The Signature was a member of a certain
group.
And so this is valuable in these two contexts, like when you want to make a statement on behalf of
an organization and potentially want to stay anonymous within that organization.
For example, maybe you want to prove that a C level executive at a particular company has made a statement
without revealing which C level executive that is.
If all of these C-level executives had published their public keys, then one of them could create a
statement signing with their private key using a form of the ring signature algorithm that allows for
more than one decoy and then publish the set of public keys of C-level executives and the signed message.
And anyone could verify that that that the person who created that message was one of the executives
without knowing which one.
Another thing would be if you wanted to make an anonymous disclosure as part of like a whistle blowing
program or one of those statements to the press where they say under condition of anonymity, someone
inside the organization has stated, stated.
And in this circumstance, maybe you want to say that someone inside the White House has made some statement
and assuming here that everyone, one in the White House has a publicized public key.
It would be possible for someone to generate a provable statement from inside the White House if they
owned one of those public keys and send that to reporter without interaction rather than the traditional
face to face method of doing this, of their identity may be revealed to the reporter or they're making
a phone call, et cetera.
But it might not be able to prove their identity as part of the White House staff without revealing
it.
And so ring signatures.
This ability to generate signatures is part of a group is helpful.
However, it does make that assumption that the public keys are publicized, which is in many cases
not a valid one.
However, in certain contexts, maybe within an organization or when using technology like block chain
could be completely ballot.
And so, as a quick recap, we started out with an introduction ring signatures describing how they're
similar to traditional digital signatures, but allow you to sign as part of the group.
We then looked inside the math behind a simple ring signature algorithm to see why this is the case
and why that substitution of the private key times g for the public key was so important, because it
is what made it only possible to generate a signature if you actually were a member of that group.
And then finally, we talked about some applications of bring signatures, namely that they allow anonymous
disclosures as part of an organization.
And so this concludes our discussion of Ring's signatures.
And thank you very much.