ROM Lower Bounds

Transcript

Yeah, so let's start and we're going to speak about low bounds. You hear me well? Yeah. Yeah. Low bounds about length of random oracle models, SNARKs and signatures. Okay. This is joint work with Alon, Matias, Daniel and Elone. Yeah. Elone is around but he's not sitting here at the moment. And yeah, okay, let me start. So I'm not going to have constant in this talks, okay? I know that many of these talks are very like constant oriented.

We have very specific constant in the upper bound. I'm going to give you more theoretical talk. So no specific everything going to be asymptotic, okay? I think this is the most significant bit for this constructions but yeah, if you want to to derive like specific constant, you know, ask your favorite ML not me. Good. So what are you know, everyone knows what SNARKs are but let me still put it formally.

So this is non-interactive prover between the proof system between the prover and the verifier. And you know, the prover want to convince the verifier that some statement is correct. He send message, non-interactive message, Elone. And the verifier either accept or reject. Okay? In the random oracle model we have a random function that both can access the random function. And you know, the prover interact with random function, make some queries, >> [clears throat] >> prepare the proof and then the verifier reads the proof make queries to the random function and either accept or reject. Okay?

Good. And this is information theoretic model which what makes it easier for us to prove things about it because we don't understand computation, but we way better understand information theoretic model. Um and in the sense that when you care about security of such scheme, we only measure the number of queries made by the made by the attacker, we don't care about his computation time. So, let me be a bit more formal on what completeness means. Completeness means that um for a yes statement, uh if the prove you know, the um

Do you have a clicker somewhere? Do you see the clicker? No clicker? There should be clicker. Yeah. Here's the clicker. So, if the honest prover acts as it should and generate a proof, then the verifier accepts in very high probability over the random function. And to make the the discussion simple, I assume complete completeness is one. Okay? And whatever I say here generalize to imperfect completeness as well. Okay, this is completeness.

Soundness says the following, for any no statement, for the for the simplicity of this talk, the security parameter lambda, think about it 128, say. So, for the adversary that make fewer queries than two to the lambda, okay? The probability that it makes the verifier accept a false statement is little of one. Okay, this is just to make the discussion simple. Everything generalize to what called T epsilon soundness, where T is the number of queries made by the prover, epsilon is the acceptance probability. Okay? Just to keep it simple, think about if you make less than two to the lambda queries, you shouldn't be able to cheat.

Good. Uh let me move to signatures. So, signatures again, triplet of protocol algorithm, key generation, signature, and the verifier. And you this is standard you know, algorithms. And completeness says that if for any message with high probability over the random function and key generation algorithm output of the secret key or the verification key if the signer using a secret key sign a message, then with probability very high probability the verifier accept. And again, for simplicity assume perfect completeness.

And what unforgeability means many times soundness means that for any again adversary that makes less than two to the lambda queries and is admissible in the sense that you only output a signature on message it didn't get the signature of otherwise it's not very interesting. Then the probability that the verifier accepts such a signature is little of one. Again, everything extend to two epsilon soundness. And one-time soundness mean that the cheating the cheating signer can only make a single signing query. Okay? This is called one-time signature.

All right. So this everything standard, nothing new. I guess you all knew it before. Okay? Okay. Few words about the random oracle model, okay? So the random oracle model is simple information theoretic model. Again, we only measure the number of queries made by the adversary. We totally ignore the computation time. Which is good and bad. I'll address it later, maybe. And it support many many well-known constructions. Well-known random oracle constructions. What you call hash-based signature or hash-based proof system they are proven in the random oracle model.

And we use it because of the random oracle heuristics. This the reason you care about the random oracle model because we instantiate the the scheme while replacing the random oracle with say SHA-256. Is it Is it secure or not? This is a difficult question, but this is what we do. Okay? So random oracle heuristics are fast to compute, no trusted setup, uh potentially post-quantum, you know, like they're potentially secure. We have no way to prove that they're actually secure, even non-post-quantum, but what we for our experience, random oracle constructions are post-quantum secure.

Widely used in practice, as we all know, and the downside is long proof and signatures right? Comparing to other alternative, and this is what we're going to discuss in this talk. Okay, clear? So, this was like the introduction. Any question about Okay, so SNARK length. Okay, let's talk the length of SNARK. SNARKs, I mean length, I mean the how many bits are transformed. Okay? I measure everything in bits, not in bytes. I'm I'm a computer scientist. This is what we do. Okay?

Uh so, Micali construction, the the well-known Micali construction, the old SNARKs we saw in following's paradigm, is length is theta of lambda squared log lambda bits. Okay? This is the proof size. Okay? And it can be reduced to theta of lambda squared if the PCP is sliding a scale conjecture is true. And we have no better upper bound. I mean, all what amazing people do here is only fighting the constant, right? Nothing more than the constant, essentially.

Which is important, but again, not in this talk. And the trivial lower bound, assuming that our our instance instances, which is mean, uh you know, SAT is uh SAT is exponential hard, then you need to transform this proof need to be at least lambda bits. Okay? You know, crypto, if you want to get two to the lambda to be secure against two to the lambda adversary, you need to transform lambda bits of lambda bits. Okay? Good. So, there's a huge gap between the trivial lower bound and the upper bound. Okay? And this is what we try to address here. And if you need to compare to group-based SNARKs, which are much the lower bound, they're basically lambda we have to only transform the proof size only data of lambda bits. Actually,

lambda bits almost. Okay. So, let's state our lower bound. So, what we prove is assuming SAT is hard, then for natural, I'm going to explain what natural mean is, no, efficient random oracle SNARKs have proof size lambda squared over log lambda, which is tight up to log square factor lambda factor. Okay? And so, what are these natural constructions?

First, we require the verifier to be non-adaptive and deterministic. Non-adaptive mean that when he gets the statement and the proof, he can prepare all his queries and make I don't put bound the number of queries, but he can prepare all his queries in one once and ask them together, okay? It doesn't There's no sequentiality a sequentiality in the way it makes the queries. So, this is rather natural. We also assume salted soundness, which is non that standard I'm going to address in few slides. And all known non-contrived constructions are or can be made natural. Only thing, when you come up with construction, typically it's it is salted soundness, and maybe it's adaptive, but it's very easy to get rid

of this adaptivity in a lower price. Okay? Okay. So, uh for such scheme, we we push the lower bound to be almost matching the upper bound apart from log log square lambda factor. Okay? Okay. Automatically, you get also lower bound what we call vector commitment or commitment with local opening. These are you commit to a very large screen like Merkle tree, whatever. You all are familiar with this creature. You commit to a very large tree, and then to you can open a small portion of it using concisely using a a short proof. And because vector commitment can be used to get

SNARKs, because we have lower bound on SNARKs, we have matching lower bound on vector commitment. Okay? So, you know, these vector commitments are measured by the commit the length of the commitment itself and how how long it take to open a small portion of it. And, you know, assuming ARITH again for natural construction, we achieve tight bounds up to again this log square lambda factor. Good. Good.

So, what is the salted soundness? Salted soundness says the following. Typically, you know, the adversary can make queries to the random oracle and then send the message the the the the proof. In salted soundness, the adversary or malicious prover can interact with the with the oracle and then slightly program it in the sense of weakly program it. Namely, if he sends to get the answer and if he doesn't like it, he can query again the same value and get a different answer. The answers are random. He has no control on the distribution of the answers. But, he can try many samples and then in the end say say, "For X, I want to use the fifth answer. For X prime for I don't know, X2, I want to to use the fourth answer, etc. etc."

So, he has some weak control over the random oracle. Not full control because then it would be you cannot have a scheme in which the adversary has full control of the random oracle. Basically, the random oracle disappears. But, this is like weakly He has limited control on the random oracle. It's not standard soundness, but most scheme, uh yeah, yeah, then they verify. After programming, they verify and get the oracle. Only on SNARK construction have salted soundness. Okay? What we use about the random oracle is that you know, its answers are random and the fact that you can try several random answers don't make any difference, but it is easy to come up with with contrived SNARKs

which are not salted soundness. Okay? Okay, so it is what it is. It's a limitation, but it's rather It is in retrospect it's a natural limitation. Okay? Good. What about signature length? So again, for one-time signature length, we have you know uh if you ignore a constant, the best thing we we have is lambda or signature which is theta of lambda square bits. And if you consider adaptive uh verifier, then you reduce it by factor of log lambda.

And uh the trivial lower bound is again lambda bits. So it's still a huge gap between the lambda bits and essentially lambda square bits. Okay? And again, signature uh uh uh group-based signature are matching the lower bound. So the huge gap between asymmetric signature as we know and group-based signature and we're trying to justify it in the lower bound. Okay? What happened in many-time signature we are even worse off because the best many-time signature is uh lambda cube length and the lower bound is still the uh omega of lambda, only lambda bits. So the the gap is even worse.

Okay? So, what we show against for natural poly not natural random oracle one-time signature, the overall length, the verification key plus the signature is lambda square over log lambda. Which again, it's now uh uh uh uh uh log log lambda away from uh from uh uh what the upper bound. And it's matches Winternitz, but actually Winternitz is non-adaptive, so it's a bit of a cheat. Okay? Okay? And that's for construction that's the same, non-adaptive deterministic verifier salted soundness.

All known construction we are familiar with have salted soundness. But for signature adaptive sound adaptive verifier is helpful, Winternitz, but in very limited sense. Only shave log log lambda factor of the length. Okay? Yeah. So, again, for natural construction of boost the lower bound, you know, up to a log log lambda factor to match the upper bound. Okay? These are the result. Um Yeah, for many time signature is actually we we we show that uh um the thing it's not the signature plus verification key have to be long, but

the signature itself has to be long. Even if the verification key is very is used, still the signature itself has to be long, which for one time signature we don't know. Maybe can come up with very long signature verification key, and this will allow you to have a short signature. Okay. So, this about the result. Let's move to um to the proof. I think it's Yeah. I like it. So, uh proving. So, both the the lower bound for SNARKs, which we did like 4 years ago, and the lower bound for signature we just did now, follow the same paradigm.

It goes as follows. We have straight a short SNARK. We have what called the heating lemma, going to explain later. We show that a short SNARK translate to a SNARK in which the verifying make few queries. Okay? This is the key component of the proof. You have short SNARK, you can reduce it. Actually, it applies to any SNARK, but it's interesting for short SNARK. It translate to it to SNARK in which the verifying make few queries. And by work of Kiltz and alone, we show that if you have a SNARK in which the verifying make few queries, this contradicts it has fast fast relative fast SAT solver, which contradict LWE.

Okay? Again, the main component is the eating lemma going to address it soon. And similar for signature, we show that short signature translates to signature in which in which the verifier makes few queries. And this actually it's impossible. Barak Mahmoudi proved 20 years ago that in any signature schemes in the random oracle model, the verifier have to make has to make many queries. Okay? So again, the problem is the same. Give me short SNARK or a signature, I translate it to say SNARK in which the query is low query complex the verifier has low query

complexity and this is impossible. Unconditionally for signatures, conditionally for proof system. Okay? This is the the main the main tool we use. Okay? Okay. So let me show you how the low query verifier goes. I I focus on SNARK, but for signature it's slightly more complicated, but same same idea. So I give you a short SNARK, we construct low query verifier SNARK P tilde and V tilde. I only describe the verifier, but the prover will be implicit.

So the verifier V tilde emulate in some sense the original verifier. You know, you have access to random oracle. It has the same instance, it get the same proof, but it has additional part to the proof, which is the important query set. Okay? And then what he does he first he he he he he computes the queries made by the verifier. You know, because the verifier is non-adaptive, you know, given the the given the input, he knows what the queries going to make by the verifier. And then he addresses them differently. So for the important queries, he acts like the original verifier. He simply for the important query he acts he asks the oracle like the original verifier the

original verifier would do. And because this set going to be small, he's not going to make many many oracle to the to the oracle. Okay? There going to be few important queries for which he acts exactly like the original verifier did. But, for the other queries, it take a very different route. It ignores the oracle. It's not going to ask the oracle. This is going to be the vast majority of the queries. For each of them, it sample a random subset, which is large but not too large.

And then, it checks if there is a combination of the important queries and for each non-important queries, some one of the answer that it sampled such that would make the original verifier accept. If there is, it accept. If it isn't, it doesn't accept. Okay? Again, for the important queries, it acts like the original verifier. It does ask the oracle, but going to be few of those, so we don't care. For the others, it totally ignores the oracle. It sample a random subset of uh possible answers. And now, check if there is a combination of the important queries, the non-important queries that make the original verifier accept.

Accept if it does. Reject if it doesn't. Okay? So, the parameter we set is basically gamma is going to be you can think of lambda over two. And the important queries set, the size of it going to be the length of the proof over lambda, which makes it the if the proof was short, then the query complexity of the new verifier going to be low. Okay? So, there's two things we should care about. Why is it sound? Okay? We should prove that the new proof system is sound because then we apply the lower bound.

No lower bound of Barak and Mahmoodi. Okay? We should do a reduction from the security of the original scheme, which has short proof, to the security of the new the new scheme, in which has low query query complexity of the verifier. Okay? So, two part. First, what about soundness? So, this is the easier part. We can show that if the original scheme is salted soundness, then the new scheme is that sound. And the reason is that the an adversary that is can so as sorted soundness access to the to the oracle can mimic what V tilde did.

For the non-important for the important query does nothing. For the non-important queries, it's make many sorted soundness query and basically it mimic exactly what it did. This is the non less interesting part. The interesting part why is it complete? So, if gamma would be lambda, then it trivial because basically the verifier choose enough candidate which cover also the right queries. But, we choose gamma to be lambda over two, so it's got the exponential fewer queries than all possible answer. So, the right answer of the oracle the one that actually chosen by the prover do not appear in this list.

Okay, for the non-important queries, none of the right answer of the oracle on on based on which the the proof was constructed appears in the in the in in the candidate answer sampled by the verifier. So, it's on the face of it it's unclear why completeness should hold at all. Okay, do you see the point? Good. So, let me see two examples and then we go to the general claim. So, the example is assume that the proof contain a single the answer to a single query.

Okay? Then, it's very easy because I put this query in the important query set. And then the very the new verifier the original verifier you get the same answer. But, this the new verifier also ask the the the the the oracle on this query. And because the the the output of the oracle's are random, the proof cannot contain many important queries. Okay? And therefore, the J can be small. The the important query set remains small.

Way more challenging is what happened in global information. Think that the proof contain the XOR of many, many queries. You cannot put all of them in the important query set because they you want to keep it small. You want to keep the query complexity of the verifier very small. Okay? And there's no way the way the verifier can select it's going to sample the right answer to to to the oracles in in this subset because it's much smaller than all possible oracles. So, the idea is to use this this option because what we can show It's like a freak show you know, like game. Because there are enough options because the verifier

choose enough options for each of the answer with high probability is going to be a combination. If it's the wrong combination, it's not the combination used to generate the proof because there is enough freedom there is a combination that make that that with XOR equal to the proof to the value in the proof. Okay? So, again there's a distinction. If for local information, we put it in the important query list. For the non for the for global information, we cannot put it because it might depend on many, many queries. We have no bound on the query complexity of the original verifier.

But we can show that you can still handle it. So, because of the way you sample the answer, you sample the answer with the other queries. Again, this is clear for XOR but it's totally on the face it's not clear for arbitrary query query structure. Yeah, this is exactly what we prove. We prove general what we call hitting high entropy events. So, it's the following. If you have a random variable X over some product set whose entropy is very high, almost full, you're missing only L bit of entropy then with high probability over a sample from this random variable, there exists a small set a small subset of queries

which are important in exactly the same sense. If you you you sample the the the values >> [clears throat] >> from the other for the other entry of X at random for large enough subset, you intersect the support of the original X. Okay? This is exactly, if you think about it, the mapping is rather similar uh the mapping is almost automatic. Sorry. Yeah. If you set X to be the answer to V's queries and condition on pi because pi is short, you see we were using the fact that pi is short, the entropy of X going to be very large and therefore the small set J that makes

everything goes well. Okay, this is the technical part of of of the paper. Okay? Questions? No. Okay. Uh so, let me summarize. For natural random oracle construction, SNARK proof size is omega of lambda squared over log lambda which is tight up to log squared lambda factor. One-time signature over a length is same value, which is even tighter. And many-time signature length is the same value, but again it's not the overall length, it's only the signature length. So, it's a stronger lower bound, but it's non-tight because many times require lambda cubed.

Open question: to get rid of randomized into end or end or randomized adaptive verifiers. We can handle somewhat randomized verifier, namely one that the the queries are deterministic, but they use additional randomness. This we know to handle, but not general random verifier. Salted sounds, of course, get rid of the salted sounds assumption. A better bound for many-time signatures. We edit We would edit automatically if we have a better lower bound on the query complexity of many-time signature, but Barack Mahmoudi doesn't generalize to many-time signature. He doesn't have a better lower bound on the query complexity of many-time signature than he has for one-time signature. So,

the right way to go is to improve that. Very nice question. And finally, I think this is more philosophical question. Maybe it does have the wrong modeling. I mean, we really like random oracle model because it's easier to prove there. But inherently when we speak of random oracle model, we put no we consider adversary we are inefficient. They have bounded query complexity, but otherwise they inefficient. And in reality, we don't care about such adversaries.

So, can something be exploited? I mean, we have to get rid of this random oracle model we all like to to use to prove things. But maybe our talk or if you want to go more for even like the well-known impossibility result for key agreement in the random oracle model, okay, of impossibility of public encryption in random oracle, exactly as this problem, the attacker is inefficient. So, maybe there's a way to to overcome this this to use proofs think differently and then all this lower bound might disappear. Yeah.

Um Thank you. >> [applause] >> Yeah, Ali. Should be some Yeah. >> Thank you for the talk. >> Uh thank you. Uh why do you write that one-time signatures are tight up to log if you write that it matches Winter nights?

>> Because we only non-adaptive and Winter nights is adaptive. So, yeah, I mean, we are tight for adaptive, we are not tight. For non-adaptive, we are not tight because a Lamport is a log factor more in the length and we match the Winter nights, but is adaptive. So, >> [laughter] >> so they mean mean you have to differ if you consider adaptive then you are not tight because the non-adaptive were also not tight because we don't address adaptive adversary. But >> I'm going to propose something. So, it is very curious how the kind of lower bound techniques between kind of signatures and SNARKs

kind of have so much shared intuition and even expressions, right? It's kind of not a priori clear, but why that is the case. But it's just very curious. >> So, the case is because the answer to the random oracle a random string. And you cannot put too much random string in your short string. That's all. So, if you put it basically in some sense if you try to compress many random string into one string >> That's underneath there are similar numbers. What I'm proposing something concrete. So, because in the case of signatures, the lower bounds are unconditional, okay? And because already we have a auto research competition on the upper bound, this could be like a useful uh an experiment for trying to do an

auto research competition on the lowest bound side. I would start actually with signatures, not the SNARK, even though maybe ultimately we might be we have more at stake and interest on the SNARK side but like because there's even constants here to be gained, right? There's like information theoretic lemmas and there could be and the gaps might be technical nuisances that you know, when we write a paper, we're just not willing to deal with the hairy complex arguments that maybe AI is more than willing to sift through.

So, I think there's a few like well-defined targets here for a lower bound auto research challenge and it could be like a good experiment on that side. >> Yes, so as I said in the beginning, we the technical lemma was proposed 4 years ago. Then we had no chance to have like tight lower bound. These days, yeah, it's yeah. Definitely might be doable. Yeah. >> So, so I have results for SNARKs and for signatures. What about snarky signatures? Do they behave more like snarks or more like signatures?

>> We think so. >> Uh snarky signatures. So so basically it's a snark where you're also um tying the proof to a proof of knowledge that um you um it's only valid for a particular message. That's not obvious to me. >> So you take a a one-way function and you prove that you know a pre-image. That's uh so you need a one-way function. If this one-way function is the random oracle, then you need the code of it to to do the snark.

And then it's outside of the model. And if you add a random oracle, like if you add a one-way function, then okay. Like this doesn't apply. So these lower bounds are for signature schemes or snarks in the random oracle, no other assumptions. >> Um I'm I'm not sure that a snarky signature necessarily depends on other assumptions. >> So what is a snarky signature? Like how do you you prove something? What do you prove?

>> Um uh you prove something but uh so you you prove knowledge um and um you tie it to a particular message such that um the proof will not be accepted um unless the verifier um checks it against that message. >> No, for fine, the message I understand, but what do you prove something that has to be be related to the signing key? And the public key, right?

>> Yes. >> So what do you do there? You need some hash to hash the the private key have a public key and that goes into your statement. >> Oh, I see. >> Okay, and then you need the code of the of the hash. >> Mhm. Okay, I'll have to think about it more. Maybe we can talk about that offline. >> Okay, great. I think we're at time. Thank you so much, Iftach.

>> Thank you. >> [applause]