D3HFERP — d3c2026

Description

We obtained the public key of a post-quantum encryption prototype, together with several ciphertext blocks. Analyze the multivariate public-key encryption scheme and recover the encrypted flag.

The archive provides the Sage source, a public key, and seven ciphertext blocks. The goal is to invert the public multivariate map and reconstruct the length-prefixed plaintext.

Analysis

Public map

The source sets the field and dimensions to

q, d, o, r, s = 3, 20, 11, 11, 11
n, m = d + o, d + o + r + s

Thus a plaintext block is a vector in GF(3)^31, while a ciphertext block contains 53 field elements. Before mixing, the central map consists of:

• 20 HFE-derived coordinate polynomials;
• 22 oil-free UOV-style polynomials;
• 11 unrestricted random quadratic polynomials.

Invertible input and output transformations hide this decomposition. A public coordinate has the form

[ P_k(x)=x^T A_k x+L_kx+C_k. ]

Because the saved matrices are symmetric and only their upper triangles are serialized, an off-diagonal entry contributes 2*A[i][j]*x_i*x_j. This factor of two is important over GF(3).

Why direct inversion works

For ciphertext coordinate y_k, inversion requires solving

[ P_k(x)-y_k=0,\qquad 0\le k<53. ]

This is an overdetermined system of 53 quadratic equations in only 31 variables. The variables must also be restricted to GF(3), so append one field equation per variable:

[ x_i^3-x_i=x_i^3+2x_i=0. ]

Each block therefore becomes an 84-equation polynomial system. msolve's F4 implementation reduces every instance to a degree-one ideal with a unique solution. No recovery of the hidden HFE or UOV decomposition is needed.

A potentially related UOV common-kernel attack was not directly applicable. Output mixing combines all central coordinates, and the 11 unrestricted random quadratics destroy the full public common kernel that such an attack would need.

...