Perpetual encryption with Yevgeniy Dodis | a16z research

Transcript

so we're really uh glad to have you have Genny dois a professor from NYU uh just uh up the street from here uh visiting today um so yeah you have Genny uh extremely prolific cryptographer and a huge number of areas uh and has shown a good ability to jump in on you know previously on Randomness generation on secure messaging and encryption and now you have Genny has been saying he really wants to start researching blockchains uh so yeah really glad that we got him this Summer oh great thank you Joe and thank you for having me it's like uh I'm excited to have such a great vibrant group so close to nvu um so yeah so this is like my our so this is Joint work

with Daniel y this is our first Venture into something kind of related to blockchain uh but in particular so I'll tell you about Perpetual encryption of how to put a private blockchain on a public one so I'll start this motivation this is actually the thing that I will care most about uh your feedback and your comments uh usually I'm all about like jumping right away and like cryptography and schemes so there will be that towards the end of the talk but I would be curious to see if our understanding of the blockchain space kind of Mak sense so feel free to interrupt ask questions and so on so I'll have some some motivation from the hopefully blockchain space then I'll motivate the notion of this Perpetual

encryption particular that I will try to argue that F application we need a new type of encryption scheme and then uh hopefully towards the end we'll talk about schemes open problems listen uh I don't need to tell you that blockchains are great they took over the world uh they have all those cool things like smart contracts they decentralized and so on but the question we ask is like okay assume you are a small company I guess 16 Z deals with a lot of like startups or something like that and I don't know you just want to I don't know you like something about blockchain you like some promise or whatever and you want to deploy it uh in your system so what do we do right for you for the internal use so it's like some kind of private use within a company or something like that not necessarily of

interest to the outside world um so there are basically two options as far as I understand either you join some public permissions blockchain already built let's say you write some smart contract on ethereum or something like that and then use it for your application so the process well you know it's not that simple but it's kind of relatively simple people at ethereum did all this echosphere and all this hard work of building consensus protocols and things like that um so it's doable but uh at least most of the public blockchains they they built without privacy in mind so everybody will know about your balances or whatever things like that if they need to so that might be undesirable alternative you will build this is really what you need is

some kind of private permission blockchain for your own companies like only for employees or something like that uh with some kind of application uh but maybe you will just build your own blockchain you read some cool papers and I don't know uh build your own thing but that seems so the pro you will get your privacy and also this permission thing and you don't you don't want like any random people inside maybe your particular blockchain but this is complicated like building a blockchain which like CRS you need like servers right so this is so we'll try to get the best of both wells in some sense we'll okay what if we can create a blockchain which is well on the other hand it will be relatively simple maybe it will leverage an existing public blockchain in fact maybe the public blockchain specifically they don't have maybe

enough of their own use they will just rent out the consensus protocol for other people so you don't need to to do to solve this hard problem uh but it will be private by novel design and most specifically the goal of this thing is uh you know not that I'm anti snark I'm very supportive of this thing but someh who to say that I would like to put some kind of encryption so more generally light and efficient cryptography without something super complicated on top of the public blockchain right so this is uh what we kind of do so basically our goal will be a little bit opposite uh of uh the current Trend currently try to build you know take everything off the main public chain and here it's like it maybe different scenarios there is a

public chain it has a lot of capacity somebody built a good one but maybe not enough customers so they rent out the public chain to like smaller companies or something like that and smaller companies will share this one public blockchain to their uses uh so let's see how it will look right so imagine there is this big public blockchain and some you have this group of people over here this sesm Street characters who want their own kind of chat or whatever something like that there will be a lot of transactions most of them will not be for your chain but this red ones will be for your sub blockchain right and the way it will look like uh you know just because you know you don't want to scan the whole thing each transaction on your thing will kind of maybe point to the

previous transaction and so on and then maybe this is like genesis block or something like that so this is how uh it will look so people and this red transactions will be encrypted in some sense so they will post this encrypted transaction on a public chain uh the good news you don't need to solve this consensus somebody did it for you so that's great uh you don't need to assume honest majority you just assume somebody solved uh you know the public blockchain problem and I mean doesn't matter what application could be messaging but let's say if you have like your own thing maybe people inside uh your little blockchain will keep track of balances or whatever um so yeah so this is how it will look so let's try to do the first attempt so the first attempt to do it would be just to distribute a fixed key

to all the members of the group so only people in your group will know the key and then uh you know roughly speaking Whenever there is a transaction let's call it Mi I it can encode balances or whatever you want in inside those things and you will basically encrypt under this K you will put you will append to the existing Ledger the transaction the transaction will tell you whatever you need inside your application but it will also tell you the pointer to the previous one right so it's like you can efficiently navigate your your chain kind of backwards right so does it make sense so this will be like a toy high level idea we'll see what's wrong with this idea and some who eventually get to Perpetual encryption okay so um all right so this is uh uh the thing so what are the good things so because somebody

Sol consensus on the public blockchain basically you have this unique linear order on the public one implicit we will get unique well we'll revisit it but you you will get this consensus for the members of the group you will have consensus inside your private blockchain uh and to The Outsiders what we care about we really don't want people to know how many transactions I might think it's like none of their business so I really would like them to uh this Cipher TI should look like random strings if it's not for you if you're not a member of the stream you know group it will be just random yeah in your previous example so are you also want to consider some internal part is revealing the messages in the plane yeah it will be it will be it will some of this external

functionality will be possible for now I will only want this thing for now we will talk a vanilla thing it will be possible by simple extensions of our scheme but for now the vanilla thing I want people to join and leave um this group and that's why we'll see the fixed key will not be appropriate but for now let's say um you should be able one member should be able to invite another member no I'm asking whether some internal party can reveal the messages that are already encrypted yeah in the plane uh for now no let's say for now very basic thing right as I said it's like a new space so if people like it if it takes off you know I am you know I'm sure there will be gazillion of extensions about things very vanilla thing right let's let's focus on vanilla

thing just to support this Dynamic group of people who can join this private blockchain so if you're a member you will get consensus and you will understand things and you have a consistent view all the members will have a consistent View All The Outsiders will have no clue what is what is happening okay so there are some challenges and I'm actually the next few slides we go through this challenges one by one but so I'll just mention the words and then we'll go systematically over these challenges you know like how to Prevail double spending if we talk about transactions and things like that how to prevent related question how to prevent Forks uh and he will be very different about distinction between fing existing parties that will be easy to solve and harder much harder problem will be about newly joining parties how

to prevent Forks access control with turnout will be easy uh you know gu of group management how can you add and delete members uh to this who have access and uh the hardest part really in this whole uh kind of thing will be how to do it with metadata metadata not just the transaction privacy that's easy to incre but some this coordination thing what period it is what is Operation and things like that we will really want to protect this metadata privacy and that will be the hardest part of it all yeah how much metadata like are you trying to hide the existence of this private blockchain or are you trying to hide the number of blocks and the when they get published so on a technical level I mean you can tell me what it implies on a technical level if you're not a member

of the group you know and there is something so basically if you're not a member of any group or you member of like three groups you just monitor scan the public blockchain there is a transaction you'll say is it for group one no for group two no for group three no otherwise it's a random string for you that's all you know so this is a concrete nothing else not it's like you're oh this is for these things that I'm not a member and this is 17th transaction nothing it will be very strong like as strong as possible and so let's try to go this will be very basic so it's kind of you you you see that I'm no waste to this things I will go through some very basic things in that just to make sure that uh you guys see that uh we are not totally crazy so

let's just try to start with how people solve various problems on public blockchain versus and'll see how to adapt it to our setting so double spending usually let's say this Cookie Monster has 100 cookies maybe it at all the cookies but now it tries to give 50 cookies to Oscar so well how do you do it in a public blockchain everything is public everybody keeps track of balances some who people will complain I mean everybody knows all the balances so it's easy so here we're not going to reinvent the wheel so I want to be very particular in that when I say about private blockchain inside the blockchain for now the members will know what is happening it's just they want to protect it from the outside well so we don't need like uh you know what zcash does or

whatever so here basically the way we'll do it we will adapt it to saying everybody inside the group right the authorized users they will keep track of balances so it's not going to be possible so here nothing really hard is happening we are doing the same thing we just adapted to inside the group but now but if you think so with each of those things it will be something obvious but then we'll transl it into a requirement and then when we sum up the requirements I will argue that no encryption scheme support this environment you know requirements and we will have to build something new so One requirement is here the joining parties might also be efficiently you know if somebody opens them whatever they say uh you know invit them to join they should be able to somewhat efficiently deduct the balances

so in the current uh you know public blockchain thinks if you let's say you know only trust the consensus mechanis but you don't have this SL clients or whatever you basically need to spend the time proportional to the sign of your chain so here we will be okay with solution which is proportional to the size of your private chain but of course this could be much smaller than the public chain so maybe you can scan public blockchain but it would be really uh one cool thing you'll do we'll actually achieve this as opposed to if you join you know scanning the entire public chain which will have gazillion of channels not related to you so we would like to be only efficient in the current in in your chain yeah are you actually preventing double spending as opposed to detecting it well I mean it's

uh it will be the same thing right it's like uh uh so okay so you there is like a subtle thing so on a public chain because Min a lot of people post transactions if somebody posts an invalid transaction that's actually a subtle point it will still go on the public blockchain it's just internally for people in the group I mean I will see how they will kind of pretend it doesn't exist from that perspective it's like a garbage uh kind of transaction so but so inside of them I don't know if you call it prevent or not but people will pretend that it doesn't exist but on the public one it will still appear as you know yeah I mean you and we don't know how this scheme Works yet but you could conceive of having zero knowledge proofs that the blocks are actually well

formed and don't have double spends and then the public blockchain would never accept them yeah so I would like I mean you can view it as a feature uh you know so I I I I view it as a positive we don't use any zero knowledge proof so I mean I view it as a positive I mean you know just tell you know you guys did amazing job with this but you know it's too complicated for me so we'll do something simpler uh so you can use a positive but also it's like yeah know thing public blockchain doesn't know people who run these things they don't need to like be like orbiters or what who post sure people can PST maybe garbage but maybe there will be some gas or something span so if you put a lot of things you just waste money for no

reason but yeah there will be nothing like that public blockchain doesn't doesn't know about anything well yeah I mean I think and he'll use no zero no proof yeah that makes sense that you know maybe it's much simpler like it would there would be a benefit to being able to prove the right blocks posted were correct cuz then it would it would simplify life for all your clients a lot because they wouldn't have to like detect double spending ignore they could just accept anything that makes it to the public blockchain has been kind of pre-checked for double spending yeah but I said double spending now I think it's trival problem anyway so I'm saying whatever solution you want so our architecture will be friendly to this thing if you want your message Mi I includes zero knowledge proof show so

basically right now think about it whatever you can do on a public thing we'll see how can they adopt it so if the public chain supports what Joe says I think we'll be able to support it also so in particular but we don't have to yeah so um so but yeah so one thing that we will do is like we will we will want for new members to only spend time proportional to the you know to their kind of chain as opposed to the whole public thing so that's a subtle thing all right this is like the really hard to it this is like one of the bigger challenges about Forks so on a public blockchain right so this gives all the cookies to Elmo so now this other guy whose name I forgot uh knows that this guy doesn't have any cookies right but

now imagine you try to do a fork on a Carl thing and there is like a completely unrelated transaction over here but the point is like this verifier on this Fork doesn't know that this guy spent all the cookies so that's kind of undesirable right it creates this inconsistent view of the world so how do you solve it on existing things that's of course the whole thing of consensus protocols you like longest chain like proof of stake all those kind of complicated things right that's what uh uh you know you need a consensus protocol I thing and I thing the point is somebody already solve consensus protocol but so how does this problem appear so this is an important few few slides just to kind of see how we envision dealing with forks so for existing members relatively so this is

Elmo some could let's say inductively there is a valid transaction a it's posted somewhere on the public blockchain Elmo is happy and Elmo keeps track existing member always keeps track to the last valid transaction in the thing then the time passes by there are all this garbage not garbage but transactions for other things that some El ignore them says not for me not for me not for me now there is a transactions that he can decrypt right but this transaction that he can decrypt will also point to supposedly a previous transaction the current thing right will have this pointer so El says oh the pointer match I can decrypt I mean maybe do the ver I mean if the verification whatever some I mean outside of our application if something doesn't match internally inside the message you can

possibly reject but here in terms of let's say assume the message is a valid you check the pointers and he says oh it's a valid transaction I move forward and now I remember the address of the next valid transaction then time goes on there is another valid transaction the pointer match you know the green pointer matches a black pointer is good now somebody tries to uh put in valid transaction right so let's say it's possibly a member of the group so this transaction actually decrypts but you know the transaction cheats maybe you try to create a fork C Prime so this is like a logical fork and this is how you would look on our public blockchain right so this post a different thing so for Elma it's not a problem so uh to Jo question the public transaction will you

know the public chain doesn't know it still goes on the public chain this C Prime but Elma ignores it because the pointers don't match he was like it's like I don't know somebody's trying to cheat maybe you have a punishment mechanism maybe not but Elmo just ignores it right so this is an invalid transaction then uh this Cookie Monster or whatever the Oscar guy tries to put another valid transaction so you know it tries to extend the chain here but again Elmo says listen this points to C Prime I mean just ignore it and if there is finally a valid transaction D Elmo is happy and he updates his pointer here right so this is U okay so this is how we envision this fork for existing M and the cool thing you don't need to worry about you know longest chain or whatever the consensus is already solved on the

public chain so you just do like totally trivial Common Sense thing and and you're happy uh does it make sense because next thing will be a little bit trickier okay so the only question is the like the Fidelity of a blockchain is a little different so like C and C Prime could be in the same block right yeah yeah so here I mean it could be in the same block I'm just saying yeah it could be so so here you're right so here you can think they could be in the same block um for now I I ignore this I I don't think it makes a difference so you just assume there's an ordering within the block and then whoever get me I'm saying C Prime whatever they saying if C Prime takes multiple transactions that will include all the multiple transactions but whoever puts them

whoever is a minor who puts them they have to point to the previous block inside your current blockchain if they don't do it you ignore it right so if somebody tries to really create a logical chain for a new member which is what we get next they will try to put those things right for a new member right so my point is for existing members is basically easy right so this C Prime D Prime existing members will really ignore it but this this Fork is really meant this is my next slide uh you know so what about new members right so now I assume the Oscar is the one who put those C Prime D Prime for this uh Zoe okay for the new member and he invit Zoe maybe give the secret keys or something like that so he really created an alternative reality right so so he

doesn't want Zoe to know about C maybe he spent like million dollars inside C he doesn't want Zoe to know about it okay so what are zo's options right so this is like a where slightly tricky stuff begins so hopefully I'll I'll explain it right so he when he joins zo he doesn't tell you he says oh this D ignore it it's like garbage or whatever like like this is a last block in our transaction is D Prime in now in our Ledger is D Prime so what can Zoe do right I mean he gives maybe Zoe knows the Genesis block or whatever ever so what can Zoe do say okay it looks cool it points to C prime it like well okay let me go to C Prime it's like okay it's cool it points to B it looks fine it looks fine oh it points to the genes

block looks like a valid chain right so Zoe kind of has no no option to you know to do something right so it looks fine right basically the issue is just following pointers which we want to do for efficiency right for efficiency we just want to follow pointers um Zoe cannot really know about this C because to here Oscar says listen ignore it this C is like random transactions for some other chain right so she she has no chance right is it at least for now right is it clear that zo has no chance all right good but and now but it's even worse if you go back to the beginning now let's say when zo actually moves now to D now there is a next really valid transaction D from zo's perspective this

is inv valid transaction like it means like this is pointing to some garbage is like wait a second this is my last thing why am I doing this so it's actually kind of worse it's not like zo upon joining sees the wrong chain but when the right chain is extended zo ignores it right just like the honest members do so basically once you join the member you you give them alternative future the alternative future keeps growing yeah um so when there's this new transaction d right uh they could trace back to C and then Trace back to B and then they realize that c is before c Prime thank you that's exactly what happens next so good so let's uh let's see what happens snack so what can we do I mean it will be actually two slides from now but I'm I'm I'm going to answer your question

exactly so um so what is a naive solution so the naive solution is Zoe I mean if she knows the Genesis block because to her everything looks like that it seems but we will do something different it seems like one thing she can do she can like scan the entire public blockchain right when she does these things and she will kind of see exactly as you said that c is prime she she can detect it if she scans the entire thing right but our goal is not to scan an entire thing and just look at the pointers with just looking at the pointers for now it seems zo has no chance right that's what I'm going to talk next basically how can do so you right if you scan the entire including all those white transactions you can detect it but that's too slow it's

possible the good news it's possible but now it like means you need to trace the whole public blockchain right so how can we do better so who can help zoy right let's see let's look at options Outsiders cannot help because they cannot they know they don't know anything everything is p random Cipher Tex there is no data so Outsiders cannot hold Zoe so what about Zoe herself to the best of my knowledge I thought about using snarks or whatever I don't know even solution with snarks even I mean we will not use any snarks we will be like super simple in what we do I don't know how to do it because those white transactions are posted by different members how do you prove that I mean I don't know how to do it right so so right now I don't have a solution for

this would be cool if you have something yeah so so Justin tell me if uh there is some SN Mar based solution here I don't know so I guess Jo solution might work if some who you reject the original transactions at the origination yeah but this requires public blockchain to have ceration so maybe there is some way to do it yeah I mean the way to do it you would need the public blockchain to be verifying something about each block that was you could prove in zero knowledge that you're posting a block that is not a fork but yeah so maybe but it leaks presumably it would leak right because ideally I don't want even the public chain to know for which transaction this you know for which sub Channel it is conceivably with some limited privacy laws you can do it so we'll try to do something slightly

different so this is what we are going to do I mean let's see if uh you know tell me if this is crazy or not so this seems kind of hard but what about existing members right I told you for existing members it's easy to detect the forks because they we there from the beginning or something like that so can existing members help zo and how and the answer is yes so let's try to see how they can help so this is so this would be our kind of assumption in this new model for this work at each point we will assume that exist at least one honest member maybe online who like anyway you assume that this is like a useful Channel you know useful sub blockchain you're building a lot of people will maybe very you know monitor it and and do things like so you kind of

assumes that if somebody puts an alternative reality which is easy to detect by existing members at least one of them will be kind of maybe online and put some kind of complaints you know and they can post on a public blockchain with is a reasonable amount of time and before I mean you can say oh this is like crazy we don't want to trust anybody of course if you look at the existing you know blockchain they assume much much much more right they assume to build consensus mechanism you need like honest majority of people like this minor so here just need like one guy right uh to be there so if you like compare what we're going to say with like you build your own house thing it seems to me that this is you need to assume much much more right to build a

consensus but he will just assume you know kind of one Hest party so this is Elmo so Elmo is honest party let's see how Elmo can help Zoe he doesn't even know zo Zoe exists and that Zoe will be joining later but now there is this invalid transaction C Elmo detects it he was like oh I can decrypt something it's decryptable by my key but for whatever reason somebody is pointing to the future I wish I could remove it as Jo say from the public blockchain but I don't want to burden the public blockchain so what can I do he can put like within a reasonable time some complaint mechanism and among the proof inside the complaint he would actually say you know what hey it's for my channel I'm just putting this somebody's putting you know maybe in the block he will point the block but basically he will

put a complaint which points to the right last block right they will put a transaction very is a reasonable time and the same these things they will do for D like when you see invalid transaction and I mean there could be some I'm not solving it it's like how to you know you don't want like gazillion of people put this complaint so I mean this I leave outside the model for now but at least somebody some who will post a complaint so now let's look at the zoy so she joins here or whatever somebody El you know this guy Oscar told me this is the latest thing she says you know what let me hang on for a little bit and let me see if there is a complaint shortly by right somebody gave me some kind of state let me see if there is

some kind of complaint shortly after and if there is a complaint how do we resolve it and this is exactly what you're going to do but in a more you know without scanning the entire chain so how we're going to do we can say Okay so the green guy the Oscar gave me one reality G Oscar gave me over here you know and there is a complaint mechanism which points to this C so let me follow these complaints until we reach a common Block B right or something I mean possibly even to the beginning or something like that and now you can see which branch is earlier than the other so in this case you can see wait a second after the common block the C Prime happens afterwards right so this this the C Prime is you know this is a valid one so this is a valid complaint

okay you can put more information to disambiguated right so this is kind of the high level idea uh in the paper with don't really address that much the complaint mechanism and things like that but we'll more focus on the encryption part um you know what kind of encryption you need but um right so this is a point the point is for Elmo it's easy to detect Forks at the latest state so this is a high level idea but there is a complication right so this is idea how we but now if we want to say how we do it here is a more complex things so in this case it was pretty easy because C Prime was in the same Appo and C right it's like it was kind of altern future you know but what if it's like the real chain went much further a lot of members

joined and left so this Elmo already knows kind of the key for this period H maybe they already forgot the key for period C I don't know we'll see what we need right so now is it obvious for Elmo to still detect this C Prime right C Prime is like for many epochs ago maybe a year ago like maybe the the Oscar say oh this chain is like dormant for one year or something like that whatever right so it's it's kind of not obvious in particular here is a requirement the requirement is that Elma must be able to detect and thec messages even as a fork is of very old state right so Elma should be really able to detect you know this C Prime corresponding to B even though a lot of stuff happened in

between right so is it clear so this is like and you'll see it will be cryptographically challenging to do okay any questions so far okay uh last two challenges will be little bit easier to solve but uh uh but yeah if you guys this is like one of the half of the pro half of the difficulty of what we're going to achieve is here so if you guys uh uh right so jumping ahead when the group membership changes Keys change it's like non-trivial for Elma it's like we don't want Elma to keep all the keys for like a b c d e FG and and stuff like that we want like some compact state all right so group management will be much easier so I'll go through inqua the native solution uses a static key for encryption but of

course what do we want to remove members from the private blockchain right so for example maybe you know this uh whoever we removed Cookie Monster is like removed so in a current thing we will assume and as I said I'm open to other things we wanted to have something simple that works we will assume a semi-trusted group manager probably the person who started the group as we'll see it will be semi-trusted but basically we'll assume there is a group manager who handles additions and dels anyway you need some Access Control to the system so we'll assume it's like some manager of the company will control who has access to the blockchain so so this green guy Kermit is going to to help people get this key so some who whatever this key K Prime is we will

assume there is a dynamic group of people and this kmit will help um you know legitimate members get the new key right but the key in particular has to change because we don't want the Cookie Monster to even know what this transaction be for my chain after it's decrypted right so we'll need to solve it and but as I said that will be relatively simple so but what it translates to our requirement the encryption scheme must support key rotation right that's that's basically my point you cannot keep the fixed key because if people are deleted they should be like Outsiders right so you cannot use a static key that's all that's all I want to say all right and finally the Privacy thing we want the encryption scheme to hide transaction quents from Outsiders of the group and

in particular the metadata is also it's not just the message content like who send money to whom but even what is the period what is a group I don't want to to to hide to leak anything so so the transaction should R random to Outsiders members of other chain and even former members so for example here imagine there is another pink chain right so this is a pink chain membership and this is my blue chain membership right possibly not overlapping well but let's say non overlapping for now so people here Elmo who is part of this guy but is not member of the pink thing if he looks at the p transaction all Elma knows it's not for my thing it's not for the blue thing I have no idea if it's a random string I have no idea if it's nothing right um also if it looks at this two

and three he cannot tell is it for the same pink Channel or not you know there is no linkability thing and this should be also called even if Elma was member of the pink thing at one but removed in two and three right is it is it clear so this is kind of the notion of privacy that we will want so what translate to requirements the cipher text must not include any channel identifiers um you know basically your user experiences you get something on the Chain you're member of two channels of two two private whatever one or two you try for each of them if it fails that's all you know okay uh no Epoch numbers nothing because even Epoch numbers leak a lot of private information if somebody leaks that this is EPO 2 for some Channel they'll say

wait a second I mean I know that all those channels are for a while maybe somebody publish the Genesis blog you kind of know right so we don't want want any EPO numbers all right so this is a summary of challenging nothing new but basically these are the things from previous slides you can read them but this is exactly requirements for the encryption scheme from previous slides that members must be able to detect and decrypt Fork even for all states right Cipher Tex must not include any channel identifier you know nothing they should really look to the random and the keys should rotate we should be able to rotate keys so I claim that no encryption really solves it and this is a primitive that we call Perpetual encryption will abstract this primitive here so this is the introduction this is

like I was outside of my comfort domain so I'm slowly moving towards my comfort zone so if you guys didn't kill me so far it's it's a good sign but this is your chance before I move to my comfort zone so does it kind of make sense I don't know high level what we're talking about all right so let me slowly start moving to my comfort zone so what is this Perpetual encryption okay so again I'll try to be pictorial so it's an encryption scheme for dynamic group of parties there will be EPO numbers there will be a lot of like messages within the EPO that's group messaging EPO really like when something changes somebody joins the group leaves the group so something like that so this is like we call them EPO right so this is like how the group membership changes maybe these guys removed these two

people added or whatever right so this is so now if you look at the perspective of uh you know so this group manager remov the Cookie Monster so now uh yes so membership is done by the group manager by for now it's trusted but we'll talk towards the end how to reduce the trust in this group manager so we want post compromise security that even the Cookie Monster has no clue about this messages now he doesn't know it's for for the group or not this is informal but I was just saying we want this perpetuity so this is important when Cookie Monster joins here even he should be able to to detect messages for EPO one when he was in the group so this is like opposite of what you what is called forward secrecy so this is like internally incompatible by Design with forward secrecy because if Cookie

Monster is the one who is online when the fork is like created with one he should be able to detect it but also like for Oscar Outsider we want like really strong anonymity onid or remov party cannot tell which EPO a cipher text is encrypted it's much more it really has to be Cy you know PUD random but the epok number will be really the hardest part once you know we do the EPO number we get everything last but not least we want it to be efficient hopefully much much much faster than snark things but uh but we wanted to we want parties to have linear stat so it could be like million messages of my thing my stat should be like short I don't want to remember my million keys and do and also encryption decryption must be subline I don't want to say oh

was it foro one was it foro 2 what is foro 3 that's like too much right I want to be able to quickly see what's going on all right so this is a little bit so this is semiformal how it translates to security requirements uh of our thing so correctness is obvious there will be an evolved SE there will a sequence of keys K1 K2 K3 for different EPO right for now the group manager knows all the keys right and we want if the message is encrypted under Ki obviously the current EPO you know basically it just means that it's like if everything is fine there is a message for the current EPO everybody decrypts it that's good right so that's one property pseud Randomness even if the attacker knew all

the previous Keys encryption under the next key looks like PUD random right completely PUD random no EPO number nothing right so this is to the randomness and finally yes it's ensures Comm of transaction metadata it's like much stronger basically we get the strongest thing possible maybe unnecessary for application but we'll achieve it and perpetuity it's actually a little bit stronger than one I said it's like you really shouldn't be able to create a fork even if you know old keys for now this is like for perpetuity for users in the last five minutes of the talk I'll augment it even to the group manager but we'll get there for now it's like even if you know all the keys you can canot augment you know reality you cannot put like a fake Cipher text at at you know at some appoh

high such that if you tell oh zo current APP of his ey please decrypt it zoy kind of gets it but a future member you know doesn't decrypt the same thing as zoy right so this a little bit subtle to see right so this is uh kind of what it says it it ensures the functioning of the complaint mechanism and the important thing I'm not of course we definitely wanted for honestly generated Cipher Tex but you cannot even make up even if you know all the keys you cannot make up a fake CER test that Zoe thinks is cool but a future member who might be in a much later State doesn't get the same message as zo and therefore complain the keys are updating every Epoch even if the group doesn't change well I mean it's up to you even that's kind of

outside it's like whatever you want either you can do it like every day you will rotate Keys it's up to you or only when the group membership changes so inside the group members there will be some delivery mechanism which is kind of orthogonal uh to this thing it's like I'll point it on the next slide but but this is you can do either way whatever it's like is there a attack where a new user joins and they're given an old key so they can't find the that's ex what cor prevention is right so if you give the old key so you can always give I guess so you can always I mean there is an inevitable attack that you can give like a valid you know say Z the group is at EPO 20 you say oh the group is at EPO 5 but you give a valid thing five but

now this members kind of don't get any new messages they will't be able to get a single new message because you know and if somebody actually post six Prime if somebody tries to extend the moment somebody tries to extend this old five they will notice somebody will complain right and they will notice yeah so um but yeah it's uh I mean there could be a weakness of the model but yeah this is uh um I mean hopefully by the way there are a lot of lowlevel questions which will still need to be solved like this one it's just I'm kind of abstracting the things which hopefully justifies that you need at least this encryption scheme maybe you will need more properties but I hope this properties kind of make sense but yeah let me know if but yeah those are excellent questions it's like there could be some

can you repeat the Perpetual again how yeah so Perpetual I mean as I said hopefully I mean on the paper I think we might have even a stronger one I don't know it's like I'm just giving you the most interesting special case you cannot come up even if you know all keys you cannot come up with a cipher text and some appoh high such that using the key for appoh high you will decrypt it right but uh a future member you know using a future key KJ you don't get the same result as Zoe right so this is kind of in the paper we have both one directional both I mean we have like even stronger thing but this is I think enough of this blockchain application we have actually even stronger definition in the paper but right so this kind of all right so let's move forward so this

is intimidation slide I'm not I don't mean to go through it so there is one point of this intimidation slide is when we like wrote the paper the first time we kind of submitted in a little bit rushed form maybe didn't do enough thing and the comments we got on the paper it looks like people say oh my God it's like there is some mess going on I want to read your paper let me kill your paper by saying that somebody else solved it so basically instead of like saying oh why don't you use this it's like okay it's uh if you want me to use this tell me how it works they don't tell you how it works it's just how it's like it's solved by multicast it's Sol by this so basically they get this comments like well it doesn't work anyway so the point of this slide and if

you're interested I'm happy to expand on any point so yeah green things are kind of this unique things that our schem definitely well also this threed thing so so green thing usually means good things which is you see uh no other kind of I don't know this is in complete table but basically we want post compromise secrecy and right if you remove somebody they cannot get it we don't want forward secrecy by Design right it's like the inclusive we want Perpetual even that somebody joins that should be able to detect like double spending Forks right so this is by Design uh we want this perpetuity which is new and roster management right now I abstracted the green guy just gives a key and magically delivers keys to group members but this is like an orthogonal

problem for example using multicast encryption I we didn't we kind of sketched it I think it's easier to combine it like black box so I think roster management you can use you know something called multicast encryption but you can use other things so this is an orthogonal problem which we are not touching In Perpetual encryption we really concentrate on this properties that I told you right but but as I said it's just uh I mean but and I can see the review because like It's Tricky somebody proposes something new and it's like usually it's like there is a model and everybody writes a paper which like increments the model this is like a very different model so people say I don't like to read this different model that me just say it's related to something without thinking anyway so I think it's new but if uh if you think there is a

different solution let me know all right so let's talk about schems okay and we'll see uh in the level of ril so I'm getting closer and closer to my comp comfort zone so I survived the difficult part I hopefully survived let's try to build it let's start with naif attempt and slowly we try to build it so here is like the tldr I think our scheme will be you know pretty efficient maybe not as efficient as conceivable it's like it would be great to improve it and so on but like no zero knowledge Pro something but there will be a couple of Tricks so it will be efficient but not completely trivial that's kind of so let's see how to do it so let's start with a naive scheme that this is a manager and and actually you know this is a current group you sample a fresh key send it to

the members and this is orthogonal how you can use multia whatever it's like we're not solving the question how then the group membership changes you send the new thing so you send K2 to existing group members send K1 K2 to new members why do you need to send b because remember we want perpetuity so we want to be able to decrypt previous things right and so on so an encryption is just a standard encryption you just encrypt using Ki Z M Chan and you put uh you know maybe uh yeah so the cipher text you put the EPO number in the clear and the decryption here it's actually very easy because EPO is in the clear you just figure out you say oh this is for EPO 5 let me look A5 and decrypt right so obviously this is wrong on multiple levels let's see so what is the issue

first of all each party has to remember a key for every previous EPO so that's bad also the manager has to send linear size messages to new members they have to kind of tell all the keys right to new members and obviously the number is in the clear right so this uh obvious issues let's try to fix them one by does it make sense sry it's like yeah so we're Switching gears we're going a little bit onto technical things not super technical but let's try to improve efficiency right there is efficiency and uh meod you know privacy issues let's try to just fix efficiency and hopefully privacy comes for free so um the one thing and this is again another comment the only comment technical comment we got the first when submitted the paper you know there was one person who kind

of understood it that suggested this solution but unfortunately it doesn't work but let's see so there is this notion of delegatable prf where which basically allows you to compress so the way you will do it at the bottom there are this Appo keys this is the actual Keys K1 K2 and so on but they should are randomly derived from some kind of Master seed every time you apply this P random generator so if you know the key here you implicitly can quickly derive the key for the whole thing so at least if you want to store the whole prefix efficiently let's say this is a prefix if you want to store these four Keys efficiently you can just store the keys is a seat for V and then so at the very least this allows you oh sorry uh this allows you to uh you know this allows so

each prefix it's easy to see that for any prefix there will be a logarithmic cover there is like a logarithmic size kind of cover that covers all those keys so at least if you generate the KE to the randomly as a group manager you can compress the storage of each of all those keys so at least the storage is no longer linear all right and even decryption if you know the EPO number you will kind of right so this the solves the first two issues they solv the issues of uh linear size messages and linear right so they solv this first two issues which is good of course what about anonymity right so the EPO number is still in the clear right so the EPO number is still in the clear you can say okay you know what let me just not put it in the clear but the moment you don't

put it in the clear you have to do trial decryption you say okay great I have a compact storage of all my secret keys but I don't know I get like the cipher text try it for one try it for EP two so this as far as I can see doesn't work because I mean you basically if you do the storage and you solve um you the moment you do anonymity you kind of kill your efficiency right at least the native thing does it make sense I this is not our solution but I just wanted to to mention this are you not doing trial decryption anyway because there's other people operating on the same blockchain so every time you see a random string you have to try and decrypt it anyway because you don't know whether it belongs to you no no but but what mean

Tri decryption it's like yeah well I have to do a trial decryption I don't to do a constant sure so when I say trial decryption I don't want to do n trial decryptions where N is a number of epo yeah so let's say there are just concretely like there let's say there are 100 channels I mean you don't know but let's say there are 100 channels and within your channel there is like million EPO right so when I mean trial decryption if I'm member of One Channel I want to basically do one decryption as opposed to million decryption right I'm not talking about a 100 thing right so yeah if you're member of three channels you will have to do three trial decryptions if you're a member of three out of 100 new thing comes you do three trial decryptions what I don't want to

do if I'm a member of a channel which has million transaction and because I need to detect Forks sure I can do volunt decryption for my channels but also remember the whole complaint mechanism it's important that if somebody tries to double span to put alternative future if I'm an EPO a million and somebody put something in Epo 3 I should be be able to detect it at complain and in the na if scheme the only way to do it I will try to see okay that million doesn't work a million minus one doesn't work I'll have to go all the way back to three in the naive scheme right so we are not going to do it we'll do something much more efficient but I'm saying this particular way doesn't solve this problem right and in some sense this is the hardest really this flip putting Appo in the clear

great but anonymity is there removing it and trial decryption this is really the key tradeoff that we are trying to solve we want to get the best of those well both efficient decryption and anonymity you don't have any ideas about solving the other trial decryption problem because that's actually problem in blockchain a lot of companies are facing that's a great one yeah not not yet but uh yeah that's a great one yeah that's I think in some sense that's what started this thing and kind of pivoted for this this right now for independent channels it seems hard to compress it right because these channels were created without any coordination so some who it seems to require that group managers maybe talk or do some kind of coordination so I think that would be great I mean as I said if you like this thing it goes again is a thing everybody

puts things into this uh uh what is it called uh you know outside the chain I forgot how how they're called whatever the starware or whatever this thing we're doing Z op this things we are putting more things on the Chain but if you like these things I can Envision million of papers I mean probably not as influential but million of open questions like this but yeah it's a great one so this one we don't solve but we will solve this one within the right so is it clear what we'll solve we'll want to have both compact storage and still sublinear storage in decryption will satisfy the whole definition formally defined but really the hard part is sublinear storage sublinear decryption time metadata hiding in fact sud the randomness and here is the thing which is was a little bit surprising I saying you can view it

as a feature or as a as a bug right but any sufficiently advanced bug is indistinguishable from a feature I'll sell it as a feature no but uh so somehow the Primitive um this pre Perpetual encryption right it's like it's a private key things there is like a private group that storees things you would expect you need keys you need tools from private key cryptography symmetric key cryptography like encryption and so on some who we will use publicy encryption I don't know it's one of the great questions if it's required I would conjecture yes I don't have the proof but basically we will solve this thing using a public encryption almost not completely as a blackbox but uh we'll see and as a free bonus I'm going to define perpetual encryption only also as a public

primitive I don't need it for the blockchain application but you know because I need public encryption to solve it once I use public encryption I can make even the final skin pineal P view it as a bonus I don't need it for the current application but I'm actually going to build a publicy Perpetual encryption instead of the secret key right so that's one one great big open question our scheme is efficient more efficient than snarks but our goal is to yeah we will use public encryption so let me tell you a little bit of the syntax and but as I said I don't I'll try to minimize any formulas or whatever just so that there is like for now a trusted setup that generates a common reference string here is a manager's algorithm first it takes this common reference string and initialize its

initial Master State possibly some public parameters just for convenience and then it can update it from EPO 5 it can go to EPO 6 and in each EPO it generates a secret key and publicy for members and remember as I told you we don't need a public encryption but we'll just build a public encryption so for free kind of right and uh people in appoh high will know secret K and public K right and so but you know or you can give public key Guide to the people from the outside or something like that so users they basically there is an encryption scheme given a public key and the message you can produce a cipher text and given the secret key and the cipher text you can get the message right and for now just to simplify notation Let's ignore this public

parameters just to to make fewel letters so this is like a super simple Sy if you like ignore this kind of stuff which we technically need but conceptually this is a simplified syntax you know the manager just initializes a state and tells basically can incrementally produces next public key next secret key users at any point can encrypt and decrypt so this is like normal public key encryption right for now so uh but of course KCT jumping ahead it's important that this Cipher Tex C let's say produced at EPO 5 you can decrypt it not just with a secret key of epo 5 but secret key of epo 6 7 8 9 10 you know anything right anything in the future but not the past so any questions uh so there will be no formulas afterwards so

maybe a few of formulas all right so let's give the basic scheme okay so this is like the basic scheme okay so the basic scheme will be the following the manager generates for now let's not worry about efficiency of the manager we'll improve it towards later it will be easy well relatively easy imagine the manager produces the entire Keys the entire key of uh public key pairs right not secret key public keys and the EPO will correspond to the leaf right so the EPO will be at the leafes as usual so this is like the ual thing so let's look at the public key so the public key for EPO 3 will be basically all the public Keys including the leaf right so this is a public key that in order to encrypt foro 3 you need to know this

logarithmically many public keys for independent public encryption schemes an encryption is just uh so an encryption you don't encrypt the message just for the leave but you encrypt it for all the parents as well it's a quick question so you generate all the public use for all the future epics ahead of time yes so for now ahead of time so as I said for now think about this is like a bounded Ty scheme you know an upper bound I'll show you all these extensions will be possible for now I think there is a fixed upper bound on the number of epo I mean yeah that's valer already sees the future so the way I'm going to present I'll present like some toy scheme it will not work we'll fix it we'll fix it we'll fix it it will work but for now bounded number of Appo yeah I assume you

know a bounded number of AO and for now assume the group manager the setup is like really slow but we'll fix it this it's kind of the same as the old broadcast encryption stuff yeah it's all very related that's why so somehow it's like I wish I could do something better but that's what like when they go the comments literally nobody like looked at our paper we didn't really get like we got only one technical comment which was an alternative scheme which doesn't work and now I mean and this is completely ACC your go is different but the construction was yeah so there will be I mean all those things that are basically this three is used almost in everything ggm pandom function to pom generators broadcast encryption is similar so the is useful for multicast encryption almost everything uses a tree and that's why people was like it cannot be new

it's like it's uses a tree so everything using a tree has to be discovered earlier so I feel like we discovered one thing where the tree is used in a slightly different way but maybe not I don't know yet so but yeah at the end it's not as I say view it as a positive old idea but Details Matter but yeah it's like you know conceptually yeah we are going to use threes like broadcast encryption traitor tracing all those papers use threes in a different way so we also using crease yeah but but you're right it looks so similar that cannot be new but I I I couldn't find yeah what we have to worry about like an adversary does not encrypt M for every public key yeah absolutely well you're right you guys are too smart so as I said the way it's it's excellent like it's like it's

not even the first attack it's the second attack but yeah so what we going to do just to say I'm going to kind of try to um you know and that's why sometimes people hate when they take cryptography without uh you know other classes they here is like you start it's like like oh don't tell me the final scheme right away so you're right there will be a lot of issues and we will hopefully solve them incrementally uh but for now let's just solve kind of efficiency issue and just kind of get a high level idea and then slowly we'll we'll solve it good so the first thing is uh you know just think about correctness for now right I just want to solve this efficiency trade of between um the storage and the trial decryptions and then we'll talk talk about adversarial stuff to encrypt you

will just encrypt you know separately for each level good and um yeah so there will be those kind of Cipher text over here so the good news is the length of the Cypher Tex is a h so it's not it's not constant logarithmic but hopefully not too bad EPO number and important thing we don't include EPO number in the cipher Tex so technically we need an encryption to be anonymous so it it should hide the public so there is a notion of anonymous encryptions there many constructions so encryption public encryption scheme will will have to be anonymous so that's that's easy let's go to the secret key so this is a little bit new I haven't seen exactly this but it kind of makes sense so the way to do a secret key so if you at Tapo 7 you as before just like as GM you want to cover

secret keys from EPO 1 to 7 so this makes sense but one thing as I said just jumping ahead why we need public I mean there will be multiple reasons we need public encryption but it's important to encrypt to seven you have to encrypt all the nodes and nobody yet knows any of those secret keys so that's why we need this kind of a symmetry jumping head we need to be able to encrypt to this node without knowing the secret key for this node right to encrypt for seven you will have to do this so nobody knows secret keys for these guys yet right so this is critical place in our analysis or whatever um I think it's kind of essential but yeah drove us NS we couldn't prove that you need public cryptography we couldn't avoid it but anyway um uh wisely we didn't put it in

the submission you know because I don't know hopefully wisely because you know anyway but yeah that's an open question so this is so compactly um you know even though you know those keys are independent but compactly intuitively this guy kind of covers this right intuitively so how do you decrypt a cipher Tex so let's do it visually so you have a cipher text for aox 3 somebody encrypted an all Cipher text and you want to decrypt it so you kind of try it level by level you can say okay can I decrypt uh you know uh sorry this is this is like an honestly generated thing and I'm trying to decrypt it this7 so I will get intu if I use what is called trasto some kind of appropriate trast encryption scheme if I you know try to decrypt using this public key and Cipher text for this one

I should hopefully fail and we'll ensure it of course but yeah you can imagine in a normal encryption scheme if you I mean with a little bit of extra effort it's called robust encryption scheme if you try to decrypt the cipher Tex encrypting after public is 3 using completely independent Keys here you will fail okay you say great let's go one level up you get this guy right so this is the next part of the se you decrypt you get an error right and finally the reason intersection it's magical but it's by design of course right there is an intersection at level two it's both green and orange now both encryptor use this key and this guy stores this key right so he decrypts it and it succeeds right so this is a key this is a key I mean there will be many lower

level details we need to fix but this is a key trick to get our efficiency issue which is good because within an hour I told you a key trick and then the remaining time will solve little issues does it make sense I'll pause here right so that's why you kind of encrypt those things and then you decrypt you you partition the things so the key point is there will be success so the key point is by design it requires a little bit of proof but it's not very hard to see that for any J greater or equal than I there will be exactly one intersection point if I is equal to J the intersection point is uh uh you know the intersection point will be exactly here but otherwise it could go somewhere up the three right it will be exactly one intersection point but for the future jumping head

there will be no intersection point if somebody encrypts here like for eight no intersection right you know anything in the future there is no intersection and anything in the past there is prec precisely one intersection so it looks like we are done we done in terms of efficiency but unfortunately in cryptography we are kind of pesky people we like our schemes to be secure so unfortunately this thing is not yet secure but it's getting there okay so let's try to does it make sense so let me tell you the attack on this scheme and then we'll slowly start fixing it so so I'll pause here I mean this is really the key idea which I find cute I haven't seen exactly this kind of usage of trees but uh but it's true you know yeah okay so let's uh have the attack on

perpetuity so the attack is basically exactly as you said uh imagine that you just put a valid Cipher text in the bottom for Zoe you know joining later right for this yellow guy joining later and put garbage over here right so you just uh something like that so then looking at the Cookie Monster he like tries to decrypt I mean doesn't match doesn't match and obviously this also doesn't match because it's garbage thing so he will just think it's an invalid thing and he will ignore it right so Cookie Monster will ignore it but zoy who joins righted I mean this is like an inconsistent Cipher text you will just ignore this thing you'll say Okay garbage garbage garbage nothing matches it's not for my Channel or don't I don't know he doesn't know it's not if it's

for his channel because he only stores this orange keys right so everything is garbage but now look at poor zo she comes here Oscar gives his a secret key for three this Cypher text is valid so Zoe actually is happy right so she is Success so you fooled right so Zoe joined at thinking it's an epox 3 and the Cookie Monster doesn't protect it right and our whole point is a Cookie Monster or anybody in future EP should protect it right makees sense so it's so we do need to solve consistency right so let's try to solve consistency yes so she sucess decrypts so let's try to look at the options I'm going to give you three options where the third one works the first two so the first option you can say well let's make

cookie monster work hard and kind of try to decrypt this the problem is I don't know how to do it efficiently aside from storing all the keys and doing trial decryption right so this will be kind of not as far as I know I don't see how to do it efficiency yes it would be great if Cookie Monster does everything but uh I mean Jo so if you guys have an efficient snark solution maybe but we'll avoid it we'll do only lightweight stuff okay so the other option is to give Zoe more keys maybe we give Zoe some of those keys over here that she can detect right well of course that's not secure because if there is Zoe maybe is kicked out at this group you know at p 4 she shouldn't be able to decry this part right so I cannot give her the keys up

the three because it's not part right because zo should only know these two secret Keys she cannot know this right so I cannot give her this and that's where of course the public encryption is so the the the thing is Zoe must be able to some who reject this thing without decrypting it right right so and public primitive that's high level how public primitive will will solve it so let me show you how to solve it on the next slide okay so but yeah you can see why we kind of inherently need this public primitive anyway let me show you how you do it okay so this is our basic scheme right so in our basic schema just expanded it you encrypt and you use normal independent Randomness for each encryption so what we going to do we're going to not use independent Randomness

for each encryption but we'll use derive it in a random way how so this is how so let's watch this animations that you know my pooc made all right so first we're going we'll do it in two steps first let's you know in addition to the message n let's encrypt for now a random seed I mean that doesn't have it's like a useless seed you just instead of a message you encrypt a useless seed for now right okay so that's well of course that doesn't solve anything but now watch another thing this random Works becomes a p random generator okay so what you do at each level the first level whatever you just apply it to initial seed so you have the se but now the seed that you decrypted the first level will be used to deterministically derive the next seed and the next

Randomness so for those you know it's like we're kind of running a stream Cipher over here and then this seat is going to be used to deterministically compute this and this it is going to be used to deterministically compute that right so this is kind of non zero knowledge but this is kind of zero knowledge enough for exactly our purposes so let's try to see if it works right um I mean it's not clear why is the trick works I'll show you in a second but is a trick clear so instead of doing deterministic Randomness I will kind of compute pseud Randomness kind of saying that if you have access to this it's okay for you to kind of break this other Cipher text in some sense right because if you're already given the key for this it's okay for you to do this but not the other way around so let's

see how how zoy will detect it so she cre that Cipher Tex because she has this key now this is our previous attack this garbage Cipher Tex so now a point that Zoe will immediately know that something fishy is going on she decre this thing now she decb the seat and now she will try to say wait a second let me take the seat derive the randomness and let me check if I re encrypt the master Cham do I get this garbage and I'm not going to get this garbage so zo says wait a second I'm rejecting right away so even though zo is only given decryption key for the bottom as a sanity check she checks the consistency of Cipher Tex up the tree all right so now Zoe herself will reject the cipher Tex so the cooky monster cannot

do it he will reject it anyway but also Zoe will reject it so this is like a way without giving the secret key on a cyer text per Cipher text basis we give zo ability to check this Cipher text up the three so this check will fail and I think so and this achieves I mean this is maybe a little bit technical that achieve some we form consistency which is enough for application where we only say that it's impossible for Zoe to succeed and the Cookie Monster to reject we in the paper we show how to achieve an even stronger one but we don't need it for the blockchain application looks like we are done we solved your consistency issue not quite so we have to do two more steps so what's the problem with this schem so we kind of getting closer and closer to right

scheme uh so the problem is this kind of strong robustness so here is an attack on the robustness scheme so imagine you know there is zoy in this epox Rishi has the secret keys and Cookie Monster has this secret Keys kind of right the the purple secret Keys when they do the trial decryption let's say they do this trial decryption on the second level right so it's important remember the saer Tex could be malicious so it's conceivable that somebody who knows let's say all the keys can produce one you know Malicia Cipher text which kind of decs differently so implicitly when I said rasas before kind of implicitly I meant like honest trabas like if you just honestly decre produce CER TCH they will be decrypted but here remember

somebody we need this what is notion of strong robustness so weak robustness so normal robust for encryption scheme if you just encrypt honestly kind of you will detect if you encrypt under two different Keys the second one will not decrypt but here we need it even against it's the malicious you know maliciously generated Cipher text right so we want to make sure that it's impossible to produce a single Cipher text sorry a single Cipher text such that when Cookie Monster tries it and Zoe tries it with honestly generated keys they will get both valid answers right makes sense sorry it's it's like it's it's almost the last technical kind of thing there is just one more um and so here is a trick implicitly in a slightly different Conant it's in the previous paper we

discovered it independently but we happy to attribute it to them so here is what you do so previously remember we just encryp the message and the seat here is what we do we're going to also as part of the certic we're going to do a commitment to the EPO number we're going to commit to EPO 5 just one more component of the suff and this is decommitment information Z so we're just going to incre the de commitment at every level right we're just going to do this commitment at every level and now if you look at this Cookie Monster maybe there is a malitia suffer text maybe will decrypt here but once you get the Z and compare it with a commitment you will see that this is not on the pass three is not on the pass you know um you know this number three that will be here

so in order for Zo to encrypt this Z has to decommit to three to this EP number right because zo will only accept if uh you know the this is like for epox 3 right and uh this Cookie Monster will reject it even though it decrypts but the decommitment doesn't match so this is like almost the last technical fix uh uh for this thing is just how to achieve the stronger bance because we care about maliciously generated side and again our goal for the whole thing is to avoid like zero knowledge snarks kind of lightweight stuff right so we are trying to use only light weight stuff good we are almost there uh unfortunately still okay sorry it is secure so now this is secure but only for what is known as

chosen PL security which just means encryptions of anything is like sud random but thater doesn't have U things so for this application it's probably not enough for blockchains we want like some kind of normal liability or whatever more specifically we want chosen Cipher tech security so now the question is can we do chosen Cipher tech security with this basic scheme let me put the scheme before and of course the first thing that comes up you can say Okay use nonm valuable commitment whatever and use chosen Cipher T secure encryption instead of chosen PL t let's use Chen Cipher text right so that's a trivial fix unfortunately this fix doesn't work here is an attack so for those you who don't remember chosen Cipher text security means you get a challenge Cipher text and you allow to decryption for any different Cipher text

anything else and it shouldn't help you so here here is a challenge cerx commitment C1 C2 C3 C4 so here is what you can do you can just uh you know replace this by garbage and ask Cookie Monster to right in this thing you can choose any party who can C you can say I take this challeng Cipher text but I can ask a future party who is Cookie Monster and the Cookie Monster will only be able to decrypt this component and we'll have no clue that I change this component right so basically if you just encrypt independently those components are not tied together so you can just replace one and right so what do we do the idea is to include a hash chain of the cipher text so there is like another something very efficient there is like something called you know just you Hash Hash Hash

so the way you build you know you hash along me message you just hash it one by one so basically this is a pseudo code Sor like roughly speaking you right we had three components previously message the SE and this commit DEC commitment thing but we also include the current kind of hash chain the details you know so basically you just can use this hash chain where you have the previous thing with the next Cipher Tex you commit kind of to all the cipher ttic and with this thing uh so the high level idea is now let's look at this attack right so he will decrypt this C3 it will give him a hash chain but the hash chain commits to the previous Cipher text right so basically uh he can recompute H3 because H3 is just deterministic hash chain uh

you know starting with a commitment it it basically it just recomputes the hash and seees that the hash doesn't match and he will refuse to decrypt so again it's a cute little uh you know sorry I don't expect everybody to follow but it's like very simple the point is is just include an extra hash so once again like if people are looking let me just see so the tag was that Cookie Monster can only decrease his3 component how does he notice that we change this component right to random and therefore CH break CH and cyber security well the Cookie Monster will figure out the hash chain this value H3 he can recompute the hash chain up to H3 and check it so if this thing change you know in the challenge in order because C3 is CCA secure you cannot play with H3 you have

to include on H3 if you change this the hash chain will will will not validate so so basically by making this the the encryption scheme individual encryption scheme CCA secure and using the hash chain we solve everything so now we are it is secure okay so we in good chance but it's only only Outsider secure okay so so this is and I said so my goal is like kind of give you the tldr we try to have a problem hopefully it kind of makes sense we want it to build it to solve it in a strong way um and the thing is it wasn't completely trival but there are this little tricks which are cheaper than I think zero knowledge proofs which I think works and and hopefully solves this whole problem so

let me tell you this is literally the last thing it's like uh what does it mean Outsider security so far they assume that the group manager is onest so in particular we implicitly assume that all those keys that the Cookie Monster get or whatever they're all consistent there is like no right so the key Evolution so the kit gives people consistent keys so the question is what can be done against the malicious manager if the manager is like not trusted or something like that well obviously they can add and remove people at will they cannot protect this confidentiality well they're not never going to exclude the group managers and all the keys in advance that seems kind of impossible but what is possible is perpetuity right so namely what we would like to do is that even a malicious

group manager cannot some who has to commit to everything in a way that even if he colludes with everywh he's the attacker you know he cannot cause you know the Cookie Monster not spot you know basically the perpetuity property that if you decrypt a future thing sorry if you can decrypt in the past you have to decrypt in the future so this we can protect and this is what we're going to do and this is a high level idea literally promise you this is the last technical idea how to achieve the strong security is um basically the group manager for now will commit to the entire thing using a miracle tree so roughly speaking inductively you will you know kind of having inductively

Computing the hash of left and right you will kind of compute the hash of the node to be the hash of left right and the current public key so you basically do a miracle tree which commits to all the public keys right and that you publish the root you will publish in public parameters which you for now you will publish it in the Genesis Block it's a bounded number of periods for now right so you will kind of do it and for secret key generation is a minor thing instead of giving people the secret key you'll give them the randomness to generate this public secret key you produce this public and you check if the public kind of matches um so basically using Miracle trees you force a group manager to commit to consistent keys and when you kind of uh open it for people

right when you give people their corresponding Keys you can easily prove kind of membership so people know that the group manager cannot lie and once the keys are consistent um uh it kind of works there is like one problem and not pro well there are two problems with this okay so one problem which is actually a great open problem like it's like there are two problems that drives us drove us nuts in this project so far it seems like you can use almost any public encryption scheme possibly with Anonymous Cipher text but for this thing to work we need a little bit it's a little bit subtle but we need like a strong correctness assumption and to the best of our knowledge lce schemes don't satisfy this assumption so we don't know how to actually instantiate Perpetual encryption from latest assumptions uh

for for Insider security so for Insider security we currently don't know because yeah as I said for the group manager not to choose there is like a subtle kind of properties that because of the noise you know I think I'm sure it's solvable I just don't know maybe enough letters based crypter to solve it but that's yet another open question I'm so it's like it's you know the the openness of postquantum is for a very unusual reason it's like we need like a very strong correctness and the other thing is like um it half solves SAS question um it's like you know um how can you know we we want like the group manager to give you this kind of openings like incrementally without storing the whole tree and there is like this cool sequence of crypto

Euro papers which people don't really know how to do this Merle tree traversal how can you commit to a Merle Tre and always be like logarithmic size instead of storing this linear thing so we can do it using these things it's like a pretty cool thing so we we can use meral three reversal to do this uh thing somewhat efficiently and but the the final thing which the current thing doesn't solve is it's still bounded number of epics even with bounded number of epics we can make the the group manager kind of efficient start with logarithmic State and slowly add keys and slowly keep constant state but it still has to be kind of for now priori bounded so uh if you want an unbounded solution basically unfortunately we need to use a hierarchical identity based encryption

never mind what it is here so so just to to to to check so for Outsider security we can just make the height of the tree like security parameter we don't need the strong correctness everything kind of works so we'll just do Merle threee Travers it for depths like 100 and to 100 is a good upper Bound for this Insider security um yeah unfortunately because you need to like compute the the mer root hash we don't know how to do it well we know how to do it more efficient than niix than snarks but not efficient in my opinion for practice using hierarchical identity based encryption so maybe go to Ping well or something like that yes so we have some um things in the padding all right so uh that's my uh next to last

slide uh we okay so what is open problem so these are like big high level open problems just kind of more applications now that you have one public chain and many private chains can they talk to each other right or something like that can you do transactions between private chains you kind of open some not the other I don't know it's like that unfortunately seems to go into the snarks that I'm trying to avoid uh a lot but I don't know maybe you can do something else um maybe also transactions in and onto the chains possibly from the outside um kind of unclear for Perpetual encryption as I said there is a super annoying technical reason why currently we don't have postquantum candidates is uh just because of this Insider with have a

strong correctness requirement uh Mo efficient scheme we we feel like the scheme's are nice but in practice I guess doing even I don't know like 2030 encryption maybe people will not like such big packets right so it would be nice and especially for Insider security where we need like you know H hierarchal DTI based encryption to me is that the most thing that for symmetric if if I only want symmetric Perpetual encryption can I actually build it without public encryption even the weakest kind of thing I conjecture the answer is no but I don't have the proof it's it's one of those like to me it's one of those surprising thing which looks like a symmetric key primitive but some who requires public techniques but I don't know uh exactly how to prove it and obviously yeah if you find it I mean the secret is

is work came up from kind of secure messaging thing we kind of had some scheme and then some we were looking like in jard for application and this blockchain came in the application so it's not like I was like a blockchain guy and I was like thinking about it something came up in a different domain and we just applied it here um so I don't know maybe there are some other applications um all right um I'll stop here does the like group action based pke does it satisfy the strong correctness requirement to be honest we didn't check so you mean like group action um uh like isogen bogy base uh I don't know enough about isogenes um I would consider yes there

is no noise in logus right here we need um it's there is like a technical definition of correctness that we need in the paper I would conjecture yes but we didn't check I don't know how practical those schemes are but um yeah it's a good thing to check I don't know good good question yeah I guess actually good so if okay his answer is yes I guess that would be postquantum so yeah we should definitely check or I guess if yeah I can look up we can check I guess uh you know at lunch whatever the the actual definition of correctness we use it's a little bit subtle it's like one of those things you write proofs and you see exactly what doesn't work so kind of go back to definition change it but it looks a prior okay it's like everything is generic with minor thing but then

it's like oh let's do it in LW and I'm glad we checked I like wait a second something doesn't really work why can't you just put the last Epoch key in the current block last EPO key in the current block you can uh how will it solve it I mean if you because alternative history could be be like an EPO 500 alternative history could be an EPO 3 so you go you register I give you key 500 I point you at some block you don't know whether it's part of a fork yet or not I see and you get the previous key yeah and you get the previous key in that block so then you go back and then you get the previous key again so you have that will solve at least partially there could be some subtlety that will solve the issue so

this is kind of an issue of multicast like a key distribution which is orthogonal to Perpetual encryption uh but with this issue um you know the decryption will be linear so sure I can try this I can say okay it's not this but you know if if I'm at 500 and this is three I will have to jump for 97 to get this Peri so the decryption scheme will belate the good news using multi scheme which also use a tree in a slightly different way it's like a lot of trees but uh you know using multi so so this is like a key distribution issue right now we justum kmit gives you this magic key for group members there is this primitive call multia which allows exactly this Dynamic group management it's like I can revoke somebody there is like one group and you can revoke and

add people so your thing will be kind of a naive solution to the multicast problem but you know this is not our work but we can use better multicast schemes which in some sense they do something similar but more aggressively using threes as opposed to pass but yeah this is a I think this is if I understand this is right it's a key distribution thing we kind of assume for now as a group manager is e honest always kind of committed nothing I said is how to distribute this keit but I think multicast will do it better than what you're saying but I think it will work yeah it seems like you started talking about blockchains but this is back more of the motivation like you're you're really only assuming sort of a bulletin board that has a total ordering of stuff yeah that's my

knowledge of blockchain it's like it started from the master initially I was like okay let's look you know the initial kind of application was more like oh it's like you have this you know groups on this bulletin people just talk and when people says nobody cares about people talking on the public thing so I had to throw some Financial stuff without telling you what this financial stuff is but yeah we don't do anything about uh or at least currently it's like you know on a technical level it's just the messaging and whatever mechanism you do for blockchain would work currently the simplest one you do whatever the public blockchain does whatever data structure you do for the public blockchain I guess I mean like you're not taking advantage of any programmability or like smart contract capability of the underlying chain I

guess I wonder if I mean we talked about the zero knowledge I wonder if there's anything else that you could use that for I hope so yeah you do this on bitcoin which is kind of interesting like you don't need I mean it' be very expensive on bitcoin but you could do it so you're saying smart yeah I'm hoping so I would love to do I mean I know a little bit about smart contracts I know high level how they work um my understanding is currently there are some private this smart I mean you can emulate some level of privacy because you can just put commitments and people do some opening so I think it would be awesome to incorporate I mean I haven't thought if there are any subtleties of smart contract currently I would just say whatever public blockchain does with smart contracts you can just put the

smart contracts inside your blockchain and do whatever okay yeah so there's maybe we're talking about two different things like you could have your private blockchain have a smart contract I think that would work fine that users would just have to validate everything you could also take advantage of smart contract capabilities in the public BL that you're building on and you might there might be some efficiency gains or that would be awesome I think that would be awesome I yeah it's like for me it's hard currently I'm only learning about this thing so it's hard to visualize the whole power I think I understand it smart I would love to brainstorm about it cuz yeah definitely we didn't put enough financial yeah that would be awesome I think it's a great great suggestion yeah one subtle thing is like you said oh we're doing the exact

opposite of starkware and other layer twos but actually the way they work is identical you're actually doing the exact same thing that they do I thought I'm doing like an rollups but they have this concept of an inbox so they just store transactions there but the the blockchain does at the Smart contract level doesn't execute them right and so what you've actually implemented is an inbox okay um so the and then the layer two just takes the transactions out of the Inbox and does whatever it does with it and then it kind of pushes back the results but uh but anyways your your application is immediately applicable two layer twos as a sort of encrypted inbox uh if someone currently don't do it I mean that would be amazing if you I mean as I said I don't know enough

that's why it's like I thought it would be a good opportunity to uh give a talk here so I'm grateful for join team for arranging the talk because yeah I don't know enough I I have a feeling feeling that this you know it could be applicable for more things I mean yeah let's talk about I mean I think that's yeah both of smart contract suggestion is interesting and yeah globally I was kind of a little bit excited just to see it looked at least on the surface we're doing opposite for for rups but maybe maybe it's actually not as opposite as I thought so I saw it's like listen you probably heard like 100 talks which are like really fascinating things how to save like a factor of three here and how to do things more efficiently in all thing I I felt like this could be a

little bit of a different methodology I don't know like different kinds of MTH different kind of tools so I would love if it's useful I would love if you guys uh you know push it somewhere or you know you know once you know we find other uses we can optimize and so on yeah smart contracts also would be amazing if uh there is a technical yeah that's my feeling in general whenever you kind of do something and when people from The Real World who know about Real World start to look at it new problems come up which you don't think about it right so this perpetuity to be honest it came from you know basically we had a scheme and once we try to formalize it and put the blockchain stuff more kind of constraints came about so um you know and luckily for us they were not like

that difficult this hash chain and this and that but they were kind of cute enough that uh you need to get them right [Applause]