A Closer Look at Falcon

Key Takeaways

uh so today we're happy to have Yonana visiting us um so he's originally for doing his PhD in boam but uh this semester he's out visiting uh the University of Washington working with Stefano tar uh so he's been working on um concrete security of signature schemes and authenticated chems and today he's going to talk about some work looking at one of the nist um postquantum signature algorithms okay thanks for the introduction um and thanks for the invitation as well um as Melissa said I want to talk all like take a closer look at Falcon signature schemes which was um is going to be standardized by by nist okay like a short introduction so our uh nowaday cryptography is mainly based on on RSA or on or on delock and um with shes algorithm together with um like large scale quantum computers like most of our our um nowadays cryptography and standards are um at risk so the solution for this is postquantum cryptography and um to standardize um like this new type of cryptography n has launched a competition already like eight years back and this competition has been going on for multiple years and um two years ago in 2022 um um like n selected four algorithms after three rounds of standardization and one of them is a key encapsulation mechanism and um they also uh chose three signature schemes and the key capsulation mechanism is is is kyber and from the three signature schemes as the title could have given hint on I want to focus on Falcon um yeah the other signature schemes are Del lithium and sphin plus where Sphinx plus is um a hash based signature schemes and all the other Primitives are based on on lses okay so what are the advantages and disadvantages of Falcon so first of all um considering all the signature schemes Falcon is very compact so compactness um in terms of the size um is a very crucial property um of postquantum schemes because it's usually the bottleneck um so Falcon tries to um to tries to achieve a very small signature plus public key size and if we compare that to to the other signature schemes that were selected um so here you can see the sizes of Falcon um regarding the signature and the public key if you for example compare it to delium um it gets like signatures that are like around a factor of four a smaller and for things plus it looks like like yeah even larger the difference and yeah even together with the public Keys um we can achieve like very compact signatures okay so why not taking Falcon so yeah is there no level three option for Falcon uh no there's not so Falcon comes only with two parameter sets one like uh with the Ring of Dimension 512 and one of 1024 and because like the ring Dimension has be to be a power of two to have nice properties they they don't get like a a level in between um right okay so why not uh just taking Falcon if if if uh um if Size Matters um like a lot of implementations are using the lithium right now and one of the reasons is um which is a disp of falcan is is really complicated to implement and um this is mostly due to gsh sampling so Gan sampling is one crucial primitive we will also take closer look in in into later um so it's hard uh to implement Gan sampling which is basically like sampling from a discrete Gan distribution and to make this also like platform independent and like uh like like a standard is uh considered to be be hard compared to for example the lithium and I think um but I'm also not an expert in this this is why like lot of like like like actor in like industry but I think you're like more experts on that um um are a bit skeptical about implementing like Falcon compared to other schemes or using F Yeah question so how important is it that it's this go why why not do some binomial so for for binomial sampling I don't get like so I I need like a like a property of the Gan sampling that I like have like enough noise and I also have like noise that's flooding enough so basically if you um imagine like a lce has like a this discrete structure and I need like enough plur to get like a like uniform structure in the lce so a binomial distribution is like not enough in that case so what does the lithium use uh the lithium not entirely sure but I think for the rejection sample they use a binomial but like so this is like the main difference here is that the lithium is based on the FIA Paradigm and um Falcon is based on on full domain hash and so like like some structural differences why like in the ca like I I have to like distinguish some or like make some distributions close enough to other distributions and they are different in the FIA Paradigm so so I can I have there more flexibility um in the distributions from from which I I sample from right so this is more a practical aspect but another question what about its security so um do we have provable security for Falcon and um if so like what concrete security and this is also actually a question and on this part I will like focus on on the remainder of of the talk okay so how does falcon look like so Falcon is following the gpv framework introduced by by chry P contan and um gpv is proving like a proposing a lettuce based construction following this full domain Hesh Paradigm and Falcon is also following the structure so for example also most of the people uh I talk to about the security of Falcon um they told me okay but I mean we have gpv gpv is proven uh to be secure so um where's the problem with Falcon um so Fon uses similar structure so it should be fine but actually it is not so if you look at the proof of a gpv and you want to use just the same arguments to prove the actual construction of Falcon um it turns out that this proof is not sufficient and one of the reasons is that okay this is like a small reason but Falcon is defined over ental lses which you can think about it's like just a special structure of lesses and not about like unstructured plain lses this is a minor point I mean we have like most of the tools we have for plain L we can also adapt to to andales but um a bigger problem is that gpv is based on statistical distance um for their proof and if you use the same arguments from for for the statistical distance and you apply it to the Falcon parameters then it turns out that distributions that should be close in the gpv proof actually not close um if you instantiate it with the Falcon parameters so the proof doesn't go through or gives no security or not sufficient security yeah and the third problem is that um Falcon tries to avoid or avoids correctness error so if like I get a signature in the signing process which would not verify then I repeat the signing process and this is a a difference in the construction which we also have to take care of if we analyze it and gpv does not consider that like just has like an correctness error which can also be like if I considering it ASM totically can just be avoided um but FAL chooses chooses this uh yeah design I would say okay and um so if we adapt these things um the question or the question is can we adapt it so can we prove Falcon like from a provable uh uh security perspective and if we can this I can do that what like concrete bit security um can we get from Falcon and this is also uh quite interesting because I mean like all the other schemes I showed you were like standardized in August I think the standard like was published in in August Falcon is not standardized yet I think which is mainly due to the the subtleties of the concrete uh um implementation but um yeah I think people are not considering security enough but it's a personal opinion um okay so then what are our results so first of all um we adapt some of the results uh from gpv um So-Cal uniformity results to um the ren Divergence which I will explain uh in a few minutes so this is like a different uh way of measuring a closeness of distributions which already has been used in cryptography um then we give a proof of um a modified generalization of Falcon uh so what does it mean first of all um we propose a very minor modification to uh to actually prove Falon without the modification we are not able to um so question is like can this modification still be applied that late in the process since the standard is not been out yet but um we think it could um and it also comes with like a very negligible efficiency overhead um but I will also go into detail in a few slides and the other modification we propose is to Hash the public key um this is also like very common practice from an engineering point of view that you has the publicy or like good cryptographic engineering but the current Falon specification is not doing that um it also has been shown that that um we can get some other security guarantees if we had the public key and um we found out that we can give a new one so especially we can um give titer multi user security if we also hash the public key um yeah so the proof go go through very tight so we can increase the security there as well okay what do we mean by generalization um so um the proof we're giving or the theorems are parameterized by the Trap do generation so trap do generation you can imagine is like part of the key generation so in the key generation I generate a trapo uh from my LS and the pre-image sampler which samples from like Aion distribution and these components we are using like PL boox so that they can also be replaced um and this can be like maybe interesting for the future because for example as I said the the key generate oh sorry the the Garian sampling can be a bit hard to implement and for example there have also been like uh proposed other key generation algorithms for example for this trap do generation so they could be replaced in the future um as well as the pre-image sampler okay so um yeah the last point is that we we optimize the security bound B we get to get a concrete uh bit secur for for one sampler and our results um are the following so we have like two uh two Falcon parameter sets a falcon 512 and F Falcon 1024 um and together with our small modification we get for um Falcon 512 we get um 100 bits of security for the full two to the 64 signing queries suggested by by nist um but if we reduce the signing queries um by a bit then we can get 118 bits of security approvable security um for for um unforgeability um and for um FAL 1024 which targets n level five and we can achieve 256 um for strong unfor ability on the other hand the uh things look look a bit worse um so so yeah I think targeting list level one is here a bit bit off I think strong unfort ability we we cannot talk about like for Fon 1024 we could not achieve any security at all but here I also have to mention so these are like the provable security would give so we don't give any uh concrete attacks um and we also don't claim that there could be like a better proofs I mean I will also talk shortly about this later so this is just what we could prove so it's just that the reduction is so loose that uh it's here yeah uh yeah um I think here it's a bigger problem I think here it's um the actual CIS advantage in the end does not give more than 93 bits of security for example so I think here it's not a problem of the reduction um because like I mean okay maybe you could also come up with a better proof to get like a better Bound for the for sis but um it's yeah rather a problem of the concrete parameters than of the reduction in this case I think sure so so so then what is the confused so um so what is the hard problem that it relies on that uh the security here or yeah the security here is reduced to to assist but you think that the parameters are meaningless in the sense they're they're like not good so then in practice it doesn't rely on that right it relies on just its own construction that's like the hard problem sure I mean you could also Define like um the scheme is like or like the assumption is the scheme is secure true but um that is right I think then but then you cannot like give any specific uh claim right like that isn't that what it what it is here right that's what you're saying that's how it is or oh no this is for the for the like modification right yeah but I mean for the I I I think the modification only makes it more secure not not not less secure um yeah sure I mean if if it can also say but I think that's also a general question how how much do we want to rely on like provable security um or on like attacks that have been there or not have been there um but yeah our goal was to reduce it to like some standard uh some standard assumptions like CIS or or Isis no because I think we have like more trust in them than in like a specific Construction okay then um I want to give some background and also like show you the concrete Falcon scheme um yeah the remainder of the talk won't have like much details on like a mathematical level but on a provable security level so I will go into some details of the proof and um because I think it's the main main contribution okay so first of all I already mentioned it the Renu Divergence so um for the ren diver test point to give like like a very brief overview so it describes the uh um the closeness of two distributions and can be seen as a generalization of Kolb Lia and has been used um already like several years um to get better security bonds compareed to arguments with the statistical distance so same thing we also applying and if you get like better security bounds um then you can also set your parameters p and the r diversion I don't want to Define it here but what is important is that um if you have like a r Divergence between two distributions p and Q then it like as we Define it looks like something like 1 plus Delta um so if two distributions are very close then the value should be close to one they are far apart than the Delta grow that also means that if we apply this in a proof then we have to apply it multiplicatively so this like compared to the statistical distance you would apply additively um if we have the diverence like this we have to apply it multiplicatively but this also means if you um if you apply or if you query such a such two distributions that are closed several times like Q times in a proof then you also get a loss of R to the Q so this grows exponentially and this makes also the loss very sensitive to the number of queries you're creting the distribution okay let's just some facts that I will I will use later I also remind you on these okay so how is Falcon defined so Falcon is defined like as for gpv is defined um based on a pre-image sample function um which is here like function f and we're Computing this over over ring like for the instantiation this will be a polinomial ring but you can also just think about this like just having like addition and multiplication and such a pre PR sample function is defined with respect to an age um and uh Maps two elements uh yeah to to an element in RQ for for a a sufficiently large Prime Q um so this is a forward evaluation of the prage samp function and it's like you can this is the additional the pre sample part you can invert it to some extent so there's also a function pre s which has a secret key and the secret key you can think about like a secret key with respect to an H so this will be the trap door in our instantiation and um with a trapo you can get a pre-image for some element c um in the image of the function so what does that mean um you you can get like an S1 and S2 um that follow uh um um the the uh this function so are actually a pre-image to see but it would be easy to get just a pre-image and this pre-image should also be like following a certain distribution and by d i Den note like distribute Gan distribution so this S1 and S2 should be actually distributed like a two dimensional Gan distribution conditioned on being a pre-image so conditioned on fulfilling this equation of the function and the AG here is theal public key exactly the the AG will be the ENT public key and the the secret key is the trapo for the public key exactly okay and Falcon is then defined like this so in the key generation I get such an age as you said like as a um UIC key and a trapdoor but uh more important um what's happening in the signing procedure so this is just like like a very condensed version of Falcon so Falcon is much more complicated also doing like know like thing FF T operations for efficiency this is just like the condensed part which we want to prove like the core which gives the security you already put the public n exactly this is also like a difference exactly so um but first of all I I sample assault so it's a probabilistic signing procedure and then I hash my salt together with a message and as as you said um here we already applied the modification that we also has the public key um right and then um The crucial Pro procedure is this pre-image sample function so then um if I hashed uh um my message and my my salt to a challenge I get a pre-image um um from this challenge this is only possible or should only be possible with the secret key so then I get an S1 S2 that fulfill um the function equation and I do this until my pre-image is small enough so it should follow a Garian distribution so it should be small like in the sense of like the norm of it should be small but um yeah since I'm sampling like something which close to G it can also land in the Tails so the probability should be low but can happen so I repeat this until I get a sufficiently small pre-image this is like to um um ignore the correct or to get rid of the correctness error and then I output the signature I I just need to Output one of the elements and the salt because the verifier in the end can compute the other element and uh then has to check check for smallness or shortness yeah is the small requirement is that to make it efficient or is that like a security so here it is uh for uh for like to to to ignore the correctness error but um overall to verify it here is a security guarantee so if I wouldn't have that so just uh check for a pre-images then I like everybody could compute this like large PR is easy to compute what is correctness error um so here is none a correctness error would be if I correctly if I use this pre-image sampling but I get um uh pre-images which is actually large even so I Ed this functionality since it should be close to a gan it can also land in the Tails and so I created a like a signature honestly but it sh still doesn't verify because the verify is oh no it's too large I don't accept it so if I choose like parameters such that my tails are very unlikely to to be like hit then there's no correctness error but as we see there is there would be a correctness this is ignored by that okay so this is how the um current Falcon specification works and what we propose is the following change so here um we sample the um the salt outside of this Loop and we propose to do it within the loop so if we fail um to get a sufficiently small signature um we say that it is uh better to start with sampling a new salt getting a new challenge for the hash and then resample of course this part is um bit less efficient because I also have like choose my new salt has to have to hash and so on but the the thing here is that the pre-image sampling is basically the bottleneck of the whole construction so like efficiency Wise It's like takes much longer than Computing the hash and also some other operations so the hash is also uh computed uh uh or from the hash is also computed the fft uh uh um uh representation and so on but these are uh way smaller than than the pre-image sampling also since um since it's like following a gan distribution it's not very likely that this happens so in expectation it's like between like a bit larger than one time I have to like uh uh execute this procedure so the expected value is 1 point something um okay so then we'll see why why this modification is uh necessary or maybe it's not necessary at least for us it was necessary to prove Fon to be secure um the first of all I want to just give a short overview how uh gpv worked or how the proof worked in um also very condensed version so what is gpv doing gpv is doing a a reduction in the end to CIS and um the sis game means um I get like a challeng h and I have to um output a short uh solution so short in the sense of the norm being bounded at most B um as a non to be a non-trivial solution which maps to zero so basically being a pre-image um with respect to this function of zero um yeah so you can also like this function is like basically all the all the values that map here to zero but construct the ls and but like if you just use this this ring notation it's like a bit easier to depict but they are equivalent okay and the reduction has like several steps I want just want to uh show you the two most important steps so we would um we use an um unfort ability adversary uh to build the re um reduction in the random Oracle model so the adversary has access to random Oracle and a signing Oracle and in the end has to Output a forgery and the first step um to prove that is to program the random Oracle by choosing some like some values S1 and S two that follow like the the Distribution on the domain and compute this function forward so if I do that then I output the value of my function but I have a pre-image like program for this value um for this to like be be sound the output of this function needs to be like close to uniform otherwise the proof won't work um okay so if I programed the random Oracle then in the next step I can simulate my assigning Oracle by just choosing the pre-images I sampled during programming the random Oracle right so this S1 and S2 they sample here pre-images for my output C and here I have to find an pre-image for the C so I can just take the one okay and then in the end um I can make the reduction so uh take the challenge Ag and forward it to the adversary and find a collision a collision I can find like a coll for my for the same challenge c um by taking the forgery which should be correct so it should be like a pre-images for the challenge C and I take the other pre-images which I programmed in the random Oracle and if I find a collision in the function I can just substract the pre-images and I have a I have a pre-image to zero which is exactly my sis solution okay then we want to take a look look at the actual Falcon proof so um why or where does this proof fail so we have a similar structure um now we reducing to entris and not Tois anymore in the end so um our AG is not necessarily uniformly distributed but uh distributed as uh Andro keys are distributed but they are well there's no no known attack that it should be easier um yeah to win to win to win the anist game then the S game but yeah um okay so same procedure again um adversary gets a public key gets access to random Oracle this is just now uh uniformly sample from RQ that was the domain of our fun H sorry the co-domain of our function and gets access to the signing Oracle signing Oracle also proceeds um just normally for this for this challenge uh public key AG okay so the first step would be to program our random Oracle again so in uh in this specific case choosing some S1 and S2 following a discrete Gan distribution and Computing the output for for the function which was exactly this equation and then we store S1 S2 and our C okay so let's take a look at this so this was the random Oracle we programmed so the question if like the reduction should go through is this distribution actually close to uniform and the question here is um what does close mean I also already hinted it a few slides ago and the question for statistical distance is no um to make more specific for the concrete parameters the statistical distance would be only 2 to Theus 35 so this is not sufficient for for making it like a a security argument right okay so yeah this distribution um and if you use the r Divergence um then we can do it so the answer is yes or or or maybe I will explain maybe U and we proed the following coroller that might be a bit overwhelming but I'll just tell you two things to look at so this is an adaption of the gpv or one of the gpv Lata and the important part so what do we need we need um the standard deviation to to be sufficiently large um and specifically so here we have the ENT lce and it has to be at least as large as the smoothing parameter and the smoothing parameter gives us nice properties um um of the L or especially of gion and one of these properties is such a uniformity property what is the S there the S here uh is this standard deviation of the Gan so here um right and if we have this so if we have these like nice lce properties then we can show that the distribution of P um and the distribution of Q which is exactly the the the distribution we programmed here are R close and and R close in that sense so we have one plus a hopefully small term and this term depends on a which is the order of the r diversion which which I ignored so far but this we can set more or less arbitrarily so this can be small um and also on Epsilon and the Epsilon is the error of the smoothing parameter so what does that mean or what is the intuition behind that so if I get if I want like a more secure scheme then I have to set a smaller Epsilon but a smaller Epsilon um comes with a larger smoothing parameter so smoothing parameter crows so I also have to set a larger standard deviation and a larger standard deviation leads to less efficiency because I get larger signatures so this is the trade of here and um yeah so like in a like normal approach by constructing a scheme we would set our parameters such that we get like a secure scheme here we had to do it like the other way around because the parameters were already set but we need to prove to fulfill this parameters um okay so what did I say maybe so it turns out this is sufficiently small this term for the actual Falcon parameters but we've also seen that the ren Divergence depends on how often I want to query a certain distrib tion so we cannot say like in general that this is sufficiently small it depends on how often um uh we query the like the distribution so how like we have to take this to the power of Q if we want to want to create the underlying distributions Q times so it depends so the reason for this statistical distance that is like non- negligable is the structure from the entry is that what now you could also you could also in the entry setting you could also set parameters that you um that you fulfill like a closed uh like a statistical distance to be closed that would also be possible the reason is that um Falcon wants to be more efficient and more Compact and sets the parameters that it like they don't claim or didn't plan to fulfill statistical distance because in other places they already use the ren diverence so this is not you to use the ren Divergence here um and they already set parameters that they don't fulfill the statistical distance but only a Divergence yeah you're talking about the number of queries is I like the number that's actually the number of qu to the hash function is the number of like signatures you're generating exctly yeah so like yeah so in the proof like I I want to change these two distribution so it depends on like how often I have to change them and this will be either like random Oracle queries or yeah signature queries right yeah so how should I think of this statistical distance is like non negligible any Divergence maybe it's small so what what does that tell me that is this secure or I mean like if if you show it like it to be secure with the r verion then it is fine yeah I mean it it depends on the concrete Bound in the end so you you lose for example something like one plus something small so I don't know if like the one plus something small leads to like a loss of two or four then you would lose one or or two bits so this will translate to like a concrete bit loss in the end okay so then um we program the random Oracle that is fine like depending on the gra that we'll see later so the next the next step is to U simulate the signing Oracle um so for the signing reset we just take the S1 and S2 um we programmed in the random Oracle since we all always like quer the random Oracle here we should have such an S1 S2 okay so what do we need to make this step go through so we need the pre-image sampler so this function we used before should be close um to a gan distribution why this S1 and S2 um we chose from aian distribution by programming the random Oracle so um these both distributions should be close as well and there again they're not statistically close but rain close and this was like based on this um file can set their parameters so this they considered already and this also has to been shown it depends a bit on the sampler but this uh this was uh was there already um but another question is um um is the image is short enough right because um if I if I get my pre-image which is like with respect to a gan distribution it can still land in the Tails and my problem here is um the Prat sampler is a probabilistic algorithm so in the original scheme it's not a problem if I have a PR that is too large because I just can repeat and Sample a new one but here I can't do that because I just have one pre-images from one pre-image for my C so I can just take that and I'm stuck in the in the simulation if I if I have to repeat um so it depends on like how probable it is and that I'm landing in the Tails or that I'm like small enough and the probability here that I'm landing in the tals um or here is it like differently but landing in the tals is two to the minus 14 which is quite High um at least too high for making the security argument going through so we need another solution and one possible solution would be to program the random Oracle not on Gan distribution for the later pre-images but on a conditional Gan conditioned on being small this would be a possible way but the problem is that the corer I show before does not work anymore so the cor we could only show for like an unconditional Gan and this is also a crucial Point like in the proof of the the corer so maybe this can be shown but um yeah not with the tools we developed there yeah would it seem like it shouldn't be possible to that way since you be like noticeably changing the distribution of the yeah so I'm I'm I'm not like 100% sure but this is what also would be my guess that it should rather not be possible yeah yeah but don't have like a like a like a proof to claim that actually didn't do that yeah okay and the other solution is what I told you before so changing the structure of the scheme so what does it help so if we also repeat by sampling a new salt we can solve this problem because um we get a new C here so we also can program a new pre-images for a new challenge so now we have the chance that eventually we get a preimage that's small enough okay so now we program uh we simulate the signing Oracle so sign plus uh um refers to the um proposed modification for Falcon and uh now we can simulate the signing Oracle without knowing secret key so we can apply our reduction so get um The Challenge Ag and then compute um a solution for for entes and yeah the fact that you Al that you put the r in there does that mean that you don't need to consider quite so many queries and like programming your because you you s of only need to program it on the RS you pict during [Music] sign potentially program the random even for other yeah okay I got it it's a good question so um like in the this proof in this like like boundaries occurs here I also needed to program it all all the other random Oracle queries because of the reduction now because the reduction now works in like finding a collision again so I have to take um the the forgery but also one possible query uh to the random Oracle because the forgery could be of like a random Oracle query which was not query to the signing Oracle um so for strong unforgeability um so either I have to do a guessing argument which you also do like hyper argument for that or I have to program all the random Oracle ques because I don't know on which one the adversar will Forge in the end if you don't care about strong for Ability yeah if you don't uh if you don't care about strong forgeability then you still need it um as we like I will also show the bound then but you still need to guess which query could be yeah yeah which random Oracle query could be used yeah it's not yeah okay so um right so we we we compute like our s S1 star S2 star from the forgery subtracted and get such a solution a solution that maps to zero and we can also see that our bound is sufficiently small because we have one beta from the uh from the winning condition of the adversary and one beater uh from from the smallness of the programmed um value so so it's a 2B okay so how does our security balance look then so um first the bound from the theorem i i i depicted in the in the overview so um there are much more terms but the most important terms are is uh is the the S advantage and we have our Ren losses here so we have a ren L from the uniformity result programming the random Oracle this is a Q times because I need the I I'm need to to to to be able to find a collision for any of the values and I have to um this pre-image sampling R diversion which is only applied in the signing Oracle so this is a q uh Qs times okay so and um yeah what does that mean for concrete like security so the problem here again is that the ren arguments on the Epsilon so um the Epsilon concretely for Falcon is set to this value which is respective to the signing with respective to the signing queries and the security parameter this is a very common choice and this is like choose like that um to support Qs queries and the security parameter of Lambda so if I um apply such an Epsilon get like my R results and apply this Q to the S times then um I lose yeah around a bit of secur or something small so for Qs this works but this means that it will fail for for the first term for the first term I have qh which is like quite larger like for for this 2 to the 96 so this term completely explodes so um if we use this uh strategy we we cannot show any security um that's why we also change our um so this was the bound from from before um that we also prove something else else um and this is reducing this term to Qs um so only program the random Oracle I think in the direction you mentioned only for the Qs values for the signing Oracle but then I still have to guess one additional query um on which I can do like my reduction in the end for the Collision proof so that's why I get like a tightness loss of qh here um right so this bound has like a tightness loss of qh and it also has a another disadvantage as youve seen before um so the CIS bound here is still too large so we have a bound of two Beta And if we plug this in like R let us estimator for that so what what what would be like the concrete bit security for this term um for the concrete parameters and for for Falcon 512 that's only 95 bits of security and for Falcon 1024 that's no security at all because the bound is is even larger than the modulus that's used so this can be Pro cont trivially okay so we also have another bound and this bound is only for unforgeability so what we do uh do here so we still have um these loss as before but we can reduce the bound to Only One beta which is also I think a common technique to yeah basic basically I mean this also reduced to Isis but like uh um to not be able to to to reduce to any queries that are like strong forgeries like like answering queries for which I also sorry do reductions for for for challenges that already also has been created to the signing Oracle okay um so then let's stick with this bound and there's one thing I ignored so far so in the beginning I told you that if we ruce the signing queries then we get better security and the question is why is this so also in the bound before I ignored one parameter and this is due to the repetitions so I don't only have Qs signing queries because of the of the of the loop I have like some upper bound constant times sign increase which is I think also inherent inherent from the from the construction so this number is not very large so concretely for for Falcon that's five or9 depending on the or why is it 5 or9 or 5 or9 to get like good security so make it like efficiently the loss sufficiently small um so 5 or9 might not sound very very large but as as as we've uh learned like the r arguments are very sensitive so if I even if I increase this by a factor of of U um of five or nine yeah this reduces security yeah why is it the maximum that's important versus like some I don't know up expected upper bound or you know some over all the quaries yeah so this we cut all also do so we could also just comp comp compute the sum of all them um the reason is um that it led to approximately the same like Security in the end um and that's why we chose to because it was easier to just choose an upper bound because it was a bit cleaner in the proof but uh it seems like it should say like cuz you say usually I expect it it's like one yeah one yeah the is true but I mean I still need uh I I still need all of the queries to fulfill like that they have to okay are you right not sure I have to check again but when we computed it it was like it led to approximate I mean it were like less like the overall was like less uh way less values true but it led to somehow the same loss but I'm not sure well yeah maybe I have to check that again it's a good point um right okay uh so what we doing um to compensate this loss is just to decrease the signing queries to achieve at least a better security and I mean this is a trade of like I think people should decide in the end what would make sense but at this how we can compensate this and yeah okay um so what about the final bit security so um like as an example for Target n level one and Falcon 512 we would analyze the bound as follows so um we get like an Isis advantage of 120 bits and for maximum number of signing c 2 to the 64 we also now have another leverage um so the Renu order we can also set and we can also optimize this Ren order this depends a bit on the bound so if you look at the bound the bound holds for every any order and you can just so this is not about like the parameters or something like this just to get tighter tighter bounds um but if the Qs is 2 to the 64 then we get such order and lose 10 bits per application um and we have to apply it for pre-image sampling and uniformity and um if we um allow only for 2 to uh 57 why 57 57 was uh um the largest value which gives only one bit of loss per application so here we get like yeah basically like the the tightest tightest security but with less aquaries and that's how we come to 118 bits of security um one one one remark is that this table ignores the qh loss we had like the tightness loss but which is also happening I think in in Practical applications a lot because it's like approv artifact and people for practical parameter sets usually ignore that um I mean from approval point of view like not not a good idea to ignore it but I think that's what for efficiency reasons happens happens a lot and if you see if we would apply it like this we cannot well we could uh yeah achieve any security we would lose like 96 bits again um right but there are some improvements where did the Q come from again the Q comes from the application of a hybrid argument um so I don't know which query um of the random oracles the adversary will use to Output of forgery in the end yeah right okay and just so like for for completion just as I said in the beginning it's like we get 256 for for normal unfor plain unforgeability for f 1024 okay then um also close to the end 3 minutes um uh some future Direction might might be interesting one thing is that the bit security I showed you on the last slide is computed with respect to the client sampler so this is like have to be a bit careful so the client sampler is not what is actually currently used in Falcon so this does not adapt to the concrete Falcon specification for the ffo sampler there's no analysis yet so this would be like an open thing like it should be expected to be in the same range but um yeah don't have proof for that so this would be a thing to um analyze the ffo sampler that's a sampler is actually used in Falcon um and PLU it into our proof so our proofs are generic so that they work the same but I have to compute the Bound in the end again so the bit security um then one could improve like the proof techniques for example the qh Plus for the qh plus this is uh not in in the in the work right now but we have an idea how to uh remove the qh loss as well to get like a tighter bound or remove it to uh to the move it to the U assumption to make the the claim a bit stronger um to actually ignore the qh loss and um another open question I think is a curon proof um so uh currently we only Pro things in the classical ROM and most of the things also live to the curum um for the r diversion is not so clear um so as I'm not an expert on the curum but as as far as I know or talk to people there are no arguments um to lift R arguments also to the curum like when I program something in the ROM or Q which is only R Clause not statistically Clause I think this would be also an interesting step to go um right okay to summarize um contributions are like like first modification H sorry sorry first form proof of the modified version of Falcon um for that we adapt some of the results from tpv to work with the r Divergence and optimize then the security bond to get get a concrete bit security for the client sampler not the ffo sampler so be bit careful about that and right so if you want to have more information like in the uh paper on ePrint or we can also talk about it if you're here yeah thank you and if you have any questions now also I mean I don't know how the time schedule is but I'm happy to we have yeah so how is the Falon team thinking about the modification yeah so they like I mean we only talked with with some of them but they were quite open to it because they they say it's like not like like like not a big modification in the sense that just like moving the salt in there um we also like open a discussion on the pqc Forum so other interested people might also be like at there but um so from one of the Au there and also one of the ERS we talked before about the results they were quite open to it but they also said but probably you're also more experts on I think they don't have lot of saying anymore because I think list has to decide what what is happening at this point uh um anything yeah no not that I know no yeah yeah but I think yeah it it makes sense so like I mean maybe it can also be proven to be secure like this but I think uh it's yeah it's just yeah in most cases change yeah exactly and just makes it potentially more secure any other questions online thank you much thank you