ZK11: ZK in Restricted Environments - Can State-of-the-Art Systems Run on Smartcards? - Silur

Transcript

[Music] hi uh thanks everyone for being uh here on this short breakout session at the very end I know everyone is getting tired uh we are going to talk about restricted environments particularly the most restricted environment in it I ever had the this pleasure to work with uh Java cards so we're going to create zero knowledge proofs on Java cards I'm uh my research mostly goes to postquantum cryptography is going to have a little Echo throughout the the talk here which will justify

my my tool my main Tool uh for generating the proofs themselves so on the agenda I'm going to justify why I used a postquantum primitive for such a thing why did I do the Java card based uh implementation then the basic protocol which is kind of an old protocol that I uh implemented um in a more optimized ways better parameters and such uh entity tricks then we're going to generalize the same uh protocol into circuits because this uh event is more about general purpose applications of zero knowledge so I was very great uh glad to hear that I'm not the only one

covering mobile proof today we already had uh mobile sdks and uh identity uh two actually in this room that many times referred that chip cards would be potentially a good way to do zero knowledge voting and ID and I'm glad to like present a practical implementation of such thing here so the current state of Z is sadly enjoying this kind of reputation uh node modules became the new approver system P requires 500 gigs to generate approves and it's start slowly starting to centralize all the use cases I'm not saying that layer two sequencers are

inherently bad because of that just reminding everyone that we have plora of use cases for uh zero knowledge besides uh blockchain scaling so the scheme itself will be implemented on letis is as I said my research is mostly in post Quantum uh either using latices or non ailan groups my choice here on ltis is not because of the postquantum uh security I'm not trying to reignite that religious War here they are just super simple to operate with I I prefer them uh

to Hash based or especially elliptic curve based or pairing based instantiations because yeah group operations on Prime are just expensive especially on rested environment when you don't even have an SDK to do such stuff so they are they produce now small proofs let thises enjoy the bad reputation that at the beginning with uh textbook learning with errors they produced hundreds of megabytes uh of proofs and Cas sizes and then we slowly started to shrink down and you're going to see where is the situation now regarding that so Java cards the pros is that it's a $2 uh trusted execution environment so

you can pack all your use cases that currently are instantiated instantiated on Intel because of sgx and private coin stuff that you need to hide from the user you can do it with this they are arguably more secure than the ledgers if you believe the common criteria certification process which is not inherently vers than what's happening in the dungeon but uh some voting and uh government ID solution do believe in the strength of the stamps and these cards are a level higher certified than the ledgers currently so they resist side Channel attacks and such against uh K exposure much more uh they are super easy to carry like it's a voting application passively

powered no uh no batteries and stuff the downside is that they are very outdated techn technology so the last version of a Java card that you can get on your hands uh on even B2B in a B2B setup is at least two versions outdated to what's the actual uh Java card operating system is right now nobody ever manufactured anything above jcop 3 even though now we are like done with jcop 4 and doing 4 point something right now but there it's just not available on the market another downside is that this is the largest card that you can get your hands on the JC op

g3h 145 that you can get your hands on as a natural person anything above this will require some form of kyc I for example I have a cryptographic consulting company tried to apply for at mno for a a more powerful card and they rejected me because I'm not in finance or governance so this is the the best we can operate and this is the S only type of java card that I tested the code on so prior work on this statistical zero knowledge ID with latices on Java cards is not a new thing this is actually the preferred way to do zero knowled uh on Java cards because that's

the only thing it can manage on a hardware level problem is that the parameter selection is kind of outdated lots of things happened since the original publication especially with ring instantiations of hard worst case problems on lses the implementation itself is lost so not only what is described in the paper are kind of suboptimal but the links doesn't Point anywhere and I didn't manage to recover it on Wayback machine either uh and also the original paper doesn't generalize to circuits I made some hacks to do that so take my uh logic how I generalize this identity

protocol with a grain of salt because it's going to be a hack but is generalized at the end so you can find the link there the properties of my implementation is that yeah it runs on 30 mahz and uh 11 kiloby of ROM we have available uh 145 kiloby of R the proof that I generate are 300 bytes uh from the card and they're generated on the card the threat model is statistical Zer no le because one really good advantage of latices beside the quantum beside the short parameter sizes is that if you do your distributions on the goian right then

the statistical closeness to verse case Gap SVP is much more easy to reason about than anything in piring based instantiation so it's kind of easy to read statistical Zer Le uh thread model her and yeah the implementation also can generalize to circuits as I'm going to show shortly so the original uh protocol from 2013 that I also linked at the beginning takes a random uh Vector so this is not your identity Vector I'm actually assuming you so your identities in this voting use case are 16 bytes so 128bit security is the Assumption here random bite uh then we pet the remaining

bytes of a ring C hash it's a postquantum way of hashing instantiated instantiated on uh polinomial rings so 16 bytes unique random string paded with uh um small Vector as in the terminology of ltis cryptography that uh the coefficients behave in a discrete Goan and we see that the challenge basically an uh ring learning with errors encryption to the approver which he has to prove that is able to uh decrypt uh aor it with the commitment so we make a commitment with the ring s the challenge

is a ring learning with error encryption super simple we have to abort of course to actually reach the zero knowledge property if the the cipher text that we received is not valid so it's not in the domain of ring learning with errors this is important of course and then we really reveal the origin commitment so it's a commit and argue protocol and your argument is opening the rlv uh Cipher text this is not anything new so far from the 2013 paper the parameters selected for the commitment scheme is uh shown about for the shortest integer solution problem

and the ring learning with errors problem we see that both fit into 16 bytes so you can utilize the short Types on Java provide 128bit security plenty the commitment size is 3 uh 20 bytes so slightly over one apdu length because the protocol you talk with Java cardsone are kind of a very primitive and dumb uh protocol you can't even use every bite in a frame that comes in an apdu the maximum length is uh 256 so you have to make two round trips for the coming commments which is actually the majority of the overhead in the whole implementation so

communicating the commitments and the cipher text are the main bottleneck here so observation one if you're familiar with cyclic latices uh they are really easy to store in the learning with errors problem because if you just rotate the coefficients around in a matrix and take a negga click uh form with it then you can span the whole lce with a single vector with this parameter it not only provides you 128bit security but you don't even have to store the roots of unity when you do the entity transform to fastly or super efficiently multiply vectors together so originally you should have

been able to get some um performance gains from storing all the roots of unity prior but turns out if you Benchmark it on a Java card because it's so restricted it's actually easier to get the new negacyclic rotation of the already stored Vector than to read from ROM so this is observation one here which is going to give a huge speed up on the original protocol two is that even though the parameters for the two worst case ltis problems are uh very different the prover the card never sends out the the ring learning with irror Cipher text so if we live with the assumption that the challenge it

receives is already in uh entity transferred form then we can synchronously decrypt as the apdu arrives and the third one this is actually the most important observation when we reach circuit uh generalization is that the encryption scheme for the ring learning VOR problem that I and the original paper instantiated is the Linder p perer encryption which is edibly homomorphic up to half of the um modulus that we selected for the quotient ring this is important later so in the be beginning I had this meme on uh Layer Two provs and stuff and

then I showed U an identification protocol for a special use case it wasn't really a fair comparison so now we're going to bridge the gap and mold this identification protocol into something that's able to proove circuits too so we know that the basic technique to do that is uh kind of old school now uh with all the polinomial techniques uh presented for example today but I'm going to use the lpcp version a linear uh PCP generalization we know that for every rank one con system there exists uh four query PCP if you do uh qsp instead of rank one then you can manage

it in three queries and but we also know that the only way we can generalize an lpcp into a general purpose snark is uh that we need a strictly linear PCP reminder that strictly linear PCP is when uh an adversary can only craft a valid Cipher text using the homomorphic encrypt uh additively homomorphic encryption scheme that we use the the only way for you to make a new Cipher text is to make a linear combination of Cipher text you already OB observed and this is a problem with us because we use the public key encryption scheme so you can always take a new uh you can always

encrypt a random bite Vector to the public key and generate a cipher text that you never seen before so your encryption scheme is fine at best because you have a translation at the very end that you've ever seen [Music] some common techniques how to overcome this big problem is either uh especially in lses so extensions Fields didn't really work out because they very quickly blow up the parameter sizes that I selected to fit into the smart card to levels that the caplet doesn't even fit on the card when compiled then another more common way is to transform your encryption scheme into secret key

version that's kind of the trivial and the most popular form how do you do lpcp based ZK ciruits but that also didn't work first because I really emphasized using the original uh DJ 13 protocol because of the small parameter size is the asynchronous decryption which is inherently public key and they all resulted in proof sizes that are not really interesting here results on the techniques on the paper below so I had to restrict the security assumption here which turns out that you can do details on the paper below why is

it true here so remember observation three that we have an additively homomorphic um encryption scheme up to a level of error we are not we don't care about bootstrapping or leveling here because the use case allows uh us to stay within the boundaries of this error Vector so the trapdoor function in this case ringing with errors have to only remain a fine that's that works uh with our increas scheme only slightly increases the verifier cost that's not in my threat model that that's the verifier computational cost I'm only caring about the proving that has to happen on the smart card verifier can be

a regular phone or a laptop that does this and of course the most important part of this is that I can reuse my original encryption scheme for the rest of the transform here so a strictly ained PCP we know that can not super efficiently but can be transformed into uh general purpose ZK snark it makes it non- interactive and uh sucin if you instantiate it uh usually through pairings which we on a gap right now the last step so we have Linder prer ringer learning with encryption ring

commitment schemes which we converted into a strictly aine PCP on the card then we need to mask these vectors in a post Quantum secure way so I can't just do pairings on these uh um on this Cipher text that I just received on the card first because I need to represent the group to elements so I need something within the same group turns there is a plora of literature on ZK or um letis equivalent masking to pairing problems this is the one I selected for the parameter sizes that are optimal for my implementation and can still fit into

the card and then you use the proposed protocol that I made the sequence diagram for so it's uh composed of these steps rank one con system to the strictly ained protocol and then you select your weapon of choice when you do the lce based uh wrapping again uh hopefully with the same group or the same parameters that I use here to replace pairing here this results if you take the latest um circum examples from the Raper ital re instantiated on Posite on pre-images of 16 bytes which is exactly our security claim fit into less than 60 kilobytes and we have roughly three

times that on ROM on the card so the circuit can be easily stored of course for more complex circuits this very quickly blows up uh way above uh to the megabytes which are not capable to store on Smart cards but I brought identify ation and voting use cases which you can uh abuse using just posidon pre-images so demo time this uh the building process runs J card sim a Java card uh simulator as unit testing and we see that that's the whole proof so that's

the whole communication happening between the card and we see that verification verification uh succeeded in in jart teim I'm going to go back for for everyone to be able to um get the GitHub link so the main takeaways here latis based crypto really did enjoy a bad reputation on key sizes proof sizes and ZK we did reach though the level when it's in some with abuse of terminology and some techniques it's arguably uh more efficient than pairing based stuff especially in restricted

environment that has been covered not just by me today so up to the point when it's takes like roughly six seconds to generate a proof on 30 mahz kind of acceptable and for very basic circuits it only takes off roughly half of the storage available on a modern smart card for you one last observation that I still didn't explore and uh two things that the implementation won't contain the interesting part because this might yield even more efficiency in the whole protocol the aditive of homomorphism used uh in the sacp generalization for circuits could

potentially benefit from uh modulus switching so when you additively add together ring learning with iror Cipher text at the very last step you can transform that Cipher text into another quotient polinomial ring that takes much less space and this I didn't Implement and has never been uh tested so we can potentially after the circuit generalization which obviously blows up the original protocol we can go back to the original quent group size second stuff that um that the the implementation doesn't cover I'm using continuous gions for the secret key generation and I round it to

the nearest integer and we know that that kind of breaks statistical ZK we don't know any attack uh against this type of key generation but statistical ZK only holds if your goian generation is truly uh a discrete goian generation with rejection sampling or or something else so for for efficiency purposes I used continuous Java SDK Goan generator and rounded it to the next integer but it shouldn't really affect performance that much it does affect though statistical uh security thanks for the attention I'm going to go back to the GitHub link for

everyone to access and yeah share observations maybe even uh the rejection of sampling key generation in code thank you thanks a lot do we have any questions yes what assumption are you making about the ballot or you're not making any assumption it's a free format come again like you're voting right it's a voting Protocol no yeah well I didn't really assumptions what's the format of the ballot of the what of theot choices who you're voting for this sche can be

generaliz not I sorry I don't really get the yeah the voting use case yes vote expressed what's the format of the vote that I really didn't get into like but identity protocols do induce uh voting protocols too because that's the main uh problem that you have to overcome here for so I don't think made any assumtion this is I kind of yeah thanks for the help

though yeah I kind of uh starting to get the question I don't have any assumptions on the form of voting yes any assumption but that's kind of the main takeaway so identity protocols do yield efficient voting protocols and if your assumption doesn't fit into that then in very worst case which does blow up proof size is communication cast you can always turn to circuits and that's why I covered both sides of this use case there's no this is justor I don't feel comfortable sharing that like are you limited b side like in terms of the the size of a b you're not the parameter size do yes yes they

do limit yeah you're convinced or you're not convinced okay more questions uh to these methods scale up let's suppose you don't care about smart card you add a big Pro on a big big computer I mean this seems amazingly efficient does it scale up to large problems yes and the ver um the ver that you have to put yourself

up with is complex circuits the trade-off that is yielded here complex circuits start to to uh yield or start to result in much more storage cost than what you would get with plunky or or paring based instantiations so this fits into restricted environments because I selected the circuit posidon pre-images that can go to Identity identify yourself like identity use cases or voting but of course as you turn to more complex circuits then you quickly see that the curve turns towards the more efficient generalized uh snark versions so it's a nonlinear blow up

then like super linear the blow up yeah at least at least because of the strictly Ain PCP like yeah the bridge between normal PCP to sa PCP will make not sure but at least super linear yes okay further question questions yeah if not then let's thank s again [Applause]