HM-LWE v3.0

In the paper's words

Hidden-modulus LWE: novel hardness assumption

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. The hidden-modulus advantage is a multiplicative factor of approximately $2^{248}$ — equivalent to adding approximately 248 bits of effective key entropy. [my conjecture] Alternative strategy (direct lattice without $p$): Without $p$, the adversary faces a simultaneous Diophantine approximation problem: given $b_i = \langle a_i, s \rangle - q_i \cdot p + e_i$ where $q_i = \lfloor \langle a_i, s \rangle / p \rfloor$ are unknown integers, find $s$ and $p$ such that all residuals are small.

   from 4.2. Hidden-Modulus Advantage: Multiplicative Factor

2. Metric N-SRE-128 (n=512) Kyber-1024 Factor Decapsulate (C, est.) ~530 ms 0.03 ms 17,700× Encapsulate (C, est.) ~250 ms 0.03 ms 8,300× KeyGen <1 ms 0.025 ms ~40× Ciphertext ~25 KB 1.6 KB 16× Security assumption HM-LWE (novel) MLWE (standardized) — Decapsulation dominates at $O(n^3)$ due to Gaussian elimination over $\mathbb{Z}_p$.

   from 6.2. Efficiency Characterization

3. Efficiency is honestly characterized: the scheme is approximately four orders of magnitude slower than Kyber-1024 and has 16× larger ciphertexts.

   from 8.1. Summary

4. We present N-SRE-LWE, a key encapsulation mechanism built on HM-LWE, prove its IND-CPA security via a KEM+DEM hybrid argument, and provide a reference implementation with experimental verification at toy scale (100% correctness across 500 random messages).

   from Abstract

5. At deployment parameters ($n = 512$, 256-bit $p$), N-SRE-LWE requires approximately 25 KB ciphertexts and decapsulation times on the order of 500 ms in optimized C — approximately four orders of magnitude slower than Kyber-1024.

   from Abstract

6. Ciphertext sizes of approximately 25 KB for N-SRE-128 with seed-generated $A$.

   from 1.3. Contributions

How it is done

1. We prove that when the modulus is known, HM-LWE reduces to standard (noise-free) linear algebra over $\mathbb{Z}_p$, placing it in the same computational class as lattice problems.

   from Abstract

2. Security analysis: Proof that known-$p$ HM-LWE reduces to linear algebra over $\mathbb{Z}_p$ (Observation 1); construction and analysis of the Kannan embedding lattice attack; quantification of the hidden-modulus advantage as a multiplicative $\pi(p_{\max})$ factor; identification and resolution of the $a_i$-range leakage.

   from 1.3. Contributions

3. Section 5 presents the N-SRE-LWE construction and IND-CPA proof.

   from 1.4. Structure

4. Observation 1 provides an UPPER BOUND on HM-LWE complexity: HM-LWE is not harder than linear algebra over $\mathbb{Z}_p$ when $p$ is known.

   from 3.2. Relationship to Standard LWE

What would falsify it

1. If the adversary knows $p$, then HM-LWE reduces to solving a linear system over $\mathbb{Z}_p$ (noiseless).

   from 3.2. Relationship to Standard LWE

Where the claim stops

1. We introduce Hidden-Modulus Learning With Errors (HM-LWE), a cryptographic hardness assumption that generalizes standard LWE by making the modulus an additional secret rather than a public parameter.

   from Abstract

2. We quantify the hidden-modulus advantage as a multiplicative factor of $\pi(p_{\max}) \approx 2^{248}$ for 256-bit primes — the adversary must enumerate candidates for $p$ before lattice reduction can be applied, because the correct lattice embedding (Kannan) cannot be constructed without knowing the modulus.

   from Abstract

3. At deployment parameters ($n = 512$, 256-bit $p$), N-SRE-LWE requires approximately 25 KB ciphertexts and decapsulation times on the order of 500 ms in optimized C — approximately four orders of magnitude slower than Kyber-1024.

   from Abstract

Where to read

1. Abstract338 words · 1 min
2. 1. Introduction711 words · 3 min
3. 2. Preliminaries380 words · 2 min
4. 3. The Hidden-Modulus LWE Problem283 words · 1 min
5. 4. Security Analysis688 words · 3 min
6. 5. N-SRE-LWE: Key Encapsulation Mechanism584 words · 3 min
7. 6. Parameter Selection and Performance292 words · 1 min
8. 7. Experimental Verification190 words · 1 min
9. 8. Conclusion and Open Problems368 words · 2 min
10. Declarations54 words · 1 min
11. Appendix A: Deprecated Per-Digit Noise Variant185 words · 1 min