Homomorphic Commitments & Signatures

Homomorphic Commitments & Signatures



all right so I'm going to tell you about home morphic signatures and as a bonus also about home Orphic commitments this is based on a joint work with Sergey and Vinod but I'm going to present things a little differently here than they are in the paper so first of all I'm going to focus on this notion of home or 'fuck commitments as a good way of really understanding what's going on in the signature scheme and also focus much more on the techniques and the mathematical tools like it's the mathematics of crypto workshop so I'll focus on that rather than the actual end result I won't even define how morphic signatures until about midway through the talk and the reason is that I think these tools are actually more even more important than the application I think there should be more uses of them so that's what I really want to convey ok so let's start with the GSW the edge entry Sahai waters fhe schemes and so this is the one that seeker presented to you and here's just a cheat sheet what you need to remember from chica's talk so the public key is some matrix a it's an L W matrix so the last row is the close to linear combination of the previous rows and the secret key is just the LW secret the coefficients of this linear combination and this is the encryption so to encrypt a bid X I'm just gonna take the secretary to be eight times R plus XG where R is a random matrix with small entries so in Sica stocks it was a zero one matrix that's not actually essentially just yours once it could be some small Garcia and everything would work just fine and that'll be useful for us later but it just needs to have small entries and G is the this gadget matrix the powers of two matrix that Sica showed you so this how to encrypt and I want to now recast the scheme as a commitment scheme so if you see nothing much changed on the slide except I got rid of the secret key and I changed the names of the procedures so now imagine that someone comes generates a public key for the g SW scheme but then immediately deletes a secret key this is a trusted third party we all trust the data correctly and just publishes the public key so now there's a public key there's no secret key well what's the point of that it's useful as a commitment what's a commitment let's have some value like I can predict the outcome of the next Super Bowl so but I don't want anyone – no you know what the hokum is will make life boring but I want people to eventually find out that have this amazing predictive power so I'm going to take this value I'm going to essentially encrypt it I'm going to call that committing to it no one has the secret key so no one can decrypt it but I'm going to remember the randomness so the randomness of the encryption are and later after the Super Bowl happens I want to convince everyone that you know I predicted things correctly so I'm going to give people this value R and the the bit X that I committed to and people can compute you know check that this commitment was computed correctly and then they know that the value I commit to was indeed the value X okay so this team hat is statistically binding if I give you this commitment the value X is uniquely determined statistically and that just follows from the correctness of the GSW encryption schemes if someone actually had security they could decrypt it so there's a unique value contained in the ciphertext of course no one has a secret key no one can get it and therefore the scheme is also computationally hiding so he just got the commitment you don't learn anything about the the value X and that follows from the security of GSW actually moreover the scheme is even extractable if you had a trapdoor so if this person distrusted third party didn't believe the secret key then they could even extract out the commitment there's a trapdoor that lets you extract but hopefully no one has it right that's why we won't step binding and and hiding okay there's many ways to do commitments even from one-way functions why would we use this well there's a nice propria this has which is that it's homomorphic it has some homework properties and we can take a bunch of commitments so commitments to different values x1 x2 and so on using the same public key a and we can take the openings to these commitments and we can do homomorphic computations on these ok so maybe as a senior let's say I didn't just predict the outcome of the next Super Bowl I predicted like all the scores of all the games in the next season and then I want to convince someone that the values I committed to I actually got corrected let's say the median score of a game ok so I want I want to convince someone that I come I predicted the median score of in the season correctly so people can do a computation can do a computation on the commitments and compute a commitment that's a commitment to the median score so you evaluate this median function I can compute some operation on the openings and come up with a small opening that convinces you that this is correct so there's two homomorphic evaluation procedure here one procedure that works on the commitments this is exactly the GSW homomorphic operations we saw that Suika presented this is doing homework operations on previously these commitments are called ciphertext so this is the homework operation on ciphertext but there's another home morphic operation which is the home morphic operation on the openings so I can take the openings the randomness here and do some operation on that and come up with an opening that opens this commitment to the right value f of X 1 up to X n where F can be again any function and that just amounts to keeping track of what's happening with the randomness of encryption as you're doing homomorphic operations and we can do that and the GS w scheme we can keep track of the randomness so ok and this is the property that I want to preserve so if you do the homework computation the commitments and the openings you get the right value you get the right opening to the home morphic the computing I think most of them have it I'm not sure if you do things like bootstrapping you might lose it actually but not most have it we'll see why cheers W in a little bit there's some extra properties that has there useful that's a great question not not really so I don't know that these commitments that anyone can open the initial commitments so it gives you some sort of binding on the home or feel evaluate commitment you can only open it one way but I don't actually know that it's that there's actually any bits that you committed to that in the beginning so as in I might not have committed to actual scores of the games like a ligand in the season but if you compute the median you know that there's only one value contained there right if you do the homework a computation so it's not useful for proofs of knowledge unfortunately okay so one more thing I want to say is what we're concerned about here is that everything is short succinct Ness so this evaluative commitment is short evaluated opening is short there's another property you might want which is that when I open the commitment to this homomorphic computation I don't reveal anything else about the values that committed to other than the value of this function we're now going to worry about that we're not the the scheming represent will not have that property we can add it okay so we can't we can have this extra property that you have privacy but that's not going to be the focus so just the main focus that everything is sure the homework a commitment sure their homework and opening is short okay so let's see how to do this this is just the GSW operation so let's say we want to compute addition well we're just gonna add the two commitments it's the adding to ciphertext and if you want to operate on the opening so you're just gonna add the bits and add the randomness and this is the equation you have right so so this commitment C plus the correct opening for it is indeed just the sum of the two to randomness is the random is just adds up okay so that that's really easy multiplication is a little bit harder so this was the home morphic operation on the ciphertext that Suika showed you so to create a product to create a homework evaluation of the product you just do C 1 times G inverse of C 2 what happens to randomness here's a little more complicated this is the new randomness you get angry and well you can check out that it works it's this complicated equation but what's really happening here is that I'm opening c1 as a r1 plus x1 G I'm multiplying that by G inverse C to well G inverse e2 is just some short value so I'm gonna group R 1 and G inverse C 2 together then I get X 1 G times G inverse of C to the G & G inverse cancel so I get X 1 C 2 I'm now writing C 2 as a R 2 plus X 2 G and now again I'm going to group X 1 R 2 together those are both short values and I get this thing so I get if I'm grouping all the shared values together I'm gonna get this Plus what I want it this is the commitment to X 1 X 2 so again we're just keeping track of what's happening with the randomness as we're doing GSW operations ok so we have this commitment scheme that has this nice amorphic properties and action I want to tell you that this commitment comes in two different flavors there's two flavors of this commitment depending on how the public is chosen so the way that the public is chosen in g SW the way that Sica showed you it has this structure so a is then lwe matrix so the first few rows are random I'm gonna write it as B and the last row is just an LW sample it's a close to linear combination of the previous rows and so that's how we chose the public key a and the GSW scheme what does that give you well it gives you statistically binding just because you know correctness of decryption someone actually had the decryption key they could decrypt and it gives you computational hiding by the lwe assumption that's just the security of GSW but there's another way we could have chosen the public key we've just chosen a uniformly random okay now there is no secret key what do you get then outside one more thing and it's even extractable using the trapdoor so VFS you can actually extract X from the commitment okay so whatever we had chosen a uniform light random what happens done well it turns out that now the scheme is actually statistically hiding a commitment no matter what bid you commit to the commitment is just a random value why is that well eight times R is leftover hash lime extractor so this is just eight times our statistically close to uniformly random okay so it's statistically hiding and it turns out to also be computationally binding there's two wish to show that so one way is you can show it based on the system the short integer solution problem directly show that that implies it's computation binding but you haven't heard what the SIS problem is you heard about LW so there's an easier way or a really easy way to see from lwe which is well I could have chosen the matrix this way you would have been able to see the difference and here would have been statistically binding so it must be the case that here it's computational binding and that's actually exactly how you prove computationally hiding here you say oh I could have chosen this the public key this way and that it would have been statistically hiding right so yeah if they lie things are really bad that there's so if they choose it this way they can extract commitments they can actually find out what you're committing to okay if they choose it this way there's another bad thing they can lie they can open commitments multiple ways so it turns out that if you choose it this way it's equivocal you can actually equally in a commitment you can open in multiple ways if you have a trapdoor and that's what I'm going to show you next but just to answer us those questions so it's very important that here whoever chooses the commitment key this a is doing it honestly and doesn't have any trapdoors those you know chooses a randomly or or this way it doesn't matter which way but then goes away okay so so that's the next thing I want to show you that actually we choose it randomly then there's a trapdoor you can choose the a with the trapdoor that lets you accrue okay that lets you open a commitment multiple ways and this is something called related to the short integer solution trapdoor which was something introduced by aitai there's a lot of variants of that I'm going to present one that's closer to something done by magenta peickert and so here the goal is to choose a make a random matrix a statistically close to random with some trapdoors such as for any matrix V we can solve we can find a short are such at a R is equal to V why so here I'm not gonna be too too worried about dimensions but we sort of the the height of me is the same as the height of our how fat it is doesn't matter you could just have one vector then you can just repeat it for each vector of V but so I'm claiming that if you can meet this goal you can equivocate on commitments Y so to open any commitment see anyone you want to any bit X I'm just going to set V to be C minus XG then I'm going to solve for R and then I get AR plus XG equal C which means I open C as a commitment of X okay so this is this is the gold this is the chapter I want and here's the way to get it so I'm going to choose a yet another way not exactly randomly not exactly as lwe but this way so I'm going to choose the first M over two columns of a uniformly at random and then the last of em over to comes I'm going to choose as BR Star Plus G where R star is some short and maybe 0 1 matrix showed randomness and again because of left over hash limit this is statistically close to uniform so this is statistically cost the uniform matrix altogether okay and my trapdoor here is going to be the the knowledge of this this randomness R star in fact it's useful to think of it as this matrix negative R star and identity and if I write it that way the trapdoor this way then 8 times T is equal to G okay so now that I have that I'm claiming I can solve this problem just when I get V I'm just gonna set our to be T times G inverse of V what happens if I take 8 times R I get a T which is G times G inverse of V I just get B hey so this lets me lets me solve that problem lets me solve this problem so this is a way I can equivocate any commitment at all to any bid I want but this is actually not quite what I want this is too weak when I do this the randomness are I come up with I do I do find some opening of the commitment but it doesn't look legitimate it's not the right distribution I mean I I managed to open it but it'll look fishy it's not going to look like someone who actually generated a commitment the right way so I actually want to also match the distributions that turns out to be a slightly harder problem so here we want to do some sort of trapdoor opening from the correct distribution and let me phrase it this way so the stronger goes I want to choose a random matrix a with a trapdoor such as the following two distributions will be statistically closed either I'm going to choose R the randomness are from some short distribution may be some Gaussian or or zero one random 0 1 but some distribution over short and 3 matrices and I'm going to compute V equals they are versus choosing V uniformly at random and then somehow opening are using the trapdoor I want to make sure that these two distributions are statistically indistinguishable or close and this should be the case actually even if you've given the trapdoor so I want the randomness to come from the from the opening procedure itself ok so so this is something that I'm now going to show you how to do it it's something I was first done by this work of Gentry Packard America telethon there's other ways there's a couple of different ways to do it and most of the works actually did by carefully analyzing discrete Gaussian distributions it really relies on concrete property of discrete Gaussian there's a different way to do it which we didn't this work with Vadim where we do it via a rejection sampling and I think the parameters are all worse in pretty much all respects but it's conceptually simple you don't need to know about Gaussian so that's one reason I actually like it ok so this is something I'm not going to show you but it's something we can do and how does it relate to the commitments so now in the in the language of commitments these two distributions should be indistinguishable either actually taking this randomness are from some specified distribution discrete Gaussian or something specific and computing the commitment correct as a commitment a bit two-bit X versus just choosing a uniformly random commitment and then equivocating it using the trapdoor two-bit X you shouldn't be able that this should be indistinguishable you can't tell which one I'm doing so the distributions are matching okay so we have we have this statistically yeah okay so that's what one morphic commitments are so just a brief summary of the whole morphic commitments this is we have a way of committing to bid using some randomness the opening is the randomness we can have homomorphic evaluate any function on the commitments and the openings these are two different homomorphic procedures things match up we have two flavors of these extractable versus equivocal and depending on how you choose the commitment key you can get one version you can get one flavor or the other and they are indistinguishable and in that critical mode we can open a commitment using a trapdoor you can open a commitment to any bid we want and the distributions match up so this is what you should remember now I'm going to use this as a tool to build signatures to build something new okay in fact I want to sort of say that this idea of commitments explains both homomorphic encryption and home morphic signature if you have the extractable version what does extractable mean there's a trapdoor that lets you let you decrypt that's encryption right that's fully homomorphic encryption and it turns out that in the equivocal mode you will get signatures and actually there's a really nice property here that this commitment can be set up in one mode or the other you can't tell the difference they're indistinguishable I don't have any application of that so if you have any ideas I think that should have some applications but right now we have application one mode and the other mode but not that you have one commitment that can work in either okay so let me now move to homomorphic signatures and let's do the motivation so here we have some user Alice she has some data X think of it as a big data base she wants to outsource this data to some cloud server okay she's gonna store X on the cloud and later either Alice or maybe some other user Bob wants the server to compute some function over this data some function f over this data and give the output Y okay so that's the that's the whole problem and you know there's two things you might be worried about one is privacy does the server learn X and if you want to solve the privacy problem you can use fully homomorphic encryption that's what secrets build about the other problem is verifiability is the answer you're getting correct that's what we're going to be concerned about here so again we can look at this problem in two settings one would be let's say that the server wasn't computing function let's say it was just a channel you were just sending extra malice to Bob so I call that communication there's two problems privacy and verifiability so privacy you know use encryption if you want to stop privacy if you want to go in the setting where the service actually don't come computation well you need homomorphic encryption okay let's look at verifiability if you just want communication you need signatures right that'll solve the just the that problem now if you want to do computation well let's just combine the terms we need some sort of homomorphic signatures so that's what how morphic signatures are let me be a little more specific okay so in home morphic signature scheme that alice is going to have some secret key s okay everyone knows her verification key I'll call that PK so Bob and everyone knows that the server two and alice is going to sign some I think of it as a big data set X using the scheme it's going to come up with some signature Sigma and she's going to give the server the data X and the signature Sigma now the server can choose any function f we want or Bob can choose it anyone can choose F can come from the sky and the sir can compute this function f of X and also homomorphic will evaluate this function over the data and the signature so in this case the data is in the clear the server knows X he's computing the function over the data and the signature is going to come with something this value Sigma Y I'll call that a certificate that certifies that Y is the output of the function f computed on Alice's data okay so Bob is going to get the func the output Y of this of this computation and the signature he's and this certificate this isn't just a signature of Y it's not like this action says that why why it certifies Y is out of the blue it certifies that Y is the output of a convert ticular function f applied to Alice's data Bob doesn't know Alice's data at this point but he'll be sure that Y is the output of the function applied on whatever data she signed okay and the main property that we want in this talk again will be just compactness so everything should be small in particular this Sigma this certificate should be of some size which is independent of the size of Alice's that are the complexity of the computation so a trivial solution to this would be just sine Alice's data with a normal signature scheme then give all of Alice's that and the signatures to Bob and Bob can do the computation itself that's not what we want we want things to be short okay and so Bob is going to want to verify whether this output Y is actually the output of the function f analysis data X this verification procedure will actually consist of two steps so one step is that Bob will do some pre-processing or processing on the function f and just the public key and he'll get something I'll call just a function specific public key for this function f and this step will be computational expensive it will actually in our scheme ideal it won't be but in our scheme this will take as much time as computing F so Bob is not saving on computation just on this communication but the second step which will be specific to the actual output and the data will be to verify that Y is correct you're just going to take this pre process public key the output Y and the certificate and this step will be efficient it's independent of their of the runtime of the computation or of the runtime of F or the size of X okay so we are getting some efficiency here but you always have to pre-process any function you want to verify yeah yeah exactly so you need pre-processing okay of a short yeah yeah it's coming I think next slide will be comparing to other work so yeah give you so okay so and the security here is that if f of X is equal to Y the car cannot convince Bob of any other output y prime so you can now give a certificate that verifies for some y prime which is not f of X that's the security there's some additional features you could ask for they're mostly I'm just going to mention them here I won't discuss them much more but for example here Alice in this scenario I'll just signs one data set X one database you could ask that she signs many different databases right and maybe she has like a data set of her employer employee salaries and some other information about her company and she you know she signed two different ones at different times so we can do that as well at that point Alice has to just each time she signs a data such as to give it some label and when you're verified computation you need to know which data said this computation was supposed to be evaluated on so you need to have that label in mind when you're verifying another feature you might want is context hiding some sort of privacy feature which is that if you get the certificate that Y is the output of of this computation analysis data you shouldn't learn anything else about else is that other than the output Y so it should preserve some privacy and again that's something that we can do but I'm not going to not gonna talk about it okay so the idea of homomorphic signatures has been around for a while and most of the passwords in homomorphic signatures looked at the case of linear functions so they were able to just do you know yet some coefficients and you are able to do like an inner product of Alice's data X with some vector of your knowledge and so the good news is we know how to do that from nice assumptions like by linear assumption czar say short integer solution and lattices if we wanted to go beyond that there was this really beautiful word by banan freeman that showed how to do degree polynomial so really constant degree polynomials and this was based on the ideal short integer solution problem so a lattice problem and the random Oracle model there's another word by Catalano in fear and ver in Chi which therefore also bounded degree polynomials but got rid of the random Oracle at the cause of using multi linear max and so in this talk I'm going to show you how to do all circuits it's going to be a level scheme so the size is do girl with the depth of the circuit but nothing else and we're gonna do it just based on this short integer solution problem or the l:w problem actually we're going to do a black box using homomorphic commitments that are equitable yeah all of these results everyone's there on equal footing yeah I think that's the next next next slide yeah so there are other solutions to this problem like give us pointing out other things you can do so one is CS proofs of snarks that were defined by Macaulay so this is a way to take any complicated and peace statement and give a very short proof that proves it and if you have that you there's a very nice simple solution to this problem so Alice is just gonna sign her data with a classical signature and then the server if you want to convince Bob that Y is equal to f of X that f of X is equal to Y for this for the data X that I'll sign these are going to create this CS prove or snog that certifies this so it's an N P statement there exists some data X and some standard signatures such that f of X is equal to Y that's what he's going it's going to give a short prove that to Bob and Bob is just going to verify the proof ok so here you actually need sustain on interactive arguments of knowledge it's a pretty strong assumption so it uses not senator assumptions like random Oracle model or knowledge of exponent type assumptions and in fact these are these are essentially there's some evidence that you cannot do it without without just types of strong assumptions in fact for the here you actually need arguments of knowledge there's evidence that these might not even exist in the most general case so you need some very targeted assumption in order to clear the the negative result there's also been a lot of works and so that's the that's the part that we're going to get rid of in this work we're going to do things just from lwe or sis there's also been a lot of works on memory delegation which is another another way of doing this problem is and there you can actually even sometimes get rid of the pre-processing and get efficient solutions where Bob never works as hard as evaluating the program the main difference is that all these solutions require some interaction there's some challenge response protocol that Bob is run with the server whereas we're talking about a completely non interactive solution solution there's really a fixed certificate that certifies the output of the computation so so that that's the main difference there okay so the theorem is that there exists a homomorphic signature scheme for arbitrary programs you can represent them a circuit where the size of the certificate is going to grow with the depth of the circuit and the security parameter but not with the size of the circular size of the data and the security would be just assuming the short integer solution or lwe problem in fact equivocal homomorphic commitments there's a caveat we're going to need to assume that all parties have access to very large public random string as large as the size of the data that alice is signing okay in the Oracle model random Oracle model you can get rid of it maybe you can just pretend that the digits of pi are good enough or sunspots or something like that but that is a caveat here so the random string is it reusable I mean let's say completely reusable everyone uses the same one yeah just just random bits in the sky exactly yeah well for correctness you can use PI rather than a random string for security you need it to be actually random kind of malicious generator do bad things yes yes if the string is generating maliciously bad things gonna happen okay so as a warm-up let's just do something really pathetic I want yeah the fire does have to read the public string yeah yeah in the so remember there's that pre-processing stage that does take as long as the data so he needs to do during the pre-processing stage so the pre-processing is inherent if you're doing it at the level of circuits rather than Turing machines because just reading the copied circuit takes as much time as evaluating it no not as far as I know okay so soul as a warm-up let's do something really pathetic or really simple just a one time one bit signature from an equivocal commitment okay I think this is this isn't well known but I don't have a good reference so someone please tell me if you know what the right reference is so here the public parameters are just going to be a random commitment not to any bit just totally random should choose it from this space of commitments at random the verification key is going to be the commitment key so and the signing key is the going to be the equivocation trapdoor and to sign a message X we're just going to use the sign is going to use the trapdoor to sample an opening to this commitment that opens it as a commitment to X okay that's it that allows you here you just signing one bit you can only do it one time that's it okay and this scheme is some nice selective secure where in the case of one bit it doesn't matter selected but not but it's actually useful the thing of it is selective so if the adverts a tells you what bid he's going to ask you to sign ahead of time you can just set the commitment to be the commitment of the correct bit so you can actually program it in the public parameters without knowing the trapdoor and now if the average is able to forge come up with a signature of the incorrect bit well you just broke the binding property of the commitment right you committed to one value the average say gave you the open the commitment to the other value you broke binding that's it okay and these distributions are indistinguishable by the location property we have whether you generate the commitment just at random and then later open it using that vocation trapdoor versus actually committing to the bit ahead of time those are the same distributions okay what if you want to do many bits still one time but now many bits well-nigh can put many random commitments in the public parameters and to sign like a long message x1 x 10 you can just use the trapdoor to sample openings for each one of these commitments to the correct values you want to sign so here the public parameters bro with the number of bits you want to sign but the public key and the verification key the verification key and signing key stay short those don't grow okay and this is the main idea we're going to use to construct the Flickr morphic commitments so the fully homomorphic commitments we're gonna have these long public parameters which are just a fairly homomorphic signatures which is never this long public parameters which are commitments just randomly generate commitments the verification key is the commitment key the signing key is the equivocation trapdoor to sign a long message x1 xn you're just going to open each one of the commitments to the right value and now the homomorphic operations work as follows so if you want to compute some homework function over the signatures that's essentially the home morphic operation over the openings of the commitments signatures are openings to commitments okay so you're just going to evaluate this function over the openings and get some certificate which is just an opening Aref so well to some commitment to the homework of value commitment the verifier is going to run the homomorphic computation so the signer that the the evaluator runs the homework account the cloud I guess runs the homomorphic computation on the openings the verifier is going to run the same the homework computation on the commitment so this pre-processing of a function f is going to run this homework computation over the commitments that are in the in the public parameters and come up with the commitment well for this function f okay and how do you actually verify that well you just check that the commitment matches that this homework will evaluate opening is a correct opening to the value Y for this home morphic evaluated commitment value if you just check that the things match up and why is this secure well you can show that there's actually selectively secure so selectively secure if you know what data is going to be signed ahead of time so not in the in the actual scheme but in the proof of security that research tells you what that I he'll want you to sign ahead of time well if he does that you can actually set these commitments in the public parameters to be committed so in the reduction you can set these commitments and public families to meet the commitments of the bits that the address is gonna want to see signed then you can give him the signatures just by giving you giving this randomness to that to the adversary if the adversary manages to come up with a function f and some forged signature so that's an opening of this commitment C F the homework value commitment to some value y prime which is not the correct output of the computation well you can compete the correct signature the correct opening of that commitment to the correct value I and now you have now you open the commitment in two different ways so you broke the binding property of the commitment okay so this shows you that this scheme already has selective security yeah yeah okay so that's really the scheme so that this gives you selective security so it's a well dip there it is a one-time signature scheme so here else is just signing one data set but different people could have totally different public key Center and signing keys they wouldn't interact interfere with each other yeah exactly you just guess what's going to be attacked see sorry these commitments in the path so now CF is the home Orphic evaluation of the function add on these commitments in the pub in the in the sky it's not uniform sorry it cannot be open to anything that's right so so I mean in the security pulled I'm not opening CF to the wrong thing right I'm opening these original I'm well actually in the in the scheme is opening commitments incorrectly the prove is creating commitments correctly I know that's a confusing part so the actual scheme is using that clear vocation of the commitments right to sign you open the commitment to whatever value on a side and the prove we're gonna set the commitments correctly to actually be commitments the value that will be signed and we don't know the trapdoor nevertheless if the address safe forges he gives he breaks the binding property so without knowing the trapdoor we managed to break binding that's the reduction this is just for one time one time is in you only sign one data set yeah so let me mention a couple of extensions so you know we started with something very simple you can just sign one data set in a selective security so if you want full set security not just selective data say doesn't isn't nice and doesn't tell you what would that I he's gonna want to see signed ahead of time there's a nice way to go from this selective to full via a notion called chameleon hash in order to do it with home morphic signatures we need some sort of a homomorphic chameleon hash and that turns out to be exactly homomorphic equivocal commitment so we have that so sorry I'm gonna I'm not gonna spend more time on that is just for those who know what chameleon hash actual is if you want to find multiple data sets so not just one data set there's a really easy way to do it which is you're just gonna use a standard signature scheme not a homomorphic one each time you want to start it sign a new data set you're just gonna choose a totally fresh Pub verification key and signing key for the home morphic signature scheme and then sign the verification key of the home morphix in with the regular scheme okay so that just sort of a hybrid signature type thing and lastly I just want to mention this context hiding property so we want to make sure the certificate only reveals the competent the result of the computation and nothing else well one simple way to do it generic list just with music so instead of actually giving the homomorphic the computed signature you give a non-interactive zero notch proof that you know it so here you don't need snart's or any thank right this is that the statement is short so that's a generic way to do it turns out that there's action nice way to do it for our specific scheme just using the properties of lattices so just the the underlying algebra you don't need an extra assumptions okay so some big open problems are how do you remove the large public parameters that'd be nice to get rid of that can we remove the dependents of on on the depth of the circuit or the bootstrapping we don't know how to do bootstrapping for this scheme we know how the different encryption doesn't quite work for a signature exactly because there's no secret key to encrypt there's no decryption key and one more problem the guy alluded to is can you do something where there's no pre-processing everything is efficient I think that would require vastly different techniques because it would really you would need to work with the idea that the computations a Turing machine rather than a circuit so that would really be different than what we're doing here but would be interesting to do that you hold an apology mention tips it is possible to fight the corporations that were done on the on the input is it do you get it free or what is the cost of achieving this oh oh that's essentially so the cut this this context hiding thing it's not you're not having the operations because the verifier needs to know what computation is supposed to be checking you're hiding the data other than the output of the computation and that's essential for free yeah in this case for this scheme I mean the scheme is already pretty inefficient but it's you know you get like not much more inefficient that's a good question so yes we actually can it's not in the paper but there's actually easy way to do it so I'll be happy to tell you

Author:

Leave a Reply

Your email address will not be published. Required fields are marked *