Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT - Nils Fleischhacker

Transcript

hello everyone H welcome to another learner share session H today we have Nils H as a speaker and welcome Nils and feel free to start when when you want okay yeah uh hi I'm Neils and uh yeah so I'm going to talk about extractable witness in for kcg commitments and also a little bit about efficient lonic OT um yeah this is Joint work with Matias and Mark and so to start first of all so you want to um construct extractable witness encryption for kcg commitment for that

it is important to first ask what even is witness encryption um and to understand witness encryption it is instructive to First think about like normal standard public key encryption okay in a normal public key encryption scheme basically what you have is you have a uh key generation algorithm normally that takes some security parameters input and it outputs a a key pair basically a public key and a secret key and what you can then do with it is that you can encrypt some message M with the encryption algorithm with the public key and you get a cipher text C and this Cipher text C can also

then be decrypted using a decryption algorithm given the secret key and the message in Prime so what does it mean it means basically that I can now encrypt like towards a public key and whoever has the secret key uh can decrypt and how how do I know who has the secret key well that's a a problem for public key infrastructure stuff but the idea of witness encryption now is slightly different where I don't want to encrypt necessarily towards something somebody at some point generated I want to encrypt towards a statement that may be true or false so if I encrypt towards a true statement then it should be

possible to decrypt and if I uh encrypt towards statement that may is maybe false then hopefully uh it should not be able to decrypt so the idea is basically to get rid of the key generation part and replace the all of this with an NP relation so an NP relation uh is basically just an efficiently um checkable relation so basically this relation R here um it consists of pairs X and W and there's some efficient algorithm Mr that basically checks if x and W are in the relation or not you can think of this um basically for example as an example circuit satisfiability problem for example where you say you

have some program defined as a Boolean circuit and you um say this relation now is um that something is in the relation if an input satisfies this Boolean circuit so that means that there exists an input that um will cause this program to at the end at the end accept output true or whatever and then we can define a language relative to this um NP relation and saying X is in the language if there exists a witness such that X and W are in the relation um this is just normal

definition of like NP relations and NP languages and the idea is now that we replace the public key with a statement and we replace the secret key with a witness for that statement and well the definition of witness encryption um the sense of correctness and security is a bit counterintuitive maybe because it has talks about two different cases essentially if we have an x w in the relation so that means X is in the language because W exists then we can basically take a message we can encrypt it towards the statement X we get a cipher text and we can then decrypt using the witness and

we get if everything worked correctly we get the message back um so this means that if x is in the language and in particular if x and W are in the relation then correctness is preserved so um we have basically a correct encryption scheme now if X is not in the language then what witness encryption says is that if I have two different messages m0 M1 and I encrypt both of them or I encrypt one of them towards a statement X then the cipher text of uh m0 and M1 should be computationally indistinguishable so nobody should be able to tell whether a

cipher text they get is an encryption of m0 or M1 the thing that is a bit weird at first glance is that what this means is that security is only defined If X is not in the language um so if you have any X that is in the language then this definition does not say that there's any kind of security if you have a language where it's actually hard to decide if x is in the language or not like Security will usually carry over to uh the a in the language as well but this is not guaranteed from this definition it's a bit counterintuitive but that's how it's defined basically

correctness holds for stuff in the language security holds if it's not in the language now what we are looking at is witness encryption for specific relations so witness encryption for like arbitrary NP relations so basically for all of NP um exists we know that we can construct it but only from very strong assumptions so we can construct it from indistinguishability ofation we can also construct it from some non-standard lce assumptions but nothing that is like from standard assumptions and nothing that's particularly efficient so what we looked at is whether we can get witness encryption for some useful specific

relations and what we look at is specifically kcg commitments now what kcg commitments are I'm guessing that most people here will probably know what kcg commitments are but um I will also not go in the details of the commitment scheme basically the only thing that's important for us is actually the verification equation of this commitment scheme but just high level what is a kcg commitment um it's a commitment scheme that allows you to commit to pols it's polinomial commitment scheme so it has some setup that basically um needs a whole bunch of these powers of TOA in there and you can commit to a polom over FP where p is basically the um order of

a bilinear group so we have these three groups G1 G2 GT and you have a bilinear pairing and if you have a polinomial over FP of some bounded degree then you can uh commit to it and what you're left with is basically a very small representation of this polinomial and with the opening algorithm I can then um create openings or proofs that show that the polinomial that I committed to evaluates to some specific value beta on a specific point Alpha and this is verified using this verification

equation now the idea would be that I can now um Define witness encryption for kcg commitments in the sense that somebody with uh an correct opening should be able to decrypt meaning we can define a relation or we can define a language where we say okay it's in the language uh is a triple of commitment a point Alpha and a value beta if there exists an opening such that the verification equation is satisfied um why would something like that seem useful well there are many protocols that actually use kcg commitments and it is think of it in a

way for example where you have a protocol and during this protocol at some point somebody sends a kcg commitment to another party and at some later point this party asks the first party to open this kcg commitment at a specific point to a specific value because this somehow um confirms something that they claimed before and if the all of this is correct then they for example will reveal a secret um but they will only reveal the secret if uh the opening is correct and if we have witness encryption for kcg commitment the idea is that we don't need to do this we can instead just encrypt towards the

statement and whoever has an opening can just do with the decryption so this is one example of how it could be useful uh the problem is that with the normal definition of um witness encryption it turns out this is not very useful why well if we look at this verification equation it turns out that for any triple of a commitment Alpha and beta we can always find an opening Pi that satisfies this uh equation okay or I say we can find it uh these things are hard to efficiently compute but they exist okay for every triple com Alpha

Beta that like syntactically is of the correct form um we can find or there exists a pi that satisfies the verification equation so in principle a kcg commitment um can be opened at any point to any value and that's bad for our definition of a witness encryption because that means that this is a trivial language like everything is in the language but if everything is in the language as I said security is only guaranteed for stuff that's outside of the language so if everything is in the language we don't need to guarantee security which will lead to a very simple but also completely useless uh

con construction like I can um basically give you a correct construction or whole witness encryption scheme that just send the message because the language is Trivial um and everything is in the language so I don't actually need to hide anything so this is not a good definition when working with this kind of trivial language but we still want a witness encryption because obviously this is not actually what we want we want that we don't want that the cipher text is decryptable just because the statement we encrypt towards is true we want it to be decryptable if somebody actually knows the witness and not otherwise and the idea here is to do

something similar to or this the difference is similar to the difference between normal proof systems and proofs of knowledge if you have if you know about a normal proof system in a normal proof system you prove that some statement is true in a proof of knowledge you you not only prove that the statement is true but you prove that you know why it's true that you know the witness and how do you define that well you define it via extraction basically if you can uh create a proof for a statement in a proof of knowledge then I can extract the witness for that statement from you and the same idea holds for witness encryption basically we Define

extractability in the sense that an encryption scheme a witness I scheme is extractable if there exists a PPT extractor such if you have any PPT adversary that can distinguish encryptions of m0 and M1 with some non-negligible advantage and the extractor can actually extract a witness W forx also with non-negligible probability so um how would we go about constructing something like that well constructing it directly is uh a bit hard we actually take a step back and construct something simpler first uh what we construct is um not an extractable witness encryption scheme

but an extractable witness cam what is a cam a cam is a key encapsulation mechanism which is very similar to an encryption scheme um but it can only encrypt random short messages the idea is basically that uh the chem fun functionality essentially abstracts what you want from a public key encryption scheme uh when you want to use it for hybrid encryption essentially uh here it's a witness cam so we have an encapsulation algorithm the encapsulation algorithm instead of the encryption algorithm it does not get as input a message instead it only gets as input the statement and

then it outputs a cipher text as well as a key the key can be thought of as just a short message that is created randomly essentially um and the cipher text can then be decapsulated if somebody has a witness and this decapsulation will then result in also in a key and if everything went correctly then the key will be the same as on the encapsulation side and so it's very similar to encryption the difference is that the key is not chosen by anyone the key just falls out of the scheme um which means we need to slightly change our definition of extractability

because it does not as stated before it does not apply to chems really because there are no messages now so um the slightly changed definition is that a witness chem is extractable if there still exists a PPT extractor such that for any PPT adversary um can still extract the witness if this adversary can basically distinguish between being given a cipher text and the correct key or the cipher text and a uniformly random key if you can distinguish between two these two cases then uh the extractor can extract a witness for the statement um Can extract a witness for the

statement with non- negligible probability okay so how would we go about constructing something like that uh for well this kcg opening this kcg verification equation basically um and for that we can look at this equation and we can observe a couple of things so on the left hand side we have a parent and this pairing is actually computable by anyone like this only uses public information the commitment and beta are part of the statement so this is something that is actually um if we look at the definition of the encapsulation algorithm the encapsulation algorithm

gets the statement as input so the encapsulation algorithm can actually compute the left hand side of this uh verification equation on the right hand side if you want to compute it exactly as stated there um you would need the opening Pi or the the proof Pi basically uh to uh compute it like that and so the basic idea is now okay maybe we can use this at the um encapsulation algorithm uses the left hand side of the verification equation decapsulation algorithm uses the right hand side of the um of this verification equation and the idea is super simple

actually so we want to construct an encapsulation scheme um so or key encapsulation mechanism so we need two algorithm we need an encapsulation algorithm and a decapsulation algorithm and now the encapsulation algorithm can compute this left hand side and the idea is okay we can for example just randomize this so we can choose a random value and we multiply it with this leftand side now in the actual algorithm we've taken this R and put it in the first part of the pairing so it's actually computed in G1 but this makes no difference right we could also just compute it outside it's just more

efficient if we do it inside um so basically what we've done is we've taken this value that we know both parties can somehow compute and we've multiplied with a random but and from that we get basically uh a value s in the Target group and this is essentially supposed to be our key material um it will turn out that this key material is actually not necessarily indistinguishable from random um it is hard to put predict but not necessarily indistinguishable from random so to get around that what we do is basically we take a random Oracle and we apply it to S and then we have a key that is um

indistinguishable from random so the question is now how can the decapsulation algorithm basically compute the same as we can of course give the decapsulation algorithm R for example but that would be bad because if we give um them R if we send R like in plain then anybody who uh basically knows the statement and R can just compute the same key as well so that would be bad so we need to somehow hide the r in our Cipher text that we basically sent to um the uh to the decapsulation on and the idea is now okay so on the left hand side we multiplied simply by R if we also

multiply on on the right hand side by R we can also pull this R into the pairing but put it on the other side so what we can send as a cipher text is simply R times the G2 part of the pairing on the right hand side which is just the to minus the alpha and a decapsulation algorithm can now simply pair uh their opening with the cipher text and it's easy to see that basically um the s that you compute there will be the same ass that the uh encapsulation computed you put it again through the random Oracle to forget an

actually uniformly distribute the key and then we can return the key and this is basically it so this is the full witness Camp um if we want to construct a witness encryption scheme from that then we can use this key in a symmetric encryption scheme to basically then do encryption and we can prove why slightly adapted standard proof for hybrid encryption um that basically this gives you a full uh extractable witness encryption scheme the so this thing is is super simple um the hard part is basically

verifying that it's actually well uh actually secure so actually extractable uh and so the question is how can we basically extract from this and to prove extractability uh we will use uh make one assumption the assumption that we make is the ldog Assumption basically we say that it should be hard for any PPT adversary to reconstruct toao if they are given like powers of toao in G1 and also a bit in G2 um basically it's like the DLo assumption just with a bit more information and this is the same

assumption that is also used in the um well most well-known proof for kcg commitments um yeah so this is the assumption that the security will be based on and we will prove the extractability in uh the combined algebraic group model and random Oracle model uh so the random Oracle model is probably very well known uh basically we assume that we have some function the function that we used here uh the H um and we assume that this is a truly random function and then if you ever want to use this stuff in reality you then need to instantiate this hash function and

hope that nothing breaks and usually it doesn't um the algebraic group model uh is probably also well known but uh um is a bit different in the sense that it's basically an assumption on the adversary uh we are assume that our adversary is algebraic which means that whenever the adversary outputs any group element it needs to explain how this group element was derived algebraically meaning uh using only group operations if you look at a normal group without like a pairing this basically

means the adversary knows a bunch of group elements and any new group element they basically need to explain as a linear combination of those group elements and uh well with the pairing it gets a bit more complicated because you have can multiply once and uh but the adversary still needs to explain how they computed the value Bas okay so so how do we prove that the scheme is extractable the idea is let a be some arbitrary but unfortunately algebraic PPT adversary that actually can distinguish between uh being given the cipher text and the real key and the

cipher text and a random key with some non-negligible Advantage call it Epsilon so that basically means that we have this probability that the adversary given Cipher text and KB can reconstruct B and this probability is 1 12 plus Epsilon okay now let us Define that k0 is actually the H of s and K1 is the uniformly random volum and the first observation that is very important is that a will query s to the random orle with high probability uh in particular if the advantage of the adversary is Epsilon

then it will vary this s to the random orle with probability at least 2 EPS now why is that well the point is basically that if they do not Cary the s to the random Oracle then their view will be independent of B okay so we can take this probability of the adversary and we can split it up Bally we by hit we denote the event that s is actually quer and then we can take these conditional probabilities and say okay so what the probability that a is able to distinguish a k0 from K1 um given that they actually qued

s now if they actually qued s well then they should be able to distinguish between them because in one case they get a random value um that is independent of the hash value and the other case they get the same value so we can only bounce the success probability by one by one there um on the other hand if hit does not occur which means that um s was not quered then we say that now the view of the adversity is actually independent of B Because as long as you do not quy a value to the random Oracle the output of the random Oracle on that point is just

a uniformly random value and that means unless you quari it the view of the adversary given b equal z and b equal 1 is identical and therefore in this case the probability is actually exactly 1/2 so you end up with something like this where so we have the probability that hit occurs and we uh replace not hit with one minus hit and we end up with basically 1 12 plus Epsilon is equal to 12 plus 1 12 time the probability of hit so we can remove the one half on both sides and multiply by two and then we get the claim that yes indeed any

adversary that is uh success successful in this uh in distinguishing actually has a significant probability of carrying uh this correct s so why is that helpful because the adversary is algebraic um if the adversary is algebraic that means they then need to explain to us how they compute it s and that will be helpful because we already know one representation of s namely the one that we can compute ourselves and now then we will have two and whether or not the those are the same will allow us to either break the ldog Assumption or

extract C so how does the extractor work um this will be first very high level and the actual extraction we will do uh next so the extractor basically receives this whole setup of the kg commitment um because it's always necessary as well as like a statement consisting of a commitment com and Alpha and beta and this commitment com so even though it's just written as an input here this commitment com is actually an output of the adversary like the adversary gets to choose the commitment um what that in particular means is that the adversity also needs to explain how they computed this

comp okay now what the extractor does is basically just compute completely honestly an encapsulation so the extractor basically chooses a uniformly random R computes the cipher text exactly as specified by the uh encapsulation algorithm and then chooses a random k and just invokes a on the cipher text and K and now might one might wonder why do we not like need to flip a coin and either give the correct key or the random key um the answer is that this is exactly the same thing that I argued before like until the point when the random Oracle is actually queried on S

it makes no difference because in both cases the key is then a uniformly random key unless un L you actually query s and since in The Next Step once s is quered we just abort a it makes no difference that we just choose K uniformly random independent of any kind of bit or something like that so basically what we do is we wait for a to query the correct s and then we abort the adversary and then we extract how we do the extraction we'll see on the next slide um and if s is never queried well

then the extractor is out of luck then the extractor basically needs to um just outputs an error symbol and can't do anything about it however um the good thing is that because we argue that s will actually be queried with significant probability we know that this doesn't happen too often so how do we actually extract so we use the AGM to extract which means we use these representations of the group elements that the adversary needs to Output whenever they output a uh group element so when the um adversity chooses the commitment they basically uh need to

explain this as some linear combination of these powers of toao in G1 for S it's uh slightly more complicated the reason is twofold once in the meantime the adversary has also received a cipher text so basically they can also of course do things uh like combine stuff with the cipher text to compute s um and the second thing is that s is in the Target group and not in G1 so that means that before like adding stuff up you can also do like one multiplication by using the pairing so what we end up with here is

that this green part is basically just the powers of to um in the case of s uh this goes from zero to 2D because we can basically pair those powers of TOA with themselves and then we end up with higher powers of to um but yeah so these are basically the powers of to paired with other powers of to the red part is just the powers of tow paired with the cipher text and the blue part is the cipher text paired with itself and for each one of those possible um group elements basically the adversity specifies a coefficient and then we basically get this large uh

linear combination of all of these group elements and this is the explanation for how s was computed um right so one thing to note here is that uh we allow the adversary here more freedom than they probably have in the real world um the reason is that if we use which is usually done an asymmetric pairing in particular type three pairing then uh a lot of these uh group elements here are not actually com efficiently computable so because uh we only have most of the powers of TOA in G1 which means like you cannot pair the higher powers of to with them for

example because you don't have them in G2 so you can do paing but we just allow the adversary more freedom than they actually have so nothing breaks in uh and we can simplify this representation uh slightly um by basically factoring out this R * to minus Alpha and putting this outside this sum and then we left with this simpler sum that is essentially just a yeah a uh line combination of all the of the powers of to okay so what we can now do is we can Define two pols we Pol Define the polinomial f

using the coefficients f i that are basically part of the explanation of the commitment comp and we Define a um uh a polinomial g this is a b variate polinomial using the coefficients from the explanation of s and if we do this um basically what we get is that if you evaluate F on to and bring that into G1 then you basically uh get this so basically this evaluated on to in group G1 is just the commitment and this evaluated on to R um in the top Target group is

basically our s Val and okay so to extract the extractor now basically checks one thing and it checks whether this polom G is equal to y * f ofx - beta now this actually corresponds to how the n ACC solation algorithm can compute s and if these are the same then the extractor outputs Pi which is just this sum basically this middle part of the uh of this explanation of

um the uh of s um so basically this part okay so if these are the same one thing we can note about that is that this mean that a bunch of these coefficients in G actually have to be zero why is that well um G needs to be uh the same as y * something here which means that every um monomial in G actually needs to contain y

these uh up here the W * X I do not contain y so that means that all the W need to actually be zero um the same thing back here we don't have a y we have a y 2 which does not occur on the other side which mean that also H needs to be zero so what we're left with is basically just this middle part as our uh polinomial G we can simply the G so what we now want to check are essentially two things so we want to check that this value that the extractor outputs is actually a correct opening so that the evaluation uh the verification equation B basically holds for this part

and then we want to check that this condition that these are the same uh is actually okay so in the sense that if it would occur only for with negligible probability then this would not be good right because then we would be able to uh reconstruct Pi but only with negligible probability which would not be enough so we need that this actually holds often enough so let us first check that the output if it occurs is actually correct so if the extractor outputs anything basically outputs a pi then we know that this equality

holds now as I said we can simplify the definition of g because all of these coefficient need to be zero because otherwise it could not be uh the same so we can plug in the simplified definition of g and then we can actually divide both sides by this part here basically we divide by y * x - Alpha and on the the other side we have a y so that cancels out and then we'll left with that this sum of Qi * x to the I is equal to f ofx - beta / xus Alpha and now if we look at the output

of the extractor the output of the extractor was this um and this is just this evaluated on position Tow and put into group G1 so that means now we actually have a value for the output of the extractor and we can just plug this value into the uh verification equation and check if it's hold or if it holds or not and well we can just do that so we can start with the right hand side of the verification equation which actually contains the pi and we plug in this value that we now know that this Pi that the X Vector outputs actually is

okay and we see here that we have F of T minus beta divided by to minus Alpha and we pair that with to minus Alpha now what the pairing does is basically it multiplies those two parts so what we end up with is basically F of to minus bet now in the Target group because the pairing has been inval but we can also rewrite this as pairing the same thing but in group G1 with the generator of G2 and now we can look at so what is what is f of to well if we look back to

what uh F basically is f is basically um this and if we evaluate it at position to what we end up with is simply the commitment so um we can plug that in and what we have then is just the left hand side of the verification equation and therefore uh that means that the verification equation actually holds if we output this uh proof part so that means if the condition is satisfied then our output is correct but the question remains what is the probability that the condition is satisfied

so the extraction fails if these two pols are not the same so the question is what is the probability that these two equations these pols are not the same and this is where we will use our computational assumption the aldock Assumption essentially we can define a new polinomial Q as by basically subtracting the right hand side of this inequality from the left hand side and um what we end up with is by definition because these are not equal we will end up with a polinomial that's a nonzero polom

however um we can if we evaluate this polinomial at position to and R basically um what we have is that this G of to and R this is just the representation of s that the adversary gave us so that is how the adversary explained their choice of s on the other side if we in basically evaluate this part on uh Tow and R what we end up with is this which is basically just how we ourselves so the encapsulation algorithm or in this the the extractor actually uh computed the

value s so these both of these are representations of s which means they are the same which means that this polomia Q is actually zero at that point so what we have is a nonzero polinomial with the root at position to R and why does that help us well that helps us because it actually allows us to um extract to or R from this polom um and we can use that to solve the ldog Assumption so we can rewrite Q

um as essentially a so Q is a byari polom we can rewrite it as a univariate polom in y with coefficient that are univariate pols in X and then we can Define p as the polinomial that is basically the same as q but we fixed X to be to and then we have two cases we have the case that P of Y is the zero is not a zero polom well if p is not a zero polinomial but we know that P uh evaluated at position R is zero then that means this is a nonzero polom

with a root at position R which means we can just Factor this polom we can uh basically find the roots of it and one of those roots will be R which means we can recover r on the root of um p and now if we do a reduction to the ldog Assumption we can basically um put our challenge of the dlog uh assumption into R and then recover it um if all of this basically turns out to be true which means that the probability that this can be true is only negligible because otherwise you would be able to break the

aldoc Assumption by recovering this on the other hand if this polinomial p is actually a zero polinomial then that's interesting because that tells us that C1 C2 and C3 must all be zero at position to um but we know that at least one of them is not a zero polinomial because otherwise the whole polinomial would be zero polinomial which we know is not the case so that means we have at least one nonzero polinomial here with a root at to which means we can again recover tow

from basically by finding the roots of one of these pols and then we can do a second reduction essentially also to the aldock Assumption where we uh then embed our challenge this time in tow and basically recover tow from these roots which mean that also the probability that this case occurs must be negligible so if we now look at the extractor basically you can think of the extractor as being executed like in this tree and they termin whenever they hit a leaf and the red leaves are basically when the extractor has failed to extract the green leaf is when the extractor

um as uh was successful in extracting and um the question is now what is the actual probability that the expector is successful and at the beginning we basically argued that the probability that s is actually quered so the probability that hit occurs is at least 2 Epsilon so the probability that not hit occurs is 1 - 2 Epsilon um and we also argued now that the um that one of these two cases occurs each of those is basically negligible because we could break the llo Assumption if it were not so that means that also the parent of these two leaves must have negligible probability

of occurring which then basically gives us that the probability that uh the uh extractor is successful is basically 2 Epsilon minus something negligible since two Epsilon is a non-negligible function that means the extractor is actually successful and therefore our scheme is actually an extractable witness encryption scheme uh an extractable witness chem uh in the combined AGM and drom um and as I said you can basically then do hybrid encryption to get get a full uh witness encryption scheme from okay so this was like the main part

and the main technical part the question is now or could be now at least uh why would I even want a witness encryption beam uh for kcg and do we have some concrete uh application for it and in the paper we as the title suggests we have one specific application which is a very efficient laconic oblivious transfer protocol so uh to explain that uh let me take a step back and just uh start with what oblivious transfer is so an oblivious transfer is basically a protocol between two parties uh one of the parties say on the left Alice wants

to send one of two messages to Bob so she has two messages Bob has a bit and they communicate and at the end Bob learns the message MB um let's make it simple and say this is two message OT so Bob sends one message Alice Alice sends one message to Bob and then he learns MB and the intuitive security notion the actual security notion is much more complicated because it's needs to be simulation based and U but this is not really uh helpful for the explanation right now so let's say the intuitive um uh security notion is basically that Alice should not be able to learn

anything about the bit B and Bob should not be able to learn anything about the other message so the one that he did not receive now there is a variant of oblivious transfer which is uh laconic oblivious transfer which was first introduced by Cho all um and the idea is that we want to make the communic ation overhead of many oblivious transfers as small as possible the idea is now instead of running individual oblivious transfer every time you basically want to exchange a message you say that at the beginning already Bob has like a whole dictionary

of many individual bits and he uh computes his first message based on this entire dictionary this message uh the length of the message should be independent of the length of the dictionary and he just sends this thing which is called a digest uh to the to Alice and now Alice can basically take her two messages and let's say we start numbering them so we have two messages in the first round she sends a message to Bob and Bob learns the corresponding uh message for this first round which depends on the value of basically um the first entry in his dictionary is and then when we want to

do a second oblivious transfer we don't need to like run send both messages now what Alis can do is she can simply continue sending messages to Bob um without Bob having to do anything and also these messages should be short in particular independent of the size of the um of the dictionary and basically you can do that for a very long time in this case I said the size of the dictionary is n so basically you would end up with being able to do n oblivious transfers uh using only very little communicational so how could a uh

witness encryption scheme for kcg help in constructing something like that well the idea is that basically we use the kcg commitment to compress this dictionary for our digest and then we send the messages and crypt it using statement that contradict each other so this is basically your scheme um so we use the kcg commitment essentially as a vector commitment here so uh we commit basically to this um to this dictionary in the sense that we use the entries of

the dictionary as a coefficient of our polinomial um or as a coefficient no not as a coefficient at the evaluations of the polinomial um and then we uh um basically send this as our digest and when Alice wants to send a message basically she encrypts m0 and M1 under two statements and the statement the first state m is that this commitment that is the digest can be opened at position I to Z and for M1 that the um commitment that is the digest can be opened at position I to the value

one so these two statements essentially contradict each other in the sense that um if somebody would be able to basically decrypt both of these messages then that would mean that can extract from them openings that correspond to both of these which would mean we can open the same position to two different values which would break binding the kcg commitment sche um the truth is that we need to uh use a slight modification of the kg commitment scheme because we need some very weak form of hiding which the normal kg commitment doesn't have uh but

that's really not that relevant here so basically we just encrypt toward these two contradictory statements and because they are contradictory only one of them is basically decryptable and so this is how the lonic then Works um right and it turns out that this is actually very efficient uh so if we have look at the digest the digest basically this is where we essentially just the kcg commitment so these are just 84 bytes independent of how large our database is the sender message which is basically two Cipher texts of our um of our witness encryption scheme are just 256 bytes um also independent of

the size of the database and so sending and receiving is uh in milliseconds so this is very efficient um actually Computing this digest for larger database sizes can take quite a while so in minutes not what days but still uh not very that fast the reason is basically that we need to precompute all of these openings essentially because otherwise uh during the receiving we would be too slow to according to the definition of aonic o um right so the one major downside is that the public parameters of this

scheme are get very large if you get to very large um sizes for the database so when you end up with public parameters uh on the order of 100 gab um although one should note that like 2 to the 31 which is mainly here because we compared it to other um to to other electronic OTS that basically had this database size um and this is an very this is a very large database size so you can imagine like if I had a database of this size and I were

to do one OT every second then I can do that for like 68 years straight without stopping um so it's very unlikely that anybody would ever want to use such a large database size and with reasonable database size of like 2 to the 18 like 12 megabytes is not that bad for a public uh yeah so basically the public param the the scheme is either has much shorter messages than uh previous uh uh previously existing schemes or is much much faster so this is a very efficient scheme and could be very practical if somebody needs a look onot with that yeah we're done and if

there are questions I'm happy to answer them thank you very very much H for the great presentation so H for everyone H feel free to to ask questions ER yeah you can unmute yourself and ask question or you can write it in the chat uh hi can you hear me yes hi hi yeah I love your work presentations very nice and and especially the way to construct the tray for the F probability and the que and because I worked a

little bit on the database so I'm wondering I mean here Al those the I mean two power to the 18 is quite nice already but I'm wondering if we can simply you know for many k datab base actually we can partially H do them so uh have you ever considering if let's say it's a database and we do this we we do this uh uh slice by slice and then uh Constructor the proof for the final part so I don't think I got the question

uh ah yeah uh I mean if we want to deal with is a large database and we want we don't want to have a very large public parameter and is that possible to do something like we do it uh uh uh with uh we divided the database into several pieces and then we do the small one and then construct the Fel yes the security for yeah yeah so the problem with uh with put uh having several pieces of it is that that works and this in practice would probably be perfectly fine like

according to the formal definition of a laconic OT that's no longer lonic because now the digest is depends basically on the size of the database um we we can do that and then you have then you have like much smaller public parameters and um I don't have the table here right now but um yeah yeah so in that case the thing is that then the digest basically grow grows with the size of the database yes uh but not like which contradicts the definition of being laconic in practice it would probably what you would do if you want to

actually database sizes that's true that's true that's true and uh oh yeah one more question have you ever considered actually use it NPC because already oblivious transfers it's very natural to consider in more complex scenario NPC um I don't know how yes maybe answer that so hey I'm also of this work so uh hi Mark um if you so depending on which MPC type you consider this can be interesting so there are certain NPC protocols where

you have a pre-processing phase uh where they do some pre-computation they store this data and then during the com the real computation so to speak everything is done very quickly so now in principle you can use lonic ot to do you can do the whole lonic OT in the pre-processing phase so even if it takes a bit longer you can do this and um even if you don't know um which Choice bits the receiver would like to have in the end it's not so bad because you can pick them randomly and then there's like standard tricks of how to from something known as random ot to regular OT so um then the online phase would be very quick um and the message complexity would be still concretely very small it would be like in with lonic OT the receiver right now sends

nothing if you do this random to regular OT then in the online phase the receiver would need to send um one bit and then the sender would send back the appropriate OT response and regarding the first question maybe it's to point out that like for the thing that you suggested with the slicing we do have benchmarks in the paper in the implementation section wow wow that's nice that's answering it's very inter yeah um yeah I also have a question first of all thank you for for the presentation I was wondering if there were like other application that you

could uh build starting from this witness encryption scheme because like as understood correctly there must be a commitment existing first before the encryption is performed so it seems to me that there's some sort of uh like interactivity required between like the one was encrypted and the one who supposed to the cryp so basically the one who encrypted already must know the one that is going to decrypt and basically because this part must publish their commitment so yeah I was wondering like if this if

this Kim can also be generalized Beyond this laconic OT and if you had any I mean there are other there are other applications at least you can Envision we have not like proven that it actually works but um so one thing is that you can for example exle in in many protocols you actually have this scenario where there is a kcg commitment and at the end basically one party ask the other to open a bunch of positions on that um kg commitment and if all of these are open correctly then some secret is revealed this is a conditional release of Secrets stuff um and you can

basically for once you can uh lower the number of rounds in this kind of protocol because you can basically just send it and encrypt it before and just skip the part where you actually send the openings because it doesn't matter you don't need to see the openings the other party can only decrypt if they actually have them um the other part is that also it gives you some some notion of weak notion at least of fairness where basically uh after receiving the openings you cannot not just stop the communication and not reveal the secret that you were supposed to reveal because well you already send it before basically uh in encrypted form so there's some notion of fairness that can

be achieved there um there's also some idea that basically you can achieve something that is very similar to let's say uh like a two round witness encryption for arbitrary messages uh for arbitrary uh relations I mean um because was essentially so if you look at how a lot of snarks work so a lot of snarks are based on polinomial iops and you instantiate those when with a polinomial commitment and basically what happens is you have this whole poop thing and at the end you basically are

required to just open a bunch of positions in one or more kcd commitments and if you have like a two round protocol you can have this whole part that is the piop stuff in the first round and then the in the second round you can basically um encrypt towards this opening of the correct opening of for these kcg commitments and when you do that basically the guarantee that you have is that this this can only be decrypted if the party if the statement is actually true so you get normal witness

encryption not extractable witness encryption uh but it needs two rounds which is normally witness encryption is like a single like one shot thing where you send a cipher text and now it would be kind of interactive thing but there may be applications of witness encryption where that you could replace it with that and then this would be much more efficient okay okay very interesting thanks a lot for again right there are more questions okay if there are no more

questions ER thank you very much n for the presentation and everyone for attending and yeah so have a nice day thank you for having bye bye thank you byebye