Structural Cryptanalysis of a Class-2 Nilpotent Lie Algebra Signature Candidate: Linearization and Equivalent-Secret Forgery

Source abstract

This study presents a structural cryptanalysis of a Fiat–Shamir-type digital-signature candidate based on class-2 nilpotent Lie algebras over finite fields. We show that the public transformation is linear in the signing secret and that public-key inversion reduces to a consistent linear system over the underlying finite field, solvable in polynomial time by Gaussian elimination. Because the associated linear map has a non-trivial kernel, the public key determines an affine family of equivalent signing secrets rather than a unique private key. Any compatible representative can therefore be used to generate a valid signature for a fresh message without access to a signing oracle, yielding a polynomial-time no-message forgery and failure of EUF-CMA security. The baseline evaluation considered n=16, 32, 64 and 128, using ten independently generated Lie algebra instances per dimension and ten cryptographic trials per instance. In the 400 baseline trials, none of the recovered compatible secrets coincided with the corresponding originally sampled private key, yet every recovered representative was sufficient to generate an accepted forgery, yielding a 100% experimental forgery rate. Additional sensitivity experiments on field size, central fraction, and bracket density showed that these parameters affect practical attack cost and rank-nullity structure but do not remove the vulnerability. The results demonstrate that the examined class-2 transformation is unsuitable as a hardness basis for a secure digital-signature construction or a meaningful post-quantum security claim.