PQC-XXJTLU · cryptanalysis

Home › Public-key schemes › ZEN

KEM · lattice

ZEN

Design

zen-1

At q = 769 the Z-shaped basis profile brings ZEN-512 key recovery to its claimed level, not above it

Holds · Argued · Cause: construction

Property: key recovery

Cost against claim: 2490.8 to 2504.7 core-SVP and 2497.1 to 2508.6 MATZOV against 2512 at ZEN-512

The NTRU lattice built from the public key holds the secret pair (f, g) as an unusually short vector, which a primal BDD attack finds after BKZ reduction. At q = 769 the reduced basis keeps flat runs of Gram-Schmidt norms at q and at 1 (a Z-shape) instead of the GSA line, and that shape lowers the dimension the final BDD step needs. With any Z-aware model, ZEN-512 falls below 2512 in both cost models the designers use themselves.

Parameter setClaimAttack costVerdict
ZEN-512512 classical, 256 quantum2490.8 to 2504.7 core-SVP; 2497.1 to 2508.6 MATZOVHolds
ZEN-256256 classical, 128 quantum2246.9 to 2253.9 core-SVP; 2260.9 to 2267.1 MATZOVHolds

What causes it

Section 5.5 and Table 1 (PDF p. 23 to 24) cost the NTRU attack with the lattice estimator in its default GSA shape, giving 2526.2 core-SVP and 2530.5 MATZOV at ZEN-512. That GSA tail runs 2.5 bits below 1, which BKZ does not produce at q = 769 with the sparse ternary secrets of Table 3 (S3/32 for g and f at ZEN-512). The estimator's own Z-aware models (ZGSA, CN11) already give the lower figures.

Evidence

Estimator runs in GSA, ZGSA and CN11 shapes reproduce the designers' figures and the attack's to 0.1 bit (ZGSA 2492.6 core-SVP at block size 1681; CN11 2504.7). An independent re-derivation with our own code, no estimator, gives 2490.8 core-SVP with a clipped Z-shape and 2526.7 with GSA. Reduced BKZ runs (fpylll, q = 769, n = 128, block sizes 10 to 30) show the Z-shape: 0.06 to 0.08 bit RMS against the Z model, 0.23 to 0.91 against GSA; on a planted instance at ZEN-512's density the BDD dimension measured on the real profile is 99 and 87, the Z model predicts 100 and 89, GSA 120 and 102. A second member of PQC-X re-ran all of this independently.

Cause in the specification: the attack also works on a model built from the specification alone.

Limits

Counted as an observation: the estimates straddle the claim, from 2490.8 to 2508.6, and no model is precise to 8 bits. Estimated, not run: block size about 1680 to 1720, far beyond any measured point, and the shape is validated up to dimension 256 only. ZEN-256 falls below its claim in core-SVP only (2246.9 to 2253.9; MATZOV 2260.9 to 2267.1), a model-dependent shortfall. ZEN-128 is unaffected, and quantum core-SVP (2446.5, 2223.7) stays above the quantum claims.

Credit

Found by PQC-X.

Implementation

Bugs in the submitted code; the specification is sound on these points.

zen-i1

Reference Compress differs from the specified rounding on five residues

Holds · Demonstrated · Cause: code

Property: IND-CCA security

Cost against claim: Conformance only: a spec-conformant implementation disagrees with the reference on 95 to 97% of encapsulations

The reference poly_compress approximates Round(256a/769) with a multiply and shift that is one too low for a in {371, 374, 377, 380, 383}. A 512-coefficient ciphertext avoids all five residues only 3.5% of the time, so a spec-conformant implementation fails the official ciphertext KATs and derives a different shared key from the reference on most encapsulations. Security is not affected.

Parameter setClaimAttack costVerdict
all ZEN sets (reference code)Compress as specifiednone: differs on five residues, a conformance defectHolds

What causes it

Section 2.3 (PDF p. 8) defines Compress as Round(256a/769) mod 256 with Round(t) = floor(t + 1/2); the reference code (poly.c, l. 583 to 596) computes ((a << 8) + 384) * 10908 >> 23. Decompress matches the specification.

Evidence

An exhaustive loop over Z_769 finds the two formulas differ on exactly the five residues (a = 371: code 123, specification 124), and cross decapsulation between the reference and a spec-rounding build disagreed on 95 to 97% of encapsulations at ZEN-128. A second member of PQC-X re-ran the exhaustive check on an unmodified copy of the reference and re-derived the mismatch rate, (764/769)^512 gives 96.5%.

Cause in the submitted code; the specification is not affected.

Limits

Interoperability defect only: no key, message or shared secret is exposed.

Credit

Found by PQC-X.