Only a public permutation hides the trapdoor: universal forgery from the public key
Practical · Demonstrated · Cause: construction
Property: existential unforgeability (universal forgery, no signature needed)
Cost against claim: a forged signature the unmodified verifier accepts, in about 0.01 s at level 128, against 2128 to 2512
Origami's public map is its layered central map composed with an input permutation derived from the public seed, with no secret transformation on the output side. Anyone undoes the permutation with public data, reads off the zone, vinegar and oil structure of the central map and its coefficients, and then signs exactly as the signer does, one zone at a time, by linear algebra. From the public key alone, no signature needed, a valid signature is forged on any message.
| Parameter set | Claim | Attack cost | Verdict |
|---|---|---|---|
| Origami-128, -256, -384, -512 | 128 to 512 classical | a forged signature accepted by the verifier, about 0.01 s at level 128 and 15 s at level 512 on one core | Practical |
| Origami-160 (listed in the security statement, no implementation submitted) | 160 classical | same construction; not run | not computed |
What causes it
The specification derives the only hiding transformation from seed_pk (its equations 45 and 46), and the central map is sequentially linear per zone (equation 14; the text forbids any quadratic term in the oil block or any dependence on a later zone). Unlike UOV's secret linear map or Rainbow's output mixing, no secret invertible map stands between the public key and the layered structure, so each zone stays linear in its own oil block once the prefix and its vinegar are fixed. The one secret linear object only fixes the algebra in which the signer samples vinegar; it never enters the public key.
Evidence
Run on the unmodified reference code, at the public interface: the shipped verifier accepts the forged signature and the three negative controls (a flipped signature byte, a flipped salt byte, a different message) all reject, with no false accept. Origami-128 300/300 forgeries on 100 random keys, -256 45/45, -384 24/24, -512 15/15; forging takes about 0.01 s at level 128. On all four sets the official test-vector key was regenerated and a forgery accepted for the test-vector message, distinct from the test-vector signature. The design attribution was checked against the specification text (the public permutation and the absence of any secret output map), and the whole run was reproduced by a separate session from the pristine sources with a forge-free verifier.
Cause in the specification, traced to the specification text.
Limits
The tail zone is a square system with no vinegar to resample, singular about 7% of the time over GF(16), so the forger occasionally restarts from the first zone; every forgery still completes.
Designers' response
On the PKC forum (2026-09-24), the designers acknowledged the forgery and announced an updated algorithm within a few days. PQC-X has not checked it.
Credit
Found by PQC-X, announced on the NIST pqc-forum on 2026-09-24.
Related public reports:
- Peigen Li (PKC forum, also ngcc.dev sign-18-2, 2026-09-22): signatures reveal the hidden subalgebra constraints; no forgery.
- Pierre Pébereau (ngcc.dev sign-18-5, 2026-09-24): the same universal forgery from the public key, found independently and published later the same day.