Exponent-VRFs and their applications with Yehuda Lindell | a16z crypto research talks

Transcript

my pleasure to introduce you HUD lindel uh he is a head of cryptography at coinbase and a CEO was a CEO at inbound security he's also a professor at barand University and he's going to talk today about exponent VFS and their applications thank you very much this is a joint work with Dan Bon and heitner the work really came out of looking at a number of different things that we wanted to do and then just observing that it turns out that all of these things and actually many other things can all be derived from a very from a single very very simple primitive simple in the sense that very simple to describe how simple it is to construct uh that I guess the future

will see but my aim in this talk is to convince you that this is a very interesting primitive and you should work on finding a simple and efficient uh construction of it and then we get all of this beautiful stuff for free okay so what's a verifiable random function I think everybody uh knows this by now but I'll go through it it's a pseudo random function with an additional proof that I'm Computing the correct value so in order that this in order for this to make sense I have some sort of commitment to my secret key or or a verification key which is some sort of commment to that key and then I'm proving when I provide a value that this is actually correct correct relative to that key so now we're sure that every time that I compute this s random

function I'm actually giving you the correct value according to the uh uh key that I committed to initially that that's all the verifiable random function is uh so what's an exponent vrf or an evf it's exactly the same thing except that instead of giving you the output of sud random function I'm going to give you the out output of the function in the exponent okay that's the only difference so depending if you like additive or multipli notation I see everybody here goes with multiplicative so you're going to swear at me throughout this presentation because I've been doing additive for the last uh I don't know how many years um I am a traditor to my uh to my field so um so

in other words instead of giving you just y I'm going to little y I'm going to give you y * G in eliptic curve notation or J to the Y in finite Feld notation that's the only difference so it's extremely simple to understand what this thing is right this is not a complicated primitive it doesn't have a complicated definition uh there are some small additional details like you want a simulator that can extract the private key during the generation of the verification key but that you can pretty much imagine is is not very difficult to do some sort of zero knowledge proof of knowledge and it's only during during the generation phase okay so very simple primitive but it can turns out you can do lots and lots and lots and lots of stuff in general the idea of intuition

is that there are many cases when we're trying to do protocols for threshold signing special cryptography or other things where we need to generate a random scaler multiply it by the generator point and send the result and uh if we need to make sure that uh we're proving correctness or or or other properties we'll see later on then with an evf it's sort of atomic because evf automatically gives you this you don't have to do a separate operation improve consistency or anything like that that's the basic idea but so what and so here are all of the applications that we have for this very very simple primitive the first is the two round fully simulatable multi-party schnor signing the fully simulatable

part is the novel part here and I'll spend probably about a quarter of this talk talking about simulation based definitions and why I'm in favor of them and why I prefer them and part of the reason is because I'm really old I know that uh but I think actually they have significant advantages and and we should uh consider them the second is a two round fully s simulatable two- party ecdsa signing protocol and I conject we can do multiparty as well but I haven't uh done the work and I'm assuming that something like with ab's protocol we could plug it in and and do do that two round fully simula with deterministic multiparty schnore not perfect on the threshold part but but without the threshold for sure one round fully

simulated will distributed key Generation Um you need some sort of unique nons sort time stamp for that but in practice that's absolutely fine for key generation MPC friendly HD derivation like bip 32 but MPC friendly that I can also verify that I'm doing the correct thing and when I get to that later on the talk I'll explain why that's important why it's not trivial something called a proof of Corum identity for multiparty schnor and now after the protocol the party the set of parties who have signed can come and prove that they are the one that signed think about for example you're giving a reward to people who actually signed they can come and claim that a reward and they can't and nobody else can can uh cheat and all of the protocols are

ually secure meaning that they're secure under General concurrent composition and they're secure for any number of Corruptions and our constructions are all on using standard assumptions in the random Oracle model so this is like a long list of all different things that we get and these things are not generally not known or or some of them you can do or maybe all of them you can do with very generic MPC methods which are extremely expensive and are uh have a cost which is relative to the size of the circuit Computing what you want to do a circuit Computing exponentiation is inas not infeasible it's close to INF feasible in practice so all of these are

actually uh new constructions and things that we couldn't do beforehand and all of it just with this very very simple primitive called an exponent vrf okay so now you can go to sleep because as long as I've convinced you that it's an interesting primitive and it's worth while researching it's going to do all these things for free I've done my job and and I can leave and we can we can finish right now but because they gave me an hour I'm now going to drive you nuts okay so I want to spend a while talking about simulatability um because I think it is important and uh I want to discuss the difference between simulation based definitions and game based definitions and what we can gain why we what we gain if we can achieve a simulation based definition and it is harder typically to do but in

many cases we can get it okay so what's a game based definition a game based definition we have a very specific task it might be signing it might be decryption but it could also be many many other things and uh we design a specific game that expresses the security that we want for uh this specific task okay so we have an CER who can interact with oracles that participate in the signing and then they have to Output a signature on some message which wasn't uh hasn't been agreed to sign that that's this is the standard type of definition if you go back to the uh non interactive protocol world when you're defining signatures

you're defining encryption uh this is a game a game essentially a game based definition where we set up a game where I have to try and distinguish between encryptions or things like that uh for encryption specifically it turns out it's actually equivalent to semantic security which is actually simulation based definition in simulation based definition we do something very very different think about an imaginable Ideal World with a trusted party who will compute the function whatever function is that we want to compute for the parties and then we're going to compare our real protocol to this ideal execution this ideal execution the parties send their inputs get back outputs and that's it and we want the output distributions to be uh uh indistinguishable or essentially the

same and so for threshold signatures you would just Define a trusted party that would for example get key shares and then and then sign on the message or something to that effect and because in the ideal world the adversary can't do anything then like likewise in the real world that's what we get one of the rationals for using simulation based definitions is that a very simple and clear ideal functionality um is a very convincing uh security definition so if I have a simple IDE do functionality which says parties give me key shares I verify that they're correct uh relative to the public key that they also sent me

I sign on the message and send back the signature then this is very very convincing I understand exactly what I'm getting over the last uh decades uh ideal functionality sometimes are no longer very simple you can see ideal functionalities themselves which are half a page to a page and they enable the adversary to interact because there are some things otherwise are very complicated if it's simple still simple and it's easy to understand that's fine when ideal functionality start becoming very very long then part of the justification for why we want this type of definition maybe we're losing a little bit but the original motivation was that we want to have something where we don't need to work hard to Define security each time and now we might seem

that okay we understand our definitions very very well but actually definitions take time to be understood and we have definitions of encryption and signatures and other things in the beginning looks fine and actually needed to be refined and if you have like an ideal based ideal model based definition then it's very very simple but there are other advantages as well but that's just one thing I wanted to point out okay so going a little bit more in detail the idea of the ideal model is that this is the best you could possibly hope for or to achieve so you have an Incorruptible trusted party doesn't exist in the real world but this is the ideal World many things we can do in Ideal World we have World Peace even in the ideal world uh all the parties have uh ideal private and authenticated channels between

themselves and this trusted party so they will send their inputs to trusted party over these perfect channels nobody can interrupt or E Drop The Trusted party computes the output correctly because they are trusted and incorrect corruptible and sends each party their output back and that's the ideal world so now words what can a party what can adversary do in the ideal World they can choose their input that's all by the way that's important sometimes being able to choose your input uh freely as every you want as as whatever you want can can be significant to security but that's the only thing the adversary can do here and not only that their input that they choose they can they cannot they can only choose before they've seen any output they can't see the out see some

part of the output and then choose their input that's the only thing they can do in this ideal model so this this Ideal World is fantastic and we can clearly see that if each party holds a Shamir sharing of for example of a private key and all they do is send it to the trusted party who reconstructs Compares it to public key and signs that this protocol will reveal nothing uh about the signing key and forging a signature in this model will be the same as forging a signature as as standard on signature okay so the ideal model actually just computes the functionality in the same way or the signature in the same way that a standal on signature signer signer would and this goes with the philosophy that what what does NPC

in general do and threshold signing is a specific example of MPC the what NPC said doesn't actually doesn't say anything about the security of the function right if you're doing NPC to compare DNA and output some you know some properties of DNA compared between two people MPC doesn't tell you anything about whether what that reveals about you right you can do secure MPC for example for two people to compare their salaries or to Output the average of their salaries you can do that you can use NPC to compute the average of two people's salaries it's a really dumb thing to do because given my salary the average of two salaries I know the other person's salary right NPC doesn't say

anything about if the function reveals anything what it tells you is that the process of computing the function reveals nothing so if my trusted party if my ideal functionality computes the the the signing algorithm like a standalone signer that means that the fact that we're using this potentially complex interactive protocol with people sending messages in it just looks exactly like as if I had a standalone signer in a secure box okay this is also by the way if you want to one of the things that using MPC if you've already built it is actually quite easy for for engineers because what you tell them is you want to Define define you want to

design a secure system that does something here is this Ideal Box that computes this thing so just pretend that you have this secure box this secure Hardware that does this thing and now you can use that to build your system the fact that you're actually not using any secure box and the fact that this is an interactive protocol with parties holding different shares in different parts of the world makes no difference whatsoever okay so that's the the Paradigm of the ideal real model and then we say that a real protocol is secure and this is of course not a definition it's the intuition but if it behaves like an Ideal World execution or stated differently the secure computation the protocol will emulate this Incorruptible trusted party

formally we say for every adversary in the real model corrupting a a certain number of parties there exists an Ideal World adversary who we call a simul L but that Ideal World adversary is just corrupting the same parties and working in the ideal model and interacting with the trusted party but the output distribution of both the honest parties and the adversary in the real world and Ideal World is essentially the same so if in the ideal model the only thing the adversary can do is choose their input then also in the real world that's all they can do and as long as that doesn't make any difference to us then everything is fine so this is the definition the simulation based definition why what are the advantages of using of a Sim using a simulation based definition I mentioned one beforehand that if I Define the ideal

functionality very cleanly and easily then I have high confidence that it's doing what I want whereas game based definitions can become complex because their complexity grows with the complexity of what I'm doing okay that doesn't mean you can't have a good game based definition of course you of course you can and we have many very good game based definitions but if you look at for example the game based definitions around password uh uh password protocols they're much more complicated than ideal functionality for a password protocol okay much much more complicated there are many more things you need to take into account and that's true in many other things as well but that's one Advent the second advantage and this is the one of the most significant or if

not the most significant is composition when we use UC security and and it's important I've seen people make this mistake simulation based definitions is not the same as UC security right we have also simulation based definitions for standard on protocols which implies sequential composition but with UC security or Universal composability it's a specific definition which is simulation based then we have the guarantee that the protocol remains secure no matter what other Protocols are running together concurrently with that protocol and with game based security you you do not have such guarantees typic I mean it depends on your game based security but your game based security uh uh definition can and

should take uh concurrent composition into account but it can only take into account concurrent composition of that protocol or something called concurrent self-c composition so if I'm running this signing protocol many many times then we want to make sure you can't forge a sign signature even if you can uh concurrently interact in multiple protocols at the same time and try to steal messages one to the other or do whatever you want I can give you that guarantee and good game based definitions for threshold signing will certainly take conc current composition into account however what happens with other protocols do I have a guarantee that running this protocol over TLS channels or next to an I'm running a schnor protocol next to a different ecdsa

protocol can I say that everything is fine maybe that other protocol will somehow ruin this protocol so in general you cannot say anything when you're thinking about threshold signing you can say something but it's a little bit weird and I don't really know how to I don't myself really fully understand what exactly is going on here but I'll try to go through the the thought process with you so let's think about a world where everybody has a fully independ all keys are fully independent what that means is that my ecdsa signning key is just a random key and not dependent on anything else in the world and if I'm running an ecdsa protocol and a schn protocol uh then my

keys for that are fully just complet truly random completely independent keys in that case what I would argue is the following thing okay so let's assume that running this ecdsa protocol or other things together with this schnor protocol somehow ruins it that's the case since all the keys are independent then now I'm going to play a game where I choose all the other keys in the world except for this one key and now I'm running them all concurrently but what is it concurrently everything else I'm just running internally because there is no other protoc protol and at the end if I can break schnor then now I can break schnor when it's just schnor and nothing else so I can make that argument but can I say something about

the simultaneous security of ecds andore not really many can I can say that I can simulate the whole ecdsa world and the schnor will be fine and I can say I can simulate the entire schnor world and EC ecdsa will be fine but can I say so I couldn't Forge a signature but could I say something about can something strange which is correlated between them happen I don't know I can't really claim something about simultaneous security across them mall I don't really know if it matters but if there are fully independent keys I can't I can say something here but it's it's not all there that that's that's all I can say it's a little bit weird and I don't really know exactly what I can say maybe it's interesting

for someone to do that and go through that process and say what we can actually say in such situations but with UC security I don't care and even if I'm using dependent Keys it's fine what you secur tells me is doesn't matter what else you're doing and even if the keys I'm using the same key for Shar cdsa which is you're not allowed to do that right then then what I'll do is I'll get the same level of security as if I used the same key for ecdsa and schnor that I did Standalone so the fact that coming back to the previous Slide the fact that I'm doing an interactive protocol makes no difference just think about the security as if I had stand Al own executions going back to the concurrency issue if you just have a game based

definition and a security proof it's not clear that you can handle an adversary that nests a bunch of sessions right no that I mean your Game based definition has to has to take that into account so any game based definition that respects itself will consider a concurrent game and if you go back to the game based definitions of uh of um rway and for key exchange who was it it's fill in someone else yeah and me here even the definitions in in the early 2000s that did this they they were concurrent definitions they had these oracles for the different executions and you could call each Oracle and each each execution had a different instance and these were stateful oracles so concurrency being

built into game based definition is not a new thing not a new thing at all but it's absolutely essential yeah the like objection to composing game based security is that it's weird uh is like I think I think that's fair but I'm curious if you have real examples no it's not that it's weird I'm saying that you can you can formally argue concurrent self-composition within itself but once you're adding other things then you don't you don't have anything formal really can say you you can you could formally argue that my schnor signature is fine as long as it's an independent key of course and I can separately argue that my ecdsa signature ass signing signature is fine but I can't really argue them simultaneously

does that matter or not I don't know but uh certainly formally I can't say really what I want to say in the next slide now when I talk or in a slide when you don't have full independent Keys then I can say very very concrete things that's what I want that's when I want to get to in terms of the reduction in a simulation based definition and okay here I'm Li here I'm sort of lying a little bit because depends on your game based defin on your simulation based definition there are two flavors one flavor which is the one that I personally prefer is where the the ideal functionality The Trusted party computes the signature scheme so it computes schnor or it computes ecdsa there are simulation based definitions which is what ran kedi does and Nikos

also does where the signing functionality doesn't comput schnore it computes some ideal signature which is you give me a message and I give you a random or an arbitrary string unique string and say that's your signature or sign to that effect I'm not talking about that flavor I'm talking about the flavor we actually compute the ecda signature or just compute the schnore signature in that case I don't care if ecdsa is secure or not and in fact in my job I really don't care if CDs is secure because Bitcoin chose to use cdsa and that's bitcoin's problem they didn't ask me it's not my responsibility what's my responsibility my responsibility is that the protocol that I used to compute that signature won't make it any

worse right it won't break things it'll only make things better well now make it that I have the the benefits of protecting the keys and and threshold approval and all those sort of things so when in in a game in a simulation based definition I'm reducing to the actual signature itself because that's what the trusted part is Computing in a game based definition I want to stress depending on how the proof works you may be reducing either to the signature scheme but you can also be reducing to the underlying hard problem and not the signature scheme itself and there is a difference and there is a difference with that okay and again it depends the game if you just see the game based

definition you don't actually know you'd have to go and have a look at the proof with ecdsa this is a very big problem because we cannot prove that ecdsa is secure so any the proof should really reduce to ecdsa and and and you you know there are certainly proofs like that and and uh and and uh in that's what you do because you can't prove itq with schnore you you actually have to do redo forking lemas and all those sort of things and and there there is a price to be paid for that in terms of complexity there's a price to be paid for that in terms of the tightness of reduction sometimes and also there's a very slight I would say it's an Epsilon advantage and an infimal Epsilon Advantage where maybe schnor is

secure but but uh the actual assumption or being used is not which is not it's not you know it doesn't make any sense actually but but you can talk about those sort of things as well but this is a difference between them I I I'm not sure if I fully agree with this weaker um I mean except for the comp the compossibility that this is very minor this is more about a difference than it is right but I mean like I understand what you're saying oh you're going to I'm I'm thinking about my my paper where we showed that even if you bias the the key distribution you can still schnor is still fine because but at that point like the forking LMA and all of that is

already there right because if I'm assuming schnor the forking LMA and all of that complexity is already there what's the problem to bring it back into the reduction of the protocol in a simulation based definition you're saying the protocol is fine and all that complexity is in the proof of the underlying primitive you think there is a difference between assuming that schnor is secure and um and and proving my protocol secure under discret log with a complex forking Lemma because firstly these are complex and subtle and you can get them wrong but second the question is why do you think schnor is secure do you think Shor is secure because because discrete log and random

article do you think it's secure because been around for so many years that it's secure personally I think that ecda ecda is secure is because it's been around for so long not because of strange proofs that in generic group models that don't really match well with ecdsa that don't convince me at all I think that at some point when a primitive has been around for so long that the Primitive itself we have we have a certain confidence in it which is somewhat independent of a proof which which has some idealized models possibly inside it maybe yes maybe not with schnor I agree with you it's much more minor with things like ecds say it's more significant but this is where it's really really important and I think the biggest reason why we should look at composition the other things really pale in comparison so with independent keys I

said it should be okay because I can simulate everything except for this but what in the real world are Keys truly independent okay so what happens if I have a neonic I have 16 words that I use for my key but I have an ecdsa key and a schnor key and a BLS key so I have 10 words that are the same and six different words for each what is what about my proof of security Now with a game based secur based definition I have no guarantee whatsoever I cannot say anything at all about security with a simulation based definition I can say that it's as secure as if you did that with local computation so if you took a BLS signature and a schnor signature and an ecd signature with with an overlapping pneumonic bad idea by the way but if you did it it's the same as

what happens in my interactive protocol okay what happens if I use a related password to derive keys or even make it simpler just just it's even not a related password I use you h 53 exclamation mark for my password to derive a key for ecdsa that's all I do is that secure I don't know it's beit weird right I mean I'm hashing it so I'm guessing that that maybe I could say something like it relates to the entropy or we can't say anything really about the security of ecd say for this or for schnor you can't and your foring L will completely fail if I did that what I can say is that my NPC protocol my threshold signing protocol for that key will have the same security as if you use a local

computation in this related key scenario do you also have to redefine your IDE functionality to have this no I don't need to because Universal composability does it for me for free I'm not fully understanding uh so let's say we take extreme examples we're running a snar signature and we're running a ideal functionality of schnor and then a different protocol we're just we're just revealing the secret key yeah so that it will be the same the the fact that I'm using the the fact the um the protocol If instead of using an interactive protocol for schnor you used a local signing local signing it would be the same so if you have somewhere else which is revealing it then it's going to break

that as well but the the interactiveness of the protocol is not harming you in any way whatsoever that's what I can guarantee so that that's and that's a next a very very big Advantage because in real life most blockchain keys are not independent if you're using HD keys if you're using bip derivation they're not independent they're not independent for hard derivations if you're going from parent to child in the tree and they're not independent for normal derivations so that means you would actually need to have your game based definition include what's happening with bip 32 or a different derivation method You' have to take it into account in order to have

uh in order the security to carry across but that becomes very very difficult to do and if you have a simulation based definition then it's for free whatever security get normal derivation is what people are doing then if I'm doing normal derivation then I get the same guarantees this and this is a very very very big Advantage because in the real world keys are not truly random people can use passwords to derve keys in the real world keys are related because we're doing bip derivation and many other things happen and when I have a simulation definition then I'm covered in the sense that you chose to use a bad key okay I'm just not making it any worse whatever you have that is uh you you maintain that same level of security and the fact

using NPC is only going to improve things okay again doesn't mean the game based definitions are bad and there are some cases where we can't get simulation based definitions and we have advantages or for efficiency other things in game Bas definitions and we can get other things it just means that there are significant advantages to simulation and I think if you can get it then this is something which is preferable having done all of that now let's get back to the topic at hand so we have a set of parties and they want to they want to generate a key I want to do it in one round so one round sounds very challenging and I'll go through and see what the problems are because if you get this then all the other applications are sort of obvious okay so what's what's the aim the aim is for each party to get

a random Ki uh which is their random uh secret uh key a secret share share of the secret key and capital K which is the public key which is the sum of all the little kis times G that's the aim that's my aim in distributed key generation there are different variants for different protocols but let's just take this basic variant here's a really bad solution a really bad solution is everybody chooses their own Ki computes KI times G and sends it out why is this really really bad because a corrupted PN can wait to see everybody else's shares or capital K I can choose a secret key that actually knows K and capital K

which is K * G and then can just compute KNN to be K minus all the other parties public shares and then if you do that what happens is the result of this protocol will be capital K where PN knows the entire private key okay is that problem clear so I'm actually able to learn the entire private key if I do this type of key generation so I can't can't just send out something and um but if I want one round how can I prevent this type of thing where I can fully determine the private the private key so attempt to to fix this bad solution is to say that I'll make each party provide a zero knowledge proof of knowledge of the discrete log

of what they send why does that solve the problem it solves the problem because PN set KNN to be something which is K minus all of this stuff and PN could not know discrete log of KNN so once I forc PN to add a zero knowledge proof of knowledge I now solve that problem and you can't do this attack but a corrupted PN can still wait to see everybody else's public shares and can now choose multiple little knns so that the sum of them all the capital K has some property for example the third bite is all zeros now Rosario says that I can prove that schnor is okay if uh even if you can do that sort of thing but um you

certainly couldn't do that with ecdsa because you can't even prove that EA is secure at all so you certainly can't claim that ECA remains secure if the third B well maybe if the third bite is all zero because the probability is 1 over two to the 56 but you can but but you uh can't claim that it's the same as original signature and most important it's not simulatable so if I want the advantages of simulatability that I said then for simulation to work it means I need to get a capital K from the ideal functionality and the result has to be that K so ideal functionality chose a random little K competed to capital K which is K * G I have to make the output look exactly like that otherwise I don't have any of the guarantees of simulation

that I mentioned beforehand so once I'm able to bias then I I can't do this so what's the solution the solution generally is to commit an open so I commit to my Ki and then I open and as long as the commitments are nonm valuable so I can't make my commitment depend on somebody else's commitment this guarantees Independence between them and then we can uh uh claim that uh um that you're unable to bias the output but it's still actually not simulatable because to get simulatability I need to be able to extract from each corrupted party their their rent their share that they're using in order to understand that let's look at what the ideal

functionality would do it would allow the corrupted parties to choose their own random input their own random shares or or arbitrary shares actually and we then choose the honest party shares at random and then output the sum of the result that that's what the ideal functionality would do you could by the way define ideal functionality where the trusted party chooses the random shares for every party you can do that that will be much more complicated to achieve and doesn't give you any security Advantage so the trusted party gets the inputs from the corrupted parties and then chooses the random inputs for the honest parties that means I have to be able to extract the honest parties inputs and in order to simulate that I have to be able to extract and therefore I just add to the commitments also zero

knowledge proofs of knowledge that I can extract from and then I'm done okay so that's one approach to generally get distributed key generation and the simulat this is by the way coin tossing or what we used to call augmented coin tossing it's exactly the same thing um so really stuff that goes back many many years so how would you simulate you receive the adversary's commitments and the zero knowledge proofs of knowledge you can extract from the commitment Exum assuming an extractable and equivocal commitment so I extract the values and I extract the secret values I send to The Trusted Party The Trusted party sends me the capital K and then I just choose random Capital KJ values for the honest parties so that they everything sums out nicely and I open and and and I

equivocate the commitments to be to those values and give simulated zero knowledge proof so I just lie about the honest part's values but what's important here is you can see in the simulation process I need to have the adversary be fixed or be uh committed to their values before the honest parties provide theirs which is intuitive because that's exactly what prevents biasing the output but in the real world it's the opposite because we're assuming a rushing adversary adversary sees can see the honest part's values first so how do we bypass that by using commitments that so we can open and extract from and so on and so forth so one uh mistake I've seen many times in simulation based multi-party proofs is around uh extracting from

NX uh so I guess like in looking at this you're assuming that NX are extractable in a multi-party case no I said I said ZK Pock Z zero knowledge proof of knowledge it has to be it has to be a nonextractive Zer proof of knowledge you can't extract if it's not a proof of knowledge okay so if you're doing if you're taking a sigma protocol and you want to be concurrently secure you need to the fish Transformer not F chamir if you do fet Shamir you'll get a simulation based proof but for Standalone or sequential composition not for concurrent composition but there is I think one situation where if the adversary outputs all the sigma protocol proofs at once then we can still extract

from many instances I've seen it in this shoe and Bon book where this if the adversary does Sigma protocol one after another and we need to extract one at a time that is problematic that they say but if the adversary outputs all the sigma protocol proofs at once then they say that it's exra yeah but I think it's probably going to be what we call again self-composition maybe they have a specific proof for when you're doing that what happens if now I'm running this with other arbitrary other protocols where possibly have related uh value used then again I think you'll have a trouble proving that I see so in in the full simulatability that that will problem so we use fish that's why we use fishland transform and the fish

trans we have a paper about it now online you can take a look and and the cost is very very small like the proof of a discrete log is less than half a millisecond so it's not significant um okay so what's important here is that in this way the simulator is able to cause the output of the result to be um exactly the the cas the public key that I got from from The Trusted party and that's why we get the simulation so I'm able to bias the output to be whatever I want as a simulator not as the adversary and that whatever I want is what I got from The Trusted part and that guarantees that it's uniformly distributed and has the correct uh um distribution okay how can we do it in in

two in a single round It seems impossible to in a single round because in a single round the adversary will always see what the ad honors part is sent beforehand so if the adversary always sees what the honors party sent first the adversary can always bias their their their output so how can it be possible to do this in one round and the answer is only if the adversary has no choice over what value they're going to give and if the simulator even knows ahead of time before the protocol starts what value the adversary is going to give and how can we achieve that simple useing evf how does that help in the initialization phase we're going to do one initialization phase and then afterwards it can generate as as many keys as we want with just one round for each key in

the initialization phase each party just chooses an evf key here I'm calling I'm adding a tier to the evf key to distinguish it from the the dkg keys and then what happens is given a non and I said we need a non or Tim stamp because you need something to distinguish this execution from another execution otherwise clearly it's impossible so I'm given a non or or the current time and each party will just compute the evf on that value and will send the capital Ki which is the result of the evf comput computation together with the proof and then you just add it all together why is this simulatable the reason is that the simulator knows these Ki Tia values

because it extracted them from initialization phase and therefore it can just compute each Ki of the corrupted parties before the protocol even begins and can send that to The Trusted party and get back the capital from The Trusted party because the simulator already knows the Ki values of the corrupted parties it can just choose the KJ values of the honest randomly like we said beforehand can lie about them being the correct EVR Val values for the honest Parties by cheating in the zero knowledge proof as part of the evf definition and then we'll just send those and we're done and the output is going to be the correct output so we bypass this problem with the adversary being a to bias the output by making sure that adversary is

committed to what they are going to Output ahead of time they have no freedom of choice so they can't wait to see what the honest party send and then do something different is that clear so you're also assuming the CBRF keys are extractable using the which the vrf keys yeah that I wrote that in the initial definition I had another bullet there where I said and you can extract the private key during the initialization and you add a proof of knowledge for that mhm you I think you're pushing one round to the initialization once and now you can generate millions of keys each one using only one round so what about thre threshold EKG um you can also do it the idea here is to just do

the same thing but to generate each coefficient of the polinomial using the evf and then you can get like type of Felman vsss uh for a polinomial and add together and do dkg what about two round simulatable signatures and now everything becomes much easier cuz it's all just the same thing over and over and over and over again okay so what what are schnor signatures we have a public key uh PIV key x a public key Q which is X x g you choose a random nons K I know that K and X reverse here but everybody gets mad at me for doing this but my belief about notations is as follows if someone's using notations which I really really can't stand and I think are really horrible then I'll

change them but if everybody's used to certain notations I don't like to change it so if you look at Wikipedia or in all these other sources about how people write ecdsa for some reason K is the nons and capital r is the result of computing K * G that's the way people write it so I sort of keep writing it and now probably in 10 years time people say yeah I hate the notation but you would have write it that way it's ready so I'm just going to leave it and this way we perpetuate terrible notation so um so so I choose a on K I write R is K * G and I output K plus the hash of the stuff times x that's the signature so how does aor signing protocol work where we generate shares of the private key in some way we generate a non in a shared

method as well where each party somehow we generate these Ki values and then then it's just a linear function which is why schnor is nice because once we have that I have my share of K the Ki I have my share of X the XI and I can just add them together and then we can I can just compute my local equation and we can just add them all together okay so that's that's schnor signatures and and as uh uh Chelsea mentioned the challenge here or the interesting part is really this step here how do we generate this nons in a way that will be as we want it to be and and uh as I'm sure you can already see in order to achieve simulation what that means is I need to

get a signature from The Trusted party and make the output of the result be that signature that signature includes either explicitly or implicitly the capital r okay the Nots the public Nots so R equals K * G so I need to make sure that this step here where we are where some generating this nons the result of this will be what I got from The Trusted party well I'm sure you can all see this is exactly the same problem as dkg so we can do exactly the same thing uh and solve it in that way so how is an Nots generated if I do a single round protocol uh uh using other methods where party send their nonsense and we somehow combine them in a way with certain

tweaks like in uh some some twoam protocols then I can prove that this is a secure signature scheme but it will not be schnor it will not have the same distribution as schnor it won't have the composability guarantees because I'm not able to make it actually be the same r that I'm getting from the external trusted party in two rounds I can generate it using commit and open but then I get a three round protocol so to get a two round protocol I can just use the evf and I do exactly the same idea as in the dkg so I can simulate to get the r and now I only have two rounds that makes sense and here it's not the the evf is generated during key generation so there's no hidden additional round or anything like that

in key generation we generate the evf key as well and then each assigning uh um protocol we have only two rounds in the one round thing you use a simulation extractable NK for the first message for the um it can't just be like a simple snor no because in the initialization I've extracted the private key of the trust of the uh the private keys of the corrupted party so I'm able to I don't need to extract I can compete it myself ahead of time so during uh evf evaluation I only need if I'm using a zero knowledge proof it only needs to be sound I only need a proof of knowledge during the initialization phase so therefore I could use if I was use if I had a sigma protocol or

something like that I would only need sound and I could use f PR here okay so why is two round signing important not necessarily important to be honest uh but I think it's even an interesting type of feasibility result well I don't know feasibility result might be pushing things certainly two round protocols for schnor and for e or this is schnor in the past were all not simulatable but you do have these papers which are using generic techniques can do to round MPC but they all uh work with a circuit so I could State this is a feasibility result the first protocol for two round simulatable signing with communication that is small in the circuit size but I think it's

interesting I think it's interesting that you can do this and and and goes down to understanding of what we need for similar ability there is a place where two round signing does make sense and this is your question yesterday Abby and that's if you have a cold element let's say you have five parties four of them online and one cold element that you have to go into a room and and do a computation then you have the four parties computer first message you can take them all walk into the room plug it into the cold machine they will then compute their first and second round message then I go out and I can give it to the others and they can finish the protocol so that is a place where two round can make a difference if that is a model that people are using whatever

deterministic signatures well what I showed you is actually deterministic as well because the input that we use the evf for signing is the message and if if we use the message we use a nons as well then we can get probabalistic but if we just use the message as the input to the evf I'll now have deterministic signing because again I'm forced to use that message there is no other message that I can use there's no other non share that I can use and then this enables you to prove security and show that you have deterministic signatures as well and the cost of this protocol will be comparable to the cost of the evf so if the evf is very efficient then this is efficient and the VF constructions we have all not sure how much I'll sure later are

reasonably efficient so we think in back of the envelope estimates between 5 and 20 milliseconds threshold signing so for threshold signing it's a little bit challenging because the way I presented evf it's it's it's a local primitive that each party has their own evf so I have different sets of parties they're going to now be signing uh they're going to have generating different nonsense so you can do this by including the set of parties signing into the evf this will be secure it won't be deterministic if I want to get deterministic signing I'm going to construct a threshold variant of an evf something which we did not do okay what additional results do we have notice that in this protocol that I

showed you from multi party schnor um the parties who signed also actually can generate a proof that they're the ones who signed because the evf computation has a proof that this is what the nons is made up of so if that's of Interest we can also do two round ecdsa signing uh which is simulatable and that's certainly something which uh uh is uh even more significant than schnor because two round ecds say even game based we don't have understand the definitions because standard assumptions because you would need to reduce to e to the problem that ecdsa uses but there is no we have no proof of security for ecdsa so

ecdsa uh two round we don't even have for game based definitions understand that assumptions so but here exactly the same thing you can take a Lind 17 and you can plug in the uh um the same idea for generating the nons and you get a two round protocol as well bip derivation this is the way bip derivation looks it's this tree and you can use and and it's based on hmax Sha but we can do this using the evf instead in order to the derivation of each step what are the advantages of this firstly the public ke is verified iable so if I'm giving you a key if I'm giving you a key which I'm deriving in in uh in bip32 you know that it's derived correctly why is that important let's

think about this case we want to do key derivation in MPC then I want to make sure that it's truly being derived from the correct private key why because I'm backing up the private key once and I want to know that all of the keys I derive are secure are going to be backed up because of I backed up that single key in a malicious environment an adversarial party can just lie about the way they're deriving the key it will look indistinguishable to you and now what will happen is you won't have any backup for all of your funds so we want to make sure that you can't do that and you can solve that in an NPC friendly way using an evf as well exactly the same way because it's just a pandom function which is how you're deriving so how can we construct EV RFS assume we

have an encryption sceme which has a lot of a bunch of nice properties okay uh basically you can a random Cipher text is a good Cipher text it has a good distribution you can prove properties that are efficiently about Cipher texts then we can do the following thing you can create a key pair for the encryption scheme and then given an input it's going to be in the random article of the construction given input X I will hash using the random Oracle from the input to the cipher teex space so now I get a random Cipher text I will now decrypt that Cipher text to to get some value Y and then I will compute y capital y = y * G and generate

a proof that the decryption what's inside that Cipher text is the discrete log of capital Y so can we do this efficiently with paer we actually can with payer you can certainly hash to a random Cipher text you can decrypt the space is not zq the order of the group but you can we can fix that without too much difficulty and you can efficiently prove that a cyhex encrypts a discrete log of a given value because of the homomorphic oper homomorphic properties of paer that proof is actually very quite efficient okay so this is not lightning fast it's like tens of milliseconds but you can do this yes Abby can you just go back one slide

what was the last proof you need to make so you decrypt uh H ofx that gives you y you compute Y and then you prove that the hash of X which is the cipher text encrypts the discrete log of Y it's the same proof in Lind 17 in key generation you're proving that I'm encrypting the correct value okay what about using ddh we can do this to ddh as well and the idea here is to use the uh the prf the well-known prf which is just uh H is a random Oracle going from strings into the group and just K * h of X is a is a uh is a sud function based on the ddh Assumption it's also a vrf if

you can because you can prove efficiently um that the result is if you on tole and then everything is fine but the problem is that for this this output here or capital Y here is actually um the little y we were talking about beforehand we want to give that times G we want to give the exponent of that okay so here we can define a source group in a Target group and we want the order of the field for the Target group to be the order of the source group so basically we want to generate an element in this source group and the x value will actually be of the order of the target group so that's the way that we can take the output of this of this prf and use that as the scaler

for uh uh the target Group which is what we're going to be using for for our signing for example in order to evaluate we're going to compute the original prf in the source group we're going to take the x coordinate and multiply that by G and that's going to be our capital Y and I'm going to prove in zero knowledge that this is correctly computed and the idea for proving this is to note that the the challenge is proving some value of k x x and th that value we can actually break out break down into a number of just additions addition an addition per bit of the scaler or the exponent and um once we once we can write that

out and you have to write that in a careful way but you can actually write this to be a rank one constraint system and then you can use bullet proofs in order to prove this okay potentially you can do other things as well but that's the way they're able to do that by looking at this uh once you break it down to the equation litic of equation for addition you can actually just Express this as the R1 Cs and get a bulletproof to come out of it okay this if of the envelope tells us 5 to 10 milliseconds maybe it's a little bit more uh but we actually have to implement this in check so TimeWise that's actually quite reasonable in fact it's very reasonable I'm looking for a nicer construction something more intuitive simpler maybe they don't exist

maybe this is good enough and fine and we'll implement it and we'll be happy with it but I think that there're these the applications are very natural they're very strong the constructions are I think they we we should be to find something simpler so that's what I'm hoping that you'll all do uh by the way that evf is actually implicit in music DN our construction is a little bit simpler and and there it's implicit in their construction but that's what's happening okay so what open questions do we have uh first you want simpler and faster constructions of evf is 10 milliseconds not good enough uh well if it's 10 milliseconds maybe it is good enough we have to we have to check but uh simpler certainly is better and for examp example if we wanted to

propose this as a bip standard as a as an alternative to bip 32 I think it's probably complicated for that we want key threshold evf constructions this is the most important open question in my opinion because if we have such an evf where the the sud random function computed on this sum is the same as uh as that then we're able to get proper threshold variants for all of the applications that I said and it's not that the Ser function we have doesn't have this it does but everything we do afterwards which we of proving the uh the way we prove all of the uh um the proofs the these do not have this

property so that's something which has to be which we need to do as well and I think that a fully multi fully similar multi party protocol not two- party is a multi-party for say that also has to be done and we don't have any example of that in the literature so that's also worthwh well doing and if there are so many applications there are probably more as well so I hope that's also something that other people will find uh thank you very oh yeah I think that's enough given my time so thank you very much so you didn't talk about this in this talk but I looked at the paper and it seems like the EV evf is proven using games a game based definition and then the applications are proven using simulation

based so maybe you can talk about about like why is that not weird as opposed to like comp so that's actually the standard uh Paradigm working cryptography if you look at an encryption indistinguishability is a horrible definition why does it convince you so yeah what in this tells you if I give you an encryption to m0 and M1 you can't see the difference all right but but but does that mean that if I'm encrypting my work contract you can't tell if I'm earning above 100,000 or below 100 ,000 I mean why is that even convincing to you to me it's not convincing at all I'm convinced because there another definition called semantic security which by the way is a simulation based definition and we've

proven that that there's equivalence between semantic security and indistinguishability so this is a very very standard Paradigm in in cryptography and we did that here as well so we had a game based definition for evf because that makes it easier to prove the security of uh um evf Construction we Prov that equivalent to a simulation based definition of evf because that makes it easier to prove the security of of applications and that's the best of all worlds having said that having written the proof some of the applications not sure it's that much easier but the Paradigm makes a lot of sense because uh you can now use like an ideal functionality in improving

applications it's nice and clean and the game based definition uh helps you to make prove your constructions more efficiently oh just a small question how do you usually go about proving the equivalence of a game based definition and a simulation based definition just in general so I mean okay if you want full equivalent I'm actually in order to get the benefits of what I said you just need to claim actually One Direction which is that if it's something is secure under the game base it's also secure under the simulation based the other direction tells you that you haven't over constructed you haven't worked too hard to construct but uh you just need to prove that given something under this definition I can prove it secure under this and then vice versa curious about the bulletproof component

that you use do you need succinctness from that or this is not no we don't uh the only thing we uh it's a question of efficiency in interactive protocol so it's not going on to any blockchain or anything we don't care about sixing this do you have two round threshold signing or yes we have two round threshold sighting for two- party ecdsa oh not for multipot CSA uh and we have for multi partty schnore in terms of threshold it's not a perfect solution why because you need to the set in advance or or you need to do like a or you need to do no or you need to do this

thing where you um you uh just in the first round you try for all subsets so for a small set of parties it's like the PVSS type construction it blows up so it's not very good for deterministic it's not true it's not truly deterministic because if different subsets will sign you'll get different nonsense it'll be secure you don't have any security problems but it won't be truly deterministic for DSA the problem is the inversion no no we have to again we just didn't I mean the two- party protocol the two- party that's fine is easy the multiparty just didn't do the I mean it just the the the only candidate protocol I can think of is ab's protocol because

three rounds if if if you can collapse the first two rounds into one because you're doing non non derivation then it should be a two round protocol but I didn't do that work is that the case with your protocol Abby no but but you can the first message is independent of the message no no that's a different thing once you do that you also lose simulatability because you need to claim that uh for ecdsa it's it's just as secure if you get the nons and then choose the message no so that's the nons doesn't get revealed in that first so at least our proof strategy for the pipel mean that yeah uh is just that you start

a session you start the next session uh as the last message of the previous session okay maybe but in any case it would it means that your C your protocol is not a candidate so it's coming out with a protocol that will that you can do non generation the first round then the the second round I just don't know the protocols that IA for cdsa are all more rounds than three and so I don't know but I I my intuition believes it should be should be possible but I could be wrong been wrong many many times in the past of intuition so I guess what is the if you're actually pinning the nons what what uh what prevents how do you avoid the Ros style attacks because the uh um you you as an adversary have no

freedom in choosing your nons you're committed to it you're committed ahead of time and you you're kind of turning EDSA to your advantage yeah yeah you're you're saying that if you're committed and you're using a prf committed ahead of time then you can now get simulatability because I know what the divers is going to do before they actually do it and that flips again what we said to get simulatability I need to be able to uh get the adversary's shares before I I I uh reveal the uh honors party shares and just by committing ahead of time essenti I'm able to do that that's exactly what's going on here and that gives us all of those applications wait wait wait so your intuition is that in any let's say like

an ecdsa signing if you can basically force all of the adversaries to for a given message have a have a specific uh non contribution then your security argument would work out I that's what you need from uh ecdsa it's a b form of what you're saying I also need that the honest parties are going to be Pito random right and not known to the adversary but but I need the yeah I want the adversaries shares in the nons OR shares to be their random shares to be known to the simulator ahead of time so their first message uh basically it should be unpredictable but verifiable yeah that's the trick you're using I guess essentially

okay so that would make a general I mean generically then you can take any three round d C DSA have the randomness committed and like essentially if you just use generic that's why I asked you but un unless you're doing other stuff if you're doing other stuff maybe over three rounds you're starting things that you need for the consistency check I don't know but if you have a protocol where it's taking you two rounds to generate a nons and then you're doing other stuff then you can collapse that down thank you [Applause]