Public key:<\/strong> $(n, e)$<\/p>\n Private key:<\/strong> $d$<\/p>\n Encryption:<\/strong> $c = m^e \\text{ mod } n$<\/p>\n Decryption:<\/strong> $m = c^d \\text{ mod } n$<\/p>\n Security relies on the difficulty of factoring $n$. If one factors $n$, then one can compute the totient $\\varphi(n)$, and then compute the modular inverse $d =e^{-1} \\text{ mod } \\varphi(n)$.<\/p>\n RSA was first standardized by NIST in 1993 as part of the Digital Signature Standard (DSS) family, specifically in FIPS 186-1, which included RSA as an approved algorithm for digital signatures.<\/p>\n There is a quantum algorithm which can be used to break RSA known as Shor’s algorithm. This algorithm makes use of the fact that $a^x \\text{ mod } n$ is a periodic function on $(Z\/nZ)^{\\times}$. If one is able to find the period $ r$ so that $a^r \\equiv 1 \\text{ mod } n$, then note $(a^{r\/2} – 1)(a^{r\/2} + 1) \\equiv 0 \\text{ mod } n $, so $gcd(a^{r\/2} – 1, a^{r\/2} + 1)$ is likely to be a factor.<\/p>\n In order to extract the period, the function is essentially spread in an unobservered superposition across the entire (exponential) set of integers $x$ from $0$ to $2^n-1$, and the exponentials computed via controlled modular exponentiation. Then the iQFT (inverse quantum Fourier transform) is applied to this overall state. The QFT is fast, in that it runs in $O(n\\log(n))$ time despite operating on $2^n$ states, since it can operate on tensor products of $n$ qubits. This allows efficient and polynomial time extraction of the period $r$ after a quick classical computation via continued fractions to get the actual factors.<\/p>\n This algorithm was discovered by Peter W. Shor: “Algorithms for quantum computation: discrete logarithms and factoring”, Presented at the 35th Annual Symposium on Foundations of Computer Science (FOCS) in 1994.<\/p>\n For elliptic curves, we take a plane curve $E: y^2 = x^3 + Ax + B$ over a finite field $F_p$, whose points form an abelian group. Choose a base point $P$. Alice picks a secret number a, and lets $P_0 = aP$ (add $P$ to itself $a$ times ), her public key. Bob picks a secret number $b$ and computes $P_1 = bP$, his public key. For the key exchange, Alice computes $aP_1 = abP$ and Bob computes $bP_0 = abP$, so they get the same point on the curve, which can be used to derive a shared key. Note that given $(aP, P)$ it is very difficult to determine $a$. This is known as the elliptic curve discrete logarithm problem (ECDLP), and is analogous to RSA where here we are using the addition in the elliptic curve group $E(F_p)$.<\/p>\n The key sizes for elliptic curves are much smaller than RSA (256 bit ECC ~ 3072 bit RSA).<\/p>\n A variant of Shor’s algorithm which still performs Fourier sampling just over the abelian group of the elliptic curve $E(F_p)$ rather than the multiplicative group of integers mod $n$. Thus, this is an effective attack on the ECDLP.<\/p>\n There is a lot of current discussion re: when quantum computers will become reliable, fault-tolerant, error corrected, and large enough to perform useful computation. Currently there are 127 qubit systems available publicly via IBM. Google also has similar sized machines. The best error correction codes appear to be surface codes, with a $d \\times d$ array with $d=7$ qubits, and then hundreds or thousands of physical qubits per logical qubit. This allows the correction of up to 3 errors.<\/p>\n In general, it may take awhile before there are thousands of qubits required to break something like RSA-1024, which would mean factoring a 1024-bit integer. Estimates range, but something like 5-10 years seems plausible, especially given the exponential nature of progress with respect to number of qubits. To that end, NIST has stated that cryptographic schemes like RSA and ECC with 128 bit security levels will be deprecated by Dec. 31st 2030, and no longer allowed by Dec. 31st 2035. This means that the transition to post-quantum cryptography has already begun, and will probably accelerate over the next five years with many systems being replaced.<\/p>\n \n NIST, Transition to Post-Quantum Cryptography Standards: There is a major issue in the meantime that encrypted data that is collected (“harvested”) now will be able to be decrypted later by sufficiently large quantum computers later (“harvest now, decrypt later”). Therefore it is crucial that these systems and databases are replaced as soon as possible.<\/p>\n To this end, NIST ran a competition to determine the best among a selection of competing post-quantum cryptography standards. <\/p>\n https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/post-quantum-cryptography-standardization<\/a><\/p>\n In the end, the three winners were: CRYSTALS-Dilithium, CRYSTALS-KYBER and SPHINCS+<\/em>, from which FIPS 203, FIPS 204, and FIPS 205 are respectively derived.<\/p>\n We’ll primarily focus on lattice-based cryptography methods in this post. These are cryptosystems based on algebraic lattices which are very similar to rings of integers in algebraic number fields (like the cyclotomic integers $\\mathbb{Z}[x]\/(x^n-1)$, but using $x^n+1$ instead, and working over $\\mathbb{Z}_q$ rather than $\\mathbb{Z}$).<\/p>\n Each system is based on a computationally hard problem that currently does not have a polynomial time quantum algorithm to solve it. We’ll go into more detail later, but examples of these problems are:<\/p>\n In this post, we’ll primarily focus on ring-LWE, module-LWE, and FIPS 203.<\/p>\n FIPS 203 is the module-lattice key encapsulation mechanism (ML-KEM) derived from CRYSTALS-Kyber. It does use module-LWE under the hood in the internal PKE (public key encryption) portion, which we’ll cover in detail later.<\/p>\n We’ll begin with ring-LWE, a post-quantum fully homomorphic encryption scheme.<\/p>\n For modern cryptography, we aim to find problems that are impractical or ideally impossible to solve, even on a quantum computer.<\/p>\n \n \n \n We’d like to ensure that instances of LWE are hard in the average case. This is done by proving reductions from well-known hard problems in computer science:<\/p>\n These lattice problems are:<\/p>\n \n $R_q = \\mathbb{Z}_q[x]\/(f(x))$<\/p>\n \n $f(x) = x^n+1$ \nwhere $n$ is a power of two. This is the “anti-cyclotomic” ring of integers.<\/p>\n The hard problem becomes:\n<\/p>\n Consider the ring $R = \\mathbb{Z}[x]\/(x^n + 1)$:<\/p>\n Ideal lattices inherit the ring’s structure, such as multiplication by polynomials.<\/p>\n \n The reduction shows that solving ring-LWE allows decoding perturbed lattice points for any ideal lattice in $R$, solving Ideal-SVP in the process.<\/p>\n \n Let $R_p := \\mathbb{F}_p[x]\/(x^n+1)$. <\/p>\n This is a finite ring with $p^n$ elements. It is not a finite field, as $x^n+1$ factors modulo $p$ (though it is irreducible over $\\mathbb{Z}$).<\/p>\n The elements look like:<\/p>\n \n \nPublic Setup<\/strong> The public setup involves the following:<\/p>\n These will be “ternary polynomials” with coefficients in ${-1,0,+1}$. The coefficients could also be drawn from a normal distribution centered at $0$ with some standard deviation.<\/p>\n \nKey Generation: Private\/Public Keypair<\/strong>\n<\/p>\n \n \nEncryption by Alice<\/strong>\n<\/p>\n \n \nDecryption by Bob<\/strong> Bob decrypts the message:<\/p>\n Homomorphic encryption allows computations to be performed on encrypted data without needing to decrypt it first. This enables privacy-preserving computations.<\/p>\n \nIf $enc(x)$ represents the encryption of data $x$, and $\\oplus$ denotes addition on encrypted data, and $\\otimes$ represents multiplication on encrypted data:\n<\/p>\n Homomorphic encryption can be used in cloud computing, privacy-preserving machine learning, and secure multi-party computations.<\/p>\n \ncode: Key generation:<\/p>\n We generate the secret key, $a$, $e$ as random polynomials, ensuring $a$ is spread out and uniform whereas $sk$ and $e$ are “small” ternary polynomials. We then compute $b = -a*sk – e$, yielding the public key $[b,a]$ and secret key $sk$.<\/p>\n Encryption takes in a public key and plaintext polynomial and produces ciphertext:<\/p>\n We scale the plaintext polynomial via $\\text{scaled\\_m} = \\lfloor q\/t \\rceil m$ and mod coefficients by $q$. Then generate random ternary polynomials $e_1$, $e_2$, $u$. Then $ct_0 = pk[0]*u+e_1+\\text{scaled\\_m}$ and $ct_1 = pk[1]*u + e_2$, and the final ciphertext is the pair $[ct_0,ct_1]$.<\/p>\n Finally, decryption:<\/p>\n We compute $\\text{scaled\\_pt} = ct[1]*sk + ct[0]$, then for each coefficient $c$ in $\\text{scaled\\_pt}$ compute $\\lfloor ct\/q \\rceil$ and take the remainder modulo $t$. The polynomial of coefficients is the decrypted message.<\/p>\n Keygen\/encrypt\/decrypt from start to finish:<\/p>\n We use serialization and base64 encoding to compress the output strings.<\/p>\n For the homomorphic encryption, we only achieve a single product, so this is “leveled homomorphic encryption” at level one for the time being. We use a form of relinearization described here: <\/p>\n https:\/\/crypto.stackexchange.com\/questions\/113740\/how-to-correctly-multiply-homomorphically-two-rlwe-based-encrypted-numbers\/113741<\/a><\/p>\n We perform multiplications of the ciphertext polynomials and the divide by $\\Delta = q\/t$. The implementation is as follows:<\/p>\n We’d eventually like to improve this to be fully homomorphic encryption.<\/p>\n While the polynomial ring structure of ring-LWE is rich and useful for things like homomorphic encryption (since they’re based on rings, the structure is readily available), this additional algebraic structure is thought to make this system potentially vulnerable to attacks that exploit these number theoretic aspects.<\/p>\n There is a generalization of of ring-LWE called module-LWE which uses the rank $k$ free module $R_q^k$ instead of just the ring $R_q$ (when $k=1$), where again $R_q = \\mathbb{Z}_q\/(x^n+1)$ as in ring-LWE. The elements of $R_q^k$ are k-tuples of polynomials in $R_q$. <\/p>\n Module-LWE works sort of like a hybrid between the original LWE scheme and ring-LWE, combining both matrix operations and polynomial multiplication. <\/p>\n Advantages of module-LWE:<\/p>\n The public setup involves the following:<\/p>\n Bob selects a private\/public keypair as follows:<\/p>\n The element $|e_0 \\rangle$ can be discarded.<\/p>\n Alice encrypts a message $m \\in \\mathbb{Z}_2[x]\/(x^n+1)$ as follows:<\/p>\n Alice may discard $\\langle s_1 |$, $\\langle e_1 |$, and $e$<\/p>\n Bob decrypts the message as follows:<\/p>\n $x = c – \\langle p_1 | s_0 \\rangle$<\/p>\n $= (\\lfloor q\/2 \\rceil m + e + \\langle s_1 | p_0 \\rangle ) – (\\langle s_1 | \\hat{A} + \\langle e_1 |)|s_0 \\rangle$<\/p>\n $= \\lfloor q\/2 \\rceil m + e + \\langle s_1 | \\hat{A} | s_0 \\rangle + \\langle s_1 | e_0 \\rangle – \\langle s_1 | \\hat{A} | s_0 \\rangle + \\langle e_1 | s_0 \\rangle$<\/p>\n $= \\lfloor q\/2 \\rceil m + \\text{small polynomials}$<\/p>\n so dividing by $\\lfloor q\/2 \\rceil$ and rounding coefficients to the nearest integer modulo $2$ returns $m$. <\/p>\n \n We’ve published our Rust implementation as a crate at https:\/\/crates.io\/crates\/module-lwe<\/a>.\n<\/p>\n The key generation is fairly straightforward:<\/p>\n We essentially generate a uniformly random matrix with coefficients in $R_q$, generate the secret key and small error vector, compute $t$, and this gives the public and private keys.<\/p>\n Encryption is also rather brief:<\/p>\n We generate random ephemeral keys as small error vectors again with coefficients in $R_q$, compute $\\lfloor q\/2 \\rceil$, convert the binary message to a polynomial with $\\{0,1\\}$ coefficients, then compute the vector $u$ and polynomial $v$. The ciphertext is $(u,v)$.<\/p>\n Finally, decrypt gives the plaintext message given the ciphertext and secret keys:<\/p>\n We compute $v – sk*u$, a polynomial, then again compute $\\lfloor q\/2 \\rceil$, and then compute $c \/ \\lfloor q\/2 \\rceil \\text{ mod } 2$ for each coefficient $c$. This yields the decrypted message.<\/p>\n \n Note that That is, if we encrypt $u$, $v$ to get $enc(u)$ and $enc(v)$, then form the sum $enc(u)+enc(v)$, we have $dec(enc(u)+enc(v)) = u+v$, so we recover the original sum.<\/p>\n We use a serialization and base64 encoding on the resulting arrays of ints to store the keys in a compact form.<\/p>\n Here is the entire encryption process from start to finish:<\/p>\n Note here we use the string methods which generate the keys, ciphertext, and message as a string.<\/p>\n \n https:\/\/crates.io\/crates\/ntt<\/a>\n<\/p>\n In both of the above schemes, we perform a certain number of polynomial multiplications. There is a way to significantly speed this operation up from $\\mathcal{O}(n^2)$ to $\\mathcal{O}(n\\log(n))$.<\/p>\n Polynomials have the property that their multiplication can be viewed as a cyclic convolution of the coefficients. That is, polynomial multiplication is just $f \\star g$.<\/p>\n In general, the Fourier transform will take a convolution of functions to a pointwise product, so that $\\mathcal{F}(f \\star g) = \\mathcal{F}(f) \\cdot \\mathcal{F}(g)$. <\/p>\n We can then perform multiplication in the original domain by performing an inverse Fourier transform, that is:<\/p>\n $f \\star g = \\mathcal{F}^{-1}(\\mathcal{F}(f) \\cdot \\mathcal{F}(g))$<\/p>\n Since we are working over the discrete ring $\\mathbb{Z}_q[x]\/(x^n+1)$, we instead use a version of the NTT which is exact and takes arrays of integers to arrays of integers. This is called the “number theoretic transform”, and relies on a root of unity in the given coefficient ring.<\/p>\n In $\\mathbb{Z}_q$, the roots of unity are given by examining the multiplicative group $(\\mathbb{Z}_q)^{\\times}$, which is just a cyclic group of order $q-1$ if $q$ is prime. Generally, the size of the group is $\\varphi(q)$, the Euler totient function, and will have cyclic factors of size $\\varphi(p_i^{k_i})$ for each prime factor $p_i$ of $q$. It is only cyclic when $q=2, 4, p^k, 2p^k$ which is the case we’ll focus on, in particular $p^k$.<\/p>\n Thus, to find an $n^{th}$ root of unity, we need that $n \\mid \\varphi(q)$. If we then have a primitive root of unity $g$, an element which generates the entire multiplicative group $(\\mathbb{Z}_q)^{\\times}$, then $\\omega = g^{\\varphi(q)\/n}$ will be an $n^{th}$ root of unity. Again, $\\omega$ is just an integer modulo $q$.<\/p>\n The NTT is then just: <\/p>\n $\\hat{a}_k = \\sum_{j=0}^{n-1} a_j \\omega^{jk} \\text{ mod } q \\quad \\text{for } k=0, \\ldots, n-1$<\/p>\n One can think of this as the discrete Fourier transform with a different root of unity. This operation can be represented by a matrix.<\/p>\n In order to optimize this operation, we use the Cooley\u2013Tukey method which uses butterfly operations recursively split the arrays in half. This is a reason that $n$ must be a power of $2$. <\/p>\n \n n.b.<\/strong> If one needs an $n^{th}$ root of unity $\\text{mod } N$ and $N$ is composite, It’s possible to find an $n^{th}$ root of unity $\\omega_i$ for each cyclic factor of size $\\varphi(p_i^{k_i})$ as long as $n \\mid \\varphi(p_i^{k_i})$ for each $i$. Then one can use the Chinese remainder theorem isomorphism to pull back each $\\omega_i$ to get a root of unity $\\omega$ which satisfies the necessary properties, namely $\\sum_{j=0}^{n-1} \\omega^{jk} = 0$ for $1 \\le k < n$.\n<\/p>\n \n code: \n FIPS 203 paper: \n Kyber paper:
\n
\n![\"Surface](\"https:\/\/jacksonwalters.com\/blog\/wp-content\/uploads\/2025\/12\/surface_codes.png\")
![\"Number](\"https:\/\/jacksonwalters.com\/blog\/wp-content\/uploads\/2025\/12\/number_of_qubits_over_time.png\"\n)
\n https:\/\/csrc.nist.gov\/pubs\/ir\/8547\/ipd<\/a>\n<\/p>\n\n
\n
\nring-LWE, homomorphic encryption<\/h2>\n
\n
\nThe “learning with errors” (LWE) problem, along with its ring-LWE variant, are examples of such problems. It involves distinguishing between two distributions:\n<\/p>\n\n
\nGiven $(\\bf{A}, \\bf{b}) \\in \\mathbb{Z}_q^{n \\times m} \\times \\mathbb{Z}_q^m$ where $\\bf{b} = \\bf{A}\\bf{s} + \\bf{e} \\text{ mod } q$:\n<\/p>\n\n
\nThe goal is to recover the secret $\\bf{s}$ or distinguish $(\\bf{A},\\bf{b})$ from uniformly random samples.\n<\/p>\n\n
\n
\nThe variant we focus on is ring-LWE, where the lattices are number-theoretic and derived from ideals in certain polynomial rings:
\n\n<\/p>\n
\nwhere $f(x)$ is typically a polynomial like $x^n – 1$. However, this choice is insecure. Instead, we use:<\/p>\n
\n\n<\/p>\n\n
\n
\n
\n
\nSolving ring-LWE allows efficient recovery of short vectors in ideal lattices:\n<\/p>\n\n
\nOur goal is to introduce the simplest possible implementation of the ring-LWE encryption scheme.\n<\/p>\n\n
\n$$R_p = \\{a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \\ldots + a_1x + a_0: a_i \\in \\mathbb{F}_p\\}$$\n<\/p>\n
\n\n<\/p>\n\n
\nBob creates a private\/public keypair as follows:\n<\/p>\n\n
\n
\nAlice encrypts a message $m$ as follows:\n<\/p>\n\n
\n
\n\n<\/p>\n\n
Homomorphic Encryption<\/h3>\n
\n
\n
Code Examples<\/h3>\n
\nhttps:\/\/crates.io\/crates\/ring-lwe<\/a>\n<\/p>\n\n
pub fn keygen(params: &Parameters, seed: Option<u64>) -> ([Polynomial<i64>; 2], Polynomial<i64>) {\n\n\/\/rename parameters\nlet (n, q, f, omega) = (params.n, params.q, ¶ms.f, params.omega);\n\n\/\/ Generate a public and secret key\nlet sk = gen_ternary_poly(n, seed);\nlet a = gen_uniform_poly(n, q, seed);\nlet e = gen_ternary_poly(n, seed);\nlet b = polyadd(&polymul_fast(&polyinv(&a,q), &sk, q, &f, omega), &polyinv(&e,q), q, &f); \/\/ b = -a*sk - e\n \n\/\/ Return public key (b, a) as an array and secret key (sk)\n([b, a], sk)\n}<\/code>\n<\/pre>\n\n
\npub fn encrypt( \n pk: &[Polynomial<i64>; 2], \/\/ Public key (b, a)\n m: &Polynomial<i64>, \/\/ Plaintext polynomial\n params: &Parameters, \/\/parameters (n,q,t,f)\n seed: Option<u64> \/\/ Seed for random number generator\n) -> [Polynomial<i64>; 2] {\n let (n,q,t,f,omega) = (params.n, params.q, params.t, ¶ms.f, params.omega);\n \/\/ Scale the plaintext polynomial. use floor(m*q\/t) rather than floor (q\/t)*m\n let scaled_m = mod_coeffs(m * q \/ t, q);\n\n \/\/ Generate random polynomials\n let e1 = gen_ternary_poly(n, seed);\n let e2 = gen_ternary_poly(n, seed);\n let u = gen_ternary_poly(n, seed);\n\n \/\/ Compute ciphertext components\n let ct0 = polyadd(&polyadd(&polymul_fast(&pk[0], &u, q, f, omega), &e1, q, f),&scaled_m,q,f);\n let ct1 = polyadd(&polymul_fast(&pk[1], &u, q, f, omega), &e2, q, f);\n\n [ct0, ct1]\n}\n<\/code>\n<\/pre>\n\n
\npub fn decrypt(\n sk: &Polynomial<i64>, \/\/ Secret key\n ct: &[Polynomial<i64>; 2], \/\/ Array of ciphertext polynomials\n params: &Parameters\n ) -> Polynomial<i64> {\n let (_n,q,t,f,omega) = (params.n, params.q, params.t, ¶ms.f, params.omega);\n let scaled\\_pt = polyadd(&polymul_fast(&ct[1], sk, q, f, omega),&ct[0], q, f);\n let mut decrypted_coeffs = vec![];\n let mut s;\n for c in scaled_pt.coeffs().iter() {\n s = nearest_int(c*t,q);\n decrypted_coeffs.push(s.rem_euclid(t));\n }\n Polynomial::new(decrypted_coeffs)\n}\n<\/code>\n<\/pre>\n\n
\nlet seed = None; \/\/set the random seed\nlet message = String::from(\"hello\");\nlet params = Parameters::default();\nlet keypair = keygen_string(¶ms,seed);\nlet pk_string = keypair.get(\"public\").unwrap();\nlet sk_string = keypair.get(\"secret\").unwrap();\nlet ciphertext_string = encrypt_string(&pk_string, &message, ¶ms,seed);\nlet decrypted_message = decrypt_string(&sk_string, &ciphertext_string, ¶ms);\nassert_eq!(message, decrypted_message, \"test failed: {} != {}\", message, decrypted_message);\n<\/code>\n<\/pre>\n\n
\nlet seed = None; \/\/set the random seed\nlet mut params = Parameters::default();\nlet (q, t, f) = (params.q, params.t, ¶ms.f);\nparams.q = q*q;\nparams.omega = omega(params.q, 2*params.n);\n\n\/\/create polynomials from ints\nlet m0_poly = Polynomial::new(vec![1, 0, 1]);\nlet m1_poly = Polynomial::new(vec![0, 0, 1]);\n\n\/\/ Generate the keypair\nlet (pk, sk) = keygen(¶ms,seed);\n\n\/\/ Encrypt plaintext messages\nlet u = encrypt(&pk, &m0_poly, ¶ms, seed);\nlet v = encrypt(&pk, &m1_poly, ¶ms, seed);\n\nlet plaintext_prod = polymul(&m0_poly, &m1_poly, t, &f);\n\n\/\/compute product of encrypted data, using non-standard multiplication\nlet c0 = polymul(&u[0],&v[0],params.q,&f);\nlet u0v1 = &polymul(&u[0],&v[1],params.q,&f);\nlet u1v0 = &polymul(&u[1],&v[0],params.q,&f);\nlet c1 = polyadd(u0v1,u1v0,params.q,&f);\nlet c2 = polymul(&u[1],&v[1],params.q,&f);\n\n\/\/compute c0 + c1*s + c2*s*s\nlet c1_sk = &polymul(&c1,&sk,params.q,&f);\nlet c2_sk_squared = &polymul(&polymul(&c2,&sk,params.q,&f),&sk,params.q,&f);\nlet ciphertext_prod = polyadd(&polyadd(&c0,c1_sk,params.q,&f),c2_sk_squared,params.q,&f);\n\/\/let delta = q \/ t, divide coeffs by 1 \/ delta^2\nlet delta = q \/ t;\nlet decrypted_prod = mod_coeffs(Polynomial::new(ciphertext_prod.coeffs().iter().map(|&coeff| nearest_int(coeff,delta * delta) ).collect::<Vec<_>>()),t);\n \nassert_eq!(plaintext_prod, decrypted_prod, \"test failed: {} != {}\", plaintext_prod, decrypted_prod);\n<\/code>\n<\/pre>\n
\nmodule-lwe<\/h2>\n
\n
\n
![\"module-lwe](\"https:\/\/jacksonwalters.com\/blog\/wp-content\/uploads\/2025\/12\/module_lwe_diagram.png\")
Public Setup<\/h3>\n
\n
\n
Key Generation<\/h3>\n
\n
\n
Encryption by Alice<\/h3>\n
\n
\n
Decryption by Bob<\/h3>\n
\n
Correctness<\/h3>\n
Code Examples<\/h3>\n
\n
\npub fn keygen(\n params: &Parameters,\n seed: Option<u64> \/\/random seed\n) -> ((Vec<Vec<Polynomial<i64>>>, Vec<Polynomial<i64>>), Vec<Polynomial<i64>>) {\n let (n,q,k,f,omega) = (params.n, params.q, params.k, ¶ms.f, params.omega);\n \/\/Generate a public and secret key\n let a = gen_uniform_matrix(n, k, q, seed);\n let sk = gen_small_vector(n, k, seed);\n let e = gen_small_vector(n, k, seed);\n let t = add_vec(&mul_mat_vec_simple(&a, &sk, q, &f, omega), &e, q, &f);\n \n \/\/Return public key (a, t) and secret key (sk) as a 2-tuple\n ((a, t), sk)\n}\n<\/code>\n<\/pre>\n\n
\npub fn encrypt(\n a: &Vec<Vec<Polynomial<i64>>>,\n t: &Vec<Polynomial<i64>>,\n m_b: &Vec<i64>,\n params: &Parameters,\n seed: Option<u64>\n) -> (Vec<Polynomial<i64>>, Polynomial<i64>) {\n\n \/\/get parameters\n let (n, q, k, f, omega) = (params.n, params.q, params.k, ¶ms.f, params.omega);\n \n \/\/generate random ephermal keys\n let r = gen_small_vector(n, k, seed);\n let e1 = gen_small_vector(n, k, seed);\n let e2 = gen_small_vector(n, 1, seed)[0].clone(); \/\/ Single polynomial\n\n \/\/compute nearest integer to q\/2\n let half_q = nearest_int(q,2);\n\n \/\/ Convert binary message to polynomial\n let m = Polynomial::new(vec![half_q])*Polynomial::new(m_b.to_vec());\n\n \/\/ Compute u = a^T * r + e_1 mod q\n let u = add_vec(&mul_mat_vec_simple(&transpose(a), &r, q, f, omega), &e1, q, f);\n\n \/\/ Compute v = t * r + e_2 - m mod q\n let v = polysub(&polyadd(&mul_vec_simple(t, &r, q, &f, omega), &e2, q, f), &m, q, f);\n\n (u, v)\n}\n<\/code>\n<\/pre>\n\n
\npub fn decrypt(\n sk: &Vec<Polynomial<i64>>, \/\/secret key\n u: &Vec<Polynomial<i64>>, \/\/ciphertext vector\n v: &Polynomial<i64> ,\t\t\/\/ciphertext polynomial\n params: &Parameters\n) -> Vec<i64> {\n let (q, f, omega) = (params.q, ¶ms.f, params.omega); \/\/get parameters\n let scaled_pt = polysub(&v, &mul_vec_simple(&sk, &u, q, &f, omega), q, f); \/\/Compute v-sk*u mod q\n let half_q = nearest_int(q,2); \/\/ compute nearest integer to q\/2\n let mut decrypted_coeffs = vec![];\n let mut s;\n for c in scaled_pt.coeffs().iter() {\n s = nearest_int(*c,half_q).rem_euclid(2);\n decrypted_coeffs.push(s);\n }\n decrypted_coeffs\n}\n<\/code>\n<\/pre>\nmodule-lwe<\/code> is not fully homomorphic, but it is additively homomorphic.\n<\/p>\n\n
\nlet seed = None; \/\/set the random seed\nlet params = Parameters::default();\nlet (n, q, f) = (params.n, params.q, ¶ms.f);\n\nlet mut m0 = vec![1, 0, 1];\nm0.resize(n, 0);\nlet mut m1 = vec![0, 0, 1];\nm1.resize(n, 0);\nlet mut plaintext_sum = vec![1, 0, 0];\nplaintext_sum.resize(n, 0);\nlet (pk, sk) = keygen(¶ms,seed);\n\n\/\/ Encrypt plaintext messages\nlet u = encrypt(&pk.0, &pk.1, &m0, ¶ms, seed);\nlet v = encrypt(&pk.0, &pk.1, &m1, ¶ms, seed);\n\n\/\/ Compute sum of encrypted data\nlet ciphertext_sum = (add_vec(&u.0,&v.0,q,f), polyadd(&u.1,&v.1,q,f));\n\n\/\/ Decrypt ciphertext sum u+v\nlet mut decrypted_sum = decrypt(&sk, &ciphertext_sum.0, &ciphertext_sum.1, ¶ms);\ndecrypted_sum.resize(n, 0);\n\nassert_eq!(decrypted_sum, plaintext_sum, \"test failed: {:?} != {:?}\", decrypted_sum, plaintext_sum);\n<\/code>\n<\/pre>\n\n
\nlet seed = None; \/\/set random seed\nlet message = String::from(\"hello\");\nlet params = Parameters::default();\nlet keypair = keygen_string(¶ms,seed);\nlet pk_string = keypair.get(\"public\").unwrap();\nlet sk_string = keypair.get(\"secret\").unwrap();\nlet ciphertext_string = encrypt_string(&pk_string, &message, ¶ms,seed);\nlet decrypted_message = decrypt_string(&sk_string, &ciphertext_string, ¶ms);\nassert_eq!(message, decrypted_message, \"test failed: {} != {}\", message, decrypted_message);\n<\/code>\n<\/pre>\n
\nthe number theoretic transform (NTT)<\/h2>\n
\n
\npub fn ntt(a: &[i64], omega: i64, n: usize, p: i64) -> Vec<i64> {\nlet mut result = a.to_vec();\nlet mut step = n\/2;\nwhile step > 0 {\n let w_i = mod_exp(omega, (n\/(2*step)).try_into().unwrap(), p);\n for i in (0..n).step_by(2*step) { \n let mut w = 1;\n for j in 0..step {\n let u = result[i+j];\n let v = result[i+j+step];\n result[i+j] = mod_add(u,v,p);\n result[i+j+step] = mod_mul(mod_add(u,p-v,p),w,p);\n w = mod_mul(w,w_i,p);\n }\n }\n step\/=2;\n}\nresult\n}\n<\/code>\n<\/pre>\n
\nmodule-lattice key encapsulation mechanism (ML-KEM), FIPS 203, Kyber<\/h2>\n
\n https:\/\/crates.io\/crates\/mlkem-fips203<\/a>\n<\/p>\n
\n https:\/\/nvlpubs.nist.gov\/nistpubs\/FIPS\/NIST.FIPS.203.pdf<\/a>\n<\/p>\n
\n https:\/\/eprint.iacr.org\/2017\/634.pdf<\/a>\n<\/p>\n