Optimization of the multivariate polynomial public key for quantum safe digital signature
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Kuang, Perepechaenko, and Barbeau recently proposed a novel quantum-safe digital signature algorithm called Multivariate Polynomial Public Key or MPPK/DS. The key construction originated with two univariate polynomials and one base multivariate polynomial defined over a ring. The variable in the univariate polynomials represents a plain message. All but one variable in the multivariate polynomial refer to noise used to obscure private information. These polynomials are then used to produce two multivariate product polynomials, while excluding the constant term and highest order term with respect to the message variable. The excluded terms are used to create two noise functions. Then four produced polynomials, masked with two randomly chosen even numbers over the ring, form the Public Key. The two univariate polynomials and two randomly chosen numbers, behaving as an encryption key to obscure public polynomials, form the Private Key. The verification equation is derived from multiplying all of the original polynomials together. MPPK/DS uses a special safe prime to prevent private key recovery attacks over the ring, forcing adversaries to solve for private values over a sub-prime field and lift the solutions to the original ring. Lifting entire solutions from the sub-prime field to the ring is designed to be difficult based on security requirements. This paper intends to optimize MPPK/DS to reduce the signature size by a fifth. We added extra two private elements to further increase the complexity of the private key recovery attack. However, we show in our newly identified optimal attack that these extra private elements do not have any effect on the complexity of the private recovery attack due to the intrinsic feature of MPPK/DS. The optimal key-recovery attack reduces to a Modular Diophantine Equation Problem or MDEP with more than one unknown variables for a single equation. MDEP is a well-known NP-complete problem, producing a set with many equally-likely solutions, so the attacker would have to make a decision to choose the correct solution from the entire list. By purposely choosing the field size and the order of the univariate polynomials, we can achieve the desired security level. We also identified a new deterministic attack on the coefficients of two univariate private polynomials using intercepted signatures, which forms a overdetermined set of homogeneous cubic equations. To the best of our knowledge, the solution to such a problem is to brute force search all unknown variables and verify the obtained solutions. With those optimizations, MPPK/DS can offer extra security of 384 bit entropy at 128 bit field with a public key size being 256 bytes and signature size 128 or 256 bytes using SHA256 or SHA512 as the hash function respectively.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.002 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.001 | 0.001 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it