NIST has defined that Kyber will be developed as a standard for PQC (Post Quantum Cryptography) key exchange and public key encryption. The main methods are Kyber512 (128-bit AES security level equivalent), Kyber768 (192-bit AES security level equivalent) and Kyber1024 (256-bit AES security level equivalent. In Kyber we modify the normal LWE (Learning With Errors) approach and use MLWE (Module Learning With Errors). With MLWE we use vectors of polynomials [2]. In this case, we will implement a very simple Kyber example and generate a public key and a private key, and then encrypt a message [1].
Simple Kyber exampleBasicsMatricesSome basic rules of matrices are: \({(\textbf{A}^T)}^T=\textbf{A}\) \(\textbf{(AB)}^T=\textbf{A}^T \textbf{B}^T\) \({(c\textbf{A})}^T=c\textbf{A}^T\) and where \(T\) is a transpose of the matrix. PolynomialsIn polynomial representation, we can take a data value of 1101 and represent it in polynomial powers: \(x^3+1.x^2+0x+1 = x^3+x^2+1\) We can then multiply, divide, add and subtract polynomial values. If you remember from school, for \((2x^2+1)\) times \((x+1)\) we get: \((2x^2+1).(x+1) = 2x^3+2x^2+x+1\) The (mod p) operationObviously, if we are multiplying polynomials, the coefficients of the powers could become large, so we perform a \(\pmod q\) operation on them. Let’s take a \(q\) value of 17 and let’s say we have: \(a=2x^4+3x^3+10x+3\) \(b=3x^5+14x^3+10x+4\) Then, to add \(\pmod {17}\), we get: \((2x^4+3x^3+10x+3)+(3x^5+14x^3+10x+4) = 3x^5+2x^4+17x^3+20x+7 = 3x^5+2x^4+3x+7 \pmod{17})\) To subtract \(\pmod{17}\), we get: \((2x^4+3x^3+10x+3)-(3x^5+14x^3+10x+4) = -3x^5+2x^4-11x^3-1 = 14x^5+2x^4+6x^3+16 \pmod {17}\) To multiply \(\pmod{17}\), we get: \((2x^4+3x^3+10x+3)*(3x^5+14x^3+10x+4) =\) [… working left to reader … ] \(= 6x^7+9x^6+7x^5+3x^4+8x^3+x^2+2x+12 \pmod{17}\) For division, we will get a quotient and a remainder. With integers 19 divided by 5 gives a quotient of 3 and a remainder of 4. In cryptography, we are typically only interested in the remainder value. So we get: \((2x^4+3x^3+10x+3)/(3x^5+14x^3+10x+4)\) Remainder: […working left to reader … ] \(= 2x^3+3x^2+10x+3 \pmod{17}\) We can use Python to check this: import numpy as np import sys import numpy q=17 a= [2,3,10,3] // 2x^4+3x^3+10x+3 b= [3,0,14,10,4] // 3x^5+14x^3+10x+4 print (np.poly1d(a)) print (np.poly1d(b)) r1 = np.floor( np.polyadd(a,b)) % q // Polynomial add r2 = np.floor( np.polymul(a,b)) % q // Polynomial multiply r3 = np.floor( np.polysub(a,b)) % q // // Polynomial subtract r4 = np.floor( np.polydiv(a,b)[1]) % q // // Polynomial divide with remainder print (np.poly1d(r1)) print (np.poly1d(r2)) print (np.poly1d(r3)) print (np.poly1d(r4)) And then the results are: 3 2 2 x + 3 x + 10 x + 3 4 2 3 x + 14 x + 10 x + 4 4 3 3 x + 2 x + 3 x + 7 7 6 5 4 3 2 6 x + 9 x + 7 x + 3 x + 8 x + 1 x + 2 x + 12 4 3 2 14 x + 2 x + 6 x + 16 3 2 2 x + 3 x + 10 x + 3 The code is: Overall, \(q\) is the modulus for the numbers. For Kyber512, this value is 3,329. The irreducible polynomialThe next key concept relates to the maximum power of the coefficients of the powers. If we do not constrain, the values of powers will become large. And, so, for each operation, we can divide by an irreducible polynomial (a polynomial that cannot be factored), and take the remainder of the operation. This is similar to our \(\pmod p\) operation in public key encryption (and where we divide by p each time, and take the remainder of the operation). If you want some examples: [here]. An irreducible polynomial of \(x^4+1\), will reduce our maximum coefficient power of \(x^3\). This variable (n) is defined as the maximum degree of the used polynomials. For Kyber512, this value is 256. In Python, we basically perform a polynomial divide. As this will create two results (the division and the remainder), we take the second returned value (using [1] to identify the second argument returned): A1 = np.floor( np.polydiv(A1,xN_1)[1]) % q Key GenerationIn Kyber we modify the normal LWE (Learning With Errors) approach and use MLWE (Module Learning With Errrors). With MLWE we use vectors of polynomials. The private key (\(s\))First, we start with the private key, and which is an array of polynomial values. In our case we will use: \(s=(x^3−x^2+x,x^3+x)\) Next, we create a matrix of polynomials for the public key (\(A\)) with: \(A=\begin{pmatrix} 6x^3+16x^2+6x+1 & 5x^2+10 \\ 3x^3+8x^2+5x+4 & 9x^3+8x^2+2x+4 \end{pmatrix}\) Finally, we will introduce an error polynomial: \(e=(x^2+1,x-1)\) Now, we compute: \(t=A.s+e\) The public key is then \((A,t)\). Using \(q=17\) and an irreducible polynomial of \(x^4+1\), we get: \(t= ( 9x^3+13x +5, 2x^3+ 8x^2 ++ 13x+5)\) I have used this program to work this out: # Based on https://github.com/jack4818/kyber-py from polynomials import * from modules import * R = PolynomialRing(17, 4) M = Module(R) s0 = R([0,1,-1,1]) s1 = R([0,1,0,1]) s = M([s0,s1]).transpose() A00 = R([11,16,16,6]) A01 = R([3,6,4,9]) A10 = R([1,10,3,5]) A11 = R([15,9,1,6]) A = M([[A00, A01],[A10, A11]]) A00 = R([1,6,16,6]) A01 = R([10,0,5,0]) A10 = R([4,5,8,3]) A11 = R([4,2,8,9]) A = M([[A00, A01],[A10, A11]]) e0 = R([1,0,1,0]) e1 = R([-1,1,0,0]) e = M([e0,e1]).transpose() t = A @ s + e print("A->",A) print("t->",t) and the test run is: A-> [1 + 6*x + 16*x^2 + 6*x^3, 10 + 5*x^2] [ 4 + 5*x + 8*x^2 + 3*x^3, 4 + 2*x + 8*x^2 + 9*x^3] t-> [5 + 13*x + 9*x^3] [5 + 13*x + 8*x^2 + 2*x^3] The code is here: Our private and public keySo, we now have a secret key: \(s=(x^3−x^2+x,x^3+x)\) and a public key of: \(A=\begin{pmatrix} 6x^3+16x^2+6x+1 & 5x^2+10 \\ 3x^3+8x^2+5x+4 & 9x^3+8x^2+2x+4 \end{pmatrix}\) and: \(t= (9x^3+13x +5, 2x^3 + 8x^2 +13x+5)\) Overall, it is extremely difficult to derive \(s\) from \(A\) and \(t\). EncryptionWe will encrypt with the public key \((A,t)\). Adding errorsThe first thing we need to do, is to create three randomized small polynomial vectors (\(e_1\), \(e_2\) and \(r\)) — this must not be repeated in any future communication. In our simple example, we will use: \(r=(x^3-1,x^3-x^2+x)\) \(e_1=(x^3+x^2,x^2+x)\) \(e_2=−x^2−x^2-x\) Converting the messaging into a polynomialIn order to process our message, we need to convert it into a polynomial. This is achieved by coverting each into a coefficient. Thus "1101" becomes: \(x^3+x+1\) Our message must then be scaled so that we have relatively large coefficients. As we have \(q\)=17, we have a half-way point of \(q/2\), and then upscale to get a factor of 9. Our message is then: \(9x^3+9x+9\) EncryptingWe can now take the public key \((A,t)\) and encrypt: \(u=A^T.r+e_1\) \(v=t^T.r+e_2+m\) and where the \(T\) symbol identifies that the matrix is transposed. The ciphertext is then \(u\) and \(v\). In our example, the result is: \(u=(12x^3+ 6x^2+ 3x+12,11x^3+ 8x^2+ 12x+16 )\) \(v= (2x^3 + 5x^2 +2)\) A snippet of the code used is: # Based on https://github.com/jack4818/kyber-py A,t,s=genkey() print("A->",A) print("t->",t) r0 = R([0,1,-1,1]) r1 = R([-1,0,0,1]) r = M([r0, r1]).transpose() e_10 = R([0,1,1,0]) e_11 = R([0,0,1,1]) e_1 = M([e_10, e_11]).transpose() e_2 = R([0,-1,-1,-1]) m = [1,1,0,1] poly_m = R.decode(m).decompress(1) print("Message: ",poly_m) u = A.transpose() @ r + e_1 v = (t.transpose() @ r)[0][0] + e_2 - poly_m print("u->",u) print("v->",v) DecryptionWe now have the ciphertext of \((u,v)\) and will use the private key (\(s\)) to decrypt it. This is achieved with: \(m_{noisy}=v−s^T.u\) This provides us with an answer which still have noise. If we expand our decryption process, we get: \(m_{noisy}=(t^T.r+e_2+m)-s^T.(A^T.r+e_1)\) This equals: \(m_{noisy}=(A.s+e)^T.r+e_2+m+(s^T.A^T.r)-s^T.e_1\) and: \(m_{noisy}=(A.s)^T.r+ e^T.r+e_2+m-(A.s)^T.r-s^T.e_1\) which gives: \(m_{noisy}= e^T.r+e_2+m-s^T.e_1\) But, we know that \(m\) is much larger than the error components (\(e\) and \(e_2\)), so we can determine if the values are closer to \(q\) or 0. If they are closer to \(q\), we define that the message bit is a 1, else it is a zero. The code snippet for this is then: m_n = v - (s.transpose() @ u)[0][0] m_n_reduced = m_n.compress(1) print("\nBefore reduced: ",m_n) print("Decrypted: ",m_n_reduced) CodingFinally, here is the full coding: # Based on https://github.com/jack4818/kyber-py from polynomials import * from modules import * R = PolynomialRing(17, 4) M = Module(R) def genkey(): s0 = R([0,1,-1,1]) s1 = R([0,1,0,1]) s = M([s0,s1]).transpose() A00 = R([11,16,16,6]) A01 = R([3,6,4,9]) A10 = R([1,10,3,5]) A11 = R([15,9,1,6]) A = M([[A00, A01],[A10, A11]]) A00 = R([1,6,16,6]) A01 = R([10,0,5,0]) A10 = R([4,5,8,3]) A11 = R([4,2,8,9]) A = M([[A00, A01],[A10, A11]]) e0 = R([1,0,1,0]) e1 = R([-1,1,0,0]) e = M([e0,e1]).transpose() t = A @ s + e return A,t,s A,t,s=genkey() print("A->",A) print("t->",t) r0 = R([0,1,-1,1]) r1 = R([-1,0,0,1]) r = M([r0, r1]).transpose() e_10 = R([0,1,1,0]) e_11 = R([0,0,1,1]) e_1 = M([e_10, e_11]).transpose() e_2 = R([0,-1,-1,-1]) m = [1,1,0,1] poly_m = R.decode(m).decompress(1) print("Message: ",poly_m) u = A.transpose() @ r + e_1 v = (t.transpose() @ r)[0][0] + e_2 - poly_m print("u->",u) print("v->",v) m_n = v - (s.transpose() @ u)[0][0] m_n_reduced = m_n.compress(1) print("\nBefore reduced: ",m_n) print("Decrypted: ",m_n_reduced) and a sample run: A-> [1 + 6*x + 16*x^2 + 6*x^3, 10 + 5*x^2] [ 4 + 5*x + 8*x^2 + 3*x^3, 4 + 2*x + 8*x^2 + 9*x^3] t-> [ 5 + 13*x + 9*x^3] [5 + 13*x + 8*x^2 + 2*x^3] Message: 9 + 9*x + 9*x^3 u-> [12 + 13*x + 6*x^2 + 12*x^3] [16 + 12*x + 8*x^2 + 11*x^3] v-> 2 + 5*x^2 + 2*x^3 Message: 1 + x + x^3 Decrypted: 1 + x + x^3 The code is here: References[1] Giacomo Pope, CRYSTALS-Kyber Python Implementation [here]. [2] Ruben Gonzalez, Kyber - How does it work?, Approachable Cryptography [here]. |