About Ring‐LWE - DevsDaddy/quarkdash GitHub Wiki

In this article, I described the rationale for choosing Ring-LWE and also provided a comparison table with the QuarkDash and NTRU/Kyber benchmarks.

QuarkDash (Ring-LWE) comparison with Kyber / NTRU

Parameter QuarkDash (Ring-LWE) Kyber‑512 NTRU‑hps‑2048
Complexity Ring‑LWE at ring Z_Q[x]/(x^N+1) Module‑LWE (MLWE) NTRU (lattice)
Public key size 2.0 KB (N=256, Q=7681) 0.8 KB 0.6 KB
Cipher text size (KEM) 1.0 KB 0.7 KB 0.6 KB
Key generation time ~12 ms ~8 ms ~15 ms
KEM-time ~9 ms ~7 ms ~10 ms
Quantum hardness (bit) ~128 ~128 ~128
Browser implementation Pure TypeScript / JS WebAssembly Pure TypeScript / JS
Timing-attack security Constant time Constant time Constant time
Simplicity of code ~500 lines NTT ~2000 lines (C/ASM) ~1000 lines

Conclusion

Kyber is faster and more compact, but usually requires WebAssembly for good browser performance. NTRU has smaller keys but is more complex to implement. QuarkDash offers a compromise: acceptable performance using pure JavaScript (TypeScript written), without external dependencies, which is important for web applications.

Justification of Ring-LWE parameters (N=256, Q=7681)

The choice of parameters is based on the following considerations:

  • NTT Compatibility: Q = 7681 is a prime of the form k*2^m + 1 (7681 = 15 512 + 1), allowing NTT with a root of order 512. This enables fast polynomial multiplication.
  • Attack Complexity: According to "Estimating the Security of LWE" (Alkim et al.), the parameters N = 256, σ = √(8/π) (standard deviation for {-1, 0, 1}) provide >128 bits of classical and quantum security against known attacks (BKZ, stacking).
  • Performance: A smaller N (256) speeds up NTT O(N log N) (2048 operations) compared to N = 512 (4608 operations). This allows for a KEM time of ~9 ms in JavaScript.
  • Key size: Each coefficient is stored in 16 bits (2 bytes), so 2 256 2 = 1024 bytes for a and the same for b → 2 KB. This is reasonable for a web environment.

Disadvantage: The parameters are not standardized by NIST (Kyber uses N=256, Q=3329). However, for proof-of-concept purposes and for use in protocols that do not require certification, the choice is acceptable.