Ethproofs Call #8: Poseidon

Transcript

Justin Drake — welcome

Okay, let's get started. Hello and welcome everyone to EF proof call number eight. Uh we have roughly 100 people uh on the call. People are still uh connecting. Uh today's topic is poseon and uh this call is a little bit of a unscheduled call uh that was prompted by a research paper uh that was uh published about a month ago and uh we actually had advanced notice about uh this paper uh back in November I believe uh because the authors uh claimed a bounty on the on the pose uh initiative.

uh the DEFM foundation organizes uh and they they they shared an early write up of of their ideas. Um and you know behind the scenes we have been basically preparing uh for today and trying to come up with a a reasonable strategy uh to to to move forward. So let me briefly uh share some slides and then we'll get uh cracking with the with the presentations. So if you're uh new to these calls, uh we do have a telegram group where these calls are announced and you can register

interest and uh get on the calendar invite. So yeah, I encourage you to to join the telegram group by scanning the QR code or entering eofroofs community. Um so this is the uh agenda of the e- proofs calls uh so far. Um and because hash functions are you know such an important uh topic uh we we're considering having a second call on hash functions call 8b uh that would be focused on alternatives to prooseidon.

So there's you know interesting hash functions such as blake uh that are being used uh today for example by air bender. Uh there's also Shati 56 um that the Bitcoiners would probably want to use. Uh and there's also newer hash functions like monolith that have extremely good performance and are very very promising uh but uh need more more eyes on them and um you know the the theme of 2026 is security and we have we'll have a whole uh series of talks uh on security topics for example formal verification you know livveness and and and fiat.

So this is the the paper that I was uh hinting at uh which uh basically has uh shown that the attack surface on poseon 2 is materially different to the attack surface on poseon one. Um the way that poseon 2 was framed is that um it could potentially inherit the cryptonalysis of pedon one. uh it's an extremely similar construction. It's by the same authors. Uh it has an extremely similar name. Um but really the uh this this new paper shows that these hash functions are are materially different. And so in

some sense the lindiness the amount of uh time resets. Uh so previously we wanted the assumption that padon 2 had in some sense seven years on liness but now it just resets to to three years because the paper is is is 3 years old. Now from a performance standpoint um pedon 2 is extremely fast. Um it is you know quite a bit uh faster than than pedon one. And prior to uh this month, we we were under the impression that pedon 2 was, you know, maybe five times more efficient than than pedon one or

potentially even more than than than five times more efficient. But what we've done in the last few weeks is optimize pad on one with, you know, novel optimizations that hadn't been uh implemented. And now we're at a point where actually poseon one is um of similar performance to to peron two specifically less than than two times slower. And this uh performance here is specifically uh referring to the plain text performance not incircuit uh performance. And when you look at an application like lean VM um which is this minimal ZKVM for aggregating postquantum signatures the end to end

slowdown uh is actually only 30%. Uh when moving from pose on two toon one and you part of the reason is that doing all of these hashes is a subset of the the overall uh workload. So there's some bad news, there's some good news. And basically what we're suggesting uh for uh for lean consensus is to just do a switch from pad on two to pad on one. Um peron 2 um is you know still not broken in the sense that with the current parameterization uh the best known attacks still don't breach 128 bits of of security.

But um you know Ethereum is extremely conservative on on security and we would want a hash function that has sufficient lindiness uh when when it does launch um on on Ethereum and you know we're planning to deploy this cryptography around [snorts] 2029 peron one is from 2019. So this would be a hash function that will have enjoyed uh 10 years of of of attention. Um, and this is just a historical anecdote, but um, when uh, Shatu was picked by Satoshi uh, for Bitcoin, it was uh, 8 years old and when Vitalik picked Ketchac for Ethereum, it was also

8 years old. So hopefully 10 years for Pedon one uh, should be should be sufficient. And one of the things that uh we're we'll be doing is focusing the the $1 million padon prize specifically on pedon one uh so that we can uh have as much confidence in it as possible. So we have these two initiatives um that Mitri will be talking about later in this call. We have um a 2026 edition of the PASon initiative which will be starting you know imminently with $150,000 and in addition to that uh we will have a million dollars for the Pedon prize

and here it's specific to Payon one a total of 1.15 uh million dollars and this is a little bit of a of a stretch goal but I'm hoping that we could um start uh a NIS competition, you know, similar to what we had uh with with SHA 3 for these ZK uh friendly hashes. I think the just the world in general would greatly benefit from this. And it's kind of very coincidental, but Andrew, you know, who's been at NIST for 18 years now and who uh who has been one of the the the key organizers of of of SH the SH3 competition, like he reached

out to me uh just a few days ago. Uh and I'm basically hoping uh to to to convince him to start such a competition maybe in 2028 or 2029. And if anyone here um would like to you know help with this potential idea um then then then please get in touch. Uh I think this would be this would be really really exciting and um to have some sort of a canonical nest standardized uh uh zk friendly hash function.

Okay. So today's call is extremely packed. We're going to have a bunch of lightning talks, two minutes each, and then we're going to have um five or actually maybe six uh presentations uh on on pad on uh crypto analysis starting with uh the main event which is the the paper that that that I mentioned. So without further ado, let's start with uh the lightning presentations with uh Dan Bon who will give us a uh an update on the uh proximity prize.

>> Ah yes, thanks Justin. Good morning everyone. Uh so this is just a quick quick uh update on what's happening with the proximity prize. So as you know uh the Ethereum Foundation set up this prize to uh study the proximity gaps basically how um which affects basically the length of hashbased proofs uh and other other other proofs. Uh so the goal is basically to resolve the proximity conjecture. The Ethereum Foundation actually put some money into resolving uh this this conjecture. Uh and the question is how what are the rules of the prize? And so the judges are myself uh Jako Mafenzi and Galon. We put together a paper that uh describes the the goals of the prize. What what what

Dan Boneh — proximity prize update

is the problem that needs to be solved? Uh what's the current state of uh [snorts] knowledge? As you remember, I think in the last meeting we had like a whole bunch of results on proximity gaps. I think we called it proxtober or something like that. We had this explosion of results uh that happened. So we kind of uh put this all um relate them all to one another and kind of describe the state of the world including even this new paper that was just posted yesterday, the stew paper uh we include that as well. It's supposed to be a living document that will uh continue continue to kind of uh uh state the state of the world and the goals of the prize. So the goal in one sent one sentence is basically to resolve uh conjectures about mutual correlated agreement, line decoding and list

decoding. Um the in in one line the the the the the grand challenges in the prize are stated as given a code uh can you identify the largest parameter delta such that for any larger value than delta the these proximity gaps fail with a certain probability and again the paper specifies that very precisely. So the paper is done people have have reviewed it and I hope we can post it on the proximity prize website um probably within a few days. I'll leave it at that.

>> Perfect. Uh any questions for Dan? >> Yeah, please work on it. It's beautiful problems. >> Yes, and the whole space would would benefit from it, not not just Ethereum. Great. Thank you, Dan. Uh next up, we have Mosen who will talk about uh push zero. >> Hi, everyone. So I just want to bring to everyone's attention this tool that we have recently open source. Push zero is a scheduling layer for zero knowledge proof infrastructure. Uh it it's built upon a very simple architecture. It has Q dispatcher and collector. So basically every piece is completely generic. You

Mohsen Ahmadvand — push0

could be you could replace it with your own tech stack. Um so the idea is any unit of work would be handled by the dispatcher. It could be a task in your prover, one of the subtasks that you have to prove and the result is always published to the queue and then you have this synchronization component that fetches all the results back together and then you can continue your u process on those. You can run parallel flows as much as you want. You can go completely parallel. You can have late synchronization with the power of the collector. The collector itself is also a custom Rust trait. You can implement it the way you want. And the Q based the Q itself what we call a message bus is something that you can also replace right now we are using NATS and jetream

but you can replace it whatever queuing system that you want. So if I want to say some differentiating features of push zero it has a guaranteed subproof collection deadlock freess um late synchronization you could see from some particular workflows this could give you a very significant boost. So we have seen that in practice. If your if your prover is written in rust, you can use zero copy prover integration. So no duplicates, no cilization, no FFI. You can implement whatever redundancy, whatever pipeline you want to have. Uh fault recovery, chaos already tested and complete linear scaling. Uh it's already published, a preprint is published on archive. Uh it's been used in production for more than 14 million blocks for over

a year. Um the source code is also fully open source. You can access it on GitHub. We have already tested it using ere SDK for different backends. SP1 used in mainet on test net also verified with risk zero and hello 2 and any other prover you want. Some numbers 5 second overhead and uh low latency. So if you want to talk about it, if you need any any help with trying it out, reach out to me directly. Thanks very much for the time. >> Thank you Mosen. Uh yeah, super exciting to see an open-source uh orchestrator.

Um and if you haven't spoken to Talpton yet, he just recently joined the EFC KVM team. I think he's very much interested in this kind of uh stuff. So um if I forget, please remind me to put him uh put you guys in touch. Um Dan Bonet in the chat um prompted by a question from Hector uh basically is saying that the uh proximity price paper should be posted on e-rint uh in the in the coming days which is fantastic. Um yeah, if you have any questions feel free to ask them in the chat or to just uh unmute or or raise your hand.

Thank you Mosen. Um, next up we have uh Justin Taylor who will give us some uh Jolt updates. >> All right. Hi everyone. Uh look pretty blurry here but uh hopefully you can hear me at least. Um all right. So I think I last gave a quick Jolt update uh back in late November. Um so just the uh everything that's happened since then. Uh so Jolt has uh integrated with uh zero OS um which means you can now compile rust programs without needing any custom fork of Rust or need to manually stub CIS calls and so forth. Uh Jolt is now zero knowledge. Um it didn't really change any of the costs. Um no need for recursion or anything like

Justin Thaler — Jolt updates

that. Um and a GPU implementation is now complete. Um so the the stuff that's well underway uh which uh we'll be wrapping up in the in the coming weeks and months. Um so we we're almost done with proof wrapping. Um it'll be an order of magnitude faster than sort of wrapping of alternative proofs uh proof systems because we can uh completely avoid non-native field arithmetic. Uh so I'm particularly excited about getting down to six kilobyte size proofs uh where the you know pro uh the extra proofer time is a fraction of a second right um but uh you can also go all the way down to like a grow 16 size proof um you know uh in in an matter of of

multiple seconds uh still still much better than if you had non-native field arithmetic everywhere uh you know like uh hashing based systems uh need to do their wrappings. Um we you know Jolt is generally targeted at proving big statements so far uh although you know you can run Jolt on a phone uh it's sort of unique in using only a few hundred bytes per cycle proved. So uh we are you know have significant optimizations uh underway uh uh for the the small uh statement sizes uh the sort of thing that arises in most privacy focused or client side focused applications. And then finally the big direction is uh switching from elliptic curve based commitment schemes to lattises. Um and so we we do expect major prover speed

ups when we do this because we'll go from 256 bit fields to 128 bit fields proof size under 100 kilobytes postquantum security and so forth and of course this will offer a major alternative to the hashing based techniques that are the focus of today's call. So I think this will be a major transition for the space and uh keep an eye on this. Uh, so that's my brief update on Jolt. >> Amazing. Thank you. And the 1.6 billion cycles with 64 H1s, that's 25 megahertz per H1. And I believe the 5090s are actually more efficient than the H 100's. Um, so yeah, that's really excellent. Um, I'm just wondering, do you have any kind of back of the envelope estimate on the speed up when

moving to latises? Um yeah, it's going to be at least uh I mean minimum 2x um but uh optimistically more like like 4x um yeah so that's that's the back of the envelope and then there there's additional like completely orthogonal prover improvements uh that we have to get around to implementing. So you know hopefully if the pure field switch is only good for you know 2x or 3x there'll be another you know uh boost from just other stuff as well. Okay, perfect. And on the GPU acceleration, I guess I have a couple questions. Um, one is um do you expect significant uh optimizations there

because it's just such a recent uh implementation and and two do you have a sense for when it might be open sourced? Yeah. So for the first one, so I think um the elliptic curve implementation that exists, yeah, it can probably get up to at least like 2.5 GHz on the same number of GPUs instead of 1.6. Um and then the hope is that uh you know, as as lattises come out, we get similar speed ups on GPUs as I I just the numbers I I just mentioned uh which is uh were for CPUs, but I I I think the GPU situation will be similar. So you know uh so so moving well above you know three three billion cycles per second on the same number of GPUs as as come the open source thing uh we're doing everything

we can um and so I don't really uh have something firm to say um but I other than we look forward to it being open source very much so it will be uh as soon as we we possibly can figure it out. >> Okay, perfect. Um, and I guess you know once you're running at 3 GHz there's like there's not much point in in in running faster because that's basically maxing out the uh the sequential evaluator. >> Exactly. Yeah. So I mean there is hope to you know um in certain settings you know to parallelize the uh trace generation. Uh but you're totally right like uh if you're running the trace generation serially, there's no point to going beyond three gigahertz of

throughput because you just can't do the trace generation any faster than that. Yeah, that's just native execution speed. Yeah. >> So we do have one question in the chat. Uh Ean is asking the previous announcement was regarding 645090s. This is for H100s. >> Oh, sorry. I just I just got it. You're right. 5090s. I just I just got it wrong. It was 509s. Yeah. Sorry. Sorry. Yeah. >> Okay. Got it. Um, great update. Thank you so much, Justin. Uh, next up we have Feder Rico who will talk about Lambda VM. >> Um, Justin, I think I'll I'll give the updates for for FedE.

Federico Carrone — lambdaVM

>> Okay, perfect. >> So, uh, the basic design is almost finished. We have almost everything implemented. It's without recursion. it must be uh 25,000 lines of code. We need to add like some accelerators. We are currently changing some things of the design to make it uh way more efficient. Um, so far, um, yeah, we we got like several, um, speed ups and I hope we can have something nice to show during, um, fort mode and, um, beast mode days uh, in KHN. So hopefully uh I I will be able

to show you there uh some of the improvements we we have been doing and we have like several other ideas on on how to improve. But um development is is is um going uh as planned and then we we hope to add uh recursion and some other cool tricks. So and GPU should be on the way as soon as that part is finished. >> Okay. Excellent. And for those who don't know, this is an event, two events happening next week. One dedicated to postquantum security, one dedicated to ZKVMs happening in CAN at TCC. Uh yeah, looking forward to the demo or the open sourcing or whatever the announcement

announcement uh is going to be. Thanks, Diego. Uh next up, we have uh Leo who will talk about Venus. >> Okay, let me share my screen. Uh can you see it? >> Not yet. >> Uh yes. >> Okay. Uh yeah. So here I'll introduce like uh the zenness like uh which is like our graph based zkVM uh back end. So the core idea is quite simple. So instead of like uh treating the proving as a back end function, we just encode the entire proving process as a computation graph. And this next shift like unlocks like three advantages.

Leo Fan — Venus

First of all is of course the uh the cross kernel optimization. So when everything is in represented at a graph then we can optimize uh across like boundaries instead of being just a stuck inside this isated kernels. Yeah. Which is quite critical for GPU efficiency. And second like it make our life easier for for security audits. So in the traditional H which stands for power abstraction layer style designs like which like we optimize kernel by kernels. So the important details such as like a fear shamir interactions or proof reduction are hidden inside the proof function. But with with a graph like everything is

explicit. We can we can trace the proof obligation step by step and even like uh build some independent checkers to verify the correctness. And the third one is the hardware support. A graph is directly complicable like to CUDA graph like on almost like every GPU and more importantly to future uh hardware such as FPJ or ASIC and this is what makes the the the architecture the design the future proof. The current status is that uh like we built our stuff based on uh this and we have finished the implementation the cuda implementation on this version 0.15 and we demonstrate about 10% improvement over that and yeah

since like right now uh uh for like the next step is like we of course as you can see like this 0.16 is out like we are optimized for that and hopefully we also push further for SPJ or ASIC. We will open source the code after the the upgrade is done. Yeah. >> Yeah. Super cool. Um I mean there is another team that's also working on uh FPJ acceleration um of ZISK and the numbers that they shared with me was that uh it potentially like 4x more energy efficient than than a 5090. Um, and you know, one reason why this is exciting is that when you move from FPJ

to ASIC, more or less you get a 10x uh improvement there on energy and efficiency. So, we're potentially looking at a 40x improvement relative to the the the 5090s, which would be absolutely incredible because energy efficiency is the key bottleneck uh at least for for Ethereum scaling. Um, and uh, yeah, great to hear that that that that you're also working on Zisk and hopefully we have a sharing of ideas there.

>> Yeah, sure. >> Um, great. And, uh, Mosen, you have a question from Jonathan in in the chat. Next up, uh, oh, and the answer is yes. So, basically, um, Jonathan was asking, is push zero agnostic from the underlying proof system? And he said and yes, so this is hope potentially a new standard in in the making where you know you can just focus on the on your proof system and then all of the orchestration infrastructure can be handled uh by push Next up we have Yoichi uh who will present EVM ASM.

Yoichi Hirai — evm-asm

>> Yes, EVM ASM is uh about guest. So the VM that will run on the ZKVMs. Um I'm sharing the slide. Uh so the approach is to implement the EVM directly using the risk 5 assembly. So not using any kind of compilers or higher level languages to uh produce risk 5 just to write instructions like load add store something like that. in the lean theorem prover and prove theorems about these assembly programs that ultimately says

that these instructions sequences of instructions implement the EVM. Um the big elephant in the room is that the Rust compiler has not been formally verified. So if you prove some nice properties about your Rust program, it doesn't uh translate automatically to the result of the compilation. So you have to do something else and then the result of the compilation changes like every time the compiler changes or somebody comes up with a nice optimization or something. So you have to repeat this effort also like defining C++ is not uh easy. It's complicated and uh

sometimes takes like multiple count stakeholders so like takes years. Um the approach here is to vive code the assembly program and vibe prove their properties in lean. The nice thing is that the risk 5 specification itself has been um translated into lean already. The foundation gave some grants and some many people worked on this. So I'm going to use this and I'm also going to use the EVM specification in lean. So I have the ingredients and the target both in uh lean. Oh, time is up. Um yeah, it's just in progress. Yes, I'm just trying

the approach. >> Yeah, I absolutely love this project. Um it's not one that we're currently supporting uh through the the ZKVM formal verification effort. Uh, but it's one that I think is extremely promising because you you bypass the whole all of the compiler. There's no Rust compiler. You just go directly to to the metal. And this would have been a crazy project uh you know even a year ago. But now it just seems oh yeah we can just do it. [laughter] Um and uh this might be the the way forward to get to a canonical guest which is end to end formally verified um and could potentially you know replace

the current strategy that we have with client diversity. Um and I believe uh you will be coming to can so really looking forward to the discussion. >> See you there. >> Nice. Um next up we have Emil who will talk about fancy aggregation. Hi, I will just simply share my screen and uh show you an example of um hashbased signatures aggregation with a hashbased snark. So as you can see there is like a,40 XMSS being a aggregated three times and then you recursively aggregate those three aggregated signatures and you

Emile — fancy aggregation

continue and so on and in the end you end up with the total aggregation below 128 kilobytes with without proximity gap conjectures and you can be even lower like approximately 25 kilobytes with those conjectures and everything has based postconquum extera. That's it for me. Thanks. >> Yeah, that's super super cool. And did I see correctly on the screenshot that not only are you merging aggregate signatures, but you're also removing signatures?

>> Yes, it's because we allow the intersection to be non-MPT. So basically when the intersection is five I've written minus five meaning that the total number of aggregated signatures is five times less than the sum of the two previously aggregated signatures. Nice. And what >> I I didn't quite have time to see the um slide post the link to it. >> I will I will show it again. Sorry. Okay. Yes. Cool. >> Yeah. And in an Ethereum context, this would all be happening in parallel across different subnets. And so, you know, what took a few seconds here will hopefully take, you know, a fractions of a of a second. Uh, super super cool.

Thank you so much, uh, Emil. Um, cool. Next up, we have uh Guy who will talk about the first approach uh to adding ZK to hashbased knocks. Uh, Guy, the floor is yours. >> Yeah. Um, okay. So everyone uh so I will tell you about our work on zero knowledge IOPS for constraint related codes. So let me start with a bit of background. So what we want is the best proximity test and so far most of the efforts were towards minimizing the query complexity which which translates to the argument size for hashbased norms. Now we might also like to have uh faster provers and most significantly

Guy Weissenberg — zkWHIR (zk approach 1)

for us honest verifier zero knowledge. So um the codes we consider in this work are interled codes which is a rather general family of codes that is generated by stacking code words from a base code uh to form a matrix and the alphabet of this code as uh are the columns of this matrix and prior works for um for these type of codes achieved uh different things com like with uh these three um um dimensions. So uh in terms of soundness what we would like to have is list coding soundness which reduces the number of queries. Uh in terms of code we would like to have code agnostic construction that we can in instantiate with whatever code uh we

want. In terms of zero knowledge, we would like to achieve that and we would like to have as little overhead as possible. And the question that we ask is can we get all of the above uh simultaneously? And the answer is yes. We can get uh we can say that the state-of-the-art zero knowledge PS are as efficient as non-zero knowledge state-of-the-art PS where the zero knowledge cost manifests in the lower order terms. So in terms of techniques, I'll just tell you very briefly that what we do is that we avoid the naive full masking approach which incurs like an overhead of at least two and we uh what we do instead is that we use like mask of sublinear size and this allows us to get basically no efficiency loss.

Now this is easier said than done because of the size mismatches between the big code word and the smaller mask and we use a new committed soundtrack relation to propagate these claims. And terms of other goodies, we also recover uh previous protocols using unified framework and we have a modular construction that we can instantiate um yeah mod construction with zero knowledge building blocks and composition and finally rely heavily on zero knowledge codes and uh distance and we also discuss the benefits of distance amplified codes in terms of efficiency. Um yeah so that's from me.

Wow, super cool. Um, and in the Ethereum context, we've already started work on shielded transfers at the L1. So, equivalent functionality to Zcash on Ethereum L1. And you know, we want to make lean VM ZK true ZK. Um, and uh, perfect timing. Um, and I believe also that, you know, Zcash might also be interested in in in postquantum uh, ZK as well. Um and coincidentally we have uh Thank you Darra. We have another um uh approach which was I guess uh and made public today from Ron. So Ron I'll

Ron Rothblum — VEIL (zk approach 2)

I'll let you explain your veil approach. >> Uh thanks. Yeah. Can you see my screen? >> Yes. >> Perfect. Uh hi everyone. So happy to tell you about this new work veil which we just uh um published on which is a very kind of simple and lightweight way to add zero knowledge to hashbased multi-linear proof systems. So first of all what are typical approaches for adding zk. So one thing that is very typically done already since the 80s is you adding zk via proof recursion or composition. So composing a nonzk proof system with a zk proof system. That's a very typical approach. Another one is more in the lines of what guy just described which is kind of adding ZK from the ground up to each and every

component in the system and to also kind of all the glue uh between the components. So these are two kind of typical approaches. They both have pros and cons. So uh the composition approach is very modular. It's very clean. You just sort of wrap everything at the end and you're happy. But it is costly because uh the ZK proof system is now proving kind of a expensive verification that usually involves a lot of Merkel uh hashes and turns out to be quite expensive. You also kind of have to wait for the nonZK proof system to finish before starting to prove in ZK. That's that that's a disadvantage. Um for uh sort of the groundup approach, the main disadvantage is that it's sort of very intrusive to the codebase. You have to change all of your components to support

ZK. um which kind of can be quite quite hairy, hard to maintain and audit. And what we were wondering is can you get the best of both worlds that's what we were attempting to get with uh veil. Um so veil is a very simple uh and lightweight compiler. It kind of tries to follow the composition approach but without the the caveats and it's very much inspired by uh mater's works on anonymous credentials that's implemented in Google wallet. So uh we implemented this as sort of a PC. uh what I'm reporting here is for kind of a very simple um inner product computation. So you commit to two vectors and prove their inner product. Um what we're seeing is is sort of very small overheads. If you were to add this to a

complex system like SP1, the overheads would be much smaller because you only do it at the end. Uh it's a lightning talk. I won't have time at all to tell you about how it's done. Um but happy to chat about it afterwards and the paper is online as is the implementation. Oh, very cool. I didn't realize the paper was also online. Um, I guess I'm curious uh for the previous presentation guy, is there any overhead to the proof size as well? >> Yeah, I mean there is going to be a a small overhead coming from the mask that you need to send um but it's going to be little order of one compared to the um big code word that you send initially.

So it will be like something you can imagine something like uh the code word being of size n and the mass of being of size like log n or like square root n. So like it's n * 1 plus of one. >> Okay. And concretely do you think you'll be roughly similar to 12%. >> Yeah. I'm not sure about that but I think we are trying to get some estimate of uh how it will perform in practice. >> Yeah. And one thing worth worth saying is that um within a complex system in which you do sharding, you can also like compose um a zk proof with a nonzk proof to shrink the size of proof if that's what you're worried about.

>> Right. Right. Right. Makes sense. Got it. Um thank you Ron. Next up we have Farah who will and will who will give if proofs updates. You share my screen. Okay. Yeah, we had another kind of major update to ETH proofs. Uh the real time proving cohort is live and running every Sunday night. Um it's capturing a snapshot of the last seven days. And just as a reminder, to be eligible for the cohort approver uh must be using a ZKVM that has been integrated into

Fara Woolf + Will Corcoran — Ethproofs update

SoundClout because that's uh security sprint milestone one. Um you have to be running a 1:1 multi-GPU cluster. So trying to submit for every block. Um you have to have a performance score right now of at least 70%. So that's sub 10sec blocks 70% of the time. And you have to have a livveness score of at least 95%. >> Sorry about this. >> That's right. Um and so also we have uh improved metrics and charts on every page too. So definitely go check it out and give us feedback on anything um you say see there that you have questions about. Um and then our next chunk of

work that we have coming up is um we're going to try to improve our block timestamp by running our own node. So we have that kind of underway. Um the ZK tester uh validator client is actually in the staking queue so we can kind of monitor that performance and begin working on that again and trying to surface that information on ETH proofs itself. Um and then we will also be integrating into ETH proofs this one um in 10 kind of proving cluster that will is going to talk about next which is this on-pre proving cluster.

>> Uh thanks. Yeah. So in addition to the pushes to the uh platform that went up earlier this week, we also announced uh both a new I guess grant initiative, this onrem proving initiative and uh it gave us an opportunity to like really take a a close look at the the ground rules for the existing grants that remained unclaimed uh from last year, the real-time proving grants. So if you go to eproofs uh.org/blog org/blog. There's a post that talks through both of those programs. Uh the TLDDR with the on-prem is that, you know, we really want to do what we can as ETH proofs to

emphasize and encourage uh on-prem proving. Uh so with our available uh grant funds, we approached the five teams that participated in the real-time proving uh cohort and four of them have decided that they're going to uh receive the grants. And so through that, they're going to get to uh enough uh funding to procure some hardware that's going to allow them to be able to kind of stand up and do these uh one and 10 proving cohorts. And so we're we're hoping to sort of use this to to monitor all the different um nuances and individual behaviors of of distributed onrem proving um and hopefully continue to grow that cohort uh after we kind of

roll out this initial round. Um yeah and then uh also in that uh same blog post you'll see a lot of information about the real-time proving. Uh just a quick note that like please don't conflate these uh grants or any competitions with uh the work that the ZKVM team is doing. That's its own separate evaluation process for the actual L1 ZKVM. And then uh if you go forward to the next slide, just a quick reminder that we've got uh beast mode coming up next Saturday in CAN. Very excited. Um a lot of great content coming together. You can find more uh online or DM me.

>> Perfect. Super exciting. Um and yeah, as you can probably tell, you know, the EF is trying to support many different initiatives financially. We have the formal verification, we have the PON prize, we have the proximity prize, we're, you know, paying for hardware. And I think as we move closer and closer to production and the the path forward is more and more clear, we're going to be you know doubling down, tripling down in terms of like financial support to actually get this uh on on mainet. Uh cool. This is going to be a long call. I think we're going to overrun the two hours by a little bit. But now we have the main event uh which is the paper that triggered uh this uh

Àlex Rodríguez García — skipping class

unscheduled call. We're going to have Alex uh present uh his uh skipping class paper. Hello everyone. Uh can you see the screen? >> Yes. Okay. So my name is Alex and this is the presentation about the skipping class papers. Thank you very much for the introduction Justin. And this is a joint work with Simon a very great postoc researcher at the exur. Now in this presentation I'll be talking about uh the posidon uh structure and what are we exactly exploiting.

Uh next I'm going to define uh what is an algebraic attack and what has been done before. Then I'm going to exemplify uh our contributions uh by explaining how we broke this bounty instance in the poson initiative. uh next I will talk about uh what are our contributions beyond the bounty and finally I will summarize the presentation and uh let the turn for the questions so first uh this is the postadon to design as you can see uh we have a permutation over the field elements that can be used either in sponge or compression mode giving rise to the hash function and this permutation consists on a

series of matrix multiplications questions. Uh, >> Alex, um, your slides are not updating for some reason. We're still seeing the title slide. >> Oh, um, oh, what? Sorry. Uh, can you >> are are now updated? >> Uh, now we can see kind of the toolbar. Um, >> just a very small subset of your screen. Uh, >> okay.

Uh what do I want now? >> That's better. Yes. >> Okay. Thank you. Okay. Thanks. >> Okay. So um as I was saying the poson is a permutation over uh T field elements uh that can be used either in sponge or compression mode. uh and this permutation takes as an input uh def elements and applies matrix multiplications, constant additions and element wise uh power maps. Uh in this structure uh the difference between posidon and posyon 2 among others is the choice of the matrix multiplication which will be important uh for our contributions and we will detail later but the important information for now is

uh that we are only applying uh sums and multiplications so that the output can be expressed as uh some polomial uh on the input variables which in particular gives rise to uh what we call an algebraic attack. Now the problem that is used to benchmark different algebraic attacks is called the constrain input constraint output problem. Uh which statement is as follows. We want to find a certain input such that the last k components remember we're talking about k field elements um so it's not k bits but k field elements that are equal to zero and the output of the permutation uh should have as well k

output elements being equal to zero. Now how can we model this problem algebraically? As I said before, uh the permutation consists on several sums and products of the input. So if we can model the input as certain variables and then propagate those variables through the permutation in this example uh t is 8 and k is three. The last three output components will be certain polomials on the inputs. Now finding a solution to the constraint input constraint output problem consists on uh consist of uh finding a solution to this system of equations.

Uh so two observations here uh for most parameters of Poseidon the number of variables is greater than the number of equations. Here we have five variables and three equations. So this is an overdetermined system. Um a a possible way of reducing the number of variables could be evaluating x3 and x4 to zero and then solving a system of three equations in three variables. Now notice that those polomials as they arrive from the posit permutation in the poson permutation we are applying a power map uh x to the alpha at every round. So in every round the degree of the polomials are increased by a factor

of alpha and if posidan consists on a rounds the output of the permutation will be of degree alpha to the r where alpha is usually 3 five or 7 a small integer. Now intuitively higher degrees make the system harder. So instead of evaluating x3 and x4 equal to zero, what we can do is finding a smarter algebraic technique to reduce the degree of those polomials and then making the system uh easier.

Now this has been done first uh at least in the pose permutation back in 2022. The idea of the round skipping trick uh is as follows. We de composed the permutation as two smaller permutations pi 1 and pi 2 where usually pi 1 consists on uh the first one or two rounds and pi 2 is the next uh all uh the remaining runs of pose. The idea is finding a certain parameterization which is depicted as b i.

So B 0 could be for example X0 + X1 + X2 and for every equation that you can see in the middle if we evaluate at a certain value at a certain X0 X1 X2 this parameterization has a property that uh the inverse under pi 1 will always be a valid input. So in this example uh that means that the last three input components will be equal to zero. Now how can this be used uh for an attack? Well, given this parameterization, we can just uh forward it through the pi to uh per permutation which consists on several posy runs.

Then we will obtain three polomials and uh we can solve a system that consists on consists of uh equaling those polinomials to zero. In particular, the advantage comes from the degree of this parameterization. If the degree is smaller than the one that we would obtain, if we directly forward those variables from the input, then the problem will become easier. Now, this is a very abstract idea. So, let me exemplify this uh with our attack.

Now in this section I'm going to be talking about uh how we broke the biggest bounty instance in the Ethereum posider initiative. This concrete instance has 16 input elements. Um these elements are over a prime field of uh where the prime is the M31 mer prime and the last two inputs and last two outputs are constrained to Also the power map is five and the permutation consists on 10 rounds in total which means that if we propagate the input variables through the whole permutation uh we are raising to the power of five 10 times which means that the output polomial will be of degree 5

to the 10. Now as Justin said at the beginning of this call uh what we're doing is exploiting a certain structure that is present in Poseidon 2 but is not present in Poseidon which in particular is as I said in the beginning of this presentation the external layer. So let's take a look at how this uh external layer looks like. In Posyon the linear layer was an MDS matrix while in Poseidon 2 uh the external layer is as given u in this slide. These are two equivalent definitions where the second definition is a 16x6 matrix uh given in blocks of 4

* 4 matrices where this M is the matrix that we can see at the right uh 5 71 3 etc. Now in particular the structure that we are exploiting is that the left matrix uh of this tensor product has this vector 0 1 - 1 0. Let me explain how with an example. Suppose that the input of our permutation remember it has 16 elements is of the following form where every letter consists on consist of a vector of four elements. So we have four elements plus four elements plus four

elements plus four elements 16 in total. And because we are uh trying to find a CO2 solution uh the last two input elements are forced to be zero. That means that we have 14 degrees of freedom in total that can be exploited. Uh these 14 uh degrees of freedom are used as follows. Four degrees of freedom are the variables in X and the other 10 degrees of freedom are used uh to define certain constants that uh I haven't specified yet which are U 0, U1 and U3.

U1 are vectors of four constants. U3 is a vector uh of two constants and two zeros. Now if you propagate this input state which I just defined through the first external layer, you will obtain something as can be seen uh on the right. In particular, neither the four first components nor the four last components depend on the variables. If we take a closer look at the second component, we have something of the form um mx plus a certain constant to the^ of five. And in the third component we have minus mx plus a certain constant to the^ of 5. What we are going to impose now is

that those constants have a certain relation. In particular, if I define y to be uh a vector of variables equal to the second component that that is mx plus certain constant to the^ of 5. I want the third component to be minus mx minus the exact same constant to the power of five. Um if this happens then the third component will be minus y. Um so what is the advantage here? We had an input uh of certain variables and after the first round we will obtain polomials of degree five in those variables. If we can make this change of

variables then our parameterization is of degree one and decreasing the degree means uh making the final system easier. Now this structure can be iterated again. So if this is the input at the first uh at the second external layer sorry after uh applying this layer we can again impose this similar equations and make another change of variables. So after two rounds we have another parameterization of degree one instead of a parameterization of degree 25 which will make the system uh way easier.

Now we could keep iterating this uh we could even skip some parts runs but in this presentation um I will leave it just here and I refer to the details uh at the appendix B of our paper. Now just to summarize what I'm saying is um we are defining certain equations so that the rounds skip exists. Uh then uh we want to find the certain solutions we want to find what are those UIs at the input and once we find those constants then we can make the change of variables that will give us a a roundscape. Uh in our case we brute force one variable.

So our contribution can be summarized as follows. We're basically saying that to find a solution to a system, we do some round skips and then we find a solution to the system. Okay, let's uh look at the experimental results. Basically, because we're lowering the degree of equations a lot, uh in this particular bond instance, the speed up expected is of around 18 uh.5 uh bits. uh we're going to give more details in the appendix B of the paper.

Now let's talk about our other contributions and key takeaways of our results. First of all, uh the round skips consists of defining certain uh sorry using the degrees of freedom of the input to skip rounds. In particular, we are using uh four degrees of freedom to skip every round. That means that intuitively uh the larger the amount of degrees of freedom at the input, the more rounds that we can skip. So the round skip doesn't work exactly the same for the same for different parameter sets.

Intuitively, the larger the state size uh the more degrees of freedom. So the more rounds that we can skip and the larger the number of constraints, the less degrees of freedom because we will have more zeros. So the less runs that we will be able to skip. So in our paper we detail a general run skip uh strategy for a variety of of parameters in particular uh parameters suggested by the authors. As I said before we also show weakness in the internal layer which was used to break this bond instance but also to describe the most powerful attack against full ramposid.

We also exploit the mode of operation of our permutation. So I said at the beginning that pose can be used either in sponge mode or compression mode. Um and in the next slide I'm going to give some intuition on why uh the sponge mode of operation can be easier than solving the constraint input constraint output problem which is a problem used to benchmark these alter attacks. Also uh we describe novel uh modeling for the collision attack that also improves upon the SQL problem which I'm going to explain in two slides.

And finally we adapt previous girlfriend script analysis to the case where we can do some run skips to the permutation uh just to argue uh what are the security margins of PON and why our attack does not threaten the 128 bits of security of uh what uh what they claim in some instances. Also we explore possible mitigations. So as Justin said at the beginning we are exploiting something that is in poson 2 that is not in poson that is uh the external layer that I've described uh previously.

So a very natural question is well do we need an MDS matrix uh to mitigate that attack that is going back to Poseidon? Well the surprising answer is that there exists a matrix that is as efficient as the matrix in Poseidon 2. uh but is completely immune to the attacks uh described in this paper. Okay. Now let's give an intuition of the round skips in sponge mode. Now let me remind you uh how the sponge mode works.

This picture is an example of two absorbing faces and one squeezing faces. Uh in this case we have two messages well sorry a message that has two parts m0 and m1. Then there is an initial value which I set to be zero for simplicity. And then we're adding the message in the rate part of the state. We propagate um this input state through the first permutation. At the output we uh add element wise the second part of the message and then we apply the permutation to obtain the hash. So what's intuitive uh the intuitive idea here? Uh the dis uh the difference

between sponge mode and the constrain input constraint output problem is that in the second permutation we have several variables at the input as before but uh the lower entries of the permutation a5 a6 a7 in the example are not constants fixed by the designer which were previously zero but are constants uh given by the previous permutation. So the intuitive idea is that we can use degrees of freedom of the input uh of the previous permutation to choose an appropriate lower elements such that we gain certain degrees of freedom for the

second permutation. And as I said before the more degrees of freedom uh the easier is to skip rounds. Uh let's go to the collision attack intuition. uh in the preach attack we have as many polomials as uh the size of the hash and uh each polomial has as many variables as the size of the hash. So in the example we will have to parameterize a fourdimensional variety uh because we have four equations.

However, in the collision attack, we can parameterize only uh a two-dimensional variety twice and then we have four variables as well. Uh and four variables and four equations is as well well defined. So what's the tricky part here in the primit? need to parameterize a fourdimensional variety in the collision, a two dimensional variety. And in some cases, parameterizing a lower dimensional variety is easier than uh a higher dimensional variety, which basically means that we can skip more rounds in the collision attack.

Now, this is a summary of the speedups uh that we obtain in our paper. Uh what can be seen in this table is that the speedups obtained in the SQL problem are smaller than the ones obtained either in the prematch attack in compression or sponge and the greatest speed up obtained is in the collision attack. Here this table the normal values of alpha is 357 and uh omega is the linear algebra constant which can be chosen to be two uh as a lower bound for the speed up. So for example in the pre-image attack for uh sponge mode in the kalabar example which is this alpha to the 11 omega the

speed up will be something like 3 to the 22. Just to summarize this presentation we have revisited algebraic attacks against poseon. uh we have explained the constraint input and constraint output hardness and then uh I've explained what's the exact weakness that we're exploiting in the linear layer. Um how the attacks can get better in the sponge mode and in the collision attack. Uh thanks for your attention and if you want to read further details uh here's a Amazing. Uh thank you Alex. If you have any questions, feel free to uh raise your hand or ask in the chat or unmute.

We do have one question in the chat from Darra who was asking um about jive mode 2:1 compression uh as opposed I guess to >> yeah originally originally described in the NMY paper but I think it um was also quite precise. >> Yeah. Um the 2 to1 compression is uh we have less degrees of freedom so the round skip is worse. uh and well in my presentation I simplified the table to only 3 to1 compressions uh but in the paper you can see like in the initial table I see I'd say it's page two or three um we give precise round skips for uh the two to1 compression as well >> uh yeah

>> uh is that is that uh 21 compression using sponge or or using drive >> uh Uh no no uh using sponge we don't have any any wrong to one. >> All right. Okay. Thanks. >> Uh J with the identity matrix. Yeah. >> Alex, do you think there's more drifts to squeeze on the attacks? Of course, they they can only get better. Uh and what is your confidence level on Poseidon 2? Do you think it will break at some point?

Uh, what a question. Um, yeah. Uh, I I think in the Ronkip part it's hard to get it better. Um, but I think in the solving part there are potential improvements. There's still some growth exploratory I think. Um, so I think it's hard to predict. Uh, the Poseidon designers took a very large security margin. So it's hard to get it lower than 128 bits of security. Um but uh I think we would need more time to to investigate.

>> Thank you. Anyway, because we were considering using um Poseidon 2 in Tcash and we will not uh I mean partly the the performance um uh issue that you raised at the start Justin um influences that as well. >> Yeah. So uh just to remark something uh our attack does not apply to all particular parameters in particular there are parameters for poseidon 2 for which our attack uh does not improve the previous state-of-the-art. For example, if the state size is four or eight, um we have no improvement and yeah in this case uh compression >> I think also for also for large for large enough fields um attack is that

right? >> Uh probably it's more related to the to the state size but I I say it's correlated. No. >> Okay. Alex, you mentioned in passing that we could find MDS matrices that are just as efficient than uh the pad onto uh matrix. Is is that is that did I understand that correctly? >> I I didn't say MDS matrices. Uh I said matrices that are resistant to our attack and the coident matrices.

>> I see. But they're not MDS. >> Uh the ones that we have found. No. >> Okay. Got it. So it was just to better understand the the scope of our attack, not to propose a new matrix of course. >> Okay, understood. And have you spent any time looking at pad on one as well? >> Uh yes, but only after the publication of the skipping class. >> Okay, got it.

>> So not much time. Yeah. >> Okay. Okay. And is it fair to say that none of the attacks that have been published apply to Padon one? >> Uh uh in our paper uh >> in your paper. Yes. >> Yeah. Yeah. Yeah. Exactly. Yes. >> What what's your intuition about the security of Poseidon 1.1? I I know that's a very general question. >> Yeah. My intuition is uh I mean it's it's hard to say. This is not mathematical and we don't have any proof. This is just an intuition and I can be wrong. I think poson one or two are more secure for larger parameters sorry for larger prim sizes and smaller state sizes uh basically because it's

more studied so I think the best understanding of the growth no basis attack uh has only come uh less than half a year ago and there can be improvements um so yeah I think the the smaller state size hasn't been as studied as the larger field side. >> And one side note on on these like small small primes, um the the Pedon prize, the $1 million will be dedicated to uh small small primes. Um so yeah, you're right. Like in in practice, in the past one was instantiated with these uh with these larger primes.

>> Great. Any further questions from the audience? If not, thank you so much uh Alex. Uh fantastic work and uh and great presentation and looking forward to your your future work uh potentially on on Padon one. That sounds exciting. >> Thanks to you and thanks for your introduction. >> Uh next up we have Katarina who will talk about Grubner basis. >> Yes. Hi. Can you see my slides? Great in a second.

Katharina Koschatko — Gröbner basis

Good. Um yeah, so um this talk will just be a very quick overview of um remnant basis crypto analysis of Poseidon. Um what are the algebraic models that have been proposed and what does this mean for the run derivation? Good. So basically for those who are not familiar with grinobasis, grinobasis is basically a tool to solve a polomial equation system. And how do we get a polinomial equation system? Basically we have Boseidon or any primitive um in a certain attack scenario say a primage attack and then we um just model this as a system of polomial equations and this is exactly the first step of a grip basis attack find an algebraic model.

Then the next step would be to actually compute the grinobasis and um this is typically a um degree reverse exographic grinobasis. So with respect to degree ordering then as a third step we transform this into a lex no basis and the advantage here is that um we have this univariate polinomial in this lex no basis and this univaried polinomial we can just solve um good so um there are several issues here so the first thing is already the algebraic modeling as we have seen in the previous talk um and as we will also see a bit later um there are a lot of um rounds keeping tricks that could be applied and um this might make the um system that

we're trying to solve um easier to solve. Then for the second step there have been recent works on how to actually skip or at least simplify this um grimnobasis computation step by um choosing a dedicated weighted monomial order instead of this um cononical um degree reverse lexographic order. And then for the um second step the next criminal basis there are some replacements but they have relatively similar um complexities. Good. So um let's start right away with this modeling tricks. Um so um for the modeling tricks we have this skipping initial full rounds of Prooseidon. Um the first work on that was uh from 2022

by um Baron Ador and they basically showed that for the initial Poseidon um they could skip the first two um full rounds and um this assumed that there is no initial matrix multiplication. If you add this initial matrix then um um only the first round can be skipped. So how is this done? Basically um one introduces um a fine subspace after the first sbox layer and um this subspace is chosen such that um when calculating backwards it um fulfills some input constraints. Say um it um is um the inner part um of um a sponge for example the init initialization.

Um then only recently um this um round skipping trick this one round skipping trick has been um generalized to a C2K. So if we have more than one state element um that is fixed in the input um and then you just saw the the very nice talk um yeah about skipping more than only or potentially skipping more than only one for round for two. Good. Um then there are also partial round skipping tricks. So for the partial round skipping tricks um one chooses some find subspace uh within uh the partial rounds. Um and um it is chosen such that um the next few partial rounds can actually be skipped and by skipping

we mean that um there is a linear relation um between um yeah those rounds. Good. And with this trick um around or at most t minus one partial rounds can be skipped if t is the state size. Um this um round skipping trick always works. Um so um this is independent of the um matrix that is actually used. Um how many rounds can be skipped actually depends on the state size and the constraints inputs and outputs. So basically the attack scenario.

Um one more thing about grid basis analysis. So um when all those arithmetization or detach function started and then um people started doing grimnobasis crypto analysis um what they did is they based the complexity um of a grinobasis attack on um the the first step of um this gripis attack. So the grim basis computation with respect to this degree reordering and um at first they um took a bound called the mccaui bound as a complexity metric [snorts] and um unfortunately this metric only is tied in case that the system is regular um and there has been a lot of proof in last few years um that typically those

um systems that come from arithmetization oriented hash functions um are not regular. So um those bounds typically overestimate the complexity and if you would now use it um for deriving round numbers it would underestimate the number of rounds needed to achieve say 125 bit uh security uh 128 bit security. So um what was done afterwards is um performing small scale experiments because large large scale is not doable hopefully if we aim for 128 bit security. So small scale experiments mean we take small primes um we um take smaller state sizes and um less round numbers and then we see um what complexity metrics do we get for the individual steps in our

experiments and then we try to extrapolate basically those metrics to um the real primitive instances or parameter sets. Um and hopefully um if our um estimations are good um or if we're confident in our estimations then um there might be conjectures. And now for Prooseidon 2 um or for Poseidon only very recently there was the first explicit criminal basis construction um where um afterwards tight security estimates could have been given and I think there will be a talk um shortly um this is the algebraic free launch uh algebraic cheap launch sorry good um so what are the implications for the security analysis of Poseidon and

Poseidon 2. So um maybe we should um so the first point is that maybe we should start basing the um complexity um not on the first step of the criminal basis um um attack but on the second step so on the um basis conversion on this FGLM step um because it's often easier to to predict what is the complexity metric in this case and there now also exists a proof of this complexity metric and then how could we potentially harden against those round skipping tricks? So, um the probably easiest solution would be okay just add rounds but um yeah this might not be beneficial for uh

efficiency. Um so one could also say okay we use an MDS matrix and this um for Poseidon 2 um in the external rounds but this would obviously be some um tradeoff um between the efficiency um using actually Poseidon one or um two with more rounds. Good. And for the partial runs, um this is always possible. Um um comp in comparison to this full run skipping tricks, um this partial run skipping tricks don't really come that much for free, so to say. Um and um yeah, a possible mitigation would still be to add t partial rounds, but it's not strictly necessary.

Um so what I have prepared here now is um a table where we show um the numbers the round numbers for Poseidon 2 for um some prime um of um approximately n bit size um with a security target security level 428 bits. And in gray you see the old round numbers and in um black I um have um some updated potential round numbers. So this is not a suggestion but um just what would it look like um if we now um used um the strategy to derive um round numbers based on the second step of a group basis attack. on the FGLM.

And you might also notice that for um the 31 and the 64 um bit um approximately instances um we also increase the number of full runs um just for the fact that um here we don't have an MDS matrix but for the 256 um bit case we have an MDS matrix in the external routes and uh finally um um it's probably necessary to revisit the different security levels. So you might know that for Prooseidon 2 there's this nice round number derivation formula and um this formula theoretically works for um different security levels and um there have been studies um on how the effect

is actually if we increase a very very high security level say one4 bits and um recently it has been shown um that um there we might need more rounds to actually reach which is a tremendously large security parameter. Good. Um so some further considerations. So um we already heard about the text scenarios beyond CO namely compression versus sponge pre-image versus collision and um might one might also consider security in schemes. Then um obviously grinobasis is not the only um possibility um to solve a polomial equation system. So there are other uh

ways recently also applied to Poseidon and a boundary winner I think was a combination of interpolation resultance. So CO2 problem and uh iterated resultance not applied so far I think. Good. Um then another open question is how um do our small scale experiments scale to actually practical sizes. So we need more experiments on larger parameter sets and uh finally are there more models exploiting structures such as the structure of the prime um or as we have seen the matrices or even the round constants.

Good. Thank you very much. >> Thank you Katarina. Um you had a table with the suggested number of uh of rounds for pedon 2. Um was a similar work done for pedon one as well? Um not yet so far. Um but I think um in the next talk Maros um mentions um some implications on the complexities um for Poseidon one and Poseidon 2. >> Um you mentioned at the end um attacks based on the structure of the prime. Um so I think there's already something that was um if the see if the uh factorization of p minus one

was smooth then um there was an attack um and of course uh in practice we want um highly toadic um fields so that puts a you know that um p minus one has a high power of two so Um what is known about the security of Poseidon in those cases? >> Um honestly I don't know. So I have not yet looked into those specific cases but more into this general gr. >> This is a bit of a of a you know general

meta question but uh are you you know satisfied with the amount of crypto analysis that's going into pedon in general and if not do you have like specific suggestions as to how we could improve things? I mean there can never be enough cryptonalis. No, [laughter] but um I think it's very nice that there is a lot of um a lot of crypton is going actually into son. And I just recently made a comparison um graphics on um different CK friendly primitives and the amount of um crypto analysis that is actually going into it. And I think um by now Poseidon is on um place two just after Mimsy.

Yeah. So this is definitely a good direction I think. >> Okay. I'm surprised we're behind Mimy. >> Yeah. But there >> I'm surprised too because yeah cryptographic engineers just just abandoned Mimi after a few papers on it. >> Yeah. I mean most of the crypto analysis is also um also statistical analysis. So a statistical crypto analysis and not so much algebraic crypto analysis. So maybe that's other way. >> Katrina so all this work is uh analyzing classical attacks on Poseidon. Are you also [clears throat] looking at quantum attacks?

>> Uh no this is just classical attacks. >> So is anybody studying the quantum security of Poseidon? Isn't that that's the whole point of moving to Poseidon? No. >> Good question. [snorts] >> Well, the there are some there's some research on uh government basis attacks like on a quantum computer and there are like generic attacks not specific to Poseidon like how to improve several cryptony [snorts] methods uh if you have a quantum computer. But I I think the the overall consensus is that like the improvement that you have with the quantum computer

on specific attacks is far smaller than the improvement that comes for example with a uh grover search. So it's not not a square root improvement. Uh it's usually much smaller. So if you for example uh tolerate 64-bit quantum security uh and if you if you already have 128 bit qu classical security then you have this uh level of quantum security. So seems that no uh super fast cryptonalytic quantum attack is known that is um so much faster than the classical one.

Well, of course, we can't exclude that it will appear, but so far the results are the improvements are not that big. >> Yeah, it's an interesting question and if we are going to have another competition um then I guess quantive security should be an explicit uh criteria in addition to ZK friendliness. Uh, Katina, thank you so much uh for your for your great presentation.

>> Thank you for having >> Next up, we have Marcus who will talk about security margins. >> Uh, thank you. Let me just screen. Hopefully, you can see it. >> Yeah. Um, all right. Yeah. Thanks for the introduction. So, let's start right away. So, where are we at? Um first let me start with like two uh like yeah two two sentences here. So the original version of posidon which uses the MDS matrices is not affected by the recent round skipping attacks. So there's there's the other round skips. You can always skip like one round. This is true. Uh but the recent uh attacks do not affect it. Um so what does it mean?

Markus Schofnegger — security margins

It retains its full level of security of course including also the margin. Um as we know now this is a bit different for Poseidon 2 because it's affected in indeed by these recent uh very nice results. Uh but still it also retains it full level of security albeit of course the margin got a bit a bit smaller. So there's now some natural questions we can ask ourselves here. Of course the most like pressing one is what is the remaining uh margin of Poseidon 2? um if we decided to low how do we get back to the original margin and should just everyone abandon pose 2 and go to pose one so let me give an overview here uh a table um so I will explain later where these are very optimistic conditions

from the attackers point of view also these are not pre-image attacks or collision attacks these are attacks on a sec instance where essentially just try to be faster in some instance than brute force would be And uh still we see that essentially uh we still have a hefty margin for most instances and we are only one bit below the security level for the bottom right instance. One bit below because uh in this case 4* 31 is 124 not 128. Um yeah and about the table you may also notice that instances with like very small state sizes which are usually used for like the larger primes uh they're missing uh simply because they're not affected by the recent

transcript attacks. Um the reason being because the external layer is always an MDS matrix even in positive 2. So why are these instances very optimistic on these conditions? Well, first um in this recent paper, you essentially in some cases can skip uh a number of full rounds and then you can skip part of a full round with the remaining so by linearizing some remaining barriers. So in this case I've skip I've rounded up the number of skipped rounds. Um also it's for the K instance not for the full pre-image instance. Uh we further assume a linear algebra constant of like uh two where realistically would have like 2.3 or something. This of course scales the complexities up again. And also all of

this uh is we're always talking about computational complexity while specifically for those algorithms the memory complexity is often very very similar uh to the computational complexity and in in in practice the memory uh is a bottleneck much sooner. So this is also something which is often overlooked. But okay let's say we're still not happy. Uh we want to restore the previous margin right. the different different ways of doing it. So first we can of course try to use different S boxes. Um now that's just a recommendation from my side or opinion.

I would not do that because that goes against the idea of poson uh and it would also require a lot more crypto analysis. Uh we would move away essentially from the very simple design it currently is at least uh with respect to the S boxes. Um we could also try to increase the number of partial rounds but I would not do that either. We'll talk about this on the next slide. So the missing options are either we increase the number of pull rounds uh to some extent or we try to adapt the matrices of course because they seem to be the core problem of those around skipping attacks.

So okay why are full rounds better? Uh first uh if we increase the number of full rounds the impact on the attack complexity is usually larger than if we increase the number of partial rounds. The reason being that first they are statistically relevant. the bar rounds of course to do something statistically but we don't we don't really use them in the in the statistical argument um and also in the recent estimates and this is shamelessly copied from the skipping class paper here um it leads to a higher ideal degree if we increase the number of full rounds compared to the number of partial rounds um so this is from a security point of view of course from the like from the computational point of view we can say that uh each part need needs its own linear layer of course. Uh

so we need we would need comparatively more partial rounds and more linear layers. So this would make the entire construction probably uh a lot more expensive. Uh and also full rounds are more traditional. It's a hand wavy argument, but it stands on decades of cryptography that uh that using full rounds essentially is the more is the cleaner way of doing it. And we have seen that they're much harder to skip than the partial rounds. Um yeah and and what would the impact be? The impact would be uh minimal. For example, if we add just full two full rounds, we would have an impact of like 10 to 15% on the final computation. So it's not huge. Of course, this also uh applies to the C to the witness size, right?

Um okay. So we can skip uh we can we can uh increase the number of rounds, but we can also try to adapt the matrices. Um to me at least it's unclear if it's possible to define a matrix which is uh provably unaffected by all the recent round skips and also as efficient as the possidon 2 matrix currently is. Um there's this direction given in the skipping class paper. Um it's heristic. I'm not sure if it works for every subspace uh or just for those. Um but then of course we can say well let's just forget those more efficient matrices. Let's switch back to MDS. And uh years ago this was uh quite bad because MDS needs like n squ number of operations and so on. Uh but recently we've shown we can do this actually

better. So uh we can use something which is called like a certain matrix uh matrix. And it turns out that for uh for for most of the prime numbers we actually use in those proof systems because they have such a high to audacity and so on we can actually define circular MDS matrices for many different instances actually works very well and uh once we have such a matrix uh we can always do uh two things. we can decide to do some entity based multiplication which is asytoically much faster than the naive approach but it turns out actually in practice it's sometimes slower than the naive approach uh or we can choose a second option which is essentially a kasuba based

multiplication and this turns out to be very fast in practice and maybe we'll hear some benchmarks num benchmark numbers in one of the next talks so uh this is all of that is not too bad and actually makes one also pretty class. So, uh let me let me come to the to the conclusion of this talk with a with another idea that this is not a recommendation of what everyone should use. Uh but if you just focus on the partial rounds which are not really the like the core of those skipping uh skipping class paper and other recent papers um then we know that also the parts are different between posid and posidon 2 and in boson one we have this uh this equivalence where we can essentially take the MDS of the parts

and and transform it into an equivalent representation then we don't have the full matrices anymore in the partial rounds but we are we have like more or less random entries there. Um so in Psyon 2 we solved that we have a very efficient matrix also the partial rounds. Uh and because of this equivalent representation in possylon one um there's there's like there there would be no security reduction so to say at least not that I know of uh by taking just the full rounds of posidon which have the MDS matrix and the partial rounds of posidon 2 this would still be faster than optimized poseidon one um and should come with no security reduction. So this is one possible hybrid we can think about um in the in the future. It may be a possible uh

strategy here. All right. So um I I was very fast. So let's let's just come to the conclusion. Uh just summing up. So uh neither two are broken. And uh so this is this is not to take anything away from the from the results which I think are very nice and very needed also. Uh and I'm happy actually that those hash functions get analyzed uh so much. Um but but yeah the results also al also show actually that there is still like a substantial margin remaining even under conditions which are quite optimistic from the attackers's point of view. Um if we are still not happy about that if you're still like feeling insecure about 2 uh then we can switch to the MDS or even to

poss one to the original spec right to avoid all of those most of those problems like one round can always be skipped but that's another another topic. Um and it turns out uh that the performance hit if we do that is actually not huge if we use some modern optimized implementations. So that's um that's always a possibility of course. Yeah, thanks. >> Thank you Marcus. Um you had this table with like um I guess security margins for pedon 2. Could you quantify the security margins for pedon one?

Mhm. Uh yeah, sure. So, uh possum one will be essentially the second column here because we can always skip one round. Um and just more detail on the table. So, the baseline here is not what we analyzed years ago. The baseline is the original round number without any skips but still using the most recent estimates for the complexity of the attacks. Uh that's the baseline. Uh the second or the third column here is essentially skipping one round which would apply to uh to Poseidon one. Okay, got it.

Any questions from the audience? I have a question around you know the methodology of setting rounds. Um, as far as I understand, the way that the industry works is that, you know, the initial authors kind of make a best guess on the number of rounds and then, you know, there's like 10 years of crypto analysis and then eventually it becomes standardized or used in in in production. But like, wouldn't it make more sense to somehow revisit the number of rounds before standardization and before it's used in practice after we have the the 10 years of crypto

analysis? um so that we can make a more informed decision when setting the number of rounds. >> Uh yeah, so I I agree totally. This this makes a lot of sense. Um it's always like um it's always a distinction between is the is the increase of the number of rounds just an informed decision or is it because we feel insecure about it and um if I think if it can be like phrased in the correct way that indeed that's we're not insecure about the about the previous round now but we make this informed decision then I think it makes a lot of sense of course. Yeah. Um but we shouldn't do it because we're afraid of the original. Yeah.

>> I I just want to say that that cryptographic engineers hate um changing parameters um as part of the standardization process. Um first of all because they have implementations and so you end up with a thing like catch 3 that is different from char 256. Um Ethereum people know about that. Um, also I mean it it leads to kind of conspiracy theories especially if you're rem if you're reducing the number of rounds then are you sort of weakening it um deliberately um or incompetently and yeah we hate it just don't do it.

Another problem maybe is that uh well if a function is not fully in production and not fully standardized it attracts much less crypto analysis. So people are like less tempted uh trying to break it because well it's not a standard yet let's wait till it like becomes really good target to break. So if you never standardize it and you just change the number of rounds then you don't have like the best scriptic minds targeted at it.

Okay, thank you so much Marcus for this reassuring message that neither Padon 2 nor Padon one are are broken yet and there's no no need to panic. Um, next up we have uh Afava who will talk about cheap plunch. >> Thank you. Yes, I hope you can uh hear me and see the slides. >> Yep. >> Yeah. Uh so hi um I'm a PhD student at Simila UIB and uh I'm going to talk about our work on crypto analysis of Poseidon which we call the chipench attack. Um this will be more of a high level overview of the ideas of the attack and some of the things have

Atharva Phanse — CheapLunch

already been uh mentioned in uh the previous talks. So this is a joint work with some other co-authors from similar and some from uh France and our work can be found on the preprint archive uh of ICR and it's also currently under submission. So the setup as we know there is a push for crypto analysis of Poseidon uh especially the Poseidon crypto analysis initiative by Ethereum and our work was also supported by one of the grants. Um there's a need for uh understanding the security of posein against different types of attacks and algebra attacks are one of the main attack vectors. uh but there are some open questions in the

space which is uh what our work focuses on and uh we also don't break uh pose fully but uh what we try to do is to improve the understanding of how the algebraic attacks uh work so that it gives us a bit more confidence uh in the overall security of pose. So the pose hash function is uh set up in the sponge mode. Uh here we're working with the doubles of length t of elements in the finite field. Uh and p is the pose permutation that's getting repeated sequentially first absorbing the messages each of block uh block length t uh and then squeezing out the hash uh output. And this uh three branches are further divided into u rate

r and capacity c. And to understand the security of this hash function in the sponge mode, we would like to focus on the security of this uh permutation specifically that's getting repeated. And one of the common methods to do that as uh it's already mentioned is the constraint input constraint output uh the coco problem. So here we uh want to find an input vector where we have uh zeros in the last t t minus k places and some values x1 to x k coming from the finite field such that when the permutation is applied uh we get k zeros uh in the output.

Um and if so K problem is easy to solve then it's possible to set up attacks pre-image or collision attacks on the entire sponge uh hash. So for one uh there's a bit more uh clarity. We have more understanding on how the attacks work not just for Poseidon but in gerally uh in general for other hash functions uh in this space. Uh but for CO when K is bigger than one there's uh very little understanding and there's uh more questions to be answered here. Uh but why is k bigger than one relevant in the first place? Um so naturally we have that k is less than the number of uh branches. Um and when we have a smaller uh underlying field uh the

values of t, r and c have to be larger. So that leads to larger possibilities for k and then more sec problems are relevant. Um but even for just k equals 2 uh we need to have better understanding of the of the attacks. So how do we solve this? CK problem uh in an attack and what are the what are the open questions there? Um so this problem of finding the X1 to XK um we consider them as variables and we construct some polinomials f1 to FM using the uh CO output constraints and also the round by round uh structure of the pose permutation uh to make this polomials. Um and then

essentially the problem of finding uh x1 to xk the problem of solving the cok problem is then equivalent to finding uh roots of these polomials and to do this we use some tools from uh algebra. So we work with the the ideal generated by these polinomials in the multivaried polinomial ring. Um and then for this attack we find a special generating set for this ideal uh which is called the grouper basis of the ideal. Um and this group basis is tied to the monomial order which is an order that we can define on the elements of the of the ring. Uh it's just a way of u comparing two monomials which one is larger and which one is smaller and there are different ways of defining these

monomial orders. So the group basis is also dependent on the order. So for some monomial orders it's easier to compute the group no basis and for some it's more difficult. Uh and that's what we do in the first step of the attack. So we compute the group basis in an easy monomial order. Um then in step two we convert this group basis to this particular uh monomial order which is the lexographical or lex order. And then here we often have uh a univariate polinomial which gives us value for one of the x1 or x1 to xk uh and then we get the solution.

So often the uh step three uh is negligible in terms of complexity in the attack. Um so it's important to understand how step one and step two behave and how the complexity behaves uh to understand how difficult it is to launch a coco attack using my basis. So the complexity of step one depends on this value called degree of regularity uh DEG and step two uh usually depends on the ideal degree or DI uh both of these values uh depend on the structure of the ideal the polinomial system that we create to begin with and also the mon the monomial order because the criminal

basis is connected to the monomial order um and it's quite tricky to get this uh values uh right as it's already mentioned that uh the systems often are not regular and extrapolating from experimental values to large uh round numbers um can also be difficult uh because usually computing these values is same level of difficulty as actually launching the attack. So uh we would need some extrapolation from small scale experiments to find out what these complexities are for uh full rounds of pose.

Um and this is where some of the previous CO analysis has maybe struggled to get this complexity estimate right and then uh the ideal degree um that was observed in experiments was also lower than the theoretical um estimates. uh which leads to also the question is step one the bottleneck of the attack or is it the step two uh and these are the questions that we u try to solve. Um so going into a bit more details of the uh technicalities uh of the groom bases. Um so the core idea is that we use a weighted monomial order. Uh and since the groom basis is u heavily

dependent on the choice of the order this gives us uh certain advantages mainly that the polinomial system that we create can essentially be split into two parts. um one part that has a lot of co-prime leading monomials and the other part that does satisfy these uh regularity assumptions that are not satisfied by the by the whole system or in some other modelings. Um also the leading monomers of this first part do not interact with the leading monomers of this uh second part. Um and this structure is what gives us the the cheap lunch attack.

So let's say we have this polinomial system that's constructed using the coco problem on Poseidon. We have some polinomials P1 to PRP from the partial rounds. Uh we have the K output polinomials from the Cok constraint. uh and essentially most of these partial draw polinomials are the ones that have this property that the leading monomer prime uh and then we essentially don't need to compute the gula basis on this part of uh the system which means we only need to solve the system a smaller system which is p1 and this final k polinomials and even here we can make uh further simplification that we only need to

compute uh on the highest part. So even smaller part uh of the system because we again rely on some of these uh regularity assumptions. Um so as a result of this uh step one of the attack which was actually computing the group basis is now needs to be uh done only on the smaller system. So it is much cheaper than expected. So then the bottleneck of the attack is transferred to step two and that is the one that should be uh used to compute the uh number of rounds. Also for step two since the complexity as I mentioned depends on the um ideal degree. Um and the bound that was observed experimentally was uh smaller than maybe some other modelings. Uh and we do

actually get this uh bound in our theoretical calculations as well. so what does this imply for Poseidon? Um so the Poseidon system in our modeling is regular. So it does satisfy the assumption for our small scale tests. Uh and this assumption is essential when we when we want to estimate the Um this also gives us the better understanding uh of the difference in contribution of full rounds versus partial rounds. uh the way they contribute to the um immunity against algebraic attacks as we can observe uh in the ideal degree that the partial rounds contribute less uh because those

are the ones that we can uh separate uh when we make the smaller system um and in our work we show that group no basis computation in step one is much faster so then the bottleneck should be step two um there are also some more results that are u covered in our work but I in cover in the presentation. Um some discussion on the round skipping tricks but uh uh much stronger results here are already covered by Alex. Um and we also can use this cheap lunch structure to further study the step two. So once we transfer the bottleneck to step two, we can also give more refined analysis of uh the complexity of step two. Um and this can be found in our work. And to

summarize uh as I said for realistic parameters we did not we did not find um any attack any improved attacks on full pose uh but our work gives us more complete understanding uh of the behav behavior of the complexity um against uh complexity of the algebraic attacks um so that gives us more confidence uh in security of the of the hash function and uh thank you >> thank Thank you. Uh we have a question from Darra.

>> Yeah. So um a partial run's a bad idea. >> So So is the security that they provide sufficient to um justify using um them given their um uh their cost. So um the the original premise behind the design was that um it was beneficial to use um partial [clears throat] runs because they were sufficiently cheap and they still gave enough security to justify using them.

Do we think that's that premise was incorrect? >> Um no. So I would uh maybe go to this. So it's not that the partial rounds do not necessarily provide security against attacks. It's just that the contribution is much less. Uh but in this ideal degree partial rounds do have a contribution even less but they do have contribution and ideal degree is what we use for the estimation of step two. Uh and already the full rounds plus partial rounds. So this overall ideal degree is large enough for realistic parameters that um this chip learn structure is not a problem so far. So I would say >> but it so looking at that formula if so basically partial rounds need to be at

least k times cheaper than full rounds in order for it to make sense to use them. Right? If this is now the >> okay so so what is K here? >> Uh K is the K. All right. See? Okay. So, how does that relate to the um the parameters of Prooseidon? Is it the um the state size or >> Yeah. Yeah. Exactly. So, it it also depends on uh it depends on the state size and also the rate and the capacity.

So the coco problem is just on the permutation and then different so you have seco like k1 in input and k2 in output and different combination of these can be used for like different attacks. So it's possible that maybe if you have large field and only three uh state size or five so then you only care about k equals 2 k= 3 uh and then maybe it's not maybe it's not a a big factor but but yeah so this k is coming from seco problem so then that case but >> but the the k for the seco problem is not going to be greater than the um state size right >> exactly yeah Yeah. Yeah.

>> Okay. And the the benefit that you get from partial runs is that you're only doing one x sbox instead of state size xboxes. So if we have I I see. So, so it does still make sense because if whenever K is less than the state size, um we can expect to that the the partial run cost is worth it. H okay, [clears throat and laughter] I see Karina.

>> Uh yes, so very nice paper. Um, do you see any chance um that you could actually combine the round skipping tricks with the cheap launch system? >> Um, round skippingly impossible. >> Um, well because so our work is like quite flexible for the um like the K in K. So, and I think that that's the part that's like the restrictions for round skipping are like it's not applicable for maybe all K. So, yeah, I haven't looked into it much yet, but I think it should be possible >> just to like start the Coke Kumner basis

from Yeah. >> Mhm. >> Yeah. because you still need to find the monomial ordering, right? that um then basically fulfills this splitting property that you have that the first part is basically a grip no basis and the second part is at least has some nice properties that you can then use. >> Yeah. Yeah. Uh yes. So yeah that is true. Um so we do need the the weighted monomial order for the chip to work. So yeah I think I'll have to look into it too. >> Just wanted to know if there is anything ongoing in this direction already. Thank you.

>> Thank you. >> Father, as a kind of latest generation uh PhD student, um is your intuition that AI will play an important role in crypton analysis going forward? Um it seems like a good match especially for Poseidon because it's so highly algebraic. Are you starting to use it already? >> Um not in the attacks itself. uh so in in the in the algebraic attacks I uh I don't I don't see how yet uh that it can be improved uh that it can improve the attacks I think but uh yeah this I could be wrong of course

>> because I've been criticizing you know latises for example as not being post AI because potentially we have these like super smart mathematicians in the future that could find hidden structures in that. But maybe [snorts] the same argument just applies to Poseidon as well. >> Sorry there. >> I was just going to say that that AI is great for for actually searching the literature. Um because search was terrible the academic literature and now it's great. So yeah, um you're not sort of redoing work that people did 10 or 20 years ago, which [clears throat] you quite often were.

>> Yeah. >> Yeah. And for those factors, yes, I have used uh I would agree that AI is definitely quite useful um uh for for learning some uh new things uh new topics. But um in the attack itself uh yeah, I'm not sure. >> Got it. Thank you, Afava. Uh, next up we have Leo who will talk about state-of-the-art crypto analysis of Poseidon. >> Do you see my screen?

Léo Perrin — SOTA cryptanalysis

You hear me first? >> Yeah, your screen. >> You see my screen? >> Yes. Perfect. >> All good. Okay. So, uh, yeah, thanks. Thanks for having me. I will try to give an overview of the state-of-the-art on the crypto analysis of posedon. There will be some overlap with the previous talk. So I will try to to skip what needs to be skipped. Um just as a small background I'm uh I'm a symmetric cryptographer. I have worked on the cryptonysis of symmetric primitives for quite some time now. And so that's going to be my perspective on this. So yeah, what do we know about the security of posedon? And I will start with my conclusions so you see what I'm building up to in this talk. uh at this stage posed is one of the safest arithmetization oriented permutations I

can think of and I can think of quite a few. Unfortunately, that's not saying that much. Uh there's still a lot of unknowns when it comes to the the behavior of the relevant algorithms. So um I'm going to go over the the main threat posed by uh polomial system solving as has already been said in the previous talks and then I'm going to focus specifically on so sponges I think by that point we are all quite familiar with how they work. We want f to be good where f is the permutation used here. And what does it mean to be good? Uh it's actually very

hard to define for a block cipher. We know that it it means that you want the key to be hard to recover. But for a public permutation, you don't really have that notion. So one of the proxies we use which is not perfect as was pointed out by Alex in his in his talk uh is this seco problem. So where you want to have an input with k zeros that is mapped to an output with k zeros constraint input constraint output um is not sufficient that this problem is hard to say that the permutation is good but if it's easy then it is bad that's there is an implication but not an equivalent so in order to be able to trust posed we

need to understand the missing word is understand the complex lexity of solving this coco problem. Uh and in particular what we would like to know is how the complexity of solving CO scales with both the number of full rounds and the number of partial rounds. Um so in symmetric crypto we have a lot of attack techniques at our disposal. You have in particular statistical attacks which tend to work really well against classical F2 primitives like linear attacks but they're are basically relevant for cuson because it's hash function and differential attacks which are not a threat because of the good differential properties of x to the power d modulo uh the potential poor

choice of a linear layer. So that was some attacks that were published when the first procedon came out that you had bad choices for the linear layer. It's stuff that's much more understood now when you have some tools that uh can test if your linear layer is good or not. And of course, now we also have algebraic attacks. I need to switch the light back on. Yeah, there we go. We have algebraic attacks. And this is much less clear. While we have a good toolbox to understand the to to estimate the complexity of linear attacks and differential attacks, for algebraic attacks, not so much. And that's the main problem we have.

Well, how does it work if we want to attack round reduced poson? Uh, so first we need to encode our SQL problem into equations. Um, and then we need to solve these equations. So we're going to use polomial system solving techniques also to solve the system and thus obtain uh an input for the permutation that has the properties that we want. We have been over this already a couple of times in the previous talk. So I'm not going to insist more. And what you actually do uh is that you use a round skipping trick first. So you are not trying to solve uh to to write it in this way. You start after a few rounds propagate and um you skip the first rounds using some huristic.

Um we can skip much more than we thought. So I really want to congratulate uh Alex and his author uh on on their work that was presented uh earlier this afternoon. It's really really good work. They really go much further than was previously thought possible because they managed to skip three full rounds if I understood correctly which is a lot for pedon two using the classical techniques that we introduced in our 2022 paper. We would be able only to skip one. So that's that's really substantial but that's the round keeping part which is very hard to to understand and we just had a breakthrough. So obviously we

don't understand it well and then we need to solve and it's also a mess. So initially the lower bounds for solving the for the complexity of solving were based on the time taken time needed to comput a gram the basis but this is completely wrong because we can get this completely for free actually. so the the initial estimates were basically useless and another issue which is arising which has started to arise much more recently is that we try to estimate the complexity of the shelf algorithms that are made to solve this palo problem. uh but they tend to be less efficient than tailor made ones and so now you have these resultantbased

algorithms you have the use of the grave transform and these can have lower complexities than these other shelf algorithms and since they are um these algorithms have been made specifically for posedon we don't have a literature on their complexities because they are brand new uh so their precise complexity remains actually quite mysterious um so my conjecture um which is most likely correct if we put C equal to omega but that's an upper bound is that if you want to solve a co instance of posedon and that your sbox is of the form x ^ d then your time scales with this quantity here so there's not much happening actually this

d to the power k * rf plus rp that's the degree that presented in his talk just before That's actually where it comes from. That's the ideal degree. But you skip some rounds. So this is captured by this uh this factor here. So you have this ideal degree, but you divide it by the basically the number of S boxes that you skip. And then once you have done this, you still need to do some linear algebra maybe or to do something to get your actual solution to well your actual univariate polinomials that you can actually solve and to to get your solution and this is where uh also some stuff can happen. So what you can always

do is something like FGLM which is going to have a complexity that corresponds to the linear algebra constants. So you know like two to the something two to the seven two to the three if you're very optimistic. Uh but if you look at resultantband based algorithms it can be lower. If you're in the univariate case then basically C is equal to one. One of my students is working on resultantbased technique for C code 2 for pedon and the complexity is corresponds here to something that's lower than two where C is strictly lower than two. Uh so it's hard to know exactly what we can use as the value of C.

So um I'm going to see what happens uh when we plug in some numbers. Um so first before I conclude I will allow myself a small complaint to the on two designers. Um I was trying to get parameters and this is what you're met with when you read the paper. So I just took quantities from a table. >> It's terrible for implementers too. >> Sorry. >> Yeah, I can imagine. Yeah. Uh there is to be fair there is a script that gives you parameters. But anyway uh for pedon one I'm just so again I am not saying that attacks with these complexities

exist. What I am putting in this table is an estimation of this uh quantity here of this uh quantity that you want to be higher than your security level if you want to have some security arguments. And then putting some estimates depending on what values we use for uh this quantity C here which corresponds to the solving step and the number of rounds that are skipped. So for instance here this quantity here is perfectly realistic. It corresponds to univariate solving where you don't skip any rounds. It's in this case it corresponds to an attack that can be relevant or not depending on your field size. But that's how it is. Uh here for instance we are very pessimistic with

the complexity of the solving step. This is just the omega from linear algebra. But we are widely optimistic about the number of sboxes that can be skipped like this is do that. So as we can see from pedon in all of the parameter sets that I have looked at and all of these guesses about the parameters of the complexity formula we are okay even in the cases where we are not okay which is when this is below the intended security level we're not that far below >> can you go closer to the microphone because sometimes you're getting a little bit >> I can try I'm not sure which microphone is being used um but yeah don't hesitate >> that seems better

>> okay Okay. Um, so yeah. So basically for procedon one even far-fetched scenarios are okay and we will see what where the difference comes from. For procedon 2 it's more complicated. So for procedon 2 you have much more variety in your parameters because the field size varies a lot more. A field size of 31 bits or a field size of 256 bits mean that you're looking at a primitive that has widely differing state sizes which then has a huge impact because when you have a small field size it means that the attacks that are relevant will be of the form K where K

is much bigger because if you want to solve for CO K when K is equal to one when uh your field size is on is of 31 bits you will just brute force actually you're not going to do all this clever stuff. You're more interested in higher values of K. Conversely, in the case where the field size is much bigger, then you don't you care only about the case K equal one, for instance. So, you have some sets of parameters um that in this table that are probably unlikely to to occur. Um but so you have some potential situations where this bound is not high enough. I am not saying that attacks matching this bound exist. I I must insist. I'm just trying to see the

behavior of the different different parameters here. The big difference between posedon one and posedon two lies in this difference in field size. Since the field size is smaller and you have then a state size which is much bigger then it means that your partial rounds are much weaker than the food rounds. That's the first difference. And second, since you have a much bigger state, you have a lot more degrees of freedom to skip rounds. So your full rounds in a way offer you less protection.

Uh so that's what's happening uh here in this uh these red values here. That's why that's why they're here. um since I have put a number of rounds clip which is again I don't know how to do that but which scales with the the state size which in my opinion makes sense since you use these degrees of freedom um then you're hit harder by these round keeping tricks I think that's where Alex was going when he said that um olderon was more secure because of its bigger field size it's because the round skipping is much harder when the field size is bigger.

On the other hand, when the field size is bigger, the solving step is simpler because K is smaller. That's what hits you when you want to do the actual solving step. If you are trying to solve for many variables, then you have to use your FGLM or other such algorithms and then your uh your quantity C here is higher. So there is like a double bind type of situation where you want to have a small state size so you cannot skip round and so the round skipping step is not very efficient but you [snorts] also want to have a large a large state size so that um the attacker has to solve for a large K and thus has to use less

efficient algorithms for the solving step. Uh that's that's just how it is. Emil, did you have a question? You had your hand up. >> Yeah, I think you phrase it as a poson one versus poson two issue, but it's so if I understand correctly, it's really linked to the field size and state size. It could be also applied to poson one with small field and large size large state. >> Absolutely. >> Absolutely. So during the introduction, I would disagree with the idea that pedon one well posed on two does not inherit the cryptonysis of Pedon one. In my opinion, the two of them are indeed super similar and it's completely fair to call posed on two poson 2. The big difference comes from this difference in

parameter sets that are considered. uh and the strongest crypto analysis results on procedon 2 also come from something else which is that if you look at the the speed of research in the area of uh polomial system solving for symmetric crypto um when we designed in I think it was published in 2022 or 2023 it was prehistory by the by modern standards it's completely obsolete our security arguments by modern standards the standards of you know two or 3 years later are very bad like we can do much much much better now. So I think a big difference in the in the crypto analysis is these recent improvements in the understanding

of algebraic attacks. It's not so much an inherent property of procedon 2 compared to posedon one. They are more efficient against procedon two because the field size is smaller. But um yeah for the I I literally use the same spreadsheet like thing to generate both both tables because procedon one and procedon one and procedon two only vary based on their on their parameters. I would argue that procedon two is a particular case of procedon one. one of >> I'm a bit confused when you say that the um field size is small. Do you mean for the challenge problems or because I mean do you mean for the challenge problems? Because um I mean if I'm if I have a particular field that is

chosen from completely different um considerations for my protocol and I'm deciding whether to use Poseidon one or Poseidon 2, then the field size is fixed. Uh I'm not sure I got the question. If you have a different field then I mean so the big difference >> I'm not I'm not sure why you're saying that the field size is smaller for two. >> Uh so I had a quick look at the spec of pose one and they seems to really focus on these elliptic curve fields but I think the spec could also be applied for a smaller field size. Yeah, there is more >> there's probably more emphasis on the smaller fields in the spec of pedon 2,

but I agree with you. >> Um, another big difference if you look at the two tables is that RP is uh partial rounds. Here you have t and t of rounds. Here you have fewer. Uh, that's also one of the big differences in my opinion. But so yeah um my conclusion is that so at this stage yeah posed on two seems safe poson one also seems safe because I would argue that they're really the same thing. Um the problem is that there is not much room for error. So there was recently this breakthrough I call it a breakthrough on the round skipping side.

So who knows how much better we could make it and the solving algorithms uh we shouldn't assume that they are going to have a complexity. So we should absolutely assume that they have a complexity that scales with the ideal degree as that eloquently argued. Uh but we should not assume that it will be raised to an exponent which is omega the the linear algebra constant because we have attacks where it's not the case as a matter of fact. So omega is an upper bound but we don't really have a lower bound at this stage. Um so if we manage to lower it substantially we would need to have to lower it substantially from you know 2.7 to 1.5 to potentially have issues and to also

have huge increases in round skipping um abilities. so I I would like to be able to find arguments on both sides, but it's um I'm afraid I'm going to have to end on this not so optimistic note. Thank >> Thank you, Leo. Um, thank you for your your honesty and uh and food for thought. Uh, we're a little over time, so we're going to try and u move to the penultimate presentation. um by Dmitri who will talk about uh the bounds on round skipping as well as the bounties.

Dmitry Khovratovich — skip bounds & bounties

>> Hello. Uh do you see my screen? >> Okay. Uh great. So I'll be talking a little bit on rounds skipping and little bit on the bounty program we plan to have for a side initiative this year. So little kind of a positive note on round skipping compared to like this some kind of devastating news we have heard. So basically how I explained to myself the recent attack. So basically uh uh if we enforce certain conditions in the state and this enforce enforce conditions are marked with uh very similar constant values around the sbox.

Um and uh you can see that in order to enforce these constraints you you spent exactly four degrees of freedom per round. Well this four comes from a particular structure of a truncated differential. Uh we have four the linear layer. Um and uh this number four it allows us to say that uh we can exhaust our degrees of freedom after skipping about like 10 over four rounds but we still have to kind of uh spend some freedom for uh guaranteeing u output or input constraints and uh because of that uh the security margin is decreased by four or in some case uh five full So uh if we look uh in further details

what has caused uh this um well sort of uh high probability truncated differential which allows us to set an algebraic variety in later rounds and propagate it up uh through the linear and nonlinear layer to the upper rounds then uh well it's of course non ideal diffusion is was exploited here the fact that MDS matrix has a certain igon vector but vector is just a specific case of non ideal diffusion and actually we can relate uh the existence of such transitions which you call differential trails to general properties of matrix M and here we hope to have some positive results. Uh concretely uh in the ongoing

research we show that all existing round skipping attacks they're reduced to two conditions. So basically first of all there must exist a certain differential trail with few active s boxes and a regular differential trail with at least that many boxes and also there must be sequence of states satisfying certain algebraic conditions and the number of conditions is proportional around like half of number of active boxes and this is all very similar to the rebound attack for those who remember like AES and asbased functions in ciphers and hash functions. uh and most importantly we can get um an interesting property.

So uh uh the branch number for a matrix M is actually the the sum of maximal sum of non-zero elements in uh X and M * X. And for the branch number we can actually upper bound the branch number by uh 40 uh over M where M is the number of rounds you can skip. It means that for the maximum b you can't skip that many because u m must be small enough and based on this theorem you can simply state that if the linear transformation is mds that you cannot skip four rounds.

Uh the question is whether you can skip three rounds. It's an open question. It depends on the particular MDS. And I I think we can design such an MDS where you can skip three rounds. Maybe it will not be the fastest uh attack but still like uh with this uh property in hand we can upper bound uh the the power of round skipping attacks and for MDS matrices of PID one we can have some kind of sort of provable bounds uh on the security against this kind of attacks that's a positive result another sort of positive thing is that we announce a bounty program for this year.

Uh the full details will be published uh early next week I think on Tuesday and uh this will the bounty will consist of two big parts. Uh so one part is um new challenges uh based on the usage of Poseidon in protocols and the SEO problem and the second part is what we call ultimate price. It's Poseidon one uh price which is aimed to find partial collisions. Well, as you may have guessed is it's the task is to find the collision not on the entire output size but on on a subset of field elements.

And of course the difficulty of this problem it grows within number of field elements. The instances concrete instances will be published on Tuesday and of course to prevent like uh searching for such collisions in advance. The instances will have a short seed to prefix all hash inputs so that you cannot uh premputee uh the numbers in advance. So it all will be published around Tuesday on beside initiative.info and later the ultimate price will have its own website. So little formulas for uh the problems that we're going to have actually one there are several interesting things. So one challenge that we'll see is to find a

nonzero uh string for the input so that the total number of zeros in the input is not more than d so that when you hash it uh and you interpret the outputs as positions the original string in this positions must be zero. So basically pine the string so that when you hash it and you look at the outputs uh it the outputs point to zero positions in the string and of course difficulty depends on on d and it all relates to usage poseidon in the fry protocol.

Um the second interesting challenge is the code zero test. This is related to usite and sat shamir and it's basically about finding a polomial for which um so that if you hash this polomial then the output is its own root. So basically to find the polinomial so that the hash of the polinomial is among the roots and of course you can also upper bound the the probability that it happens and we'll select the instances so that it's difficult enough uh for people to try and the the collision challenge for which there will be a big prize uh it's yeah kind of regular collision property

find two instance two inputs so that they are equal in uh up to t uh field output field elements and the total price font is close to uh 1 million and it it grows with every uh failed elements you are able to collide on. That's actually it. Uh that's the summary of my talk and yeah I'm ready to answer the questions. Quick question on the portion which is not the pose on price but the 150k um is poseon 2 going to be part of the scope or are you also focusing on pose on one there?

>> Yeah, the plan is to focus on pose one. So, and we expect of course that it the methods will be applicable to Poseidon 2. But as long as our kind of main idea is to try to break Poseidon one, uh then I think it makes sense to to specify only Poseidon one as a target >> and for Poseidon one you're focusing only on qualar right. uh yeah well to narrow the scope yeah of course we can describe many more but it will make verification difficult and so on I I don't think that selecting qualar it makes the competition kind of unfair

or make it more difficult to define something I think one big advantage of qualar is that the degree of the sbox is small so that you can actually penetrate more full rounds uh at arena Uh yes about the the challenges um does it make sense to maybe also have a challenge regarding uh the matrices in the partial runs? So basically what uh Marcus mentioned that um the the partial runs or the matrix in the partial runs used for Poseidon 2 should be as secure as um the MDS matrix in the one case.

>> Yeah. Well probably it's a good question. Maybe there should be an award. So I think I think it's in the plan to award a paper that will have this question answered basically whether we can use um a nonMDS metrics for Poseidon one safely in partial rounds because it will benefit the optimizations. So not not a challenge but rather like a a grant or a gift uh to whoever answer the questions positive positively or negatively. Uh maybe this has been already said but to be sure understand uh it the choice of

the MDS matrix is totally free. >> Uh no we'll specify it. Uh >> Um yeah, I don't think it's it's free because um well it will have a big state and it will be difficult by by itself to verify that the matrix is MDS. So probably will not bother with it. >> Okay, Emil might be worth coordinating with Mitri so that whatever MDS metric you use or whatever you think is reasonable uh is potentially also used for the price. Uh thank you so much Mitri for these uh two pieces of good news hope.

Thomas Coratger — Poseidon benchmarks

Um and we're going to end off with another piece of good news uh regarding the Padon benchmarks uh from Toma. >> Can you see my screen? >> Yeah. Perfect. So I will give a short presentation about uh PLR3 and our posed one benchmark and I will give a brief word at the end about another project called pron regression. So I will go very quick over the slides. Uh you can check later if you want but this has already already been presented in extend so I will not go through it largely but

what's done basically it is a hash function built for for snarks that is very efficient inside circuit. Um on the contrary shadow 256 and ketch are more difficult to handle within within snots and so uh that's why we are choosing procedon for for our work. Um the problem is that with the recent attack we started to check posed on one again u from a code perspective and from a benchmark perspective to see if we can make it uh fast and try to limit the slowdown when compared to procedon one.

It is important to understand from an implementation perspective was changed. So basically between the two version of procedon we have the same sbox the same run constant run count sorry the same security but only the mixing layer change and so we have this dense matrix multiplication in procedon one with an MDS matrix that is very costly and that has been rendered very cheap inside posed 2. So we have to deal with this and to find solution to make this MDS stuff tractable.

That's why uh with the naive syncs we have like a lot of multiplication and we are trying to find techniques to reduce the number of multiplication from n square to something more tractable. So the MDS matrix that we are using is circulance. This means that each row is a shifted copy of the first one and uh this specialized structure unlock fast algorithm. So we are using katuba and potentially FFTbased algorithm. So these are the two main techniques that we are exploring inside3 and mainly the katuba convolution.

Here I have recapulated what all of the fields that are available inside 3. So you have baby bear, koala bear, meren, goldilocks. So these are listed there. These are the main ones that we we support in monkey 3 right now with a number of bits right there and the algorithm that we are using for posed on one. So mainly caratuba for everything and for goilux caratuba or FFT for the larger wids we are using FFT but we haven't studied that much this part because for all of our application including lin VM and the new lin consensus we are using kala baref so that is our main interest right now so goldilock I say it's less stud

here you have like the wrong configuration that we are using inside block So basically you have all of the grids that are tested for all of the fields. So baby bear, koala bear, goldilocks and mer. You have the Xbox degree the number of full round the number of partial round. And what is interesting to notice there is that the number of full round and the number of partial round is the same for both procedon one and procedon two only the linear layer differs. Here I think that this is the most interesting slide because these are like the benchmarks that we have run with procedon one and procedon 2 on a silicon more precisely M1 pro and this is very important because I think that if you

run with an L4 or something more performant you will get completely different numbers from my experience but basically there you have all of the fields that I summarized you have each time like posted on one and a post on two version both for scalar and ple. So this means that each time this is important to to have the number per permutation this is what you have there because for 31 bit field you have four lanes while for 64 bit field you have two lane. So what is important to compare there is the number the number

this is recapitulating there and what you can see and what is interesting is that more often like the slowdown is 2x when you compare procedon one to procedon 2 right there. So this is a bit of a slowdown but we expected at the beginning much more. So finally this is a pretty good news here like if you want to to check after you have like the precise benchmark for the scalar version with all all of the slowdown line by line and also the same thing for the packet version but as you can see there the let us say the average slowdown is 2x for posted on one for the packet version. This is the most

important one because in lin VM we are always doing um procedon in a packet form. That means that we compact things then we do procedon over four lanes and then we unpack. Uh so that is the good news about the benchmark because at the beginning we expected something much worse and finally with some techniques rearrangement packing formats CID and a bunch of of tricks we managed to to have like a 2x uh 2x slowdown which is not dramatic for our use case. And so finally I want just to to give a word about another project that is inside the plunky 3 uh GitHub organization but as a

separate repo the blank recussion project. So that is a project maintained mostly by Robin and um initiated by the polygon cryptography team initially and now mostly maintained by Robin. And inside this uh repo you have um a recussion uh based technique based on plunk3 on its own. So what does it mean? It means that you can verify a proof inside a stack circuit. So this enable proof composition and multilayer recussion. So the basic idea is that you you have a proof, you construct a

circuit based on this proof and then you proof this circuit. So that allows you to to do some some recussion and some two to one aggregation uh all all of that based on PL3. So we are importing all of the primitives of plank3 and we are doing recussion based on this. So that is a very interesting project and you can imagine that this is a bit the same things that we are doing with LINVM because the goal is the same to be able to handle some recussion or of proof but this is on a different approach because there it is a circuit based approach where you are building your circuits. This is not a VM. While on the LINVM side of things, you are

building we are building a minimal ZKVM with a specific GSL. So a language specific to express your program um in this language. So this is a different approach but this is visually interesting for us to have uh a comparison between the two. And so if you want to check it out for for now like the project is very simple with four basic crate the circuit crate where you can build your circuit from basic operations like mad and all of this. Then you have the circuit prover where you can generate proof for those circuits and then you have the recussion part where you verify a proof inside a new circuit to do the recussion pipeline. And finally we have a procedon

two ashing inside circuits uh to handle procedent two precisely. So but we want for sure in the near term to support procedon one as well all the discussion that we we had today during this talk. So if you want to check it out here you have the link of the GitHub repo and yeah thank you for for your time and like don't stay to to ask ask question or reach out. >> Perfect. Thank you, Tumar. Uh we have two questions. Um have you considered tomb cook I guess as an alternative to caruba and FFT?

>> Yeah. Yeah, we have tried these things. Uh for now we haven't seen that much benefits. >> Um we have cooked different techniques and this is the most optimized that we have for now. >> But I understand. >> Yeah. Intuitively, I would expect to cook to be better than FFT. Um, and then the question is between Katu and Toon Cook. Um, but I may be wrong. >> Yeah, we have check and for now uh we haven't seen any particular improvement.

We have seen also that things depend a lot on um on the widths that you consider for procedon. uh we are not for example if you take like koala bear uh opposed one we are not using exactly the same tricks for um 16 and 24 wids so sometime that can vary because of the of the size of the matrices and >> final question from Hector uh what is the oncircuit overhead of pad on one versus pad on Um I think that this is most like a question for Emil, but I don't think

that this is this is dramatic at all. Uh I don't know in Lin VM. I think this is the same order of magnitude as the 2x. Uh yeah, I would say so if you prove your possance via an air where you commit to a bunch of colons and then you prove that the relations are valid and see I don't have a clear answer but the 2x from Thomas makes sense to me but what I can say is that if you use GK to prove positance basically you will use um like a bunch of some checks to prove the cube transitions and you can move out the linear are um layers out of the some checks and in some sense you will

only prove cubes and so you will not see any slowdown moving from poson 2 to poson one tlddr using gk posedon one is as fast in circuit as posed 2 and also maybe final word on this I think that for our application that is in VM and xmss aggregation the cost of proving procedon is not that dramatic inside the VM. So even like if we have like a reasonable slowdown, it it is okay.

>> Okay, final final question asks uh but does GKR have other security issues? >> Yes, [laughter] but yes, in some sense yes, it's a fair point. But I guess we can that I think there are some tricks. I know the paper that you think of that you can use some tricks to avoid this kind of issue but definitely uh yes it's a bit tricky. Yes, I agree. Amazing. Congratulations to the 57 people who made it to the end of this two hour and a half call. Um potentially I'll see a bunch of you on the next call uh where we'll talk about

alternatives to pose. Thank you so much uh to everyone and to the speakers. Have a great day. Bye. >> Bye.