GeMSS: Multivariate Signatures with HFEv-
GeMSS is a post-quantum signature scheme whose signatures have only a few hundred bits and whose public key is a system of quadratic equations. Learn how a hidden polynomial over GF(2^n) becomes a signature, how the signer finds roots, and why NIST dropped the scheme after a key-recovery attack.
Pashalis Laoutaris 41 min read
Try it
Interactive GeMSS Signatures Visualizer
🔐 GeMSS Signatures
GeMSS: Multivariate Signatures with HFEv-
Introduction
A signature of 36 bytes is smaller than a signature of ECDSA on P-256, which has 64 bytes. It is nearly a thousand times smaller than a signature of Picnic, which has about 33 kilobytes. The multivariate scheme GeMSS reaches this size at the 128-bit level. The price is a public key of 375 kilobytes.
The public key of GeMSS is a list of quadratic equations over the field with two elements. A signature is a solution of those equations for a value that depends on the message. Solving a random system of quadratic equations is a hard problem. The signer can do it because the equations hide a structure: they are a univariate polynomial over a large field, disguised by two linear maps.
This guide builds GeMSS from the third-round specification. It reproduces the public key and the signature of the official known-answer tests byte for byte. It also tells the end of the story. GeMSS was a candidate in the NIST post-quantum process, and a key-recovery attack ended its chances. The scheme is a good way to learn how multivariate signatures work, and it is not a scheme to deploy. For other signatures built from a single idea, see the Picnic guide and the SPHINCS+ guide.
Table of Contents
- History and Standards
- The Idea: a Polynomial in Disguise
- The Secret Polynomial
- From the Polynomial to the Public Key
- Inverting the Public Key
- Four Rounds: the Feistel-Patarin Construction
- Verification
- Parameter Sets
- Interactive Visualizer
- A Worked Example
- Python Implementation
- Where It Stands
- Limitations
- Security Status
- FAQ
- References
History and Standards
GeMSS stands for “Great Multivariate Short Signature”. It descends from the Hidden Field Equations, or HFE, which Jacques Patarin published in 1996. The specification calls HFE and its variants the most studied schemes of multivariate cryptography. Its direct ancestor is QUARTZ, a signature scheme by Patarin, Courtois, and Goubin that was submitted to the NESSIE project. QUARTZ produced signatures of 128 bits for a security level of 80 bits.
The GeMSS team has six members: Casanova, Faugère, Macario-Rat, Patarin, Perret, and Ryckeghem. Their affiliations in the specification are CS, CryptoNext Security, INRIA, Sorbonne University, Orange, and the University of Versailles. The scheme uses the minus and vinegar modifiers of HFE, which gives the name HFEv-.
GeMSS was a third-round alternate candidate for signatures, together with Picnic and SPHINCS+. NIST IR 8413 describes the outcome. During the third round, an attack on GeMSS dramatically reduced its security and undermined NIST’s confidence in its maturity. That result led NIST to eliminate GeMSS from consideration for standardization. The report adds that the attack makes the vinegar and minus modifiers useless for security in an HFEv- construction, and that repairing the scheme would change too much and cost too much performance.
The Idea: a Polynomial in Disguise
Let n be a number such as 177 and let K = GF(2^n) be the field with 2^n elements. Every element of K is a vector of n bits, and the map from bits to field elements is a bijection. A polynomial F(X) over K can therefore be seen as a map from n bits to n bits.
Inverting such a polynomial is easy. To solve F(X) = Y for a given Y, find the roots of the univariate polynomial F(X) - Y over K. Algorithms for this have a cost that grows only quasi-linearly with the degree. The degree of F must stay small for this to be practical.
Now choose F with a special shape. Let all exponents of X have the form 2^i + 2^j. In characteristic 2, raising to a power of 2 is a linear map over GF(2). A product of two such terms is therefore a quadratic form in the bits of X. The result is that, written in bits, the n output bits of F are quadratic polynomials in the n input bits. This is the HFE shape.
The trapdoor works as follows.
- The secret key is the polynomial
Fand two invertible linear mapsSandToverGF(2). - The public key is the map
x -> F(xS) T, written as quadratic equations in the bits ofx. The linear maps hide the structure ofF. - Inverting the public key means undoing
T, finding a root of the univariate polynomial, and undoingS.
An attacker sees only quadratic equations with no visible structure. Solving a general system of this kind is the MQ problem. The security of the scheme depends on whether the hidden structure leaks, and that is the point where GeMSS failed.
Two modifiers strengthen the construction.
- Minus. Remove
Δof thenequations from the public key. The public key hasm = n - Δequations. The signer fills the missingΔbits with random values before inverting. - Vinegar. Add
vextra variables to the system. They enter the coefficients ofF. For each signature, the signer fixes them to random values and gets an HFE polynomial inXalone.
The public key then has m equations in n + v variables.
The Secret Polynomial
For RedGeMSS128, the parameters are n = 177, v = 15, Δ = 15, so m = 162 and n + v = 192. The degree is D = 17 = 2^4 + 2^0. The field is GF(2)[X] / (X^177 + X^8 + 1). The specification says that the reference implementation uses this trinomial.
The polynomial has this form:
F(X, v) = X^17
+ sum A[i][j] X^(2^i + 2^j) for the exponents 3, 5, 6, 9, 10, 12
+ sum (B[i] + linear in v) X^(2^i) for the exponents 1, 2, 4, 8, 16
+ C(v) a quadratic form in the vinegar variablesThe leading coefficient is 1. All other coefficients are random elements of K. The coefficients of X^(2^i) depend linearly on the vinegar variables, and the constant term C(v) is quadratic in them. For fixed v, the polynomial has degree 17 in X.
The secret key in the NIST package is only a seed of 16 bytes. SHAKE128 expands it into 16,536 bytes. These bytes hold the 207 coefficients of F, each of 177 bits, followed by the matrices. The matrices are not stored in full. The seed gives a lower triangular matrix L and another lower triangular matrix U, both with ones on the diagonal, and the inverse of S is L * U^T. The same construction gives the inverse of T. A matrix built this way is invertible by design, because its determinant is 1. The specification notes that this method cannot generate all invertible matrices, and that the loss does not weaken the scheme.
From the Polynomial to the Public Key
Key generation turns F into m quadratic equations. The specification describes three steps.
- Write
Fin bits. ReplaceXbyx_0 + x_1 X + ... + x_176 X^176, where thex_kare bits. Each powerX^(2^i)becomes a linear form in thex_kwith coefficients inK. Each product of two such powers becomes a quadratic form. After this step,Fis a vector of 177 quadratic forms in 192 variables, where the vinegar variables followx_176. A quadratic form needs192 * 193 / 2 + 1 = 18,529monomials: one constant, and one for each pair of variables, including each variable with itself, becausex^2 = x. - Change the variables. Substitute
x -> xSin every form. The matrixQof each form becomesS Q S^T, and the two triangles of the result are added to give an upper triangular matrix again. - Mix the equations. Multiply the vector of equations by
T, and keep the first 162 of the 177 results.
The public key has 162 equations. A coefficient of one monomial is an element of GF(2^162), so the key is a list of 18,529 elements of 162 bits.
The NIST package stores the key in a packed format. The first 160 equations are stored monomial by monomial. The last two are stored one after the other, with their monomials in another order, and the last bits of the final equation fill the padding of the other one. The packed key has 375,213 bytes, which is 162 * 18,529 bits rounded up. The specification gives a size of 375.21 kilobytes for this set. My code reproduces the file of the package, and the first bytes of the key are efe65b6a73b37d5e3a28843c.
Inverting the Public Key
The signer must find a point s with p(s) = d for a given d of 162 bits. This is the inversion function Inv_p of the specification.
- Complete the target. Append
Δ = 15random bitsRtod. This gives a vectord'of 177 bits. - Undo the mixing. Compute the vector
U = d' T^-1, which is an element ofK. - Fix the vinegar. Draw random values for the 15 vinegar variables. The polynomial
F(X, v) - Uhas degree 17 inX. - Find a root. If the polynomial has no root in
K, go back to step 1 with new random bits. Otherwise pick a rootZ. - Undo the substitution. The point is
s = (Z, v) S^-1, a vector of 192 bits.
The root search is the costly part. All roots of a polynomial P over K lie in the factor gcd(P, X^(2^n) - X), because every element of K satisfies x^(2^n) = x. The code first computes X^(2^n) modulo P by squaring n times. In characteristic 2, squaring a polynomial squares each coefficient, so a square is cheap. Then it takes the gcd. The degree of the gcd is the number of roots. If this number is larger than one, the code splits the gcd with the trace map. It picks a random β and computes the sum of (βX)^(2^i) for i from 0 to n - 1 modulo the gcd. The gcd of that sum with the first gcd splits the roots into two groups, and the code recurses. A polynomial of degree 2 over a field with an odd n is solved directly with the half-trace.
When there are several roots, the specification fixes the choice. The roots are sorted as integers, and the signer takes the one with the index H mod l, where H is the first 64 bits of SHA3-256(U) and l is the number of roots. This makes the choice deterministic.
How often does a root exist? The polynomial F(X, v) - U behaves like the zero set of a random system of n equations in n unknowns. The specification cites a result that such a system has exactly s solutions with probability 1 / (e * s!). My code found the following for 160 random values of U and the vinegar variables: 55 cases with no root, 62 with one root, 34 with two, 7 with three, and 2 with four. A root exists in 66 percent of the cases, which fits 1 - 1/e = 63 percent. The specification gives the expected number of attempts as about 1.58, and I measured 1.52 with this sample.
Four Rounds: the Feistel-Patarin Construction
One inversion would give a signature of 162 bits, the size of the hash. This is too short. A birthday attack on a 162-bit hash costs about 2^81, which is far below the 128-bit level. GeMSS follows QUARTZ and chains nb_ite = 4 inversions in a Feistel-Patarin construction.
The signer computes H_1 = SHA3-256(M) and H_(k+1) = SHA3-256(H_k). Let D_k be the first 162 bits of H_k. Start with S_0 = 0 and, for k from 1 to 4, invert the public key on D_k xor S_(k-1). The inversion gives a point S_k || X_k, where S_k has the first 162 bits and X_k has the other 30 bits, and the next round uses S_k.
The signature is S_4 || X_4, then X_3, X_2, X_1, so it has 192 + 3 * 30 = 282 bits. That is 36 bytes. The point S_4 || X_4 has 192 bits, and each earlier round adds only its 30 extra bits, because the verifier can recompute the 162-bit part.
The number of rounds comes from Theorem 2 of the specification, which is adapted from the QUARTZ analysis. It requires that (2^m)^(nb_ite / (nb_ite + 1)) is at least 2^λ. For m = 162 and nb_ite = 4 the left side is 2^129.6, which exceeds 2^128. With nb_ite = 3 it would be 2^121.5. The three newer sets of the third round use three rounds with a refined analysis in Section 8.6 of the specification, which I did not check.
Verification
The verifier needs only the public key and a few hashes.
- Parse the signature into
S_4 || X_4, andX_3,X_2,X_1. - Compute
D_1toD_4from the message, as the signer did. - For
kfrom 4 down to 1, evaluate the 162 equations of the public key at the pointS_k || X_kand addD_k. The result isS_(k-1). - The signature is valid when the chain ends with
S_0 = 0.
Evaluating the key is fast. A point has about 96 bits equal to 1, so each equation needs about 96 * 97 / 2 additions, and the code does all 162 equations at once with bit operations. The specification lists 141 thousand cycles for the verification with RedGeMSS128. A random string passes with probability about 2^-162, because the last value S_0 has 162 bits.
Parameter Sets
The specification defines six sets for each of three security levels. The third-round report notes that the sets differ in how much they rely on the modifiers. GeMSS and WhiteGeMSS rely on them least, and RedGeMSS and MagentaGeMSS rely on them most. The sets with a larger degree D sign more slowly. The table lists the 128-bit sets with the values of the specification.
| Set | Degree D |
n |
Minus Δ |
Vinegar v |
Rounds | Public key | Signature |
|---|---|---|---|---|---|---|---|
| GeMSS128 | 513 | 174 | 12 | 12 | 4 | 352.19 KB | 258 bits |
| BlueGeMSS128 | 129 | 175 | 13 | 14 | 4 | 363.61 KB | 270 bits |
| RedGeMSS128 | 17 | 177 | 15 | 15 | 4 | 375.21 KB | 282 bits |
| WhiteGeMSS128 | 513 | 175 | 12 | 12 | 3 | 358.17 KB | 235 bits |
| CyanGeMSS128 | 129 | 177 | 14 | 13 | 3 | 369.72 KB | 244 bits |
| MagentaGeMSS128 | 17 | 178 | 15 | 15 | 3 | 381.46 KB | 253 bits |
At the 192-bit level the public keys have 1,237.96 to 1,348.03 kilobytes and the signatures have 373 to 435 bits. At the 256-bit level the keys have 3,040.70 to 3,321.72 kilobytes and the signatures 513 to 600 bits. I recomputed the key and signature sizes of all 18 sets from the formulas m * (N(N + 1) / 2 + 1) bits for the key, with N = n + v, and N + (nb_ite - 1)(N - m) bits for the signature. All of them agree with the table of the specification.
The specification gives timings in millions of cycles for signing: about 608 for GeMSS128, 67.2 for BlueGeMSS128, and 2.05 for RedGeMSS128. The three sets use the degrees 513, 129, and 17, and they differ a little in n, Δ, and v. The signing time follows the degree, because the root search costs about n squarings of a polynomial of that degree.
Interactive Visualizer
The visualizer above runs RedGeMSS128 in your browser, for real. It generates the key pair of 375,213 bytes, signs the message, and verifies the signature. A run took about half a second in my tests, and a slower computer may need a few seconds.
- Seed of the generator. The generator is the AES-256 counter generator of the NIST known-answer tests. It supplies the secret key and the random bytes of the signature.
- Message. Text, or hexadecimal bytes after
0x. - Bits to flip. The positions are bits of the 288 bits of the signature, so you can see a single flipped bit being rejected.
The log shows the expansion of the seed, the sizes of the key, the hash of the message, each of the four inversions with its attempts, and the four steps of the verification. The defaults are the values of the first known-answer test, so the signature is the one in the NIST file.
A Worked Example
The first known-answer test of RedGeMSS128 starts from the 48-byte seed 061550234d158c5ec95595fe04ef7a25767f2e24cc2bc479d09d86dc9abcfde7056a8c266f9ef97ed08541dbd2e1ffa1. The generator gives the secret key 7c9935a0b07694aa0c6d10e4db6b1add. The message has 33 bytes, d81c4d8d734fcbfbeade3d3f8a039faa2a2c9957e835ad55b22e75bf57bb556ac8.
The public key has 375,213 bytes and SHA3-256 digest 764c18c9b35777dcd5f29d4faff3b59c8cd73d1f6ab5a3900452e5ca2873bdc2. The first coefficient of F is the constant term 501dac72725e3254104f9f7003a3f50693aa245b5ea101, and the coefficient of X is 2e1b13f2f238b8b038bb70a7157ec9d96e1ff960e57d00, both as 23 bytes in little-endian order. The first row of S^-1 is 0342ae445e28d601f2bacd6978ae6ee3f6a5c6d277ebab67. The matrix S^-1 is dense: it has 18494 bits equal to 1 out of 36,864.
The hash of the message is H_1 = afaa93992f510b7892aa9a70542e819c73a95f1c7bda6d3f2b2fad23e21e80a6. Its first 162 bits are the target of round 1, which is afaa93992f510b7892aa9a70542e819c73a95f1c03 when written as 21 bytes. The four rounds went like this:
| Round | Target D_k xor S_(k-1) | Attempts | Roots in the last attempt | S_k || X_k |
|—|—|—|—|—|
| 1 | afaa93992f510b7892aa9a70542e819c73a95f1c03 | 2 | 1 | c6fb544535c0a79f47d56ca620d14302f2acb4756c7b0cb8 |
| 2 | 13fb357b0ca025d9da2f5428e88033ab20b41a8c00 | 2 | 2 | a711c4f3e4d96dd6406725d8c9a562057057f7b0b55290d4 |
| 3 | efad6b67b8738fcd17b00f7ffe04a7051bb58fc002 | 1 | 1 | b5accb873f8f6127979ed105d197fe5bc87586cab39f2d73 |
| 4 | b8d17c671e17c61a615345d118980945f17db52803 | 4 | 1 | af28b3cbb412c53a66dbae90c734ea7477b7e739ce93f0ac |
The NIST package prints these intermediate values in a debug file, and they agree with mine. In round 2 the last attempt found 2 roots, so the signer used the hash of U to choose between them. The signature starts with the point of round 4, followed by 12 more bytes. They hold the 30-bit fields X_3 = 0x1ccb67ec, X_2 = 0x352414ad, and X_1 = 0x2e031edb one after another. The whole signature is:
af28b3cbb412c53a66dbae90c734ea7477b7e739ce93f0acec67cb5c2b0549bded31e002The verification starts from S_4 || X_4. It computes S_3 = b5accb873f8f6127979ed105d197fe5bc87586ca03, then S_2 = a711c4f3e4d96dd6406725d8c9a562057057f7b001, then S_1 = c6fb544535c0a79f47d56ca620d14302f2acb47500, and finally S_0 = 0. The signature is valid.
Python Implementation
This is a complete GeMSS for the sets whose degree is 2^I + 1: RedGeMSS128, BlueGeMSS128, and GeMSS128. A field element and every vector of bits is a Python integer. The class Scheme holds the parameters of one set.
# gemss.py
# GeMSS (HFEv- with the Feistel-Patarin construction), written from the specification of the third round
# and checked against the known-answer tests of the NIST package. The code handles the parameter sets whose
# secret polynomial has the degree D = 2^I + 1 (RedGeMSS, BlueGeMSS and GeMSS). The tests run RedGeMSS128
# (D = 17), where Python signs in a few seconds.
# A vector of bits is a Python integer. Bit k of an element of GF(2^n) is the coefficient of X^k, and it is
# also the value of the k-th variable x_k of the multivariate system.
import hashlib
from collections import namedtuple
Params = namedtuple("Params", "name level d_log n v delta nb_ite k3")
# n: GF(2^n) = GF(2)[X] / (X^n + X^k3 + 1); v: vinegar variables; delta: removed equations; D = 2^d_log + 1
RED128 = Params("RedGeMSS128", 128, 4, 177, 15, 15, 4, 8)
BLUE128 = Params("BlueGeMSS128", 128, 7, 175, 14, 13, 4, 16)
GEMSS128 = Params("GeMSS128", 128, 9, 174, 12, 12, 4, 13)
def xor_columns(row, positions):
acc = 0
for j in positions:
acc ^= row[j]
return acc
class Scheme:
def __init__(self, p):
self.p = p
self.n, self.v, self.nb_ite, self.k3 = p.n, p.v, p.nb_ite, p.k3
self.nv = p.n + p.v
self.m = p.n - p.delta
self.degree = (1 << p.d_log) + 1
self.mask_n = (1 << p.n) - 1
self.mask_m = (1 << self.m) - 1
self.words_n = (p.n + 63) // 64
self.n_monomials = self.nv * (self.nv + 1) // 2 + 1
# The coefficients of F in the order of the secret key: the constant, the quadratic terms in the vinegar
# variables, then X, X^2, X^3, X^4, X^5, X^6, X^8, ... The exponents 2^i come with v more coefficients.
layout = [("const",)]
layout += [("vq", a, b) for a in range(p.v) for b in range(a, p.v)]
layout += [("lin", 0), ("lin", 1)]
for i in range(1, p.d_log):
layout += [("quad", i, j) for j in range(i)]
layout += [("lin", i + 1)]
self.layout = layout
self.n_coefs = len(layout) + (p.d_log + 1) * p.v
self.spread = [sum(((b >> i) & 1) << (2 * i) for i in range(8)) for b in range(256)]
# ------------------------------------------------------------ GF(2^n)
def reduce(self, x):
n, k, mask = self.n, self.k3, self.mask_n
while x >> n:
hi = x >> n
x = (x & mask) ^ hi ^ (hi << k)
return x
def mul(self, a, b):
if not a or not b:
return 0
table = [0, a, a << 1, (a << 1) ^ a]
for i in range(4, 16, 2):
table.append(table[i >> 1] << 1)
table.append(table[-1] ^ a)
result = 0
for shift in range((b.bit_length() + 3) // 4 * 4 - 4, -4, -4):
result = (result << 4) ^ table[(b >> shift) & 15]
return self.reduce(result)
def sqr(self, a):
s = 0
for i, byte in enumerate(a.to_bytes((self.n + 7) // 8, "little")):
s |= self.spread[byte] << (16 * i)
return self.reduce(s)
def inverse(self, a):
result, e, base = 1, (1 << self.n) - 2, a
while e:
if e & 1:
result = self.mul(result, base)
base = self.sqr(base)
e >>= 1
return result
# ------------------------------------------------------------ the secret key, expanded from the seed
def expand_seed(self, seed):
# SHAKE128 of the seed gives F, then L and U for S^-1, then L and U for T^-1
nq, nr = self.nv // 64, self.nv % 64
words_s = nq * (nq + 1) // 2 * 64 + ((self.nv + 63) // 64) * nr
nq_t, nr_t = self.n // 64, self.n % 64
words_t = nq_t * (nq_t + 1) // 2 * 64 + self.words_n * nr_t
total = self.n_coefs * self.words_n + 2 * words_s + 2 * words_t
stream = hashlib.shake_128(seed).digest(total * 8)
pos, coefs = 0, []
for _ in range(self.n_coefs):
coefs.append(int.from_bytes(stream[pos:pos + 8 * self.words_n], "little") & self.mask_n)
pos += 8 * self.words_n
l_s, pos = self.read_lower(stream, pos, self.nv)
u_s, pos = self.read_lower(stream, pos, self.nv)
l_t, pos = self.read_lower(stream, pos, self.n)
u_t, pos = self.read_lower(stream, pos, self.n)
assert pos == len(stream)
return coefs, self.product(l_s, u_s), self.product(l_t, u_t)
@staticmethod
def read_lower(stream, pos, dim):
# A lower triangular matrix with ones on the diagonal. Row i has ceil((i + 1) / 64) 64-bit words, and the
# rows are stored in blocks of 64. The bits above the diagonal are cleared and the diagonal is set.
nq, nr = dim // 64, dim % 64
rows = []
for block in range(1, nq + 1):
for r in range(64):
i = 64 * (block - 1) + r
raw = int.from_bytes(stream[pos:pos + 8 * block], "little")
pos += 8 * block
rows.append((raw & ((1 << i) - 1)) | (1 << i))
for r in range(nr):
i = 64 * nq + r
raw = int.from_bytes(stream[pos:pos + 8 * (nq + 1)], "little")
pos += 8 * (nq + 1)
rows.append((raw & ((1 << i) - 1)) | (1 << i))
return rows, pos
@staticmethod
def product(lower, upper_t):
# the matrix L * U^T, with both factors stored as lower triangular matrices
size = len(lower)
return [sum(((lower[i] & upper_t[j]).bit_count() & 1) << j for j in range(size)) for i in range(size)]
@staticmethod
def invert(rows):
size = len(rows)
left, right = list(rows), [1 << i for i in range(size)]
for col in range(size):
pivot = next(r for r in range(col, size) if (left[r] >> col) & 1)
left[col], left[pivot] = left[pivot], left[col]
right[col], right[pivot] = right[pivot], right[col]
for r in range(size):
if r != col and (left[r] >> col) & 1:
left[r] ^= left[col]
right[r] ^= right[col]
return right
def parse_polynomial(self, coefs):
p = self.p
it = iter(coefs)
poly = {"const": next(it), "vq": {}, "lin": {}, "quad": {}}
for item in self.layout[1:]:
if item[0] == "vq":
poly["vq"][(item[1], item[2])] = next(it)
elif item[0] == "lin":
poly["lin"][item[1]] = [next(it) for _ in range(1 + p.v)]
else:
poly["quad"][(item[1], item[2])] = next(it)
poly["quad"][(p.d_log, 0)] = 1 # the leading term X^(2^I + 1) has the coefficient 1
return poly
def univariate(self, poly, vinegar):
# the HFE polynomial that remains when the vinegar variables are fixed: a dict exponent -> coefficient
bits = [(vinegar >> j) & 1 for j in range(self.v)]
const = poly["const"]
for (a, b), c in poly["vq"].items():
if bits[a] and bits[b]:
const ^= c
out = {0: const}
for i, coefs in poly["lin"].items():
coef = coefs[0]
for j in range(self.v):
if bits[j]:
coef ^= coefs[1 + j]
out[1 << i] = coef
for (a, b), c in poly["quad"].items():
out[(1 << a) + (1 << b)] = c
return out
# ------------------------------------------------------------ the public key
def secret_system(self, poly):
# F(sum_k x_k X^k, vinegar) as quadratic equations over GF(2): Q[k][l] for k <= l is an n-bit integer
# whose bit c is the coefficient of x_k x_l in equation c (x_k^2 = x_k is stored on the diagonal)
n, v, nv = self.n, self.v, self.nv
power = [1]
for _ in range((n - 1) * self.degree):
x = power[-1] << 1
power.append(x ^ (1 << n) ^ (1 << self.k3) ^ 1 if (x >> n) & 1 else x)
q = [[0] * nv for _ in range(nv)]
for (a, b), c in poly["quad"].items():
ea, eb = 1 << a, 1 << b
for k in range(n):
term = power[k * (ea + eb)]
q[k][k] ^= term if c == 1 else self.mul(c, term)
for l in range(k + 1, n):
term = power[k * ea + l * eb] ^ power[l * ea + k * eb]
q[k][l] ^= term if c == 1 else self.mul(c, term)
for i, coefs in poly["lin"].items():
for k in range(n):
q[k][k] ^= self.mul(coefs[0], power[k << i])
for j in range(v):
q[k][n + j] ^= self.mul(coefs[1 + j], power[k << i])
for (a, b), c in poly["vq"].items():
q[n + a][n + b] ^= c
return poly["const"], q
def change_variables(self, q, s_rows):
# x -> x S: Q' = S Q S^T. The two triangles are added, so the result is upper triangular again.
nv = self.nv
s_bits = [[i for i in range(nv) if (row >> i) & 1] for row in s_rows]
sq = []
for a in range(nv):
acc = [0] * nv
for i in s_bits[a]:
qi = q[i]
for j in range(i, nv):
acc[j] ^= qi[j]
sq.append(acc)
full = [[xor_columns(sq[a], s_bits[b]) for b in range(nv)] for a in range(nv)]
out = [[0] * nv for _ in range(nv)]
for a in range(nv):
out[a][a] = full[a][a]
for b in range(a + 1, nv):
out[a][b] = full[a][b] ^ full[b][a]
return out
def keygen(self, seed):
# the public key as a list of m-bit integers: the constant, then the monomials x_a x_b with a <= b,
# row by row. Bit e of an entry is the coefficient in equation e.
coefs, s_inv, t_inv = self.expand_seed(seed)
poly = self.parse_polynomial(coefs)
const, q = self.secret_system(poly)
s, t = self.invert(s_inv), self.invert(t_inv)
qs = self.change_variables(q, s)
columns = [sum(((t[i] >> e) & 1) << i for i in range(self.n)) for e in range(self.m)] # the first m columns of T
def mix(vec):
return sum(((vec & columns[e]).bit_count() & 1) << e for e in range(self.m))
pk = [mix(const)]
for a in range(self.nv):
for b in range(a, self.nv):
pk.append(mix(qs[a][b]))
return pk
def index(self, a, b):
return 1 + a * self.nv - a * (a - 1) // 2 + (b - a)
# ------------------------------------------------------------ the packed format of the public key
# This is the packed format of section 2.6.6 of the specification.
# The first 8 * floor(m / 8) equations are stored monomial by monomial. The last m mod 8 equations are stored
# one after the other, with the monomials in the order x_0 x_0, x_0 x_1, x_1 x_1, x_0 x_2, ... To save the
# padding bits, the last bits of the very last equation fill the padding of the other ones.
def lower_order(self, bits):
return [bits[0]] + [bits[self.index(a, r)] for r in range(self.nv) for a in range(r + 1)]
def pack_public_key(self, pk):
m, nv, count = self.m, self.nv, self.n_monomials
mq8, mr8 = m >> 3, m & 7
pad = (8 - count % 8) % 8
lost = (mr8 - 1) * pad if mr8 else 0
out = bytearray()
for c in pk:
out += (c & ((1 << (8 * mq8)) - 1)).to_bytes(mq8, "little")
equations = [self.lower_order([(c >> (8 * mq8 + e)) & 1 for c in pk]) for e in range(mr8)]
packed = []
for e, bits in enumerate(equations):
if e == mr8 - 1:
bits = bits[:len(bits) - lost]
packed.append(bytearray(sum(bits[i] << (i - k) for i in range(k, min(k + 8, len(bits)))) for k in range(0, len(bits), 8)))
if lost:
tail = equations[-1][len(equations[-1]) - lost:]
val = sum(b << t for t, b in enumerate(tail))
for j in range(mr8 - 1):
packed[j][-1] ^= (((val >> (j * pad)) & 0xFF) << (count % 8)) & 0xFF
for chunk in packed:
out += chunk
return bytes(out)
def unpack_public_key(self, data):
m, nv, count = self.m, self.nv, self.n_monomials
mq8, mr8 = m >> 3, m & 7
pad = (8 - count % 8) % 8
lost = (mr8 - 1) * pad if mr8 else 0
pk = [int.from_bytes(data[i * mq8:(i + 1) * mq8], "little") for i in range(count)]
pos = count * mq8
chunks = []
for e in range(mr8):
size = (count - (lost if e == mr8 - 1 else 0) + 7) // 8
chunks.append(data[pos:pos + size])
pos += size
assert pos == len(data), (pos, len(data))
val = 0
for j in range(mr8 - 1):
val |= ((chunks[j][-1] >> (count % 8)) & ((1 << pad) - 1)) << (j * pad)
for e in range(mr8):
keep = count - (lost if e == mr8 - 1 else 0)
bits = [(chunks[e][i >> 3] >> (i & 7)) & 1 for i in range(keep)]
if e == mr8 - 1:
bits += [(val >> t) & 1 for t in range(lost)]
pk[0] |= bits[0] << (8 * mq8 + e)
k = 1
for r in range(nv):
for a in range(r + 1):
pk[self.index(a, r)] |= bits[k] << (8 * mq8 + e)
k += 1
return pk
# ------------------------------------------------------------ roots of a polynomial over GF(2^n)
@staticmethod
def trim(a):
while a and a[-1] == 0:
a.pop()
return a
def poly_mod(self, a, g):
# remainder of a modulo g (g is not zero); lists of coefficients, lowest degree first
a = list(a)
inv = self.inverse(g[-1])
while len(a) >= len(g):
if a[-1]:
factor = self.mul(a[-1], inv)
shift = len(a) - len(g)
for i, c in enumerate(g):
a[i + shift] ^= self.mul(c, factor)
a.pop()
return self.trim(a)
def poly_divide(self, a, b):
a, inv = list(a), self.inverse(b[-1])
q = [0] * (len(a) - len(b) + 1)
while len(a) >= len(b):
if a[-1]:
factor = self.mul(a[-1], inv)
shift = len(a) - len(b)
q[shift] = factor
for i, c in enumerate(b):
a[i + shift] ^= self.mul(c, factor)
a.pop()
return q
def poly_gcd(self, a, b):
a, b = self.trim(list(a)), self.trim(list(b))
while b:
a, b = b, self.poly_mod(a, b)
return a
def monic(self, a):
inv = self.inverse(a[-1])
return [self.mul(c, inv) for c in a]
def square_mod(self, a, g):
out = [0] * max(0, 2 * len(a) - 1)
for i, c in enumerate(a):
if c:
out[2 * i] = self.sqr(c)
return self.poly_mod(out, g) if len(out) >= len(g) else self.trim(out)
def quadratic_roots(self, g):
# g = X^2 + a X + b with two roots in GF(2^n), n odd: X = a Y gives Y^2 + Y = b / a^2, solved by the half-trace
b, a = g[0], g[1]
c = self.mul(b, self.inverse(self.sqr(a)))
y, term = c, c
for _ in range((self.n - 1) // 2):
term = self.sqr(self.sqr(term))
y ^= term
root = self.mul(a, y)
return [root, root ^ a]
def split_roots(self, g, rand):
# g is monic, has no repeated roots, and all of them lie in GF(2^n). As in the reference code, a polynomial of
# degree 2 is solved directly when n is odd. Otherwise a random beta is drawn from rand, and the gcd of g with
# the trace of beta * X splits the roots into two groups; the first group is handled before the second one.
if len(g) == 2:
return [g[0]]
if len(g) == 3 and self.n & 1:
return self.quadratic_roots(g)
n_bytes = (self.n + 7) // 8
while True:
beta = 0
while not beta:
beta = int.from_bytes(rand(n_bytes), "little") & self.mask_n
cur = self.poly_mod([0, beta], g)
acc = list(cur)
for _ in range(self.n - 1):
cur = self.square_mod(cur, g)
size = max(len(acc), len(cur))
acc = [(acc[i] if i < len(acc) else 0) ^ (cur[i] if i < len(cur) else 0) for i in range(size)]
acc = self.trim(acc)
h = self.poly_gcd(g, acc) if acc else g
if 1 <= len(h) - 1 < len(g) - 1:
break
other = self.poly_divide(g, h)
return self.split_roots(self.monic(h), rand) + self.split_roots(self.monic(other), rand)
def find_roots(self, terms, u, rand):
# all roots in GF(2^n) of X^D + sum terms[e] X^e + u, in increasing order; rand is used to split the roots
d = self.degree
low = {e: c for e, c in terms.items() if e < d}
low[0] = low.get(0, 0) ^ u
red = [(e, c) for e, c in low.items() if c]
x_power = [0] * d
x_power[1] = 1
for _ in range(self.n): # X^(2^n) modulo the polynomial
out = [0] * (2 * d - 1)
for i, c in enumerate(x_power):
if c:
out[2 * i] = self.sqr(c)
for deg in range(2 * d - 2, d - 1, -1):
c = out[deg]
if c:
for e, fc in red:
out[deg - d + e] ^= self.mul(c, fc)
out[deg] = 0
x_power = out[:d]
diff = list(x_power)
diff[1] ^= 1 # X^(2^n) - X
full = [low.get(e, 0) for e in range(d)] + [1]
g = self.poly_gcd(full, self.trim(diff))
if len(g) <= 1:
return []
return sorted(self.split_roots(self.monic(g), rand))
# ------------------------------------------------------------ signing and verification
def evaluate(self, pk, s):
# the m equations of the public key at the point s, as one m-bit integer
bits = [i for i in range(self.nv) if (s >> i) & 1]
result = pk[0]
for x, a in enumerate(bits):
for b in bits[x:]:
result ^= pk[self.index(a, b)]
return result
def sign(self, seed, message, rand):
# rand(count) returns count random bytes (the generator of the known-answer tests, as in the reference code)
coefs, s_inv, t_inv = self.expand_seed(seed)
poly = self.parse_polynomial(coefs)
n_bytes, m_bytes = (self.n + 7) // 8, (self.m + 7) // 8
minus_bytes = n_bytes - m_bytes + (1 if self.m & 7 else 0)
h = hashlib.sha3_256(message).digest()
s_state, xs, trace = 0, [], []
for k in range(1, self.nb_ite + 1):
d = (s_state ^ int.from_bytes(h, "little")) & self.mask_m # D_k xor S_(k-1)
tries, attempts = 0, []
while True:
tries += 1
r = int.from_bytes(rand(minus_bytes), "little")
r &= ~((1 << (self.m & 7)) - 1) if self.m & 7 else -1 # keep the m bits of d in the first byte
dr = (d | (r << (8 * (self.m >> 3)))) & self.mask_n # D_k || R_k
attempts.append(dr)
u = 0
for i in range(self.n): # (D_k || R_k) T^-1
if (dr >> i) & 1:
u ^= t_inv[i]
vinegar = int.from_bytes(rand((self.v + 7) // 8), "little") & ((1 << self.v) - 1)
roots = self.find_roots(self.univariate(poly, vinegar), u, rand)
if roots:
break
if len(roots) == 1:
z = roots[0]
else:
hash64 = int.from_bytes(hashlib.sha3_256(u.to_bytes(n_bytes, "little")).digest()[:8], "little")
z = roots[hash64 % len(roots)]
point = z | (vinegar << self.n)
s_state = 0
for i in range(self.nv): # (Z || vinegar) S^-1
if (point >> i) & 1:
s_state ^= s_inv[i]
trace.append({"k": k, "tries": tries, "roots": len(roots), "d": d, "attempts": attempts, "state": s_state})
xs.append(s_state >> self.m)
h = hashlib.sha3_256(h).digest()
bits, length = s_state, self.nv
for x in reversed(xs[:-1]): # S_k || X_k, then X_(k-1), ..., X_1
bits |= x << length
length += self.nv - self.m
return bits.to_bytes((length + 7) // 8, "little"), trace
def verify(self, pk, message, sig):
width = self.nv - self.m
total = self.nv + (self.nb_ite - 1) * width
if len(sig) != (total + 7) // 8:
return False
bits = int.from_bytes(sig, "little")
if bits >> total:
return False
first = bits & ((1 << self.nv) - 1)
bits >>= self.nv
x_values = []
for _ in range(self.nb_ite - 1):
x_values.append(bits & ((1 << width) - 1))
bits >>= width
digests, h = [], hashlib.sha3_256(message).digest()
for _ in range(self.nb_ite):
digests.append(int.from_bytes(h, "little") & self.mask_m)
h = hashlib.sha3_256(h).digest()
s, x = first & self.mask_m, first >> self.m
for k in range(self.nb_ite, 0, -1):
s = self.evaluate(pk, s | (x << self.m)) ^ digests[k - 1] # S_(k-1) = p(S_k || X_k) xor D_k
if k > 1:
x = x_values[self.nb_ite - k]
return s == 0
class ShakeRandom:
# a stand-in for a random source: the signing function needs random bytes for the minus bits, the vinegar
# variables, and the splitting of the roots. A real signer would use the operating system.
def __init__(self, label):
self.label, self.counter = label, 0
def read(self, count):
self.counter += 1
return hashlib.shake_128(self.label + self.counter.to_bytes(4, "little")).digest(count)
if __name__ == "__main__":
scheme = Scheme(RED128)
seed = bytes.fromhex("7c9935a0b07694aa0c6d10e4db6b1add") # the secret key: 16 bytes
message = b"The secret of getting ahead is getting started."
pk = scheme.keygen(seed)
packed = scheme.pack_public_key(pk)
print("public key: %d equations in %d variables, %d monomials, %d bytes packed" % (scheme.m, scheme.nv, len(pk), len(packed)))
print("SHA3-256 of the packed public key:", hashlib.sha3_256(packed).hexdigest())
signature, trace = scheme.sign(seed, message, ShakeRandom(b"example").read)
print("signature: %d bytes, %s" % (len(signature), signature.hex()))
print("attempts per iteration:", [t["tries"] for t in trace], "roots found:", [t["roots"] for t in trace])
print("verify the signature:", scheme.verify(pk, message, signature))
print("verify another message:", scheme.verify(pk, message + b"!", signature))
flipped = bytearray(signature)
flipped[10] ^= 1
print("verify after one flipped bit:", scheme.verify(pk, message, bytes(flipped)))
print("verify with the packed key read back:", scheme.verify(scheme.unpack_public_key(packed), message, signature))Running the file generates the key for the seed of the first known-answer test and signs a sentence:
public key: 162 equations in 192 variables, 18529 monomials, 375213 bytes packed
SHA3-256 of the packed public key: 764c18c9b35777dcd5f29d4faff3b59c8cd73d1f6ab5a3900452e5ca2873bdc2
signature: 36 bytes, 1c6c3a87f2c1c2cd3682f6c933c5f7f7312b77abc63c43ecba9f37a95073583b66425502
attempts per iteration: [1, 1, 2, 4] roots found: [1, 1, 2, 1]
verify the signature: True
verify another message: False
verify after one flipped bit: False
verify with the packed key read back: TrueI checked this code against the official known-answer tests of the GeMSS round 3 package. I read the files and the C reference code, and I did not run that code. For all 10 tests of RedGeMSS128, the code starts the generator of the NIST test suite, which I ported from the code of the package, and draws the secret key. It generates the public key, and the packed form of the key matches the file in all 375213 bytes. It signs the message with the random bytes of the same generator, and the signature matches in all 36 bytes. The file of intermediate values that the C code writes agrees with mine in all 40 rounds: the targets, every attempt with its random bits, and the points S_k || X_k.
The code also reproduces the first 3 tests of BlueGeMSS128, with a key of 363,609 bytes and a signature of 34 bytes. It reproduces the first test of GeMSS128 itself, with a key of 352,188 bytes and a signature of 33 bytes. That signature took 365 seconds in Python, because the polynomial has degree 513. Signing with RedGeMSS128 takes about 1.8 seconds, and key generation takes about one second.
Further tests cover the field and the rejection of bad signatures. The field GF(2^177) is commutative, associative, and distributive, a number times its inverse is 1, and x^(2^177) = x. At 25 random points, the public key and the secret map (F(sS)) T give the same 162 bits. Each of the 288 single-bit changes of the signature is rejected, and so are a changed message, another key, a signature of the wrong length, and the all-zero signature. None of 2,000 random strings was accepted.
The page code has its own SHAKE128, SHA3-256, AES-256, and field arithmetic with 32-bit limbs. It matches OpenSSL on 620 inputs. It makes the same public key as the file in the first three tests, and it reproduces all 34 test vectors that the Python code produces, including runs with flipped bits. I ran its page in a simulated browser.
Where It Stands
- Eliminated by NIST. GeMSS was a third-round alternate. The third-round report removed it from consideration after a key-recovery attack, and NIST did not advance it. It stays useful as a teaching example of multivariate cryptography, and of how one algebraic insight can break a family of schemes.
- Tiny signatures, huge keys. The signature of the 128-bit sets has 30 to 36 bytes, and the public key has about 352 to 381 kilobytes. This is the opposite of hash-based schemes.
- Fast verification. The specification lists 91 to 141 thousand cycles for the verification of the 128-bit sets.
- Slow key generation and signing. The specification lists 16 to 20 million cycles for key generation, and 1.8 to 608 million cycles for signing, which depends on the degree.
Limitations
This is a teaching implementation, not a production one:
- Do not use these parameters. The attack below applies to GeMSS. The code is for study.
- Not constant time. The code branches on secret values and the number of roots changes the running time. The reference code has constant-time parts, and its root finder is not constant time everywhere. Section 2.8 of the specification proposes constant-time solvers for roots of degree two and three, and a production signer would also need a secure random source and careful handling of the number of roots.
- Slow for large degrees. The root search takes minutes for a degree of 513. A C implementation is far faster.
- Randomness. The signing function takes its random bytes from the generator of the tests. A real signer needs a secure random source.
- Only some sets. I did not implement the 192-bit and 256-bit sets, the sets with three rounds, or the variants for other devices that the specification mentions. The code covers a degree of the form
2^I + 1. - No salt. The signature function follows the reference code, which does not add the salt of the modified inversion that the specification discusses for provable security.
Security Status
The best attacks on HFEv- before the third round were exponential in the number of vinegar variables and in the number of removed equations. This is why the design chose the modifiers. The third round changed the picture.
- Tao, Petzoldt, and Ding. Their paper “Improved Key Recovery of the HFEv- Signature Scheme” shows that the minus modifier does not enhance the security of HFE-type cryptosystems and that the vinegar modifier raises the cost of their attack only by a polynomial factor. They conclude that the proposed parameters of GeMSS are not as secure as claimed. NIST also cites their CRYPTO 2021 paper “Efficient Key Recovery for All HFE Signature Variants”.
- Baena and others. Their paper “Improving Support-Minors Rank Attacks: Applications to GeMSS and Rainbow” improves the attack. The authors estimate a time of about
2^72against GeMSS128, and they say that increasing the parameters is not a practical repair.
NIST IR 8413 calls the attack catastrophic. Earlier MinRank attacks were exponential in the number of vinegar variables and removed equations. The new attack is polynomial in the number of vinegar variables and is not affected much by the number of removed equations. A projection modifier could stop the attack, but the paper of Baena and others reports that this would slow signing by about 2^14. NIST judged that the repairs were too large a change for a submission in the third round. It also notes that later work made the support-minors approach practical when the solution lies in an extension field, which is the case for HFEv-.
The lesson goes beyond GeMSS. The security of a multivariate scheme rests on the hope that the hidden structure does not leak from the public equations. A new algebraic way to see the structure can break the hope for a whole family of schemes at once. The Dilithium guide and the Kyber guide cover lattice schemes that NIST chose, and the SPHINCS+ guide covers the scheme that rests only on a hash function.
FAQ
Why are GeMSS signatures so short?
Because the signature is a solution of a system with m = 162 equations in 192 unknowns, plus 30 bits for each earlier round. A solution has only the bits of the unknowns. Other schemes carry commitments, hash paths, or lattice vectors, which are much larger.
Why is the public key so large?
The key lists every coefficient of 162 quadratic equations in 192 variables. Each equation has 18,529 coefficients, so the key has about 3 million bits. This is inherent to multivariate schemes that publish the equations.
What are the minus and vinegar modifiers?
Minus removes a few equations from the public key, so that an attacker cannot use the full HFE system. Vinegar adds extra variables that the signer fixes at random. Both were meant to make attacks harder. The third-round attacks show that they do not give much security in HFEv-.
Why does the signer retry?
The polynomial F(X, v) - U has a root with probability about 63 percent, so about a third of the attempts fail. The signer draws new random bits and new vinegar values and tries again. This is why the signing time varies, and why four rounds need about six attempts on average.
Was GeMSS broken?
A key-recovery attack reduced its security dramatically, according to NIST. The authors of a later paper estimate about 2^72 for GeMSS128, which is far below the 128 bits that the scheme claims. NIST eliminated it from consideration. I did not verify the attacks myself.
Is the signature deterministic?
It depends on the random source. The random bits for the minus part and the vinegar variables come from a generator, so two signatures of one message differ when the generator differs. In the known-answer tests the generator is deterministic, which is why the signature is the same every time.
References
-
Casanova, Faugère, Macario-Rat, Patarin, Perret, and Ryckeghem. “GeMSS: A Great Multivariate Short Signature.” Round 3 Submission, specification and supporting documentation. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography
-
NIST. “Round 3 Submissions,” the GeMSS submission package with the reference implementation and the known-answer tests. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography
-
Tao, Chengdong, Albrecht Petzoldt, and Jintai Ding. “Improved Key Recovery of the HFEv- Signature Scheme.” Cryptology ePrint Archive, Paper 2020/1424. Available at: https://eprint.iacr.org/2020/1424
-
Baena, John, Pierre Briaud, Daniel Cabarcas, Ray Perlner, Daniel Smith-Tone, and Javier Verbel. “Improving Support-Minors Rank Attacks: Applications to GeMSS and Rainbow.” Cryptology ePrint Archive, Paper 2021/1677. Available at: https://eprint.iacr.org/2021/1677
-
Alagic, Gorjan, et al. “Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process.” NIST Internal Report 8413, July 2022, updated 26 September 2022. Available at: https://doi.org/10.6028/NIST.IR.8413-upd1
-
Patarin, Jacques. “Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms.” EUROCRYPT 1996, Lecture Notes in Computer Science 1070, pages 33 to 48.
-
Patarin, Jacques, Nicolas Courtois, and Louis Goubin. “Quartz, 128-bit Long Digital Signatures.” CT-RSA 2001, Lecture Notes in Computer Science 2020, pages 282 to 297.