A Thorough Treatment of Highly-Efficient NTRU Instantiations

Abstract

Cryptography based on the hardness of lattice problems over polynomial rings currently provides the most practical solution for public key encryption in the quantum era. Indeed, three of the four schemes chosen by NIST in the recently-concluded post-quantum standardization effort for encryption and signature schemes are based on the hardness of these problems. While the first encryption scheme utilizing properties of polynomial rings was NTRU (ANTS ’98), the scheme that NIST chose for public key encryption (CRYSTALS-Kyber) is based on the hardness of the somewhat-related Module-LWE problem. One of the reasons for Kyber’s selection was the fact that it is noticeably faster than NTRU and a little more compact. And indeed, the practical NTRU encryption schemes in the literature generally lag their Ring/Module-LWE counterparts in either compactness or speed, or both.

In this paper, we put the efficiency of NTRU-based schemes on equal (even slightly better, actually) footing with their Ring/Module-LWE counterparts. We provide several instantiations and transformations, with security given in the ROM and the QROM, that are on par, compactness-wise, with their counterparts based on Ring/Module-LWE. Performance-wise, the NTRU schemes instantiated in this paper over NTT-friendly rings of the form $\mathbb {Z}_q[X]/(X^d-X^{d/2}+1)$ are the fastest of all public key encryption schemes, whether quantum-safe or not. When compared to the NIST finalist NTRU-HRSS-701, our scheme is $15\%$ more compact and has a 15X improvement in the round-trip time of ephemeral key exchange, with key generation being 35X faster, encapsulation being 6X faster, and decapsulation enjoying a 9X speedup.

1 Introduction

The NTRU encryption scheme [19] was the first truly practical scheme based on the hardness of lattice problems over polynomial rings and, in many ways, the first really practical quantum-safe encryption scheme. The hardness of NTRU was originally stated as its own assumption, but as lattice cryptography evolved over the next few decades, the most natural way to view the hardness behind the NTRU encryption scheme was as a combination of two assumptions over a polynomial ring $R=\mathbb {Z}_q[X]/(f(X))$. The first assumption, which we call the NTRU assumption, is that the quotient of two polynomials $\textbf{f}$ and $\textbf{g}$, with coefficients chosen from some narrow distribution, looks uniform in R. The second assumption, which later became known as the Ring-LWE assumption [25, 30] states that given a uniformly random $\textbf{h}\in R$, and $\textbf{h}\textbf{r}+\textbf{e}$, for polynomials $\textbf{e}$ and $\textbf{r}$ with coefficients from a narrow distribution, it is difficult to recover $\textbf{e}$. One could eliminate the need for the first assumption by choosing a relatively wide distribution for $\textbf{f}$ and $\textbf{g}$ [29], but the resulting scheme becomes very inefficient; thus all practical instantiations of NTRU were based on these two assumptions.

Since Regev’s seminal work constructing an encryption scheme based on the LWE problem over general lattices [28], and its subsequent porting to lattices over polynomial rings [23, 25, 30], most of the community effort of shifted to building encryption schemes that do not require the NTRU assumption, and are just based on the decisional version (which was shown to be equivalent to the search one in [25], and for which no faster practical algorithm is known) of the Ring/Module-LWE problems. Indeed, in the first round of the NIST call for quantum-safe encryption, only 3 out of 17 proposals for lattice-based encryption schemes over polynomial rings relied on the NTRU assumption, while the rest used just an LWE-type assumption.

There are a few reasons for avoiding the NTRU assumption. The first is that the additional NTRU assumption is known to be false in the regime where the modulus q of the ring is noticeably larger than the dimension [1, 8, 15, 22] (for the same parameters, the Ring-LWE problem is still believed to be hard). While the attacks against this parameter regime have not been extended to the one used for public key encryption, it does give some reason for concern. Secondly, in many rings, the division operation is significantly more expensive than multiplication, and so the assumption was also avoided for efficiency considerations. And third is that the NTRU assumption does not naturally lend itself to more flexible instantiations, such as Module-LWE. That is, it naturally operates over a module of dimension 1 (again, due to the division operation), whereas LWE-based schemes can be extended to work over modules of a larger dimension. This has the advantage that the underlying ring operations do not need to change as one increases the security parameter. In fact, all of the non-NTRU finalists in the NIST post-quantum standardization process use the module structure [5, 10]. These schemes are also significantly more efficient than the finalist NTRU-based proposal [21].¹

There are, however, also several advantages to NTRU-based schemes. One real-world advantage that NTRU has is that all patents on it have expired, while there may still conceivably be some (possibly still hidden) intellectual property claims on the Ring/Module-LWE schemes. Also, NTRU may have practical advantages when used in certain scenarios involving zero-knowledge proofs, since the ciphertext has a simpler form and thus may require shorter proofs that it was correctly formed. In this paper, our goal is to put NTRU-based constructions on equal footing, performance-wise, as schemes based on Ring/Module-LWE.

1.1 Speed

The most efficient lattice-based schemes are those that natively work over rings $\mathbb {Z}_q[X]/(f(X))$ that support the Number Theory Transform (NTT). When the polynomial f(X) factors into components having small degree, one can perform multiplication (and division) in the ring using the Chinese Remainder Theorem. That is, one evaluates the multiplicands modulo these factors, performs component-wise multiplication, and finally converts the product back into the original form. The process of efficiently doing these computations is the NTT and the inverse NTT.

The most commonly used NTT-friendly ring is of the form $\mathbb {Z}_q[X]/(X^d+1)$, where d is a power-of-2. For well-chosen q, the polynomial $X^d+1=(X^{d/2}-r)(X^{d/2}+r)\bmod q$, and the respective factors similarly split as $(X^{d/2}-r)=(X^{d/4}-\sqrt{r})(X^{d/4}+\sqrt{r})\bmod q$, etc. until one reaches an irreducible polynomial of a small (usually 1 or 2) degree. Because of this very nice factorization (the “niceness” mainly rests in the fact that all factors have 2 non-zero coefficients, making reduction modulo them linear-time), evaluation of any polynomial modulo the irreducible factors can be done using approximately $2d\log {d}$ operations over $\mathbb {Z}_q$. These rings also have some very nice algebraic properties – in particular the expansion factor [24] controlling the growth of polynomial products in the ring is the minimal of all rings. The one disadvantage of these rings is that they are sparse and so one cannot always find one for an appropriate security level. The hardness of the NTRU and Ring-LWE problem directly depends on the degree of the polynomial f(X). Based on the current state of knowledge, obtaining 128-256 bit hardness requires taking dimensions somewhere between 512 and 1024. Since there are no powers of 2 in between, and because one may need to go beyond 1024 in case somewhat better algorithms are discovered, the sparsity of these rings is an inconvenience. The Module-LWE problem overcomes this inconvenience because the problem instance can be made up of a matrix of smaller rings, but this does not work for NTRU because this approach would significantly increase the size of the public key.

One can overcome this issue in NTRU by using “NTT-friendly” rings $f(X)=X^d-X^{d/2}+1$ where $d=2^i3^j$.² The rings $\mathbb {Z}_q[X]/(X^d-X^{d/2}+1)$, for appropriately-chosen primes, also support efficient NTT because $X^d-X^{d/2}+1=(X^{d/2}+\zeta )(X^{d/2}-(\zeta +1))\bmod q$, where $\zeta$ is a third root of unity in $\mathbb {Z}_q$ (not equal to 1). And after that, every term $(X^k-r)$ factors into either $(X^{k/2}-\sqrt{r})(X^{k/2}+\sqrt{r})$ or into $(X^{k/3}-\root 3 \of {r})(X^{k/3}-\zeta \root 3 \of {r})(X^{k/3}-\zeta ^2 \root 3 \of {r})$ modulo q. In both cases, one can efficiently proceed with the very efficient NTT because all factors have two non-zero coefficients. As can be seen from Table 1, there are many such polynomials of degree between 512 and 1024. In the work of [26], a version of NTRU was implemented over the ring $\mathbb {Z}_{7681}[X]/(X^{768}-X^{384}+1)$, but due to the structure of the ring, no factorization into three terms was necessary. In this work we show that there aren’t any efficiency issues when the latter does happen, and give an instantiation of a scheme over the ring $\mathbb {Z}_{2917}[X]/(X^{648}-X^{324}+1)$. The conclusion is that all of the schemes in Table 1 should have almost equally good instantiations.

One should also mention that Module and Ring-LWE schemes can be used in non-NTT-friendly rings [9], and the inefficiency of multiplication in these rings can be partially overcome by doing multiplication in a ring with a larger modulus and/or degree of f(X) which supports NTT, and then reducing back into the original ring. This is, however not possible for NTRU-based schemes because NTRU requires polynomial division, and it is not known how to map this operation between rings. On the other hand, if a ring supports NTT, then division is essentially as fast as multiplication, with only the operation in the base ring (which is of a very low degree) being different. Thus any hope of having NTRU-based schemes being competitive with Ring/Module-LWE schemes seems to require defining the NTRU encryption scheme directly over NTT-friendly rings.

A reason that NTRU was traditionally not defined over NTT-friendly-rings was presumably due to an attack of Gentry [18] against a version of NTRU over the ring $\mathbb {Z}_q[X]/(X^d-1)$, where the polynomial $X^d-1$ could be factored as $(X^{d/2}-1)(X^{d/2}+1)$. The observation was that instead of working over the ring $\mathbb {Z}_q[X]/(X^d-1)$, one can reduce everything modulo $X^{d/2}-1$ and work over the ring $\mathbb {Z}_q[X]/(X^{d/2}-1)$. What makes the attack work is that reduction modulo $X^{d/2}-1$ is a ring homomorphism and that this reduction increases the size of the maximum coefficient by at most a factor of 2. Thus one can solve a shortest vector problem (upon which NTRU is based) in a lattice with a significantly smaller dimension, but whose norm increased by only a factor of 2. From this attack, one might infer that it’s important to have the polynomial f(X) be irreducible (or have a large component of it be irreducible). Interestingly, however, the theoretical works of [23,24,25] showed that in the reductions from worst-case lattice problems to average-case problems over polynomial rings (e.g. Ring/Module-SIS, Ring/Module-LWE), one needs the polynomial f(X) to be irreducible in $\mathbb {Z}[X]$, but the polynomial f(X) splitting in $\mathbb {Z}_q[X]$ does not seem to make the average-case problem easier.³ And in fact, most practical lattice-based constructions work over the ring $\mathbb {Z}_q[X]/(X^d+1)$, where d is a power of 2. While polynomials $X^d+1$ are irreducible in $\mathbb {Z}[X]$, they are always reducible in $\mathbb {Z}_q[X]$; and consistent with the theoretical intuition, there have not been any attacks exploiting the factorization of $X^d+1$ modulo q. We therefore don’t see any danger of using NTRU over NTT-friendly rings.

1.2 Decryption Error and Compactness

To make NTRU encryption work efficiently over NTT-friendly rings, one creates the public key as $\textbf{h}=p\textbf{g}/(p\textbf{f}+1)$, for a small prime p, and then the encryption function (which is one-way CPA secure – meaning that it is hard to decrypt for a random message) outputs $\textbf{c}=\textbf{h}\textbf{r}+\textbf{m}$, where $\textbf{r},\textbf{m}$ are polynomials with coefficients coming from a narrow distribution. The decryption algorithm computes $(p\textbf{f}+1)\textbf{c}=p(\textbf{g}\textbf{r}+\textbf{f}\textbf{m})+\textbf{m}$. If the coefficients of the product $p(\textbf{g}\textbf{r}+\textbf{f}\textbf{m})$ are smaller than q/2, then one can recover $\textbf{m}$ by taking the above value modulo p.

One important area of optimization (and what was already recognized in the original NTRU scheme [19]) is that the product $p(\textbf{g}\textbf{r}+\textbf{f}\textbf{m})$ does not always need to be less than q/2, but only with very high probability. On the one hand, this probability should be negligible, as obtaining decryption failures on honestly-generated ciphertexts is the folklore way of recovering the secret key in LWE-based schemes. On the other hand, the decryption error can be defined as an information-theoretic quantity. Unlike the security parameter, there is therefore no safety margin needed as there is no danger of a better algorithm being found to lower this quantity.

To make the decryption error an information-theoretic quantity, one should define it as being worst-case when the adversary is even given the secret key [20]. In LWE-based schemes, the message is an additive term in the decryption procedure, and since the message’s coefficients are generally small (normally in $\{0,1\}$), there is no difference between a worst-case and an “average-case” (or even best-case) message. In NTRU, however, as we saw from the decryption equation, we need the quantity $p(\textbf{g}\textbf{r}+\textbf{f}\textbf{m})$ to be smaller than q/2, and $\textbf{m}$ is multiplied by $\textbf{f}$. Purposefully choosing a “bad” $\textbf{m}$ can, therefore, make a large difference (increasing the decryption error by factors larger than $2^{100}$ is normal for standard parameter choices). The naive way to keep the worst-case decryption error small is to increase the modulus q so that encryption errors do not occur. But increasing q weakens the security of the scheme by making the lattice-reduction algorithms more effective.

In this paper, we demonstrate three different ways of handling the decryption error. The first way is a generic transformation $\textsf{ACWC}_0$ from any scheme into one in which the message does not affect the decryption error. Hence the worst-case correctness error of the transformed scheme equals the average-case correctness error of the original scheme. This transformation is most likely folklore, and it is presented in Fig. 5 on page 16. The downside of this transformation is that it increases the ciphertext size by the message length.

The two next manners in which a worst-case decryption error is handled preserves the ciphertext size of the underlying scheme. The transformation $\textsf{ACWC}$ (Fig. 6 on page 18) requires some specific properties of the distribution from which the message is generated. A natural distribution that satisfies this property is having coefficients uniformly-random modulo p. When p is not a power of 2, this distribution is not particularly pleasant to sample with AVX2 optimizations (due to the branching caused by rejection sampling), and so it was proposed in [21] to sample the distribution as a binomial distribution modulo p. Since the binomial distribution is very easy to sample by summing up and subtracting random bits, and because this value modulo p is pretty close to the uniform distribution, this is a more preferable way of sampling the secret coefficients. Still, being required to only sample the message $\textbf{m}$ according to the uniform distribution could be an acceptable compromise. It is an interesting open problem as to whether our transformation can still be proved secure under the same assumptions for a different, more easily sampled, distribution of the message.

Our final way of handling adversarial-generated messages does not involve any transformation, but rather shows how for certain distributions of $\textbf{m}$, the worst-case decryption error is not much worse than the average-case (or best-case), as in LWE-based schemes. Consider the coefficients of $\textbf{m}$ as consisting of a message part $\mu$ and an error part $\epsilon$. One has this implicit split by defining a function $f(\mu ,\epsilon )=\textbf{m}$ in a particular way where $\epsilon$ and $\mu$ are sampled independently. A property that we need from f is that $f(\mu ,\epsilon ) \bmod \, 2=\mu$. Thus if one recovers $\textbf{m}$, one can also recover $\mu$. If we want to choose $\textbf{m}$ according to the binomial distribution (as in e.g. NewHope [3], Kyber [5], or Saber [10]), then f can be a very simple function as described in Lemma 4.1. And of course, we also want the decryption error of this function to be approximately the same for all adversarially-chosen $\mu$. It turns out that because the adversary only gets to set the residue modulo 2 in the binomial distribution, he has no control over the sign of the final output, nor the variance of the conditional distribution. And for this reason, the worst-case error distribution is close to the random one.

A further observation is that if we only need to recover $\mu =\textbf{m}\bmod 2$, then there is no need to set the parameter p large enough so as to be able to recover the entire $\textbf{m}$. In particular, we could just set $p=2$ and the decryption procedure would still work. By decoupling the magnitude of p from the magnitude of the coefficients of $\textbf{m}$, we can set $\textbf{m}$ to be large (which increases the hardness of Ring-LWE), while keeping $p=2$. The value of p has no effect on the hardness of any version of Ring-LWE (since $p\textbf{h}$ is as uniform as just $\textbf{h}$), and based on the state of affairs regarding solving Ring-LWE problems, finding $\textbf{m}\bmod 2$ is as hard as finding $\textbf{m}$. We discuss the complexity of this problem in Sect. 4.3 and present the scheme in Sect. 4.4.

1.3 Proofs in the (Q)ROM

Our two transformations $\textsf{ACWC}_0$ and $\textsf{ACWC}$ are defined relative to random oracles, and have proofs in the ROM that are conceptually very simple. We show that $\textsf{ACWC}_0$ transforms any one-way secure ($\mathsf {OW\text {-}CPA}$) encryption scheme into one that is $\mathsf {IND\text {-}CPA}$ secure, and that $\textsf{ACWC}$ transforms any $\mathsf {OW\text {-}CPA}$ secure encryption scheme into one that is also $\mathsf {OW\text {-}CPA}$ secure. Note that we cannot prove $\mathsf {IND\text {-}CPA}$ security of $\textsf{ACWC}$ since there exist instantiations for which application of $\textsf{ACWC}$ yields a scheme that simply isn’t $\mathsf {IND\text {-}CPA}$ secure.⁴ By working with ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ security,⁵ a slight generalisation of $\mathsf {OW\text {-}CPA}$ security, we can combine the aforementioned transformations with the well-known Fujisaki-Okamoto transformation $\textsf{FO}^{\bot }$ in a way such that we obtain a tight proof for the resulting KEMs.

Since post-quantum security is a central goal of the constructions in this paper, we also prove all our results in the quantum random oracle model (QROM). That is, we show the security even if the adversary can perform queries to the random oracle in superposition between different inputs. The two constructions involving the random oracle are $\textsf{ACWC}_0$ and $\textsf{ACWC}$. We show that $\textsf{ACWC}_0$ transforms a one-way secure ($\mathsf {OW\text {-}CPA}$) encryption scheme into an IND-CPA secure one. This proof is a reasonably straightforward application of the one-way to hiding theorem, O2H [31] in the variant from [4]. (O2H is a common technique used in random oracle proofs for encryption schemes.) The drawback of the use of O2H is that it introduces a square-root in the adversary’s advantage. (That is, if the adversary has $\varepsilon$ advantage against the underlying scheme and it makes q random oracle queries, then it has advantage $O(\sqrt{q^2\varepsilon })$ against the result of the transformation.)

In contrast, security of $\textsf{ACWC}$ does not have an obvious proof using O2H. Instead, we use the measure-and-reprogram technique (M &R) from [11, 13]. This technique was developed for proving the security of the Fiat-Shamir transform. The fact that this technique works here is unexpected for two reasons: First, it was designed specifically with transformations of sigma-protocols (or related structures) into signatures or non-interactive proof systems in mind; transformations of encryption schemes such as $\textsf{ACWC}$ have a very different structure. Second, M &R is a technique for adaptive reprogramming of the random oracle: Its core feature is, on a high level, that we can measure a query that the adversary will use later for its attack (e.g., as part of a forged signature), and sneak in a value of interest $\varTheta$ into the answer to exactly that query (e.g., the challenge in a sigma-protocol). But in our setting, there is no such value of interest $\varTheta$. (We use a random value $\varTheta$ when invoking the M &R theorem because that is technically required, but we would be perfectly happy if the random oracle was not reprogrammed at all.) We thus “misuse” the M &R for a situation where reprogramming is not required in the first place. This raises the interesting open question whether there could be variants of the M &R theorem that only cover the measurement-part of it (without reprogramming) but have tighter parameters and could be used in situations such as ours to produce a tighter reduction.

Furthermore, the use of M &R also leads to better parameters than we got using O2H: The advantage of the adversary against the result of the transformation $\textsf{ACWC}$ is $O(q^2\varepsilon )$, i.e., no square-root is involved. (However, in contrast to $\textsf{ACWC}_0$, we only get one-way security. This is not a limitation of the proof technique, though, but stems from the fact that $\textsf{ACWC}$ does not achieve $\mathsf {IND\text {-}CPA}$ security. But note that in a setting were we only need one-way security, we still do not have a better bound than $\sqrt{q^2\varepsilon }$ for $\textsf{ACWC}_0$; in this case, $\textsf{ACWC}$ gives strictly better security.)

1.4 Concrete Results and Comparison to the State of the Art

Fig. 1.

Overview: How to obtain efficient $\mathsf {IND\text {-}CCA}$-secure KEMs from our NTRU-based PKE schemes. Solid arrows indicate tight reductions in the ROM, dashed arrows indicate non-tight reductions. ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ is a strengthening of standard $\mathsf {OW\text {-}CPA}$ security, where the adversary is allowed to return q many guesses (instead of just one). $\mathsf {PRE\text {-}CPA}$ security stands preimage resistance which in the setting of NTRU is essentially equivalent to $\mathsf {OW\text {-}CPA}$ security.

We now describe the various ways that one can instantiate NTRU using the techniques described in this paper and compare it to other lattice-based schemes. We defined three different ways to instantiate NTRU, with all three approaches being in the same ring and only differing in the secret distributions and the manner in which it is transformed into a scheme with a small “worst-case” decryption error. When working over the ring $\mathbb {Z}_q[X]/(X^d-X^{d/2}+1)$, we will write $\textsf{NTRU}\text {-}\textsf{A}_q^d$ to be the scheme in Fig. 7 which did not require any transformation. By $\textsf{NTRU}\text {-}\textsf{B}_q^d$, we denote the scheme presented in Fig. 9 which is derived from the generic NTRU scheme $\textsf{GenNTRU}$ (Fig. 8) by utilizing the size-preserving transformation from Fig. 6. And by $\textsf{NTRU}\text {-}\textsf{C}_q^d$, we refer to the scheme in Fig. 10 derived from the folklore transformation of the generic NTRU scheme $\textsf{GenNTRU}$ (Fig. 8) in Fig. 5. All of the aforementioned schemes are CPA-secure, and we use the standard FO-transformation from Fig. 4 to create a CCA-KEM. The above is summarized in the overview Fig. 1.

In Table 1, we summarize the “interesting” instantiations of the schemes described in this paper having between 150 and 350 bits of security. We also compare these to other instantiations of NTRU and Module-LWE based schemes in Fig. 2. For a consistent evaluation of security, we used the online LWE hardness estimator [2]. This estimator has undergone some updates since its initial release, but still does not (as of this writing) include some recent cryptanalytic techniques (e.g. [14]) which could lower the security a little bit. Nevertheless, it still provides very meaningful results for comparing between various schemes.

In comparison to NTRU-HRSS, which was a finalist in the NIST standardization process, $\textsf{NTRU}\text {-}\textsf{C}_{2917}^{648}$ is based on an NTRU problem with the same error distribution, and has an approximately equal security level. But due to the fact that we show how to control the worst-case decryption error, the ciphertext/public key sizes are $15\%$ smaller. If one looks at $\textsf{NTRU}\text {-}\textsf{C}^{768}_{3457}$, which has a similar public key/ciphertext size as NTRU-HRSS-701, one sees that the tradeoff for no error vs. $2^{-252}$ error is 30 bits of security, and the difference in security is even larger if one considers the $\textsf{NTRU}\text {-}\textsf{A}$ version. In our opinion, exchanging such a large security margin in return for reducing $2^{-250}$ to 0 in the information-theoretic decryption error term, is not a sensible trade-off. The comparison of our NTRU instantiations to Kyber shows that the two schemes are essentially on the same size/security curve.

We produced a sample implementation of $\textsf{NTRU}\text {-}\textsf{A}_{2917}^{648}$, as it is most similar in security to NTRU-HRSS-701. In Table 3, we compare this scheme to NTRU-HRSS and other highly-efficient lattice-based schemes such as Kyber and NTTRU. The efficiency of our implementation is similar to that of Kyber-512, even though the NTRU variant has about 30 extra bits of security. The efficiency improvement is due to the fact that there is no matrix sampling required in NTRU-based schemes. When compared to NTRU-HRSS-701, there is a clear difference in efficiency, with $\textsf{NTRU}\text {-}\textsf{A}$ being over 15X faster for round-trip ephemeral key exchange. The running time of $\textsf{NTRU}\text {-}\textsf{C}$ should be quite similar, and $\textsf{NTRU}\text {-}\textsf{B}$ will be a little hampered by the more complicated (uniform vs. binomial) error distribution, but should also be close.

Table 1. Parameters for the $\textsf{NTRU}$ schemes $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{A}$, $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{B}$, and $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{C}$ from this paper. All of the variants of the $\textsf{NTRU}$ schemes work over the same ring, with the only difference being the underlying distributions of the secrets and messages, as well as the transformation (if one is necessary) from an instance with worst-case decryption error to one with average-case. The public key and ciphertext are of the same length (except for the ciphertext of $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{C}$, which is 32 bytes larger) and it is reported in bytes. The inertia degree is the smallest degree of the polynomial ring over which one has to perform operations at the bottom of the NTT tree (for efficiency, one may not always want to split down to the smallest possible degree, though). The parameter $\delta$ is the decryption error for a worst-case message (computed via a Pari script), and the security (in the ROM) is obtained using the LWE estimator script [2].

Table 2. Comparison to Existing Work. The Kyber parameters are taken from the Round 3 submission to the NIST PQC Standardization Process. The NTTRU parameters are from [26], and the NTRU-HRSS-701 parameters are from [21], and the NTRU-HRSS-1373 instantiation is from the comments to the NIST PQC mailing list. For consistency of comparing these schemes to those in Table 1, the security of the schemes are computed using the LWE estimator script [2].

Table 3. Number of cycles (on a Skylake machine) for various operations of a CCA-secure KEM. The numbers for Kyber-512 and Kyber-768 are taken from [17, Table 3], which shows an improved implementation of Kyber90’s (i.e. the version using AES and SHA-256 instead of SHAKE) when using prefix hashing and employing an explicit reject in the decapsulation procedure.

While all the parameters in Table 1 are over rings of the form $\mathbb {Z}_q[X]/(X^d-X^{d/2}+1)$, we mention that another interesting instantiation would be a version of $\textsf{NTRU}\text {-}\textsf{A}$ from Fig. 7 with $\eta =\psi _3^d$ over the ring $\mathbb {Z}_{3329}[X]/(X^{512}+1)$. This would have exactly the security of Level 1 Kyber, a decryption error of $2^{-197}$, and public key/ciphertext sizes of 768 bytes. The parameters make it an attractive NIST level 1 candidate. The one difference is that the inertia degree would be 4, which requires one to do inversions and multiplications in degree 4 rings, but we don’t believe that this should cause a noticeable slowdown.

2 Preliminaries

2.1 Notation

If $\mathcal M$ is a finite set and $\psi _\mathcal{M}$ is a distribution on $\mathcal M$, then $m \leftarrow \psi _\mathcal{M}$ samples m from $\mathcal M$ according to $\psi _\mathcal{M}$. We write $m \leftarrow \mathcal M$ to denote sampling according to the uniform distribution. For a random variable X, $H_\infty (X)$ denotes its min-entropy.

For the sake of completeness, we summarise all relevant quantum preliminaries in the full version [16].

2.2 Cryptographic Definitions

Public-Key Encryption. A public-key encryption scheme $\textsf{PKE}= (\textsf{Gen}, \textsf{Enc}, \textsf{Dec})$ consists of three algorithms, a probability distribution $\psi _\mathcal {M}$ on a finite message space $\mathcal {M}$. If no probability distribution is specified we assume $\psi _\mathcal {M}$ to be the uniform distribution. The key generation algorithm $\textsf{KeyGen}$ outputs a key pair $( pk , sk )$, where $pk$ also defines a finite randomness space $\mathcal {R}=\mathcal {R}( pk )$. The encryption algorithm $\textsf{Enc}$, on input $pk$ and a message $m \in \mathcal {M}$, outputs an encryption $c \leftarrow \textsf{Enc}( pk ,m)$ of m under the public key $pk$. If necessary, we make the used randomness of encryption explicit by writing $c := \textsf{Enc}( pk ,m; r)$, where $r \in \mathcal {R}$. By $\psi _\mathcal {R}$ we denote be the distribution of r in $\textsf{Enc}$, which we require to be independent of m. The decryption algorithm $\textsf{Dec}$, on input $sk$ and a ciphertext c, outputs either a message $m = \textsf{Dec}( sk ,c) \in \mathcal {M}$ or a special symbol $\bot \notin \mathcal {M}$ to indicate that c is not a valid ciphertext.

Randomness Recoverability. $\textsf{PKE}$ is randomness recoverable (RR) if there exists an algorithm $\textsf{Recover}$ such that for all $( pk ,sk) \in \textsf{supp}(\textsf{Gen})$ and $m \in \mathcal {M}$, we have that

$$\begin{aligned} \Pr \left[{\forall m' \in \textsf{Preimg}( pk ,c) :\textsf{Enc}( pk , m';\textsf{Recover}( pk ,m', c)) \ne c \mid c \leftarrow \textsf{Enc}( pk ,m)}\right] = 0\, , \end{aligned}$$

where the probability is taken over $c \leftarrow \textsf{Enc}( pk ,m)$ and $\textsf{Preimg}( pk ,c) := \{m \in \mathcal {M}\mid \exists r \in \mathcal {R}:\textsf{Enc}( pk ,m;r) = c \}$. Additionally, we will require that $\textsf{Recover}$ returns $\bot$ if it is run with input $m \not \in \textsf{Preimg}( pk ,c)$.

Correctness Error. $\textsf{PKE}$ has (worst-case) correctness error $\delta$ [20] if

$$\begin{aligned} \mathop {\mathbb {E}}\left[ \max _{m\in \mathcal {M}} \Pr \left[{\textsf{Dec}( sk , \textsf{Enc}( pk ,m)) \ne m}\right] \right] \le \delta \, , \end{aligned}$$

where the expectation is taken over $( pk , sk ) \leftarrow \textsf{Gen}$ and the choice of the random oracles involved (if any). $\textsf{PKE}$ has average-case correctness error $\delta$ relative to distribution $\psi _\mathcal {M}$ over $\mathcal {M}$ if

$$\begin{aligned} \Pr \left[{\textsf{Dec}( sk , \textsf{Enc}( pk ,m)) \ne m}\right] \le \delta \, , \end{aligned}$$

where the probability is taken over $( pk , sk ) \leftarrow \textsf{Gen}$, $m \leftarrow \psi _\mathcal {M}$ and the randomness of $\textsf{Enc}$. This condition is equivalent to

$$\begin{aligned} \mathop {\mathbb {E}}\left[ \Pr \left[{\textsf{Dec}( sk , \textsf{Enc}( pk ,m)) \ne m}\right] \right] \le \delta \, , \end{aligned}$$

where the expectation is taken over $( pk , sk ) \leftarrow \textsf{Gen}$, the choice of the random oracles involved (if any), and $m\leftarrow \psi _\mathcal {M}$.

Spreadness. $\textsf{PKE}$ is weakly $\gamma$-spread [12] if

$$\begin{aligned} \mathop {\mathbb {E}}\left[ \max _{m\in \mathcal {M},c\in \mathcal {C}} \Pr \left[{\textsf{Enc}( pk ,m) = c}\right] \right] \le 2^{-\gamma }\, , \end{aligned}$$

where the probability is taken over the random coins of encryptions and the expectation is taken over $( pk , sk ) \leftarrow \textsf{Gen}$.

Fig. 2.

Left: q-Set One-Wayness game ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ for $\textsf{PKE}$, where $q=1$ is standard $\mathsf {OW\text {-}CPA}$. Middle: Preimage resistance game $\mathsf {PRE\text {-}CPA}$ for $\textsf{PKE}$. Right: game $\mathsf {IND\text {-}CPA}$ for $\textsf{PKE}$ and adversary $\mathcal {A}= (\mathcal {A}_1,\mathcal {A}_2)$.

Security. In the usual one-way game $\mathsf {OW\text {-}CPA}$ for $\textsf{PKE}$, the adversary has to decrypt a ciphertext $c^*$ of a random plaintext $m^* \leftarrow \psi _\mathcal {M}$ by sending one candidate $m'$ back to the challenger, and wins if $m' = m^*$. In the generalized ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ game, the adversary gets to send a set $\mathcal {Q}$ of size at most q and wins if $m^* \in \mathcal {Q}$. The formal definition of ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ is given in Fig. 2 and the advantage function of an adversary $\mathcal {A}$ is

$$\begin{aligned} \textsf{Adv}^{{q}\mathsf {\text {-}OW\text {-}CPA}}_\textsf{PKE}(\mathcal {A}) := \Pr \left[{{{q}\mathsf {\text {-}OW\text {-}CPA}}_\textsf{PKE}^\mathcal {A}\Rightarrow 1}\right]\, . \end{aligned}$$

For $q=1$ one recovers standard $\mathsf {OW\text {-}CPA}$ security, i.e., $\mathsf {OW\text {-}CPA}:= {{1}\mathsf {\text {-}OW\text {-}CPA}}$. We also introduce preimage resistance of $\textsf{PKE}$ by the defining the advantage function of an adversary $\mathcal {A}$ as

$$\begin{aligned} \textsf{Adv}^\mathsf {PRE\text {-}CPA}_\textsf{PKE}(\mathcal {A}) := \Pr \left[{\mathsf {PRE\text {-}CPA}_\textsf{PKE}^\mathcal {A}\Rightarrow 1}\right]\, , \end{aligned}$$

where game $\mathsf {PRE\text {-}CPA}$ is given in Fig. 2.

Finally, we define the $\mathsf {IND\text {-}CPA}$ advantage for an adversary $\mathcal {A}$ as

$$\begin{aligned} \textsf{Adv}_\textsf{PKE}^\mathsf {IND\text {-}CPA}(\mathcal {A}) := \left| \Pr \left[{\mathsf {IND\text {-}CPA}_\textsf{PKE}^\mathcal {A}\Rightarrow 1}\right] - \frac{1}{2} \right| \, , \end{aligned}$$

where the game $\mathsf {IND\text {-}CPA}_\textsf{PKE}^\mathcal {A}$ is defined in Fig. 2.

Lemma 2.1

($\textsf{PKE}\ \mathsf {OW\text {-}CPA}\implies \textsf{PKE}\ {{q}\mathsf {\text {-}OW\text {-}CPA}}$). For any adversary $\mathcal {A}$ against the ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ security of $\textsf{PKE}$, there exists an $\mathsf {OW\text {-}CPA}$ adversary against $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_\textsf{PKE}^{{{q}\mathsf {\text {-}OW\text {-}CPA}}}(\mathcal {A}) \le q\cdot \textsf{Adv}_\textsf{PKE}^{\mathsf {OW\text {-}CPA}}(\mathcal {B})\, . \end{aligned}$$

where the running time of $\mathcal {B}$ is about that of $\mathcal {A}$.

Proof

Sketch. The reduction $\mathcal {B}$ runs the adversary $\mathcal {A}$ on the inputs it got from its $\mathsf {OW\text {-}CPA}$ challenger and obtains the set $\mathcal {Q}$ of size q. It samples $m \leftarrow \mathcal {Q}$ uniformly at random and forwards m to the $\mathsf {OW\text {-}CPA}$ challenger, with probability 1/q it guessed the right one when the solution is contained in $\mathcal {Q}$, thus, the claim follows.

Lemma 2.2

($\textsf{PKE}\ \mathsf {PRE\text {-}CPA}$ and $\textsf{RR}\overset{\textbf{tightly}}{\implies } \textsf{PKE}\ {{q}\mathsf {\text {-}OW\text {-}CPA}}$). If $\textsf{PKE}$ is randomness recoverable, then for any adversary $\mathcal {A}$ against the ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ security of $\textsf{PKE}$, there exists an $\mathsf {PRE\text {-}CPA}$ adversary $\mathcal {B}$ against $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_\textsf{PKE}^{{{q}\mathsf {\text {-}OW\text {-}CPA}}}(\mathcal {A}) \le \textsf{Adv}_\textsf{PKE}^{\mathsf {PRE\text {-}CPA}}(\mathcal {B})\, . \end{aligned}$$

where the running time of $\mathcal {B}$ is about $\textbf{Time}\left( {\mathcal {A}}\right) + q\cdot \left( \textbf{Time}\left( {\textsf{Recover}}\right) +\right. \left. \textbf{Time}\left( {\textsf{Enc}}\right) \right)$.

Proof

The reduction $\mathcal {B}$ forwards to $\mathcal {A}$ the challenge public-key and ciphertext $c^*$ and obtains a set $\mathcal {Q}$. For every $m \in \mathcal {Q}$ it runs $r := \textsf{Recover}( pk , m, c)$ and then runs $\textsf{Enc}( pk , m; r)$ to obtain c. If c equals $c^*$ it returns (m, r) as the solution, otherwise it continues with the search. If no element is found it can return a random $m \leftarrow \mathcal {M}$. Clearly, if $\mathcal {A}$ wins, then so does $\mathcal {B}$. Since the reduction $\mathcal {B}$ runs $\mathcal {A}$ once, and algorithms $\textsf{Recover}$ and $\textsf{Enc}$ at most q many times, the claim follows.

Key-Encapsulation Mechanism. A key encapsulation mechanism $\textsf{KEM}= (\textsf{Gen}, \textsf{Encaps}, \textsf{Decaps})$ consists of three algorithms and a finite key space $\mathcal {K}$ similar to a PKE scheme, but $\textsf{Encaps}$ does not take a message as input. The key generation algorithm $\textsf{Gen}$ outputs a key pair $( pk , sk )$, where $pk$ also defines a finite randomness space $\mathcal {R}=\mathcal {R}( pk )$ as well as a ciphertext space $\mathcal {C}$. The encapsulation algorithm $\textsf{Encaps}$ takes as input a public-key $pk$ and outputs a key encapsulation ciphertext c and a key K, that is $(c,K) \leftarrow \textsf{Encaps}( pk )$. The decapsulation algorithm $\textsf{Decaps}$, on input $sk$ and a ciphertext c, outputs either a key $K = \textsf{Decaps}( sk ,c) \in \mathcal {K}$ or a special symbol $\bot \notin \mathcal {K}$ to indicate that c is not a valid ciphertext. We say $\textsf{KEM}$ has correctness error $\delta$ if

$$ \Pr \left[{\textsf{Decaps}( sk ,c ) =K \mid (c,K) \leftarrow \textsf{Encaps}( pk )}\right] \le \delta \; , $$

where the probability is taken over the randomness in $\textsf{Encaps}$ and $( pk , sk ) \leftarrow \textsf{Gen}$. In terms of $\textsf{KEM}$’s security, we consider the $\mathsf {IND\text {-}CCA}$ advantage function of an adversary $\mathcal {A}$:

$$\begin{aligned} \textsf{Adv}_{\textsf{KEM}}^\mathsf {IND\text {-}CCA}(\mathcal {A}):= & {} \Pr \left[{\mathsf {IND\text {-}CCA}_\textsf{KEM}^\mathcal {A}\Rightarrow 1}\right]-\frac{1}{2} \end{aligned}$$

where game $\mathsf {IND\text {-}CCA}$ is defined in Fig. 3.

Fig. 3.

Game $\mathsf {IND\text {-}CCA}$ for $\textsf{KEM}$

The Fujisaki-Okamoto Transformation with Explicit Reject. To a public-key encryption scheme $\textsf{PKE}= (\textsf{KeyGen}, \textsf{Enc}, \textsf{Dec})$ with message space $\mathcal {M}$ and associated uniform distribution over $\mathcal {M}$, randomness space $\mathcal {R}$, and hash functions $\textsf{H}: \{0,1\}^* \rightarrow \mathcal {R}\times \mathcal {K}$, we associate $\textsf{KEM}:= \textsf{FO}^{\bot }[\textsf{PKE}, \textsf{H}] := (\textsf{KeyGen},\textsf{Encaps},\textsf{Decaps})$. Its constituting algorithms are given in Fig. 4. In [17] it was formally shown that including a short prefix of the public-key into the hash function provably improves the multi-user security of the Fujisaki-Okamoto transform. In this work, for simplicity, we will omit this inclusion and analyze the security in the single-user setting.

Theorem 2.3

(${{q_{\boldsymbol{\textsf{H}}}}\mathsf {\text {-}OW\text {-}CPA}} \ \textbf{of} \ \textsf{PKE}\overset{\boldsymbol{\textsf{ROM}}}{\implies } \mathsf {IND\text {-}CCA}\ \textbf{of}\ \textsf{KEM}$). For any adversary $\mathcal {A}$, making at most ${q_\textsf {D}}$ decapsulation, ${q_\textsf {H}}$ hash queries, against the $\mathsf {IND\text {-}CCA}$ security of $\textsf{KEM}$, there exists an adversary $\mathcal {B}$ against the ${{{q_\textsf {H}}}\mathsf {\text {-}OW\text {-}CPA}}$ security of $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_\textsf{KEM}^\mathsf {IND\text {-}CCA}(\mathcal {A}) \le \textsf{Adv}_\textsf{PKE}^{{{{q_\textsf {H}}}\mathsf {\text {-}OW\text {-}CPA}}}(\mathcal {B}) + {q_\textsf {D}}2^{-\gamma } + {q_\textsf {H}}\delta \, , \end{aligned}$$

where the running time of $\mathcal {B}$ is about that of $\mathcal {A}$.

The proof is very similar to formerly known proofs for FO - after showing how to simulate oracle $\textsf{Decaps}$, we argue that the challenge key cannot be distinguished from random unless the adversary $\mathcal {A}$ queries $\textsf{H}$ on the challenge plaintext. When reducing to plain $\mathsf {OW\text {-}CPA}$ security, a reduction would have to guess, but a reduction to ${{{q_\textsf {H}}}\mathsf {\text {-}OW\text {-}CPA}}$ security can simply keep a list of all of $\mathcal {A}$ queries to $\textsf{H}$ and return this list as the list of plaintext guesses. For the sake of completeness, a full proof is given in the full version [16].

Theorem 2.4

($\mathsf {IND\text {-}CPA}\ \textbf{of} \ \textsf{PKE}\overset{\boldsymbol{\textsf{ROM}}}{\implies } \mathsf {IND\text {-}CCA}\ \textbf{of} \ \textsf{KEM}$ [20] ). For any adversary $\mathcal {A}$, making at most ${q_\textsf {D}}$ decapsulation, ${q_\textsf {H}}$ hash queries, against the $\mathsf {IND\text {-}CCA}$ security of $\textsf{KEM}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {IND\text {-}CPA}$ security of $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_\textsf{KEM}^\mathsf {IND\text {-}CCA}(\mathcal {A}) \le 2\big (\textsf{Adv}_\textsf{PKE}^{\mathsf {IND\text {-}CPA}}(\mathcal {B}) + {q_\textsf {H}}/ \left| \mathcal {M} \right| \big ) + {q_\textsf {D}}2^{-\gamma } + {q_\textsf {H}}\delta \, , \end{aligned}$$

where the running time of $\mathcal {B}$ is about that of $\mathcal {A}$.

Theorem 2.5

($\mathsf {OW\text {-}CPA}\ \textbf{of} \ \textsf{PKE}\overset{\boldsymbol{\textsf{QROM}}}{\implies } \mathsf {IND\text {-}CCA}\ \textbf{of} \ \textsf{KEM}$ [12]). For any quantum adversary $\mathcal {A}$, making at most ${q_\textsf {D}}$ decapsulation, ${q_\textsf {H}}$ (quantum) hash queries, against the $\mathsf {IND\text {-}CCA}$ security of $\textsf{KEM}$, there exists a quantum adversary $\mathcal {B}$ against the $\mathsf {OW\text {-}CPA}$ security of $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_\textsf{KEM}^\mathsf {IND\text {-}CCA}(\mathcal {A}) \le 2q\sqrt{\textsf{Adv}_\textsf{PKE}^\mathsf {OW\text {-}CPA}(\mathcal {B})} + 24q^2\sqrt{\delta } + 24q\sqrt{q{q_\textsf {D}}}\cdot 2^{-\gamma /4}\, . \end{aligned}$$

where $q := 2({q_\textsf {H}}+{q_\textsf {D}})$ and $\textbf{Time}\left( {\mathcal {B}}\right) \approx \textbf{Time}\left( {\mathcal {A}}\right) + \textsf{O}({q_\textsf {H}}\cdot {q_\textsf {D}}\cdot \textbf{Time}\left( {\textsf{Enc}}\right) + q^2)$.

Fig. 4.

Key encapsulation mechanism $\textsf{KEM}= \textsf{FO}^{\bot }[\textsf{PKE}, \textsf{H}]$, obtained from $\textsf{PKE}=(\textsf{KeyGen},\textsf{Enc}, \textsf{Dec})$ with worst-case correctness error.

3 Worst-Case to Average-Case Decryption Error

In this section we introduce two worst-case to average case correctness transform for public-key encryption.

3.1 Simple Transformation $\textsf{ACWC}_0$ with Redundancy

Let $\textsf{PKE}$ be an encryption scheme with small average-case correctness error and $\textsf{F}$ be a random oracle. We first introduce a simple transformation $\textsf{ACWC}_0$ by describing $\textsf{ACWC}_0[\textsf{PKE},\textsf{F}]$ in Fig. 5 which adds $\lambda$ bits of redundancy to the ciphertexts, where $\lambda$ is the size of the message space. The resulting scheme has small worst-case correctness error.

Fig. 5.

$\textsf{ACWC}_0[\textsf{PKE},\textsf{F}]$ transforms $\textsf{PKE}$ with small average-case correctness error, with message space $\mathcal R$ and associated distribution $\psi _\mathcal R$, into $\textsf{PKE}'$ with small worst-case correctness error. The resulting scheme is $\lambda$ bits longer.

Lemma 3.1

If $\textsf{PKE}$ is $\delta$-average-case-correct, then $\textsf{PKE}':= \textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$ is $\delta$-worst-case-correct.

Proof

We need to upper bound $\delta '= \mathbb {E}\max _{m \in \{0,1\}^\lambda } \Pr [\textsf{Dec}'(\textsf{Enc}'(m))\ne m]$, where the expectation is taken over the internal randomness of $\textsf{KeyGen}$ and the choice of random oracle $\textsf{F}$, and the probability is taken over the internal randomness of $\textsf{Enc}'$. Since a ciphertext $(\textsf{Enc}( pk , r), \textsf{F}(r)\oplus m)$ fails to decrypt iff $\textsf{Enc}( pk , r)$ fails to decrypt, and since message r is drawn according to the distribution $\psi _\mathcal R$ on the message space of $\textsf{PKE}$,

$$\begin{aligned} \mathbb {E}\max _{m \in \{0,1\}^\lambda } \Pr [\textsf{Dec}'( sk , \textsf{Enc}'( pk , m))\ne m]&= \mathbb {E}\mathop {\Pr }\limits _{r \leftarrow \psi _\mathcal R} [\textsf{Dec}( sk , \textsf{Enc}( pk , r))\ne r] = \delta . \end{aligned}$$

Lemma 3.2

If $\textsf{PKE}$ is weakly $\gamma$-spread, then so is $\textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$.

Proof

Follows directly by how $\textsf{PKE}$ is used, since the ciphertext of $\textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$ consists of the ciphertext of $\textsf{PKE}$, plus the message blinding part.

Theorem 3.3

(${{q_{\boldsymbol{\textsf{F}}}}\mathsf {\text {-}OW\text {-}CPA}} \ \textbf{of} \ \textsf{PKE}\overset{\textrm{ROM}}{\implies } \mathsf {IND\text {-}CPA}\ \textbf{of} \ \textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$). For any adversary $\mathcal {A}$ against the $\mathsf {IND\text {-}CPA}$ security of $\textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$, issuing at most ${q_\textsf {F}}$ queries to $\textsf{F}$, there exists an adversary $\mathcal {B}$ against the $\mathsf {OW\text {-}CPA}$ security of $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_{\textsf{ACWC}[\textsf{PKE}, \textsf{F}]}^{\mathsf {IND\text {-}CPA}}(\mathcal {A}) \le \textsf{Adv}_{\textsf{PKE}}^{{{{q_\textsf {F}}}\mathsf {\text {-}OW\text {-}CPA}}}(\mathcal {B}) , \end{aligned}$$

and the running time of $\mathcal {B}$ is about that of $\mathcal {A}$.

In the $\mathsf {IND\text {-}CPA}$ game for $\textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$, the challenge ciphertext $c^* \leftarrow \bigl (\textsf{Enc}( pk ,r), \textsf{F}(r)\oplus m_b)$ perfectly hides $m_b$ unless the adversary queries $\textsf{F}$ on r, thus breaking $\mathsf {OW\text {-}CPA}$ security of $\textsf{PKE}$. A reduction to ${{{q_\textsf {F}}}\mathsf {\text {-}OW\text {-}CPA}}$ security can simply keep a list of all of $\mathcal {A}$ queries to $\textsf{F}$ and return this list as the list of plaintext guesses. For the sake of completeness, a full proof of Theorem 3.3 is given in the full version [16].

Theorem 3.4

(${{p_{\boldsymbol{\textsf{F}}}}\mathsf {\text {-}OW\text {-}CPA}} \ \textbf{of} \ \textsf{PKE}\overset{\textrm{QROM}}{\implies } \mathsf {IND\text {-}CPA}\ \textbf{of} \ \textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$). For any quantum adversary $\mathcal {A}$ against the $\mathsf {IND\text {-}CPA}$ security of $\textsf{ACWC}_0[\textsf{PKE}, \textsf{F}]$, with query depth at most ${d_\textsf {F}}$ and query parallelism at most ${p_\textsf {F}}$, there exists a quantum adversary $\mathcal {B}$ against the $\mathsf {OW\text {-}CPA}$ security of $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_{\textsf{ACWC}[\textsf{PKE}, \textsf{F}]}^{\mathsf {IND\text {-}CPA}}(\mathcal {A}) \le 2{d_\textsf {F}}\, \sqrt{ \textsf{Adv}_{\textsf{PKE}}^{{{{p_\textsf {F}}}\mathsf {\text {-}OW\text {-}CPA}}}(\mathcal {B}) }. \end{aligned}$$

and the running time of $\mathcal {B}$ is about that of $\mathcal {A}$.

Since the random oracle is now quantum-accessible, we will use the O2H lemma to argue that we can reprogramm $\textsf{F}$ on r, again with the consequence that $c^*$ now perfectly hides b. In accordance with the definition of the O2H extractor, our reduction will pick one of $\mathcal {A}$’s queries at random, measure this query, and return the measured plaintexts as its guess list. Since the query has query parallelism at most ${p_\textsf {F}}$, the list has at most ${p_\textsf {F}}$ many elements. For the sake of completeness, a full proof of Theorem 3.4 is given in the full version [16].

3.2 Transformation $\textsf{ACWC}$ Without Redundancy

Let $\textsf{PKE}$ be an encryption scheme with small average-case correctness error, and let $\textsf{F}$ be a random oracle. We will now introduce our second transformation $\textsf{ACWC}$ by describing $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$ in Fig. 6. Again, the resulting scheme has a small worst-case correctness error. Instead of adding redundancy to the ciphertexts, however, the scheme makes use of a generalised One-Time Pad $\textsf{GOTP}$.

Definition 3.5

Function $\textsf{GOTP}: \mathcal{X} \times \mathcal{U} \rightarrow \mathcal{Y}$ is called generalized one-time pad (for distributions $\psi _\mathcal X, \psi _\mathcal {Y}, \psi _\mathcal {U}$) if

• 1. Decoding: There exists an efficient inversion algorithm $\textsf{Inv}$ such that for all $x \in \mathcal {X}$, $u \in \mathcal{U}$, $\textsf{Inv}(\textsf{GOTP}(x,u), u) =x$.

• 2. Message-hiding: For all $x \in \mathcal {X}$, the random variable $\textsf{GOTP}(x,u)$, for $u \leftarrow \psi _\mathcal {U}$, has the same distribution as $\psi _\mathcal {Y}$

• 3. Randomness-hiding: For all $u \in \mathcal {U}$, the random variable $\textsf{GOTP}(x,u)$, for $x \leftarrow \psi _{\mathcal X}$, has the same distribution as $\psi _\mathcal {Y}$

A simple example of the generalized one-time pad $\textsf{GOTP}: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ for the uniform distributions is $\textsf{GOTP}(x,u):= x \oplus u$ with inversion algorithm $\textsf{Inv}(y,u):= y \oplus u$. The second and third properties are obviously satisfied since the XOR operation is a one-time pad.

Let $\textsf{PKE}$ be a public-key encryption scheme with $\mathcal {M}= \mathcal {M}_1 \times \mathcal {M}_2$, where $\psi _\mathcal {M}= \psi _{\mathcal {M}_1} \times \psi _{\mathcal {M}_2}$ is a product distribution. Let $\textsf{GOTP}: \mathcal {M}' \times \mathcal{U} \rightarrow \mathcal {M}_2$ be a generalized one-time pad for distribution $\psi _{\mathcal {M}_2}$ and $\textsf{F}: \mathcal {M}_1 \rightarrow \mathcal{U}$ be a random oracle. The associated distributions $\psi _{\mathcal {M}_1},\psi _{\mathcal {M}_2},\psi _{\mathcal {M}'},\psi _\mathcal {U}$ do not necessarily have to be uniform. (If $\psi _\mathcal {U}$ is not uniform, then the distribution of the random oracle $\textsf{F}$ is such that every output is independently $\psi _\mathcal {U}$-distributed.) $\textsf{PKE}'$ obtained by transformation $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$ is described in Fig. 6.

Fig. 6.

$\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$ transforms $\textsf{PKE}$ with small average-case correctness error into $\textsf{PKE}'$ with small worst-case correctness error. The output length of the two schemes is the same.

Our first theorem relates the average-case correctness of $\textsf{PKE}$ to the worst-case correctness of $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$.

Lemma 3.6

Let $\textsf{PKE}$ be a public-key encryption scheme with $\mathcal {M}= \mathcal {M}_1 \times \mathcal {M}_2$, where $\psi _\mathcal {M}= \psi _{\mathcal {M}_1} \times \psi _{\mathcal {M}_2}$ is a product distribution, and let $\Vert \psi _{\mathcal {M}_1} \Vert := \sqrt{\sum \limits _{M_1}\psi _1(M_1)^2}$. Let $\textsf{GOTP}: \mathcal {M}' \times \mathcal{U} \rightarrow \mathcal {M}_2$ be a generalized one-time pad (for distributions $\psi _{\mathcal {M}'},\psi _\mathcal {U},\psi _{\mathcal {M}_2}$) and $\textsf{F}: \mathcal {M}_1 \rightarrow \mathcal{U}$ be a random oracle. If $\textsf{PKE}$ is $\delta$-average-case-correct then $\textsf{PKE}':= \textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$ is $\delta '$ worst-case-correct for

$$\delta '=\delta + \Vert \psi _{\mathcal {M}_1} \Vert \cdot \left( 1+\sqrt{(\ln {|\mathcal {M}'|}-\ln {\Vert \psi _{\mathcal {M}_1}\Vert })/2}\right) .\,\, $$

Proof

For any fixed⁶ key pair, $\delta '( pk , sk )$ can be bounded by an arbitrary $t\in \mathbb {R}^+$, plus the probability that $\delta '( pk , sk )$ exceeds t. To bound the latter, we set as t fixed-pair average-case correctness $\delta ( pk , sk )$, plus $\Vert \psi _{\mathcal {M}_1}\Vert \cdot \sqrt{(c+\ln |\mathcal {M}'|)/2}$, and use helper Lemma 3.7 below. A full proof is given in the full version [16].

Lemma 3.7

Let g be some function and B be some set such that

$$\begin{aligned} \forall m\in \mathcal {M},\mathop {\Pr }\limits _{r_1 \leftarrow \psi _1, r_2 \leftarrow \psi _2, u\leftarrow U}[g(m,r_1, r_2, u)\in B]\le \mu , \end{aligned}$$

(1)

where $\psi _1$ and $\psi _2$ are independent. Let $\textsf{F}$ be a random function mapping onto U. Define $\Vert \psi _1\Vert =\sqrt{\sum _{r_1}\psi _1(r_1)^2}$. Then for all but an $e^{-c}$ fraction of random functions $\textsf{F}$, we have that $\forall m\in \mathcal {M}$,

$$\begin{aligned} \mathop {\Pr }\limits _{r_1\leftarrow \psi _1,r_2\leftarrow \psi _2}[g(m,r_1,r_2,\textsf{F}(r_1))\in B]\le \mu +\Vert \psi _1\Vert \cdot \sqrt{(c+\ln |\mathcal {M}|)/2} \end{aligned}$$

(2)

Proof

We show that for any fixed $m\in \mathcal {M}$, the probability in (2) holds for all but a $e^{-c}\cdot |\mathcal {M}|^{-1}$-fraction of random functions $\textsf{F}$. The claim then follows by the union bound. The full proof is provided in the full version [16].

Lemma 3.8

If $\textsf{PKE}$ is weakly $\gamma$-spread, then so is $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$.

Proof

Follows directly, since the ciphertext consists of the ciphertext of $\textsf{PKE}$.

Theorem 3.9

($({q\cdot }{{q_\textsf {F}}})$-OW-CPA of $\textsf{PKE}\overset{\textrm{ROM}}{\implies } {{q}\mathsf {\text {-}OW\text {-}CPA}}$ of $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP},\textsf{F}]$). Let $q \in \mathbb {N}$. For any adversary $\mathcal {A}$ against the ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ security of $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$, making at most ${q_\textsf {F}}$ random oracle queries, there exists an adversary $\mathcal {B}$ against the ${({{q\cdot }}{{q_\textsf {F}}})\textsf {\text {-}OW\text {-}CPA}}$ security of $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$ with

$$\begin{aligned} \textsf{Adv}_{\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]}^{{{q}\mathsf {\text {-}OW\text {-}CPA}}}(\mathcal {A}) \le \textsf{Adv}_\textsf{PKE}^{{({{q\cdot }}{{q_\textsf {F}}})\textsf {\text {-}OW\text {-}CPA}}}(\mathcal {B})+ q\cdot 2^{-H_\infty (\psi _{\mathcal {M}'})}\, , \end{aligned}$$

where the running time of $\mathcal {B}$ is about $\textbf{Time}\left( {\mathcal {A}}\right) + \mathcal {O}(q\cdot {q_\textsf {F}})$  .

In the ${{q}\mathsf {\text {-}OW\text {-}CPA}}$ game for $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP},\textsf{F}]$, the adversary is presented with an encryption $c^* \leftarrow \textsf{Enc}( pk ,M_1^*\Vert \textsf{GOTP}(m^*, \textsf{F}(M_1^*)))$ of a message pair $(M_1^*, m^*) \leftarrow \psi _{\mathcal {M}_1} \times \psi _{\mathcal {M}'}$, and has to return a list $\mathcal {Q}$ such that $m^* \in \mathcal {Q}$. Unless $\mathcal {A}$ queries $\textsf{F}$ on $M_1^*$, $m^*$ is perfectly hidden from $\mathcal {A}$ and $\mathcal {A}$ cannot win with probability better than $q\cdot 2^{-H_\infty (\psi _{\mathcal {M}'})}$. If $\mathcal {A}$ queries $\textsf{F}$ on $M_1^*$ and wins, a reduction can again record $\mathcal {A}$’s oracle queries, and then use the query list $\mathcal {L}_{\textsf{F}}$ and $\mathcal {A}$’s one-way guessing list $\mathcal {Q}_\mathcal {A}$ to construct its set $\mathcal {Q}$ by going over all possible combinations $M' = M_1' || M_2'$, where $M_1' \in \mathcal {L}_{\textsf{F}}$ and $M_2' := \textsf{GOTP}(m',\textsf{F}(M_1'))$ for $m' \in \mathcal {Q}_\mathcal {A}$. If $\mathcal {A}$ queries $\textsf{F}$ on $M_1^*$ and wins, then $\mathcal {L}_{\textsf{F}}$ will contain the right $M_1^*$, meaning that $\mathcal {B}$’s list $\mathcal {Q}$ will contain the challenge plaintext. Note that the ciphertext for $\mathcal {B}$ would be defined relative to $M_2^* \leftarrow \psi _{\mathcal {M}_2}$, but due to the properties of $\textsf{GOTP}$, $\mathcal {A}$’s one-way game can be conceptually changed such that its ciphertext is also defined relative to $M_2^* \leftarrow \psi _{\mathcal {M}_2}$, and $\mathcal {A}$ wins if it returns a list $\mathcal {Q}$ containing $m := \textsf{Inv}(M_2^*, \textsf{F}(M_1^*))$. For the sake of completeness, a full proof of Theorem 3.9 is given in the full version [16].

Theorem 3.10

($\mathsf {OW\text {-}CPA}$ of $\textsf{PKE}\overset{\textrm{QROM}}{\implies } \mathsf {OW\text {-}CPA}$ of $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$). For any quantum adversary $\mathcal {A}$ against the $\mathsf {OW\text {-}CPA}$ security of $\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]$, making at most ${q_\textsf {F}}$ random oracle queries, there exists a quantum adversary $\mathcal {B}$ against the $\mathsf {OW\text {-}CPA}$ security of $\textsf{PKE}$ with

$$\begin{aligned} \textsf{Adv}_{\textsf{ACWC}[\textsf{PKE}, \textsf{GOTP}, \textsf{F}]}^\mathsf {OW\text {-}CPA}(\mathcal {A}) \le (2{q_\textsf {F}}+1)^2\ \textsf{Adv}_{\textsf{PKE}}^\mathsf {OW\text {-}CPA}(\mathcal {B}), \end{aligned}$$

where the running time of $\mathcal {B}$ is about that of $\mathcal {A}$.

Intuitively, the proof follows the same idea as its classical counterpart. In contrast to the security proof for $\textsf{ACWC}_0$, however, we can not simply apply the O2H lemma, as a reduction needs both a query to $\textsf{F}$ from which it can extract $M_1^*$ and its final output m, and an O2H extractor would simply abort $\mathcal {A}$ once that $\mathcal {A}$ has issued the query to be extracted. We will therefore use the measure-and-reprogram technique (M &R) from [11, 13], arguing that we can run the adversary, measure a random query, and continue running it afterwards to obtain its final output m. For the sake of completeness, a full proof of Theorem 3.10 is given in the full version [16].

4 NTRU Encryption over NTT Friendly Rings

In this section we present three instantiations of the NTRU encryption scheme in polynomial rings of the form $\mathbb {Z}_q[X]/(X^d-X^{d/2}+1)$, where $d=2^i3^j$, where the parameters are set such that multiplication and inversion can be performed very efficiently using the NTT.

4.1 Notation

We denote by $\mathcal {R}$ the polynomial ring $\mathbb {Z}_q[X]/(X^d-X^{d/2}+1)$, where the positive integer d (of the form $2^i3^j$) and the prime q are implicit from context. Elements in $\mathcal {R}$ will be represented by polynomials of degree less than d, and we will denote these polynomials by bold lower-case letters. That is, all elements of $\mathcal {R}$ are of the form $\textbf{h}=\sum \limits _{i=0}^{d-1}\textbf{h}_i X^i \in R$, where $\textbf{h}_i\in \mathbb {Z}_q$. There is a natural correspondence between elements in $\mathcal {R}$ and vectors in $\mathbb {Z}_q^d$, where one simply writes the coefficients of a polynomial in vector form. As additive groups, the two are trivially isomorphic. We will thus sometimes abuse notation and for a vector $\vec v$, write $\textbf{r}:=\vec v$ to mean that the coefficients of the polynomial $\textbf{r}$ are assigned the coefficients of the vector $\vec v$.

For an integer $h\in \mathbb {Z}_q$, we write $h \bmod ^{\pm }q$ to mean the integer from the set $\left\{ -\frac{q-1}{2},\ldots ,\frac{q-1}{2}\right\}$ which is congruent to h modulo q. Reducing an integer modulo 2 always maps it to a bit. These functions naturally extend to vectors and polynomials, where one applies the function individually to each coefficient. For a set S, the function $\textsf{H}_S:\{0,1\}^*\rightarrow S$ denotes a hash function modeled as a random oracle that outputs a uniform distribution on S. Similarly, for a distribution $\psi$ (over some implicit set S), we will write $\textsf{H}_\psi :\{0,1\}^*\rightarrow S$ to denote a hash function modeled as a random oracle that outputs a distribution $\psi$. The function $\textsf{pref}(\cdot )$ extracts a short (around 32-64 byte) prefix from an element of $\mathcal {R}$.

4.2 The Binomial Distribution

For an even k, we define the distribution $\psi _{k}^d$ over $\mathbb {Z}^d$ to be the distribution

$$\begin{aligned} \sum _{i=1}^k\vec a_i-\sum _{i=1}^k\vec b_i,\quad \vec a_i,\vec b_i\leftarrow \{0,1\}^d. \end{aligned}$$

(3)

The distribution $\bar{\psi }_{k}^d$ is the distribution over the set $\{-1,0,1\}^d$ defined as $\psi _{k}^d$ reduced modulo 3. We will mostly be working with $\bar{\psi }_{k}^d$ and $\psi _{k}^d$ for $k=2$, which are, by definition, generated as $\vec b=\vec b_1+\vec b_2-\vec b_3-\vec b_4$ and $\vec b\bmod ^{\pm }\,3$, where $\vec b_i\leftarrow \{0,1\}^d$. Each coefficient of $\vec b$ and $\vec b\bmod ^{\pm }\,3$ is distributed as

(4)

(5)

We now state a lemma, which is used for the construction of $\textsf{NTRU}\text {-}\textsf{A}$ in Fig. 7 that shows that by creating the distribution $\psi _{2}$ in a special way, one of the components of the distribution can be completely recovered when having access to whole sample. Note that this cannot be done if each coefficient is generated as $b=b_1+b_2-b_3-b_4$. For example, if $b=0$, then every $b_i$ has conditional probability of 1/2 of being 0 or 1. If, on the other hand, we generate the distribution as $b=(b_1-2b_2b_3)(1-2b_4)$, where $b_i\leftarrow \{0,1\}$, then one can see that $b_1$ can be recovered by computing $b\mod \,2$.

Lemma 4.1

The distribution $\psi _{2}^d$ can be generated as

$$\vec b=(\vec b_1-2\vec b_2\odot \vec b_3)\odot (1-2\vec b_4),$$

where $\vec b_i\leftarrow \{0,1\}^d$ and $\odot$ denotes component-wise multiplication. Furthermore, $\vec b\bmod 2 = \vec b_1$.

4.3 The NTRU Problem and Variants

In the framework for the NTRU trap-door function [19], the secret key consists of two polynomials $\textbf{f}$ and $\textbf{g}$ with small coefficients in a polynomial ring (e.g. $\mathcal {R}$) and the public key if the quotient $\textbf{h}=\textbf{g}\textbf{f}^{-1}$. The hardness assumption states that given $(\textbf{h},\textbf{h}\textbf{r}+\textbf{e})$, where $\textbf{r},\textbf{e}$ are sampled from some distribution with support of elements in $\mathcal {R}$ with small coefficients, it is hard to recover $\textbf{e}$. For appropriately-set parameters, one can recover $\textbf{e}$ when knowing $\textbf{f}$, and we will discuss this when presenting the full encryption scheme later in the section. For now, we are mainly interested in the security of NTRU.

The security of the NTRU function described above is naturally broken down into two assumptions. The first is that the distribution of $\textbf{h}=\textbf{g}\textbf{f}^{-1}$ is indistinguishable from a random element in $\mathcal {R}$. And the second assumption is essentially the Ring-LWE assumption which states that given $(\textbf{h},\textbf{h}\textbf{r}+\textbf{e})$, where $\textbf{h}$ is uniform in $\mathcal {R}$ and $\textbf{r},\textbf{e}$ are chosen from some distribution with small coefficients, it is hard to find $\textbf{e}$ (and thus also $\textbf{r}$). We point out that one can eliminate the need for the first assumption by choosing polynomials with coefficients that are small, but large enough, so that the quotient is statistically-close to uniform [29], but the resulting scheme ends up being significantly less efficient because the coefficients in the polynomials of the second (Ring-LWE) problem need to be rather small to compensate; and this in turn requires the dimension of the ring to be increased in order for the Ring-LWE problem to remain hard. The below definition formally states the first assumption for the distributions used in this paper.

Definition 4.2

(The $\mathcal {R}$-$\textsf{NTRU}_\eta$ assumption). For a distribution $\eta$ over the ring $\mathcal {R}$ and an integer p relatively-prime to q, the $\mathcal {R}$-$\textsf{NTRU}_\eta$ assumption states that $\textbf{g}\cdot (p\textbf{f}+1)^{-1}$ is indistinguishable from a uniformly-random element in $\mathcal {R}$ when $\textbf{g}$ and $\textbf{f}$ are chosen from the distribution $\eta$, and $p\textbf{f}+1$ is invertible in $\mathcal {R}$.

Another common version of the assumption simply states that $\textbf{g}\cdot \textbf{f}^{-1}$ is indistinguishable from random, and it doesn’t appear that there is any difference in the hardness between the two. The reason that multiplication of $\textbf{f}$ by p is useful is because it eliminates the need for an inversion (which cannot be done using NTT) during the decryption process; and so we use this version of the problem in the paper. The downside of this multiplication by p is that half of the “noise terms” in the decrypted ciphertext increase by a factor of p. We now define the Ring-LWE problem that is specific to our instantiation, and which forms the second assumption needed for the NTRU cryptosystem.

Definition 4.3

($\mathcal {R}\text {-}\textsf{LWE}_{\eta }$). Let $\eta$ be some distribution over $\mathcal {R}$. In the $\mathcal {R}\text {-}\textsf{LWE}$ problem, one is given $(\textbf{h},\textbf{h}\textbf{r}+\textbf{e})$, where $\textbf{h}\leftarrow \mathcal {R}$ and $\textbf{r},\textbf{e}\leftarrow \eta$, and is asked to recover $\textbf{e}$.

One can also define the decision version of the above assumption as

Definition 4.4

(Decision $\mathcal {R}\text {-}\textsf{LWE}_{\eta }$). Let $\eta$ be a distribution over $\mathcal {R}$. The decision $\mathcal {R}\text {-}\textsf{LWE}$ assumption states that $(\textbf{h},\textbf{h}\textbf{r}+\textbf{e})$, where $\textbf{h}\leftarrow \mathcal {R}$ and $\textbf{r},\textbf{e}\leftarrow \eta$, is indistinguishable from $(\textbf{h},\textbf{u})$, where $\textbf{h},\textbf{u}\leftarrow \mathcal {R}$.

In the original $\textsf{LWE}$ definition of Regev [28], the distribution $\eta$ was a rounded continuous Gaussian, as this was the distribution most convenient for achieving a worst-case to average-case reduction from certain lattice problems over solving $\mathcal {R}\text {-}\textsf{LWE}_{\eta }$. When implementing cryptographic primitives based on the hardness of $\mathcal {R}\text {-}\textsf{LWE}_\eta$, it is more convenient to take $\eta$ to be a distribution that can be easily sampled. Some common distributions include uniform (although sometimes it is not that simple to sample) and those that can be generated as sums of Bernoulli random variables such as $\psi _{k}$ and $\bar{\psi }_{k}$ from (4) and (5).

The most efficient known attack against the $\mathcal {R}$-$\textsf{NTRU}$ and $\mathcal {R}\text {-}\textsf{LWE}$ problems are lattice attacks. They work by defining a set

$$\mathcal {L}^\perp _\textbf{c}(\textbf{h})=\{(\textbf{v},\textbf{w})\in \mathbb {Z}[X]/(X^d-X^{d/2}+1)~:~\textbf{h}\textbf{v}+\textbf{w}\equiv \textbf{c}\pmod q\}.$$

When $\textbf{c}=\textbf{0}$, the above set is closed under addition, and therefore forms a lattice. To distinguish the quotient $\textbf{h}=\textbf{g}/\textbf{f}$, where $\textbf{f},\textbf{g}$ have small coefficients, from a uniformly-random $\textbf{h}\in \mathcal {R}$, one can try to find the shortest vector in $\mathcal {L}^\perp _\textbf{0}(\textbf{h})$. If $\textbf{h}$ is random, then a vector of $\ell _2$-norm less than $\varOmega (\sqrt{qd})$ is very unlikely to exist in $\mathcal {L}^\perp _\textbf{c}(\textbf{h})$. On the other hand, if the coefficients of $\textbf{f},\textbf{g}$ are noticeably less than $\sqrt{q}$, then $(\textbf{f},-\textbf{g})\in \mathcal {L}^\perp _\textbf{c}(\textbf{h})$, and so an algorithm that can find a good approximation to the shortest vector should find something of length significantly less than $\varOmega (\sqrt{qd})$.

When $\textbf{c}\ne 0$, $\mathcal {L}^\perp _\textbf{c}(\textbf{h})$ is a shifted lattice and finding the shortest vector in it is known as the Bounded Distance Decoding (BDD) problem. For practical parameters, the complexity of the two problems is identical. Interestingly, when q is very large with respect to the size of the secret coefficients, finding a short vector in $\mathcal {L}^\perp _\textbf{c}(\textbf{h})$ is significantly easier when $\textbf{c}=0$, as opposed to when $\textbf{c}$ is random [1, 8, 15, 22]. This phenomenon prevents the NTRU assumption from being used in scenarios requiring such a large gap (and so one uses Ring-LWE and Module-LWE schemes in those scenarios), such as in Fully-Homomorphic Encryption schemes. This security issue, however, does not seem to extend to the NTRU parameters that are used in practice for public key encryption and signature schemes.

We now define a version of the $\mathcal {R}\text {-}\textsf{LWE}$ problem in which the adversary is not asked to recover the entire vector $\textbf{e}$, but just $\textbf{e}\bmod 2$.

Definition 4.5

($\mathcal {R}\text {-}\textsf{LWE}2_\eta$). Let $\eta$ be a distribution over $\mathcal {R}$. In the $\mathcal {R}\text {-}\textsf{LWE}$ problem, one is given $(\textbf{h},\textbf{h}\textbf{r}+\textbf{e})$, where $\textbf{h}\leftarrow \mathcal {R}$ and $\textbf{r},\textbf{e}\leftarrow \eta$, and is asked to recover $\textbf{e}\bmod 2$.

While we do not have a formal reduction from $\mathcal {R}\text {-}\textsf{LWE}$ to $\mathcal {R}\text {-}\textsf{LWE}2$, based on the state of the art of how Ring-LWE problems are solved, the two are essentially equivalent. We now present two heuristic arguments for the equivalence of $\mathcal {R}\text {-}\textsf{LWE}$ and $\mathcal {R}\text {-}\textsf{LWE}2$.

Suppose that there is an algorithm that solves $\mathcal {R}\text {-}\textsf{LWE}2_\eta$ and we feed it an instance $(\textbf{h},\textbf{h}\textbf{r}+\textbf{e})$ of $\mathcal {R}\text {-}\textsf{LWE}_\eta$. If the $\mathcal {R}\text {-}\textsf{LWE}2_\eta$ solver returns a correct $\textbf{f}\equiv \textbf{e}\pmod 2$, then we can create another instance

$$(2^{-1}\cdot \textbf{h},2^{-1}\textbf{h}\textbf{r}+2^{-1}(\textbf{e}-\textbf{f}))=(\textbf{h}'\textbf{r}+\textbf{e}').$$

Note that $\textbf{h}'$ is still uniformly random and the distribution of $\textbf{e}'$ is now “narrower” than that of the original $\textbf{e}$ – if the coefficients of $\textbf{e}$ were distributed as $\psi _{2}$, then each coefficient of $\textbf{e}'$ has a probability 3/16 of being $\pm 1$ and 10/16 of being 0. Based on the state of the art, a $\mathcal {R}\text {-}\textsf{LWE}$-type problem should be easier with this narrower distribution. So one should be able to call the $\mathcal {R}\text {-}\textsf{LWE}2_\eta$ oracle again, even though the distribution of $\textbf{e}'$ is now different. It’s easy to see now that this procedure will eventually recover the entire polynomial $\textbf{e}$.

Another heuristic argument is based on a slightly-modified version of decision $\mathcal {R}\text {-}\textsf{LWE}$. In particular, if we assume that the decision $\mathcal {R}\text {-}\textsf{LWE}$ problem, in which just the first polynomial coefficient in $\mathbb {Z}_q$ is noiseless, then there is a simple reduction from this problem to $\mathcal {R}\text {-}\textsf{LWE}2_\eta$. In the reduction, we simply add a noise with distribution $\eta$ to the first coefficient, and we decide whether the decision $\mathcal {R}\text {-}\textsf{LWE}$ instance is real or random based on whether or not the answer returned by the $\mathcal {R}\text {-}\textsf{LWE}2_\eta$ oracle matches our added error modulo 2. While the version of the decision $\mathcal {R}\text {-}\textsf{LWE}$ problem where the first integer coefficient has no error is slightly different than usual, the current best-known algorithms would solve the decision problem by solving the search version. And in the search case, the two versions of the problem are equally hard.

The work of Brakerski et al. [7] considers this “First-is-Errorless” version of $\textsf{LWE}$ and shows that it is essentially as hard as the usual version. Boudgoust et al. [6] extend this problem to it’s Module-LWE variant and showed that an even stronger assumption has a (non-tight) reduction from the usual Module-LWE problem. In short, it is very reasonable to assume that the concrete hardness of the $\mathcal {R}\text {-}\textsf{LWE}2_\eta$ problem is the same as that of $\mathcal {R}\text {-}\textsf{LWE}_\eta$.

4.4 $\textsf{NTRU}\text {-}\textsf{A}$: Encryption Based on $\mathcal {R}$-$\textsf{NTRU}$ + $\mathcal {R}\text {-}\textsf{LWE}2$ for $\eta =\psi _{2}^d$

We now give a construction of our first $\mathsf {OW\text {-}CPA}$-secure encryption scheme, $\textsf{NTRU}\text {-}\textsf{A}$, whose hardness is based on the combination of the $\mathcal {R}$-$\textsf{NTRU}_\eta$ + $\mathcal {R}\text {-}\textsf{LWE}2_\eta$ problems for $\eta =\psi _{2}$. The way that this scheme differs from the more usual NTRU constructions is that the secret key does let one recover the entire $\textbf{e}$. This can pose a problem because generally $\textbf{e}$ the message in the $\mathsf {OW\text {-}CPA}$ NTRU scheme, and yet we can only recover a part of it. This is not a $\mathsf {OW\text {-}CPA}$ scheme and we will not be able to obtain a CCA-secure KEM using generic transformations.

We remedy this issue by only making the value $\textbf{e}\bmod 2$ be the message. This requires that for a given random message $\textbf{m}$, the $\textbf{e}$ is generated from the correct distribution (i.e. $\psi _{2}$) with the additional restriction that $\textbf{m}=\textbf{e}\bmod 2$. An interesting aspect of this scheme is that because the message is not the entire $\textbf{e}$, the adversary does not have as much freedom to pick it so as to maximize the decryption error. If the adversary can only pick $\textbf{e}\bmod 2$, it turns out that the worst-case decryption error is quite close to the “best case”. We now proceed to describe the $\mathsf {OW\text {-}CPA}$ scheme in Fig. 7.

Fig. 7.

$\mathsf {OW\text {-}CPA}$ Encryption Scheme $\textsf{NTRU}\text {-}\textsf{A}$ based on the $\mathcal {R}$-$\textsf{NTRU}_{\psi _{2}}$ + $\mathcal {R}\text {-}\textsf{LWE}2_{\psi _{2}}$ problems. Only the procedures $\textsf{Gen1}$ and $\textsf{Gen2}$ are randomized. We include the coins $\rho$ as input for the Encryption algorithm (which will be passed to $\textsf{Gen1}$ and $\textsf{Gen2}$) because these are explicitly used in the CCA transformation. The coins used in the key generation are implicit.

OW-CPA Scheme. The distribution of the coefficients of the secret polynomials used in key generation and encryption $\psi _{2}$ (see (4)) and is produced by the $\textsf{Gen1}()$ algorithm in Fig. 7. As per Lemma 4.1, this distribution can be generated as $b_1+b_2-b_3-b_4$ or, equivalently, as $(b_1-2b_2b_3)(1-2b_4)$, where all the $b_i$ are Bernoulli random variables. The reason the latter distribution is interesting to us is that modulo 2, it is one of the variables that creates it – $b_1$.

The secret key is generated by choosing polynomials $\textbf{f}',\textbf{g}\leftarrow \psi _{2}^d$ and computing $\textbf{f}=2\textbf{f}'+1$. If $\textbf{f}$ is not invertible in $\mathcal {R}$, we restart. Otherwise, the public key is $\textbf{h}=2\textbf{g}\textbf{f}^{-1}$ and the secret key is $\textbf{f}$.

To encrypt a message $\vec m\in \{0,1\}^d$, the encryptor first generates a random polynomial $\textbf{r}\leftarrow \psi _{2}^d$ using the $\textsf{Gen1}()$ procedure. He then needs to choose a polynomial $\textbf{e}$ such that $\textbf{e}\bmod \, 2$ (as a vector) is $\vec {m}$. Furthermore, when $\vec m$ is chosen uniformly at random from $\{0,1\}^d$, the distribution of $\textbf{e}$ should be $\psi _{2}^d$. To create such a distribution, we define $\textbf{e}=\textsf{Gen2}(\vec m)$. By Lemma 4.1, $\textbf{e}$ is distributed according to $\psi _{2}^d$. The ciphertext is $\textbf{c}=\textbf{h}\textbf{r}+\textbf{e}$.

To decrypt the ciphertext $\textbf{c}=\textbf{h}\textbf{r}+\textbf{e}=2\textbf{g}\textbf{r}/\textbf{f}+\textbf{e}$, we multiply it by $\textbf{f}$, centralize it mod q, and then reduce modulo 2 to obtain

$$\begin{aligned} (\textbf{c}\textbf{f}\bmod ^{\pm }q)\bmod 2 = 2\textbf{g}\textbf{r}+\textbf{e}\textbf{f}\bmod 2= 2\textbf{g}\textbf{r}+2\textbf{e}\textbf{f}'+\textbf{e}\bmod 2 \end{aligned}$$

(6)

If all the coefficients of $2\textbf{g}\textbf{r}+2\textbf{e}\textbf{f}'+\textbf{e}$ (as integers) are smaller than q/2, then modulo 2, this value will be exactly $\textbf{e}\bmod \,2$, which is $\vec m$. Since the coefficients of $\textbf{e}$ have absolute value at most 2, in order to have decryption be correct, we need the coefficients of $\textbf{g}\textbf{r}+\textbf{e}\textbf{f}'$ to be less than $q/4-1$. We will now move on to show how to compute this probability.

Decryption Error for a Worst-Case Message. The decryption error of $\textsf{NTRU}\text {-}\textsf{A}$ can be computed following the template given in [26, Section 3.2]. As discussed above, if a coefficient of $\textbf{g}\textbf{r}+\textbf{e}\textbf{f}'$ (as an integer) has absolute value less than $q/4-1$, then the output of that coefficient in (6) will be $\textbf{e}\bmod \, 2$, as desired. So we now need to understand what each coefficient of $\textbf{g}\textbf{r}+\textbf{e}\textbf{f}'$ looks like. This is easiest to see via an example of how polynomial multiplication in the ring $\mathcal {R}$ can be represented by a matrix-vector product. If we, for example, want to multiply two polynomials $\textbf{a}\textbf{b}$ in the ring $\mathbb {Z}_q[X]/(X^6-X^3+1)$, where $\textbf{a}=\sum \limits _{i=0}^{5}\textbf{a}_i$ and $\textbf{b}=\sum \limits _{i=0}^{5}\textbf{b}_i$ then their product $\textbf{c}=\sum \limits _{i=0}^{5}\textbf{c}_i$ can be written as in (7).

$$\begin{aligned} \begin{bmatrix} \textbf{a}_0 \quad &{} -\textbf{a}_5 \quad &{} -\textbf{a}_4 \quad &{} -\textbf{a}_3 \quad &{} -\textbf{a}_2-\textbf{a}_5 \quad &{} -\textbf{a}_1-\textbf{a}_4 \\ \textbf{a}_1 \quad &{} \textbf{a}_0 \quad &{} -\textbf{a}_5 \quad &{} -\textbf{a}_4 \quad &{} -\textbf{a}_3 \quad &{} -\textbf{a}_2-\textbf{a}_5\\ \textbf{a}_2 \quad &{} \textbf{a}_1 \quad &{} \textbf{a}_0 \quad &{} -\textbf{a}_5 \quad &{} -\textbf{a}_4 \quad &{} -\textbf{a}_3\\ \textbf{a}_3 \quad &{} \textbf{a}_2+\textbf{a}_5 \quad &{} \textbf{a}_1+\textbf{a}_4 \quad &{} \textbf{a}_0+\textbf{a}_3 \quad &{} \textbf{a}_2 \quad &{} \textbf{a}_1\\ \textbf{a}_4 \quad &{} \textbf{a}_3 \quad &{} \textbf{a}_2+\textbf{a}_5 \quad &{} \textbf{a}_1+\textbf{a}_4 \quad &{} \textbf{a}_0+\textbf{a}_3 \quad &{} \textbf{a}_2\\ \textbf{a}_5 \quad &{} \textbf{a}_4 \quad &{} \textbf{a}_3 \quad &{} \textbf{a}_2+\textbf{a}_5 \quad &{} \textbf{a}_1+\textbf{a}_4 \quad &{} \textbf{a}_0+\textbf{a}_3 \end{bmatrix}\cdot \begin{bmatrix} \textbf{b}_0 \\ \textbf{b}_1 \\ \textbf{b}_2 \\ \textbf{b}_3 \\ \textbf{b}_4 \\ \textbf{b}_5\end{bmatrix} = \begin{bmatrix} \textbf{c}_0\\ \textbf{c}_1\\ \textbf{c}_2 \\ \textbf{c}_3\\ \textbf{c}_4\\ \textbf{c}_5\end{bmatrix} \end{aligned}$$

(7)

Notice that $\textbf{c}_3,\textbf{c}_4,$ and $\textbf{c}_5$ are a sum of three independently-generated integers of the form

$$\begin{aligned} c=ba+b'(a+a'). \end{aligned}$$

(8)

The coefficient $\textbf{c}_2$, however, is simply a sum of 6 independent random variables of the form ab. Or to make it look similar to (8), we can think of it as the sum of three random variables of the form

$$\begin{aligned} c=ba+b'a'. \end{aligned}$$

(9)

It should be clear that the distribution of (8) is wider than that of (9), and so the probability that the coefficients which follow the former distribution will be outside of the “safe zone” is larger. The coefficients $\textbf{c}_0$ and $\textbf{c}_1$ are a hybrid of these two distributions. For example, $\textbf{c}_1$ is the sum of one coefficient from (8) and two from (9); while $\textbf{c}_2$ is the sum of two from (8) and one from (9).

To bound the probability that decryption will be correct, we should therefore bound the distribution of $\textbf{c}_3,\textbf{c}_4,\textbf{c}_5$, or in the general case, a coefficient in the bottom half of $\textbf{c}$ and then apply the union bound. So the widest distribution will consist of sums of d/2 random variables having the distribution as in (8). The term $\textbf{g}\textbf{r}$ in (6) has this exact distribution, where each coefficient of $\textbf{g},\textbf{r}$ is distributed according to $\textsf{Gen1}()$.

The term $\textbf{f}'\textbf{e}$ is distributed differently because in our security proof we need to consider an adversarially-chosen message $\vec m$, after the adversary sees the public key. Because the adversary does not get to choose the whole message, but just the modulo 2 residue, it turns out that the failure probability for a worst-case message is not too different than for a uniformly random one. In (10), we give the distribution of a particular coefficient of $\textbf{e}_i$ conditioned on the message bit being either 0 or 1.

(10)

One can see that in both cases the distribution is centered around 0 and has variance 1, and so one should not expect a very large difference in the decryption error. Experimentally, it turns out that the worst-case messages occur when choosing $\vec m=\vec 0$. Furthermore, the worst-case message is the same for any secret key.⁷ This implies that the worst-case correctness error is the average-case one where the distribution over the coefficients of $\textbf{e}$ is as in $\textsf{Gen}2(0)$ of (10). As in [3, 5, 26], the error probability reported in Table 1 is computed via polynomial multiplications which represent convolutions of random variables.

IND-CCA-Secure KEM. One can apply the Fujisaki-Okamoto transformation $\textsf{FO}^{\bot }$ from Fig. 4 to obtain the IND-CCA secure version $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{A}:= \textsf{FO}^{\bot }[\textsf{NTRU}\text {-}\textsf{A}, \textsf{H}]$ of $\textsf{NTRU}\text {-}\textsf{A}$. The concrete security bounds on the $\mathsf {IND\text {-}CCA}$ security of $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{A}$ from Table 4 can be derived in the ROM using Lemma 2.1 and Theorem 2.3 and in the QROM using Theorem 2.5.

Table 4. Bounds on the $\mathsf {IND\text {-}CCA}$ secure NTRU-variants $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{A}$, $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{B}$, and $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{C}$. Constants and negligible terms are suppressed for simplicity. The value q is the sum of all adversarial (random oracle and decryption) queries, i.e., $q = {q_\textsf {H}}+ {q_\textsf {D}}+{q_\textsf {F}}$. The $\varepsilon$ values are the advantage functions of the underlying NTRU assumptions: $\varepsilon _A = \textsf{Adv}^{\mathcal {R}\text {-}\textsf{NTRU}_\eta } +\textsf{Adv}^{\mathcal {R}\text {-}\textsf{LWE}2_\eta }$ for $\eta =\psi _{2}^d$; $\varepsilon _B = \textsf{Adv}^{\mathcal {R}\text {-}\textsf{NTRU}_\eta }+\textsf{Adv}^{\mathcal {R}\text {-}\textsf{LWE}_\eta }$ for $\eta = U_{3}^d$ and $\varepsilon _C = \textsf{Adv}^{\mathcal {R}\text {-}\textsf{NTRU}_\eta }+\textsf{Adv}^{\mathcal {R}\text {-}\textsf{LWE}_\eta }$ for $\eta =\bar{\psi }_{2}^d$.

4.5 Generic NTRU Encryption and Error-Reducing Transformations

Figure 8 defines $\textsf{GenNTRU}[\eta ]$ relative to distribution $\eta$ over $\mathcal {R}$. Note that $\textsf{GenNTRU}[\eta ]$ is randomness-recoverable (RR) because once we have $\textbf{e}$ and $\textbf{c}=\textbf{h}\textbf{r}+\textbf{e}$, we can compute $\textbf{r}=(\textbf{c}-\textbf{e})\cdot \textbf{h}^{-1}$. Because we checked that $\textbf{g}$ is invertible, it holds that $\textbf{h}=3\textbf{g}\textbf{f}^{-1}$ also has an inverse.

Fig. 8.

Generic NTRU $\textsf{GenNTRU}[\eta ]$ relative to distribution $\psi$ over ring $\mathcal {R}$ with average-case correctness error. During key-generation, we need to check that $\textbf{g}$ is invertible in order to have the randomness recovery property. It seems doubtful that this check adds any actual security in practice, but for all parameter sets, it only adds less than $0.01\%$ chance to a restart, so it does not make much difference either way.

By the definition, the $\mathsf {OW\text {-}CPA}$ security of $\textsf{GenNTRU}[\eta ]$ is implied by the $\mathcal {R}$-$\textsf{NTRU}_\eta$+$\mathcal {R}\text {-}\textsf{LWE}_\eta$ assumptions. In this subsection, we will consider two concrete instantiations of $\textsf{GenNTRU}$, namely $\textsf{GenNTRU}[U_{3}]$, where $U_{3}$ is the uniform distribution over $\{-1,0,1\}^d$, and $\textsf{GenNTRU}[\bar{\psi }_{2}^d]$, where $\bar{\psi }_{2}^d$ was defined in Sect. 4.2. Both schemes do not have sufficiently small worst-case correctness error, which is the reason why we will first apply one of our average-case to worst-case correctness error transformations from the last section.

NTRU-B: Encryption Based on $\boldsymbol{\mathcal {R}}$-$\boldsymbol{\textsf{NTRU}_\eta }$+$\boldsymbol{\mathcal {R}\text {-}\textsf{LWE}_\eta }$ for $\boldsymbol{\eta =U_{3}^d}$. We define the generalized one-time pad $\textsf{GOTP}: \mathcal {R}\times \mathcal {R}\rightarrow \mathcal {R}$ relative to distributions $U_{3}^d$ as $\textsf{GOTP}(\vec {m}, u):=\vec m + u \bmod ^{\pm }\,3$. Then $\textsf{NTRU}\text {-}\textsf{B}:= \textsf{ACWC}[\textsf{GenNTRU}[U_{3}^d], \textsf{GOTP}, \textsf{F}]$, obtained by applying the $\textsf{ACWC}$ transformation from Sect. 3.2 to $\textsf{GenNTRU}[U_{3}^d]$, is described in Fig. 9. Its message space is $\mathcal {M}' = \{-1,0,1\}^{\lambda }$ with distribution $U_{3}^d$, where $\mathcal {M}_1 = \{-1,0,1\}^{d-\lambda }$ and $\mathcal {M}_2 = \{-1,0,1\}^{\lambda }$.

Fig. 9.

Randomness-recoverable $\mathsf {OW\text {-}CPA}$ encryption scheme $\textsf{NTRU}\text {-}\textsf{B}$ with worst-case correctness error based on the $\mathcal {R}$-$\textsf{NTRU}_{U_{3}^d}$ + $\mathcal {R}\text {-}\textsf{LWE}_{U_{3}^d}$ problems for $U_{3}^d$ being uniform over $\{-1,0,1\}^d$.

By Lemma 3.6, the average-case correctness error of $\textsf{GenNTRU}[U_{3}^d]$ and the worst-case correctness error of $\textsf{NTRU}\text {-}\textsf{B}$ are off by an additive factor of

$$\varDelta =\Vert U_{3}^{d-\lambda } \Vert \cdot \left( 1+\sqrt{(\ln {|\mathcal {M}'|}-\ln {\Vert U_{3}^{d-\lambda }\Vert })/2}\right) \approx \Vert U_{3}^{d-\lambda } \Vert = 3^{-(d-\lambda )/2} \approx 2^{-0.8 \times (d-\lambda )}$$

which can be neglected for $\lambda =256$ and $d \ge 576$. Hence, for all practical parameters considered in Table 1, worst-case and average-case correctness errors are equal. Using the techniques Sect. 4.4 it can be verified that the error probabilities reported in Table 1 are correct for $\textsf{NTRU}\text {-}\textsf{B}$.

Finally, one can apply the Fujisaki-Okamoto transformation $\textsf{FO}^{\bot }$ from Fig. 4 to obtain the IND-CCA secure version $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{B}:= \textsf{FO}^{\bot }[\textsf{NTRU}\text {-}\textsf{B}, \textsf{H}]$ of $\textsf{NTRU}\text {-}\textsf{B}$. In the ROM, the concrete security bound on the $\mathsf {IND\text {-}CCA}$ security of $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{B}$ from Table 4 can be derived by combining Lemma 2.2 with Theorems 3.9 and 2.3. We refer to Fig. 1 for an overview of the implications. In the QROM, the bound can be derived by combining Theorem 3.10 with Theorem 2.5.

NTRU-C: Encryption Based on $\boldsymbol{\mathcal {R}}$-$\boldsymbol{\textsf{NTRU}_\eta }$+$\boldsymbol{\mathcal {R}\text {-}\textsf{LWE}_\eta }$ for $\boldsymbol{\eta =\bar{\psi }_{2}^d}$. We define $\textsf{NTRU}\text {-}\textsf{C}:= \textsf{ACWC}_0[\textsf{GenNTRU}[\bar{\psi }_{2}^d], \textsf{F}]$ with uniform message space $\mathcal {M}' = \{0,1\}^{\lambda }$, obtained by applying the $\textsf{ACWC}_0$ transformation with redundancy from Sect. 3.1 to $\textsf{GenNTRU}[\bar{\psi }_{2}^d]$ is described in Fig. 10. By Lemma 3.1, the average-case correctness error of $\textsf{GenNTRU}[\bar{\psi }_{2}^d]$ and the worst-case correctness error of $\textsf{NTRU}\text {-}\textsf{C}$ are identical. Using the techniques Sect. 4.4 it can be verified that the error probabilities reported in Table 1 are correct for $\textsf{NTRU}\text {-}\textsf{C}$. Finally, one can apply the Fujisaki-Okamoto transformation $\textsf{FO}^{\bot }$ from Fig. 4 to obtain the IND-CCA secure version $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{C}:= \textsf{FO}^{\bot }[\textsf{NTRU}\text {-}\textsf{C}, \textsf{H}]$ of $\textsf{NTRU}\text {-}\textsf{C}$. In the ROM, the concrete security bound on the $\mathsf {IND\text {-}CCA}$ security of $\textsf{CCA}\text {-}\textsf{NTRU}\text {-}\textsf{C}$ from Table 4 can be derived by combining Lemma 2.2 with Theorems 3.3 and 2.4. In the QROM, the bound can be derived by combining Lemma 2.2 with Theorem 3.4 and Theorem 2.5.

Fig. 10.

$\textsf{NTRU}\text {-}\textsf{C}$: a randomness-recoverable $\mathsf {OW\text {-}CPA}$ encryption scheme with worst-case correctness error based on the $\mathcal {R}$-$\textsf{NTRU}_\eta$ + $\mathcal {R}\text {-}\textsf{LWE}_\eta$ problems for $\eta =\bar{\psi }_{2}^d$.