Renaud Dubois - Even faster P256 for onchain Passkeys and SGX

Transcript

so we're going to talk about sep 256 R1 which actually is the elliptic curve used in pasis and uh Intel onclave sgx so briefly uh our team uh we are four former uh Ledger Innovation we left and we just launched our company and our Mantra is that there is no web two or web 3 but just web and making the difference uh between uh between the two vanish is our is our purpose so we are currently focusing on supporting the p00 256 onchain uh we H the fastest implementation actually I think that the safe module use it um B Bas is working

on it um and some other actors uh we are also working on Ed 255 uh 19 uh for similar reason it's uh it's implemented uh in in fedo uh framework which we work on and we also have works on MPC Frameworks so among the team I'm Reno I'm a cryptographer um have been introduced so briefly what we did last year uh we ended up finalist at East Global New York with our invisible wallets so implemented pasy on Chen uh we were we were were rewarded for this open source implementation um by the rro prgf and

recently we've been granted by theum condition to continue work on ECC work and I will present some of our new results okay so briefly sep is is a nonnative to e serum but it's the most widely used elliptic for classical uh cryptography that we have in our daily lives so when we perform TLS uh TLS exchanges uh some of the passport so for instance Dutch passport use use this curve uh Intel uh Intel Enclave uh SSH and PAs Keys uh so we had two two talks uh referring to to it uh in in the morning thank to them uh it has been

specified by nist uh so as as I said it's not native it has to be emulated uh with evm instruction uh in order to to implement it for uh for a smart contract or smart smart account and being so widely used it's a natural conduct for ACC abstraction so we had this uh very good talk of by Evo about ACC obstruction so briefly uh what how is this invisible uh wallet uh constricted is by using acon subsection with with this curve so this means that we are able to verify uh the the pasy framework uh on chain so it means that using your

touch ID what you are in really doing is you unlock the access to the private key that is store in the secure CL uh of your smartphone which is is the most um secure um uh component of your of your smart it's actually a secure element um the and the related public key is uh is pushed uh to the US of RC 4337 as your signer and uh there is a little front that translates the transaction from uh from the pasy um uh pasy API to to the unchain um so this use has been

described by safe sooner and also uh we had this um this MPC MPC implementation over P so I will be fast um and there are also some proposal to um um so mainly it was written by Justin Dre uh on ethereum research it has been implemented by scroll and Tao and uh it happens that the TJX um which U which H to uh to to guarantee the Integrity of competion uh executed uh in The Enclave is secure also by by this curve uh it's actually live on scroll on Tao and uh actually they are not using your

computation but they they could save a lot of gas by by doing so so if there is someone connected to scroll with Tao uh I would like to to speak to to them so so last year um we we deliver the fastest this fastest implementation so we have two we had two results um so a straightforward result without uh without any additional uh deployment uh which cost 200 K gas and one we requiring uh to deploy an extra contract for each public key uh so this is expensive it's million 3 million gas uh but the the verification is very fast

down to 60k and if you compare to all the gas you have to spend when you perform a standard um uh ERC 4637 transaction uh you already have some something like around 2 to 300K so this makes this signature that was uh overwhelming before um no it's it's not that expensive related to to the smart smart acut uh implementation so depending on the use we provided these two implementation uh improving by a large Factor PR PR PR ones uh and everything is described uh on the paper uh written

written here and you have a link to to the repo implementing GS um so what we did uh since then uh we we make things better uh so we make it even faster without without pre precomputation dropping from 200k to 160 uh only requireing a few amount of extra um uh extra C data uh meaning that it's not fully compatible with the RP 7 to2 but another very important point that we we implemented is that we make this uh computation generic because today we have we are talking about the

256 but there are so many curves and many use case uh that could benefit to have a generic um generic scalar scalar multiplication meaning uh there are for example other ecosystem as cosmos is using the Ed 255 there is a cur stet there is a framework Pala Vesta uh actually the the G1 group uh of the BN curve uh could also be uh be fastened by uh uh by such um by such mechanism um so genericity is also a very important uh property so this is a list of proposal of of eips to to make

Evolution uh to to the term protocol and uh we don't know if tomorrow another curve uh rise or pop for for some very convenient system we'll have to update and push again a new AP so um what we propose would be to to implement double scalar multiplication I will describe it later as as one extra EIP um so so I will try to give the Insight of how those pre computation works so we had presentation Yesterday by Laurence and Aran uh on elliptic curves uh I won't go into into deep details but give

gives the ID so basically what what you do when you do a standard uh scalar multiplication is an algorithm called double NAD which is the equivalent of square multiply no anyone knows about those here one okay not that much uh and uh what we what we do when we when we compute this elliptic scalar multiplication basically we only have two operation doubling and addition and what those implementation are performing is that uh instead of computing the double and add separately for each for each point when we do a double scalar multiplication so two multiplication at once uh we are able to

mutualize some some of the computations here what happens in blue are a double uh the number of doubles the addition are in orange and in red appears the precomputation so for instance the last line uh of the table uh figure uh the high amount of precomputation we have to perform with with this extra contract and so the two new implementation we are pushing are the two green lines um so one is still compliance with 7212 and uh a bit faster and the the EIP would like to to to push is the the the second the second green line so with this 512 extra bit of uh of data we are able to to have

a massive gain in in a gas cost so as I said basically ECC is easy you have points what you can do with them you can add them and you can double them okay uh so only thing is that the the scalar field is huge and there are lot a lot of points okay so basically uh what you perform when you want to do a double and AD so we don't have to know what eliptic curve is is for instance if I have an object and I can just hard or double hit uh the way double and hard per um uh works is that I will look at uh the

exponents and for each bit if there is a one I will double and had um the the the input value if if it's is a zero uh I will just double it so starting from p uh so from from the most uh significant bit I have a zero I double it and when I have a one so Computing the 5 p i double again I add p and this is 5p you you have the same example for computing seven times the value the value Q so starting from Q double and adding is 3 Q double and adding it's seven 7 Q the ID of the stro Shamir trick is to metalize the doubling

so you double you you perform only one one doubling and uh you um you will perform only uh one um one addition so now if I look at this some p+ Q I have one point of precomputation H and looking at each bit of exponent uh no if there is a one on both line uh I will double and add the point H uh if it's a zero it's only a doubling and if it's a zero one one of the line I will add p p or Q so so doing this uh we mutualize all the doubling and we keep

the same number of of addition so basically Str Shamir is nearly twice effective as um as performing two uh two scalar multiplication and for higher Dimension you can have more prec computations uh but this is the same um the same principle uh um so just a word about isogenes um because I guess some of you have heard about the Ed Ed curve someone knows about Ed 255 yeah for instance it's used in Cosmos it's used uh actually it's part of the fedo framework only ubis is implementing it uh and it

has a very interesting property that it's a schnor signatures are very more convenient to implement MPC uh MPC framework more efficiently and more securely uh because ecsi is very error prone there'll be devastating consequence lately on the Garo genos scheme so we we really hope that at some point uh we'll have a uh massive switch to to Z Ed cure but actually you can using the same uh exactly the same formula as before which is the veor Str representation of the 300 256 you can convert your uh art curves to the

various St presentation perform using uh uh this uh this um unified uh unified code the computation and then switch back to to the Ed uh Ed representation so this means that uh the quotes that we are pushing uh so adding just those isogenes uh uh enables us to implement the Ed curve so as a as a conclusion um uh so we implemented uh efficient uh and generic ECC progressive pre compile that means that we will deliver soon all the solid Cod code Associated to those results uh it will be released around

the 22 of April uh and it going to be audited which was not the case of the previous fcl and uh it add generic ECC capacities to the evm uh but I think it would be interesting to uh to push this uh as um as a herp uh currently there is a very interesting RP which is called MSM but I think that maybe if it has not been implemented it's because it's very complex because it had the genericity to the elliptic curves as well as U um unbounding the length of of input and its use is restricted to some ZK scheme

while double uh double scalar multiplication actually uh enables to implement most uh most of the classical uh authentication mechanism ecdsa EDSA cdsa Etc so uh mainly what what we will try to do is to find um to find allies in in L2 to push uh to push this to avoid to to switch from one RP to another when when we we need to switch curves and that concludes my [Applause] talk thank you very much uh H for your

presentation and we still have some minutes for some questions does anyone have a question here so no questions but but later if you come up like with an idea or doubt H know is like we be richb outside or through lincolin H thank you very much [Applause]