Lightning Talk: On the (In-)Security of Fiat-Shamir by Ron Rothblum, Succinct

Transcript

All right. Uh, the final lightning talk that we have before the the second panel is Ron Rothblum from Succinct with a cheeky titled uh lecture on the insecurity of fiat shamir. Ron Rothblum. Thanks. >> Okay. Hi everyone. Um, I'm Ron Rothblam. I'm a cryptographer at Succinct and I want to talk to you about uh security today and specifically about one aspect of security that we tend to take uh somewhat for granted and I'm personally a little bit worried about and that's known as famil. So I want to kind of start the presentation with this very famous quote by uh Sylvia Mikalli who is

a very famous cryptographer who among other things co-invented zero knowledge proofs and uh snarks that cryptographers seldom sleep well. And the reason for that is that all of what we do in cryptography almost all what we do in cryptography relies on assumptions which we believe to be true but we're not sure. So we have to keep sort of one eye open when we're asleep to make sure that nothing broke. And you know, zooming in on ZKVMs, we're making uh a few cryptographic assumptions and I want to kind of like highlight what they are and kind of then zoom in on one of them. So, first thing I want to mention is this uh notion of proximity gaps with uh Arancha mentioned earlier in in her talk. Uh this is a conjecture that most teams rely on. I'm

happy to report that at succinct as of this week we're uh proving in real time without making this conjecture. So, I'm sleeping a little bit better. Uh so kind of happy about that. Second thing we rely on are hash functions that are collision resistant. Meaning that it's hard to find collisions in these hash functions. This is a very very standard cryptographic assumption. Ethereum relies on it. All of us rely on it on a day-to-day basis. Not particularly worried about that. The third one is fameir which I want to talk about today so I won't go into it yet. And the fourth one that which I won't have time to go into is about recursion. Um so if you're interested ask me offline about that. So I want to go into fiat shamir. So what is fiair?

So it's this beautiful idea invented by almos fiat and adi shamir uh almost 40 years ago in this beautiful paper. And what it lets you do is basically design interactive protocols. So back and forth interaction but then magically make them non-interactive which is kind of huge. And their original idea was to do this to construct digital signature schemes. But nowadays we're going uh far beyond that and using them to construct uh snarks and almost all snarks rely on this idea. Cool. So what is the idea uh in this transform? So we go from an interactive proof generically into a non-interactive proof. And the idea very briefly is as follows. So we start off with an interactive protocol say for example

something like fry. Um and you know so it's we have a prover P and a verifier V and they interact. They send messages back and forth. And we're going to make an assumption here that the messages that the verifier sends are just like uh random random messages. And it turns out that for the protocols that we actually care about, this is indeed the case. So we have an interactive protocol, but interaction is no good, right? We want to post our proofs on chain. We don't want to go back and forth. And what fmir lets us do is kind of replace this interaction by a hash function. So the idea is to build a new interactive protocol in which so you can emulate the first prover message easily. You just run the interactive prover but then rather than wait for the verifier to respond with its random challenge, you

derive the random challenge by hashing the message that you just produced. Okay, using that you can generate the next challenge and go so on and so forth and generate all of the challenges and therefore the entire proof. So this is the beautiful feature transform. It's very simple when I present it this way. actually doing it in code turns out to be more challenging and this is very well known to have a lot of implementation bugs but that's not the focus of my talk so I want to focus on doing feature uh you know as you're supposed to and what happens then and you might say you know if you do feature as you're supposed to then it's really really well battle tested we've been using fatir and in signature schemes for a very long time okay so why am I losing sleep over this

well the reason is that the way we use fatir nowadays is is very different than the traditional way in which it was used to build signature schemes in particular because we're now proving general purpose computations using feature and that worries me and the reason why it okay before the reason why it worries me a word about soundness so why is it intuitively sound well because the verifier's challenges are derived via hash they seem unpredictable to the prover so it seems to emulate the interactive case and you know in cryptography we're not uh satisfied with intuition we want more of an analysis So we've known for about 30 years now that fameir is secure if you uh think of the hash function as purely random function. Okay.

And this is commonly interpreted as saying is you know if you have an attack against fameir it means your hash function is not behaving as well as expected switch your hash function. So that's a common interpretation but actually this interpretation has been challenged. So sequence of works showed that there are examples of sound interactive protocols but if you apply fetch to them they are totally broken. So this looks very alarming but for a long time no one really cared so much because the protocols we had here these examples were convoluted. They were sort of um contrived protocols that were intentionally designed to fail. So people were not particularly worried. I think something uh changed a little bit and this work that we had earlier this year. This is with collaborators uh so

Dimmitri Kovtovich and Lev Suhanov both were at the EF at the time I think left maybe has left since then and in this work we showed that there's actually an attack against a real world protocol a variant of GKR that is very common um and popular and this affects real world systems so this is an example of a PR by polyhedra um giving a particular fix or mitigation against our attack so this is very much real world so given this attack Where do we stand in terms of of security and what worries me? So, so proximity gaps, you know, we know we can avoid them. Aranch already said we have to. So, worried about that.

Um, in the worst case, if we are not able to prove stronger bounds, we'll get a 2x improved size. Not ideal, but also not the end of the world. Collision resistance, as I said before, doesn't worry me too much. In the very unlikely event that someone says finds uh collisions in Poseidon, we'll switch to a different hash function. um we have a very very good understanding about collision resistance of hash functions. So that again does not worry me so much. Recursion overhead, I didn't have a lot of time to to speak about that. Worst case, we'll do less recursion. Maybe we'll do no recursion. We could work with steam improvers. This again is in the worst case in case something is broken. The one place where we don't really have a fix is frame mirror. Okay.

So we do know we have examples of real world protocols in which if you do frame they are entirely broken no matter what hash function you use. And you know if we had a similar attack against protocols that uh run in ZKVMs we would have a problem. So that worries me. I don't think this event is very likely but you know it's very very risky because we don't have a backup plan. So just to summarize I really view the the fetch security that we're assuming in snarks to be a new or different uh cryptographic assumption. I don't think we can just rely on the fact that it's fetchir has been used in a different way for many years.

the fact that we have the random uh oracle analysis is kind of is maybe good but it's not enough because we also know that there are attacks concrete attacks that are not captured by this random oracle analysis. So my conclusion you know famir is it's it's a it's an assumption and I think we're sort of taking it for granted and we need much more research about it. I can report to you that there's a line of work more of the in the theory community from which I come trying to instantiate future provably and we've made a lot of progress here but there's still a lot more to be done. Um so I think you know there may be some hope in the long run to use this line of work but we still have plenty to do. Okay so I'll I'll end the talk here and happy to take

questions. [applause] >> Thank you Ron. Um got a question from the audience. So are there any hardness assumptions on the hash function that make fiat shamir probably secure in a specific real world protocol in specific real world protocols? >> Yeah. So for the way we're using them in ZKVMs, the answer is no. There is an assumption known as correlation and tractability which sort of partially suffices. It would suffice for certain types of protocols which this line of work deals with. But the short answer is no. The assumption is that famil of this protocol is secure.

>> Great. Thank you very much. My >> pleasure. >> [applause]