# Ring and Module LWE Stealth Address Protocol - Marija Mikić | 3327 / Attic42, University of Belgrade

- Channel: [ETH Belgrade Community](https://streameth.org/eth-belgrade-community)
- Date: 2024-10-07
- Duration: 26:52
- Topics: People & Blogs
- Watch: https://streameth.org/watch/yt-NX0bLzyNR1s
- YouTube: https://www.youtube.com/watch?v=NX0bLzyNR1s

## Transcript

[Applause] thank you thank [Applause] you okay uh as you already heard my name is Maria and uh I work in senior ZK researcher in team 327 uh which is part of atic 42 company and also I work as assistant professor at faculty of mathematics in Belgrade and U also I'm head of department for differential equation at the same faculty uh but also I'm co-founder of mathematical Academy and mathematical Academy is some kind of private school where we are working with talents in the field of mathematics physics and cryptography and for example this year our uh talents best of them obtain 41 medals on the state competition so we are very proud of them and uh for example last year with cooperation with atic 42 and ethereum Foundation we organized probably the first zero knowledge proof course on balcan so let's start uh today topic is ring and model learning with errors stealth address protocols so today we will talk about postquantum cryptography and of course private transactions so let's start first we will talk about private transactions you know that blockchains like zcash and Monero have some cryptographic methods at their core that enables privacy of transactions but there is a great need to introduce private transactions on the public blockchain such as ethereum so when we talk about privacy of transaction what we mean by that maybe we want to hide the amount of transaction but maybe we want to hide the recipient address maybe sender address but maybe we want to hide all three things together or maybe we just want to hide one of them okay and we can do it we can use different cryptographic methods for example we can use zero knowledge proofs like like zcash we can use ring signatures steal addresses like Monero or for example we can use fully homomorphic encryption and today we will talking about stealth addresses and with stealth addresses uh we want to achieve that we want to hide the recipient address so we want to have the same structure as we have today and uh we want to hide the recipient address in order to achieve this we want to this structure so we have the recipient Bob and we have Alice Alice will be sender so first Bob needs to generate some kind of stealth meta address and he will send this stealth meta address directly to Alice or he will add this stealth meta address D directly to some registry and after that Alice will find this uh stealth meta address of Bob she will perform some operation and after that she will calculate new address of Bob and she will send the money to this new address and after that Bob is able to control the assets from this address this is the general idea okay so when Bobs add felt meta address to this registry everyone can send the money to Bob's new address every time Bob's will generate new address steal stealth address okay and we can achieve this using different cryptog graphic methods the most know is dual the most know one is dual Key T address protocol which includes Dy Helman approach so in order to obtain the address sender and the recipient will calculate this address in a different manner they will use share key okay and uh also they they will use some other things but important here that uh we will have multiplication of scolar and point on elliptic curve and hash and we can achieve to obtain this uh using different cryptographic methods for example here we can use elliptic curve pairings in order to achieve this and uh these true Protocols are results of um work of my colleague Miko and me and we created two new protocols that using elliptic curve pairings one protocol using single key and the second one using dual key and we obtain really good implement ation result uh and those protocol above are really great protocols but they are not Quantum resistant protocols and if we want to have Quantum resistant protocols then we need to use different technique so we use ring learning with errors and model learning with erors technique in order to obtain stealth address protocol that are quantum resistant and these two protocols also created Miko and I and today we will talk about these protocols and in order to obtain post Quantum security we can also use fully homomorphic encryption and what was our motivation to do this well um we read the paper based Delta address protocol that was written by vitalic and Tony and they use defy Helman approach so they use dual Keys Del adds protocol and they already implemented some things like this contracts they use uh dual key Ste others protocol the cipti curve and also vew tag VI vew tag is here just for optimization reason but also we can see on top of this they wanted to have different schemes that using elliptic curve pairings and of course ltis Bay schemes so they want to have post Quantum schemes and this was our motivation okay so now uh in order to understand our protocols we need to explain the basic concepts so we will start with Matt but we will talk about only basic concepts so we won't hurt you at least not much so let's uh start with learning with errors but before this we need to go through technique Learning Without errors so we want to explain why we need to add errors uh you know that when you have your private key usually today you obtain your public key as a result of multiplication your private key with generator point on elliptic cve okay and when someone wants to calculate your private key and he's knowing your public key he needs to Sol discrete logarithm problem on elliptic curve and this problem cannot be solved in real time for our computers but quantum computers can solve this problem so in order to calculate public key from private key we need to use different technique if we want to have post Quantum security so let's start I think the best way to understand something it is to use this on example so we will start on example and uh here in this is this and example we have Mio and M has some secret vector and this secret Vector will be M private key okay in order to obtain public key from this private key Miko will multiply uh this public Matrix a with his private key so we can see here this is the first column of our Matrix a this will be the second column third fourth and this is the first coordinate of our secret key second third and four for so this result here will be the vector and this Vector will be publicy of M okay so it it is easy very but now if someone want to solve um um this problem and find the private key from the public key he needs to solve the system of linear equations and this equation will be here will be X here will be y Zed and T so we will obtain nine equations and four unknown variables okay but we know that there exist a solution of this system of linear equations and the solution will be private key so instead of considering this system of equations we can consider system of four equations so we can choose the first four equations and obtain this system and this is system this system is system of linear equations and I think that everyone here in the room know to to solve this system so we can use uh goian method of elimination or we can use gr rule okay so we can solve this and this algorithm is not secure because we can find Miko private key using Miko public key okay and because of that we need to add errors so now we want to explain technique learning with errors so let's start um we will have the same example as we had before and now in order to calculate Miko's public key using Miko private key we will multiply uh the Public Public Matrix a with private Vector this little s and then we will add errors so the left hand side is the same as we already had in the previous example and we will obtain this was the public key from the previous example and now we add some numbers and these numbers are errors and what are these errors so we will choose some numbers from some range here in the example we use numbers from the range from minus 5 to 5 okay and we choose random values and only M knows these values okay so if someone wants to calculate me a new public key this will be after we add these errors he needs to solve this system now we we have nine equations and four unnown variables so we will obtain this system here when we add errors and this system here probably does not have solution you can try I did not solve this but why because we have here N9 equation and four unov variables and if someone wants to calculate M private key using this public key of M he needs to um solve every system with every possibility so here uh we need to add uh Min - 5 -4 minus 3 and so on and every equation so we we'll have a lot of possibilities and we need to solve every system here so if we have a private key that has a lot of coordinates we will obtain uh so many possibilities that our computers cannot solve this problem but also quantum computers so this is the idea and uh in order to obtain even harder problem we can use modular arithmetics so here in order to calculate m publicy uh we will use modular arithmetics so we will divide this number 2,800 56 with number 89 and the remainer of this division will be 11 so if you are looking now this system and we obtain these values as Miko public key I think that you can agree that probably no one of you cannot solve this problem in real time so is idea and U we talk that we will use technique ring learning with errors and model learning with errors but we talk only about technique learning with errors so why we need to add rink because uh for example if we consider this problem this problem is problem that we already saw that when we are using technique learning with errors we have here in order to calculate one coordinate on M public we have scalar multiplication of one row of metrix and private key of M okay and we want to have some magical operation here to obtain cheap product operation so in order to obtain this we will use ring polinomial why because we can use fast Foria transformation in order to calculate this in fast way so because of optimization reason we will choose to work with ring of binomials so when we say that we are working with ring of polinomial that means that we are working with polinomial that has degree that is less uh than D and of course we will calculate coefficients modul Q so we have modular arithmetics and degree of polinomial will be less than D okay so here we'll be work um we we we we will work in this um space so let's start uh the first that we need to mention here is that um these techniques learning with errors learning with errors and model learning with errors are similar techniques because uh when we are um first we need to have this equality to hold and when we are using learning with errors we have this so we will not have polinomial but we will have system of equations but when we are using ring learning with erors Technique we will obtain polinomial but only one equation and we when we are using model learning with errors technique so we will have for example um columns and in this columns we will have polinomial so this will be the mix of that okay so we will have system and we will have polinomial okay and now in order to calculate some stuff we want to explain how we can um do addition and multiplication on polinomial ring so in this example I want just to show you how we calculate um the result of addition of polinomial F and Q so if we have that this is polinomial f and this is polinomial Q then we will obtain this using high school math yeah but now because uh we were working with modu of five this number here eight will be number three okay and this is easy and let's multiply them and we will obtain this result but here we can go back and see so we are working with ring of polinomial so when we have x to the degree D and add zero that results needs to be add one that result needs to be zero so here x to the 4th because fourth is n will be minus one so here we have minus one and this 8 because we calculate modulo 5 will be three so when we have x to the point to the power of 5 we will obtain X multiplied by x to the power of 4th and this is mean minus one and because of that we obtain minus 6 and sixth is one because we calculate using model of five so this is very simple and now we can explain our protocol so we want to have the same structure as we already had and uh we have recipient here Bob and we have sender here address and we already said that first thing that Bob needs to do he needs to generate some kind of Steal meta address okay so in order to do this uh Bob's uh needs to calculate his private key and in order to calculate public key he also needs to add errors so Bob needs to uh calculate private key and private key will be this little K and then he needs to calculate this errors he will choose these errors he will multiply this public uh when we talk about Ring of polinomial this will be will not be Matrix this will be polinomial so we will multiply polinomial with polinomial and add uh polinomial of Errors okay but coefficients in this polinomial will be very small numbers so we will calculate calculate this Public public key and add this key in this registry and this is this little V will be uh viewing key and viewing key is here just for if you for example have tax inspector and you want to prove to them uh to to your tax inspector that that you pay all taxes for all your transactions then you need to give him Ving key but if you don't need that then we don't need to use this key so and because of this we call uh this Keem dual key so okay after this we will add this in this registry and the sender will go to the registry and find this public key in the registry and after that he will generate um Alice will generate her pair of keys so in order to calculate uh her public key she needs to calculate uh public key in a way she will multiply public uh polinomial with uh her private polinomial and add polinomial of Errors okay and she will obtain this and this will be uh Alice publicy and she will put this public key in this Epal publicy registry okay in order to calculate the address of Bob what she needs to do she will multiply her a private polinomial private key with a public polinomial public key of Bob okay and we know that Bob will be calculate this share key in a different manner so he will multiply his private key with public key of Alis and this is technique Dy Helman but here we know that we add some errors so Bob only knows his errors and Alice only knows her errors so when we multiply these things we will not obtain the same result we will obtain the same result if we we are using dual key Ste address protocol without errors but with errors we will obtain different result and because of that we need to find a way that both of them obtain the same address and we can do two things the first thing that we have here on the slide uh we need to cut off the lower bits of every coefficient in order to calculate the same address so in order to calculate the same shared key and there is different way and we can use it to calculate uh that both calculate the same result but uh in order to do that we need to use some advancement and here we will use just cutting off lower bits and uh after calculating of the share key well uh this will be the public key of new address of Bob so Alice will mul multiply public polinomial with the shared polinomial and add public key of Bob in order to calculate address and then she will send the money to this new address and Bob will uh have private key for this new address and this private key will be result of addition of uh his private key for his uh stealth meta address and the share key and of course we know that we will obtain the public key as a result of multiplying this polinomial private key with public polinomial and add error so this will be the address of Bob and Bob knows private key uh for this address and we know that if someone wants to calculate private key from this uh public key well um if we choose that Bob's private key has a lot of coordinates he cannot do it even if he had quantum computer so it is safe we have uh we have secure protocol and in this uh Protocol no one cannot know that Bob except Alice that Bob uh received the money so this was the first protocol and the second one using model learning with error so we will have uh Columns of polinomial and how we uh do addition here well in the same way as we had using ring of polinomial but just in one row we are using technique that already used and in different row using the same technique so everything is similar and also multiplication here is the going on the same way as we already talk about so we will optain um second protocol that are using model learning with errors T address um and here we won't go to details because everything's look so similar and uh we just need to add some vectors in order to have same dimensions and nothing else can cannot be changed so in order to obtain this model learning with errors and why we are doing this because we can use some implementation result for this uh technique model learning with errors and and because of that we we are using uh this approach and for the end of this talk I want just to mention some things I want to mention that um fully homomorphic encryption the Holy Grail of cryptography are using this technique ring learning with errors so if you understand this you can work with fully homomorphic encryption and why fully homomorphic encryption is important because for example example you can perform some operation over encrypted data and obtain the encrypted data and whoever working on this uh does not need to have decryption key so your data are safe and only user can decrypt the data and if user perform the same operation he will obtain the same result as a result of decryption of this so it is very important to use fly homomorphic encryption when we have some sensitive data and you can think now how you can um you can use this our approach with ring learning vors and model learning with erors in order to create protocol that is stealth address protocol but using fully homomorphic encryption it is very easy and you can think about this and this is everything for today thank you [Applause] do we have any questions in the [Music] audience feel free to ask yes one [Music] second yeah thanks for the talk I hope that this isn't a stupid question but this um this um sta address protocol only works if if ethereum also supports something like dilithium and so it's not working with ecdsa or anything like that okay thank you so I just want to say there is no things as stupid questions like like like no one's GNA like think anything of you even if you ask something that's stupid like that's we're here to learn things so feel free to like ask questions ask the things that you don't understand that's how we're going to figure out things together without that being said any more questions oh my God there's 10 hands in the back whoa whoa whoa I'm just kidding um so feel free like like last call sold Maria thank you so much for an amazing talk and it was a pleasure as always to have you as a speaker give it up one more time for Maria