ZK14 -Towards Practical Witness Encryption from Arithmetic Affine Determinant Programs Lev Soukhanov

Transcript

Here's Lev from Aloinit. So yeah, thank you for uh this talk and for waiting and bearing with us. Let's get started. Up to you, Le. >> Okay, let's go. Uh so uh yeah I want to talk about witness encryption which is basically a uh I would say it's a um and very interesting cryptographic primitive um which relates to public key encryption in the same way uh as snarks relate to signatures. So if you think about a snark as a um sort of like universal

signature in which like um your public key is a uh NP statement uh and um your signature uh is like a proof that you know um you you know the uh the witness to the statement. So witness encryption is a similar thing but for public key encryption. So you want to encrypt with a NP statement. Well, we are we will be talking about witness encryption for NP. Uh and uh yeah and to decrypt you need to have a witness for this uh uh uh for you you would need a witness to

this statement. Okay. Uh so the important difference between the two primitives is that witness encryption is not practical yet. Yes. So there are like bunch of properties. There is correctness which means that you successfully decrypt if you have a correct witness and uh there are few different notions of security. I personally prefer extractability but there are some concerns about that. uh but uh whatever like uh basically all all they say that if you don't have the witness it should be hard to decrypt.

Okay. So yeah so some background background is that theoretically there were there are like actually quite a few constructions for witness encryption. Um but they typically require you to construct at least a Dyson sphere uh at least. So um so so some roads go through strong even stronger primitive called indistinguishability at some in indistinguishability forcations. Some some do not. Um there is like the most efficient approach on which we base our uh we base our scheme. Um it's called

define determinant programs. Uh it's a paper of these people. Uh and u yeah it's from 2020 and it still requires you to be at least type one centralization to run that. Uh to be specific, it scales uh as n cubed depending on your uh statement size. Uh and um it only supports boolean circuits. And so n cubed of something like 10 ^ 9 is 10 ^ 27. And maybe you maybe you can avoid building a Dyson sphere, but still it it is not feasible right now. Um so a downside of this approach is that

ADP is not based on any standard assumption or honestly not on any assumption at all in the sense that it's it its own assumption. Uh so but that's what we have to deal with. Uh yeah so uh so our idea was taking ads. Uh I will not talk about how ADPs work by the way because I I won't have enough time. Uh but the basic idea is to take ADPs and somehow make them work not with boolean circuits but with arithmetic circuits and hope that n cubed is not bad enough is not is not is not uh is not that bad. Uh so

so yes this is like our basic idea I guess. Uh so and I want to talk about how it how it actually works. Uh so what is an aine determinant program? So uh I will sometimes say arithmetic find determinant programs it's a brainsing term in the sense that the shape of the ADP and ADP is the same. They just encode different uh circles. Uh so uh uh it's defined by a collection of matrices uh and we have an input um so let's denote m of x this linear combination uh and then uh

um important part here uh is that so it's just a collection of n square n plus one square matrices um and an important part is that we will actually allow inputs from the algebraic closure not from the original field but but from algebraic closure. Actually you could allow inputs from any ring but any ring contains a maximal ideal so this is not a problem. Uh so uh anyway uh how do they work? Uh yeah before that uh there we will sometimes okay typically we will consider a fine inputs. A fine input is an input for which you set x0 equal to one.

Okay. Uh and we will say projective inputs if x is anything and we will say that input at infinity is if x0 equals zero. Uh and we will denote x0 as this nice red one. Uh to improve readability of our gates further. So we say that ADP accepts an input if you compute M of X compute the terminant and it's zero. >> Okay.

>> Yes. I have a very question that doesn't work with binary fields just because you mentioned >> well uh we we could use for example so original construction does not work for binary fields for various reasons but uh our construction can potentially work for extension of a binary field but we we do want our field to be cryptographically large and actually this is an unpublished result but we have broken ADP for small fields. So uh so so but but this is not about characteristic. It's about uh field size. It's about field size. So you you

could potentially use small characteristic. We'll use large characteristic because we need parent based cryptography and it is not secure over small characteristics. Uh so anyway um so we will consider gates of the following form. A by B equals C by D. So this is even even better than R1 CS. Uh like slightly better than R1 CS slightly more expressive. Uh so our matrices will have size 2 M + 1 by 2 M + 1 and M is amount of gates that we have.

So uh and ADP is a sum of gate contributions uh where each gate contribution is intended to be the matrix which will have rank two when uh which is intended to have rank two uh when the gate holds and rank four when it does not hold. So basically what will happen is because you have m gates and your matrix is 2 m plus one by 2 m plus one then when you're reading them up um if all the gates hold the rank will be uh deficient and determinant will be zero and if if your gates uh at least one of the gates is broken then rank will be four and determent will be not zero

except it is negligible probabilities. So how these gates work? So L and D are just 2 M + 1 by 4 and 4 by 2 M plus one matrices and UI is what we call gate matrix and it actually depends on X. So it has different coefficients before different X I uh and it looks like this. So and then you can meditate a bit and look on the on this matrix but the claim is that and C of X is some random linear function that we hide from you. So basically what what what will happen is that uh first of all you can easily see that if the gate does not hold the rank is

four uh and u well with some effort and gaus method you can check that rank is two uh if this holds and c does not happen to be zero. Okay. Okay. So now encryption and decryption. So from ADPs how do we build witness encryption? The answer is we just add into a single matrix cell of of matrix M0 we just add our message which will be a field element.

And to decrypt we solve this equation in T. So we find such such t that this is zero. Okay. So this is basically how the construction works. Uh okay. So there are few problems with this approach. Uh so the problem is basically that attacker can try to probe you with uh projective inputs at infinity. So it can try to evaluate the uh your um your ADP

program on inputs that are uh that have x0 equal to zero. Just some inputs that do not involve matrix and zero. And the problem is that um the the basically what happens if if it is able to solve the circuit at infinity like uh find the valid solution at infinity. um the decryption algorithm fails but there is actually an attack uh yes so there is illustration of a solution at infinity I'm not sure if it helps anyone uh so um so yes while there is no direct way of decryting the message using the

solution of infin at infinity if you have enough solutions at infinity it is possible to uh excfiltrate like enough information about kernels of gate contributions and eventually recover the randomness to break the scheme. Uh so this is called correlated span attack. We well it's it's described in the original paper. We slightly generalized it. Uh and basically the story is that you should not allow at least many projective solutions at infinity. Uh so we we we define a notion of projective safety which basically bans you from having solutions at infinity.

So the way we do it is we we we have the following combinatorial notion f first of all base case is that our f first variable which is x0 is certified. So the one is certified because it's inf at infinity one is zero and uh certified means it is forced to be zero if for any solution at infinity it it will be forced to be zero. So and then we say that variable v is certified if it satisfies the following gate certifying gate v ^ 2 equals a b where a or b are already certified variables. It's like inductive predicate. For example, x1 squared will be something involving x1 and co a a or b will be constant and

etc. So it's like an inductive notion which allows you to prove that that if you set x0 to zero then everything is zero. Okay. So so basically there are no non-trivial solutions with x0 equal to zero. So then the big question is can you actually write any useful circuit using this extremely restrictive notion and the answer is somehow yes but but it's kind of hard okay so I'm not sure how much time do I have >> 10 more minutes >> okay uh so yeah basically we we have some gadgets u we need more we need new gadgets because like normal gadgets we

cannot multiply numbers they we will need to split them into bits. Uh so yeah so how do we certify a variable? Uh naively you take a field element you could split it into bits for example at least if it was like in the uh click field but it would pay uh it would cost low f constraints. It's of course still an improvement over a boolean circuit but not good enough improvement uh for us. Um so we want uh to only use it as a last last resort and uh uh and basically try to certify everything uh everything using some tricks. Um so I think I removed most of the examples from the

slides because I knew I will not be able to tell them. But let's consider a simple example of fifth power. So everybody who likes doing Poseidon wants to do fifth power of an element. So clear clearly clearly well maybe third power of an element but in our field it's fifth. Uh so uh so let's let's first consider this unsafe gadget. Um so x2 is x1 squared x3 is x2 by x1 x5 is x3 by x2. So when one equals zero, this become so so this is like how this system of equation looks at infinity.

And you can see that it has solutions at infinity because well you can set x1 to zero and x2 x3 just need to be zero simultaneous like one of them needs to be zero but other doesn't need to be zero. So basically you you do have solutions at infinity here. It's not safe. But we can add two more constraints. For example, we can say that x3 squared equals x5 by x1. And I I would like to note that x1 is certified already. So this actually certifies x3.

And we can do for example x2= x3 by x1. And because x1 certified already, this will certify x2. So it's not actually impossible. We just need to like get a bit clever about it. Uh uh so the output variable X5 still remains uncertified. And this is actually behavior of our most of our gadgets that they um certify only one side like only inputs or only outputs of the gadget. But then when you compose them uh basically we get that we only need to certify like only outputs or only inputs or the global composition in this case the output. So x5 remains on certified

uh oh I have more gadgets. So okay uh just ve very quickly uh we we have this uh fixed power exponent and the idea is that basically this works in the odd order subgroup of a field and the idea is that instead of like multiplying things you also compute square roots. So instead of a by b equals c you you use a by b equals c squ and it's like you get sort of like a drift in the exponent but otherwise it kind of works nicely. Yeah, it's it's it works up to the twist by elements of uh remember we we're actually working in the algebraic closure. So uh the gadget operates up to

the twist by elements of this group of like roots of unity of power of two. But it's actually not a problem uh uh to to check the pairing equation. So yeah, I will not be constructing extension field basis. I will just say that we we actually managed to keep our matrices over the base field and usefully and and use this bug or feature that we are forced to work over the algebraic closure by making a circle that constructs the element of this algebraic closure and constrains them.

So we also get like 12x advantage because of that. So blah blah blah snark verification strategy is very scary. move everything to the multiplicative group and then in the multiplicative group do the tricks that I talked about. Um uh yeah we use yes. >> Can all of this be done automatically? >> No no well well uh not yet uh well when you replace me with AI uh the and and you probably like roughly at the same stage we can retire and and this will be done after months. Uh so uh yeah so we have um sort of like like

very optimized for this specific proof system snark which is a version of Garuda. Uh it uses like one hash one public input which which is like crazy but it uses one public input. uh and uh yeah and uh like only interesting thing about it otherwise is that we moved all the operations which we we we didn't figure out how to do G1 operations. So instead we did pairs and moved them into the uh GT because we know how to multiply numbers and don't know anything else. Uh so yeah so what we achieve we achieve like plausibly imple implementable we for general np and by plausibly implementable I mean not using

a dyson sphere so um currently the circuit is at 15k constraints and I challenge anyone to improve that uh so and it's and [snorts] n cubed still sucks so it's like 340 terabytes cipher text but it it will fit it will fit in the data center. So uh not a Dyson sphere tier anymore. Uh I I stand that it is implementable not practical. Uh so uh yeah this is like currently what we have. Uh so one announcement is that we we now have cryptographic challenges. Uh um so we will be happy that anyone tries

to attack this thing except us. uh like we we want more more eyes on it. Uh we have some prizes uh for the effort. Uh and uh yeah that that's it. We are of course working on improving this uh blah blah blah. Any questions? >> Thank you. Thank you.