Zero-Knowledge III (Eurocrypt 2026)

Okay. So, uh let's start a session. Welcome to uh the third zill knowledge session. We have three talks here. Let's start the first one. But uh unfortunately none of the authors come to come to the stage here. So instead the presentation is done by uh um their representatives. So the title is poly polyarismic proofs for multilinears over binary towers. So the Jako will present it. Thank you for the introduction. Uh yes Ben and Jim could not uh do it so you're stuck with me in in theirstead. Okay. So what is this object of this session and what do we want to construct? We want to construct snarks. And there's many reason I don't think you need me to elaborate too much on why these primitives are interesting, but I'm going to just do it anyways and give you like an example. And a narc is something that allowed you to verify a computation faster than it can be carried out. As an example, suppose that you have a claim that the quadrillion digit of of pi is at zero. In a snarak you can generate a proof of the fact in a quas linear amount of time in the number of steps in this case a quadrillion and you can verify the proof in poly logarithmic in the number of steps which is much much smaller time to compute than what it would take to compute it. Further the proof is also similarly succinct and these particular primitives have many application including letting blockchain verify state transitions very efficiently. It's an important uh part of the Ethereum road map and it's really a very fun and cool primitive in general. Okay, the natural question that follows is how do we go about building snarks? And the claim is that if you have an ideal functionality known as a polomial commitment scheme, then you can build any kind of narc. And in practice like modern constructions are almost entirely made and efficient depending on the polinomial commitment. So let me introduce what uh exactly a polinomial commitment look like. So it's an interactive protocol between a proven verifier and I'm going to give it like as an ideal commitment an ideal functionality description. So there's going to be a commit phase in which the prover chooses some multilar polomial that according to whatever reason it might do it sends it to the ideal functionality and the ideal functionality outputs a receipt confirming confirming that it has committed to the polomial. Later on the verifier can choose an evaluation point chosen over some field submit it to the functionality and the functionality will return the evaluation of the polomial committed to at that point. Okay. So once you have one of these you can build any kind of narrow that you might want in reality the situation in practice is more complex than that. Before I assumed that ideal functionality was defined over a single field but in reality for performance characteristics you actually want your computation to be arithmetized over a small field while it needs to be proven over a large field. So just to give you like some crash course this is not a a old realization this is something that came from practical implementation of snarks before 22 and22 circa like all snark use single cryptographically large 256 bit uh prime fields. Later on it was realized that this actually was inefficient and the trend from then from then on to actually go towards smaller and smaller fields with a lot of practical deployment using 32-bit fields. You know the natural question is can you go even smaller and in this work the motivation is to actually go for tiny fields which are fields which are much smaller than the trace length. Translength is the uh number of steps of the computation and the previous work by Ben and Jim were the first to write a narc for multilinear over this bin over binary field. So the smallest possible field you could deal with unfortunately you did not get such thinness which is not uh desirable in many application. for some bike shad notation I'm going to write L over K for the for L is a large field which is an extension of a small field K and you should think like for example F to the 2 128 as an extension over the binary field but most of this work works for other setting of small field and large fields okay the main technical challenge that this work solves is how to take any large field PCS and adapt it to one that works native ly over computation carried over a small field. So okay, what should this look like? So I'm going to have a tell you I have a large field PCS and I'm going to assume I have this ideal functionality I showed you before. The transformation will will take this and try to build a small field PCS out of it. So in the commitment phase the prover will specify a polomial whose coefficients are now defined over the small field uh the small field k and then the compiler will somehow adapt it to some polomial t prime over some large field. Now I once I have that I can commit to what I want with the with my deal functionality receive the receipt and once the verifier wants to query a point now over the large field very crucially like the the proven verifier will run some interactive protocol which will allow us to reduce the evaluation of the polomial to an evaluation of this uh t prime polomial and this will like the adaptation that we want and what we care about is doing this in an efficient way. So there are many question you can ask. So effectively how is the you know what are the parameters that you get of the committed underlying scheme and the works answer that the polomial over the the the small field and it adaptation over the large field will be the same size. So you actually don't get any any blow up by adapting from like a a small field to a large field. The proverhead is linear in the bit length of the input. The verifier overhead is logarithmic in the size of the input and there is a very small soundness penalty. So essentially this is a optimal essentially optimal adaptation from a small from a large field PCS to a small field PCS. Okay. How do we go about doing this? So there are some standard possible approaches stman which I'm going to show to you and then I'll tell you why they're terrible. So suppose I give you like a polomial defined so say these are the coefficient of a polomial defined over a small field and I want to commit to this with a with a large field scheme. What I can do is I can zero pad each of the coefficients of this polomial to get corresponding large field elements. Now this is a polomial which is honest to go defined over like a a large field and I can commit this with the with a um I can commit it with a large field scheme. Fortunately this is a bad is a bad idea because the size the bit size of the polomial over the large field that we have defined is now scaled by the the degree of the extension. And secondly, you also have a problem that you know you have no guarantee in your protocol that the prover actually committed to a polomial where actually each element is padded. So you have both a soundness and an embedding overhead problem. Okay. So in this work we show some different ways to do better and you know once you see this uh picture a very natural question you might very natural approach that you might have is to try to pack things more efficiently. So what does it mean? So I'm going to take again my polomial which is defined over this small field and now instead of padding each element and then interpreting each padded element as a large field element what I'm going to do is I'm going to chunk it. So I'm going to take you know extension degree many chunks of this polomial and then pack them together a single large field element. So now if you paid attention the bit size of these two representation are exactly the same. So while before we were ballooning by like a degree a degree um sized ballooning now I'm actually keeping the same bit size exactly and yeah so the plan of attack for a transformation will be that the prover adapts their small field polinomial to this packact large field polomial and commits to it using the underlying polinomial commitment scheme. Okay, the problem that we have is that now we have this pack polinomial where like the structure is different like with the with the padded polomial we you know we know exactly that an evaluation of the padded polinomial and an evaluation of the original unpadded polomial would give you the same result. Now when you pack you're kind of changing the structure of the polomial that you're dealing with and so you might have problem. So what we need to do is to be able to reduce evaluation claims on the unpacked polomial to evaluation claims on the packed polomial. So we're going to just do some definitions. So I'm going to have this beta v be a basis of the of l over k. Um yes I'm going to take a an evolation point and I'm going to split it in two parts R minus and R plus. So roughly since we're going to be we pack by um taking one element taking uh degree extension elements and packing them into a single mode field elements. What will happen is that the valuation point will be split in a part corresponding to the um corresponding to the uh base field and one part which is conf which remaining on the other variables and our starting point will be something that might be a bit confusing if you haven't seen it before but there's a standard vector matrix vector property of multi evaluation that is if I get any pol any multilinear polinomial t defined over some field. I can take its coefficients, write it in this particular matrix. I can like and I can write the valuation as uh a a matrix a vector matrix vector product where I have like uh the on the left hand side for you is the it is the left hand side for you. The left hand side is the part corresponding to the this R minus part of the valation point. Then you have the part on the right on the right and you have the coefficients in the middle. So looks ugly. The algebra works out. This is exactly what evaluating a polomial at a multi- polinomial at a point looks like. Our plan of attack will be that the prover will compute the right endpoint or the the right part of this. So the um the matrix vector part of this vector matrix vector product and it will send it to the verifier. Then once it has this part has been sent to the verifier the verifier can itself compute the remaining part of the of the product in time which is o to to do the k where k is the extension degree. Okay. So this is going to be the plane of attack and so yes so the prover has sent this uh this vector here the the matrix vector the result but of course the prover we're not in the business of trusting provers. So the prover might have lied. So now you have to verify that the that the um prover has effectively sent you what it claims to be. So with this the prover should have sent this vector SV which is claimed to to be equal to the polomial evaluated on the R plus part of the valuation point. So what is it suffices to check is that this SV satisfies this u this equation. So this is the equation there. So for every V in the for every for every V you want to check that this star equation holds. Now it might be very tempting now to do something which is uh bit is there's something very natural which is to take this equation which is defined over two to the kum constraints and then combine them using the basis. So it is true that if I take the sum of these claims over all these with the scale by the basis I exactly get an evaluation of the packed polomial at the R plus point. This is tempting. Are we done? Like can we can I just then ask the polinomial commitment scheme to give me the valuation at R R prime? Unfortunately, no. Otherwise, this work would be much easier. Um and the the annoying part is that if you look at this equation over a star, both sides are divine over the large field L, not over the base field K. So while BV is linearly independent over K, it is not linearly independent over L. So basically this is not sound. The prover can choose like can choose like SV in a way in which the this equation over here cancels out and you actually can make the verifier believe whatever you want. So we need to be more a little bit more careful. Okay, let's do this. So the so our problem before was that we have these many claims that were defined over the large field and we wanted to uh and we had a problem that like the BVs were independent only over the small field. So what we're going to do we're going to take this claim and we're going to decompose them as much as we can so that they are actually defined over the small field where we know that we can de compose using the basis we can recompose using the basis. So you have these many claims and now each of each of SV is going is defined over the is defined over the the large field. So what I can think of it I can think of it like as a vector of base field elements. So I can also look at the right hand side this TVR I can do the decomposition of a multilinear polinomial into its components and since TV is actually defined over the base field the only thing which is defined over the extension field is this EQ polomial so I'm going to de compose that as well right so I'm going to do the same things and now I have this equation and my strategy is that I'm actually just going to look at rows so I'm going to define one claim for each of the rows. So I'm going to look at the first row over there of SV times the is equal to this EQ that time that okay sorry just to go there. So before I had like one claim I just combining by the basis but now I'm going to have these claims for each row and I'm going to combine each row. Now each of these rows will be defined over the base field. So actually the trick that I was doing before for the basic combination will in fact work. Okay. So this leads to this following protocol. So I going to have the prover send you this SV matrix which is going to be the claims as before. But now I'm going to think as being like a de composed matrix where I've taken these elements over L and I've actually decomposed as element over the small field K. So the prover claims now that each of the columns satisfies the original claim. So the the verifier uses it to check the columns to check the the consistency with the matrix vector product that we saw before. Good. Then the verifier needs to still check the rows and the rows induce the constraint that we saw in the previous slide. So this will give us these kind of constraints. And now if you've been in this field for more than five minutes, this is a sum check. So the final strategy is to run a sum check on these claims. Well, will this eventually end up the sum check will batch all these different claims over to a single evaluation of t prime at a at a point in the extension field and this will be exactly what we use our large field commitment to evaluate. Okay, so this is the old protocol the Yeah, so this gives you this strategy gives you an essentially optimal adaptation from like a small field PC uh to a from a large field PCS to a small field PCS where the proverhead is basically just doing the sum check. The verifier overhead is like effectively computing this major vector product but you should think about the parameters being set so that everything is logarithmic and everything is fine. Okay, good. So the paper also has further contributions in that they also analyze like the baseful polinomial commitment schemes for read solomon and foldable uh codes and to make it work over concurren characteristic tool. This involves a few adaptation like uh using the additive entity and uh yeah and other than that there's also like uh you know theoretical works and nice and all but you also are interested in figuring out whether the techniques in a work end up having concrete performance. So the the is that if you work for like um if you work um on binary fields and you have like lesser embedding overhead, you're able to get much more efficient protocols. And this is comparing this work with the the plonky free library which is a very optimized uh library for working on um on proof systems. And you can see that like the the fact that for the same for the same input size you actually get like much smaller like everything across the board. So the commit is smaller, the proof uh the proof time is smaller, the verification time is basically the same. Good. This was my time. Thank you for your attention. [applause] He's happy to have questions. Any any questions? Maybe I have missed uh from your talk but is there what is the assumption behind it? So all of this is a pure random oracle model. So here we're trying to do like an IOP with this good characteristic and you can instantiate it with we can instantiate this recipe with any polinomial commitment that you want but for this particular work for the baseful instantiation we are just making things secure in the pure random oracle model. Uh thank you for your talk. Just quick question. Uh this only works for extension fields. So not for large prime fields. >> Yes, exactly. You need an extension structure in order to like decompose claims claims. as well. If you're working over the same field uh or you want to do like some sort of like module switching then you can also do this kind of things but there are different techniques from this work. >> Thank you. >> Perfect. >> Okay. So let's thank the the speaker here. Thanks. >> Thank you. Okay, the next talk is um care out of and proofs and applications to privacy preserving cryptocurrencies. Speaker is you. Okay, go ahead. Okay, thanks for the introduction. I'm Uchan. It's my great honor to be here to present our paper entitled key after proofs and application to privacy preserving criminal currency. This is a joint work with my student Mjang and Shan Fu. So let's begin with the background. Here is the underlying of this talk. So transaction privacy in payment system breaks into confidentiality and anonymity. Confidentiality means that outside observer cannot lend the transfer amount while the anonymity means that outside the observer cannot lend the identities of the sender and receiver. So in decentralized payment system transaction are kept on the blockchain to ensure public verifiability. Bitcoin and ethering simply expose all transformation in public at the cost of sacrificing privacy. The UTX model and the accountbased model are two mainstream model in cryptoc currency compared to the UTX model. The accountbased model offers superior functionality but attaining privacy is more challenging due to state posistence. So in this work we forced we focus on accountbased cryptoc currencies. So the initial work like PGC and the simply focused on the confidentiality and the later work diamond just to focus on how to add anonymity. Diamond develop many of the main proof to build anonymous za with an anonymity on top of zer. So let's have a close look at the anonymous zer because it represent the sort of pbc with sketch it as below. So each account is associated with an algama key pair and encrypted balance with public key serve as its account address. To generate a transaction the sender first select an inside an set then decide a vector of transfer amount and encrypt each transfer amount under the public key with reduced randomness. Finally generate a proof to test the legality of the transaction. However anomalies suffer from three shortcoming. First is a security model is weak because the counter model fails to capture the inside attack notably the roy attack. So the vulnerability stems from the random reusing which is also very crucial for the anonymous zus design. So although we have mitig mitigation approach it require participant to proof proof knowledge of their circuits during registration which is not satisfying for the following reasons. So the first techn technical challenging is how to defend against a wide range of inside attack including the ro key attack. The second one is limited anonymity in anonymous many proof requires the sender index and receiver index size in obvious of opposite parity. Such constraint halves the anime guarantee. So although this deficit can be remedied by picking larger enemy set but comes with the cost of increased communication cost and transaction size. So the second techn technical challenge is how to achieve bad anonymity guarantee without sacrificing efficiency. Well the third shortcoming is inefficient multi- receiver transfer ano only support single receiver transaction. That [clears throat] means if a sender want to pay t receivers, he must syncially executing the basic protocols t times. This incurs prohibitive overhead for largeity and reveal the transaction patterns. So because the sender must lie in the intersection. So the third technical challenging is how to enable efficient built-in multi-receiver transaction. So motivated by the state of the affairs, this work aimed to develop a well-rounded PBIBC that featuring strong security, rich functionality and high efficiency. We present the first account-based cryptocurrency simultaneously achieving strong privacy and the efficient multi-receiver support. So let me first let let us first introduce the framework of PBBC. So formalizing security model for PBSA turns out to be very tricky because the security model must be strong enough to capture all real world attack while remaining clean and handy to use for security reduction. We introduce a bunch of oracles to capture re to capture the adversar's abilities. Notably the we introduced the rich register the crafted account oracle to capture inside attack. We establishes the security of PBBC upon three oragonal pillars. The authenticity ensures safety resistance. The soundness ensures policy compliance while the ledger indistinguishability ensures privacy. Uh due to time limit I will skip the formal game definition here. Please refer to our paper for the details. So our framework only require two building clock building blocks. The first is actively homorphic public encryption while the second one is a labeled NISK. Let's see how it works. We just focus on the most important part. Consider the sender want to conduct a multi-receiver transfer. He first randomly pick inside an emity set and then forms a bonding transfer amount vector and encrypted each transfer amount vector each transfer amount on the corresponding public key using independent randomies. Well, here we use independent randomies to break the correlation among session keys of multi-receiver encryption. This help us to completely solve the technical challenge. one about the inside attacks. Secondly, we admit the multi-receiver transaction solves the technical champion two about the built-in multi-receiver support in syntax sense. Well, let's have a closer look at the legative statement which can be for decomposed into the following sub policies. Particularly the a positive enforces strictly positive transfer to intended receivers. This setting not only align with practice more importantly combine with the binding property of the public key encryption the sender index the receive index and uh the decoy set must be disjoint. This makes the proof of disjoint redundant which was exactly the most complex and restrictive part in anonymous ether. This help us to solve the techno chion too about the limited anonymity. Well, we prove that if the underlying public encryption is indep simulation sound extractable and adaptive zero knowledge, then the ppbc framework we proposed to satisfy authenticity, soundness and ledger indistinguishability. Well, let's move to the most technical part of this talk. How to give an efficient instantiation of our generic generic framework. As as to the choice of the encry encryption component, we choose twist gama. Why? Because it is zp friendly. Look, the right half of the cyex is exactly a person commitment. Even nice subtext on the different public keys still share the same commitment key. This enable twister gama seamlessly s with all the kps that accept the p commitment as instance notably the bulletproof and uh a lot of sigma protocols for linear relations. Well, by plugging the twister gama into our framework, we obtain concrete legal statements. The once highlight in red requires a so-called K proof. That means just to prove partial knowledge. More precisely, proof knowledge of openings of some key subset among impublic commitments without revealing which key subset. Well, as to the choice of key after vamp proofs, general purpose zikps or general key after vamp proofs a bit heavy. The deer based key after vamp proofs turns out to be the best choice due to its high efficiency. This line of research start with the back start with the breakthrough of the GK protocol achieving logarithmic precise for k equals one and the followup work try to extend to general key. However, all these workers share a common limitation. That is they support only homogeneous statement. That means all the substatement are committed under the same discrete logarithm commitment key. Well, now let's build the proof piece by piece. We begin with pi 0 which stipulates exactly n minus t minus one transfer amount equals zero. So this can be proved via the existing deal based homogeneous care proof. Well let's come to the pi positive which stipulates exactly t after transfer amount are positive. This should be proved by the deer based homogeneous range proof. However no such proof exist in the literature. It will require a brand new design. So the design turns out to be difficult. Why? Because on one hand so that the homogeneous K after V proof take uncommitment as input and just prove knowledge of key hidden commitment while on the other hand the range proof like bully proof take key commitment as input and prove constraint of all key commitment. So the technical changing is how to fit the hidden commitment to the ranch proof without revealing their indices. Well, our start pointer is the GK1 bending proof. Why? Because we find it is ranch friendly. That means it pick mechanism allows the verifier to obtain a randomized version of the real touched commitment. However, it only supports the case K equals one. So a nice method for extending to arbitrary key is just invoking the very basic GK one of many proofs key times. The problem is that both communication and comm computation complexity a linear in K and even worse a malicious prover could cheat with duplicated index during the key invocations. So to solve the inefficiency in SE our idea is to aggregate correction terms via random linear combination. This helps to reduce the computation cost make it independent of G and halfves the communication cost to solve the security issues that means guarantee no duplicated index are used. Our idea is to introduce indication bit vector to represent the secret index set. and let the prover first commit the indication bit vector to P and let in the protocol. The verifier use the same polinomial mechanism to homorphically reconstruct an other commitment called P prime of the selection the indication bit vector SI and check its consistency with P and P indeed commits to K1s. Well, thanks to the B design, we successfully generalized the classical GK1 proof to arbitrary key C and it still preserves the ranch proof friendliness because the verifier can now obtain a randomized version of key aggregated commitment. It remains to show how to build PI balance and PI servant. Well, because we use independent randomies for different public keys in encryption. So these two proofs require the DL based heterogeneous C7 proof. That means proof statements over unpublic commitments generated on the distinct commitment keys. Well, most debased homogeneous C proof crucially depend on the homorphism across sub statement. When commitment keys are different, such homorphism does not hold anymore. So extending deer based homogeneous cap proof to the heterogeneous setting is non-trivial. Again, it require new design. So our start point is the SF protocol because it does not rely on cross commitment homorphism. Well, the major downside of the SF protocol is its verifier and the pro complexity are both quadratic. So why SF is quadratic? Our main insight is that the SF protocol use polinomial to encode the secret index set which is overkill. It make it results in a very dense basy matrix and thus the aggregation cost is quadratic. So our idea is to drop the heavy polinomial mechanism and use lightweight indication beta vector instead. So this change is so simple yet powerful because the best matrix immediately become diagonal and highly sparse. So this help us to reduce the aggregation cost from quadratic to optimal linear. Note that our new protocol does not require cross instance homorphism. It can naturally extend to heterogeneous setting just by modifying the basis. So in some we reduce the pro and verify cost from quadratic complexity to optimal linear complex complexity at meanwhile we enrich the statement expressiveness from homogeneous to heterogeneous. So this table highlight our contribution to zonog proof. So we propose the first deer based homogeneous cap proof with ranch proof fine and the first deal based heterogeneous cap proof with linear proof and a verifier cost. Putting all the together we obtain anonymous PGC and efficient instant instantiation of our PBC Pabc framework. >> [clears throat] >> Okay. Uh we implement and evaluate our proposed CF V proof and uh the transaction layer of anonymous PGC in C++. So the experimental result confirm our theory. Our homogeneous CF proof integrates range proof seamlessly. The cost rate are even below one. Our heterogeneous cap proof greatly improves the SF protocol in both functionality and efficiency. While compared to the anonymous laser, in addition to asymptoic improvement and security enhancement, our anonymous PGC also exhibits superior concrete performance and significantly better scalability in the multi-receiver setting. Okay, here's a brief summary of this talk. First, we enrich the ZKP toolbox for partial knowledge. We extend the GK Wing proof to generate K for the first time and make it range proof friendly. And we also constructed the first deer based heterogeneous C proof based on the SF proof with the optimal prover and verified cost. As the application, we present a generic framework of privacy preserving accountab currency from actively homorphic encryption and NISK achieving strong security and built-in multi-receiver support resolves the open problem in diamond at all about inside attacks and multi-receiver transfer. uh we also present a efficient instant called the out anonymous PGC which outperforms the sort of anomalizer in both security and efficiency. Okay, that's all that's concluded my talk. Thanks for your attention. I'm happy to take any question. Thanks. [applause] >> Question from the front line. Um, so why not just unconditionally send to all of the n receivers so that you don't need the uh pi zero and pi positive proofs? >> Mhm. because you're you're only um the sender uh would only be um compromising its own privacy by sending to more than the intended number of recipients. >> Sorry, >> the sender would only be compromising its own privacy by sending to um more than the intended number of recipients. So more than K. Um that doesn't seem to be necessary for um balance preservation for example. >> Mhm. So so so what's the question? >> Sorry. Why not send to n recipients unconditionally? >> Why is the sentence the recipient? >> So, so you're doing a lot of work to make sure that the send has only sent to exactly K [clears throat] >> of the recipients why send to all N unconditionally. >> Oh, okay. Uh the the number of real the number of real intended is public in the transaction information. It's kind of public. So, so >> just we don't know which K receivers but the the number of real intent the number of real receiver is public in the transaction that's the requirement for the CFM proof. So what I'm saying is is there an efficiency reason for that or um I I don't know what why do you need to um kind of only send to K recipients >> uh because uh is uh all the KF proof require it as a statement otherwise the proof does not work. No, no, no. I'm saying why do you need the proof? Um, rather than just sending to all n I mean is is it because the the transaction size would be n over k times larger? Is it because that doesn't seem to be the case because you need you need um that n times overhead anyway. >> Uh sorry I don't quite catch you. We can talk offline. Okay. Yeah, probably other questions. I have actually one usually partial knowledge. Yeah. >> Partial proof of knowledge means that uh you have K in case of K out of N. >> Mhm. >> It usually means that you have you know at least at least K witnesses out of N. But in your case exact exactly >> exactly K. >> Yeah. Yeah. Yeah. Yeah. >> I watch it. Okay, that's that's interesting. Okay, so all the product questions will be given directly to the to the speaker. Thanks. Thanks again to the to the speaker. >> Thanks. [applause] >> Okay, the let's move on. The third talk is the robust non-interactive zero knowledge combiners. Um the speaker is Lorenza. Okay, thanks for the introduction and thanks to all of you for being here. Particular thanks goes also to my coders Mikuel Champi Daniel and Yusha who should be somewhere here in the audience also. And without further ado, let's see what these robust combiners for NEZ actually are. We will just have a very brief introduction to robust combiners in general and then we will have a quick stroll through the main results of our work which as you can see really embed the the full package. Right? We have definitions and possibility results all the way to constructions and then we will just conclude with a few closing remarks and related open research questions. So today our favorite subject Ellis will be tasked with uh having to instantiate some mission critical piece of software that fundamentally relies some synchroraphic primitive P and in her design process she actually has to instantiate this primitive at the end of the day. She's faced with the existential dilemma. Do I pick implementation B1 or implementation P2 where mind you these are implementations of exactly the same primitive whose security may be rooted in completely different premises. Right? You can have pre-quantum versus postquantum, different setup assumptions, different instantiations of the same setup or even different implementation specific characteristics. What's important that is that to the eyes of Alice really uh this um distinction points that she has identified are such that each of these instantiations has its own pros and cons. Be it efficiency uh better reliability with respect to potential future attacks and the list goes on. Of course, by taking into consideration more uh tension points, well, Ellis could very well end up in a situation but which is really unable to uh pick uh with reasonable certainty which among uh all these candidate instantiations will actually lead her to achieve security on the long run uh and will actually be able to uh again safeguard the security that uh her users are actually expecting to receive from her piece of software. So how can we help Ellis sleep tighter at night? Well, we can remove this decision point alto together. So instead of having to pick, Ellis can now just pick all the candidate instancations she wants. This may very well have uncomparable uh features, let's say, that uh Alice would like to tap into with respect to each individual candidate and bunch them together into into a single instantiation that will indeed securely instantiate the primitive as long as only a subset of the candidates is secure. Yeah. Yeah. So that even if the Qday arrives, if some postquantum assumption is broken or if say some standardized primitive gets backed just hypothetical, then uh you know hair users will still be able to uh sleep tight at night. These are combiners in general. Robust combiners are a particularly interesting class of combiners uh that from a formal standpoint restrict the combiner from introducing any new uh cryptographic assumptions other than the fact that t of the input candidates were indeed secure candidates and this allows for ruling out uh let's say a non-combiner which could very well discard all the input candidates implementing the primitive from scratch. This was first formalized back in 2005. And uh the way this was introduced consisted of asking that whenever we have an adversary that attacks the security of the combiner, it truly must be the case that we are violating our belief that at least t of the candidates were indeed secure candidates. Yeah. In particular, it must be the case that uh we are able to come up with some n minus c plus1 amount of reductions meaning that we can for sure break all the candidates we deem to be broken plus at least one of the candidates which was instead secure. And just to clarify this end C++ one let's see a very quick example uh you may be familiar with uh this construction. So like if you concatenate multiple hash functions, you indeed get a collision resistant hash function as long as at least one of these input candidates is uh collision resistant. Um what um why is this a robust combiner? Well, the point is that whenever we can find a collision for the combiner, it really must be the case that we have found this n minus c plus uh plus one reductions we were looking for. And as you can see on the right hand side, we have our N minus C reductions that are not surprising, but for sure we can violate our belief that at least one of the schemes were secure. Okay, so that's the idea. Let's see how we can cast it in the context of NISK. We would like to keep the same semantics, right? So we have T candidates that are secure out of N. We would still like to get a NISK, but now Nisk is a multi-propy primitive. At the bare minimum, we require soundness and zero knowledge to all at once. And so, uh, we need really to clarify what T actually means and what we're actually breaking. What security property are we breaking for the combiner and what does this imply for the security of the underlying candidates. And to do that, uh, we can see an example with n= t3 and t equal 2. A combiner will securely instantiate uh, both properties at once. So soundness and zero knowledge and as long as at least t of the input candidates are secure with respect to each individual of the properties. And this may be a bit surprising you may wonder I mean what's the point in considering such a definition as opposed to asking that two of the candidates should be simultaneously sound and zero knowledge at once. And the advantage as you can see is that this configuration that is displayed here allows for t equal 2 meaning that we can salvage partial security of the candidates. So that even if some crypto assumption uh leads uh gets broken and leads say to the breach of zero knowledge of scheme 2. Well we could the combiner could very well reduce the soundness of the uh of this partially broken primitive so that it can still meaningfully contribute towards the security of the combiner. Second question, what are we breaking? Well, a valid adversary for the combinary is such that uh any of its underlying security properties gets broken. Uh and this should imply the existence of n minus c plus1 reductions to the security of the underlying candidates. But mind you, it's not sufficient to just ask in this case for reductions to soundness given that indeed the candidates are also zero knowledge candidates and we really do not want to leave security on the table. So it is acceptable to either break soundness or zero knowledge of the underlying candidates in order to in the context of defining a valid adversary for the combiner itself. So what we are saying here is that indeed improving the security of each individual property of the combiner. Well, we could very well use all the security that we have from the combiner and this really embodies uh the spirit of robustness that we would like to to capture with a multi-property primitive. Finally uh our definition is parameterized by the runtime of the versaries so that we can capture computational as well statistical properties alike. Okay. And that's more or less what we get at the end of it from at least from a pictorial standpoint. The first result that we show is that indeed it is impossible to achieve any such combiner unless we have at least that is at least greater than the major than the half of the candidates. And the way we do that consists of exhibiting a counter example. Yeah, very roughly this counter example is in a setting that looks like this. So we have two candidates with t equal one. And u this just to give you a bit of an hint uh the candidate primitives that we are providing as input to the combiner look like this. So one simply outputs the witness, the other simply outputs zero. So that we have one candidate that is unconditionally sound while the other is unconditionally is your knowledge. As you can very well imagine, these candidates are not really providing much security on their own. So we should not expect the combiner from in to get NSI without relying on any external assumptions intuitively, right? And crucially, yeah, this combine I mean such a combiner relies on the fact that we can salvage partial security. Um, of course, if you are unhappy with that, well, we still have some more crafty under examples that allow one to rule out even more restrictive definition of combiners, uh, such say as a one that would ask one candidate to be simultaneously sound and zero knowledge at once. Okay. And these are obtained from let's say adopting the spirit of these two these two candidates. So this specific counter example in a more crafty way. Now I just want to uh show you one of our three constructions just to see also how this definition is operable in practice. Uh and we will do that with evaluating NX in a recursive fashion. That's the only building block we will need. So we are essentially in the realm of knowledge sness. The prover will first evaluate a proof uh a proof of knowledge uh pi one using the original statement a witness and then it will go for another layer of nix. So that at the end of the day the verify instead of verifying pi one uh it will be verifying a pi12 which is a knowledge sound proof for which uh uh yeah that proves knowledge of the fact that the provers was an accepting proof for the previous layer. Yeah. uh and if both skins are knowledge sound well this is indeed still a knowledge sound proof for the original statement and witness intuitively while uh also of course preserving zero knowledge and as well as hiding by one uh from [clears throat] uh to the actual verifier. Yeah. And um what we're going to see that this core idea can be uh used in a rather intuitive way to achieve some fall tolerance the some degree of full tolerance that we would be expecting from a combiner. Yeah. So this fact that we can crucially hide by one. So let's see an example with n= 3 and t equal 2. Uh we first take all the possible combinations of sides t out of the n candidates. In this case combinations of sides two out of three. the prover will just run the recursive proof strategy that we mentioned before so that it will be computing this final layer proofs and now the verifier will accept only the proofs are accepting. So as you can see we're really not introducing any external crypto assumptions. We're not doing anything crazy. We are exclusively relying on u the security of the underlying candidates in order to prove that our final scheme is indeed uh an why is this a robust combiner? Well, let's see it for zero knowledge for instance. Uh we must be able to define an adversary that somehow manages to leak information from any of these final proofs so that it may break zero knowledge. And um let's try to do that. If this adversary does not really violate zero knowledge of any of the underlying candidates, well then there's no hope to do that. All these final layer proofs are simulated and indeed the verifier really cannot do much just by looking at these final proofs. If we have one reduction, so if the adversary manages to violate zero knowledge for one of the candidates, well now it can start doing something so that say it may retrieve the pi tree from by looking just at pi tree one. But as you can see in each of these combinations, we have at least one zero knowledge scheme so that uh intuitively we are able to hide the original witness and we're able to break the chain. Let's say that this verifier is attempting to build to get all the way back to the original witness. Okay. And indeed we can define a simulator with such a configuration of schemes as long as these equal to one essent. I mean as long as we have at least one at most one broken scheme. Of course if as soon as we introduce a second reduction. So as soon as this verifier breaks zero knowledge of one another of the schemes then indeed we violate zero knowledge. But as you can see now we have our desired number of reductions. And if we really instantiate our scheme with at least one scheme with at most one scheme that is broken well then we really have the security we were expecting. This scheme can be generalized actually to arbitrary N&T uh and we show that uh our construction has tight threshold with respect to the lower bound we have identified works for all of MP but as you can very well imagine it's not really that efficient of a scheme. Yeah at the end of the day we need to evaluate tentious proofs. So if you start combining many candidates then things are just going to blow up very very quickly. And on the paper you can also find two other constructions that trade off uh either uh the class of supported languages or the threshold in order to improve on this ladder metric so that we can indeed combine uh even a polomial number of uh schemes in the security parameter. Yeah. So we get better performance. But again, still these combiners at the end of the day are still relatively theoretical. If you want to learn more, there is a pointer here to the full version of our paper. U you can find really a lot of formal details and that's arguably the main contribution of our work. So getting to actually properly formalize what the robustness means, how we can prove that say a zero a combiner is zero knowledge combiner. So how can we get the reductions and so forth? So if you're into that type of stuff, I would definitely invite you to to read the paper. Uh and um yeah, we also have a few open problems uh that we're leaving along the way stemming from definitions u by considering say different alternative models, alternative security properties as well as of course more definitions of combiners. uh given that again these are tools that are gaining even a bit of traction um also with respect to other primitives such as king capsulation modules for for the postquantum transition of TLS for instance so getting um designing new constructions that can actually be deployed in practice can actually make a difference for let's say certain mission critical settings in which we really value security over efficiency and over which uh we really want to ensure that the user can have some reliability ility in terms of uh ensuring that there is the defined schema there knowledge that's all and thanks a lot [applause] question from from >> really interesting and actually have probably many questions. Um the first is um if I look at your T out of N construction at the end um you know you like the one before the slide. Yeah this one basically. So whenever you take T out of N then you have to like reorder them I guess the I mean you have to pick an ordering for each of them >> for for the schemes in how you nest proofs you mean? >> Yeah. Basically because like when you pick P3 and P1 you could have done the other way around but I guess it doesn't matter that much. >> Yeah. But the efficiency that you get in the end is like sort of n to the t proofs in in in order. >> Yeah. And ch proofs. Yes. >> Yeah. So what's the most efficient thing you got? Because you mentioned also other constructions. So I wonder >> um I mean very roughly these other two constru I mean the output of this final construction is just a concatenation of proofs. So yeah this case linearly with the with the security parameter. Um the final construction is similar as in we still have n I mean a linear number of proofs uh actually n proofs we have right n proofs plus some additional material coming from for instance from the mpc >> wait you had t choose n sorry n choose t before right I think >> yes for this for the scheme that we showed here yes >> yes >> for the others no >> so what's the the order basically between n and t I'm not sure to understand >> the sorry >> the order like How many proofs do you get at the end? Basically, because before it was n choose t roughly. >> Yeah, with these other two schemes. N times uh yeah n basically. Yeah, we get proofs. >> Okay. >> With these other two schemes. >> Um and then second question, can you do something with folding? Because you know you're recursing. So I'm not sure if this can do something like this. Um I mean I'm not really sure because really at the end of the day in order to keep this invariant right it's not like we can compute less proofs than that. Uh yeah well for instance yeah for zero knowledge you need in order for zero knowledge to hold you need to ensure that each of these cominations has at least one knowledge sound scheme. So you cannot I don't think you can really compress that further in any reasonable way and a similar argument also holds for knowledge soundness. So thanks. Welcome. [snorts] >> Okay. Wait foration, right? >> Uh it depends. Uh this construction is non blackbox because we need to nest proofs. So yeah, we need to >> Yeah. But this second construction is blackbox. The third construction is not blackbox. >> Right. Okay. Um so if we kind of look into the structure of um the proof system so for example suppose there an IOP that we um we know is um information theoretically secure so we're less worried about that being broken uh and a PCS then um we can consider combining the the PCS's. Um but what can you say in in general about um how much more efficient you can get for white box combination? So that would that allow you to break the um the t um uh the the um impossibility result you have on the threshold. >> Um so could you repeat the question? I mean a bit. So if we if we know more about the proof systems, we know the the structure. >> Yeah. >> Um >> does the impossibility result the threshold still apply? >> Yeah, I mean this is fundamental impossible. Yeah, I don't think uh you can get around it in any way because yeah, you can always find a counter example like the one you we we showed on the slide. But yeah, maybe I didn't get your point. I mean, what's your proposal, let's say, to make it work? >> Well, I I'm not sure. Um it it seemed to me that the impossibility result um okay I I can't think of a way to a way around it. So yeah maybe it's yeah still >> yeah we can talk more okay more from the back and then moti next. >> Hi uh thanks for the talk actually my question is very similar like about this impossibility result. And you show this counter example where one of the scheme is not zero knowledge, the other is not sound. >> Yeah. >> What if you want to get this robust construction only from schemes that are perfect zero knowledge? So you only care about uh the possibility that soundness have been broken. >> Okay. So you you Okay, let's see. So you're asking basically whether uh I mean you assume you're already preassuming that the final scheme is zero knowledge no matter what and you still want to and you only want to consider soundness. I mean you want a combiner for soundness let's say you can do a combiner for soundness uh if these uh lesser yeah I mean with you can go around this impossibility pretty much but yeah and um yeah it's the construction is similar to the one for hash functions pretty much. Yeah. So I mean you need to you have multiple schemes one of which are sound and yeah you can but again arguably this goes a bit um beyond let's say the spirit of the commerce you want to consider because at the end of the day yeah you would like to I mean even if a scheme is perfectly zero knowledge could be broken for whatever reason right you can have a I don't know a broken instantiation uh whatever I mean >> okay the last question from moti It's a com It's a comment. I know the field is getting older older than usual. It's already 50 years. So concepts uh don't pass the century barrier. But uh the I see the paper as a very good application of what we called in 1990 meta proof. a proof that I have a proof >> it's a crypto paper and then just to refresh the the minds of the people in in 2012 we put a very old version of of the work on e-rint I think so it's good also to use the old terms because the theory of 1990 is now in blockchains and everywhere and it's good that the field will keep the legacy >> so I'm it's a it's a comment in general not just for this but this this proof that I have a proof in Nisuk >> is called metaproof >> metap proof okay >> and other people already reinvented it and they called it other names but this is the original name >> thanks for that [laughter] >> okay so let's wrap up thanks speaker again and all the people joined to the session