The DME cryptosystem

The DME cryptosystem

DME is a multivariate public-key cryptosystem for KEM, signature and encryption based on the composition of linear, affine and exponential maps over finite fields, developed by Ignacio Luengo at Universidad Complutense de Madrid.

The base field \(\mathbb{F}_q\) has \(q=2^e\) elements, and the cryptosystem works on \(n\) variables \(x_1,x_2,\ldots,x_n\). The underlying encryption map is the (interleaved) composition of certain invertible linear+affine maps \(L:(\mathbb{F}_q)^n\to(\mathbb{F}_q)^n\) and exponential maps \(E:(\mathbb{F}_{q^r})^{n/r}\to(\mathbb{F}_{q^r})^{n/r}\). The name DME used to stand for «double matrix exponentiation», since the first iteration of the cryptosystem had only two exponential maps in between three linear (without affine) maps. Currently, more general configurations are considered, so DME is no longer an acronym.
The linear maps that are used commonly in DME are either permutation matrices (used mainly in the first versions of DME) or sparse matrices consisting of a diagonal of square blocks of small size (typically \(2\times2\) or \(3\times3\)). However, no technical restriction exists for using a different type of linear maps, besides the potential increase in the size of the public and secret keys. The exponential maps \(E(z_1,\ldots,z_{n/r})=(\bar{z}^{M_1},\ldots,\bar{z}^{M_{n/r}})\) are given by an \((n/r)\times(n/r)\) integer matrix \(M\) such that \(\gcd(\det(M),q^r-1)=1\), which guarantees the invertibility of the map. The matrix \(M\) has only a few non-zero entries per row, and those entries are powers of \(2\). There is also an implicit \(\mathbb{F}_q\)-linear map \(\Phi:(\mathbb{F}_q)^n\to(\mathbb{F}_{q^r})^{n/r}\).
The private key consists of the sequence of all the maps that make the encryption map, and the public key of the \(n\) polynomials in \(n\) variables \(p_1(x_1,\ldots,x_n),\ldots,p_n(x_1,\ldots,x_n)\) with coefficients in \(\mathbb{F}_q\) that are obtained by composing all the maps that make the encryption map. For a reasonably chosen configuration of the maps, those polynomials do not have too many coefficients.
The encryption/decryption maps are not used directly in the cryptosystem, but combined with a standard padding scheme. For signatures, the PSS padding is currently used, although other alternatives can be also considered. For a more thorough description of the cryptosystem, we refer to the original article dme1.pdf by Ignacio Luengo. A patent in Spain was granted in 2018 for 20 years to DME (see patente.pdf).

NIST PQC 2017

For the NIST PQC 2017 call, we submitted a KEM cryptosystem called DME-(3,2,48), which consisted in two fixed exponential maps \(E_1:(\mathbb{F}_{q^2})^3\to(\mathbb{F}_{q^2})^3\) and \(E_2:(\mathbb{F}_{q^3})^2\to(\mathbb{F}_{q^3})^2\) interleaved between three linear maps without any affine component over the finite field \(\mathbb{F}_{2^{48}}\). The first two linears consisted of three \(2\times2\) blocks and the last of two \(3\times3\) blocks. The integer matrices that define the exponentials were:
\[
M_1 = \left[
\begin{array}{ccc}
2^{24} & 2^{59} & 0\\
2^{21} & 0 & 2^{28}\\
0 & 2^{29} & 2^{65}
\end{array}
\right],
\qquad
M_2 = \left[
\begin{array}{cc}
2^{50} & 2^{24}\\
2^{7} & 2^{88}
\end{array}
\right].
\]
The secret key stores the (non-zero) entries of the the linear maps and is \(288\) bytes long. The public key, which are \(6\) polynomials with \(64\) coefficients each, is \(2304\) bytes long. The encryption map defines an application \(\{0,1\}^{288}\to\{0,1\}^{288}\), i.e. it applies on sequences of \(36\) bytes. The shared secret, which was \(33\) bytes long, was padded with \(3\) bytes \(0x01\), and encrypted with the public key. The recipient decrypted the ciphertext to recover the shared secret and the padding applied (which was verified to be correct).

Two additional KEM cryptosystems were also submitted to NIST to provide different levels of security and for speed and key-size comparison. The first of those, called DME-(3,2,24), had the same structure over the smaller finite field \(q=2^{24}\). The matrices \(M_1\) and \(M_2\) were also slightly different. The second, called DME-(4,2,24), also worked over the small field, but had 8 variables instead of 6. Of course, that required a change in the last intermediate field, which was \(\mathbb{F}_{q^4}\) instead of \(\mathbb{F}_{q^3}\), and the structure of the linear and exponential maps.

A further KEM cryptosystem, called DME-KEM3 was developed after the submission round was closed, due to some concerns with certain structural attacks. The new idea was to start with 6 variables, then apply the map augmentation map \((x_1,\ldots,x_6)\mapsto(x_1,\ldots,x_6,x_1 x_3 x_5,0)\), and continue with an 8 variables DME scheme.

Unfortunately, a very specific attack (see dme2.pdf) was found for DME-(3,2,48) which was able to recover most of the secret key from the public key. Although the attack does not extend directly to 8 variables, it was enough to disqualify the submission to round 2.

NIST PQC 2023

For the NIST PQC 2023, we submitted a signature cryptosystem called DME-3rnds-8vars-64bits-sign (and also two other similar versions with 32 and 48 bits). The new design has three exponentials \(E_1,E_2,E_3:(\mathbb{F}_{q^2})^4\to(\mathbb{F}_{q^2})^4\) with a fixed structure but indeterminate entries. More precisely, the three matrices that define the exponential maps are
\[
\begin{aligned}
M_1 &= \left[\begin{array}{cccc}
2^{a_0} & 0 & 0 & 0 \\
2^{a_1} & 2^{a_2} & 0 & 0 \\
0 & 0 & 2^{a_3} & 0 \\
0 & 0 & 2^{a_4} & 2^{a_5}
\end{array}\right],\qquad
M_2 &= \left[\begin{array}{cccc}
2^{b_0} & 0 & 0 & 2^{b_1} \\
0 & 2^{b_2} & 0 & 0 \\
0 & 2^{b_3} & 2^{b_4} & 0 \\
0 & 0 & 0 & 2^{b_5}
\end{array}\right],\qquad
M_3 &= \left[\begin{array}{cccc}
2^{c_0} & 2^{c_1} & 0 & 0 \\
0 & 2^{c_2} & 0 & 2^{c_3} \\
0 & 2^{c_4} & 0 & 2^{c_5} \\
0 & 0 & 2^{c_6} & 2^{c_7}
\end{array}\right],
\end{aligned}
\]
respectively, with \(a_0,\ldots,a_5,b_0,\ldots,b_5,c_0,\ldots,c_7\in[0,127]\) such that
\[
\begin{aligned}
c_1&\equiv a_0+b_0+c_0-a_1-b_2\pmod{128},\\
c_7&\equiv a_3+b_4+c_6-a_4-b_5\pmod{128},\\
c_4&\equiv c_2+c_5-c_3+57\pmod{128}.
\end{aligned}
\]
The linear maps have \(4\) blocks of size \(2\times2\) each, but only the last three maps include an affine part. The secret key, which is 721 bytes long, includes the linear+affine coefficients and the values of \(a_0,\ldots,c_7\). The public key consists of 8 polynomials \(p_i(x_1,\ldots,x_8),\) of which \(p_1,p_2,p_7,p_8\) have exactly \(65\) monomials and \(p_3,p_4,p_5,p_6\) have \(25\) monomials. The structure of those monomials depends only on \(16\) values \(f_1,\ldots,f_{16}\) which are derived from \(a_0,\ldots,c_7\). After some extra tricks, the public key can be stored in only \(2889\) bytes. The encryption map defines an application \(\{0,1\}^{512}\to\{0,1\}^{512}\), which gives signatures of \(64\) bytes. Before applying the encryption map, a message is first passed through a PSS/SHA3 padding scheme with \(256\) random bits. On a laptop with an Intel(R) Core(TM) i7-8565U CPU at 1.80GHz, with 8Gb of RAM, running a Linux Mint 21 x86_64 operating system, the performance of the API primitives (for messages of 200 bytes) is the following: dme-keypair (251 usec), dme-sign (41 usec) and dme-open (12 usec).

DME 2024: DME^(-) and DME⁽⁺⁾

We developed two improved versions of the DME cryptosystem: DME⁽⁺⁾ for KEM and DME^(-) for signatures. The idea of DME^(-) is simple: instead of an encryption map \(\mathbb{F}_q^n\to\mathbb{F}_q^n\) which is (almost) a bijection, several polynomials are removed to get an map \(\mathbb{F}_q^n\to\mathbb{F}_q^m\) with \(m < n\) which is not longer one-to-one. This is useful for signatures, but unfortunately cannot be applied to KEM. We decided to also use an extra round with respect to our PQC 2023 submission, for a total of four exponentials and five linear maps (three of those with an affine part) and increase the size of the finite field to \(q=2^{128}\). The resulting DME^(-) scheme, called dme-4rnds-8vars-128bits-sign-half, defines an encryption map \(\mathbb{F}_{q}^8\to\mathbb{F}_q^4\) with exponential maps \(E_1,E_2,E_3,E_4:(\mathbb{F}_{q^2})^4\to(\mathbb{F}_{q^2})^4\) given by
\[
\begin{aligned}
M_1 &= \left[\begin{array}{cccc}
2^{a_0} & 0 & 0 & 0 \\
2^{a_1} & 2^{a_2} & 0 & 0 \\
0 & 0 & 2^{a_3} & 0 \\
0 & 0 & 2^{a_4} & 2^{a_5}
\end{array}\right],\quad
M_2 &= \left[\begin{array}{cccc}
2^{b_0} & 0 & 0 & 2^{b_1} \\
0 & 2^{b_2} & 0 & 0 \\
0 & 2^{b_3} & 2^{b_4} & 0 \\
0 & 0 & 0 & 2^{b_5}
\end{array}\right],\\
M_3 &= \left[\begin{array}{cccc}
0 & 2^{c_0} & 0 & 0 \\
2^{c_1} & 2^{c_4} & 0 & 0 \\
0 & 0 & 0 & 2^{c_2} \\
0 & 0 & 2^{c_3} & 2^{c_5}
\end{array}\right],\quad
M_4 &= \left[\begin{array}{cccc}
2^{d_0} & 2^{d_4} & 0 & 0 \\
0 & 0 & 2^{d_1} & 2^{d_5} \\
2^{d_2} & 0 & 0 & 2^{d_6} \\
0 & 2^{d_3} & 2^{d_7} & 0
\end{array}\right],
\end{aligned}
\]
respectively, with \(a_0,\ldots,a_5,b_0,\ldots,b_5,c_0,\ldots,c_5,d_0,\ldots,d_7\in[0,255]\) such that
\[
\begin{aligned}
b_4&\equiv a_1+b_3-a_0-b_0+a_4-a_3+b_1+61\pmod{256},\\
c_4&\equiv a_0+b_0+c_1-a_1-b_2\pmod{256},\\
c_5&\equiv a_3+b_4+c_3-a_4-b_5\pmod{256},\\
d_4&\equiv a_1+b_2+c_0+d_0-a_0-b_0-c_1\pmod{256},\\
d_5&\equiv a_4+b_5+c_2+d_1-a_3-b_4-c_3\pmod{256},\\
d_6&\equiv b_2+c_0+d_2-b_3-c_3\pmod{256},\\
d_7&\equiv b_1+c_1+d_3-b_5-c_2\pmod{256}.
\end{aligned}
\]
The linear maps have \(4\) blocks of size \(2\times2\) each, but only the last three maps include an affine part. The secret key, which is 1619 bytes long, includes the linear+affine coefficients and the values of \(a_0,\ldots,d_7\). The public key consists of 4 polynomials \(p_1(x_1,\ldots,x_8),\) \(p_3(x_1,\ldots,x_8),\) \(p_5(x_1,\ldots,x_8)\) and \(p_7(x_1,\ldots,x_8),\) of which \(p_1,p_3\) have exactly \(85\) monomials and \(p_5,p_7\) have \(109\) monomials. The structure of those monomials depends only on \(16\) values \(f_1,\ldots,f_{16}\) which are derived from \(a_0,\ldots,d_7\). After some extra tricks, the public key can be stored in only \(6215\) bytes. The encryption map defines an application \(\{0,1\}^{1024}\to\{0,1\}^{512}\), which gives signatures of \(128\) bytes. Before applying the encryption map, a message is first passed through a PSS/SHA3 padding scheme with \(128\) random bits. On a laptop with a Intel(R) Core(TM) i7-8565U CPU at 1.80GHz, with 8Gb of RAM, running a Linux Mint 21 x86_64 operating system, the performance of the API primitives (for messages of 200 bytes) is the following: dme-keypair (2477 usec), dme-sign (136 usec) and dme-open (54 usec). The DME⁽⁺⁾ version has an encryption map \(\mathbb{F}_q^n\to\mathbb{F}_q^{m}\) for some \(m > n\) which is injective but not surjective. The secret key consists of some combination of linear+affine and exponential maps, producing \(n\) polynomials in \(n\) unknowns, which is augmented by introducing \(m-n\) random polynomials with the same monomial structure than some of the first \(n\). A final component of the secret key is a big invertible linear map that combine all these polynomials. The public key is just the final \(m\) polynomials. This type of cryptosystem is useful for KEM, but not for signatures. For our submission, we started with a standard DME in 8 variables and 8 polynomials over \(\mathbb{F}_{2^{64}}\). The same exponential matrices as above were used, but no affine components were included. This gave 8 polynomials of which the first four have 48 terms each and the last four have 54 terms each. We augmented the scheme by introducing 8 extra random polynomials and combined them with the first eight polynomials using a \(16\times16\) linear map consisting in four \(4\times 4\) blocks. The resulting public key has in total 816 coefficients, which corresponds to a public key size of 6535 bytes. The secret key has 4435 bytes, since only the random polynomials have to be stored, plus the coefficientes of the linear matrices and exponents of \(M_1,M_2,M_3,M_4\). On the same laptop as above, the performance of the KEM primitives is: dme-kem-keypair (480 usec), dme-kem-enc (22 usec) and dme-kem-dec (43 usec). For comparison, the standard non-augmented scheme with the same parameters has a public key of 3271 bytes, a secret key of 659 bytes, and the performace of the KEM primitives are: dme-kem-keypair (458 usec), dme-kem-enc (13 usec) and dme-kem-dec (33 usec).