Blind Signatures with Georg Fuchsbauer | a16z crypto Research Series

Transcript

All right, morning every welcome everyone to today's A16Z crypto research seminar. Uh very happy to introduce George Fushbower from TU Wine uh who's done lots of kind of very deep work in cryptography and today we have the benefit of getting a tutorial from him specifically on blind signatures. So take it away. >> Thanks Tim. So I'll talk about blind signatures and some applications and since this is A16Z I'll focus mainly on applications to blockchain protocols. Okay. So let's start with some basics. What's uh a signature scheme? So we have a signer or a singer called Sai uh who has a verification key and a signing key. and he can use this signing key to produce signatures on any message which

can then be verified using uh his verification key. What's a blind signature scheme? So here now we have uh another participant. So meet humor the user she has some message and she wants to get a signature on that message from Sai without revealing the message to Sai. So they run a protocol at the end of which Yuma holds a signature that verifies under SI's public key. But we want blindness. So we want Sai not to learn the message that he signed.

Moreover, we want something stronger which is that if he later sees the signature, he cannot link it to any of the signature issuings that he has run in the past. Now in terms of unfortability, all we can ask for as siders know what he's signing. What we will ask is that if he s if he runs this uh signature issuing protocol n times then no one can produce n plus one signatures and that's called one more unforgeability. Okay. What has this uh concept been um introduced for? First it was by David Ch using ecash and I'll talk about this briefly. It was also considered for e voting. So for example in a voting protocol you authorize to you identify to the voting authority and

then you get a blind signature on your vote and then you can later cast it and it is authenticated but uh yeah the authority doesn't see what you voted more generally you can build anonymous credentials from it which I guess a nice application would be to have like a privacy preserving um ID where when you go out to buy alcohol you can prove that your older lens 21 without revealing your actual birth date. And recently there has been a lot of renewed interest in the concept due to applications in contact tracing, advanced DPNs, private relays, private access tokens, privacy paths, and Bitcoin blind coin swaps and I'll talk more about the last

application. By the way, feel free to interrupt me at any time. It would be nice if this is interactive. Yes, >> just a s sanity check for me. uh FHA would just solve blind signatures, right? Okay, good. >> So the the question was whether that fully homorphic encryption would solve um would solve this problem. Yes, because the user could just encrypt the signature. The sign evaluates the signing functionality on the cipher text, gives it back to the user, the user decrypts and has a signature on the message. Yeah, we want something efficient, but that would yeah solve the problem. And should I think of the like in the voting example you talked about some kind of like authority that you go to to get should I think of that as kind of the canonical type of application >> ecash is is and I'll I'll show like this

chian ecash which I think is kind of the that really also shows you this one more unfortibility why this is uh >> important okay so for those who are interested um here's a first instantiation which uses RSA so the RSA assumption says that if I have n the product of two large prime numbers and some public exponent e. Then it is hard to compute e roots modulo n. Okay, so if you don't uh like number theory, here's a nice abstraction. That's all you need to know. There's a function that takes an input and this function is defined as raising it to the power of e modulo n.

And that's efficient to compute using square multiply. And the RSA assumption says that you can't go back, right? If I give you the evaluation of that function, you can't find a a pre-image. And what makes RSA particularly interesting is that there is a way of going back if you have a secret trap door. So this is actually a a trapdo one-way permutation in crypto terms. And you can set up this um when you generate this modulus n you can generate it together with the secret key that allows you to invert the function. Okay, here's how you build signatures from this. also conceptually a very um simple idea. This is RSA full domain hash code called like this because before you start you first

hash the message and we assume that this hash is a number between zero and n and then a signature on that message is simply the inversion of the RSA function right you compute f inverse on the hash of hash of the message and that's your signature right how can you verify signatures >> encrypt >> yes >> you encrypt it back >> exactly so basically if you see a signature Since that is easy to do in public, you can check whether if you evaluate f on it, you get back the hash of the message. Now John's idea was to turn this into a blind signature scheme.

And so again, the only property you need to know about this f is that it's homorphic and its inverse is also homorphic because if you raise x0 * x1 to the power of e, that's the same as raising x0 to the power of e and multiplying with x1 to the power of e. Here's how blind signing works. The user chooses some random value R in the RSA domain, computes the hash of the message, and then blinds it by multiplying it by f of R and sends that to the signer. And since F is also a bjection and R is uniformly random, this perfectly hides the message. So M prime doesn't contain any information about the message. Now what the signer does is compute f inverse on this blinded

message m prime. So how can the user obtain a signature on the message from sigma prime? So basically what she does is she takes this blinded signature and divides by r and I claim that that is an rsa signature because if you just plug in so what is sigma prime? It's f inverse of this blinded message. So that's this divided by r. Now we use the property that f inverse is homorphic. So this is f inverse of the hash times f inverse of f of r that's r and that cancels out with r. Right? And so she has obtained sigma defined like this.

Okay. So what was the first as I said like the canonical example what you can build from uh a blind signature scheme and that ch as initial motivation for this is >> so so R is part of the blind signature R is M prime comma R or >> R is gone right the blind signature so the the >> no no but like the communication protocol >> in the >> so like R needs to be sent back to >> R so R uh the user keeps R and then uses it to unblind the blind blind signature, right? But then the the final signature is deterministic. So R is not part of the blind signature. Yeah. Okay. How can you do ecash or what is ecash? So the motivation was can you have a digital analog of physical cache and in

particular can you have something anonymous as cash? So can we have a protocol where the client can withdraw coins from the bank can then spend these coins with merchants? for example, Marcelos the merchant so that then later the merchant can deposit these coins at the bank and get his account credited, right? The question is, can you have anonymity? And so I was at uh an event about the digital euro and there was some Austrian uh central banker. And so he explained a lot of um economic properties about the digital euro. And then I asked, "What about privacy?" And then he said, "Well, if the bank gives you a token, then obviously when the token comes back to

you, it can link. So you can't have privacy." And I thought, "Okay, I'll stop asking cryptographic questions." Okay. So what can you do? What can you use? Blind signatures right? So, how can you get anonymity? We want to make sure that the bank doesn't know what coin Alice withdrew. And so, how is this done? The client picks a random serial number from a large enough space. So, there's no like realistic chance of collisions. Gets a blind signature on the serial number from the bank. And that is her coin, right? So, it's a zero number together with a signature by the bank.

When she wants to use the coin to spend it, she just passes on this information and then you immediately see, well, it's not physical, it's digital. You can copy it. What about double spending? How can we prevent the client from spending this anywhere? And so, this is online ecash. And the solution is very simple. It's basically like in Bitcoin, you check whether it's already been spent, right? So when the merchant receives a coin, it first asks the bank, is this a coin that hasn't been spent yet? The bank needs to remember all the coins it ever received.

And if not spent yet, then um the merchant can give the goods, right? Yes. >> Can you explain what that means? What a spent means here. >> Okay. So the the bank just remembers, it doesn't know which coins it issued, right? That was blind. But it it knows what coins it already received for payments like deposited coins. And so the idea is basically you don't accept the coin before you deposit it. And so the bank can check whether it was already spent before. Yes. >> So the merchant now can't use that coin again. >> Yes.

>> Um okay >> that that's true. Yeah. So there's so Okay, since you're asking there's many variants of ecash. So the first one was offline ecash. Can I have a system where the merchant doesn't have talk to talk to the bank? So basically any merchant optimistically uh accepts coins and somehow in this spending protocol the client has to encode her identity in the coin in a way that's still anonymous. But if the same coin was deposited twice at the bank then there's a mechanism of retrieving um Alice's identity. And so then that's actually not yet your question. Then you can do transferable offline ecash.

That's something that I've worked on and it's probably the most secure scheme is probably uh one we did some years ago where you want to have a merchant being able to retransfer the coin and then at some point it goes back to the bank and if at any of these transfers there was a double spending you can retrieve the the wrong doer um by extracting the identity but as long as there was no double spending everything is anonymous. So these are things you can do with like cool crypto tricks.

Okay. So that's all very uh 1980s. So you might wonder what can blind signatures do for us in a blockchain context. So as a motivation um consider the lightning network. So that's a protocol that allows you to do off-chain payments in Bitcoin. But I don't want to get into any like details of it. All you need to know is that there's a way of opening so-called payment channels between users. So that if say this is like a payment hub, if Alice has a channel to the hub and the hub has a channel to Bob, then Alice can send bitcoins to Bob via this payment hub and they can even like do like incremental

payments without putting anything on chain. But yeah, not uh relevant for this talk. Okay, what's relevant is how this is done. So the way it's done is that Alice creates a Bitcoin transaction that needs two signatures to be spent, right? One by Alice and one by the payment hub and if both basically there's signatures by both of them then you can think of this bitcoin being transferred to the hub. So really there's more than one transaction but like I'm abstracting away details.

Okay. So what's the protocol? Alice signs this transaction. So basically her bitcoin is now escroed in this transaction. Uh the payment hub does the same for his channel with Bob and then they can transaction and then when they close the channel they all like put the missing signature and then all the bitcoins are basically transferred to the receiver. Okay, what's the problem here? The problem is if we go back, what if Alice signs and then the payment hub just signs as well, takes Alice's coin and never pays Bob, right? That's something that you want to prevent in these lightning channels. So, how can this be done? Not clear a priority. It's Bitcoin, so you can't just encode any

statements you want into like the spending of a coin. But I guess an artifact of um sorry, I Yeah. Yeah. So maybe first like what would you do if you did have full programmability? How would you solve the problem? >> Say that this transaction can only be taken if that transaction is on the chain or something like that. Yeah. Okay. But basically the problem we want is we want these things to be atomic meaning that either both payments go through or none of them does. Right?

There's a fair thing, right? Of course the payment hub can just abandon but then it doesn't steal Alice's coin. As I said, it's not clear how a priority how to do this in Bitcoin, but there's one functionality that Bitcoin has, which arguably is an artifact of how Bitcoin addresses are defined because it's the hash of a public key. And so it has this functionality that you can use to encode spending conditions, which is called a hash lock. So what the payment hub does is it chooses a random value X and it hashes it and then it can encode into this transaction the value Y and say that you can only take this transaction if you know a

pre-image. Right? So now this secret X needs to be known to take this transaction. And now I argue that now you get atomicity by the following pro protocol. So the the hub goes first encodes. So the the hub is the only one who knows secret X. There's a transaction that you can only take if you have X. So now the hub can safely sign this transaction because it it knows as long as I don't publish X um this cannot be taken. Now Alice, so it communicates Y to to Alice. Alice, so yeah, the Bitcoin is escroed here. Alice in her transaction also puts this hashlock in there. So for spending this transaction, you also need to know X.

Alice signs this transaction. But now either nothing happens and then there's like time locks as well. So everything is reverted that you can do in Bitcoin. But if the payment hub takes the first transaction, it needs to publish the secret value X, right? And now Alice can give the secret value to Bob and Bob can take the second payment. Okay. So in terms of security or like economic security, that's good. What's bad about this is privacy. So there might not only be Alice and Bob that transact via this hub. There might be another Alice and another Bob the transact or a third Alice and a third Bob. And all of these transactions have the same hashlock,

right? And so you can link them. And this is the problem that Tumble Bit wants to solve or does solve using blind signatures. >> What's the linkability again? Oh, if you see so if the once these transactions are posted on chain because the channel is closed, you see the transaction and you see the hashlock that was used and you know that um these two things belong together because they have the same hashlock because that's exactly what insurance. >> So there's no mixing at the hub you're saying.

>> Exactly. Yeah. Yeah. Baby, same question. So this is um the regular Bitcoin transaction has this problem too. So you're trying to do better uh using payment hubs. You want the payment hub to the same service. >> Yes. Exactly. You want Yeah. You want to have some like for example, you could you could think of this hub being a mixing service. Like a lot of people put Bitcoin in there. It mixes it. People get their bitcoins out. Everyone's guaranteed I get something out. That's atomicity. But then there's no linkability between what went in and what goes out.

Hence the name tumble bit, I guess. Yeah. Okay. Okay, so here's the idea of Hileman at all. Instead of requiring a hash pre-image to redeem this transaction, they require an RSA signature. Okay, so now the payment hub selects some random message M and says that you can only take this transaction here if you have a signature on M. And basically, so the payment hub has the the secret key. Um so what changes now on this side of the protocol what Alice can do of course if Alice puts the same signature like basically buys a signature for Bitcoin nothing is gained but now we can use the blinding of RSA

because what she does is she buys a blinded signature right so she takes the message M runs the blind signing protocol and says payment hub can you please issue a blind signature on this blinded message here's a transaction action which you can only take if you give me a blinded signature, right? And so if the payment hub complies, then Alice can unblind the signature, give it to Bob, and Bob can redeem this transaction. That's something that you could encode in Ethereum. But the problem is in Bitcoin, you can't because RSA signature verification is not an op code. So what they do is they like play some tricks to get the same uh functionality but using different means.

Uh, sorry. How do you verify an a blinded signature? >> Um, how does Alice know that sigma prime corresponds to her um blinded message? >> Uh, she's not the only one that is a check, right? Somebody else also has to check or no? >> No, she so she's the one that puts in So basically she puts in if this worked um the blinded message m prime and says that only if the um if the payment hub puts RSA inverse on M prime in there which is something you can check then uh the payment I see you can take the >> she she puts the blinded message there.

>> Yes, exactly. That's kind of the what before was the hash value is now the blinded message. What before was the pre-image of the hash value is now like an inverse of the RSA function which is the blinded signature. Do you have to do you run into like issues if Alice is malicious because you're not checking that it's the hash of message times some randomness or >> I mean here think of it as no Alice no Alice can't really do anything. I mean if Alice is malicious money she loses her money. Exactly. It's in her interest that he puts the I think >> the correct thing in there. Yeah. >> And then to follow up does does the merchant need to check something?

Um basically so Alice and the merchant they are like Alice wants to buy something from the merchant right and the merchant says I give you the goods once you give me that signature I need to get the money. So the yeah so Alice can or whoever can unblind whoever blinded it can unblinded the message can unblind the signature and then um use it to redeem the second transaction. >> Who knows M? basically everyone that's that's kind of that's so M is kind of the statement that's encoded in a transaction and sigma is the witness that you want for that transaction.

>> M is just public. >> Yeah, exactly. M is public. But the thing is that here there's only M prime and so things are and that's like information directly unrelated to M and so um it's the two payments are unlinkable. Here's how you get this actually to work. So what we want here is we want to have a mechanism. So that if Bob has a signature on M, he gets the payment and otherwise he doesn't. Right? So the way they do this is that the hop sends the challenge the message for which Bob needs a signature and then it just encrypts to H which is the transaction signature that makes this

transaction go through under the key that is a signature on M. Right? So, as long as you don't have a signature, this transaction you can't take it because you can't decrypt. If you have a signature, you can use it to decrypt the cipher text. You obtain the transaction signature, you sign the rest, and then you get the the payment. Okay, so that's one side of the protocol. Here's how Alice can blindly buy a signature using very similar tricks. So she sends the blinded message m prime and now the payment hub can like produce sigma prime from it by using its secret key. It won't send it right because Ellis can just take it to give it to Bob

and then the payment hub loses the money. So again they want some contingent um mechanism and so now instead of sending sigma prime to Alice the payment hub encrypts it under some random key. Now, Alice can't obtain anything. So, what can we do? How can we make sure that Alice only gets the key if she pays, right? If if she gets the key, she gets a signature. That's what she wanted, right? How can we make sure she only gets the key when she pays? Use hashlock again. So, in so the payment hub sends Alice the hash of the key. This shouldn't

like endanger the cipher text assuming the hash function is good. And one way Alice now makes a payment that says you can only take this payment if you give me that key. So if the hub takes the payment, so she signs it. If the hub takes the payment, needs to publish the key, Alice can decrypt the cipher text and thus obtain what she wanted, namely Sigma prime. So once she has sigma prime. Okay. So first of all because now everything's signed that bitcoin goes to the hub. Alice has sigma prime by decrypting c prime.

She unblinds sigma prime to get sigma. She gives sigma to Bob. Bob uses sigma to decrypt this cipher text. Gets a transaction signature by the payment hub. Completes it by his own signature and thus receives the other bitcoin. So you need the payment hub to prove that it put in the correct signature there. So there you need that. >> So that's that's all nice if the payment hub is honest, right? And that's actually an encryption of a payment hub signature under an RSA signature and so on. Sorry to >> also what is the encryption? So so C is equal to encryption of sigma comma t like what um >> what is you're encrypting to knowledge of like a signature. What what exactly

is that saying? >> That can just be any symmetric encryption scheme. I mean typically you would hash sigma first to have like a >> I see symmetric key encryption scheme >> but what is the condition you're encoding there in some sense like basically Bob should only be able to decrypt it or the receiver should only be able to decrypt it if it receives the blind signature right >> if it has a signature that goes with M >> ah because the payment provider or the payment hub knows the sigma it's just like some kind of chem I see okay >> that also relies on the fact that RSA signatures are deterministic like it wouldn't work with a proistic signature scheme.

>> Do you think this flow would be simplified if you had like witness encryption to knowledge of a signature? >> There's like that's kind of where I'm building up to. You can simplify all of this. >> Okay. >> So maybe yeah, you don't have to think any further. >> Okay. But first of all, obviously um >> so that that whole previous discussion was about what what goes wrong if the hub wants to lie about C. >> Exactly. The hub can just put anything in there. The hub can put anything in there. Right. All this argument relied on the fact that these things are wellformed. So in particular, yeah, how can Alice be sure that C prime is correct? So what would be the statement? The statement is C prime is an So there exists some key K

such that C prime is an encryption of sigma prime where sigma prime is a blinded signature for M prime and K is a pre-image of Y. Right? That's kind of the conditions you would have thinkled. >> Yeah. Yeah. So really how can I be sure that C prime and Y are correct. Right. >> Exactly. So how can you be sure? Use a zero knowledge proof. Right. And that is exactly the idea of zero knowledge contingent payments which is a protocol that uses exactly this idea of adding a proof that these things are wellformed. And since you can prove basically any NP statement here so that this this witness sigma uh verifies what you can do is you can so zero knowledge contingent payments is a protocol that allows you

to buy NP witness for anything you want for Bitcoin in a fair way. And so the first use case that uh Maxwell who invented it did was a protocol where the statement is a sudoku puzzle and then you have an atomic swap where you can buy a sudoku puzzle for bitcoin and either everyone gets what they wanted or no one gets anything and so it's like a fair exchange protocol. >> But does this require the encrypter to know what the solution is or >> Yes. Otherwise you can break NP, right? I mean >> Uhhuh. So it's not like witness encryption. No, it's No, no, no. Here.

Yeah. This in the thing that's encrypted is something that's known by Yeah. And this Yeah. So, this protocol was then broken by Companelli, Jinaro, Goldfeder, Nitardo, and fixed. And then I broke theirs again and fixed it. And so, now it's seems to work with Gross 16 which they used at at the time. there was some problem with who sets up the parameters for the proof system right and so they said well the verifier can but then you have a problem if for um if the verifier cheats and so that's why you need actually subversion zero knowledge which is a concept that we introduced anyway that's not what they do because like proving RSA statements

is kind of messy probably using snarks I mean the sudoku puzzle is a really simple circuit that checks whether something's a sudoku puzzle this would be a lot more complex So what they do is use cut and choose techniques meaning that basically Alice sends a lot of blinded blinded messages to the hub and then the hub just and then al the hub like encrypts it then Alice selects a subset and the hub has to open them and Alice can just check whether that was correct right and if there was anything incorrect um there's a good probability of catching the hub the problem is that there's many problems because um you want to avoid Alice.

Well, first you want to avoid this opening proof that Alice can then get a signature, right? And so basically what you do is Alice sends um blinded versions of M prime or actual images for which she already knows the solution and then she opens these. But then you also want to make sure that Alice can't obtain more than one signature. So you have to do additional things. So you end up like in a three round uh protocol. Okay, same thing for Bob right here. They also propose a cut and choose based protocol that uses randomizability of RSA to make sure that this is correct.

Okay, let's let's zoom out and look at what we want to achieve in this part here. Basically, Bob wants to buy a Bitcoin if and only if he has some signature, right? But that seems very related to what Bitcoin does anyway, right? it because to get Bitcoin you need a signature on a transaction. The problem is that if this is an RSA signature, Bitcoin doesn't accept them. So why don't you just replace RSA by something that Bitcoin accepts, namely Schnore. And then this part of the protocol is basically done, right?

Because now Bob can create a transaction from an address of the payment hub and then says that or the pay and then if he gets a signature from the payment hub on this transaction, he gets the bitcoin. That's the by specification of Bitcoin. Now let's look at the other part. Is there maybe also a way once we switch from RSA to Schneore of this blindly buying a signature interfer away from Bitcoin. Okay. So now let's enter another technical part. So I'll explain signatures and blind signatures.

>> Sorry, just to go back. Yes. So, you're saying like if you can do this, the second transaction is just going to be a normal like pay to shore public key hash kind of transaction >> and that's that. >> Yeah. >> Okay. All right. >> Because it's Yeah. It's kind of this is like getting bitcoin if you know some signature from the sender that's if the signature is a >> so they'll just use the merchants's public key or whatever, right? Or public like public key or whatever >> the the hub's so the hub is paying the merchant, right? So the hub's public key >> I see.

>> And if you so if you have and if the merchant makes a transaction um gets a signature on this transaction from the hub then gets the money because it has a signed transaction. >> And remind me why the hub can't claim it in that case. >> Um be well because um the transaction basically says transfer one bitcoin to Marcelus. >> Oh, right. The recipient's hardcoded. Exactly. And if if once it signs the money is gone, right? The the recipient >> could go ahead and publish the transaction if they wanted, but the money would go to the merchant in any case. Yeah. Okay.

>> Exactly. The it could even Yeah. It could also publish the transaction but not sign it yet and then say if you have a signature, you get it. That's how Bitcoin is defined. Now, is there a way of getting the signature blindly by Alice? So, let's so we'll focus on the on the first part now. Okay. Here's Schnore signatures. Now we're in a typically an elliptic curve group of order Q generated by some generator G and we have a hash function that maps bit strings into Z Q. Secret keys are elements in Z Q. Verification key is X * G. So note that I use additive notation.

So this is often written as G to the^ of X but it's the same. So basically the discrete logarithm problem says that if I give you this group element X you can't find little X its exponent. Now to show how signing works, it's instructive to look at where this schnoy signature actually comes from and it's from an identification protocol. So meet Marcel P the prover and Jul the verifier. They run a protocol where the proofer convinces the verifier that he knows the secret key corresponding to the public key. So how is this done? So the proofer starts by generating uh an ephemeral key pair. So it picks a random scalar X,

computes the group element R * G, sends it to the verifier. The verifier chooses a random challenge in Z Q and the proofer should now reply with R that he picked before plus the challenge times the secret key. And you can show that uh if the proofer convinces the verifier, it should do so for a lot of challenges C. And if you get two S's for two differences, then you can basically from these two equations compute the secret key. So that's why it's a it's really a proof of knowledge. You can only do this if you know X. Okay. How can the verifier check whether S has this form?

[Music] It's basically check the equation in the exponent. Right? So here we don't have exponents but basically if you like multiply this equation by the generator you get that s * g equals little r * g which is capital r plus c * the key and that's exactly how you verify schwar signatures as well. Okay so how do you turn this into a signature scheme? generate C from from a hash. >> Exactly. Use the feature transform.

Pretend look use a random oracle to generate this uh challenge value C or in real world implementation use a hash function. So the the signer just runs this protocol on its own and instead of waiting for a verifier challenge, it hash it creates it using a hash function um on the first protocol message and also the message. So now you can bake the message into this protocol. So that's called the future me transform of this protocol. And so this was shown to be an unfortable digital signature scheme in the random oracle model if this group is discrete logarithm hard. And that was proven by

my academic father and grandfather Preon and St. Okay. How can we turn this into a blind signature scheme? So let's go back to the identification scheme. So we had Marcel and Jeul but they since this is more modern they should be Marcelis and jewels in case you know the characters anyway. So the idea is that basically the blind serer and the user run this protocol interactively because now what the user can do the user can compute this challenge. So compute the hash with the message and now arguably the message is hidden and then the signer finishes the protocol.

So it's not a blind signature because basically if the signer later sees a signature it's exactly the R and the S value that it sent. So it's easy to link right. So it doesn't work yet. >> So ide user is just computing the >> the user is choosing the R and computing the hash function. Pardon? >> So far the user is choosing the R and computing the hash function. So >> the the R is sent by the signer but then the user kind of creates this challenge that in the regular signature protocol the signer would create because it knows the message but now let's outsource that to the user because it's the user that knows the message right it's a first idea but it doesn't work since we also want the signature not to reveal

anything about the signing session. So what schno came up with is I think a very cute uh observation that you can actually blind these values. So what the user does is she samples alpha and beta random blinding values. She receives this first message R and now she blinds it into a message R prime which is R plus alpha* generator plus beta * X. Okay, why it's done like that you'll see later. And that will be the first component of the blind signature. Right?

So now it's by these blinding factors. It's unrelated to what the signer saw. She now computes the hash value that goes with this R prime. Right? So she hashes RP prime public key and the message. Now obviously she can't send this hash value because again then the signer learns something about the message. So what she does is she also blinds this by using this beater again. So she signs a blinded version of the challenge to the serer and then the serer just does what it did before two apparently seemingly unrelated values right but it turns out that if you do this calculation that if you take this value s received from the serina you add

your blinding value alpha to it then that pair is actually a valid signature. So you can kind of this blind unblind trick also works for sure. And what's also not too hard to see is that this scheme satisfies blindness actually perfect blindness. So the signing session is information theoretically unrelated to the resulting signature because what does the the signer see? It sees the final signature RP prime S prime. It sees the value C.

But um actually yeah if if you look at R prime then alpha is kind of an independent random value that completely blinds R. This value C that the sign sees is completely blinded by beta. Now it seems there's a third value but that's just uniquely determined by anything else. Right? For every RC combination there's only one S that makes it a value signature. And so yeah the blinder doesn't learn anything. Uh sorry the signer. What is C prime here? I see. >> Sorry. Yeah, this one I didn't spell. So C prime would be the hash value that went with the with the actual signature.

So you could think as the the Schnore signature being like um it's like a a value R, a value C, which is the hash value, and the value S. But really, you only need two of them. And so yeah, the argument is that um although the signer learns C prime, which is just by verifying this final signature, the value C doesn't reveal anything because it's blinded by beta. So there's three values where one of them is determined by the other two and the remaining two are both blinded by independent uh random values. It's kind of the argument.

>> So if you only cared about a computational version of blindness, could you just skip the beta? >> I don't know if there's anything simple. I think it's just a a nice effect that you get perfect blindness. >> Okay. But like why do you need the beta? Like >> why um why do you need the beta? If if the user sent just this hash value, the signer can remember it and then see if that's the hash value that goes with the final signature. So that would link it again. >> That would link the hash value. So when you get the signature RP prime S-prime on some message, you don't know which signing um um session it was from, but you can determine like when you verify it, you compute this hash value here, right?

That's for verifying the signature. And if this hash value turns out to be something that you've seen in a signing protocol, then you can link it to that signing session. So you also need to blind see. So you're saying only later when it sees like m comma sigma only then will it be able to relate it back >> if you don't blind. Yes. Okay. >> But in the in the blind signature model the signer is not the verifier. >> Um no the signer is the prover signer is the one who knows the secret key. So why would the signer see the future verification of this? Um >> because in real like think of the ecash example, right? I I'm the bank. Alice

withdraws a coin. I remember the C value. Later I see a signature that has a C value. I know that it's the coin that I gave to Alice. >> Also like u this may be a bit weird question. Why do we need a hash function? Why can't I just like sample a random string that somehow depends on all these values? like like we're not doing fiat here anymore because the protocol is actually >> you want you want to have um a shore signature at the end, right? That's where the hash function is from. So you want you want this final thing to >> I thought the reason that uses a hash function was because it's no it's not interactive anymore, right? If it was interactive.

>> Oh, okay. >> Yeah. So so yeah, you have the signature scheme, you want to make it not interactive. the blind signature scheme, it's necessarily interactive because the user has to intervene with its message. And so yeah, the you want to have a hash here because in the end you want to have a schno signature. And that's also yeah, that's kind of you see later the the that's kind of there's a lot of blind signature schemes in the literature, but if you want to do stuff on Bitcoin, you can't just invent your own signature scheme. You need to have a blind signing protocol for an existing signature scheme. And that's kind of the one of the things that that we did. We we'll come to that.

>> Good for everyone. Yes. >> Are you going to comment on ECDSA at all or what's known there? >> No. So for ECDSA, I mean we want provable security, right? ECDSA, there are blind ECDSA signing protocols. But since ECDSA itself doesn't have a security proof, it's kind of mood to think of whether the blind signing protocol is secure. That's why I think it's less interesting. And that's why I also think like the world is moving towards nor with Ed DSA anyway. Okay, that's debatable. Bitcoin did and like the most conservative thing does.

Yes. >> Can you explain again the role of that hash? Um, yes, that one. Um if we go back to schnore signatures in the end what you want is so the signature is a pair of a group element R and an integer S such that this equation satisfies where C is defined as the hash of the first signature element the public key and the message. Right? So in the blind signing protocol you need to somehow make this C uh this hash uh appear because it will be part of the um verification equation of the final signature. So the value S will depend on it.

>> I see. And if you don't care about that then there's many other ways to do that part. If you don't care about your final signature being a standard signature then there are many ways to do this. >> Yes. I mean there's just different approaches of where you don't use a signature. Yeah. Okay. Good. So if you zoomed out and you don't care about the details of Schnore, let's get back to um our cryptocurrency example. So this was so our motivation was that Alice wants to blindly buy in a fair way a Schnore signature. And now all you need to know about Schnore is that this is the verification equation. So Schnore signature is a pair R S. So that s * g equals r plus c is the hash of rx in the

message and x is the public key. Okay, that's all we need in order to buy a blind signature. There's a substep which is to buy a discrete logarithm and that's ide all ideas uh by Yonas Nick um where let's first solve this problem. So we have the buyer who has some group element T and some Bitcoin and she says whoever gives me the discrete logarithm of this group element will be paid some bitcoin. So here's the seller who has the discrete logarithm and wants to get some bitcoin and we want this thing to be atomic.

So now we don't need hashlocks because schno signatures allow us to do a lot of cool tricks because of its structure. So the way the protocol works is that first as before they create a multisig output except that now it's um it's actually a schnore multi- signature but you can think of this being a signature of the buyer and signature of the seller. Now what the seller does is it sends what's called an adapter signature, right? So it's like a schno signature except that this value s is not s but s prime and it doesn't satisfy the verification equation cuz otherwise this signature would be that and the buyer could just um sorry no one could take the money.

Ignore that. But it has this um structure here that s prime * g equals t the element of which the discrete logs should be solved plus r + c * x. So it sends that Alice can check once Alice got that she signs the output and now in order to take the money again by this multi- signature um stuff details of which I won't get into the seller now has to produce a signature with the same R value right so it has to produce a signature RS to get the bitcoin so that this satisfies this equation here >> so the c is hash of rx and t and m or something or in this

>> in the adapter signature. >> No, there's no T in there. It's just basically the transaction info, right? It's the signature >> on the >> on the the transaction. >> Oh, what's little C exactly? >> C is the the so if for signature is the hash of the message and here the message would be the transaction that's being signed. Okay. So now Bob produced the signature and took the Bitcoin and now Alice has lost her Bitcoin. How can she still get what she wanted?

>> Yes, >> she has RS prime and RS and that's enough to >> exactly. So if she computes s prime minus s. So if you subtract these two equations then you see that s prime minus s is exactly the discrete log of t because that's the only thing on the right hand side that doesn't cancel out. So this adapter signature allows you to kind of do this conditional things where only if you take the money you will reveal something that allows you to get the secret that you wanted as like an analog of these hash lock transactions before.

>> So is this sort of the same thing where like you're not supposed to reuse the nons and then you're or something like that or >> no because it's so okay. So this is basically something that applies to the interactive protocol. Well, let's see here the writers. So what what Tim referred to was that if you run this protocol and you reuse the same R but answer a different C then basically from the two resulting S's you can extract the secret key. So it's basically exactly what happens in a security proof should never happen in the real world.

In the security proof, you imagine that if this proof convinces the verifier, once this R is out, there must be a good chance of replying to a random challenge. And so there's a good chance of replying to two random challenges. And if so, then you can extract the key. But if you do it in the real world, then you lose a key. That's actually something that has happened I think for ECDSA that has the same problem. There was some Sony PlayStation and that's how the secret key was extracted because they didn't use uh they didn't have a good randomness generation. And so so they use the same first message several times again like abstracting away. What do we have now? We have a protocol that allows you in an atomic way of buying a discrete logarithm for Bitcoin. And

once you have that, I argue that buying blind signatures is very straightforward because what you do is so now we want to buy a blind signature for Bitcoin. What you do is you just run the blind signing protocol. So the blind signer signs sends his message R. The user or the buyer sends her message C and then the signer doesn't reply otherwise the signature is gone and the bitcoin is not there. So what they do instead they run the protocol for buying this value s and this value that s is the discrete log of something that the buyer can compute. So as you can see with Schnore signatures you can simplify these uh anonymous coin

swaps a lot. In the remaining time I'd like to focus more on blind schnore signatures and the security properties that we know of it. So I told you that blindness is something that you can easily check and it holds unconditionally. But it's kind of the blinder the thing gets, the less unfortable it gets, right? There's a trade-off, right? So what do we know about one more unforgeability of schnoir signatures? What do we mean by one more unforgeability? And I argue what we want is concurrent security.

Why? Because if you look at an application of blind signing, think ecash, think a bank um signing blindly signing a lot of serial numbers. You want to be protected against concurrent attacks. Why? Because there might not only be Yuma the user. There might also be Usain. There might also be Yuri and while Usain probably replies very quickly, Yuri might start a signing session and disappear into space and then the bank can't just wait until he comes back before he issues like starts the next session, right? So you'll have this because otherwise he's vulnerable to denial of service attack. So you really want to uh have to interleaf sessions to start a lot of sessions and

then close them uh later. So what we know about concurrent security of blind schnore is Schnore himself showed that if the so-called Ross problem which stands for random inhomogenities in an overdetermined system of linear equations if this problem is hard then signatures are secure in the generic group model and the random oracle model right so that's very surprising in crypto proofs because if you already assume all these idealizing things then usually you don't have any assumptions you want to make but here you even need assumptions and so we showed that you can like show the same thing in the algebraic group model but what he showed is that it's actually equivalent he showed that if you can solve this ROS

problem then you can attack Bitcoin in a concurrent attack and it was for a long time yeah it was not clear how difficult this ROS problem was we knew that it would there were subexponential attacks but then four years ago uh there was a practical attack by Ben Hammuda at Al who showed that if you can open lambda where lambda is a security parameter think of 256 parallel sessions at the same time then you can very efficiently compute lambda plus one signatures right something you don't want from a blind signature scheme okay so the open question was can we define a secure blind signing protocol for shnore

signatures again there are concurrently secure blind signature schemes but if we need to use shnore because for example, we want to use it in Bitcoin or because we want to have a blind signing protocol for something that's standardized like at DSA, then um yeah, we need to like engineer around this existing signature scheme. Okay, so the the attack obviously uses the fact that uh there's these concurrent sessions and so what it does it it obtains a lot of R values and then it engineers the C values in a malicious way depending on all the R values. Right? So an obvious way of of preventing this attack could be to break this uh dependency. And so this was

together with my student Matias Wolfe who doesn't want pictures online. So I put someone else instead. The idea was that in the first round the user commits to all her randomness right to the blinding values and her message and then when she sends this challenge C. So note that now once the randomness is committed this challenge C is like determinist is like determined by the randomness and the value R right so there's only if you prove that the C is wellformed with respect to the things that you've committed then there's only one C that you can send and that breaks the the attack. So it turns out that it does not only break the attack but you can actually prove that that makes the

scheme secure. So we show that you get one more unfortibility if you assume unfortibility of schnore which for cryptographers is kind of a bad assumption right it's interactive but in practice it's kind of you wouldn't use a blind signing protocol for a signature scheme that's not secure right so that's kind of a minimum assumption you make on your system anyway and you need to assume soundness of your proof system so there's no other assumptions or idealized models or anything >> what do you mean you have to assume unforgeability of snor isn't known.

>> Yes, it's known in the random oracle model under the discrete log assumption. >> Yeah, >> but now we prove a statement about this hash function. So, we can't just pretend it's a random oracle, right? That's why we kind of make the assumption that for a concrete hash function, Schnore is secure, which is kind of just this interactive assumption, right? The adversary gets a public key can ask for signatures and then has to come up with >> so pi is like a snark or whatever you like general purpose. >> Yeah. Yeah. Yeah. Even if it wasn't I mean if it involved the the statement it can't be a random work right you can't prove. Yeah.

>> Are you going to say anything about the intuition about why without this trick like >> you know fails. Yeah. Like >> how the Ross attack works. >> Yeah. >> Okay. I can try. So it's basically >> I mean it's a bad idea. You don't have to do No, it's it's a bit technical, but it's basically you have to >> like 30,000 ft version or >> so what you want is you have all these R values and you want to um you want to somehow get a linear combination of these R values and the corresponding S values so that you can like satisfy so you have um so you can view it as

>> further. So the the what the attacker can do is choose all of the C's in a batch knowing all of the Rs. >> Exactly. So basically imagine you have a system of equations where every uh line is the verification of a Schnore signature. You want to have lambda plus one lines but then you only have lambda C's because that's the number of signing sessions and you and on the right hand side you have something generated by the random oracle which corresponds to this. This is why this random inhomogenity inhomogenities of this equation and now there's a way of obtaining um a solution which are lambda C values so that lambda one equations are satisfied and if you get these you can just do linear combinations of all the stuff you got

and obtain lambda plus one short signatures that's kind of the idea and it depends on yeah that you know all the R values and then you can choose the C's to your liking and not use what Uh here the snacks uses makes you use. >> So lambda here is going to correspond to the number of bits of the right hand side entries of these equations. Is that >> lambda? It's basically the way you do this linear combination is by a bit decomposition. That's where the lambda comes from. I mean you can also have it shorter by using like the old subex like combining the two attack using the subexponential attack and this trick. So you don't need to go all the way to 256 signing sessions. But that's when the attack becomes completely practical because then it's just Yeah. And so if I could do this attack, I can just make

the hub spend money to Bob without having to send money to the hub. Is that the consequence? >> I think the if like the simple example would be the the classical ecash. It's basically Alice ask like withdrawing Lambda coins but in parallel and then obtaining Lambda plus one coins. >> I see. >> Yeah, it's how severe the attack is. No, but it's really something you don't want in a in a blind signature scheme. That's nice and theoretical, right? But if you want to use it, you need to implement this proof. And so that's what we did in this paper. Um, we gave three implementations using at the time 2023, which is ages ago in in snark time, the state-of-the-art u available snarks. So

we used growth 16 and plon, which are two proof systems that require trusted parameters. And yeah, maybe a word on this. It's also kind of yeah you want if you're in Bitcoin everything's decentralized who sets up these parameters or in this blind signature example who sets up the parameters and since that's like uh an older result where I showed that gross 16 is subversion zero knowledge even if the parameters have been subverted zero knowledge is maintained and so here who wants to be protected it's the user sorry it's the signer that verifies the proof. So the signer can set up these uh parameters and then the user can be sure

that it's still this proof that she makes under the sinus parameters doesn't reveal anything about the about her message. Okay. Okay. And then plon and since these are snarks like the this is like um 400 bytes or so for gross 16 800 bytes for for plon and they verify really fast like uh surprisingly with this implementation plunk was a lot faster than gross 16 which was not to be expected. So all these numbers are very like depending on which libraries we use and because nothing was like really optimized this was basically just to get some idea of of feasibility. Okay. Now we know that snarks are short. We know that they are fast to verify. The um bottleneck is how complicated it is to

create them like the prover time. So this really depends on the statement because you have to represent the statement as an arithmetic circuit and then depending on how big the circuit is that determines the proof of time and the and the CRS size. So the statement is about these two things. So it depends on the elliptic curve you use and it depends on the hash function. So if we use snug friendly components like the baby jump job elliptic curve and the posedon hash function which have very low algebra like um arithmetic like low arithmetic circuit representation then you get numbers like this the CRS is less than a megabyte and you run for a second to generate the proof that's very nice but it's cheating right

because we said we want a blind signing scheme for something that's already used in practice. So now we have to deal with the bitcoin parameters which is the sep curve and char 2 as the hash function. And now of course things get ugly. You have like um this circuit rep the circuit representation of the statement has like a million constraints in uh R1 CS um specification and so your CRS becomes half a gigabyte and you and the proofer runs for a minute. But it's not I mean I argue it's not that shocking because if you look at what happened with the first generation of Zcash then they claimed that to produce the

shielded transaction the proof of runtime was like 2 minutes. So these are numbers that uh yeah didn't prevent adoption uh in the past. As I said, the problem is really that these um um so for the snarks we used um BN5 uh 254 um curves and they're like not compatible with the Bitcoin curve, right? Because the the fields are different and if this is what you need because you need pairings for these for these snarks. So if you use a snack that doesn't use pairings like Spartan, then you can actually use the proof make the proof use the twin curve of the bitcoin curve sack q whose order is the prime of

that curve. So this thing works really well together. So we expected this to be really efficient but um yeah nice but the proofer time was even slower but we think that's really because nothing was optimized of the of the the libraries that that we used. So this should be a lot a lot faster. So if we look if you look at this blind signing protocol um then the user proves some statement that involves the message right and so an idea would be can't the user not in addition prove any predicate of that message and that actually gives an instantiation of a primitive that seems very useful but hasn't been defined in

the literature which we call predicate blind signatures I think it's quite an obvious thing you might want to have. It's an um a generalization of partially blind signatures where the signer has some control over the messages that it signs. And so the idea is that now there's a predicate that the signer and the user agree on. They run this protocol and then the sign is guaranteed that the message that it's signed satisfies the predicate and the user is guaranteed that that's all the signer learns. Okay. And now yeah, let's conclude with a silly example. What you can do with this?

>> I'm sorry. to the point is any verifier also learns about the predicate. >> No, that's the thing like in partially blind signatures if you if you say that the public uh part of it is kind of the predicate of the message that's something that the verifier learns and the nice thing about these predicate blind signatures is that the result is a signature on a message and nothing else and it's completely independent of the predicate. I >> see. So the point here is that the signer may only want to sign certain messages such as messages that don't break the law or whatever. >> Exactly. Exactly. Exactly. Yeah. Yeah. Okay. Okay. So to conclude, uh here's a here's a a speculative application of this. So meet Sam the Sima Sina who runs a cryptocurrency exchange. And you know

these days people they don't own their bitcoins. They're actually in the exchange. And can we still have anonymous payments? And I argue that with this uh predicate blind signatures you could. So what the user could do is create a Bitcoin transaction from an address of the exchange and then have it signed blindly. Normally an exchange would never do that because it might lose all its money, which is what happens sometimes. So what you could do is use as a predicate that the amount of this transaction that you're signing is less than some value V and then the exchange can just debit the user account by V and yeah then this

becomes secure. I mean like this is assuming that there's a lot of people doing the same thing. So you have anonymity set there's only one address of the exchange. So it's not like realistic but just to some uh yeah example. That's it. So I thought since the Banksy Museum is just around the corner I might also put this picture here and yeah open for questions. >> So have there been better fixes for the ROS that avoid general purpose miss? >> Not to my knowledge. So, it seems yeah, seems like we're still state-of-the-art, which I also I don't see how there's any better way around it. It's like it's

really what you want to do is now optimize that snark. But like this idea, yeah, to prevent the attack is you have to avoid the the user from manipulating the C values and like how like what other ways are there? Actually maybe I should have asked this like in the beginning of the talk but you also care about here that like a malicious uh you you z cannot use the interactive protocol to learn something about the key >> or something like that right like >> that is basically covered by unfortibility right I see yeah it's >> oh okay that you're saying unfortibility already cut >> yeah if you if you learn something yeah I don't know like obviously if you learn a few bits about the key you can't forge

but there's like yeah I mean saying that unfortibility holds only when the user behaved correctly uh in the pro protocol or something but >> yeah but that would be very weak right you want to have >> no but I'm saying that I mean the only property like why do you care about leaking bits of your key as long as no one can make signatures of it and no one can make signatures because that's unfortibility that's yeah >> so would you say is there is there a big open question in blind signatures or like but differently like five years from now is there something you really hope the community has proven are constructed.

>> I mean, if it's for Bitcoin, it needs to be Schnore, right? Because they're not going to put the different signature in there. >> How about zooming out? >> Zooming out. I still think like uh you want in the end you want to use standardized signatures. So, I still think shore is a is a very good target of for optimizing blind sign blind signature issuing. So you think the most important thing is just to have better snarks for the for >> if unless someone finds a different way of securing it. Yeah. >> So if you did ECDSA blind signing, do you run into the same like >> let's assume the unfortunatility game reduces to producing an ECDSA signature.

>> Yeah. Yeah. Yeah. >> Now I don't know if ECDSA is secure or not, but I'll assume that. >> Yeah. >> With the instantiation of shot 256 or whatever. >> I >> do you need the same kind of proving with >> I don't know. I don't Yeah, I would have to look it up. The thing is that this other tricks we used, they really only work for Schnore, right? This adapter signature. So, in that sense, if you want that application, you already want but just blind signing maybe, yeah, maybe there is a you can show that heristically ECDSA blind signing is already concurrently secure.

>> Do you feel like with good enough snarks these would be used? I mean depending on how how interested people are in privacy, right? If you look at Zcash, this was used, right? This shielded transactions. So, yes, I think so. And I think as I said like uh the fact that you can use the that this seg curve happens to have a twin curve gives you a lot of uh like room to play with because then yeah like arithmet like this group arithmetic becomes native for the snark.

>> Yeah. No I mean I think there's nothing standing in the way of very fast provers with very nice ver verifier cost for this. I mean yeah the like sha will be the the big cost right because you this unless with your techniques you can do this faster because you don't represent it as a circuit I don't know >> probably today the two and a half minutes could be you know couple seconds or something >> yeah then I think it's usable right if you believe if you trust the snark >> does this blind paradigm make sense for more things blind encryption blind snarks I don't know like blind crypto photography, you know, I want to have an interactive protocol where a signer in

encrypts something for me, but they don't know what they're encrypting. I mean that's I guess witness encryption could be kind of viewed as this >> is that essentially >> but I think zero knowledge proofs are in a way already if if there are simulations sound there are already an a generalization of signatures because you you can like you prove some statement and even if you've seen a lot of proofs you can't make new proofs that's uh simulation soundness and then if that statement is I know my secret key that's a signature scheme but that statement might be anything so in that sense as like >> I need to know the statement I'm proving though is there a way for me to prove a

statement I don't know >> well you need to prove something right so there met the statement and then the statement just becomes a witness but you could generate a proof under an encryption >> I see okay >> and then >> exactly >> and then you give it back to the guy who decrypts it everything >> no but somebody needs to know the witness right like you need to extract from somewhere >> I mean if it no Like let's say functional encryption solves more than right? Because then it's still you have the you can't like delegate the way like delegate decryption in a restricted way to someone else right it's only you decrypt it or you don't in FG in function encryption you can say yes you can decrypt but you'll only

obtain a function of the message so in that sense it's more general but it doesn't solve everything. Thanks again.