EthCC 2: Silur

so hi everyone thanks for coming and thanks for the organizer - for inviting me since I couldn't settle whether to call this talk natural crypto Mansi or crypto necromancy I settled with an attempt to revive non-commutative cryptography and I brought some blockchain applications for this area quick question how many of you have encountered non-commutative cryptography Oh quite some okay I brought some interesting topics for you - so we were going to have a quick recap what this area of research is why it is especially interesting in blockchain applications and as I promised we will have some cool examples of that so non-commutative cryptography were started by Wagner and Majak in 85 they made a pretty simple public infrastructure public key cryptosystem based on able-nan Napoleon groups of course this system found out to be unsecure but it was really interesting a new perspective for cryptography and started a new area of research so the basics of non commutative non abelian cryptography it's the area formerly is called combinatorial group theory it has nothing to do with combinatorics it's I like to express it how groups work together the representation that you see above is called the art in representation it's a universal representation of every group ever you will list the generators for your group and you define the relationship between your generators it can be infinite or finite various kinds and the representation from these groups is the union of the generators and the inverses and the group action is that you just put them next to each other just string concatenation this this is gonna be really important later for I in the blockchain use-cases part the group action is just throwing concatenation there are some fundamental problems in this area for example the word vert problem this should be familiar for everyone with a computer science background the cone u gives the problems this shouldn't be that familiar it's a much harder and much interesting problem not just in cryptography it's widely used in physics and chemistry too it's it has search proper variants decisional problems blind decisional problems various kinds what you see here is the blind search problem and the decomposition problems that recently started to became popular so once we have the representation theory okay we have defined that how we write down our groups that's it ideal for this kind of cryptography we have to actually find for one so we have requirements for these kinds of groups too of course it has to be well studied as usual in cryptography the word problem that you saw should be solvable in linear time deterministically and the trapdoor problem that you are using for hiding data should not have a polynomial probabilistic time solution as usual and of course it should show exponential growth with the basis the basis here is the generators in the Archon representations left side so one of the mainstream the most common platform group for noncommutative cryptography were the braid groups this is how a braid group look like it has a an algebraic and the geometrical representation you can see that geometrically this is these are curves with an additional Z dimension that gives death and two braids differ from each other if you change the depth between a crossing and anything else how you pull the strings if you don't change the crossing orders you're basically looking at the same braid this is going to be important representing braids on computers have ridiculously small computational and memory overhead is why initially this this was an interesting part of cryptography research sadly the conjugated search problem has a deterministic solution but happily it's still very very an unofficial so this was the Golden Age of great group cryptography and how they died Bigelow and Kramer proved that actually break roots even if they don't seem they are linear they are a subgroup of the general linear group and that's a really big slab in every form of cryptography who remembers the algebraic eraser it almost became the iso standard for a graph ID card public key cryptography it was like a huge deal super efficient low-energy assumingly secure but it turns out that it were not there since kramer came up with Lars Kramer normal form they found an algebraic span attack and the ISO standard was revoked and in various area from physics there there was advances in new algorithms for solving the decomposition and the conjugacy problem so non-commutative crypto were like officially tied in order early twenties so where are we now up to best of my knowledge this took like one year to collect this data and if you think or or so any other advanced with this please note me but up until today where we are with non commutative attacks and cryptography and properties every solution for the conjugacy search and decision problems still need to generate all the supper submit sets these are minimal commutators for a selected element you can see the complexity of searching with the best known algorithm called a cycle D cycle attack here is the the complexity of that and it may look of course it looks polynomial but there is a catch here we don't know about for K the bet there is a conjecture that it may be polynomial but now it looks like it's exponential so take a note that K is is unknown in the equation mostly in in terms of N and L where L is the length of the braid so all other conjunctions there are several several papers of braid breaking great group cryptography but those are addressed for special braids group cryptography is where they are using special braids like the necklaces were Oberoi or sliding slats it's not a general solution for all kinds of non-commutative a billion groups so there has been some positive advances also so it turns out that you don't always need the one and all the conjugates the search problem because basically any non abelian group that has only one sided distributivity is a very good candidate to research for noncommutative crypto like the general linear group mart matrices we have plenty of cryptanalysis tools from this area so how many of you formally expressed security in complexity theory terms with generic case complexity it's kind of a new kind of complexity expressed for reasoning about complexity because in cryptography we have average and worst-case and they are like half of this root from different sides it's it's just not enough to reason really really well about cryptography well generic case is one and it it was invented from guys who worked with non-commutative cryptography called basically accurately a sewer line and and others so another advance that I personally like some of you know that I'm really into post quantum and fully homomorphic encryption system is that most con you get research problems and decomposition problems fall into quantum ha complexity classes by default so this is my personal idea it has some mathematical reasoning but this is where you can attack this whole talk in my opinion the linearity the the advanced by Bigelow and Cramer the linearity of bread groups is a scalability problem it just means that in the later examples the commitments and the public keys will be quite large but it will be efficient to compute on and the security is not that much broken we have other groups to work on so all the RIS cryptanalytic or breaking algorithms that I've spoke now is specifically made for break groups and I've said that we have several platform crews like Tom's on groups love our tables Mayim at matrix decompositions that are not addressed by these attacks also the shifted conjugacy so here is the key for this talk why I choose to be the topic on this conference is that because only non-commutative cryptography has the ability that if you change the underlying platform group it's invariant of the communication history so if you take a thought experiment and express elliptic curves as in art in representation of the parameters of the elliptic curves you have vai and the relationship between your parameters is the equation of the elliptic curve but you can't just concatenate together your secret key and the generator the group action is different you have to multiply this according to elliptic curve mathematics but in non commutative cryptography you can just put your secret key next to according to the relationship next to each generator and if you change the underlying group the logic is not gonna change so if we found a better way a more scalable way for break groups on an ideal world where aetherium uses bridge root cryptography we can scale without losing any transactions private keys alone or disproof witnesses whatsoever so here is example number one Ezequiel snark with brain Group cryptography you have user secret key and a private key as usual on the common reference string the public key is the conjugate of your secret key of course you have bases and or not to express logic and if you have an n-bit algorithm you have entered three braids it's stranded rate this is gonna use black bread groups for a platformer group but but note again that this can be any kind of other platformer group so you have to take care of eliminating most free sub subgroups we haven't spoken about freeze rap subgroups basically you have to avoid them in this kind of cryptography because they have really efficient solutions for breaking your system you still have to leave some free Throop subgroups in in your system and is better if they are in finite but you have to take care of most of them otherwise users can generate secure keys in the case of braids because only positive braids are free you have to somehow Express whether to use a positive or a negative exponent so I just use the binary key for this where zero Defense Initiative and one positive exponent for the generator and now you express your data with another braid and conjugate the commitment of your binary circuit we don't hear that I called this Zika start with trivial gadgets because even though there are more efficient and and more secure zero knowledge proof out there you can't really work with them because the effort you have to take from your Arkell algorithm to reach a boolean circuit or vectors to wrap or use Pinocchio or bulletproof is enormous like it's too much work and there are some really nice efforts on that like Socrates and stuff but using non-committed cryptography you just have to real able your boolean circuit it's one - one transition from Euler algorithm to a representation where you can use a form of cryptography here is some absurd a code for that this one already uses the Fourier transform to make it non interactive I basically just has your commitment and if I get a 1 I prove that my commitment binds to my input and if it's a 0 I have to prove that the commitment binds to me you can optionally of course omit this it binds to me part if you are not using authenticated snarks like you don't have to verify that X or or Alice is the person who made the proof is just valid and here you see a binary adder and subtractor generator based on Bray's day it supports arbitrary length binary addition and subtraction and you saw that it's like it's five lines it's quite trivial and it's part of my research to make a complete test expression gadget leap based on braid groups braid theory for awasum we have second example the guys behind mix at will be giving a talk today so I'm not gonna ruin the fun but verifiable shuffles another quite trivial think you can achieve with non commutative cryptography if you remember the image if you just remove the z axis from the geometrical representation these braids induce the permutation so it's just the perimeters permutation and this z axis can serve as a key if you remove remove it from the brain and iterated asking whether you know the original cone you get of it proves that you know the initial braid behind the permutation you achieved a verifiable shuffle and my favorite example how many of you are familiar with identity based encryption ok the same the same guys so I consider identity based Crypton a mess crypto adoption goldmine it's the best thing we can ever dream of except that it up until now relied on a trusted third party but last year there was an advanced called a registration based cryptography where you don't have another trusted third party generate your keys for you there is a curator that just holds your key it's kind of similar to a IP c31 a seven to one where you have a proxy contract for holding the keys the trick here is it's not just a mapping like on a storage level it's mathematically cryptographically your public key is made to look like your driver license plate passport number whatsoever you can ask how your public key to look like and it can look like anything so how do I say governments can can easily transform from a centralized and trusted infrastructure to two block chains in a little over of course it's really unlike this will happen in the future so registration based encryption relies on indistinguishability obfuscation and somewhat statistically binding hashes and you can achieve indistinguishability obfuscation with bread groups because different conjugates for an algorithm will reach different obfuscation for it just a quick recap on i/o currently software companies defend against reverse engineers read programme obfuscation but everybody they do it now is just obscurity you measure the security of those system with with Russian teenagers and energy drinks within indistinguishability obfuscation is truly cryptographically secure and you measure the security of it in bits so it's the one and only true form of program of obfuscation you can achieve and it can be used to construct fully homomorphic encryption zika snark whatsoever so back on track different conjugates for a boolean circuit expressed as a braid will yield two different obfuscation and you basically retrieve the destination all problems that it relies relies on so what's the actual security for a for a boolean circuit expressed on on braids so the you saw that the theoretical bastard algorithm for solving the conjugacy problem the cycle decycle algorithm has this particular complexity class I've evaluated it for sha hash with hundred bit byte input and it reached or we can see the exponent okay it reached 129 or a bit of security with this complexity class so it's still this is again my personal staff break group still has a bad reputation but in my opinion it's not so bad so 129 bit security is quite good I think so my closing thought even though non-commutative group 2 has a bad reputation and and it deserves it it had some really big slabs and advancement in all elliptical breaks and stuff but that's only one part of use cases for noncommutative crypto I don't see any reason leaving elliptic curve research dad because NIST internists curve has a backdoor it we know that it has a backdoor and we didn't abandon elliptic curve cryptography are not that much of an ideal platform group for non Abel in cryptography and we completely abide abandoned this area the immutability primitives like they are invariant of communication history is a cold mind for blockchain use cases this is this prevents hard Forks on cryptographic primitive updates we can trivially construct boolean 0 planes from boolean circuit we can trivially construct cryptography representations so wack you can use any form of protocol based on it and it's not by default because a VPP is somewhat quantum secure but it's really close to being somewhat secure by default so if I have any time left I'm ready for questions personally or any of the contacts about me thank you very much for the attention [Applause] thank you for a fascinating talk I wanted to ask experience teaches us that once there's one polynomial solution for the problem there's gonna be better and better Pournami solutions especially if some entity has an incentive for this we see this over and over again the reason we use the or knowledge books is because they were super inefficient and then they were we all decided that they're super great for industry and then they got improved and improved and improved why wouldn't this happen for noncommutative a cryptography so why would you feel kind of safe in deploying it even if it's upgradeable as you say safe in deploying it knowing that maybe as long as there's a big enough bounty the algorithms will get better better than better there is a beginning of bounty so I've said that conjugacy the con you gave the search problem is not just a uppers in cryptography it's variously used in fluid dynamics and physics and chemistry so but this is one of the advantages also so this is an area that not only cryptographers work on and this is why I dared to say that great group conjugate search has as much research as prime factoring chronologically this is not true because great groups have been around since the 20s but because various area of science works on the problem and still couldn't give came up with a better solution if we if this would break completely bread cryptography it would in one way change the word because of the other advances it induces and I said we can just change the platform group and the blockchain wouldn't care I will follow up but I'll take it offline I think okay then thank you again for your attention [Applause]