How are public and private keys generated and used for encryption and decryption in a lattice based cryptosystem?

I've recently become quite interested in lattice based cryptosystems, and I wish to understand them more deeply. I have only a rudimentary understanding of the shortest vector problem (SVP), and its brother the closest vector problem (CVP), which are central to this form of cryptography, though I understand lattices, vectors, and bases quite thoroughly (I took some linear algebra in college back in the day). I thought it would be more educational to actually understand how keys are generated and the actual encryption process.

So, how are private and public keys generated in a lattice based cryptosystem, and how are they used to encrypt and decrypt data? I'd prefer more words than math please and thank you!

I'm glad there are these types of questions that inspires the spirit of learning, eventhough this question is a bit too broad. Also, Chris Peikert is a member of this site, he may drop by if we're lucky.

First, key generation.

Generally, there are 2 major paradigms of key generation: NTRU, and learning-with-error.

• In NTRU, 2 short vectors (typically denoted by $f$ and $g$), are sampled, and their quotient is computed as the public key (typically $h$).

• In learning with error, 2 short vectors are sample (typically denoted by $s$ and $e$), a base matrix $A$ is derived from a short seed using some PRNG, and the public key $T$ is calculated as $T=As+e$.

  There are ways to compress $T$ by dropping lower-order bits. An alternative way to represent the public key is to consider $A$ as row vector with $(A, I)$ with $I$ an identity matrix, and $T$ as matrix product of the column vector with elements $s$ and $e$ with the aforementioned row vector. It's a bit like this: $T=AS$

So how to encrypt and decrypt in lattice crypto? There are various methods.

To explain the NTRU paradigm requires quite a bit of maths, and since you said you prefer words, I'll skip most of that. It suffices to say that, there are proofs that shows the encryption and the corresponding decryption "formula" are correct.

The LWE paradigm simply use the key generation formula to generate key share (we'll get to encryption in a jiffy), which will be accompanied with some reconciliation information as the error terms make the computation not 100% exact. After generating the key share, the ciphertext is added to the key share element-by-element. During decryption, the user applies the key generation formula to the key share using their private key, and use that, the reconciliation info, to recover the plaintext from the ciphertext.

The form of LWE key exchange and encryption is only IND-CPA secure, and Fujisaki-Okamoto transformation is applied to make them IND-CCA secure. It had long been observed that, matrix multiplication can be transformed into element-wise multiplication when working under NTT domain, and such optimization are typically employed in the schemes.

Formulas for presentational clarity:

• encryption:

Generate a random short vector $R$ and compute ciphertext $U$ and $V$.

$$U=AR$$ $$V=M+TR$$

• decryption:

Decryption. Additional reconciliation info are usually involved.

$$M=V-US$$

You haven't mentioned digital signatures, but I suppose you'll want to hear about this part.

The most familiar and newbie-friendly form of DSS in Lattice is the Fiat-Shamir with Abort paradigm. For ease of comprehension, let's look at Schnorr's signature first.

Being a DLog-based scheme, it has a private exponent $x$ and public key $y=g^x$. Various forms of Schnorr's signature scheme involves a formula not so different from:

$$k-cx$$

Here, $x$ is the private key, and $k$ is a cryptographically-secret random number. The secrecy of both of these numbers make it impossible to recover either from just the value of the above formula.

When signing, the signer computes:

$$r=g^k$$ $$c=\operatorname{Hash}(r,m)$$ $$s=k-cx$$

and $(r,s)$ is the signature.

the formula concerning the correctness of the scheme is:

$$r = g^s \cdot y^c = g^{k-cx} \cdot g^{xc} = g^k$$

When verifying, we first put $r$ into the hash function along with the messagae, and compute $c$; then we compute $g^s \cdot y^c$ and check if it equals $r$.

In a Fiat-Shamir with Abort paradigm signature scheme, exponentiation is replaced with multiplication, scalars are replaced with lattice elements, and an additional check is made with regard to the bound of the norm of signature elements.

Additionally, the scheme repeats itself until the signature vectors don't leak info on private key.

So:

• Keygen:

$$T=AS$$

• Sign:

$$U=AY$$ $$C=\operatorname{Hash}(U,msg)$$ $$Z=Y+SC$$

• Verify:

$$V=AZ+TC$$ $$W=\operatorname{Hash}(V,msg)$$

Then check that $W=C$ and that the norm of $Z$ is small enough to deter potential forgery attack.

There are signature schemes not based on Fiat-Shamir with Abort, most notable the GPV framework and its instantiation Falcon. This is a math-heavy "beast".

Lastly, we have to mention that, there are 3 major forms of lattice ranked according to their structure:

Ring-based: The entire element is a polynomial, which is isomorphic to a subset of matrix elements from a higher rank.

Module-based: The elements in the matrix are polynomial "modules", which in turn is, isomorphic to

Unstructured: The elements are integers (finite fields in most schemes).