eprint.iacr.orgpaper

A Universal Forgery Attack on the Origami Signature Scheme from the Public Key Alone

This IACR ePrint paper breaks Origami, a multivariate post-quantum signature scheme submitted to the NGCC round-1 public-key call, showing its bilinear construction is effectively a Rainbow-type scheme whose central map leaks through the public verification key in a predictable coordinate order. The authors derive an equivalent secret key from the public key alone, enabling universal forgery at roughly the cost of one signature verification (~0.01s at Origami-128), and demonstrate the attack against the unmodified reference implementation across all four parameter sets and the official test vectors. They also refute Origami's security proof by breaking its inversion assumption in a bilinear independent-coefficient model, and note a separate structural flaw where honest signatures lie in a proper subspace rather than the full space the specification assumes.