{"id":533,"date":"2024-09-27T13:09:01","date_gmt":"2024-09-27T19:09:01","guid":{"rendered":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/?p=533"},"modified":"2024-09-27T13:09:05","modified_gmt":"2024-09-27T19:09:05","slug":"post-quantum-cryptography-kyber-for-dummies","status":"publish","type":"post","link":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/2024\/09\/27\/post-quantum-cryptography-kyber-for-dummies\/","title":{"rendered":"Post Quantum Cryptography: Kyber for Dummies"},"content":{"rendered":"\n

On August 13th<\/sup> 2024 NIST published the standards FIPS 203 (Kyber), FIPS 204 (Dilithium) and FIPS 205 (SPHINCS+) which are all quantum resistant algorithms that will soon replace those currently in use. The Kyber standard is a key encapsulation scheme which uses public key enabling and will replace the Diffie Hellman exchange. Dilithium and SPHINCS+ are signature schemes that will replace RSA. Both Kyber and Dilithium use polynomial modular arithmetic that relies on the hardness of a set of problems that can be rephrased as lattice problems which have been proven to be the worst-case quantum hardness – meaning quantum computers can\u2019t solve these problems effectively.<\/p>\n\n\n\n

In September 2022 the NSA released a road map on the swap from The Commercial National Security Algorithm Suite(CNSA) 1.0 to CNSA 2.0 which swaps algorithms that are not quantum resistant with the new quantum resistant algorithms.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

In this blog I will give a super simplified explanation of Kyber and how it works, based on the Alfred Menezes Cryptography 101 lecture on the subject. I highly recommend watching his lecture if you want to get a better or more in depth understanding. I\u2019ll only be covering Kyber but the Cryptography 101 lecture also covers Dilithium which uses most of the same base mathematical concepts that Kyber uses.<\/p>\n\n\n\n

Mathematical Tools used in Kyber<\/h2>\n\n\n\n

Kyber mainly relies on the mathematical concept of Rq<\/sub>: taking a polynomial of Zq<\/sub>[x] and dividing it by xn<\/sup>+1. Now what does this mean? First q is a prime modulus, and Zq<\/sub>[x] is just a regular polynomial like 3+2x+7x3<\/sup> but all the coefficients are modulus q. For example, if we instead had a modulus of q=3, our polynomial would change to 2x+x3<\/sup> as 7 modulus 3 is 1 and 3 modulus 3 is 0. The second part of Rq<\/sub> is dividing by xn<\/sup>+1. This keeps the degree of the polynomial less than n so at most the highest degree of the polynomial is n-1. Kyber uses multiple of these Rq<\/sub> polynomials in matrixes with some linear algebra to perform the algorithm.<\/p>\n\n\n\n

Kyber also uses size, which is equal to the absolute value of the highest coefficient in the polynomial. In our example the size of 3+2x+7x3<\/sup> is 7. Kyber then takes this one step further and uses what\u2019s called a ‘symmetric mod’ instead of a regular modulus. The difference is in the size of the set of integers modulus q: if a number r is greater than (q-1)\/2 we take r-q. In practice this means the higher numbers of the modulus are swapped out for negative numbers. See in how mod 17 in figure 2 changes the numbers larger than q\/2 to r-q seen in figure 3.<\/p>\n\n\n\n

\n
\"\"
Figure 2: https:\/\/cryptography101.ca\/wp-content\/uploads\/2024\/08\/v1-slides-kyber-and-dilithium.pdf slide 23<\/a><\/figcaption><\/figure>\n\n\n\n
\"\"
Figure 3: https:\/\/cryptography101.ca\/wp-content\/uploads\/2024\/08\/v1-slides-kyber-and-dilithium.pdf slide 31<\/figcaption><\/figure>\n<\/figure>\n\n\n\n
\n

If we again take our example polynomial 3+2x+7x3<\/sup> but with the symmetric mod 3 (also know as ‘mod-s’ 3) we get -1x+1x3<\/sup>. The modulus of the first equation, 2 mod 3, equals 2 which is larger that q-1\/2=1. So we swap it for r-q= 2-3 equaling -1. And remember, the size is the absolute value of the coefficient so if -2 is the largest polynomial coefficient the size is 2.<\/p>\n<\/div>\n\n\n\n

The last base concept Kyber uses is called rounding. This is where we take the result of mod-s q and divide it into two sections. (See figure 4)<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

In English, if the result of the mod-s q is on the bottom half of the modulus ring, we round it to a 1 and if its on the top of the modulus ring we round to 0. Well use this to help represent the message we\u2019re sending.<\/p>\n\n\n\n

\"\"
Figure 4: https:\/\/cryptography101.ca\/wp-content\/uploads\/2024\/08\/v2-slides-kyber-and-dilithium.pdf<\/a> slide 6<\/figcaption><\/figure>\n\n\n\n

The hard problem that Kyber relies on is called the Decisional Module learning With Errors problem (D-MLWE) which is related to the hardness of the MLWE problem. The MLWE problem goes like this: suppose t = As+e, where each is a matrix of different dimension of Rq<\/sub> polynomials. A is a k by l matrix, t,e and a are all 1 by k. Given t and A, find s. Another important factor is that s and e\u2019s polynomials are a \u2018small\u2019 size meaning there bounded by q\/2. Having a small size is important as two polynomials with small sizes added together is also relatively small. The addition of e is what makes the problem hard – without it the solution would be relatively simple linear algebra, adding e makes it difficult.<\/p>\n\n\n\n

\"\"
Figure 5: https:\/\/cryptography101.ca\/wp-content\/uploads\/2024\/08\/v2-slides-kyber-and-dilithium.pdf<\/a> slide 9<\/figcaption><\/figure>\n\n\n\n

Kyber Protocal<\/h2>\n\n\n\n

Now for how the protocol actually works: Alice will create an instance of the MLWE problem by choosing t,A,s and e. t and A are Alice’s public key, and s is her private key.<\/p>\n\n\n\n

For Bob to encrypt a message m he must first take m in binary [0,1]n<\/sup> and then convert it to a polynomial of n-1th degree where each binary digit is a coefficient i.e 101 becomes 1 + x2<\/sup>. Bob then selects r,e1<\/sub> and e2<\/sub> where r is a matrix of Rq<\/sub> with dimensions of 1 by k and the polynomials have size of some small number c1<\/sub> or less, e1<\/sub> is the same but with another small size of c2<\/sub>, and e2<\/sub> is just a singular polynomial of Rq<\/sub> with the same size of c2<\/sub>.<\/p>\n\n\n\n

Using these he computes<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

The last thing to note is that all of the Rq<\/sub> polyomials are being randomly generated both for r,e1<\/sub> and e2<\/sub> and this is the same for Alice’s A,s, and e. If this seems confusing, following the decryption gives some clarity.<\/p>\n\n\n\n

How decryption works: Alice takes u,v and computes Roundq<\/sub>(v-sT<\/sup>u) which will result in the message m. We need to follow the algebra to get a sense why this works.<\/p>\n\n\n\n

Alice has v-sT<\/sup>u we can then substitute in the formulas for v and u, giving us<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Note 1: Substitute in the formula for t,<\/p>\n\n\n\n

Note 2: Expand out the equation<\/p>\n\n\n\n

Note 3: Cancel out common term sT<\/sup>AT<\/sup>r<\/p>\n\n\n\n

Why does this Roundq<\/sub>(eT<\/sup>r+e2<\/sub> \u2013 sT<\/sup>e1<\/sub> + round(q\/2)m) give us back m? Because if the error polynomial eT<\/sup>r+e2<\/sub> \u2013 sT<\/sup>e1<\/sub> coefficients all round to 0 it\u2019s the same as 0 + round(q\/2)m. The error polynomial doing this is not guaranteed, but in practice rounding to 1 happens with such low probability it\u2019s not a concern.<\/p>\n\n\n\n

This algorithm allows users to share keys among themselves which would let them then swap to using a symmetric key algorithm like AES. This is a simplified version of Kyber and only goes over the base idea of how it works. Lots of math is simplified and just explained in English – please refer to Alfred Menezes Cryptography 101 lecture to get a more in-depth and mathematical explanation.<\/p>\n\n\n\n

With quantum computers getting more and more powerful they are rapidly getting closer to being able to run algorithms that will break RSA and DiffeHellman. As we have learned the ins and outs of these classic algorithms, I believe it is important for us as future cyber security professionals to also be up to date on these new quantum resistant algorithms that will become the standard in the next 5-7 years.<\/p>\n\n\n\n

References:<\/p>\n\n\n\n

Kyber and Dilithium Cryptography 101 Playlist:<\/p>\n\n\n\n

https:\/\/www.youtube.com\/playlist?list=PLA1qgQLL41SSUOHlq8ADraKKzv47v2yrF<\/a>
Cryptography 101:
https:\/\/cryptography101.ca\/kyber-dilithium\/<\/a>
NIST FIPS 203 (Kyber):
https:\/\/csrc.nist.gov\/pubs\/fips\/203\/ipd<\/a>
NIST FIPS 204 (Dilithium):
https:\/\/csrc.nist.gov\/pubs\/fips\/204\/ipd<\/a>
NIST FIPS 205 (SPHINCS+):
https:\/\/csrc.nist.gov\/pubs\/fips\/205\/ipd<\/a><\/p>\n\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

On August 13th 2024 NIST published the standards FIPS 203 (Kyber), FIPS 204 (Dilithium) and FIPS 205 (SPHINCS+) which are all quantum resistant algorithms that will soon replace those currently in use. The Kyber standard is a key encapsulation scheme which uses public key enabling and will replace the Diffie Hellman exchange. Dilithium and SPHINCS+ … <\/p>\n

Continue reading “Post Quantum Cryptography: Kyber for Dummies”<\/span><\/a><\/p>\n","protected":false},"author":680,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[1],"tags":[21,22,19,23],"class_list":["post-533","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-cryptography","tag-cryptography101","tag-kyber","tag-post-quantum","entry"],"featured_image_src":null,"featured_image_src_square":null,"author_info":{"display_name":"Hayden McNally","author_link":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/author\/hayden-mcnally\/"},"_links":{"self":[{"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/posts\/533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/users\/680"}],"replies":[{"embeddable":true,"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/comments?post=533"}],"version-history":[{"count":29,"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/posts\/533\/revisions"}],"predecessor-version":[{"id":599,"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/posts\/533\/revisions\/599"}],"wp:attachment":[{"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/media?parent=533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/categories?post=533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wpsites.ucalgary.ca\/jacobson-cpsc\/wp-json\/wp\/v2\/tags?post=533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}