Karl Yu | An overview of additive PCS

um next up i we have um carl you who hung from hash coke um he's going to give like an overview of some of the existing examples of additive schemes yeah so carl take it away yeah thank you thank you yashin for inviting me to speak here and my topic of brain hair is about addictive polynomial commitment skin so actually this is a refinement of polynomial commitment skin with addictivity so before we dive into addictive polynomial commitment scheme we just begin with uh what is polynomial chemical scheme actually basically a polynomial chemistry is a set of algorithms like which consists of setup commit and verify and in the evaluation in the first phase like uh as a set of phase this is a a deterministic algorithm that outputs public parameters for committing to polynomials of degree d so actually you can see very schemes that leverage the the low degree extension of a polynomial this is useful because you can easily find that in the invalidity of your commitment by just a limited number of operations so this is very useful and uh the second phase is commitment uh the approver commits his uh his uh his data to um polynomial and this algorithm outputs a commitment to polynomial and an open hint and after the prover commit his his secret value to the polynomial the verifier can verify uh with all this public data by having access to it and um he can check the validity of of this uh opening hint and yeah so uh the start point is kcg scheme uh this is a this is a this is a polynomial command scan that uh that that needs a trusted setup a transit setup is is a so-called trapdoor that if if this was leaked and the whole security of of the whole scheme can be broken so the commitment the commitments of of of kcg skin is as false yeah so uh in terms of the evaluation proof that k-3 commitment scheme that is yeah wait um where's the mainland yeah so in terms of the evaluation proof in the case of minimum skin that this this relies on a theorem called a polynomial remaining theorem that you can this makes you that uh you can prove that uh um you can verify that uh a given point in uh you know a polynomial that is actually equal to um yeah so actually um yeah so this is uh this is for uh you can prove that you uh um a point in a polynomial is actually equals to uh the given y so actually um in the evaluation phase that we verify this evaluation proof we mainly use for um women use parents [Music] parents operations on elliptic curve is is very costly so so there are many solutions to reduce the number of parents operations in in in all all of these schemes right so uh the pairing operation is mainly for checking the uh equality of of two equations and uh based on the kcg convenience scheme um there are many other schemes that uh uh yeah so that is uh that as uh the variation of of the kcg scheme like the bulletproof that it makes use of of inner product argument the commitment in this scheme is as false and you can see that if we treat the coefficient of of this commitment and if we treat this coefficient of this commitment and the generators separately we actually can rewrite this as an inner product argument which yeah so um yeah so everyone can re recompute these points by his own so bulletproof is transparent and uh yeah so from high level the strategy to include problems into an inner product is as follows like we encode the value that we want to prove in a given range into a big representation like you encode 3 as one zero right so so the one problem that we uh we face is that we make we need to make sure that each bits of this representation is actually zero or one so we need to construct a com complementary vector that to assist with us so you can see the details in in bullet proof that how they uh can uh to see the details of the construction of such vector and we combine all these vectors into a polynomial and later convert this into a single inner product so as many uh many other schemes that i used to do um we need to blind the vectors that we command committed to uh in order to achieve a zero knowledge property so the second case that i want to bring here is the historic polynomial commitment scheme which is transparent post quantum and many other properties this is library uh this this is this game is from a vector matrix matrix vector products and based on the observation that given either the coefficient of function or its evaluations of boolean hypercube the evaluation of the skin polymer polynomial can be turned into a contraction of a specific tensor and i haven't read these polynomial schemes too much but the this but but the thing that the the commitments to metrics is the culmination of peterson commitment which is addictively homomorphic and and if you are interested you can read that and uh the third uh case uh and and the third case here is it's darks integer uh it it starts it is a dark skin right so uh one one key component of this game is integer encoding that you represent a a given function as a linear combination monomial basis like like that result one limitation of this of such skin is that you need to choose uh just choose the value that you want proof is not less than the p which is the prime uh which is the order of prime of prime field right so um yeah so uh to see uh the correctness of of um of this equation you can choose you choose a f of f of x like uh like uh like like three uh multiply x x to the third degree uh plus da da da yeah and then what and what and you choose q that is uh that is not less than uh p which is um um you can choose like if you choose the f of x these will is equals to three uh uh like three multiply x to the third degree you can choose a p q like uh like like a five right so actually the coefficient of of these polynomials is um uh yeah so it's it's actually uh a modulus of of of the prime right so yeah so like if you go through this you can see the output value is equal to the content concluding of the coefficient of the given polynomial right so uh this brings us to homomorphism here but we just skip out the monomial homomorphism and just focus on the addictive homomorphism which is like f of q plus g of q is equal to f plus q f plus g of q right so this only holds if if we choose um the the q the value of q um suitably right so uh to sum up um the addictive hormone uh addictive uh i think addictivity of of the normal communal skin is it's very useful that we can um uh evaluate the the the proofs uh uh efficiently right so commitment efficiently and the one limitation of the dark skin is that the the ad operation only works for a bounded number of operations that you need to choose choose q values you want to prove a cue point that you want proof is is is is no less than the order of prime field right uh finite view and yeah so thank you yeah yeah um any any questions for carl carl works for is looking for research engineers and i just dropped the job description documents in the chats so if you're interested you can reach out to me or you can reach out to me cara and taro