Skip to main content
3 of 3
added 27 characters in body
Saegusa
  • 173
  • 5

Criterion for unicity and existence of pre-image in multivariate cryptography

Repost from math.stackexchange since no one could help me there and it concerns my research.

I am reading Ding's Multivariate Public Key Cryptosystems and in the book the author explains the so-called bipolar construction where one chooses three maps to construct encryption and signature schemes. The vector spaces we consider are $\mathbb{F}^n$ and $\mathbb{F}^m$ where $\mathbb{F}:=\mathbb{F}_q$ is a finite field. Two of those maps are affine (usually denoted $\mathcal{S}:\mathbb{F}^m\to\mathbb{F}^m$ and $\mathcal{T}:\mathbb{F}^n\to\mathbb{F}^n$) and the third one $\mathcal{F}:\mathbb{F}^n\to\mathbb{F}^m$ (usually called the central map) is a system of $m$ multivariate quadratic polynomials in $n$ variables that is supposed to be "easily invertible". One then considers the public key $\mathcal{P}=\mathcal{S}\circ\mathcal{F}\circ\mathcal{T}$. To encrypt a message $\mathbf{w}\in\mathbb{F}^n$ one then simply computes $\mathbf{z}=\mathcal{P}(\mathbf{z})$. The decryption then follows recursively by setting $\mathbf{x} = \mathcal{S}^{-1}(\mathbf{w})$ and so on.

Then, the author makes the following claim:

If $m\geq n$, the pre-image of $\mathbf{x}$ by $\mathcal{F}$ i.e. $\mathcal{F}^{-1}(\mathbf{x})$ is unique.

It is not clear in my mind why this is true. The map $\mathcal{F}$ is not linear, is it? It's made up of quadratic multivariate polynomials. Why should the resulting pre-image be unique?

Likewise, for signature schemes they later consider $n\leq m$ and then the author makes this claim:

If $n\geq m$, then the pre-image $\mathcal{F}^{-1}(\mathbf{x})$ always exists and there might be multiple.

Why is this true? I thought that the map being easily invertible necessarily made it so that a pre-image exists. The claims are on page 15.

Saegusa
  • 173
  • 5