Merken
LatticeHacks
Automatisierte Medienanalyse
Diese automatischen Videoanalysen setzt das TIBAVPortal ein:
Szenenerkennung — Shot Boundary Detection segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.
Texterkennung – Intelligent Character Recognition erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.
Spracherkennung – Speech to Text notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.
Bilderkennung – Visual Concept Detection indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).
Verschlagwortung – Named Entity Recognition beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.
Erkannte Entitäten
Sprachtranskript
00:01
to that
00:04
and the and a and the OK and with that I'll leave you with the experts would world islamic on 0 there we go thank you all for being here and I especially year for the coming to a heavyduty mass talk at 10 15 PM on the number 2 so we are going to talk about how to use lattices in cryptography and I encourage you because we're going to be doing a lot of coding in this talk we have put all of the code in our slides online at this find website so if you want to pull out your laptops and play along with us during the talk and make sure that everything works you're welcome to to do that right now so you can copy paste all of our code samples into stage and as we're going along so here's some
01:17
headlines about cryptography cryptography appears a lot in the news lately and everyone well this an article that is not about Bitcoin the cryptocurrency were blocked and so here's a couple examples and and all of these have something in common these articles popularizations of Cryptography
01:34
Research and what these have in common is lattices so this is the topic of our talks for you today wire people talking about lattices in cryptography
01:45
so there is kind of 2 things that you can do with lattices encryptor number 1 we can break stuff which is super fun so there is you know basically every kind of crypto that you can think of there's probably some way to break it using lattices including you know but both like old so public key cryptosystems long broken public cursed cryptosystems encrypted systems that were still using today and tomorrow's cryptosystems so the other thing that you can do with lattices is make cryptography including sort of futuristic things like POS quantum cryptography fully homomorphic encryption even people try to do things like indistinguishability obfuscation but maybe that was a bad idea will find out in 20 years so OK so this talk is going to sort of happened in multiple parts were going to break stuff ergonomics of so if you get lost in 1 part maybe you can catch up and another piece so 1 is the
02:40
lattice this is not a lattice this is a lattice if I blow diselenide editing the speakers and in the room at a translators OK lattice lattice different OK so for the
03:00
purposes of this talk directly multiple kinds of lattices in mathematics kind organize talk about is think of it as a repeating grid of points in dimensional space so we have like ndimensional Euclidean space hopefully you can imagine and dimensions and think of a repeating grid of points look something like this in 2 dimensions this is a lattice of lattice of which I just want this center so massive the translators so I apologize to affine translators but is slightly more seriously AI and you can think of I mean that we're going to have sort survives start looking points but you can think of the point is actually representing national mathematical things like polynomials so later on in the in the top we're going to see lattices of polynomials so you can give each lattice point as representing some kind of mathematical objects here lettuce or you know maybe something of by the time you then all these points you need to have some structure in place so for instance from instead of taking a stand which pictures and letters all over the place we can also take some of these 2 vectors so imagine there's over here there's a 0 point and then from there we have these 2 vectors going out to lines and then these are chosen so that every other daughter you can be reached with 1 of those combinations so just to get up here you take it twice to get over here you take it twice and subtract this 1 so every dot can be which was to to think now these are not unique this is also the green ones also form a basis for all the blue ones like very long would stretch but again any combinations of these 3 and before you you can reach all the docks the the when you think of when you learn about courted systems then you learned about say the real numbers and you had like x y coordinates now here the difference is that the only allow integer multiples only entire copies there's nothing between those stops you can't take half of B 3 if you take half of the 3 you land here there's nothing that's a 2nd game played you can't stop so we can only hope till the next start and if you wanna describe these is more math then we go for coordinate systems so for instance this be 1 vector is something like 2 over and 3 of 4 up so then you would have this 1 is 2 and this 1 is 3 . 4 and then to start those to be put them in the top row this is the 1st cornered the 2nd quarter and for the 2nd vector the same thing out of tools dimensions is very small but when you look at
05:53
something like this you get the sort of a tunnel vision there's somewhere in origin and you can see it goes up to 3 dimensions now can't gonna use those with a few hundred after thousand dimensions were not gonna do this with pictures I think we would totally fine with having coordinates for those and then does the top row but I have 3 thousand entries and economy towels and thousand such alliance so each other vector will have its own line so mathematically there's no problem going beyond for images so we'll go back to dimension
06:32
to understand what a lattice is why why do we care about lattices what are we going to do with lattices so for this talk most of what we're going to do with lattices is fine short vectors in them so we saw that we could have multiple BCs for the same lattice some of them might be have super long vectors but were interested in finding pretty short vectors in some lattice given an arbitrary description of the lattice so this is called the shortest vector problem and the promise generally given some description of a lattice find the shortest vector so there are a few ways that you can try to compute this this problem turns out to be pretty hard to solve exactly as so the fastest algorithms that we have to compute the shortest vector exactly in a lattice run in exponential time in the dimension so 2 to the N in dimension and but but you can compute an approximation for the shortest vector so something that's kind of short but not exactly the shortest vector in polynomial time which is fast enough for the purposes of computer science so that you have that option also so hard to solve exactly easy to solve approximately that's kind of our set up and in this
07:48
talk of the specific algorithm that will be using to compute approximate short vectors is called the LLL algorithm which was named after its inventors Lenstra lens for low last so the input to this algorithm is somewhat basis men dimensions the output is a pretty short vector in the lattice were pretty short means that the length of that vector and if you can sort of Euclidean length is something exponential In the dimension times the length of the actual furnace vector this doesn't like super impressive it turns out to be nontrivial to find and if it is good enough for our purposes in breaking a lot of cryptography so that's the part that we're excited about so element are it some the
08:34
examples with stage which is a lot like Python plus a bunch of functions that you might not have seen before which is kind of like Python itself Python with a lot of functions you might not seen before of some of them are pretty obvious and the same as in Python like you 2 times 3 utilities 6 I what's wrong way and
08:54
if you do 2 and then add a carat symbol which is like shifts 6 for the Americans or maybe it's the left to 1 for the Germans on that is not exclusive or that's exponentiation which people people who take mathematics in the tech language for later the users 5 exponentiation so to the 3 years it on there's also to functions which do what you might expect like if you factor an integer a polynomial then x squared minus 9 is X plus 3 times X minus 3 can ask for the roots of a polynomial x squared minus 9 has minus 3 and 3 1 of those ones doing there that's the power like the multiplicity the number of times that of a root shows up to a few factors x squared it would tell you that well that's X minus 0 with multiplicity 2 and its various other functions a gets more more complicated there's some useful functions like
09:47
generating random primates this is generating what Lagrange range would give your random prime number on it and it goes up to to the 512 again that exponentiation is to the 512 power and then if you have 2 prime numbers like this p and q you good multiply them together get a big number N and hasten we were doing the RSA cryptosystem and then choose some exponent for RSA like exponent 3 and then you can encrypt a message you can do some message which is an integer modulo n and compute power now that actually is a Python function you can use power in Python itself the random priming each stage where you have to implement itself implemented yourself the how you can do in our in straight up I thought and that gives you a message to the power he modulo n and that's your cyphertext for instance the 3rd power of a message modulo at and then there's some slightly more complicated procedure for figuring out the exponent that you need to decrepit using the same power function again lots of warnings that we should be giving about how they implement RSA don't to do exactly this say maybe some of the warnings you actually see later from some attacks but there's many many more warnings if you actually can do Crypto Library then you should do something which has got a lot more protections and what we're showing you were just gonna do that kind of mass details and not get into all sorts of other attacks the out the so the thing
11:12
that we want to get from the previous slide is that we care somehow about factoring so we want our say to be secure so that we have a secure Internet which means it is to be hard to factor this modulus and so how hard as factoring I don't know it seems pretty hard let's build the Internet sense get and so for this
11:31
next section we're going to talk about how to factor with lattices so we care about factoring for the purposes of proving the security of our ceremonies establishing the security of our state so how hard as factoring really some of you might have may have seen a talk
11:46
user its let's explorers kind of the parameter space of this problem now I have sale or modulus additive colored purple and say 2 primes P and Q and P times Q equals and that's kind of a set up so if I give you P times Q and N and P and Q and and then you know how to factor in because they give you the factors so the promises rank that regard without part if I
12:12
give you an and 1 of the factors p then you can still factor and because you can use division to get q then you're done so still were were angered territory
12:24
if I give you neither of the factors p and q 0 but I just give you and then I hope this problem as hard as other where the Internet is broken a the currently sort of the best algorithm that we have for factoring in this case is subexponential time in the length of the modulus N current record nobody's factor the ROC 1024 challenge and public yet maybe the is factored numbers of the slot size I don't know but if you super excited about this topic you can see our target 29 C 3 for more information say this is somewhat hard let's
12:59
do something a little bit more exciting what if I give you something like this like half the bits of p and half the bits that you if they happen to be a range like this this tended to be really easy you can sort of divided like rearrange a couple bits and then just and recover both p and q so surprising but there's no like real situation in which you can imagine like this being relevant to your daily life right let's make this a little more exciting and what
13:26
about this this easier hard like this is like half in between something that's easy and halfway in between the some of hard where we stand this this is more exciting by so it turns out that this with this kind of information if I give you half of the bits of P like say the most significant half of bits of the other doesn't really matter which have disappeared give you then you can factor and in polynomial time even know like the remaining half of disappear that you don't know is like a gigantic you camper force that they were doing something super interesting here and it turns out that the way that you do this is with lattices hence a subject of our time so let's see how this
14:07
works so this is a little cryptographic magic trick this is all staged code that you guys can run so if you don't believe me that this works you can totally renders yourself and verify that it works so many do I little magic trick here so I generates 500 fold primes p and q totally legitimate nothing up my sleeve these like all eyes just like you know primes whatever stage so as to generate prime III multiply them together to get an the products and then I generate this value a which is like most of the bits of P except for like the least 86 OK so if I like looking at
14:46
and this value a in hexadecimal like there's a bunch of zeros in the listen if you did that is they deleted the elicited that's so I learn most enable like not all of it and 86 bits is enough that they definitely shouldn't be able to brute force so far my laptop and I wouldn't even be able to run like a square root of things on my laptop in sort of feasible time to get this done and in time for the talk so what I want to do is to recover my factorization of the arts a modulus and here with only this partial information about the key not the full so how do I do
15:22
that I construct a matrix so we talked about 2 matrices A lattices being somehow connected and my matrix contains my value a which is like the bits of p that I'm allowed to know and then and some other things that are also public and then I run my magic l over the monitor OK so here comes the magic trick now I take the output of the yellow logarithm I construct a polynomial somehow from the vector that I got from l l and if I compute the roots of that polynomial i magically recovered p magic the rabbit appeared again and you know I don't know where it came from what has happened because I hope you're confused because you should be confused but I believe this works like somehow magic happened it I have factored very efficiently again so this is
16:22
an example of what's called coppersmiths method so cover it is 1 of the greatest cryptanalysis of the 20th century and probably 1 of the greatest cryptanalysis of the 21st century except we don't really know cause he works for the US government out but hopefully will find out in 50 years I'm super excited and so anyway I mean like yeah his all of his work is amazing and really so what the something about public the so I and actually like his original paper from 1996 that describes sort of the generalization of this method is pretty hard to read so what I'm gonna presenters kind of a simplification which is due to how program several years later but of course the simplification still has multiple steps and looks very confusing so that's sort of the state of of cryptanalysis um so I will explain what's going on in English and this will probably still look like magic so what I just did in English step by step is I wrote down some polynomial in this case is a linear polynomial onto a plus X X is going to be my unknown that has a pretty small remark P don't window peas i know that p divides and I know and but I don't know p but somehow this fact still helps me I constructed a lattice basis from the coefficients of some polynomials that I could just write down that I knew that vanished mod p if I evaluated them men are a you know a blizzard sleepless x squared and sounds good for them in a lattice basis run LOL on this lattice basis to give me a short vector and then I turned that short vector and pollen polynomial again and then compute its roots and magically the piece of the prime that I was looking for it is 1 of the roots of this ponymy and I can prove that this is the case but this is like magic the lattices doing something
18:12
at this point I'd say 0 kind of like the thoughts you know when a miracle cure occurs where the miracle is somehow l like you throw some crypto keys and LLL and like magically private keys fall out I don't know what happens let me give you don't even like mathematicians have been studying that this stuff for years we still feel like this because words way better than it's supposed to we normally know life and so uh so yeah you can if you don't believe us we have fully weaponize code on the website you can try it out and you know the way you can get from it
18:57
this so when and a trip to there was a lot of these studies on coppersmith had published a paper in whole graph dominated comprehensible and there lots of grad students publishing a paper want if you know not this piece of p but that piece of p all this piece all some chance of some some kind of theoretical papers by would anybody be so stupid and give you a whole triangle of of p I mean idea was artificially cutting off the last 86 bits this is nothing that you would see in practice that 2012 at the 1st encounter with covers miss in the wild this was just after 2 93 when he gave a talk here that a friend of ours said by the wave effect at some time in the smart card keys and on the kind of funny now fast told this year there was a great paper at this year's Unix users Conference on a group of Czech researchers and they did notice that some carts bind Fenian that's a big Township manufacture and if you have some of those from external BGP drives a such that might be having such chip so they tended to Rocha return coppersmith and when the news sometime this fall and that notice that Infineon is generating the primes in a very strange way this is not how you generate types I mean you can search for a whole bunch of those things and you'll get a prime but why so what was known year was M and with a lot of massaging and searching around they had managed to get this a this will exponent a there allergies also known that match to get this ain't was sufficiently small set that you can search so then big 1 of those bases computed a modem enters covers misdetected get k you get a number yeah then probably it's a vector test you don't get a number of well too bad so just try this for each of those these look the same like ideas and there's the letters anatase talk part just 1 dimension 3 but someone large dimensions and in the paper go through lots of variations of how we can trade off the number of AC of to try for the dimension of the lattice so there's a lot of trade offs but this ache she affected 1024 bit and 2048 bit RSA keys that were used in real life it say of
21:27
course was much more and thank you and you can use as we here then Shaw's algorithm is going to factor or a say 10 24 hours a 2048 hours a 4 thousand 96 is going to be a nightmare when this is gonna
21:51
happen well that's not entirely clear there's some predictions for instance back in 2015 when we gave the TTC stock might mask other deputy director of the Institute for quantum computing at the University of Waterloo said half chance of factoring our 2048 by 2031 and then just this year Darío deal was this is somebody who's the head of that said vicepresident at idea and the head of IBM q now with within like you thinking about the James Bond films this must be something cool and it is this is IBM's quantum computer dare I say weaponization division this is the commercial quantum computer division the actually working on building a useful quantum computer that they can sell and he says he has written a look back in history and say that the 5 year period starting last year is like the real start of quantum technology not just research as a scientific field and use advertising their 50 Cubitt quantum processor has just compare to what you need for sure is over them well the usual estimators that Shaw's algorithm needs 2 times the number of bits in Europe or it's a modulus somebody else's hours in modules that can that that would be illegal your own test are as a modulus either you tried factory need twice that number of Q. that's Pershore's are run thank you these quantum bits inside a quantum computer to has that comparative maybe 5 cubits last year 1749 enqueued that's this year to 100 cubits next year sounds like within a few years will be up to 4 thousand 96 cubits and that's the end anniversary 2048 except well it's actually a little less to panic about on this given these few years further because Shaw's algorithm needs 4 thousand 96 perfect cue that and what's being built RQ bits that only last a little while and then they degrade and you have to do some sort of error correction and it's not like a normal error correction you say the same thing 3 times 3 times 3 times and if somebody only word it wants to develop and figured out if they heard it twice with an error the figured out effort for quantum bits you need like a thousand quantum that's a thousand times you're the size you computation to simulate 1 good CUDA assuming that you're cubits or the level of reliability that we think is reasonably achievable which means sure needs 4 thousand 96 times a thousand students that and that's several doubling further away it's going to be some years maybe like 2031 before somebody in public is factoring ROC 24 so what we
24:28
do about this well close quantum cryptography there's lots of replacement for I say that we don't know how to break with quantum outcomes lakeshores out and missed a year ago called for submissions of proposals for standardization and they got the deadline was the end of last month we got 82 submissions they put at this table which was classifying these submissions into there's there's a latticebased codebase multivariate space you can see the numbers for encryption and signatures numbers of submissions at TQC hacks we talked about code based and hashbased because those the oldest lasting post 1 proposals there's some systems from 40 years ago code based in hashbased proposals which seem to survive quantum computers and there are also lots of code in hash based systems that more ma much newer but at least there's some that go way back and if you're willing to pay the expensive them than it seems that you can get security at what that means is nobody's come up with a quantum algorithm that breaks the a lattice based in multivariate those go back about 20 years there some lattice in multivariate proposals that we don't know how to break even if somebody built a big quantum computer and then other there's things like I sergeants published about 10 years ago 1st proposal somebody came up with a pretty good quantum attacked now the supersingular isogenies which have held up for a few years but maybe they don't continue to hold
25:52
nist put up a week ago the list of submission so we'll be hearing quite a bit more about these submissions not in this talk that over the next few years as people study the security of these and figure out are these things that we can actually trust to protect their data against the big quantum computers they only posted 69 instead of the 2 that they receive because they said well the other 13 were not complete not following the rules so we're down to 69 submissions a week ago and now we're down to actually somewhat and fewer submissions on so there's some that have put in red here 3 hours after Mr. posted this list of submissions I guess again is in red there are Lawrence Penny who might be in the audience on and in any case you'll be able to see the videotape later yeah he posted a script which retrieves a guess again plain text from cyphertext without the secret key so that's the end of gas again and that was OK 3 hours and 10 minutes that's good work uh life have of be another 1 there I also broken by somebody named lawrence penny arm and then let's see OK case 17 that's 1 Italian I put up a script that brakes on rock costs that's 1 where are that actually I should say that the threedimension before age to 17 you guess again those a all the submissions in there maybe not things have been studied so much what about a codebase submission like rack cost Windham kobe signatures kid who well Tonya II and also under this whole and also something important spending are posted a script which well completely breaks right cause actually came up with 3 different attacks and this maybe it's OK with bigger parameters but it's not something you should use with the parameters we submitted and then another example here of 5 or what Dutch people in the audience was is called hell last on this proposal is well it's it's OK if you use it with signatures that start chosen cyphertext attacks if you have somebody else giving you signature scheme like until as but the submission claims chosen ciphertext attack security and we posted a script we well done in again and man who wrote that I'm drink and also somebody named lawrence 1080 p watch out for this guy I right so at this point there is still some submissions left and um will be hearing more about what gets broken by Lawrence and maybe some other people in the future
28:37
thanks OK so here's a measure breaking the listing some words they just to do for fun
28:52
so I want to show you know the variation of how to break are the with lattices which is the Coppersmith small public exponent attack so right this is audience participation time His code right so I take a message which is squeamish loss of frogs how we pronounce that I turn it into an integer by making it base 35 this is just like like printed out nicely on screen there's nothing really complicated going on here I generate a perfectly legitimate RSA modulus and it has 1024 bits and I encourage my message with RSA by me lot and I is a problem here was the problem 2 small thank you get to people the audience is the following day we got a problem which is that's theciphertext is smaller than N and in fact it's like the message cubes is going to be smaller than and so this like modular reduction and doesn't do anything and we can just compute cube roots are the integers like easily so this is not secure are as encryption can problems problem this is this is why use of padding schemes for our 1 of the many reasons that so messages to small rescued lesson and modular reduction does nothing that means you're not actually doing on yeah here's a variant of this problem but
30:20
it's a little bit more complicated so I made my modulus and a little bit smaller just so the example could fit on the screen uh but like that's not going to be the issue here so generated perfectly legitimate parsing modulus N 300 bits I'm not gonna turn a factory even notes by possible and so now I have a message which is the passage for today's swordfish turn it into an integer in the same way as before not only do anything super complicated ID textbook RSA encryption by keeping the message might and OK so since I since my messages larger in my in my modulus smaller I don't have the same issues before I just write compute the cube root of the cyphertext it is not equal to the message so I've not broken way but there might still be an issue so maybe like since this message has a particular format you can imagine an attacker could guess like the message is the password for today something and maybe there's like whatever password it is and maybe they know that it has 9 characters but they don't know what it is so can a computer that so
31:25
maybe the attacker have guessed that the message looks like this where they don't know some chunk of the message but they know the rest of it through some attack so I have my secret value by my evaluated the attackers guest given the magic trick again so I construct a matrix is gonna be a lattice basis from my guess is what the message looks like and the cyphertext and the modulus and I just like filled in some zeros for the for the part of the message that I I don't know yet OK so I have a lattice basis would I do that I run aloe on it as before I get some vector I construct a polynomial from the coefficients of this vector I'm still magic and when I look at the roots of the polynomial I got the piece of the message that I didn't know back out again that it will be present in scared into never trying to implement hours and you're in the place so
32:37
OK what's going on it looks very much like before so I'm gonna write this in English I don't expect you to necessarily be able to like prove that this works but just like verify that I don't know like were doing something I wrote down some polynomial that has is pretty small roots so in this case the I I don't know it's swordfish is but I know that swordfish plus the thing that I guess for the message is is my message in and I know of a cube that mind and then I get the cyphertext so some you know swordfish plus a cubed minus the should be 0 my at some polynomial in magic I construct a lattice of the coefficient vectors of polynomials that vanish mind and 1 of them is the thing that I wrote down there and I don't know like n times x squared things get I called El Al's magic happens anyway my hands and then somehow I got upon meal out of LL and my solution swordfish was the root of the corresponding upon male so this is coppersmiths small uh are the exponents attack and there's a bunch of variants of its it's super cool and so if I just freak you out
33:50
some here's some countermeasures against Coppersmith sort of patting attacks small exponent etc. you could if you did hear about the stories are as I've it's 1 option but if you must use are as a user proper padding scheme are LEP that kind of thing but if you must use odds they don't use small excellent he like use x linearly 6 5 5 3 7 this definitely doesn't work yeah so so where she didn't come the intermediate what hours a the whole time we also talk want to talk about constructive uses of letters and so on and talk about 1 of the oldest of the latticebased cryptosystems called and true it's due to of saying that the Python so men publications 98 there's even some pre printed and online from 96 and every looking for just some as far as ATCC they're pretty aggressive and advertisements and they did manage to get speech that possibility curves and are is a on committees see this whole had larger key sizes and models have a text but they were kind of going forward just as in all competition there were not so much running the all we might be secure against con computers even though shows a paper that appeared this was not so much on the mind of people now they did a similar system and an encryption system and the signature system see multiple signature systems had a bit
35:20
of a bumpy right the I remember being a captain 2006 than from me and was giving yet another talk breaking some of the interesting just systems and you was like so the who when the owners has not yet broken and signature system as well for the designers of delivered ball like that the the encryption
35:43
system has held up better than at the beginning a little bit too small parameters but in principle this was fine and so there was a bunch of code announced in the last 20 years but there wasn't all that much of a research into how to use it efficiently and then just because you have a nice mass system like is a you take into the 3 all the things you just seen are proper artists 80 but improperly used so secure usages is usually big issue it but not much happened on that think partially because our and then to company had decided to patent this thing and we all like why should I spend my time investigating in a system which I Convex you free use afterwards by now the pattern expired some have to talk about it and say well let's look at how it works and maybe you can break some stuff 1st of all that to understand
36:37
how inter works so was R is a you've seen you need pretty large integers with n sure we need polynomials and there's 1 system parameter which is N. which is the d limit on the degree of these polynomials the set of integer polynomial so you have coefficients 0 1 2 minus 5 and whatever and then for the examples of initial like loss less than 250 like 7 or something if you have 2 such elements and you want to add them you can just do this coefficient was so the EIS Europe must be 0 is a coefficient of 1 in 1 must be 1 is a coefficient of X and so on until all the way till x to the n minus 1 which has a minus b n minus 1 and the 7 minus 1 we also want to multiply that's nice you multiply polymer of degree 3 was 1 of degree for the getting something of degree 7 but we want like to have something of small degree so we need some way of wrapping around and so define a thing called a cyclic convolution where you basically rat everything around after n minus way minus 1 and the rule for this is the coefficient of X 2 1 for instance the v e a r i a i b j these 2 indices so they will sum up to 1 or n plus 1 and for the x to the n minus 1 they will sum up to the n minus 1 so I might as 1 the
38:14
whoops they will sum up to X minus
38:18
a 2 n minus 1 OK so this is our explanation of which we can compute we can work with that we can teach it to a computer if you want to know where it comes from is the same slide was a little
38:29
bit more math notation so that she doing is work in the polynomial ring that's just a fancy way of saying polymers into the coefficients and then we reduce modulo X to the n minus 1 this is the same kind of function that we say we use what 7 but we take every model of 7 and replaced by 0 PM replaced every model of X to the n minus 1 by 0 or take x to the end and replace it by or and then all the operations just look the same way except that they have to write n minus 1 there what let's see some numerical examples our goal
39:09
and starting with a little bit of incomprehensible stage notation for creating a tight classes the X which is going to have our polynomial objects in looking in an example that others have here is a polynomial 4 times x squared plus x plus 3 2 3 terms in that 3 things being added up to the coefficients of the images for 1 and 3 that are multiplied by x squared in X and 1 this is degree to that's the the biggest projects that you see there are the exponent if you multiply then the distributive law says to multiply each term that you're adding up by a every other term you're adding up like if you multiply F times x to be move by the 3 times x get 3 acts both by x and x critic squared and so on and all the times you're just built in to see another example multiplying by the so the polynomial g there's a bunch of things all go through all of them but looking at the last coefficient of F that 3 they gets multiplied and 0 point with the mouse here are the 3 and F gets multiplied by the 2 in g and that gives a 6 and the 3 enough gets multiplied by 7 times x giving 21 times x where 23 times x will is also 2 times X which adds to the 21 times x giving 23 times x etc. You can multiply all these are just all it do the work for right what about that multiplication operation with the and coefficient things well this is how you say that and say you take 2 inputs and coefficient polynomials of gene and multiply them the percentage knowledge is like in seem odd x to the n minus 1 for instance if n is 3 then the same polynomial f if you multiply F by X then you get the same 3 x and x squared and for Q and what happened to the fore excuse to turn to the 4 if you see x to the end it turns into 1 if you see the and was 1 turned into X and so on and if you multiply a by x squared then it will rotate the coefficients again and another example the same f and g from before if you do the convolution you multiply F and G and then replace X Q with 1 which means you add the 29 into the 6 producing 35 and so on leaving you with only and course
41:22
but back to the description of the think of little more comfortable with our elements here so we're gonna continue working with polynomials but you saw the last examples but then if you imagine multiplying multiplying or explantation you see that the coefficients get larger and larger so similar to ours a we also need to reduce mod l go see the sea and same schema justified as before we will need to have some reduction here so there will be another system parameter called q does prime it's to be that chapeau power of 2 and it just means we will have all coefficients are bounded by at most q so when you wish q we reduce model there's 1 condition that he was not only because we also have free running around as another thing would be reduced the so we have 2 things to reduce by will have this x to the n minus 1 so will reduce the degree and we will reduce the coefficients so every single coefficient each of those M coefficients will apply the reduction what all reduction what 3 to them but we're now ready to get and show public keys a private keys what we do is we pick tool such polynomials got even more restrictive because we don't have small so this 2nd G will only be allowed to have zeros and in a few plus and minus what's the so this is much much smaller than q will does allow a few once in a few minor sponsors going be fixed number of those 4 f and a fix some of those 4 G and then on our Saviour multiplier was to sing so here we have a different operations will search for 1 h such that h times f was this sector convolution will give 3 times g fun the doesn't work so it the try again so if it doesn't work at the time with a different answer yeah when you think of the math notation which dividing by the staff and not always find good will become divide by 0 so some of the to throw away and try again so all public key is gonna be this H and the private key is going to be the f yeah H and F for that we can deduce that is redundant to remember a some are we done information we only computed once because well take some time it's gonna be called f 3 because it runs along with the reduction what 3 edits such that if I take F times F 3 I'm getting 1 so there is a polynomial where all the coefficients for all the powers of X as 0 except for the constant the OK I got to the fullest slide in the
44:17
talk so this is explaining how to encrypt and of the crops except for don't do it this way I mean this way you get all the pending attacks and whatever but this is giving the the hop math problem so this was a down to something similar to ours AB save after factor similarly he became distill the EntRel problems the if you want muscles in practice you have to be a bit careful how you should see and you have to put in some paddings you should really what don't you this way so we have some more slides of how to use it but let's don't wait for a part in a message m do some stuff get a cyphertext to some more stuff and get em back FIL some attacks is gonna be put assembled the pick another of those polynomials was very few nonzero coefficients again limited to plus a minus 1 let's call this are and then the severed x simply part times the speech which was all public again this modification which limits everything to degree less than n and then we add all message so we need to somehow get all message into a polynomial which has coefficients in this set plus minus 1 and 0 but there's no restriction on the density this can be told me everything plus 1 can be evident that minus 1 no restrictions the so when you take a message internally and then replace poles of 3 with powers of X so getting mn there no big deal and then a caption was easy then you have encountered you send the cyphertext over and I was a question how we can get this em back so we basically would like to divide by h but divine H. compasses use because 8 is public anybody could do that and there's always am sitting roughly will be an inexact division so if we wouldn't have any of the reductions mod x the n minus 1 this would just be divide page and take the left over take the remainder because we have this reduction to then 1 x 2 n minus 1 this 1 is not possible yeah now here's the way that BG crypto crypt if we have the secret key it is thus I've attacks the multiplied by if this was our 1st secret key and remember the relation between the public in the secret key that was 8 times f is greedy you know putting everything so we the plugin see this have a text that was R times age plus M the and then we move things around I should have said these modifications of fully so that we can move things around us distributed if it's commutative everything you want OK so we can move this if it makes the and F times age gives a 3 D the the 1st time simplifies to R times 3 G and the 2nd term OK now we have F times every em this running around but there is now a free the 1st in the 1st term so if we cannot reduce much 3 we don't have to worry about the R times 3 G term and they have this f 3 running around which is multiplied by at is 1 so if I have this 2nd part if times m because I got rid of the 3 by reduction then I have this times 3 it gives me f times f 3 which is 1 times so it gives me at best if account so I've been kind of glancing over that any to reduce mod m every once in a while so partially because else would see some growth so that's the important part in the encryption function and then down here in the D capture function I need to 1st reduce reduce what cubicles else's relation the station's airforce 3 only works what killed and I also have to move my representation to something specific nominees I tell you what Q you would want to have 0 till q minus 1 and now shift this to be symmetric to 0 so now going from minus q over to talk you over to that's how this works so this is that moment in
48:50
waterfall software engineering where they're just drop the 100 pages of documentation on your desk and said implement this this is what the designers of the perilous it actually works so say forget the computer during itself this'll be with smaller Anderson cues in these and what these number coefficients and in Athens on by smaller parameters and you can use but that said we saw fit on the slide so i there's 1 the functions you can find on line is random Deepali this is not a state function is something which takes as global variable D and give you and also and gives you a polynomial that has well D in this case 5 plus a minus 1 coefficients out of well a maximum of 3 goes up to x to the n minus 1 to at most x to the 6 and there's some random polynomial and then there's another function that we put up golden verbmod prime and that is doing this come up with f 3 f sub 3 which well what is it has 3 supposed to do let's check that's what it's supposed to do is that if you multiply F by F 3 was in multiplied so assistance convolution operations on when you multiply F by F 3 exposed to be something that's 1 mod 3 and F you look at this and ignore all the multiples of 3 like 3 and minus 3 then all left with is 1 so think of this as f times of 3 is 1 my there's also some inversion large you that was for computing h the public he was well some formula with some duties in threes and divide by f at some point well as q is something that if you multiply it by f convolved with enough then you get 1 mod q q is 256 in this example and yeah 257 mod 256 is 1 and these multiples of 256 although it alright and then G is another secret and the public key is 3 times the 1 over f times g modulo Q and there's a weird thing that happens here which is this minus sign now if you're accustomed to mind in SEE YOUR lowerlevel languages then it'll give you negative outputs if you give it a negative input Mont something of cities is easier film multiple of Q. you'll get you'll get 0 we say much you if you have a negative number you get something between minus 1 and minus of Q minus 1 you have a positive number you get a positive result which can actually be a real problem for crypto leaking whether that input was was positive or negative in the math description adventure there was some footnote in some part of the design document going in and make sure you only release of a range of exactly Q numbers between 0 and q minus 1 hour what she said between something like minus q over 2 q over 2 minus 1 and then if you leak well whether the input was positive or negative that's actually maybe a security problem so instead of that we have a function on 1 which is balanced mod which always gives a result which is well it's like a normal sign character assigned by its between minus 1 28 and and 127 if q is 256 are and that's the public key no more leakage of whether the original inputs was positive or negative and to check what this arm Q was supposed to do the whole point of H is that if you multiply each by f more by the public key by this important for the secret key modulo q then you get the same thing as 3 times the the random that was come up with another 6 all right let's see
52:22
if we can encrypt and here's a message just bunch a random 1 zeros minus ones and then another random all that was showing up in the encryption and then the cyphertext C is you take h times public key and then add em to it that's this convolution of ancient or add em and then reduce mod q and that gives students a randomlooking bytes some randomlooking bite and the corruption was multiply the cyphertext by the secret f reduce mod q and then Tonya mentioned that while this is going to be the same as 3 times g times or a plosive times M and then wealth and multiplying that by the F 3 and reducing mod 3 finally gives exactly the same as the original input message so the system actually works it has successfully decrypted a message from the size of
53:18
how this should actually work then somebody tell you that he can't just reduce what 3 and what a major take something like this
53:29
expression and you hope that there is a 3 that is running around the let's assume all 5 and we have 6 6 is beautiful be divisible y by 3 but only reduce what 5 and F is 1 which is not a multiple of 3 so in principle this should work now the reason that it still works or depending on the promissory shoes them works most of the time it's that the parameters chosen such that the numbers are small enough so this only works if there's more to q on the right hand side doesn't exceed take away the 3 so if there's actually no need to compute what to say if this thing on the right hand side is by itself a small thank you so this is where everything comes in the Rosetta beginning all you're only allowed to choose a few of the coefficients to be nonzero here only allow to shoes plus and minus ones because of this r times 3 G R as only small provisions G is only small coefficients and OK them if the 3 running around so the maximum coefficient we get at every moment is is a plus 1 of ah hits a plus 1 of G and the multiply and then the sum this up to n times but they can't be any such thinks there's only the coefficients are nonzero so the worst precision of this product will be d times a perfect match of plus 1 plus 1 and perfect measure of minus 1 minus 1 the so there really conspired to always add up to the maximum we can see something like 3 D for the 1st part and then similarly while there was no weight restrictions on em but there was a major streets on f so when a coefficient of f of which only if the it's a nonzero coefficient of M we get assignment so the max see any coefficient is going to be 4 times the now how our choice will be that you want to have that q over 2 is larger than 40 so this is our q large enough say last part of 2 then the seduction will not make any problems talking now it was like she had to do with that of I
55:56
promise at the beginning that this is a latticebased cryptosystems the mass of the talk about polynomials no yes yes scene and not as part of the talk that you can take a coppersmith thing and put polynomials in as basis vectors but 1st have to still explain how to translate the engine problem the problem of finding f into a problem of finding a short vector in a lattice so
56:22
1st of all here's how I set up of the same matrix so for set of images I'm only allowed to use public information I don't know the F I don't know the G but I do know this H and undismayed is this capital H block there that is going to be a block which is in columns n n rows and then about today is the identity matrix so that has a queue entries are all equal to 1 on the diagonal and then there's another matrix which has just ones on the diagonal and everything is 0 appear but this is the interesting part H. I've been putting in each row all the coefficients of middle age where she divide by 3 but keep such that if I take any vector take as a polynomial say this 1st vector there this 1 0 0 0 would be the constant 1 the other 1 will be the constant 3 such that it corresponds to modification by the polynomial h at so it's an example I have this long links to an actor I have the 2 n by 2 n matrix city here and I'll take the 1st part because that is just the unit vector so that will take from the top part of the matrix just the Q times identity so that just gets me q there press is 0 so that the 2nd part of this this 3 0 0 0 and I said 8 should be such that if I multiplied by anything it's like multiplication by the part number so this will grapple exactly 1 times this polynomial h so that tells you how you write this polynomial there and then you would have say the next coefficient would give you this 1 but rotated this 1 wrote attempts to so this is our you item matrix and now what is a short vector in this lattice to get any vector in the lattice that means take integer multiples of these vectors that means a taking some polynomial combinations or indeed a polymer combinations of us the reason why I'm getting g times F out of energy come I have out of this is while I don't know what it looks like but there is a polynomial case and this economy effort I know such as patents f the cake have times matrix is give me Geko my F and G and F are small that means they have very few nonzero entries and the entries of a small they only plus a minus 1 so if I'm right about this and all what steps in a moment then this vector in the lattice is very likely be the shortest vector at all so then I can use l l something track to get this perspective so if you run through this while this molecule just means there's some certain multiple of Q so that h times F is 3 D that molecule so this times k times q and that's the case I'm stuffing and there a gamma don't trust the death implemented as seen on works just
59:46
implement just implements doesn't you realize how hard this is a paratrooper lots age and the 1st thing is just a little higher conversion of h and h divided by 3 my Q addiction through little on time skip that part
1:00:02
and just say what happens when you multiply they a lot of the pollen on what's happening here is that each 3 which is h divided by 3 that's being multiplied by x and x squared execute and so on as convolution which means it's rotating the coefficients around if you look at each line of numbers 58 to 10 54 you see that on the next line rotated around uh 1 position to the left of 58 has gone to the to the end and so on and OK so here's a bunch of polynomials and what matters about these polynomials is that some combination of these if you add up some of these and subtract these you're gonna get g modulo q because remember F is a bunch of Our 1 x x squared and so on added and subtracted in some way and if you multiply that by age you get 3 G and this H 3 years while you multiply by its each over 3 that's going to give you g so g is going to be and subtract whichever of these polynomials you get for corresponding to you wrote F in the 1st place a secret F was of some differences of these exports
1:01:12
are right and I just show you the matrix that comes up at the end of this year's this 2 n by 2 n matrix where on the bottom left to the same numbers that we were are just looking at with some 58 and so on and so then down the diagonal there's some cues in ones are right and then we pull out the idea to give us are short vectors in the lattice and OK there's ll results and suddenly there is much shorter results the these are all I'll give you not just 1 short vector but among too short vectors short can assure basis in this case you see super short vectors up at the top the 1st rows of very short combination of the original vectors are if you extract the 2nd
1:02:00
half and I L old bracket 0 see the 1st row and in the bracket and colon is taking from positions in 2 2 and 3 2 n minus 1 of that 1st rail and they give you 5 nonzero coefficients to more I 0 coefficients converting those into a polynomial is exactly the secret after well with the minus sign but that doesn't affect the decryption so if you run for this effort that the attacker found just from the publickey setting up the matrix running L on this polynomial lattice then you break inches you can decode any message you want the now you have to scale this up to get real security of course 7 dimensions is not enough on if you go to say 150 dimensions and 101 nonzero terms in enough and so on and QC ln of 2 to the 32 vendors can be more than 2 to the 200 choices of the secret have he try the attack again and that the
1:02:58
attack does not find plus and minus ones that still finds a kind of short polynomial else not necessarily the the shortest but it's sort assured and it's still breaks the system which is kind of scary where you need to do the reason this still breaks the system is a q is actually too big you don't always have crypto parameters being more secure of the bigger when q is really big that allows this kind of big f decrease crypt because the whole decryption procedure needed that there wasn't some wraparound modulo q if q is smaller it actually gets more secure and NSF does not break the system anymore and then well for good security also needed to be someone better
1:03:41
so when you do this there's a whole bunch of text taking account should small and smoothed should small uh logic the shoes molecule has larger and they're all the copper protects a measure the beginning but due to the close on a positive note if you want to take
1:03:58
this and try this at home and out of it if you want to try this at home everything that we talked about uh so there are plenty of things you can do so you probably don't use lattices yourself right now and so every near submission to the pose quantum crypto competition has a reference implementation which is available online at more than 90 per cent of them have survived to survived a week of catalysis so utero can go and analyze these implementations break them improve the security whatever you like so this is what the world needs and if you're interested in integration of quantum safe computing quantum safe crypto into actual protocols there is a project called the open quantum state project i which has a bunch of implementations of schemes and and integration of the 2 things like open as itself uh you may not want to use this right now because schemes may become obsolete due to cryptanalytic advances like the ones we've seen and there's a lot of work at every level to break stuff analyze proposals look at implementations that all sorts of things needed and if you feel really feel inspired to turn on POS quantum cryptography in your own projects we would recommend using a hybrid approach with elliptic curve cryptography and not using bearer quantum pose quantum schemes right now so Google did this for example uh this past year uh with apos quantum key exchange uh and it did a hybrid approach of elliptic curves so that is all we have so thank you very much and that we hope to the more broken the few tests to be this is
1:05:38
a you the it could that the in and it it would be kind the cut back
00:00
Binärcode
Expertensystem
Zahlenbereich
Ruhmasse
Gasströmung
Code
CayleyBaum
Rechenschieber
Systemprogrammierung
DijkstraAlgorithmus
Digitalsignal
Framework <Informatik>
Rechter Winkel
Kryptologie
Korrelation
Abgeschlossene Menge
Stichprobenumfang
01:13
PublicKeyKryptosystem
Kryptosystem
Zahlenbereich
Chiffrierung
MessagePassing
Kryptologie
Datenverarbeitungssystem
Nichtunterscheidbarkeit
Quantenkryptologie
Computersicherheit
Kontrollstruktur
Exponent
CayleyBaum
Rucksackproblem
Quantenkryptologie
Kryptosystem
Schlüsselverwaltung
Kryptologie
Physikalisches System
RSAVerschlüsselung
QuickSort
CayleyBaum
Chiffrierung
Refactoring
Mereologie
02:39
Subtraktion
Punkt
HausdorffDimension
Mathematisierung
Schaltnetz
Vektorraum
Euklidische Ebene
Eins
Multiplikation
Datensatz
Ganze Zahl
Koeffizient
Reelle Zahl
Spieltheorie
Translation <Mathematik>
CayleyBaum
Datenstruktur
Gerade
Basisvektor
Vektorgraphik
Mathematik
RaumZeit
Dimensionsanalyse
Vektorraum
Physikalisches System
QuickSort
CayleyBaum
Polynom
Basisvektor
Mathematisches Objekt
Gittermodell
Koordinaten
Instantiierung
05:52
Algorithmus
Approximation
Polynom
Exponent
HausdorffDimension
Vektorraum
Vektorraum
EFunktion
QuickSort
CayleyBaum
Konfiguration <Informatik>
Deskriptive Statistik
Polynom
Datensatz
Algorithmus
Dampfdruck
Informatik
Maschinelles Sehen
Bildgebendes Verfahren
Gerade
Basisvektor
07:46
Algorithmus
Lineares Funktional
Dicke
Exponent
HausdorffDimension
Softwarewerkzeug
Mathematisierung
Vektorraum
Element <Mathematik>
Vektorraum
Dicke
EinAusgabe
CayleyBaum
Arithmetisches Mittel
Open Source
Software
Algorithmus
Funktion <Mathematik>
Kryptologie
Code
EinAusgabe
Basisvektor
Dimensionsanalyse
Vererbungshierarchie
CayleyBaum
Basisvektor
Funktion <Mathematik>
08:52
Formale Sprache
Chiffre
Zahlenbereich
Eins
Chiffrierung
Open Source
Mooresches Gesetz
MessagePassing
Multiplikation
Spannweite <Stochastik>
Kryptologie
Code
Restklasse
Chiffre
Programmbibliothek
Exponent
Wurzel <Mathematik>
Implementierung
Leistung <Physik>
Verschiebungsoperator
Lineares Funktional
Teilbarkeit
Mathematik
Exponent
Primzahl
Kryptosystem
Kryptologie
Mathematisierung
Ruhmasse
Symboltabelle
Primideal
RSAVerschlüsselung
Algorithmische Programmiersprache
Teilbarkeit
QuickSort
Software
Wurzel <Mathematik>
Ganze Zahl
MessagePassing
Instantiierung
11:05
Parametersystem
Teilbarkeit
Computersicherheit
TexturMapping
RSAVerschlüsselung
CayleyBaum
RaumZeit
Teilbarkeit
Internetworking
Rechenschieber
Refactoring
Mereologie
Garbentheorie
CayleyBaum
Aggregatzustand
12:10
Videospiel
Bit
Dicke
Teilbarkeit
Division
Partielle Differentiation
ROCKurve
Zahlenbereich
Strömungsrichtung
EFunktion
Information
RSAVerschlüsselung
Teilbarkeit
Division
QuickSort
Internetworking
Faktorisierung
Spannweite <Stochastik>
Datensatz
Algorithmus
Rechter Winkel
Refactoring
Information
13:23
Bit
Polynom
Partielle Differentiation
Ausnahmebehandlung
Primideal
Biprodukt
Information
CayleyBaum
Code
Forcing
Refactoring
Vererbungshierarchie
Information
CayleyBaum
14:44
Matrizenrechnung
Bit
Matrizenring
Sechsecknetz
FeasibilityStudie
Matrizenrechnung
Partielle Differentiation
Vektorraum
Information
RSAVerschlüsselung
Teilbarkeit
QuickSort
CayleyBaum
Wiederherstellung <Informatik>
Logarithmus
Quadratzahl
Forcing
NotebookComputer
Information
Wurzel <Mathematik>
Funktion <Mathematik>
16:19
PublicKeyKryptosystem
Web Site
Punkt
Polynom
Adressierung
Vektorraum
CaseModding
Kombinatorische Gruppentheorie
Code
Koeffizient
Kryptologie
Bildschirmfenster
Wurzel <Mathematik>
CayleyBaum
Optimierung
Basisvektor
Algorithmus
Videospiel
Teilbarkeit
Physikalischer Effekt
Vektorraum
Kryptoanalyse
QuickSort
CayleyBaum
Polynom
Wurzel <Mathematik>
Koeffizient
Basisvektor
Mathematikerin
Ablöseblase
Wort <Informatik>
Schlüsselverwaltung
Aggregatzustand
18:56
TVDVerfahren
Bit
Wellenlehre
HausdorffDimension
Gruppenkeim
tTest
Entscheidungsmodell
Zahlenbereich
Physikalische Theorie
Überlagerung <Mathematik>
Gradient
HausdorffDimension
Algorithmus
Datentyp
Stützpunkt <Mathematik>
CayleyBaum
Softwaretest
Soundverarbeitung
Beobachtungsstudie
Schnelltaste
Videospiel
Teilbarkeit
Schlüsselverwaltung
Graph
Matching <Graphentheorie>
RaumZeit
Überlagerung <Mathematik>
Primideal
Vektorraum
RSAVerschlüsselung
Teilbarkeit
Dreieck
CayleyBaum
Modem
Chipkarte
Primzahltest
Menge
Mereologie
Schlüsselverwaltung
21:49
Kryptosystem
Bit
Quantencomputer
tTest
RaumZeit
Übergang
Algorithmus
Prognoseverfahren
Multivariate Analyse
Datenverarbeitungssystem
Total <Mathematik>
Qubit
Softwaretest
Ereignisdatenanalyse
Quantenkryptologie
Computersicherheit
Quantencomputer
Isogenie
Frequenz
Elektronische Unterschrift
RSAVerschlüsselung
Quantisierung <Physik>
Datenfeld
Chiffrierung
Fehlermeldung
Instantiierung
Standardabweichung
Tabelle <Informatik>
Zahlenbereich
ROCKurve
Abgeschlossene Menge
Division
Code
Reelle Zahl
HashAlgorithmus
Schätzung
Quantisierung <Physik>
Coprozessor
SchreibLeseKopf
Schätzwert
Qubit
Algorithmus
Fehlermeldung
Fehlererkennungscode
Physikalisches System
Modul
QuickSort
CayleyBaum
Verdeckungsrechnung
Coprozessor
Rückkopplung
Faktor <Algebra>
Wort <Informatik>
Normalvektor
Bitrate
25:52
Bit
Punkt
Rundung
Primideal
Chiffre
Chiffrierung
Elektronische Unterschrift
Skript <Programm>
Kompakter Raum
Skript <Programm>
Figurierte Zahl
Einflussgröße
Metropolitan area network
Videospiel
Parametersystem
Physikalischer Effekt
Computersicherheit
Quantencomputer
MailingListe
Nummerung
Schlussregel
Vorzeichen <Mathematik>
Elektronische Unterschrift
Ranking
Chiffrierung
Wort <Informatik>
Schlüsselverwaltung
28:50
RSAVerschlüsselung
TVDVerfahren
Einfügungsdämpfung
Bit
Chiffre
Computerunterstütztes Verfahren
Computer
Code
Methodenbank
MessagePassing
Ganze Zahl
Syntaktische Analyse
Vererbungshierarchie
Passwort
Wurzel <Mathematik>
Graphiktablett
Touchscreen
Exponent
Nummerung
Dateiformat
RSAVerschlüsselung
CayleyBaum
Ordnungsreduktion
Chiffrierung
Ganze Zahl
Würfel
Rechter Winkel
Dateiformat
Faktor <Algebra>
MessagePassing
31:22
Algorithmus
Matrizenrechnung
Polynom
Exponent
Matrizenrechnung
Chiffre
Vektorraum
Vektorraum
CayleyBaum
MessagePassing
Polynom
Wurzel <Mathematik>
Würfel
Koeffizient
Mereologie
Basisvektor
Wurzel <Mathematik>
CayleyBaum
MessagePassing
33:47
Konstruktor <Informatik>
Bit
Kryptosystem
Exponent
Seidel
Kryptologie
Nummerung
Sprachsynthese
Computerunterstütztes Verfahren
Physikalisches System
Nummerung
RSAVerschlüsselung
Elektronische Unterschrift
QuickSort
Multiplikation
Informationsmodellierung
Chiffrierung
Elektronische Unterschrift
Rechter Winkel
Chiffre
Eigentliche Abbildung
Kurvenanpassung
Schlüsselverwaltung
Brennen <Datenverarbeitung>
Graphiktablett
35:41
Einfügungsdämpfung
Bit
Multiplikation
Polynom
Konvexer Körper
Element <Mathematik>
Nummerung
Code
Physikalisches System
Chiffrierung
Elektronische Unterschrift
Mustersprache
Faltungsoperator
Chiffre
Inverser Limes
Gruppoid
Indexberechnung
Operations Research
Implementierung
Parametersystem
Seidel
Ruhmasse
Schlussregel
Physikalisches System
RSAVerschlüsselung
Polynom
Minimalgrad
Ganze Zahl
Koeffizient
Parametersystem
Faltungsoperator
Instantiierung
38:13
Nichtlinearer Operator
Lineares Funktional
Multiplikation
Polynom
Mathematisierung
Mathematisierung
Ausnahmebehandlung
Computer
Ordnungsreduktion
Rechenschieber
Physikalisches System
Informationsmodellierung
Zahlensystem
Restklasse
Koeffizient
Parametersystem
Rechenschieber
Faltungsoperator
Polynomalgebra
Gruppoid
Operations Research
39:07
PublicKeyKryptosystem
Bit
Subtraktion
Punkt
Polynom
Stab
Mathematisierung
Klasse <Mathematik>
Zahlenbereich
CaseModding
Element <Mathematik>
Zahlensystem
Term
Deskriptive Statistik
Zahlensystem
Multiplikation
Informationsmodellierung
Ganze Zahl
Koeffizient
Faltungsoperator
Bildgebendes Verfahren
Differenzenrechnung
Leistung <Physik>
Parametersystem
Nichtlinearer Operator
Exponent
Distributivgesetz
Mathematisierung
Physikalisches System
EinAusgabe
Teilbarkeit
Ordnungsreduktion
Rechenschieber
Objekt <Kategorie>
Polynom
Minimalgrad
Existenzsatz
Konditionszahl
Koeffizient
Parametersystem
Faltungsoperator
Restklasse
Projektive Ebene
Information
Quotient
Instantiierung
44:17
Resultante
Bit
Punkt
Extrempunkt
Formale Sprache
Selbstrepräsentation
Chiffre
Computer
Computerunterstütztes Verfahren
Homepage
Deskriptive Statistik
Negative Zahl
Zustandsgröße
Exakter Test
Kryptologie
Vorzeichen <Mathematik>
Chiffre
NotepadComputer
Umkehrung <Mathematik>
Gerade
Funktion <Mathematik>
Umwandlungsenthalpie
Parametersystem
Lineares Funktional
Computersicherheit
Ausnahmebehandlung
EinAusgabe
Gleichheitszeichen
Kommutator <Quantentheorie>
Teilbarkeit
Dichte <Physik>
Rechenschieber
Motion Capturing
Polstelle
Divergente Reihe
Polynom
Chiffrierung
Koeffizient
Versionsverwaltung
Schlüsselverwaltung
Software Engineering
MessagePassing
Fitnessfunktion
PublicKeyKryptosystem
Mathematisierung
Zahlenbereich
Sprachsynthese
CaseModding
Term
Abenteuerspiel
Faltungsprodukt
Division
Ausdruck <Logik>
Chiffrierung
MessagePassing
Spannweite <Stochastik>
Multiplikation
Zufallszahlen
Koeffizient
Restklasse
Arbeitsplatzcomputer
Faltungsoperator
Drei
Graphiktablett
Leistung <Physik>
Relativitätstheorie
Primideal
Ordnungsreduktion
Minimalgrad
Mereologie
Normalvektor
52:22
PublicKeyKryptosystem
Chiffrierung
Faltungsoperator
Faltungsoperator
Chiffre
tTest
Physikalisches System
CaseModding
EinAusgabe
MessagePassing
Ordnungsreduktion
Eins
53:26
Gewichtete Summe
Gewicht <Mathematik>
Momentenproblem
Extrempunkt
Zahlenbereich
Basis <Mathematik>
Extrempunkt
Eins
Demoszene <Programmierung>
Chiffrierung
Multiplikation
Arithmetischer Ausdruck
Ganze Zahl
Koeffizient
Ordnungsreduktion
CayleyBaum
Auswahlaxiom
Parametersystem
Teilbarkeit
Kryptosystem
Ruhmasse
Vektorraum
Biprodukt
CayleyBaum
Polynom
Rechter Winkel
Koeffizient
Mereologie
Restklasse
56:20
Matrizenrechnung
Umsetzung <Informatik>
Multiplikation
Momentenproblem
Schaltnetz
Matrizenrechnung
Vektorraum
Zahlenbereich
Eins
Datensatz
Multiplikation
Weg <Topologie>
Ganze Zahl
Einheit <Mathematik>
Perspektive
Nichtunterscheidbarkeit
Warteschlange
CayleyBaum
Bildgebendes Verfahren
Basisvektor
Vektorraum
pBlock
Binder <Informatik>
CayleyBaum
Energiedichte
Menge
Rechter Winkel
Koeffizient
Mereologie
Translation <Mathematik>
Information
Gammafunktion
Diagonale <Geometrie>
1:00:02
Resultante
Matrizenrechnung
Subtraktion
Ortsoperator
Schaltnetz
Zahlenbereich
Vektorraum
CayleyBaum
Eins
Polynom
Datensatz
Ganze Zahl
Restklasse
Basisvektor
Minimum
Faltungsoperator
Faltungsoperator
Diagonale <Geometrie>
Gerade
1:01:57
Parametersystem
Matrizenrechnung
Ortsoperator
HausdorffDimension
Computersicherheit
Physikalisches System
QuickSort
Algorithmische Programmiersprache
CayleyBaum
Eins
MessagePassing
Auswahlaxiom
PoissonKlammer
Polynom
Chiffrierung
Maßstab
Kryptologie
Reelle Zahl
Vorzeichen <Mathematik>
Restklasse
Koeffizient
Computersicherheit
MessagePassing
Auswahlaxiom
1:03:38
Offene Menge
Kontrollstruktur
Implementierung
Abgeschlossene Menge
Computer
Computerunterstütztes Verfahren
Nummerung
Mathematische Logik
Eins
Übergang
Chiffrierung
Systemprogrammierung
Kryptologie
Quantenkryptologie
Chiffre
Schlüsselverteilung
Zustand
Quantisierung <Physik>
Kontrollstruktur
Ordnungsreduktion
CayleyBaum
Hybridrechner
Einflussgröße
Elliptische Kurve
Implementierung
Basisvektor
Inklusion <Mathematik>
Softwaretest
Quantenkryptologie
Protokoll <Datenverarbeitungssystem>
Kryptoanalyse
Computersicherheit
Kryptologie
Nummerung
Hybridrechner
QuickSort
CayleyBaum
Quantisierung <Physik>
Integral
Datenstruktur
Rechter Winkel
Offene Menge
Verbandstheorie
Projektive Ebene
Vorwärtsfehlerkorrektur
Versionsverwaltung
1:05:37
Hypermedia
Medianwert
Systemprogrammierung
Schnitt <Graphentheorie>
Metadaten
Formale Metadaten
Titel  LatticeHacks 
Untertitel  Fun with lattices in cryptography and cryptanalysis 
Serientitel  34th Chaos Communication Congress 
Autor 
djb

Lizenz 
CCNamensnennung 4.0 International: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. 
DOI  10.5446/34858 
Herausgeber  Chaos Computer Club e.V. 
Erscheinungsjahr  2017 
Sprache  Englisch 
Inhaltliche Metadaten
Fachgebiet  Informatik 
Abstract  Lattices are an extremely useful mathematical tool for cryptography. This talk will explain the basics of lattices in cryptography and cryptanalysis. 
Schlagwörter  Security 