What Makes Single-Part Ciphertext Possible in NTRU, and Why Do LWE Schemes Typically Need Two Parts?

Question

Both LWE-based and NTRU-based PKE/KEMs are lattice-based cryptographic approaches. Why do LWE-based schemes typically require two parts in the ciphertext, while NTRU-based schemes need only one single ciphertext?

• Is there any scheme that designs an LWE-based scheme using only a single polynomial in the ciphertext structure? Is it possible?

Kyber: $$ \begin{aligned} & \mathbf{u}:=\operatorname{NTT}^{-1}\left(\hat{\mathbf{A}}^T \circ \hat{\mathbf{r}}\right)+\mathbf{e}_1 \\ & v:=\operatorname{NTT}^{-1}\left(\hat{\mathbf{t}}^T \circ \hat{\mathbf{r}}\right)+e_2+\operatorname{Decompress}_q\left(\operatorname{Decode}_1(m), 1\right)\\ & c_1:=\operatorname{Encode}_{d_u}\left(\operatorname{Compress}_q\left(\mathbf{u}, d_u\right)\right) \\ & c_2:=\operatorname{Encode}_{d_v}\left(\operatorname{Compress}_q\left(v, d_v\right)\right) \\ & \text { return } c=\left(c_1 \| c_2\right) \end{aligned} $$

NewHope: $$\begin{array}{ll} & \hat{\mathbf{u}} \leftarrow \hat{\mathbf{a}} \circ \hat{\mathbf{t}}+\operatorname{NTT}\left(\mathbf{e}^{\prime}\right)\\ & \mathbf{v}^{\prime} \leftarrow \mathbf{N T T}^{-1}(\hat{\mathbf{b}} \circ \hat{\mathbf{t}})+\mathbf{e}^{\prime \prime}+\mathbf{v} \\ & h \leftarrow \operatorname{Compress}\left(\mathbf{v}^{\prime}\right) \\ & \text { return } c=\operatorname{EncodeC}(\hat{\mathbf{u}}, h) \end{array}$$

Frodo: $$ \mathrm{B}^{\prime} \leftarrow \mathrm{S}^{\prime} \mathrm{A}+\mathrm{E}^{\prime}$$ $$ c_1 \leftarrow \operatorname{Pack}\left(\mathrm{~B}^{\prime}\right)$$ $$ \mathrm{C} \leftarrow \mathrm{~V}+\operatorname{Encode}(u)$$ $$c_2 \leftarrow \operatorname{Pack}(\mathrm{C})$$

$$ s s \leftarrow \operatorname{SHAKE}\left(c_1\left\|c_2\right\|\right.salt \| k, len \left.{ }_{\text {sec }}\right)$$

$$\text{ Return ciphertext } c \leftarrow c_1\left\|c_2\right\| \text{salt and shared secret} ss$$

NTRU:

$$\mathbf{h}= unpack\_Rq0(\text{packed_public_key})$$ $$\mathbf{c}=\mathrm{Rq}\left(\mathbf{r} \cdot \mathbf{h}+\mathbf{m}_1\right)$$ $$\text{packed_ciphertext} = pack\_Rq0(c)$$

Answer 1

I wish that I could upvote this question more than once; I think that it touches on an interesting division of the way in which we construct public/private key cryptography key establishment schemes. I'm not sure how well I can articulate this and welcome other views.

Two constructions

Public/private key cryptography depends on computational processes where it is hard to determine the output from the input. This might be the extraction of modular $e$th roots, the calculation of discrete logarithms, or the solution of noisy linear equations.

I claim that there are two different types of scheme:

• Ones where some parameter of the process is constructed from a secret value, knowledge of which allows inputs from outputs. Examples here might include RSA and NTRU.
• Ones where each communicator has a known input-output pair to the process and an auxiliary computation that combines an input with a non-corresponding output in a manner that commutes (or approximately so) and also such that the output of the auxiliary function is hard to compute using only public values. Examples here might include ECDH where $$\mathrm{input}_A(\mathrm{Output}_B)=\mathrm{input}_B(\mathrm{Output}_A)$$ or the Ding key exchange where $$\mathbf{input}_B^T\mathbf{output}_A\approx \mathbf{output}_B^T\mathbf{input}_A$$

Two key establishment methods

From the first of these constructions, it is easy to construct a key transportation scheme. Alice generates a public parameter from a secret value, and distributes this. Bob generates a secret input and creates the associated output which he transmits to Alice. Alice is able to recover the input using her secret values.

From the second of the constructions, it is easy to construct a key exchange scheme. Alice and Bob both generate secret inputs and compute the corresponding outputs. They exchange their outputs publicly and use the auxiliary computation to create a shared value.

Building key transport from key exchange

The key exchange scheme described above can be converted to a key transportation scheme. Alice selects a secret input and generates an associated output, which she then publishes and distributes as a static public key. Bob selects a secret input and generates an associated output; he also completes the auxiliary computation using his input and Alice's output to create a shared secret value. He then combines this shared secret value with whatever key material he wishes to transport and sends Alice both his output from the first process and the combined key and shared secret value. Using Bob's output, Alice can also complete the auxiliary process and recover the shared secret value. Using this she can recover the material.

Notice that in the above, Bob's transmission to Alice contains two distinct elements: his output from the main process and the combined shared secret value and key material.

Schemes that fall under this description include El Gamal and the K-PKE method in ML-KEM.

Focus on LWE schemes

Let's put this framework over the various cryptographic constructs for key establishment based on learning with errors. Deviating slightly from formal definitions of LWE, cryptographic LWE constructs tend to be based around a computation $$\mathbf y = M\mathbf s+\mathbf e\mod q$$ where $M$ is a $n\times n$ integer matrix, $\mathbf e$ is a $n$-long vector with "small" entries. In many instantiations, $\mathbf s$ is also small.

Using Ding's key agreement, this lends itself to the second type of construction where $M$ is a parameter, $\mathbf s$ is the input ($\mathbf e$ can also be considered input if you wish) and $\mathbf y$ is the output. We have to tweak things slightly by having one party (say Alice) use the matrix $M$ and the other (say Bob) use its transpose $M^T$. Thus $$\mathbf{output}_A=M\mathbf{input}_A+\mathbf e_A$$ $$\mathbf{output}_B=M^T\mathbf{input}_B+\mathbf e_B$$ and they can agree an approximate shared secret $$\mathbf{output}_B^T\mathbf{input}_A\approx\mathbf{input}_B^TM\mathbf{input_A}\approx\mathbf{input}_B^T\mathbf{output}_A$$ with $\approx$ covering an error equal to the dot product of two small vectors.

Naturally, this can be used as a key exchange if we tidy up the $\approx$ issues. This means that we can also convert to a key transport mechanism in the manner described above. This is the approach taken with ML-KEM (at least in the PKE parts), New Hope, and Frodo. Because these are all taking the approach of building a key transportation out of a key exchange and hence all of them exhibit the two component cryptograms that we described.

I interpret your question as to whether there are constructions that use an LWE computation in the manner of our first construction, from which inputs can be recovered from outputs. I would claim that NTRU is an example of such (this may offend some lattice cryptography purists). In this case, we choose our parameter $M$ to be of the form $M=F^{-1}G\mod q$ where $F$ and $G$ are matrices all of whose entries are "small", and where all of the entries of $F$ are divisible by some small prime $p$ (e.g. $p=3$). In this case, given a computation $$\mathbf y=M\mathbf s+\mathbf e\mod q$$ with $M$ of our special form, $\mathbf s$ and $\mathbf e$ small, the NTRU decryption process says to multiply by $F$ to get $$F\mathbf y=G\mathbf s+\mathbf F\mathbf e\mod q$$ as all of the products on the right hand side are of small elements, we hope that we can drop the $\mod q$ and get something that holds over the integers. Reducing this mod $p$ removes $F\mathbf e$ and multiplying by $G^{-1}\mod p$ recovers $\mathbf s$.

This does not preclude the existence of other soluble instances of LWE-like computations for other specially constructed $M$.