Multivariate Cryptography
Expert-defined terms from the Professional Certificate in Post-Quantum Cryptography course at London School of Business and Administration. Free to read, free to share, paired with a professional course.
Affine Quadratic System (AQS) #
A set of equations where each equation is a quadratic polynomial over a finite field, possibly preceded by an affine transformation of the variables. Related terms: Multivariate Quadratic (MQ), affine map. In multivariate cryptography, AQS are the core of many signature schemes; the public key consists of an AQS, while the private key includes the hidden affine transformations that simplify solving the system. Example: The public key of the Rainbow signature scheme is an AQS with layered structure. Challenges include ensuring that the affine transformations do not leak information that could be exploited by algebraic attacks.
Bilinear Form #
A function B: V × V → F that is linear in each argument separately, where V is a vector space over a field F. Related terms: symmetric bilinear form, rank. Bilinear forms appear in the analysis of multivariate systems because they can be used to express certain quadratic terms as products of linear forms. For instance, the term x₁x₂ can be represented as B(e₁, e₂) where e₁, e₂ are basis vectors. Understanding the rank of the associated matrix helps assess the hardness of solving the underlying MQ problem.
Ciphertext #
Only Attack (COA): An attack model where the adversary has access solely to ciphertexts and attempts to recover the plaintext or secret key. Related terms: chosen-plaintext attack, known-plaintext attack. In the context of multivariate encryption schemes such as HFE (Hidden Field Equations), COA is relevant because the public key is a set of multivariate polynomials; observing many ciphertexts may reveal statistical patterns exploitable by algebraic techniques. Countermeasures include randomizing the encryption process and adding salts to the plaintext before applying the multivariate map.
Degree of a Polynomial #
The highest total degree among its monomials. Related terms: total degree, quadratic. Multivariate cryptography typically restricts the degree to two (quadratic) because higher degrees increase the size of the public key dramatically while offering limited security gains. Nevertheless, some schemes, like UOV (Unbalanced Oil‑and‑Vinegar), explore degree‑three extensions to achieve specific performance characteristics. Maintaining low degree is essential to keep key generation and verification efficient.
Equivalence Class (under affine transformations) #
Two MQ systems are considered equivalent if one can be obtained from the other by applying invertible affine transformations to the variables and the equations. Related terms: isomorphism, canonical form. This concept underlies the security of many multivariate schemes: The private key consists of the secret transformations that map a simple, easily solvable system to the public, seemingly random MQ system. An attacker who can identify the equivalence class can potentially recover the hidden transformations and break the scheme.
Finite Field (𝔽_q) #
A field with a finite number of elements q, where q is a prime power p^n. Related terms: Galois field, characteristic. Multivariate cryptographic constructions are usually defined over 𝔽_2 (binary field) or 𝔽_q with small q to keep arithmetic fast. The choice of field influences the algebraic structure of the MQ problem; for example, over 𝔽_2, every quadratic term is a product of two bits, simplifying implementation but also enabling specific attacks that exploit the field’s linearity.
Groebner Basis #
A particular generating set of an ideal in a polynomial ring that enables systematic solving of systems of polynomial equations. Related terms: Buchberger algorithm, reduction. Groebner basis computation is a primary tool for cryptanalysis of multivariate schemes. If an attacker can compute a Groebner basis for the public MQ system, they can solve for the secret variables, effectively breaking the scheme. The security of many multivariate protocols relies on the computational hardness of Groebner basis computation for random dense MQ systems.
Isomorphism of Polynomials (IP) #
The problem of determining whether two sets of multivariate polynomials are equivalent under a change of variables and a linear combination of the equations. Related terms: IP1, IP2. In multivariate cryptography, IP forms the basis of security: The private key often consists of the isomorphisms that map a simple base system to the public MQ system. An attacker who can solve the IP problem can reverse this mapping, thereby recovering the secret key. Known algorithms for IP are exponential in the number of variables, which provides a security margin for well‑parameterized schemes.
Jacobian Matrix #
The matrix of first‑order partial derivatives of a vector of multivariate polynomials with respect to its variables. Related terms: determinant, rank deficiency. The Jacobian is used in analyzing the invertibility of the multivariate map employed in encryption schemes. If the Jacobian is singular at some point, the map fails to be locally bijective, potentially leading to decryption errors. Designing schemes with a Jacobian that is nonsingular for all inputs is a key practical consideration, especially in signature schemes where signing must be deterministic and reliable.
Key‑Recovery Attack (KRA) #
An attack that aims to reconstruct the secret key (or the secret affine transformations) from the public key. Related terms: structural attack, algebraic attack. For multivariate schemes, KRAs often target the hidden structure of the MQ system. In HFE, a KRA may involve recovering the hidden univariate polynomial by solving a system of linear equations derived from the public MQ representation. Countermeasures include adding perturbations, using larger fields, or employing “double‑hide” techniques that increase the algebraic complexity of the public key.
Layered Quadratic System (LQS) #
An MQ system organized into layers, each containing a subset of variables that interact in a prescribed way. Related terms: Rainbow, oil‑and‑vinegar. The Rainbow signature scheme is a prominent example; it builds a sequence of UOV‑type layers, each providing additional security margins. The layering structure allows for efficient signing (by solving one layer at a time) while preserving resistance against generic attacks. However, the layered design can be vulnerable to “cross‑layer” attacks that exploit correlations between layers if parameters are not carefully chosen.
Multivariate Quadratic (MQ) Problem #
The computational problem of solving a system of m quadratic equations in n variables over a finite field. Related terms: NP‑hard, random instance. The MQ problem is the cornerstone of multivariate cryptography; its presumed hardness underlies the security of all schemes in this category. Randomly generated MQ instances are believed to be intractable for both classical and quantum computers when the ratio m/n is appropriate (typically m ≈ n). Cryptographers design parameters to ensure that the public key corresponds to a random‑looking MQ instance, thereby inheriting the hardness of the MQ problem.
Niederreiter Cryptosystem (multivariate variant) #
A code‑based encryption scheme that can be expressed as a multivariate quadratic system using the parity‑check matrix of a linear code. Related terms: McEliece, code‑based cryptography. While traditionally not a multivariate scheme, certain transformations allow the Niederreiter system to be interpreted as an MQ problem, enabling hybrid constructions that combine code‑based and multivariate security assumptions. This dual nature can provide resistance against attacks that target either representation alone.
Oil‑and‑Vinegar (OV) Scheme #
A class of signature schemes where variables are partitioned into “oil” and “vinegar” sets; quadratic equations are constructed so that each equation contains only vinegar‑vinegar and oil‑vinegar products, never oil‑oil terms. Related terms: UOV, unbalanced. The structure ensures that, given a random assignment to the vinegar variables, the resulting linear system in the oil variables can be solved efficiently, enabling fast signing. Verification requires checking the multivariate equations. Security relies on the difficulty of solving the underlying MQ system without knowing the vinegar assignment. Unbalanced variants increase the number of oil variables relative to vinegar variables to improve security margins.
Public Key #
In multivariate cryptography, the public key is typically a set of m quadratic polynomials in n variables that define the encryption or verification map. Related terms: private key, key generation. The public key must be large enough to appear random, preventing adversaries from detecting hidden structure. For example, a Rainbow public key may consist of thousands of coefficients, each representing a term like x_i x_j. Managing the storage and transmission of such keys is a practical challenge, especially for resource‑constrained environments.
Quadratic Form #
A homogeneous polynomial of degree two, often expressed as x^T A x where A is a symmetric matrix. Related terms: bilinear form, rank. In multivariate cryptography, each quadratic term of the MQ system can be represented by a quadratic form. Understanding the rank of these forms helps evaluate the algebraic independence of the equations, which affects the difficulty of solving the system. Low‑rank forms may lead to vulnerabilities, as they can be eliminated or simplified through linear transformations.
Rainbow Signature Scheme #
A multivariate signature algorithm that stacks several UOV layers to form a deep, layered MQ system. Related terms: UOV, layered quadratic system. During signing, the signer solves each layer sequentially, fixing a subset of variables at each step. Verification simply evaluates the public MQ polynomials on the provided signature. Rainbow offers fast signing and verification, and its security is based on the hardness of solving random MQ instances with a layered structure. Recent attacks have reduced the effective security margin, prompting recommendations for larger parameter sets.
Security Parameter (λ) #
The bit length that quantifies the intended security level of a cryptographic scheme. Related terms: key size, bit security. For multivariate schemes, λ determines the number of variables n and equations m required to achieve a target resistance against known attacks. For example, to reach 128‑bit security against Groebner‑basis attacks, a scheme may need n ≈ 200 and m ≈ 200 over 𝔽_2. Selecting appropriate parameters is a delicate balance between security, key size, and computational efficiency.
Tensor Rank #
The minimal number of simple tensors needed to express a given tensor, often used to analyze the complexity of multivariate polynomial systems. Related terms: decomposition, multilinear rank. In the analysis of MQ systems, tensors can represent the collection of quadratic coefficients. Low tensor rank may indicate hidden algebraic structure that can be exploited by attacks. Cryptographers aim for high tensor rank in the public key to avoid providing shortcuts for algebraic solvers.
Unbalanced Oil‑and‑Vinegar (UOV) #
A variant of the OV scheme where the number of oil variables significantly exceeds the number of vinegar variables. Related terms: Oil‑and‑Vinegar, signature scheme. The unbalanced design enhances security because the attacker must solve a system with many more unknowns than equations, increasing the combinatorial difficulty. UOV is widely studied due to its relatively small signature size and efficient verification, making it a candidate for post‑quantum standardization. However, parameter selection is crucial to avoid specialized attacks that target the unbalanced structure.
Vinegar Variables #
In the OV family, the subset of variables designated as “vinegar,” which appear in every quadratic term together with oil variables but never multiply each other. Related terms: oil variables, signature generation. Assigning random values to vinegar variables reduces each quadratic equation to a linear equation in the oil variables, enabling fast signing. The security of the scheme depends on the attacker’s inability to guess the correct vinegar assignment without solving the full MQ system.
Wilhelm’s Attack (Algebraic Compression) #
A technique that reduces the number of variables in an MQ system by exploiting linear dependencies among the equations, thereby accelerating Groebner‑basis computation. Related terms: Faugère F4/F5, complexity reduction. Wilhelm’s attack demonstrates that certain multivariate schemes with poorly chosen parameters may be vulnerable to algebraic compression, which effectively lowers the security level. Designers mitigate this risk by ensuring that the public MQ system exhibits high algebraic independence and lacks exploitable linear relations.
XOR‑Masking #
A simple method of adding randomness to a plaintext before applying a multivariate encryption map, by XORing the plaintext with a random mask. Related terms: randomized encryption, countermeasure. XOR‑masking helps prevent deterministic patterns in ciphertexts that could aid a ciphertext‑only attack. In practice, the mask is transmitted alongside the ciphertext (often encrypted with a symmetric key) or derived from a nonce. Properly applied, XOR‑masking preserves the correctness of decryption while enhancing resistance to statistical analysis.
Yao’s Garbled Circuit Transformation (applied to multivariate maps) #
A technique for converting a multivariate polynomial evaluation into a Boolean circuit and then garbling it for secure computation. Related terms: secure two‑party computation, oblivious evaluation. Although not a core part of standard multivariate cryptography, garbling can be used to outsource the evaluation of a public MQ system in a privacy‑preserving manner. This approach highlights the versatility of multivariate maps beyond encryption and signatures, extending to protocols such as zero‑knowledge proofs and secure multiparty computation.
Zero‑Knowledge Proof of Knowledge (ZK‑PoK) for MQ Systems #
A protocol that allows a prover to convince a verifier that they know a solution to a given MQ system without revealing the solution itself. Related terms: Sigma protocol, commitment scheme. Constructing efficient ZK‑PoK for multivariate systems often relies on commitment to the secret variables and challenge‑response rounds that leverage the algebraic structure of the MQ equations. Applications include authentication, anonymous credentials, and blockchain smart contracts where the prover must demonstrate knowledge of a valid signature key derived from an MQ scheme.