Zero-Knowledge & Quantum (Eurocrypt 2026)

Welcome to the the I guess the second quantum session of of today. Um So, uh our first speaker will be Zihan Hu. Um who will be talking about post-quantum security for succinct non-interactive reductions. Um and the paper is by Zihan along with Alessandro Chiesa, Zijin D, and Yu-Chi Chen. >> Okay. So, thank you for the introduction. Today, I'm excited to tell you about our work on post-quantum security for succinct non-interactive reductions. This is a joint work with my advisor Alessandro Chiesa, my amazing collaborators Zijin D and Yu-Chi Chen. They are also here today at Eurocrypt, so feel free to reach out. Okay. Let's get started. I need to first tell you what are succinct non-interactive reductions, the primitive in the title. They are really similar to SNARK, so let's start with the SNARK picture. SNARK satisfy some completeness, soundness, and non-malleable soundness. The most notable property might be the succinctness, which says that the proof pi is much much shorter than the NP witness length w. Okay. Then, how about succinct non-interactive reductions, or as in IRDX? I don't even know how we pronounce this word, so let's just use reductions to refer to the long word succinct non-interactive reductions for simplicity. Okay. Here are the differences between uh reductions and arguments. Verify now instead of outputting yes or no, we are output a reduced instance x', uh and then imagine that here we start from hard relation R and a much easier relation R'. Reductions also need to satisfy some properties, but now uh we are we care about whether the reduced instance and the reduced witness is in the reduce relation. So, I just put the statement everywhere on completeness, soundness, and not soundness. I want to emphasize again that this reduction also satisfies succinctness. Pi is much shorter than the W. Okay, great. Now, you know about the definition, but are they useful? Why we study them? The first reason that reductions can be composed just as in the picture shows to obtain a SNARK. Okay. So, if you can show reduction are secure, then you can automatically get a secure SNARK. That is to say, reductions are helpful in design of SNARK. Great. The second reason that in some applications SNARKs reductions can even be more powerful than SNARKs. What I mean that since we are aiming for something weaker, reductions are actually much cheaper to construct. So, in this proof current data, incrementally verifiable computation, if you use reductions, then you can obtain a much more efficient construction that we even use in the practice. Okay, great. Today, our focus will be post-quantum hash-based reductions. Why we study hash-based reductions? This is because they have a advantage of efficiency and also they have public setup. And why we study post-quantum security in specific? This is because those hash-based reductions are likely to be part of the post-quantum designs. And you know that now the quantum the Q day is really approaching and we really need to work hard to see if those proposals are post-quantum secure. This has never been established established before the reductions. Okay. So, where those hash-based reductions come from? They come from the so-called BCS transformation that originally work on two ingredients, IOP and Merkle tree. IOP is just the Oracle version of IP where the verifier only needs to read a few bits from the prover's message. And here the verifier is also a public coin. The second ingredient is the so-called Merkle commitment scheme where we need a hash function to compress a very long message to roughly half its length. And so on and so forth until you get a root. This allows you to locally open it very efficiently. With these two ingredients, it's easy to get SNARK. You just apply the idea of like let's say instead of sending those long proof, we can commit to it. And the second idea is that we still need to reduce those interactions, so we need another hash function for Fiat-Shamir to derive the verifier randomness. Then the prover can just send a short proof pi showing the picture and the verifier can decide on its own. The good news about BCS protocol is that it's shown to be post-quantum secure in ideal model. What I mean is that if you treat these two hash functions like this idealization, the random oracle, then the framework already showed that it is secure against any adversary that make quantum queries to these two random oracles. Then how about reductions? It's similar, but we replace the first ingredient IOP by its reduction version, interactive oracle reduction. So, here the verifier at the end will output the reduced instance. And with roughly the same idea, you can get uh 16 non-interactive reductions. Okay? This is very simple and efficient way to get reductions. And it's shown to be secure in the classical random oracle model. But, while it is believed to be post-quantum secure, such security has never been established in the literature. So, our question today is, is this BCS protocol really secure in the quantum random oracle model? You may see it like, "Wait, you already know something that works for the special case, works for the IOP. Why not just use it?" The answer is, we cannot and also we shouldn't. The first reason that they needed the underlying IOP to satisfy something that the current IOR does not satisfy. The second reason is that they only apply for IOPs, not IORs. And even in the classical setting, these two proofs are quite different. And we have even larger gap in the quantum case. The third problem is that they only prove non-adaptive security, while we want the stronger notion, adaptive security. And also, their proof is somehow somewhat monolithic, meaning that if you want to change the protocol just a little bit, then you need to redo every proof they they did. But, we want a somewhat more modular proof that aligns with the classical one. We are back to the drawing board. Okay? Now, let me tell you how our results solves all the previous issues. We prove we propose a new security notion called post-quantum zero-knowledge soundness that captures the Fiat-Shamir arrow just as the classical case. And we show that our security notion is very powerful. It implies the post-quantum knowledge soundness of the BCS protocol. Specifically, with the error roughly equal to the post-quantum zero-sum knowledge soundness error plus some collision error. Similar bound has appeared for the classical case in the literature. And that we show that even though we propose something new and it's post-quantum, but it's still very easy to work with. Because it's implied by some standard knowledge standard classical security notion called the relaxed round-by-round knowledge soundness. So, if you have a relaxed round-by-round knowledge sound IOP ILR, then it's automatically satisfy our new security notion with some quadratic loss. And here is the classical counterpart. So, if you put everything together, our result So, I'll just show that BCS protocol really is post-quantum knowledge sound with the error roughly equal to the quadratic loss times the relaxed round-by-round knowledge soundness error plus a collision finding error. Great. I have a few stuff to emphasize. The first one is that this classical security notion is really satisfied by the state-of-the-art ILRs. So, our our result applies for all ILRs we know. And also, here we mean adaptive security in contrast to the prior work. And our proof also have advantage that we analyze those loss from Merkle tree and the loss from Fiat-Shamir separately into their ends. And if put put it together, it's just gave you a modular proof saying that the BCS error is the Fiat-Shamir arrow plus the Merkle tree arrow. Even more, our bound are tight because of the pre- preimage finding algorithm and collision finding algorithm. Okay. Now we are about to go to the technical part. But due to the limited time, I will only talk about this our new security notion and how it implies the BCS security. Great. Now let's begin with the definition. Our security notion also mimic the classical one, so let's start with the classical zero-sum game where the adversary can submit a partial transcript as a move to the game. And the game will use this hash function, some some random function to derive the outputs. After this all T classical moves, the adversary will output a full transcript all this proofs and instance to the game and game will compute the reduced instance. The adversary wins if the reduced instance and witness is in the in the relation, while it does not know witness for the instance it begins with. The state reservation soundness error is simple. It's just defined as the maximum probability that T move adversary wins in this game. And if you look at carefully, it's a really capture the classical Fujisaki arrow if you treat the Fujisaki arrow function as a random oracle. Great. How we lift it to the post-quantum case? Most of the game are just the same, but so instead of the classical move, now we allow the adversary to make a super position move just showing the picture. It's the first register is just again the a transcript and the second register is for answer. The game will use a coherently evaluate random function to derive the answer. And after all these T quantum moves, the adversary will again output exactly the same outputs as the classic case, and it's still classical. The game will compute the reduced instance as usual. The winning condition is same, and we define the post-quantum zero solution noise soundness error just as the maximal probability that adversary wins in this post-quantum game. Okay, so the only difference is that the game we have in the game we have a quantum moves. And again, just as the classic case, this really captures the post-quantum Fisher-Rao Great. Now you know about the definition, how we do the security reduction. Again, let's start with the classical picture. We get get some insight from them. Okay, so the in the classical case, the idea is just to construct a zero solution adversary by simulating the BCS adversary and show that they roughly have the same winning probability. However, they have really different query interface just as shown in the picture. In the left, the BCS adversary queries to random oracles, while on the in the right, they have only some budget for moves. So to match the interface, we need to specify how does the reservation adversary understand those random oracle queries and how it derives outputs. Okay. The first one is relatively easy. You can just maintain a database for that. It's just a list sampling classical database. The last item is also easy. With the database, you can extract underlying pies from CM. The tricky part is second one. A natural proposal might be like we just use the database to extract the online pies and make a move. However, we really need to carefully show that uh this simulation does not hurt the winning probability. To be more specific, uh if in the real world the future mirror queries are answered just as the uh the hash value on CM and if we use this uh proposal to simulate the future mirror queries, and they will be answered by those hash values on pies. So, can adversaries really notice this simulation? Unfortunately, it is easily noticeable. But fortunately, uh if we put this CM in the hash value uh in a hash input, then uh these two are really indistinguishable. So, in the actual proof, we also use the uh include salt in the definition in order to incorporate this CM. Okay, great. Now, everything's fine is fine in the classical case. How we leave it to the post-quantum case? The idea is roughly the same, but uh now the query access are quite different. The BCS adversary now has a quantum query, and the simulation adversary has can have a quantum moves. So, again to uh match the interface, now we need to simulate those quantum queries and derive outputs. If you are familiar with QROM technique, the first one is still easy. You can use Gentry's compressed oracle to get a quantum database to simulate those uh queries. And the the last one is also relatively easy. Prior work show that as long as this CM is classical, uh Uh, then then this should not hurt the winning probability. The tricky part is still the second one. Uh, the natural proposal to lift the uh what works in the classical case is just to coherently extract pies from CM and then make a move. But again, we need to show this does not hurt the winning probability. Well, now the two oracle access are in the quantum uh queries. Can we use private technique to show these two are indistinguishable? We found it's really challenging cuz private work only deal with classical of CM. Well, now in these two queries, you really have superpositions of CM. We need a new technique. We propose a generalized instability lemma saying that uh for any partition of the database, if uh deciding which partition set database belongs to commutes almost commutes with a classical query, then its quantum version commutes with a quantum query. Privately, it was only known for binary partitions. And since now we can deal with uh exponentially different partition sets, we can deal with those exponentially possibilities for the online pies, and this allows us to deal with this CM in superposition. Great. Now, let me summarize. Uh, we showed that the BCS protocol is post-quantum straight line straight line knowledge sound uh in ideal model for all the set of honest IORs. And our proof has additional advantage that uh we analyze the Fujisaki-Okamoto error and the Merkle tree error separately as just as shown in the picture, this mirroring the classical proof. I didn't mention it uh in the talk, but we also uh isolated the required properties of V C into a clean nice definition here. Okay. That's all I have today. Thank you for your attention and I'm happy to take questions. >> [applause] >> Thank you, Zihan. Any questions? >> Hello. Thank you for this talk. So, my first question is uh uh so, the this notion of succinct non-monetary reduction, is it like a similar notion of reduction of knowledge that it is just a hash-based variant so you can apply it for something like a folding scheme-based incremental verification incremental computation? >> Yeah, just probably it's hard to go to the beginning of the slide, but these reductions are really used for those like incrementally verifiable computation. Uh and also like it packed as the folding scheme or like accumulation scheme to use in those applications. >> Yeah, so my second question is in this quantum model, like when you apply it to like when you apply that folding technique I I know with the reduction loss accumulate exponentially with with regard to the step. Uh I I'm not sure if I answered it accurate I'm asking it accurately. >> Okay, I think though those folding step happens in the underlying information theoretical coin the IOR not happening in this compiler. Uh for our compiler, if you like sequentially compose it, the loss is just like the loss from the first component plus the loss from from the second component. So, it's not exponential. >> you if you just in this case the is additively loss. So, okay. Thank you. Thank you very much. >> One more quick question, maybe? >> Thank you for the nice talk. I'm just curious, um, would you comment a bit about this round-by-round knowledge soundness, how it differs from the standard uh, knowledge soundness? >> I see. That's a great question. Uh, so in the recent work, they studied this relaxed round-by-round knowledge soundness. It's just saying that, uh, uh, you first get, uh, like a witness from the from later round, and then you need to get a witness for the previous round. So, it's like, uh, uh, the state function also has, uh, like, uh, witness as a input as as far as I remember. Uh, yeah. >> Great, so let's thank Zihan again. >> [applause] >> Okay. Um, so the next talk is, uh, "Black-Box Simulation Barrier Persistence in a Fully Quantum World" by, uh, Ni Wai Chao, uh, Kai-Min Chung, uh, Xiao-Liang and Jia-Hui Liu, and Xiao will be giving the talk. >> Okay, um, thank you for the introduction, and, uh, thank you for all for being here for this talk. Uh, I'm Xiao-Liang from the Chinese University of Hong Kong. Um, uh, today I'm going to share our new results on the black-box simulation barrier for quantum knowledge So, I'll start with the recording the, uh, setup of zero knowledge. Uh, this definition for this zero knowledge is, uh, I believe you are familiar with. Um, here intuitively, it's basically interactive proof or argument system, where the verifier learns nothing more than the fact that X is true after the interaction. This is just our intuition. There is a mathematically formal way to define this ZK property, which we shall look at later. But for now, I'll emphasize the uh importance of [snorts] this uh primitive. As you know, this is one of the central crypto tool and uh it's behind the many of the applications such as uh authentication schemes, blockchain, and cryptocurrencies nowadays. Uh it's also fundamental to secure two-party and multi-party computation. That's just because ZK is literally a special case of two-party computation. So, your understanding of ZK both on the possibility and impossibility will contribute to our understanding of 2PC and MPC directly. So, because of this, this notion has been like has been like studied uh and draw a lot of research attention. Um we have a deep understanding of it for both the constructions and impossibilities. So, today uh this talk will particularly focus on the lower bounds of the round complexity. Basically, it asks how many number of rounds are necessary to finish this uh zero-knowledge interaction. Here, rounds are defined as the number of messages exchanged between these two parties. Okay? It's a special case of uh communication or complexity. So, why this problem is interesting? That's just because uh if you have a deep understanding of this, like it can guide the future design of the protocols. Basically, you know what you cannot do. So, it won't waste your time. And also, um as this is a special case of 2PC, the lower bounds for interaction complexity will directly be the lower bounds for interaction complexity for 2PC. And also, as we will see later in this talk, uh this uh problem is closely connected to some general theoretical computer science topic, especially the computational complexity and communication communicational complexity. So, um before I start, uh we need to first recall the formal definition of zero knowledge. Uh as you know, uh we define through the something called simulation paradigm. Here, we basically compare two world. The first world is the real world where nothing but the interaction of the like real parties. You have a uh prover and a potentially malicious verifier. The prover holds the witness and talks to the potentially malicious verifier. So, to define ZK, we're going to compare it with something called simulated world. In this simulated world, there's no real prover, but we have something called a simulator. The main difference between a simulator and the honest prover is that simulators don't The simulator doesn't have the witness for the statement. So, here uh the simulator in this simulated world is trying to enforce the malicious verifier to output the same thing as in the real world. If there exists such a simulator like who can successfully enforce the malicious verifier to output the same thing as the in the real world, then we say this protocol is a zero knowledge. The rationale behind this is just because in this simulated world, there's no witness at all. So, it doesn't contain any information related to the witness. So, if what the verifier outputs here is the same or indistinguishable from that in the real world, that means the real world does not leak any information about the witness as well. So, that's a formal definition. But, if you look at this this definition for a little while, you will realize that there is a asymmetry. Like in a real world, the prover can finish the interaction just because he has this honest witness. But, in the simulated world, why? Why should we expect that such a simulator can finish the interaction without witness? So, putting in other words, this simulator has to have some advantage over the honest prover. Otherwise, this is impossible to achieve. So, one common way to define the advantage of simulator is we allow the simulator to do something called a rewind. Basically, um the simulator can try to interact with the malicious verifier for multiple times. It starts one interaction. In the middle of the interaction, if there's some message that the simulator cannot answer, the simulator simply drop this interaction and start from scratch to start a new interaction, possibly with a different interaction path. He can keep doing so until one day he found a full full complete transcript finished the finishing the interaction. So, that's the advantage of simulator. In this definition, the simulator actually is only makes use of the malicious verifier in terms of its API, basically input-output behavior. That's why we call it a black box simulation. We treat the verifier we start as a black box. Uh I do emphasize that that there exists something called non-black box simulation, where in addition to this black box use, the simulator also can somehow utilize the code of the verifier. In this uh simulation paradigm, possibly the simulator can do something different than simply rewinding. However, I do want to emphasize that our current understanding of non-black box simulation is quite limited uh both in possibilities and in impossibilities. This is really a direction like worth further research. But in this talk, I will solely focus on uh black box simulation. Okay. So, for black box simulation, first I want to recall some important results in this line. Um I do want to emphasize that this is a very important line of research. The this line of research starts like dating back all the way to 19 1996 by Goldreich and Krawczyk. Um so, I didn't list every paper in this line, but just a pick two of them, which are most closely related to this to our work. So, the first work is by Barak and Lindell. Uh they proved that in the totally classical setting, uh you cannot have constant round zero knowledge unless BPP equals NP. Okay? So, here the hardness assumption is necessary because uh by definition, zero knowledge is a trivial for the class BPP. Cuz for BPP, you can compute the witness yourself. So, you can construct a trivial simulator. So, you do need some hardness assumption. The BL results is for constant round impossibility assuming BPP equals NP. Just recently, uh the work by Cha, Chung, uh Liu, and Yamakawa proved that um basically lifted this result to the post-quantum setting um under a different assumption that NP is a subset of BQP. Basically, if NP is not a subset of BQP, then uh constant round zero knowledge in the post-quantum setting is impossible. Okay? So, our results basically can be understood as lifting the results to the fully quantum setting. Cuz this one only focused on post-quantum setting, meaning that all the honest parties and their communication channels are classical. It's only the malicious verifier who could be quantum. And also the of course the simulator. So, um why this uh results is uh interesting, though um there are basically four reasons. First of all, if you only have the impossibility result for post-quantum setting, you cannot explain the fact that there exist a fully quantum zero knowledge where all the parties are quantum, as well as like fully quantum multi-party computation. It's a multi-party computation where you want to compute quantum functionalities. And that's like necessitated uh quantum communication. We have such notions, but we don't have a constant round constructions. So, but our impossibility result can be used to explain this unsatisfied situation. And also, um if you view it from the quantum supremacy perspective, actually there exist uh several crypto primitives such as the quantum key distribution. For example, in the classic setting, you cannot do this without public key assumptions. But, in the quantum setting, you can you can't do it with like without public assumptions. So, this notion demonstrated some sense of a quantum supremacy. Also, for OT in the classical setting, you need a public key assumption, but in the quantum setting, you only need post-quantum one-way function. So, and also non-interactive commitments and the interactive arguments, you can use quantum ability to compress their round complexity. So, given these interesting quantum supremacy results, one would be interested in asking, like, can you achieve some form of quantum supremacy for zero knowledge as well? Our result says no. Even if you have full quantum power, you cannot use it, for example, to compress the round complexity further beyond a constant. So, the situation is very much similar to the post-quantum and the classical setting. And also, um uh this uh our results connects quantum zero knowledge to the problem of whether BQP equals QMA. So, uh it has been a very interesting relation between the round complexity of uh round complexity of zero knowledge and the compu- computational complexity. But, if you just stop at the post-quantum land here, you can only relate to relate the BQP to NP. That's because the honest parties are classical. So, if you if you want to prove something by the honest protocol, it has to be something in NP. So, our results, like, allows the quantum communication quantum protocol. In this sense, like, the honest parties could at least have a zero knowledge protocol for QMA. Then, our impossibility connects QMA with BQP. This is I think more interesting than just connecting it to NP and BQP. Uh also like in terms of our technique, uh as you will see later, is the fully quantum setting is quite different from a post-quantum setting. Uh we need a basically a new mathematical language to capture or to do the analysis and to capture the essence of the impossibility. Uh that's basically the why this problem or our results is interesting. Okay. So uh first uh before I talk to the uh technical parts, let's first uh uh go back to this picture where the simulator has advantage over the uh honest prover by rewinding. So the things in the black box setting, rewinding is the only advantage. So if you want to prove impossibility results, there is actually a unified paradigm. Like if you can find some way to invalidate the simulator's power of rewinding, then like you can possibly achieve a impossibility results. So this paradigm is typically instantiated in the following way. First, you take a zero-knowledge protocol for which you want to prove impossibility. For example, a constant-round zero-knowledge protocol. Uh then out of this honest orange-colored verifier, you build a malicious verifier V star. This is the purple color. Uh typically this V star is nothing but uh just the original V with random recording. For this V star like people develop a different kind of techniques to prove that no simulator can exist or no simulator can work for such a V star. So that's a like generic paradigm. I haven't explained why it works. Now now let me show you why it works. Okay. Take this uh uh uh let me be more concrete about the setup. For example, you have honest prover P and honest verifier V here. You build a malicious verifier out of this honest one. This malicious verifier works in the following way. You pick a random function h epsilon. It basically outputs one with probability epsilon, but otherwise it outputs zero. So, at a certain round I, the malicious verifier you build just to forward this all the prefix that this is a PI, so the PPL all all the current transcript to the random function. If the function outputs zero, this V star abort game immediately and output a rejection. Okay? However, if this uh function returns one, now this V star going to utilize this honest verifier by feeding into the whole transcript and learn the next message and then forward it to the external prover. Okay? The malicious verifier we start we build does this at every round. It basically is querying the function and deciding to early abort or not. If it doesn't early abort, then the game is just like a real execution between P and V. So, here the first observation is that you can you can adjust epsilon like to to um adjust the early aborting probability. Smaller epsilon means that you abort more often. Okay? Um Now, with this general template, uh I can interpret the Barak Lindell results in the following way. They basically found a clever way to set up this epsilon. So, this is this clever way is the highly non-trivial and I don't have time to introduce how they did that, but they did that to achieve two effects. First, they prove that by setting this epsilon properly, the honest prover can still go through the execution with one or poly probability. However, the successful rewinding will only happen with almost a zero probability. Um since I'm running short of time, I won't go through all the technical details, but these two things together will imply that uh if you run the simulator with the V star because of the first result the simulation is close to the real execution. So, the simulation should always make the verifier success except with probability one over 40. However, in the second case since the we're running happens with probability zero, basically such a simulator can be interpreted as a malicious prover together with this uh random function. So, if there's no revamping, the interaction between the simulator and this uh H and V together is our malicious V star. So, this part of interaction will become straight line because there's no revamping. Then, you can basically forward this interaction ex- outside. You can think that the V honest to V is now is external and you have a malicious V star to interact with this malicious to interact with this honest to V. Then, based on this this V should accept with probability zero. These two things putting together will give us the BQP decider. That's the paradigm of uh this how how we instantiate that random reporting paradigm. Okay. Next, um CCLY basically extend that techniques to the post-quantum um They first they get stuck at the place that if you look at this picture you need to forward this message to the external honest verifier, right? But, in the post-quantum setting simulator has quantum, malicious verifier, which is a combination of H, epsilon, and V are quantum. Uh implication this is that this part will actually be quantum. So, they need to handle the situation like how do you forward a quantum message to a external classical verifier? So, um without um going too much into the details, basically they utilize something called the measure and reprogram technique developed by uh 34 et al. First initially for the uh initially for the quantum uh fast Fourier transform, but roughly speaking, uh this technique uh selects some random uh positions or random quantum message and measure them and forward the measurement outcome, which is classical, to the external verifier. By our careful analysis, uh this will only affect the winning probability of simulator by one over poly. Okay. So, if you play with the parameters carefully, you you can use this technique to recover what we saw in the previous slide as in the classical setting to eventually achieve the impossibility. Uh another thing that's very important for the analysis is this uh V is actually deterministic, so that if you repeatedly ask the same P message to the verifier, the verifier is always like respond you with a concrete fixed V response. Let's fix this as the only man technical tools if you want to contact this to the post-quantum setting. So, in our setting we need to lift everything to the fully quantum setting, uh there are basically two obstacles. First of all, all the previous message are quantum, like you cannot even define this random aborting verifier. Uh you cannot apply this to random function to this uh quantum history and then ask the verifier to to to to decide to continue or abort. So, we solve this by uh change the model to this the model where the prover and verifier they pre-share some EPR pairs and instead of sending the actual quantum message, uh the prover just do do teleportation, so that the you the prover send the classical teleportation keys to the verifier. So, now you need this way, we basically we dequantize all the first message. But, I would say that this is only a syntactic solution in the sense that we push the problem to somewhere else. The real problem is not really the the the the communication. is really that the verifier in the quantum setting is not classical. So, here um we design some uh techniques um to handle this the purely quantum verifier. Uh I don't have time to go through the details one by one. I will just summarize it as uh uh if you take looking at the purified point of view and uh uh we develop bunch of technique to recover the fact that simulator can only learn one response for each round. This is a classical intuition. You need to lift it to the quantum setting using some very very different quantum language and a new uh design. Okay. So, um So, this talk like I've been focusing on uh research background, interpretation of our results, and also technical difficulties. But, I say very little about our actual techniques. Um Uh that's because uh it's impossible to describe our techniques even at a very high level. I I give this talk once, and I cannot even finish the technical discussion in 1 hour. So, but fortunately, there are two 1-hour talks on YouTube. Uh one is given by me at uh total crypto workshop. Uh the other one is given by my collaborator, Jiahui Liu, uh probably at MIT. Um if you're interested, uh my version is more on the techniques, and her version is more on the background. You can uh take a look of one of the uh two talks. Okay? Uh this is our full paper if you're interested in the full technical details. Uh warning you that it's more than 100 page. So, uh probably you you want to look at the talk first. Yeah. Um yeah. With that, I will end this talk. Yeah. I'm happy to answer any questions. >> [applause] >> Okay. So, since we're tight on time, I think questions will have to be offline. Um so, uh the next speaker Thank you, sure. much. >> [applause] >> Thank you. Okay, um so the third talk of this session is a sum check protocol for approximate computations um and talk will be given by Zachary Des Fontana. >> All right. Thank you very much. We have the slides. All right. So, I'd like to start with an apparent conflict. On one hand, we have proof systems. These are interactive protocols where in approver can convince a verifier that it executed some computation and this computation produced some outputs. On the other hand, we have the sorts of computations that people in the real world actually care about. These computations are overwhelmingly numerical. These show up in AI, in physics, in engineering, in graphics. This is what computers from the beginning were designed to do, these numerical computations. Today, supercomputers are measured in how many numerical computations they can do per second. And we have specialty hardware to do numerical computations. We have floating point units, special processors for them basically in every single CPU and GPU today. So, the conflict arises because in proof systems, we work with exact arithmetic typically over finite fields. And these field operations need to be simulated in software. Whereas on the numerical computation side, the hardware natively supports these operations and these operations are approximate real operations rather than exact. So, today if you want to combine the two, you take your numerical computation, say a large language model, and then you need to pay first to fit it somewhat awkwardly into a proof system crossing the barrier from numerical computing to proof systems. And then you have to pay again to cross back to hardware which supported numerical computations in the first place and not proof systems. To go one way you're paying about three orders of magnitude in overhead. And then to go the other you're paying another two orders of magnitude. These overheads compound and this becomes totally impractical for anything beyond a simple demo. What I'm going to talk about in this work is redesigning proof systems from the ground up with numerics in mind. We're going to design a proof system that itself is a numerical computation. So it's very efficient to translate the underlying computation into the proof system. And it's also very efficient to implement the proof system on real hardware today. Where we're going to start is the sum check protocol. This is an interactive protocol where a prover makes a claim about the sum of an exponentially large number of polynomial evaluations. Prover and verifier interact and by the end if the prover was honest the verifier is indeed convinced that this is true sum of evaluations. We're going to make an approximate sum check protocol. By that I mean the prover and verifier are solely going to a perform approximate real or complex operations. And the statement that the verifier is convinced of is a little bit different than the typical case. Rather than being convinced that the sum is exactly equal the verifier is instead going to be convinced that the sum is is reasonably close is within some big delta. One of the reasons that this is so challenging is if we look at the classical sum check protocol it doesn't matter if the prover's claim is far from the truth if it's near to the truth unless it's exactly correct. With high probability the verifier is going to reject. Moreover this is an inherent property of sum check. Sum check protocol is fundamentally built on air correcting codes. Air correcting codes have these these the sensitivity property which is undesirable in our case. So, what we need to do is we need to redesign the protocol from the ground up, discarding air correcting codes, and we need to redesign the analysis of the soundness also discarding air correcting codes. What I'll walk you through here is just the high level of the soundness argument. There are lots of new tools we need to bring in to talk about completeness, talk about soundness, talk about round by round soundness. Moving away from air correcting codes, there's a lot of numerical analysis, complex analysis, a lot of subfields of math and computer science that don't necessarily see the light in cryptography typically, and so uh if you're to take one thing away from this, it's that these tools are particularly interesting and can be applied in the setting surprisingly. So, when discussing soundness, I need to provide you a little more detail on the classical sum check protocol. I'll walk you through that. I'm going to walk you through the classical soundness argument, and that will serve as a template for trying to get the approximate sum check to work. So, in the classical sum check protocol, we have some polynomial G. This is a V variate D degree polynomial. Prover's going to make some claim about the sum. It's going to send over a small D degree polynomial univariate that's consistent with this claim. Verifier checks that this polynomial is indeed consistent and sends over a random value. Now, this repeats recursively. Reason this can repeat recursively is that now the verifier has claim of the identical form essentially. We have on the left side constant value, and on the right side a sum of polynomial evaluations. We call sending over polynomial and then getting back a random challenge one round, and And protocol involves many of these rounds. So, if we want to prove soundness here, we're going to take a look at a single round. Let's take a look, for example, at the first round. Let P be the polynomial that the prover sends, and let Q be an honest polynomial, what the polynomial what the prover would send if it was being honest at the beginning. So, we have that if the prover lies about the sum initially, it also needs to lie about the polynomial it says. So, P and Q disagree here. Now, by the factor theorem, we have that P and Q can only coincide on so many points. In fact, they can only coincide on D points, which means that the verifier is sampling random values from a set S. The probability that two polynomials evaluate to the same points is bounded by the degree and the size of the set. Once we have this, it's simple union bound over all the rounds to prove the soundness of the classical sound check protocol. It's a number of variables in the original polynomial times the degree divided by the size of the sampling set. So, now if we return to the protocol and we want to make this approximate, I'm just going to take every single equal sign, and I'm going to turn it into approximate equal sign. Prover is going to compute a good enough P. Verifier is going to check that, yeah, it's a it's good enough polynomial. It's going to send back a random challenge, and then they'll recurse on this new approximate claim. So, using the template from before, the classical sum check soundness arguments, let's see if we can rerun it and get it prove the soundness of this protocol. So, we start out, and we have that, well, the initial claim, if it isn't approximately equal to the true sum, then it must be the case that the true polynomial and the polynomial that the prover actually sends aren't approximately equal. Now, equality and inequality of polynomials is well defined, but approximate equality, that's not quite well defined, but let's let's just try and get past that for a second. We'll return to that. We also need some sort of approximate factor theorem. And that, at least we don't have. So, now we have two issues that we need to resolve to get this this proof template to work. And I'll show how we work through them in order. To start, take a look at these polynomials. Are they similar? Are they different? Are they close? Are they approximately equal? What about these two? They they certainly look a little bit similar, especially over the center of all, though they have different degree. We need an objective measure. And while there isn't a canonical measure, there there are several objective measures. And we're going to pick a particular one that has nice features for our analysis. One we'll pick is the maximum magnitude of the difference of the polynomials over some specified interval. This has the nice property that if you're working with constants, it sort of generalizes the notion of distance of constants or the difference of constants, because the difference of constant polynomials has a maximum distance that's just the difference of the constants. We're going to denote this, for example, for an interval J using this notation. Now, we think about what do we want from an approximate factor theorem? We'd like that if we have the difference between two polynomials, if we equi-space uh points, and we sample from these equi-spaced points, and we know that a polynomial is large somewhere, we should also like that we can bound how often it's in some small horizontal strip. Taking a cue from the original factor theorem, which I've written here in a more general form, which supports both the case where P and Q are equal, and where they're not equal, we might come up with uh something like this. And I'll walk you through this. First, we have the probability that random evaluations are close on the left side. This is coinciding with the probability random evaluations were exactly equal in the factor theorem. Then we have a nearly identical term where it's just dependent on the the degree that fraction of evaluations that could actually be zero if they were non-equal. And then we have this extra term that says something about whether polynomials are approximately equal. And this is corresponding to the in the original term whether they're exactly equal or not. And now you might reasonably object that there's something I haven't talked about. What's going on with this kappa here? Surely this is where all the complexity lies. I've been I've been turning equal signs into approximately equal signs. I've keep hunting complexity as we go along. Surely we can't get a nicely formed kappa here. Especially given the fact that on the left side we're sampling from a discrete set and then the right side we have a probability distribution over uniform distribution that's continuous. Well, luckily we do have exactly what we need. If we go back to the turn of the century, Evgeny Yakolevitch Remez has a theorem that can help us. This is his theorem right here. Give you a moment to digest it. I I'll translate it for you. This is a slightly atypical rendering, but if you have a D degree polynomial over the real numbers and you have some measurable subset of some interval, there's a relation between the size of this subset, >> [snorts] >> the size or the maximum magnitude over the original interval, and then the maximum magnitude of the polynomial over this this restricted subset. And here we have an explicit kappa which depends on the D degree Chebyshev polynomial. To help you visualize this, this is sort of what the kappa looks like for various degrees. It's monotonically increasing from zero to one in both the domain and the range. Now Now, interested in this for the opposite reason that we are. He's interested in approximating functions. He wants to say that if we have a very good approximation of some functions, so if if difference between two functions is very close to zero for a large subset of an interval, then it can't be a terrible approximation somewhere else. Can't be large somewhere else. We're going to use the contrapositive of this, that if F is far away, so if the the two polynomials are very far away from each other in some location, then they can't be close very often. And what it so happens that this Remez inequality implies a factor theorem of an approximate factor theorem of exactly the style that I presented before. Moreover, this isn't just for the real numbers. There are Remez style inequalities for a variety of of different domains associated with metric spaces. And so very recently that was proved that that this is the kappa value that's optimal for the complex numbers. What we gather from this is that if you have a Remez style inequality, you can turn it into an approximate factor theorem. So if we return to our soundness analysis now that we have a coherent definition of non-approximate equality between polynomials, and now that we have an approximate factor theorem, if we work through an inductive proof, we pull in some complex analysis, some measure theory, we end up getting that by induction the verifier accepts with probability at most this term here. Now, we can plug in the specific kappa value using whatever Remez theorem we'd like, and we can simplify, and we get something that contains two parts. The first part is the original soundness error, and the other other part is the soundness error that's added in because of approximation. We have the degree, the number of variables, and we have two approximation related parameters, which I haven't fully defined for you. Now, if we go to the approximate sum check protocol again, we look at it at a high level, there are some details that I haven't covered. You might have a couple questions. Like, for example, how does the prover compute these messages reasonably well? How does the verifier check this in a way that's sound and complete with approximate operations? And what happens if we try and run the round-by-round soundness analysis to determine what happens if the challenges are provided non-interactively, say, via the Fiat-Shamir transform? I'm not I don't have the time today to talk about this, but if you're convinced that we can resolve these issues, or you've read the paper, or you trust the reviewers, what we have is an approximate sum check protocol that can slot in wherever a sum check protocol appeared before. So, now, rather than paying twice across the barrier from numerical computations to proof systems, we have a proof system that is inherently numerical. Any computation that you can fit into a proof system, into a sum check-based proof system, you can fit into the approximate sum check protocol, and then you can implement that on real hardware with approximate operations, say, with floating-point operations. That being said, this is uh initial step in I think what could be a longer line of work. This result doesn't immediately admit something like, say, the GKR protocol. There's additional work there going from a univariate factor theorem to a multivariate short simple that's approximate. Additionally, we don't have an approximate polynomial commitment. You can attach the approximate sum check protocol to an exact commitment, but it would be certainly interesting if we can get a more efficient approximate uh commitment. Additionally, if you don't care about the sum check protocol in particular, or maybe you don't even care about proof systems, the high-level takeaway is that there are results in complex analysis, and measure theory, and approximation theory that are potentially useful in cryptography as demonstrated here. With that, I'll take any questions. >> [applause] >> Thank you, Zach. Any questions? So, some a few here. Okay. >> Thank you for the talk. So, my first question is So, the sum check protocol as is approximate, and I wonder Could you elaborate a little bit more if you plug it into a sum check based PIOP like Spartan? Then, what sort of PIOP we get? Do we need to like adjust the soundness uh the the security notion like the knowledge soundness? Like, do we can we still get some sense of the extractability so the witness? I don't know if you understand my question. >> Yes, yeah. I I understand your question. So, the anything that that touches the commitment assuming we don't have an approximate commitment, we can use all of the classical notions. Here, you have to think about well, what what is the statement being proven? And so, [clears throat] specifically in Spartan, I think this is a good example. Spartan relies on polynomial identity testing. And it turns out if you try and lift the approximate factor theorem to a multivariate approximate Schwartz-Zippel in the same way you might lift, say, the classical factor theorem to the actual Schwartz-Zippel theorem, you you run into some exponential blow-up in issues. And so, Spartan actually at by its construction, you run into some issues, but it's not because of the approximate sum check protocol getting rid of some notion of extraction or binding or things like that. It's It's actually a function of the polynomials and the properties of polynomials when they're approximate being different. But, it's a good question. >> I think at the front there. >> Thank you for the great talk. Um I'm curious about the additive error term. There was a two to the number of variable term and then some kind of square root. How do you set parameters? What do you think about this term? Do you think it's like a good term? Is it a necessary term? Do you have lower bounds for it? And even if you don't, like are there good settings of parameters that would make even stand alone this approximate sum check uh let's call it usable stand alone. Yeah. >> Yeah, [snorts] that's that's a a good question. So, the way I think about it is you certainly can pick the approximation parameters to drive this term down as low as you want. Of course, you're going to pay in efficiency because you're going to require higher precision to do this. The way I guess the way I think about this is there are settings of parameters that are compatible today that can provide you interactive reasonable interactive soundness. In the non-interactive setting, it gets a little bit more complicated. Additionally, you were asking about whether this is necessary, whether this is a weakness of the analysis. So, if you're to do the analysis via the the factor theorem because of some some properties of the Ramus inequality, specifically the fact that there are polynomials for which it's tight, we do immediately get an attack. In the same way that in the classical sum check, an attack would be picking a polynomial that does have it it's coincident with the true polynomial in exactly D locations, we can pick one that's awfully close. And so, this is this is tight up to constant terms. >> I think there was maybe one more question though. >> In the inequality, the inequality is based in this set that is a measurable subset of the interval. But, computers only work over rational numbers and the subs any subset of the rational numbers has measure zero. So at the end inequality doesn't it don't doesn't say anything real for computers. So I don't know how it's possible to use it in this context. >> So that's a it's a good question and going from the Remez inequality to this approximate factor theorem what we do is on the left side we're connecting something discrete. We have a discrete sampling set. We're sampling challenges from there and on the right side we have something continuous where it can and and when you work through this implication that's where this this notion of the discreteness and computers enters and I assure you it doesn't present any any issues. In fact the the fact that the J or the fact that E is is measurable means that it covers a certain number of these points that are randomly sampled and then you can reason about how this this interval interacts with the equi-spaced discrete points. >> Okay, thanks. >> Thank you. >> Thank you. Let's thank all the speakers of the session again.