New Digital Signature Scheme with 24-Byte Signatures: X-1

[Martin Feussner]

Dear all,

We would like to share with you a new digital signature scheme, which we call X-1. The paper about it is available at: https://eprint.iacr.org/2025/2061

It is a hash-and-sign multivariate digital signature scheme. Its central trapdoor arises from the product of two one-variable polynomials, resulting in a structured quadratic map. The signature generation corresponds to efficiently inverting this map via polynomial factorization, while the security of the scheme reduces to solving a certain bilinear system, which is known to be computationally hard.

The paper provides parameters for the X-1 instantiation targeting NIST security level 1. The scheme is quite fast (even with its reference implementation) and has one of the smallest signature sizes ever proposed for this security level:

+--------------+--------------+
| Component    | Size (bytes) |
+--------------+--------------+
| Signature    | 24           |
| Public Key   | 23,040       |
| Private Key  | 48           |
+--------------+--------------+

+--------------------------------------------+------------+------------+------------+
| 10^4 iterations                            |    Min     |    Avg     |    Max     |
+--------------------------------------------+------------+------------+------------+
| Key generation (ms)                        |   0.7816   |   0.7933   |   1.0346   |
| Signature generation (ms)                  |   0.2288   |   1.8505   |  17.0706   |
| Signature verification (ms)                |   0.0319   |   0.0376   |   0.0605   |
+--------------------------------------------+------------+------------+------------+
| Key generation (clock cycles)              | 2,188,421  | 2,221,060  | 2,892,193  |
| Signature generation (clock cycles)        |   638,983  | 5,184,432  | 47,849,308 |
| Signature verification (clock cycles)      |    86,767  |   102,826  |   166,856  |
+--------------------------------------------+------------+------------+------------+

We invite cryptanalysts to have a look at our scheme. We will appreciate any comments or discussions on potential vulnerabilities or improvements.

Best regards,
Irene Di Muzio, Martin Feussner and Igor Semaev

[niux_d...@icloud.com]

Note that both polynomial factorization and bilinear solution are easy problems. Although polynomial factorization doesn't have unique solution(s), I gather any correct solution will lead to correct answer, thus a forgery.

So would your team spoil us by explaining concisely how do you guarantee forger doesn't get that degree of freedom?

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/3b9ac3b7-e657-484f-8241-f4924b79f89bn%40list.nist.gov.