DME is a cryptosystem of the multivariate family. That is, it consists in a polynomial map \[ \begin{array}{ccc} g:K^n & \to & K^m \\ \left( \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right) & \to & \left( \begin{array}{c} g_1(x_1,\ldots,x_n) \\ \vdots \\ g_m(x_1,\ldots,x_n) \end {array} \right) \end{array} \]
where the \(g_i\) are polynomials with coefficients in the field \(K\).
The idea is quite symple: your public key is just the polynomials \(g_1,\ldots,g_m\), and when someone wants to encrypt some message, just encode it as the values \((x_1,\ldots,x_n)\), evaluate the polynomial map in those values, and send the correspondent values to you. Then you need some method (which essentially will be your private key) to find the original values from the encrypted message. That is, decrypting is esentially the same as inverting the map \(f\).
If these polynomials have degree \(1\), we are in the realm of linear algebra, so we know easily to invert the map just by computing the inverse of a matrix.
However, if the degrees of the polynomials are higher, we get into a completely different scenario. Here it is not even easy to determine if the map is bijective or not. It could be bijective, it could map seven different values to a single one, it could map infinetly many to one, or it could even be the case that for some values it is injective, and for others it is not.
Given a value in \(K^m\), finding the possible preimages is essentally solving a system of polynomial equations. There is a general method for that, based on elimination theory; so one might think that this family of cryptosystems are doomed. But the caveat is that the general method makes use of Gröbner basis, which are really expensive to compute (and by really expensive I mean something like double exponential in the worst case, which in practice means that toy examples are ok, but as soon as the size grows, it becomes unfeasible).
Ok, so now that we know that in general it is difficult to decrypt the messages in this kind of cryptosystems, we have another problem: how does the legitimate recipient of the message decrypt it? Or in other words: how can we construct the map \(f\) in such a way that someone that knows some secret information (the private key) can invert it, but it remains hard to do so without that secret information?
The usual way to solve that question is to make \(f\) by composing several maps that are easy to invert. The list of those easy to invert maps will be the public key, whereas the final composition, would mix them in a way that is hard to recover. As a very easy example, consider the following maps:
As you can easiyly see, the first and last ones are just linear maps, and the rest consist on adding a function of one variable to the other one; so their inverses can be easily computed:
Now, if we compose all the three of them, we get that \((x,y)\) maps to
\[ \left( 2 x^{6} + 36 x^{5} y + 270 x^{4} y^{2} + 1080 x^{3} y^{3} + 2430 x^{2} y^{4} + 2916 x y^{5} + 1458 y^{6} - 8 x^{4} - 100 x^{3} y - 468 x^{2} y^{2} - 972 x y^{3} - 756 y^{4} - x^{3} - 9 x^{2} y - 27 x y^{2} - 27 y^{3} + 8 x^{2} + 56 x y + 98 y^{2} + 4 x + 13 y , x^{6} + 18 x^{5} y + 135 x^{4} y^{2} + 540 x^{3} y^{3} + 1215 x^{2} y^{4} + 1458 x y^{5} + 729 y^{6} - 4 x^{4} - 50 x^{3} y - 234 x^{2} y^{2} - 486 x y^{3} - 378 y^{4} - x^{3} - 9 x^{2} y - 27 x y^{2} - 27 y^{3} + 4 x^{2} + 28 x y + 49 y^{2} + 3 x + 10 y \right) \]
which doesn't look that easy to invert at all (note, this case is actually small enough to be inverted with the elimination techniques mentioned before, just take it as a toy example to showcase how the complex systems can be obtained by composing simple ones). In this example we also observe a phenomenon that we have to be careful with: the complexity of the polynomial system (which will translate into the size of the public key) can grow a lot if we don't choose the simple pieces to compose carefully.
So, summarizing, the challenge of creating a multivariate cryptosystem consists on choosing some elementary maps such that:
DME stands for double matrix exponentiation, because two of the elementary pieces mentioned before are matrix exponentiations (we will see later what this means). Besides these two matrix exponentiations, there are some linear maps and some auxilary transformations that basically consist on choosing the right way to represent the objects. Don't worry if this paragraph makes no sense to you now, we will explain it all carefully now.
We will see how the map is constructed step by step. For the purpose of this section, we will assume we have fixed some parameters. Later we will explain what different choices could have been made. For starters, assume we work in some binary field. In the example implementation, we use \(\mathbb{F}_q\) with \(q=2^{48}\). This will be our basic way to represent data. That is, all data will be seen as a list of elements in this field. Since it is a binary field, it is easy to represent a list of 48 bits as an element of this field. Just represent them as a degree \(48\) polynomial in \(t\) with coefficients in \(F_2\), where the coefficients are the values of the bits. This polynomial should be considered as a representative of its class modulo some irreducible polynomial. The choice of this irreducible polynomial doesn't really matter from the mathematical point of view (all possible choices are isomorphic), but maybe some choices can allow more efficient implementations, so we choose \(f=t^{48}+t^{28}+t^{27}+t+1\).
So now that we have a way to represent series of bits as elements of our field, we will consider vectors with \(6\) entries in this field. That is, we will see a series of \(288\) bits as a vector
\[ (x_0,x_1,x_2,x_3,x_4,x_5) \]
where the \(x_i\) are polynomials in \(t\) modulo \(f\) as before. That will be our plaintext. For reasons that you will later see, if too many of these vectors are zero, our system will fail, so we have to force them to be nonzero. This is done by adding some padding: that is, instead of considering \(288\) bits, we will consider a few less, and insert some \(1\)'s between them. In particular it is enough to introduce 3 such \(1\)'s, but in order not to break bytes, we actually add \(3\) bytes of padding; that is, we encode \(33\) bytes and interleave \(3\) bytes with the value \(1\) in the last positions of \(x_1\), \(x_3\) and \(x_5\).
Ok, so now that we have our plaintext correctly padded and expressed as a vector, the first step we take is to apply a linear transformation to it; that is, multiply it by a matrix with entries in \(\mathbb{F}_q\).
But remember that we mentioned that we have to be careful to prevent the complexity of the total map to explode; so the matrix that we use here must have a specific shape. In particular, it must look as follows:
\[ L_1=\left( \begin{array}{cccccc} a_{1,1} & a_{1,2} & 0 & 0 & 0 & 0 \\ a_{2,1} & a_{2,2} & 0 & 0 & 0 & 0 \\ 0 & 0 & a_{3,3} & a_{3,4} & 0 & 0 \\ 0 & 0 & a_{4,3} & a_{4,4} & 0 & 0 \\ 0 & 0 & 0 & 0 & a_{5,5} & a_{5,6} \\ 0 & 0 & 0 & 0 & a_{6,5} & a_{6,6} \end{array} \right) \]
That is, we have divided our vector of 6 entries in three parts of two entries each, and aplied a linear transformation to each one of those three pairs. The entries of this matrix \(a_{i,j}\) will be the first part of our private key (to be precise, what we use for decryption is the inverse of this matrix, but to keep things simple just imagine that we keep this matrix, and apply its inverse when decrypting).
Ok, so now that we have aplied a linear map, we have a new vector
\[ (y_0,y_1,y_2,y_3,y_4,y_5) \]
It's time to apply one of those misterious matrix exponentiations. But first, we have to change the representation of our vector. The reason for that is that the matrix exponentiation does not act over \(\mathbb{F}_q\), but over \(\mathbb{F}_{q^2}\). That is, we have to see our vector of six entries in the field of \(2^{48}\) elements, as three elements in the field of \(2^{96}\) elements. That is actually quite easy, since we can just see \(\mathbb{F}_{q^2}\) as the set of degree 1 polynomials over \(\mathbb{F}_q\), modulo some irreducible polynomial. The actual choice of this polynomial is not important from the mathematical point of view, so just assume that we have picked some irreducible polynomial \(f_2\in \mathbb{F}_q[T]\) of degree 2, and consider our vector as
\[(Y_0,Y_1,Y_2)=(y_0+y_1 T, y_2+y_3 T, y_4+y_5 T)\]
Ok, so now we have our data expressed as elements on a bigger field. What do we need now to apply a matrix exponentiation? Well, a matrix of course! But in this case, the entries of the matrix are not elements of any finite field, just integers. Again, to make sure that the complexity of the total map does not explode, we must be careful with the choice of the matrix. Take a matrix of the form
\[ A=\left( \begin{array}{ccc} 2^{E_{1,1}} & 2^{E_{1,2}} & 0 \\ 2^{E_{2,1}} & 0 & 2^{E_{2,3}} \\ 0 & 2^{E_{3,2}} & 2^{E_{3,3}} \end{array} \right) \]
and apply it to our vector in \(\mathbb{F}_{q^2}\). But wait a second! this is not a linear transformation, this is a matrix exponentiation. This means that the matrix is not aplied as a multiplicative operator: it is aplied as an exponent. That is, mimic the process you follow yo multiply by a matrix, but change the products by exponentiations, and the sums as products.
Confusing? Ok, let's just put it down explicitely. Formally we are aplying an operation defined as follows:
\[ (Y_0,Y_1,Y_2)^{ \left( \begin{array}{ccc} 2^{E_{1,1}} & 2^{E_{1,2}} & 0 \\ 2^{E_{2,1}} & 0 & 2^{E_{2,3}} \\ 0 & 2^{E_{3,2}} & 2^{E_{3,3}} \end{array} \right) } = (Y_0^{2^{E_{1,1}}}Y_1^{2^{E_{1,2}}}, Y_0^{2^{E_{2,1}}}Y_2^{2^{E_{2,3}}}, Y_1^{2^{E_{3,2}}}Y_2^{2^{E_{3,3}}}) \]
Ok, so we know how to apply this matrix exponentiations. But wait a sec, how can we apply the inverse transformation? Don't worry, there is a way: just make sure that you matrix \(A\) is invertible over the integers modulo \(2^{96}-1\) and take its inverse there. Now, by using the finite field version of Fermat's little theorem it can be seen that the matrix exponentiation corresponding to the inverse matrix takes us back to the starting point (well, not exactly, if there are zeros involved, things behave differently, that is why we needed to add some padding to make sure that we got not zeros at this point).
One would be tempted to consider the polynomial \(f_2\) and the values \(E_{i,j}\) as part of the private key, but it happens that it would add no extra security (they are either irrelvant or can be easily recovered), so in order to keep keys more compact, they will be agreed on in advance, as part of the standard setup.
Now that we have applied the matrix exponentiation, we have a new vector of three entries in \(\mathbb{F}_{q^2}\). Just like we did before, that is the same as having a vector of six entries in \(\mathbb{F}_q\):
\[ (Z_0,Z_1,Z_2)=(z_0+z_1T,z_2+z_3T,z_4+z_5T) \leftrightarrow (z_0,z_1,z_2,z_3,z_4,z_5) \]
Next step is easy: just another linear transformation. In this case, the matrix will have a different form. In particular we will multiply our vector by the matrix
\[ L_2=\left( \begin{array}{cccccc} b_{1,1} & b_{1,2} & b_{2,3} & 0 & 0 & 0 \\ b_{2,1} & b_{2,2} & b_{3,3} & 0 & 0 & 0 \\ b_{3,1} & b_{3,2} & b_{3,3} & 0 & 0 & 0 \\ 0 & 0 & 0 & b_{4,4} & b_{4,5} & b_{4,6} \\ 0 & 0 & 0 & b_{5,4} & b_{5,5} & b_{5,6} \\ 0 & 0 & 0 & b_{6,4} & b_{6,5} & b_{6,6} \end{array} \right) \]
The \(b_i\) are just values in in \(\mathbb{F}_q\), and the only thing we have to make sure is that the matrix is invertible. As before, this matrix (or its inverse) will be part of the private key.
After multiplying by it, we get a new vector \((s_0,s_1,s_2,s_3,s_4,s_5)\in{\mathbb{F}_q}^6\).
The next step in our encryption process is a new matrix exponentiation; but this time it will happen in a bigger field. Now we will see our vector in \({\mathbb{F}_q}^6\) as a vector in \({\mathbb{F}_{q^3}}^2\), that is
\[ (s_0,s_1,s_2,s_3,s_4,s_5) \leftrightarrow (s_0+s_1S+s_2S^2,s_3+s_4S+s_5S^2)=(S_1,S_2) \] where the polynomials in \(S\) are considered modulo some irreducible one \(f_3\in \mathbb{F}_q[S]\) of degree three.
Now, just like we did before, we fix some matrix of the form
\[ \left( \begin{array}{cc} 2^{F_{1,1}} & 2 ^{F_{1,2}} \\ 2^{F_{2,1}} & 2^{F_{2,2}} \end{array} \right) \]
that is invertible modulo \(2^{144}-1\). Aplying the corresponding matrix exponentiation we obtain
\[ (S_1,S_2)^{\left( \begin{array}{cc} 2^{F_{1,1}} & 2 ^{F_{1,2}} \\ 2^{F_{2,1}} & 2^{F_{2,2}} \end{array} \right)}= (S_1^{2^{F_{1,1}}}S_2^{2^{F_{1,2}}}, S_1^{2^{F_{2,1}}}S_2^{2 ^{F_{2,2}}})= (R_1,R_2) \]
and again, we see it as a vector in \({\mathbb{F}_q}^6\)
\[ (R_1,R_2)=(r_0+r_1S+r_2S^2,r_3+r_4S+r_5S^2) \leftrightarrow (r_0,r_1,r_2,r_3,r_4,r_5) \]
Just as before, the choice of this matrix and the minimal polynomial will be fixed in the setup.
Now we apply a new linear map and we are done. The final part of our private key is another matrix of the form
\[ L3=\left( \begin{array}{cccccc} c_{1,1} & c_{1,2} & c_{1,3} & 0 & 0 & 0 \\ c_{2,1} & c_{2,2} & c_{2,3} & 0 & 0 & 0 \\ c_{3,1} & c_{3,2} & c_{3,3} & 0 & 0 & 0 \\ 0 & 0 & 0 & c_{4,4} & c_{4,5} & c_{4,6} \\ 0 & 0 & 0 & c_{5,4} & c_{5,5} & c_{5,6} \\ 0 & 0 & 0 & c_{6,4} & c_{6,5} & c_{6,6} \end{array} \right) \]
which will be multiplied by our vector to obtain the final cyphertext.
Summarizing, we have three elementary transformations, each of one easy to invert, that we compose to get our encryption map. But wait a second, those exponential transformations are not expressed as polynomial maps! Well, it turns out they are. If you try to follow the track of what happens when you compute it, you can verify it. So we can express the total composition of maps as a polynomial map. And the six polynomials that will express it will be the public key of our system.
You can also check that the strange choices we did (the shapes of the matrices, and the facts that the exponents are powers of two) will ensure that the polynomials that appear in this expression will have exactly 64 monomials. Moreover, since we have fixed the exponentiation matrices, each monomial will be the product of four powers of variables, and the exponents that appear will always be the same. So in order to encode the public key we only need to write the coefficients that appear. That is, the public key will consist on a list of \(64\cdot 6\) elements of \(\mathbb{F}_q\). The private key will be the coefficients of the linear maps, that is, \(48\) elements of \(\mathbb{F}_q\).
Now a little problem needs to be addressed: how do we compute the public key? One way would be to rewrite all elementary maps as explicit polynomial maps, and compose them all. But that is not specially efficient. There is a faster way. Since we know exactly what exponents will appear in the polynomials, for a given plain text we can compute the values of those powers. Then the final result will be a linear map applied to the vector of those products. The matrix that determines this map can be determined by linear algebra if we know enough pairs preimage-image. So we can choose a lot of random plaintexts, compute their corresponding monomials, and the corresponding cyphertext step by step (that is, applying the five elementary transformations). With enough of them, we can obtain the matrix with the coefficients of the polynomial transformation.
We have seen how the DME cryptosystem works with a specific choice of the setup. In particular, we have chosen a prime \(p=2\), a finite field \(F_{2^48}\) of characteristic \(p\), two positive integers \(n=2, m=3\), two field extensions of order \(n\) and \(m\) over our original field, and two special matrices \(A\) and \(B\). These parameters can be changed, and then we would obtain different incarnations of the cryptosystem.
In general, a setup would consist of the following choices:
With this choices, we have a cryptosystem that can encrypt vectors of \(n\cdot m\) entries in \(F\) (minus the padding). The choice \(n=2,m=3\) that we showed here is the one implemented in the submission for the NIST, but right after writing it, we found that there are ways to reduce the security of the private key, so we recommend other choices. \(n=2,m=6\) might be a better one.
It is still not clear what choices of matrices are the most secure. An intuitive guess is that the inverses having a big Hamming weight could be better than smaller ones, but it is just an intuition. Further research would be necessary to understand how these matrices should be chosen.