Post-Quantum Single Secret Leader Election with Dan Boneh | a16z crypto research

Transcript

there is a professor of computer science at Stanford University that's in the field of Applied cryptography and security and she probably doesn't need a lot of introduction he's one of the most prominent academics working in our space um I need some intersection and photography and blockchains so we're hoping that great thank you Laura all right so uh I guess that this is a pleasure to be here thank you all for uh for inviting me I've been spending a couple of days in the lab this is like an awesome place to visit I highly recommend anyone who's watching should apply to visit the lab really awesome energy going on here so wonderful wonderful spot and also this seminar series is fantastic this is such a wonderful resource that goes on YouTube I hope everybody's watching the YouTube

videos whether a lot in LA Live or uh when they go up on on YouTube Okay so let's get started so today what I wanted to talk about is this concept uh what's called uh Secrets a single secret leader election it goes by the name of ssle it's gotten some attention uh recently and so I wanted to talk about some recent results in particular how to make post Quantum secure ssle and this is based on joint work with adidi Pratap and Ali or rotem oh and I should say also this is going to appear in in afd Advanced versus advances in financial technology aft is an awesome blockchain conference everybody should go to afd and submit their best paper best work to afd we need we need a blockchain focused conference and aft is is a good

candidate for that okay Lee so let's start with a quick review of uh where we come from right so we start with uh proof of work systems or proof of work consensus and you guys know in proof of work consensus there are a bunch of minors that generate uh that generates blocks they each work to solve a particular puzzle and when somebody solves the puzzle they basically post a solution to the puzzle along with a block yeah so in some sense in some sense at the time that the block is posted there's also a proof that the person that's posting the block is the elected leader and there's no gap between posting the block and electing the leader yeah that's improved for work

systems and then when we transition to proof of stake systems uh what happens all of a sudden we introduce a gap yeah so in a proof of stake systems typically a leader gets selected yeah so the you know the system says you know you are the leader you're the block proposer for this uh for this slot and then sometimes later the leader goes ahead and uh posts their block yeah so there's a gap between the leader election time and the time that the block is posted and this introduces a bit of an issue in that uh what can happen is uh you know the block proposer is known in advance so the point is that now you know who is going to propose the block so you can go ahead and uh attack that particular block proposer for example you can dos them maybe you can bribe them you can do all

sorts of things to prevent them uh from publishing the block and as a result boom you get uh you get a hold there's no block published in the system and so what does this what does the system do it moves on to the next leader but the next leader is also known in advance so now everybody just shifts their dos attack to the next next leader and uh so on and so forth and so you get a whole bunch of gaps in the in the chain and as a result you heard the aliveness of the chain okay so that's the problem that uh that we'd like to solve so by the way even in ethereum too uh the leaders are kind of known in advance and so uh this could lead to kind of a sequence of of holes if in fact somebody tries to repeatedly

attack the elected leaders so what do we do so first of all I guess I wanted to point to this uh wonderful uh uh survey it's a blog post by Chris Lara and uh Joe that kind of goes through different uh leader election mechanisms everybody should read this blog post very very good survey of this area uh and so uh let's kind of look about look at what what are the options so one thing we can do is uh well we can try to use a consensus protocol that doesn't have a leader yeah so it's a leaderless consensus protocol and one example is uh red belly consensus as a paper from 2021 so that's one option but you know most protocols that we use do actually have a leader and so what else can we do so the other approach of course which many of

you might be familiar with is what's called a secret leader election sometimes this goes by the name of probabilistic leader election or ple probabilistic leader election sometimes this is called the vrf method so it goes by a lot of names um and the way it works I guess this is what's used by all by our by algorand by oroboros Paris and so on so the way this works is again I'm going to give a very high level description but the way this works is basically every validator has um a number K we'll call it VK this number K comes from from a vrf but let's not worry about that let's just imagine the the validator has a number K and then uh when it's time to choose a leader basically to keep things simple we'll say that a random Beacon publishes

some 256-bit number R and the leader is the is the validator that has the closest number to uh to r or more precisely the leader is the is the validator who is close enough to r that the difference is uh you know the range divided by the number of validators overall yeah so an expectation you'll expect that there's roughly one liter well an expectation there's exactly one leader elected every time but you see what the problem with this is the problem of course is that the probability that no leader is elected because we have the strict inequality to satisfy no leader is elected or multiple leaders are elected this probability is non-negligible and as a result all these systems have to deal with these Corner

cases where nobody got elected or multiple people got elected somehow there's a Runa often there's a runoff election between the elected leaders leaders and so there's kind of more logic that needs to go into place uh when we use ple yeah probabilistic leader election it's a great way to secretly elect a leader because nobody knows who the leader is until they publish their VK so we do have a secret leader election mechanism but it's not a single secret leader election because we might be electing multiple leaders or no leaders at all yeah so that's kind of the problem that we set out to solve so what we would like to use is actually what's called a single secret leader election mechanism which has all the properties of ple the leader is Secrets but you are guaranteed that there's only

one leader elected every every time yeah so let's see the properties we'd like to have is it should be fair so all the parties are equally likely to be elected or you know if it's a stake bait system maybe it's weighted by their stake uh we'd like the system to be unpredictable which means that the leader remains secret you have no idea who got elected until the leader decides to reveal themselves when would they reveal themselves most likely they'll reveal themselves when they publish the block not before yeah but until they choose to reveal themselves they should remain uh secret and then it should be unique this is a single property this should be exactly provably exactly one leader gets elected not zero not two not three exactly one yeah so those are the three

properties uh we're trying to satisfy so let's just look at the trivial uh protocol to do this so the trivial protocol would be well if we have a random Beacon that just generates you know Randomness for us well when we just have the random Beacon choose one of the end parties yeah and we're done so let's see so that is guaranteed to be fair because we're choosing one party at random from the end parties it's guaranteed to be unique because the beacon is choosing exactly one of the N but of course it's completely predictable because once the beacon is public you know exactly who the leader is going to be and then you can go and dust them okay so the trivial mechanism using a beacon doesn't actually work now surprisingly actually building a secure

ssle protocol this turns out to be a lot harder than uh than we think this is actually not a not an easy primitive uh to satisfy I'll show you some constructions in just a minute but kind of constructions that for example don't use a random Beacon they end up using fairly heavy cryptographic tools yeah so it's like this is not an easy thing uh to construct and we're going to go through a couple of the constructions uh in just a minute so one thing that's interesting is there's this really a nice paper by azuvian capaletti this paper actually looks at a comparison of doing single secret leader election versus probabilistic leader election where we might have where it's Secrets but we might have more than one leader elected and what they looked at is particularly uh private attacks against

this proof of stake consensus this is a purely a combinatorial paper yeah it's a combinatorial analysis uh comparing the two in particular if you uh look at the impact of these privacy attack and the longest chain uh protocol yeah consensus protocol and uh you know they're worried about what happens when the block producer keeps some blocks to themselves and they surprisingly I mean they showed that actually ssle results in Faster consensus yeah in particular what that means is um you know the time until you are confident that the block is really there is something like you know 25 faster with ssle versus uh with ple when the attacker controls a third of the stake yeah so there's really ssle really

not only is a simpler logic you don't have to worry about the case where you have multiple leaders it actually leads to faster settlement time which is uh which is pretty interesting typically for longest chain this is specifically for longest chain and their their analysis is only in synchronous networks they kind of leave it uh to other other networks they leave it as an open problem it's kind of a cute it's very cute it's kind of a nice it's purely combinatorial it's not this is not an experiment it's a like a recombinatorial analysis of what happens and I guess I wanted to also mention that there's another aspect of uh secret leader election which we're not going to talk about there's kind of the uh you can kind of go all out on leader election where you can say well what if I want even more privacy right you guys

remember the in ssle what happens is when I publish my blog I reveal my identity right and perhaps even in ssle I reveal how much stake I have well you can ask well what happens if I want to keep uh the leader's identity private so nobody knows who published the block or I want to keep every every validator's stake I want to keep it private like why why should the world know how much uh stake I put into uh into the consensus so there's actually some work that focuses on full privacy so I listed some some papers here some variations of oroboros and so on that focus on complete privacy but these systems interestingly so yeah so they hide the stake and the identity of the of the leader but these systems basically are

primarily their ple based systems yeah so they still use uh vrf lag mechanisms but for example some of these papers just focus on what's called an anonymous vrf so you know that the vrf value is correct but you don't know which vrf value which vrf it actually came from and that's how you hide the identity of the leader so again they're not focusing on ssle which gives us advantages and Consensus These are just they're focusing primarily on privacy and still staying in the ple realm um cool okay so we're not going to look at this model we're going to stick with the ssle model where you remain the leader remains Secrets until they publish their block and then everybody knows that that's who they are okay so because of the uh these these advantages

in in consensus in fact uh if you look at the uh ethereum timeline maybe this is kind of an old picture actually what does it the merge and The Surge and The Purge and whatever you know all the all the all the cute names that come up there in fact see single secret single secret leader election is kind of one of the uh components that they're looking at uh this is kind of a research area for the ethereum foundation but hopefully this is something that we'll actually see uh deployed uh in in a version soon so that's interesting that um it's actually getting some Traction in practice as well also when you look at Aztec Aztec put up an RFP recently so Aztec once when they launched they want to have a decentralized uh sequencer and so if they have a decentralized sequencer they have to have a leader

election protocol and in fact in this RFP they specifically say um you know we want to allow the sequencer the option of anonymity during the selection of the leader yeah they might even want to do it during block submission but particularly doing a selection of the leader they want to have leader privacy so they're all to looking at ssle type type protocols so um yeah so even it's it's kind of interesting that even l2s are interested in uh ssle these days so yeah so it's quite a kind of becoming kind of an important problem in the in the blockchain space okay so now that we have our background on on ssle uh let's look at some ssle constructions yeah so this area really kind of uh got quite a lot of attention and so let's look at a

couple of constructions so I guess this is something that uh our original paper from it's by now ancient history like almost 2020 it's like a long time ago in the world of blockchains yeah uh we basically gave a construction using a threshold foliomorphic encryption so no Beacon just uh but as I said if you don't have a beacon it turns out you need fairly uh uh very fairly powerful cryptographic tools there's a construction I should say so using using fhe's one one thing in the paper we also give a construction just to show feasibility we give a construction from IO uh you can also give a construction from functional encryption so these are pretty heavy cryptographic tools you need to construct it like uh from scratch uh there's also another oh but by the way I

should say like the fhe fully homomorphic encryption based system if you have in in parties you're trying to elect a leader among end parties it turns out the multiplication depth of the circuit is only around login yeah and it's actually a fairly simple construct fairly simple construction to describe maybe I won't do it here but you interested in seeing how it works it'll take me literally two minutes to describe it it's a very very direct and simple Construction the other approach Which is far more practical is using what we call re-randomizable commitments and that's actually what I'm going to talk about yeah so I'll talk about um exactly about what what we randomizable commitments are in just a second so this is the in the original paper and then the ethereum foundation actually went and optimized that this is kind of what they would like to use

perhaps in a future version of ethereum and I'll mention also that there's a even a a construction uh due to Catalan at all that gives stronger security uh in the in the sense that they look at adaptive Corruptions rather than static Corruptions then you can build it based on pairings you can build it using MPC and then Sansone in the ethereum foundation even looked at constructions from misogynies the reason again they were interested in post-quantum ssle and so there is a construction for misogynies as well unfortunately their the performance of isogenes is not as great as we would like and so the natural question is if we want to build a post Quantum system what would we like to build it from can

somebody say what do we like to build post Quantum systems from lattices exactly so the question is can we oh sorry I skipped a step I forgot to say to say that sorry before we get to lattices well fine I'll say it so the question is can we build ssle from lattices but if we look at the existing families of constructions well fhe is built from lattices so it's inherently uh post Quantum but fhe is pretty heavy weight mechanism yeah so we'd like to use something that doesn't have to rely on fhe all these previous constructions were based on discrete log and pairing they fall apart in the uh post Quantum world exogenes are post Quantum and the NPC methods well it depends on which NPC you use so maybe it is maybe it isn't uh

okay so that's kind of the state of the world and the question that was open is can we have a post Quantum ssle by the way the reason uh we started looking at this it's called also kind of a philosophically interesting uh question which also came to us from the ethereum foundation and they they said that for every cryptographic primitive they deploy they would like to have even though it's pre-quanton today they would like to have a post Quantum variant so that if you know oh my God tomorrow we open the New York Times and it says somebody in the world built a quantum computer the ethereum foundation has they know what to do they know what to deploy so for everything it's quite a uh very it's a very good philosophy actually for everything they deploy they want to have a post Quantum variant

maybe they don't deploy it right away but they want to have it in their pockets instead in case they need it uh they need it in an emergency so for ssle we need to have a post Quantum version all right so let's go and and build one and the one that I'll focus on because they kind of chose uh this approach I'll we'll focus on post Quantum from re-randomizable commitments and that turned out to be kind of an interesting question that's that's what I want to tell you about all right so to explain how to build it I first of all have to explain what a re-randomizable commitments and how how do they come up in ssle so let's walk slowly through the ssle construction that uses re-randomizable commitments and you'll see exactly what the problem is

all right so we have our parties so we have our end validators that we want to choose a leader from the first thing that happens is called the commitment step so what is the commitment commitment step well everybody basically generates some random number and they commit to that number so they publish a commitment of their number they also publish a hash of that number and the reason we publish that hash is to make sure that all the committed numbers are unique yeah we don't want to have any duplicates so this doesn't break the commitment it just reveals enough information to argue that the commitments are unique okay good so that's just the setups setup stuff now that we've done the setup uh what happened so this happens at the beginning of time Yep this is one time

for the entire entire chain or at one time for many many slots so what happens next is now uh we have the re-randomization phase where a party wakes up yeah so here Alice woke up and what she will do is she will shuffle all these commitments and re-randomize them okay so they she literally permutes them under a random permutation but of course just permuting is not enough because uh you can just look at the original commitments and the new commitment and figure out what the permutation is so what she does in addition to permuting she also re-randomizes the commitment so they don't look anything like the original commitments okay and we keep doing that oh sorry and then she has to produce a proof that the shuffle was done correctly yeah this is called a

proof of Shuffle that this is a zero knowledge proof that she permuted and re-randomized but she didn't change any of the committed values yeah so she didn't drop any commitments she didn't add any commitments and she didn't change any of the existing commitments that's a proof of Shuffle and then we just do this over and over again the parties just go ahead and every Everybody Just permutes and then once they're done permuting they're happy to kind of every thing got permuted around what happens is we're going to use a Beacon to randomly select one of these commitments for example the beacon says position number two is going to be my uh the leader and now nobody knows who uh who position number two is because everything got permuted yeah so the leader is secret to this point the leader is committed to it selected but

nobody knows who the leader is because nobody knows what is inside of the commitment but when the leader is ready to publish their block what they'll do is they'll reveal the fact that this is uh K3 is their commitment and a proof that K3 is in fact uh their uh their commitment and then now they can publish the block yeah does that make sense so that's the process of commit and Shuffle um yeah so uh right so the commitments hide who so we select one commitment that doesn't reveal who the leader is but the leader can later on open the commitment and reveal that that's who they are so that's the general framework for doing it and so now the question is what kind of a commitment scheme do we need to make this work so what we need

well okay so yeah yeah so the question is uh oh what is what is post Quantum alternative mean in practice oh my God Elaine you want to get you want to get philosophical I see yeah sure I'm just wondering like there are pre-compiled right that support clearly not post content photography like Olympic curve arithmetic so those seem really tough to protect yeah so I see okay uh good question okay this is this is a philosophical question like what does it mean to be post Quantum secure if you have pre-quantum Primitives pre-compiles deployed in the evm

uh well uh uh your your your guess is as good as mine but I suppose if somebody comes up with a with a quantum computer earlier than we expect you know presumably these pre-compiles will continue to exist um but we will also add post Quantum equivalent pre-compiles so people can migrate their their their contracts to these new to these new precompiles this is by the way a pretty deep rabbit hole because as you know there's a way to immunize existing systems against the future quantum computer uh but that's maybe that's a discussion for another another talk yeah so thanks Elaine this is a good good question but that's a pretty that's kind of a long long and complicated conversation we can have that debate or not debate that

conversation maybe after the talk sounds good yep okay excellence yeah please the whole transcript of this ssle would go on channel yeah yeah so of course the ssle transcript has to go Unchained and that's a that's an excellent question and so what happens is actually here I'm describing a simplified version of of the protocol so here we permute basically all the commitments so every time we permute we would have to write it all on chain there are optimizations that dramatically reduce the amount of communication I'll get to that at the very end yeah we don't so we can basically use we don't have to permute everything we can use a rapidly mixing mixing Shuffle and then we only only uh touch a few commitments at a time yeah

so we'll get to that at the very end can they not just those commitments with identities yeah yeah so this assumes this assumes one honest party so as long as one of the parties is honestly shuffling and not revealing uh what the shuffle is then then at the end you break the connection between the commitments and the validators I know what like commit of K1 is right so now I know a value that is associated with a person when at the very end no no you don't know what you don't know what the key is I know the commitment yeah but the commitment changes every time it's reroute the commitment it gets re-randalized every time yeah so the commitment changes as you walk through

this process God yeah so at the End by the time you get here the commitment is unrelated to the original commitments why is the random Beacon necessary why can't you just say the first commitment is the winner yeah there okay good so there are some some uh technically technical issues with that um so let's see so if you say that the first commitment is the winner so the last shuffleer basically could always Place themselves first and then they win yeah does that make sense yeah so right yeah so you don't want to do that yeah it's interesting without without a beacon this is uh like I said we need pretty heavy heavy uh tools to actually

build this okay so let's look at the components that we need to make this construction work okay so what are the components that we need for this so we need re-randomizable commitments which we'll talk about in just a second we need a proof of correct Shuffle and we need a Randomness Randomness Beacon as we just uh just said and the properties you know fairness is guaranteed by the beacon is going to choose one element at random unpredictability happens because of the hiding property of the commitments and uniqueness happens because all the committed values are are distinct okay so let's talk about re-randomizable commitments and see uh see what they are so what is a re-randomizable commitment you can kind of already visualize uh what's needed here but let's go through it uh carefully so basically there's a

commit algorithm that will generate a commitment to a key and then the key will become available to the committer okay so the commitment algorithm generates a key for the committer then anyone can go ahead and re-randomize the equipment and later on whoever holds the key can prove that this is their commitment yeah so that's kind of a at a high level what we'd like to achieve the Syntax for this is you know we set up the system with some public parameters the commit algorithm generates a commitment and a key there's a randomized algorithm that takes a commitment and re-randomizes it and there's a verify algorithm that takes a commitment and a key and says yes this is a valid key for this commitment or not yeah those are the that's the syntax for these for the system let's go

through the requirements so we'll say that this is T randomizable if you can re-randomize t times okay so let's just see what that means basically if I generate a commitment so I have a commitment and a key and I repeatedly randomize T times so I iterate relatively randomize again and again and again and again T times until I get a new commitment then the verifier will still accept the key k for the re-randomizable commitment that's if we do it up to T times if you do two plus one times maybe it doesn't work but T times we can we can support uh we also needed to be non-degenerate meaning that if I generate two random commitments the probability that I get different Keys is almost one yeah if I always got the same key then we'd have a

problem yeah but I'm gonna get different keys with very high probability and now let's talk about the security properties so the First Security property is binding the standard binding property which means that given a commitment I cannot open it in two different ways you can only open it in one way and the unlinkability property is a little bit more tricky to Define but the unlinkability property goes as follows well I'm gonna ask you to randomize uh I either I zero or i1 times what I'll do is I'll generate one commitment com0 and I'll randomize it I zero times I'll generate another commitment com1 and I'll randomize it I one times and the property is maybe you guys can guess

that the property is that if I give you the two commitments so you see the original commitments and you see either the re-rand advisable Zero's commitment or first commitment you can't tell which one you saw yeah that's the unlinkability property so once I re-randomize equipment you can't tell whether it came from com0 or from com1 they both look the same way and this basically again means you can on you cannot undo the permutation by just looking at the commitments because after we randomize they all look the same that's kind of the unlinkability property all right that's what we're trying to construct so the first question to ask is does this even exist at all yeah is there any way to construct this thing and so the first observation is that uh using discrete

log this is a trivial thing to construct yeah under the decision if you helmet assumption it's very very simple to construct this so let's just walk through the construction you'll see it right away uh basically we're going to fix a group yeah where the decision defe helmet problem is believed to be hard and the way we commit is basically we're going to choose a random key K and then we're just going to Output the generator and the generator to the K G and G to the K that's going to be our initial commitment well how do we re-randomize if I give you a commitment you come if you you see a commitment as a pair of group elements so I give you u and v how do we randomize well we're just going to choose a random R and we're going to erase both u and v to the power of r now

already looking ahead anyone who's familiar with DDA with decision diffie-hellman knows that once I raise things to the r they sort of become pseudo-random so you can't connect this to the original thing anymore so good we're getting our good unlinkability properties uh and then how do I verify if you reveal K yeah if once you reveal K it's easy to test that K is correct simply take the first element take U and raise it to the K and check if that's equal to V and you see that the re-randomization uh preserves the discrete log relation between the two values yeah so very simple like the The Binding property is easy the unlinkability property is easy there's a very simple theorem this is in fact infinitely re-randomizable uh it's

binding and unlinkable and streaming assuming ddh what could be what could be easier and simpler to use great not only that in fact this kind of uh this kind of re-randomizable commitment also have a also has a very good proof of Shuffle yeah this is what's called the buyer growth uh proof of Shuffle so this is great like everything is just just comes along and maybe this is why whisk actually works as well as it does uh and uh so everybody's happy with this the only problem with this Construction is it's not Quantum resistance yeah so we've got to build something that's Quantum resistant so the question then is how do we build re-randomizable commitments from lattices and this turns out to be a pretty interesting question

because the first thing you try doesn't work yeah okay so uh with Lada says everything is harder everything is harder yeah so here it's nice and clean very simple construction now let's switch gears and talk about the world of lattices and how do we actually build something like this uh that's post Quantum secure okay so a good starting point is well let's start from a lattice commitment scheme yeah uh let's say here I'm going to go slowly let me just kind of explain uh how these lattices work how do we use lattices in cryptography by the way I hope people are familiar with what a lattice is right the lattices uh well technically it's a discrete what is it a discrete subgroup of R to the N that's the mathematical definition the more

human definition is uh you know I give you a bunch of vectors and art at the end and you take all integerly oh sorry n vectors in R to the n and linearly independent vectors in R to the n and you take all integerly new combinations of those vectors yeah that's a lattice and there are lots of of computational problems and lattices and many of those problems are believed to be hard for a quantum computer which is why we can build cryptography from lattices okay so let's talk about how do we build uh lattice commitments well so when we use a lattice we have to first of all fix a prime cue okay so there's some prime uh there are parameters because we're going to be dealing with matrices yes they're uh matrices of Dimensions M by n and then there's often a noise distribution Chi that generates uh low

Norm noise like the numbers the noise is going to be like numbers in the range minus five to five yeah so it's just some low noise uh noise distribution and the way we could we can commit the way we would generate a commitment in the re-randomizable commitment scheme is as follows what we'll do is we'll change we'll choose a random Matrix a so this is a tall matrix it's an M by n Matrix we'll choose a random key K and then we'll choose a random noise Vector from the noise distribution e and the way the commitment will work is you know K is going to be our secret key and the commitment is going to be very similar to the G comma G to the r which is going to use the lattice equivalent of that so the Matrix is going to be one element

and the other Matrix the other element will be a times K plus Some Noise Okay this is an important component a times K plus Some Noise by the way it's important to realize this is just a vector right so we're doing a matrix Vector product which gives us a vector and then we're adding some noise to this vector so the commitment looks like a matrix and a vector that's it okay that's a very reasonable Place uh to start um and so the question is how do we re-randomize this yeah that's the first question so uh maybe I should maybe I I should ask if anybody sees here let me kind of skip ahead no Ah that's it how do we verify first of all so the commitment is going to be a matrix and a vector how do

we verify that the key K is correct well I'm going to reveal the key K and what we're going to check yeah so here pay attention how do we check that the key is correct we're going to compute the product B times K this is a vector and if this if k k is the correct uh key for this commitment what will happen is that b times K is going to be close to the vector B yeah let me just remind you why that's the case if we look at the definition of b b is going to be B K plus the noise Vector so if we take the vector um if we take the Matrix B and multiply it by K basically what we're going to get is a vector that's off from B by the vector e and e is a low Norm Vector

right so basically if these two are close in other words their difference is a low low L2 Norm Vector then we say that K is correct so let me ask you see if anybody can help me here so how would we re-randomize this commitment so we have a commitment you know Matrix and a vector that satisfy that we want to preserve this relation that b times K is close to the vector B how would we re-randomize the commitments ah yes exactly exactly exactly exactly that's exactly where we're headed perfect thank you so uh what we're going to do exactly we're going to do kind of a kind of a thing that comes up in in lattice's uh

quite a bit and the way we randomize is we're going to choose a random sort of Boolean you know minus one plus one square matrix it's not a rectangular Matrix anymore it's a square Matrix and what we'll do is we multiply both the Matrix and the vector by this lower Norm low nor Matrix R okay fine this is all standard a lot of stuff so far why does verification let's just verify why does verification still work well remember this relation this is how the vector is defined so why does this relation still work well we multiply if we multiply both sides by r you see we're multiplying both sides by The Matrix R the noise the difference between B and B times K becomes R times e yeah our low Norm Matrix times the

lower Norm vector well a low nor Matrix times a lower known Vector is still a low Norm Vector yeah so they still remain close to one another not as close as before they get a little bit further apart because we multiplied by a random Matrix but they still remain close this is by the way why I why I said that we only need T randomizable because the more we randomize the further apart they drift and eventually they're going to drift too far apart and we're going to reject the key so we can only re-randomize T times great so to go after a good start yeah this is kind of the first thing that we we tried surprisingly this doesn't work yeah so good so uh so great we have a scheme so the question is I guess I gave it away the question is is it secure

so let's look at the analysis so it's not so hard to prove a theorem that shows that the scheme actually is unlinkable so if you re-randomize in fact the the commitment you get is um is unlinkable to the original commitment and this is based on the standard learning with errors problem which I'll explain what that is in just a second great and the proof you know this is I'm not going to go through the proof it's not a very interesting proof it's kind of a standard argument using lwa and the leftover hash lemons this is kind of for a cryptographer this is like literally bread and butter yeah we do this we do this in our sleep so not a very difficult proof uh but I guess now I have an opportunity to show you I'm not sure if everybody is up to speed on the world of lattices so

just to make just to show you what these assumptions look like uh let me explain what the learning with errors assumption is I have an opportunity to explain this so let me show you uh what the assumption is uh and the Assumption I'll describe it in kind of uh well describe it the way I like to describe it um so again we have these parameters the prime the dimension and the noise distribution and just so you see real numbers the primes tend to be relatively small so like they're 15-bit primes uh the dimensions are in the hundreds yeah so these are big big vectors and the variance is actually again very small the noise distribution is literally numbers between minus five and five it's kind of a gaussian between minus five and five with variance of 1.75 yeah this is from one of the nist candidates for

uh post Quantum key exchange so you can see very concretely by the way the fact that these primes are so small is why these lattice systems actually work so quickly because we're not dealing with there's no big number arithmetic here we're just dealing with very very small numbers computers love these things and so uh this is why this is so fast what does the Assumption say the Assumption basically says that um if I choose a random Vector s yeah so it's an n-dimensional random Vector s and I give you two boxes one box basically will spit out vectors of the form while A1 a2a3 these are the vectors and then scalars of the form A1 times the secret Vector plus noise A2 times the secret Vector plus noise yeah if I give you this output versus if I give

you just vectors with random scalars yeah so here you can see the definition of what these things are so Random vectors plus well computed scalars or random vectors with random scalars the Assumption says there's no Quantum polynomial time algorithm that can distinguish between these two boxes yeah that's the assumption so it's kind of interesting it's very interesting for example if the noise was Zero if all the noise value were zero this would be false right because if all the noise values were zero then after a few samples you'll be able to solve for S and then you'll be able to check that all the results actually look like us so it's kind of this remarkable thing that by throwing in a little bit of noise

into these relations you make the scalars look indistinguishable from random that's what the lwe Assumption says and there's this classic result of regev that says if in fact you gave an algorithm for lwe then um in fact this would give us a way to solve a difficult problem something we believe is hard for a quantum computer yeah the approximate shortest Vector problem yeah so a lot of the nist candidates are based on variations of this based on ring lwe so I think it's actually good if somebody hasn't seen this I think it's good to stare at this for a little bit because just so you understand like uh in 15 years most of uh well I should say

um kind of many of the post-quantum candidates that will be deployed in the real world are going to be based on assumptions of this flavor yeah so literally the security of the internet is going to start depending on these types of assumptions so it is really kind of important to understand the quantum security of these of this type of assumption yeah so um I would argue that it's pretty important in the next couple of years that a lot of the folks who are specialists in designing Quantum algorithms think more about you know what is the best algorithm for uh for kind of resolving the lwe question just because this problem is going to become so important for the health of the internet okay that's a bit on the side now let's go back to our to our main story

so the question is remember we had our re-randomizable commitment example and it was unlinkable just like we needed once you re-randomize everything becomes random what was the other property of a commitment scheme that we needed you need to be unlinkable what was the other property binding it needs to be binding so the question is is is this commitment scheme actually binding in other words is it really difficult to find a commitment B and B and two different Keys such that b times K is close to B is close to B times K Prime right that if we could do this this would break binding and in fact it turns out it's not that difficult to show that in fact for a random Matrix B this is difficult you

can't do this yeah just secure there's just no K in K Prime will be mapped close to one another the adversary can choose the commitment adversarially right the problem is B is not random it's chosen by the adversary and actually if you think about this for a second you'll see the adversary can choose a matrix B for which this problem is Trivial for example if the Matrix B is made up of Lone Norm columns you know vectors of low Norm then in fact any lower Norm K will collide with any low Norm K Prime and boom we have we broke binding and this is not just a theoretical attack this actually would break the ssle yeah the protocol just stops being secure so this construction just doesn't work yeah it's kind of the first thing

you try just doesn't work and what's even worse is you try to to kind of hope that you can fix it quite easily but the trivial fixes don't work for example maybe we can uh fix the Matrix b as part of the trusted setup process or maybe we can generate the Matrix not as a random Matrix maybe we can generate it as a as a random Oracle applied to some seed yeah so we generate the Matrix derive The Matrix from some C so we force it to be random so it can't be so the adversary you can't just choose whatever Matrix it wants but the problem with these two solutions is they break the re-randomization uh mechanism so we can if we do this either one of these we can't re-randomize the commitment

anymore yeah so like the obvious Solutions don't work so we need to invent something new yeah and so the first step is solving this problem and so let me show you the solution the solution is basically to say well you know there's this observation that it's true that that uh in fact you can cause collisions but in fact if you choose random K and K Prime there are very few matrices that will cause these values to collide with one another yeah they exist but they're very rare yeah and so what we'll do is if we choose enough random vectors enough random K1 to KL then in fact you can argue that with very high probability there is no Matrix there are no

collisions among these these set of vectors yeah so that's kind of the observation and that's going to be our way out and so the actual commitment scheme what we'll do is rather than if you remember before we used a single vector now instead of committing to a single Vector we're going to commit to a matrix this is going to be we're going to expand this into a matrix away from a vector and in fact this Matrix that we're gonna that's gonna we're gonna use as a key is going to look like just uh basically L random vectors and we force it to be L random vectors by basically using a hash function yeah so which will model as a random Oracle so kind of we force the adversary to use a random key The Matrix we have no control over the

Matrix can be arbitrarily adversarial but the key we can force it to be um to be a random looking Vector a random looking Matrix yeah and the point is everything works the same so to verify you're just going to reveal the seed and you're going to check these L2 L2 Norm conditions and re-randomizable re-randomization works exactly as before okay so that's kind of the uh almost the final construction and you can now you can prove these two theorems the scheme is binding assuming the the hash function is a random Oracle and the point is now the scheme is also sorry it was unlinkable unlinkable is easy now it's also binding using H being a random Oracle and we still preserve the unlinkability so now we have the two

properties that we want yeah how make sure I think you're an LS um yeah okay so asymptotically it's just logarithmic in the you know in logarithmic in the security parameters and in reality is going to be also in the in the probably around 100 or so so not too bad okay yeah I think another question so the question is if you fix B in the setup procedure The Matrix B can you re-randomize and no the answer is you cannot be randomized because re-randomization required changing the Matrix yeah and so uh yeah that unfortunately doesn't work yeah cool it's a good question okay great are we done yeah but this requires all of these L vectors to be randomly chosen right well we

force them to be randomly chosen by choosing them from by choosing them from the hash function here we go here yeah so they're not actually uh adversary doesn't get to choose to meet the vectors however it wants it has to choose a seed and then derive them from the hash function it used to prove that as well like well no you just no no you reveal the seed and then the verifier that verifies the key will and by the way it's interesting this is exactly why The Binding depends on H being a random Oracle because we do need these uh these vectors to be to be random looking yeah and the random work over guarantee that need to prove that it multiplied

correctly by a small Matrix ah fantastic question there fantastic that's exactly where we're headed okay perfect couldn't you couldn't have asked that at a better time so so the question is are we done well unfortunately there are more problems so it's kind of interesting there are more problems these problems don't come up in the diffie-hellman case in the ddh case all this stuff is like not a problem here all these problems come up it's exactly what I was asking so if you think back to our definition of unlinkability remember we said that if you re-randomize I zero times it looks the same as re-randomized re-randomizing i1 times well that's assuming re-randomization is done honestly but what a free randomization has done this honestly

then it turns out we have a problem yeah so it turns out uh you'll break unlinkability which again breaks the ssle uh protocol so let's define so we Define actually a stronger notion of re-randomizable commitments we'll say that they're strongly unlinkable if they're unlinkable even if the re-randomization is done adversarially which is what you're asking right what if you choose a malicious Matrix r right and it turns out that the ddh construction is strongly unlinkable trivially this problem just doesn't come up in the ddh world whereas what I just showed you is insecure yeah it's not that hard that's actually it's a little tricky but it's not too hard to show that it's insecure as an attack there's a real but like what you said Lara actually leads to a real Attack

and so okay now we're getting short on time so I'll just say there's one more step we need to take to immunize the construction again to make it strongly unlinkable so there's one more immunization step that maybe I'll leave to the paper uh and so we can get we can get actually a strongly unlinkable scheme and so now we get uh so now we have already randomized commitment we have to marry it with a proof of Shuffle and so which proof of Shuffle works with this commitment it turns out we can use an adaptation of biograph uh to the ring lwe settings and we get a nice proof of Shuffle uh which gives which gives us an efficient ssld overall yeah so that's kind of the end of the story and I'll say uh who's asking about posting oh

you're asking about posting things on chain so this is this this bullet addresses that issue then in fact when you implement this in practice like in whisk and in some other papers you don't re-randomize the whole set you just re-randomize a small set a small portion and you use kind of a rapidly mixing process that even if you re-randomize a small shuffle a small set it very quickly converges to um to a uniform distribution yeah so you don't have to write on chain you don't have to write that much data every time yeah and maybe I'll leave this also for the for the paper yeah you do everything sort of you describe Things based on Plain LW yeah we do yeah we give we give both yeah so the paper basically gives instructions from LW and from Ring lwa The Ring LW is actually

more efficient so probably that's what you'll end up using uh in the real world and uh yeah so this gives us this post Quantum security and so yeah I think I'll stop here basically this is um I think there's a still a lot to do here in the post Quantum setting so the question is could we have other lattice based ssle schemes in particular there's a again there's a very nice uh lattice sorry there's a very nice pairing based paper for uh ssle from the same group CFG um and one thing if people are interested in working on this it'd be nice to look at this construction and convert it to the lattice settings I showed you the re-randomizable plus Shuffle construction there's a whole other path to ssle that would also be nice to convert to the lattice settings

so there's actually more more work to do here but yeah that's where we are so now there's a there's a post there's a post Quantum alternative to ssle so you can feel safe in deploying the DV helmet ssle you know if the world collapses and tomorrow somebody builds a quantum computer we have a fallback and uh you know we're hap back to our to our happy state okay so I'll stop here thanks uh thanks for listening happy to take any questions great yeah please one component of this was the randomness Beacon yeah what are like post Quantum solutions for randomly speaking oh oh yeah yeah that's a good for the full thing to be post Quantum that one also has to be yeah so I guess I guess what you're asking is uh

do we have a post Quantum vdf right and so the answer is yes we do uh so the vdfs you know the vdf that actually is going to get deployed is a hash chain based vdf how do you prove that how do you prove that the vdf is computed correctly well you give a snark proof that the hash chain was computed correctly so now we just need a post Quantum snark proof and what's that called so one example is the Stark system there are other there are lattice based yeah there are a lot of space plus Quantum systems but one example of a post Quantum proof snark system is is Stark right so you could build a vdf by using a post Quantum hash function which is easy along with a with a stark proof yeah

space PDF is a pretty interesting challenge yes yes absolutely a lot of space vdf would be would be awesome that's a fantastic open problem yeah I guess I guess you would have to well I guess if you could we have lattice based snarks so I guess you could just take the hash chain one and combine it with the last base start but like a native lattice based vdf that's a fantastic question yeah so please solve it yeah it's a really really nice problem to work on yeah oh yeah please Laura Pilates oh oh that's a great question so so what we would need is a vrf right so do we have a lattice based vrf if you're interested

in just a slotted VR it's it's not a vrf but it's a vrf it's like a slight relaxation of a vrf that works for probabilistic leader election and it only uses hash functions it's really it's really simple there's like a hash chain and ah yeah yes right yes all you need is Hash functions for a probabilistic leader election ah yeah yeah good good all hash functions are sufficient yeah good I see so you don't even need lattices you can just rely on hash functions yeah even even easier but for but if we go back to the vrf question I guess um well there's a generic answer if because if once we have a lattice base narc we would in a lattice based prf we converted it we can convert it into a

lot of space Europe business hash basis it's like spotted vrf the Restriction is that you can only compute it once per slot but that's all you need that's all you need yeah good good good good because you basically reveal your key for that slot which is the spot in the hash chain and then yeah yeah so so just to maybe to summarize what Joe said for the people at home uh so Joe is saying that there's a very simple construction for ple probabilistic leader election just from hash functions you don't need anything other than hash functions that's great so then it'll definitely be post Quantum secure yeah please become the random shuffle it seems to me that these two things are the same

um oh I ran the beacon and random well okay not not quite right so uh random shuffle or rather uh Shuffle proof is married to the uh commitment scheme right to your the shuffle proof you're doing is you're re-randomizing the particular commitment scheme that we have and then you have to argue that the committed values on the input side are equal to the committed values on the output side modular the order so that's more specific to the exact construction of the commitment scheme whereas a beacon is just generic it just gives you random bits it doesn't care about the commitments so what they need is approval for permutation yes exactly exactly so you need to exactly you need to are you need to prove that the output

is a permutation of the inputs right nothing was added nothing was dropped nothing was changed yeah I know that's what these proofs to shuffle do yeah so we have we have pretty we're very good ones uh that's that's what gets used here in fact the the Whisk construction um one of the the things very cool things they did is they really optimized the proof of Shuffle to get it kind of as efficient as possible that was very very cool work yeah cool it's a great question yeah awesome thanks yeah this was fun [Applause]