D-NTRU (Wang, Lei and Hu, Information Sciences 438, 2018) is a "double" variant of the NTRU public-key cryptosystem that combines twin-prime moduli q1q_1 and q2=q1+2q_2=q_1+2 via the Chinese Remainder Theorem, cutting NTRU's ciphertext expansion to roughly 2:12:1 (a factor 2.52.5–2.82.8 smaller than NTRU at the same parameter sets) and speeding up encryption by roughly 2.22.2–2.82.8, with an IND-CPA proof in the standard model that reduces only to the average-case NTRU one-wayness assumption. The source paper leaves open whether D-NTRU, or a closely related variant, can be anchored to worst-case lattice hardness — as the wide-key variants pNE and NTRUCCA are — while keeping this efficiency. Later work gives worst-case reductions only for non-practical NTRU problem variants (Pellet-Mary–Stehlé 2021; Felderhoff, Pellet-Mary, Stehlé 2022) and IND-CCA2 security for D-NTRU-based encryption only in the random oracle model (Seyhan–Akleylek 2023); no worst-case-to-average-case reduction is known for the practical-parameter decision NTRU problem underlying D-NTRU.

Background

NTRU, introduced by Hoffstein, Pipher and Silverman in 1998, is a fast public-key encryption scheme defined over the truncated polynomial ring R=Z[X]/(XN−1)\mathbf{R}=\mathbb{Z}[X]/(X^N-1). Its public key has the form h=p⊗fq−1⊗g mod qh=p\otimes f_q^{-1}\otimes g\bmod q, where ⊗\otimes denotes multiplication in R\mathbf{R}, pp is a small modulus (typically 33), qq is a larger coprime modulus (hundreds), and f,gf,g are sparse ternary polynomials — polynomials whose coefficients lie in {−1,0,1}\{-1,0,1\} with prescribed numbers of 11s and −1-1s. Encryption masks the message with a random sparse polynomial; decryption multiplies by ff, which cancels the mask, and reduces modulo pp. Recovering ff and gg from hh amounts to finding an exceptionally short vector in the rank-2 module {(x,y)∈R2:x⊗h≡y(modq)}\{(x,y)\in\mathbf{R}^2 : x\otimes h\equiv y \pmod q\}, the "NTRU lattice"; the assumed hardness of this average-case task is the NTRU one-wayness assumption.

Provable security for encryption is graded by attack model and by the strength of the underlying assumption. IND-CPA (indistinguishability under chosen-plaintext attack) and IND-CCA (under chosen-ciphertext attack) are the standard confidentiality notions; proofs may hold in the standard model (no idealized assumptions) or only in the random oracle model (ROM), where hash functions are modeled as truly random functions. A worst-case-to-average-case reduction is the strongest known form of security evidence: it shows that any efficient attacker on the scheme (an average-case problem) yields an algorithm for a worst-case lattice problem such as approximating the Shortest Vector Problem (SVP) — over general lattices for LWE-based schemes, or over ideal lattices (lattices arising from ideals of number rings, the structured lattices produced by polynomial-ring cryptography) for ring-based schemes. As surveyed by Peikert (2016), LWE-based schemes enjoy such reductions, but NTRU at its practical parameters does not: its security rests directly on cryptanalysis of an average-case assumption. Peikert's survey explicitly posed the question of whether any NTRU-like problem admits a worst-case hardness reduction.

Partial positive answers exist only in an impractical parameter regime. Stehlé and Steinfeld (EUROCRYPT 2011) defined a variant, denoted pNE, that is IND-CPA secure under worst-case problems over ideal lattices — but the proof forces the secret keys to be sampled by rejection from discrete Gaussians whose width exceeds the smoothing bound — the Gaussian width above which discrete Gaussian samples become statistically close to uniform modulo the underlying lattice, so that the public key becomes statistically close to uniform — together with a large modulus; Cabarcas, Weiden and Buchmann (PQCrypto 2014) benchmarked pNE and confirmed the resulting keys and ciphertexts are far larger and slower than practical NTRU. Yu, Xu and Wang (PKC 2017) extended the worst-case guarantee to prime cyclotomic rings, in the same wide-key regime. Steinfeld, Ling, Pieprzyk, Tartary and Wang (PKC 2012) then lifted pNE to IND-CCA2 security in the standard model under the same worst-case ideal-lattice assumptions, at only a constant-factor overhead over pNE, via lossy trapdoor functions (functions that statistically compress their input and can be inverted only with a secret trapdoor); this scheme, NTRUCCA, shows that worst-case anchoring and standard-model CCA are simultaneously achievable in principle — but only at pNE's impractical cost.

Against this backdrop, Wang, Lei and Hu (2018) proposed D-NTRU, which trades a different commodity: it keeps NTRU-style sparse ternary keys and accepts an average-case-only security proof in exchange for much better communication efficiency. The public key is a pair (h1,h2)(h_1,h_2) where h1=p⊗fq1−1⊗g mod q1h_1=p\otimes f_{q_1}^{-1}\otimes g\bmod q_1 is an NTRU-style component over the prime q1q_1 and h2h_2 is a uniform mask over the twin prime q2=q1+2q_2=q_1+2; a ciphertext is a pair (⟨h1⊗r1+r2⟩q1,⟨h2⊗r1+r2⟩q2)(\langle h_1\otimes r_1+r_2\rangle_{q_1},\langle h_2\otimes r_1+r_2\rangle_{q_2}) with r1r_1 sparse ternary and r2r_2 message-bearing. The ciphertext expansion ratio is ρD=1+log⁡q2q1≈2:1\rho_D=1+\log_{q_2}q_1\approx 2:1, a factor 2.52.5–2.82.8 smaller than NTRU's; the paper reports asymptotic and empirical encryption speedups of roughly 2.22.2–2.82.8 and decryption speedups of 1.31.3–1.91.9 over NTRU at three practical parameter sets (N=157,223,349N=157,223,349 with (q1,q2)=(269,271)(q_1,q_2)=(269,271) or (521,523)(521,523)). The IND-CPA proof proceeds in the standard model through a chain of polynomial-time equivalences — NTRU one-wayness, an intermediate variant C-NTRU's one-wayness, its ciphertext-distribution decision problem, and finally the D-NTRU distribution decision problem — so security reduces to the average-case NTRU one-wayness assumption. Correctness is guaranteed by a sufficient criterion: no decryption failure can occur whenever q1>δq_1>\delta with δ=2(pmin⁡{2dg−1,2d}+2df−1)\delta=2(p\min\{2d_g-1,2d\}+2d_f-1) for the sparsity parameters df,dg,dd_f,d_g,d; and key generation enforces a norm condition on the key pair (Fact 1 of the paper) by rejection sampling. The open question is what it would take to place this efficiency profile on a worst-case foundation.

Problem Statement

The source question, from Wang, Lei and Hu (2018): D-NTRU's IND-CPA security is proved, in the standard model, only relative to the average-case NTRU one-wayness assumption. The objective is to determine whether D-NTRU, or a closely related NTRU variant — by which is meant a construction that retains NTRU-style sparse ternary keys and twin-prime moduli combined via the Chinese Remainder Theorem in a rank-2 module lattice — admits a worst-case-to-average-case reduction — a proof that any efficient adversary against the average-case problem underlying the scheme's security implies an efficient algorithm for a standard worst-case lattice problem over ideal lattices (such as approximate SVP), analogous to the reductions for pNE and NTRUCCA — while maintaining the efficiency that motivates D-NTRU: compact NTRU-style keys (public-key size within a constant factor of practical NTRU — at most 3×3\times at the stated parameter sets, rather than the quadratically larger keys of pNE and NTRUCCA), ciphertext expansion ratio at most 2.1:12.1:1 at twin-prime moduli, and encryption and decryption throughput at least 0.9×0.9\times that of practical NTRU at the stated parameter sets. Constructions outside this class, or that attain the reduction only at key size, ciphertext expansion, or throughput outside the bounds above, do not resolve the question.

References

  1. Baocang Wang, Hao Lei, Yupu Hu, 'D-NTRU: More efficient and average-case IND-CPA secure NTRU variant', Information Sciences 438 (2018) 15–31. DOI: 10.1016/j.ins.2018.01.037, https://doi.org/10.1016/j.ins.2018.01.037 (source paper)
  2. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, 'NTRU: A ring-based public key cryptosystem', Algorithmic Number Theory (ANTS-III), LNCS 1423, 1998, pp. 267–288. DOI: 10.1007/BFb0054868, https://doi.org/10.1007/BFb0054868
  3. Damien Stehlé, Ron Steinfeld, 'Making NTRU as Secure as Worst-Case Problems over Ideal Lattices', Advances in Cryptology – EUROCRYPT 2011. DOI: 10.1007/978-3-642-20465-4_4, https://doi.org/10.1007/978-3-642-20465-4_4
  4. Ron Steinfeld, San Ling, Josef Pieprzyk, Christophe Tartary, Huaxiong Wang, 'NTRUCCA: How to Strengthen NTRUEncrypt to Chosen-Ciphertext Security in the Standard Model', Public Key Cryptography – PKC 2012. DOI: 10.1007/978-3-642-30057-8_21, https://doi.org/10.1007/978-3-642-30057-8_21
  5. Daniel Cabarcas, Patrick Weiden, Johannes Buchmann, 'On the Efficiency of Provably Secure NTRU', Post-Quantum Cryptography – PQCrypto 2014. DOI: 10.1007/978-3-319-11659-4_2, https://doi.org/10.1007/978-3-319-11659-4_2
  6. Yang Yu, Guangwu Xu, Xiaoyun Wang, 'Provably Secure NTRU Instances over Prime Cyclotomic Rings', Public-Key Cryptography – PKC 2017. DOI: 10.1007/978-3-662-54365-8_17, https://doi.org/10.1007/978-3-662-54365-8_17
  7. Chris Peikert, 'A Decade of Lattice Cryptography', Foundations and Trends in Theoretical Computer Science 10(4), 2016. DOI: 10.1561/0400000074, https://doi.org/10.1561/0400000074
  8. Alice Pellet-Mary, Damien Stehlé, 'On the hardness of the NTRU problem', Advances in Cryptology – ASIACRYPT 2021, LNCS 13093, pp. 3–35. DOI: 10.1007/978-3-030-92062-3_1, https://doi.org/10.1007/978-3-030-92062-3_1; IACR ePrint 2021/821, https://eprint.iacr.org/2021/821
  9. Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, 'On Module Unique-SVP and NTRU', Advances in Cryptology – ASIACRYPT 2022, LNCS 13694, pp. 709–740. DOI: 10.1007/978-3-031-22969-5_24, https://doi.org/10.1007/978-3-031-22969-5_24; IACR ePrint 2022/1203, https://eprint.iacr.org/2022/1203
  10. Kübra Seyhan, Sedat Akleylek, 'Indistinguishability under adaptive chosen-ciphertext attack secure double-NTRU-based key encapsulation mechanism', PeerJ Computer Science 9:e1391, 2023. DOI: 10.7717/peerj-cs.1391, https://doi.org/10.7717/peerj-cs.1391
  11. Zhichuang Liang, Boyue Fang, Jieyu Zheng, Yunlei Zhao, 'Compact and Efficient KEMs over NTRU Lattices', 2022. arXiv:2205.05413, https://arxiv.org/abs/2205.05413
  12. Sidoine Djimnaibeye, Djiby Sow, Mahamat Borgou Hassan, 'A Torus-Structured Generalisation of NTRU: the NTC Assumption, its Cryptanalysis, and a Compact KEM', 2026. IACR ePrint 2026/1642, https://eprint.iacr.org/2026/1642