Extractable Witness Encryption for KZG Commitments - Brechy

Transcript

start soon recording so Brey Flor is yours thank you thank you yeah so yeah uh thank you all for being here I will just present uh on this topic that I've been working for the last couple months so it's basically based on a paper um extractable witness encryption for K commitments uh first of all like a brief story of like how this came up so during July we um the part of the research team uh held a um meet up on MPC related topics in in Japan and this

is where Roo came up with this topic that he he has been um working on for a while and uh just decided to share share it with me and see like if this could be built uh to do some something with it so yeah yeah he's a guilty one um basically it's uh everything about this paper which is an implementation of this scheme and also the author was invited for one of the uh I think I think it's like coffee hours uh something like that or learn share sessions in in PSC so there is this video uploaded for those who want uh

want to take a look um and then we realize since this implementation uh has lonic OT as a sample use case that we could actually Benchmark this with uh MPC which is the um library that pis notary is using for for its project so it's a like um NPC tools made with rust and so um um uh this uh o transfer is uh like a important piece of um carbon circuit based MPC I I will talk about it a bit more so yeah uh like in general like

what is uh witness encryption so don't kill me let's let's go from from the beginning like um we can treat encryption as uh this scheme with two functions so we have one function to encrypt a message and we have this uh sep text and then a decryption function uh that uh codes this message and we can recover the original one so um uh like pre famous uh encryption scheme public encryption uh has another step that is a E Generation step so you generate a public key and a private key and then you encrypt uh your

message using a public key and you will be able to decrypt it using uh the generated private key on the other uh side so witness encryption uh basically twists this idea and you perform an encryption uh with a puzzle or a problem um and then you will be able to decrypt this paper text using uh the solution for this uh problem um this is like translated of or we use another words py words here that your encryption is um you're making an

encryption towards statement and you will decrypt using a witness which is basically the solution to this uh problem so um with this encryption uh it's used with MP problems uh which basically means that uh if there is a solution to this problem or if there is a witness this uh can be verified uh efficiently so with a deterministic algorithm uh in in poal time um based on this we can build a relation so an MP relation uh what this means is that we can grab a lot of

instances of this problem in which we can have this uh pairs of uh statement and witness or problem and solution uh in which we can put uh dispair into the relation if the checking uh algorithm returns uh is is valid so basically if you have um a witness that is a solution to this problem uh then this pair can be put into these uh into the relation with this we can define a language uh of every statement uh so you can say that uh a statement if is part of this language if

uh there exists a solution uh such that the um checking algorithm verifies or such that the pair is uh part of the relation so in general a witness encryption correctness is it's is defined for every pair inside the relation so you will be able to encrypt and decrypt your message and recover the original message uh if uh your um statement and witness are are part of the relation and then uh security or semantic security of of the scheme

um it's guaranteed for uh those statements that uh don't have a solution so in other words like um the statement is not part of the language so if if there is no solution for your problem then you won't be able to recover your message or uh here is labeled as um uh encodings for different messages are basically in the stim uh this translates to like uh if no witness exists then the safer text should uh reveal nothing about the message so uh if there is not uh a valid

solution decryption shouldn't be possible um this uh turns us into this direction in which with the encryption is more targeted or her problems were uh determining that uh statement is part of the language or that a statement has a solution um is not feasible without the actual witness so uh witness encryption for arbitrary and Fe relations exist U but these are not efficient uh in this case we will look uh at the specific relation so uh we

will look at witness encryption for kcg commitments um well PG polom commitment scheme uh this is a scheme of uh that allows allow you to commit to a polinomial and then provide proofs uh that you know this polinomial and efficiently verify it so um the most important so the important steps that we will focus on on is basically the verification equation that this is uh what we will use to construct or or

scheme and um So based on this uh equation we have uh two parents operations um that we we can uh efficiently U verify that uh with uh commitment and um a point uh Alpha and then evaluation of this point Alpha Beta uh we can verify uh in the other side with the proof that uh this checks and this is uh not so expensive sorry changing Windows here so we can Define with this um relation we can build a relation out of this uh

in which we can encrypt our messages with this triple um so a commitment uh a point Alpha and an evaluation beta um of our polinomial and then we can decrypt this message with a proof and this will be our language or defined language so um the the this triple commitment um Alpha beta will be part of language if there exists a proof Pi such that this verification equation um checks so this

term is equal to this term now there is a problem with this and this is uh the problem is that for every basically for every triple [Music] um it it there exists um proof that that can verify this check um based on this equation now this is not of course um competition feasible I I mean it's not efficiently um findable like you cannot find this um very easily but then coming back to our security definition for General Windows

encryption uh we see here that security is is basically defined for statements that are not part of the language so statements that has no solution and in our case um they all they all have a solution so this turns into that um we we we cannot build this uh scheme on this based on this relation um with with like General with the general with the encryption definition um taking a step back of how this can be solved or fixed um the paper uh the the authors uh based

the scheme on a key encapsulation mechanism so a key encapsulation mechanism um instead of like encrypting a message uh it generates a key based on uh our problem so we can input our statement to this um Cam and then we will output a key from one side and then a Cy text in the other side we can then provide this cyer text and or proof pile and we will generate another key which if the proof p uh is valid um this two keys will be the

same so this could allow you to perform per form some kind of symmetric encryption scheme based on these Keys um allowing you to perform some encryption some real encryption for messages and so this is the main algorithm for the key encapsulation mechanism um the authors provide a proof in the paper that this is actually extractable um which I won't go over but uh what does uh that being what does it uh why is it like extractable or or what

does this extractability gives us so it basically um uh we we can be safe or certain that if um if you're generating the same uh key I I will go over this but just to Define uh um talk about stability here we can be certain that if if you have a a valid proof then you will have the actual polinomial or so the actual solution uh to to the to this to to your statement so um let's go over the encapsulation um

algorithm so it's quite easy like this is super simple and if you go through the code you will see that it's basically just just this uh couple steps to perform an encapsulation so you first uh generate a random scaler uh that you will use to generate your secret so we can see that uh our secret here is basically the first part of the equation of of the verification equation um so this this will be our secret um we like um it seems like this secret is not indistinguishable from random so we

need to um hash it so our our key will actually be uh the hash of our secret and then we need uh a way to send this Randomness to to the an other party the crypy and this is why we multiply this another term of uh the paing equation um with with our Randomness as well and so our encapsulation mechanism will return we will just receive our statement and will return a or key in our side and then this cyer

text the decapsulation mechanism uh so it has the already um one one side of the pent equation given and then it should has to input the proof pile and then that's it uh the the key will be the hash of the secret which if you can see like if the if this equation checks then both Secrets will be equal and then our hash should be the same for both um with this we can then Define the extractable winess encryption for our

kcg commitments in which we have an encryption uh function that receives our statement and a message and so our first step will be to encapsulate um the statement this will give us our safer text for the randomness thing and then our key and what we do here is simply um use some symmetric encryption for message uh which for instance I'm doing just a plain exort in in my implementation and then this uh Cypher text 2 will be the encrypted message and the decryption function will

just receive the proof pi and then uh this tle of cyer text which one will be used for the decapsulation mechanism uh generating or key and then and basically decrypt the encrypted message um returning the the original message and so yeah this is uh basically the couple functions that uh are the core of the implementation um so kak is the name of of the library and um it's a it's a r

implement ition so it has a very simple layout um with just four modules in which like each module just have these functions so a kcg module which is uh quite like generic uh kcg stuff so the four steps of kcg and I recently added this um FK um algorithm for calculate batch of openings efficiently and then I also uh it also has a way to um create your your powers of tow from a powersoft tower file um that is also cool and then uh the kec capsulation mechanism module

which is the encapsulation and encapsulation functions and then the general Windows encryption modules with encryption and encryption these are the four functions which just one through and then um there is a a uh a new module called back that uh basically is some uh facilitations to work with vectors um so if we have a vector um we can think of uh these values as basically evaluations of a polinomial um at at each uh and root of unity so if if we think of a vector of

something like this then we can perform the inverse fast for transform and convert this into into its polinomial uh coefficient representation the one that we're used to and um so for this uh I create this basically commit function that you can input um an array of values so basically an array um which you have to append a random element because then your commitment uh will reveal like you know if it's easy to think what your polom what Your array

value is then you could calculate the um which one it is based on the commitment so you have to Blind the polinomial in a way and then uh yeah basically to what I said uh perform the universe FB transform um perform the the FK openings for all the proofs and then just uh commit to this polinomial um but the important part of this uh is oblivious transfer so this is um last last topic i w for you more with

this so uh H go so obl transfer uh is a two- party protocol between um a center and a receiver now the whole idea of this is that um you have one party that is the center that has some data and you have one party that is the receiver that uh needs some data from you uh but the the receiver don't want you to know like what data he wants and so you you don't want the receiver to know like any of the other data so the center uh doesn't learn the the choice of the

receiver and the receiver um cannot uh learn what other things are on on your database so um the very simple scheme of this is one out of two transfer so this means that you have two options and the receiver can choose one so this is made uh with um Regular publicy encryption uh in in um Regular like uh all schemes uh so you have both of your messages and then the receiver generates a public uh secret key pair it sends you uh it's public key you encrypt

both messages uh but so in a way that the receiver can only decrypt the selected one you send the crypto messages and then the receiver tries to the cryp both and uh will we know which one is is the valid one like that that is also part of the scheme so lonic aties transfer is basically this but for end messages so you as a sender you um have a lot of messages um it's like performing a multiple uh one out of two um OB transfer but at once so you in initialize your batch of

messages then the receiver uh select all of these messages um this is what uh they usually call a dictionary so it's basically an array of or your all your choices then the sender encrypt all the messages uh send all the cyer text and then the receiver will decrypt all the messages like only being able to decrypt the the ones that they selected and this is the current implementation uh like made in the library so we just have our bullan choices so this is an array of

selections um and we use the CIT function that we that that I showed in the in the previous slide then the sender basically does this so the sender has its uh like all the values uh for the the desired uh data and encrypts uh each one for each possible option so um so then in thetion it has to use the commitment this basically is the finding of this selection so this is how we save um index is basically the index of the

array and then these are the options so if it's zero you will send the value zero this tople and if it's one you will send the value one so you encrypt both messages and you send both uh in the other side we can be sure that uh the receiver will be able to decrypt Only The Chosen message because it has to provide this uh proof for for this uh specific um uh index and so this is how we're certain that um they won't be able to know all the other parts of the database and um

the sender uh like never knows uh what what are the options of the of the receiver so yes that's that's all the presentation hope I didn't take too long and um yeah happy to receive any any questions related to this I I will send uh the links sorry I didn't mean to raise my hand uh I stop the recording now or after the questions I guess we can keep the questions I assume just in case we can cut them out

otherwise you're thinking um I I have one question um well a couple of them but I will just as one theor uh the first is the angle about the vector module then I assume it's just the fact of being able to encrypt and decrypt multiple Witnesses at once but all other than that there's no like I to say a more complex purpose for it rather than this is it is that correct yeah that that is correct it's just so the the vector module uh what it it tries to leverage this uh efficiency gain that we can have if we use plory transform to

interpolate our polinomial basically that's that's basically it sure that makes sense thank you I think yeah thank you Alex for the for the for the talk um I have like a quick question about this oblivious transfer related thing so can you go back a little bit uh sorry yeah maybe the [Music] code yes yes this one okay so um I was wondering uh what is the efficiency comparison of this lonic OD

comparing to something like the OD extension so uh what what is the what is the difference uh Happening Here comparing to the what's the additional steps that required here compared to that you know um the traditional OT yeah so I I think the the most important um part to to highlight about this is that you you can just do one run of communication uh I think that's that's the main thing so when when you uh so you you commit to all all of your

options and then you just put that in the open and then the the center uh basically can encrypt uh the whole database uh and send it all together uh so you don't have to run multiple one out of two OTS uh you can just run um a bunch of them at once um right right right so so senders can be more than one one party sure yes that's true that's that's very interesting thanks yeah I think the comparing to like the the traditional OT

extensions it's going to be adding like the pairing mode pairing operations so that's that's the that's the that's the overhead of this um this scheme I guess y thanks yeah no thank you um yes uh thank thank you uh I have to to review your your latest um works on on on OT I know you're working on OT but I I didn't have the time to to review it yet so happy to to keep discussing this uh so um D oh I don't know if to you had a

question uh sorry can you hear me yes oh uh so I think I missed some parts so uh would you explain me so what is the difference between this witness encryption and uh using like kind of public key encryption so what is why do we use the witness encryption over the public yeah so um like in general uh what um so public encryption has this uh mechanism of of of of like the the

generation of like public private key uh so you you you will always encrypt to to a generated public key um General witness encryption uh encrypts towards uh you you could say a problem so any any problem that uh you you can efficiently find uh uh efficiently sorry not find uh check if if you have a solution you can you can check that this is actually the solution to to this problem and so but the thing with this is that um like uh this last item here General uh with this encryption

relies perhaps more on hard problems where determining that um a statement has a solution is not really feasible without a witness so General uh witness encryption um you you might perhaps be um using a problem that you don't know if there is a solution and this is why uh you have this security guarantee that okay if your problem has no solution then uh you won't be able to to decp your message um so this is uh part of the reason that we have to Define extractability later um but then the thing is that you don't need so you can encrypt something

and and like put it in the open and you don't rely on any um anything on generated from anyone in specific so you you can encrypt something uh so that anyone with the solution can decrypted of course in in in our scheme this isn't the case because in our scheme we rely on someone committing to a polinomial so we need a commitment to encrypt um which is different from General witness encryption uh so like uh so as you said so like in witness encryption case the

uh like unlike the public encryption like the one who can decrypt the message can be like there are multiple people who I mean whoever has the witness for the statement can decrypt so but in public encryption the only one person I mean so I think it's kind of generalization of uh public INR so yeah okay yeah yes yes no but you can definitely think think of it like that yes um that's true yes uh so I will sorry Jero um I

will um read your questions so um can you explain how encryption decryption using commitment opening proof differ from public care encryption in more abstract way so perhaps uh the different question was the answer to that yeah I was thinking like this is like a generalization of um public key encryption plus uh verifying the like authenticating the center of the message with signature but I guess like admitting this like authentication part

it's like more efficient or R do you can you can reduce the round of interaction is my understanding correct I I think so like I I couldn't say because like uh I don't like I think yes um I don't but I don't feel comfortable like answering uh so yeah I think so okay no worries we can we can keep discussing yes yes of course um so sorry um um what did you mean with any category

use case or situation that is more suitable so like again I was thinking this is like a generalized version of the you know just like encryption decryption plus authenticating the me the the sender but you can just submit this um uh opening proof that is corresponding to the commitment then you can omit this procedure of authentication which you have to do plus um in the public key encryption scheme

so um I don't know I was wondering if there's any situation that is that is more suitable to use um oneus encryp encryption from KZ commitment compared to normal you know public key encryption plus authentication um scheme but no yeah um that was my question yeah yeah um so I think a b um a b uh think that this uh should I mean at least my research is to or my implementation is to focus on is uh performance so for instance uh the gang

uh that what what this could uh allow is that for instance um NPC could be more performance so this is why I I have lately I've been changing directions towards more performance than uh convenience in a way and and I I should focus on that from now um oh and Rico says the difference is that with this encryption you don't need to know the identity of the decryptor in advance that's true um sorry um I I will answer um tak's question so if the number of um

all transfer uh so one out of two o is is small um then an attacker can easily make the same polinomial and and read the content of the O transfer so yes this is possible um but then this is why um on this commit uh function uh that I uh made on this Vector module uh I am appending a random element to the vector because yes that's uh you will basically you can reach to the same commitment and then you can verify oh this is the same commitment as this other one and then see uh yeah it's the same thing uh but so you you need some you need to part

your polinomial with some brandess uh yeah that that is necessary um yeah uh I'm not sure about uh p and commitments on um sorry and yes it's it's an important difference uh thank you thank you enrio for um for that yeah it's like with with this encryption you you can just put things

in the open um generally right uh but then uh you you can just rely on on the your message being safe if if um someone uh can basically provide a solution to the to this problem um yeah hope this was clear I I was quite unsure of where to target this presentation but uh yeah thank you for for the questions and any other question that uh there could be yeah

Carlos yeah I have one um what are the biggest um let say limitations that you currently see for U let's say widespread adoption of witness encryption and what would be what would need to be improved such that these uh changes are get better like is it that it's just not practical or it's not fast enough or I there's not use cases like in you yeah so for for General witness encryption I think the problem so for arbitary andp problems I think it's not efficient uh but I really haven't looked into it like I I mainly focus on on this

scent implementation [Music] and also like even for for this implementation um it's sometimes hard to find valid use cases so um yes uh uh well and R has been of great help with that um with some for instance FOC of War um mechanics uh for for a game um or well this most proven one is lonic transfer but then um yeah this is why I'm trying trying to trying to narrow the the the scope of of this implementation

to something so of to to specific proven use cases yeah thank you for for sharing that enrio um for so for General um Windows encryption I I haven't uh take the the time to to Del into it um but uh I can uh like I will be happy to talk like uh for instance with with aransa I think uh you you I don't know if you want to comment something on this but you you did give um send me a very nice paper uh for Windows incription for Signature aggregation I'm cor yeah like at some

point earlier this year I would say July June I was looking a lot in winess encryption but then the idea we were having didn't work out and I just quit it uh I mean I was with Guru B stent from uh I mean at some point I would like to retake uh this project so it would be cool to to to discuss a bit more so what what was the goal if I may ask the what sorry the the goal of um of the of the

research so the paper uh I share with Bry let me remind BR was a framework for doing winess encryption from signature schemes right and what we were trying to do with the guru was like trying to do windows encryption for um simple languages for lookup relations and only lookups yeah or at least uh to prove that something is I mean I look up on a one zero Vector so uh to prove that some value is binary or we're trying to

explore like other relations but then didn't work out as we were were expecting yeah that's a paper that's the paper we're trying to work on well uh thanks thanks a lot uh for for attending I hope this was interesting and uh yeah that it helped and um let's let's keep talking like uh this is ongoing work so