XJTLU’s PQC-X laboratory breaks NGCC candidate Origami

The Post-Quantum Migration Interdisciplinary Laboratory (PQC-X) at Xi’an Jiaotong-Liverpool University has identified a universal forgery attack against Origami (NGCC Round 1 candidate, sign-18). The research was carried out by Hugo Louiso, a PhD student of Professor Jintai Ding at the laboratory.

Hugo Louiso

Next-Generation Commercial Cryptography (NGCC) is a programme run by the Institute of Commercial Cryptography Standards (ICCS) to evaluate and select cryptographic algorithms for future commercial applications. Its first round includes 84 public-key candidates: 34 digital signature algorithms, 41 key encapsulation mechanisms and nine key exchange algorithms. The evaluation is expected to be completed by June 2027. Origami is one of the Round 1 digital signature candidates. Digital signatures are widely used for electronic files, identity authentication and similar applications to verify the source and integrity of information.

The attack shows that an attacker with only a user’s public key can generate a valid signature for any message without obtaining a genuine signature or the user’s private key.

Hugo Louiso explains: “Origami’s public key accidentally gives away the recipe the owner uses to sign, so anyone who has it can sign too.”

The attack works across all four Origami parameter sets and can be reproduced using the official reference implementation and test vectors provided by the design team, without modifying the implementation. This indicates that the issue lies in the design of Origami itself rather than in a programming error in a specific implementation.

Using an ordinary laptop and only the public key, the researchers can forge signatures at all four security levels proposed by Origami: Origami-128, Origami-256, Origami-384 and Origami-512. According to the tests, generating a forgery takes about 0.01 to 5 seconds, roughly the time required to verify a normal signature.

The attack was also independently discovered by Pierre Pébereau of KU Leuven, Belgium, around the same time. The two teams subsequently collaborated on the full paper. The authors are Hugo Louiso, Pierre Pébereau, Professor Jintai Ding, Director of PQC-X, Hao Guo, Siyong Tao of Tsinghua University, and Peigen Li of BIMSA.

Hugo Louiso has informed the Origami design team of the finding. The paper has been submitted to the IACR Cryptology ePrint Archive. Origami is currently under evaluation as an NGCC Round 1 candidate and has not yet entered the standardisation or practical application stage.

By Qinru Liu