Associative Multivariate Permutation

Question

Popular multivariate schemes are constructed by having a several easy-to-invert functions/maps as parivate key, and their composition as the public key.

When signing, the hash, or a padded form of which is converted to a series of multivariate variables, and its pre-image under the maps computed as signature. However, public-key encryption is not as easy to construct as signature schemes in multivariate cryptography right now.

I'm wondering if it's possible to do the following:

For signature:

1. Generate a random public multivariate system $g()$,

2. Generate a random private multivariate system $f()$ as private key, and publish $p = g \circ f$ as public key.

3. Publish $\sigma = f(h)$ where $h$ is the hash of the message signed, and verify $g(\sigma) = p(h)$.

For key exchange:

1. Generate a random public multivariate system $g()$,

2. Generate a random private multivariate system $f()$ as private key, and publish $p = f \circ g$ as public key.

3. Client generates a random $x$ and sends $y = g(x)$ as public component, and calculates $p(x)$ as the key exchanged.

4. Server calculates $f(y)$ as the key exchanged.

My questions are:

1. What are the known attacks that doesn't involving inverting the multivariate equations system?

2. Had there been similar proposals? And if not, possibly why?

Answer 1

A couple of papers by Faugère and Perret (and, in one case, von zur Gathen) provide efficient (i.e., polynomial time) algorithms to solve the Functional Decomposition Problem:

• Given: a list of $u$ multivariate polynomials $H = (h_1, \ldots, h_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u$ in $n$ variables over some field $\mathbb{K}$.
• Task: find a non-trivial decomposition $(F,G)$ where $F = (f_1, \ldots, f_u) \in (\mathbb{K}[x_1, \ldots, x_n])^u$ and $G = (g_1, \ldots, g_n) \in (\mathbb{K}[x_1, \ldots, x_n])^n$ such that $H = F \circ G$.

There are various definitions of "non-trivial" designed to explicitly exclude pathological cases such as where $F$ or $G$ are the identity or linear transforms. Suffice to say that any cryptosystem claiming security based on the hardness of multivariate polynomial decomposition, such as your proposals, should convincingly argue why the algorithms of Faugère et al. do not apply.

Specifically, these algorithms enable the attacker to obtain $f$ from $p$ in your proposals, even without using $g$. This breaks the schemes without inverting anything because $f$ represents the secret key.

There was a similar proposal called 2R$^-$. It was the original motivation for Faugère and Perret to study the FDP, which lead to that scheme's demise.