Reports › kem-19 · Constant-time review
Lore (kem-19)
| Candidate | Lore |
|---|---|
| Family | Lattice (module-LWR) |
| Archive | Lore.zip (SHA-256: e33130fb45a3b1e220f8043739d1396a884c0043cb4336104e67e5404c7cc725) |
kem-19-1: Lore-512's reducible ring admits smaller quotient attacks
| Severity | Medium |
|---|---|
| Scope | design |
| Status | Lead |
| Affected | Lore-512 (Lore-L4), both SHAKE and SM3 variants |
| Discovery | Moderate |
| Exploitation | Forum's heuristic full-recovery estimate is about 2^451 classical work; not independently validated |
| Credit | Xu Haomeng and collaborators |
| Date | 2026-09-23 |
Original source: NGCC PKC Forum post
Lore-512 uses Z_1028[x]/(x^768+1), but x^768+1 = (x^256+1)(x^512-x^256+1). The factors are coprime modulo 1028: writing y=x^256, their Bézout difference is 3, which is invertible modulo 1028. Public ring equations therefore project into degree-256 and degree-512 quotient rings, and the two recovered secret projections would reconstruct the full secret by CRT. A secret with coefficients in {-2,-1,0,1,2} projects to coefficients bounded by 6 and 4 respectively, so the smaller instances do not lose the small-secret structure.
The forum estimates approximately 451 classical and 391 quantum bits for full recovery, below the claimed 512-bit classical level. Those figures depend on an independent-coefficient/GSA lattice model that has not been reproduced here and does not fully model Lore's fixed-composition secret, rounding correlations, or concrete reduction costs. This is a structurally verified parameter-selection lead, not a demonstrated full-size key recovery or a confirmed 451-bit attack.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
python3 kem-19/reproduce_ring_projection.py
The preflight checks exact quotient multiplication and CRT reconstruction modulo 1028 using small-secret polynomials. It does not run lattice reduction; inspect Lore-L4/params.h and poly.c in either submitted backend for the modulus, degree, and negacyclic multiplication.