GeMSS (Great Multivariate Short Signature) [1] is a multivariate based signature scheme [3]. It has one of the smallest signature and private key sizes, but has a relatively large public key. It uses the Hidden Field Equations (HFE) with minus and vinegar modifiers (HFEv-) [4]. Overall GeMSS has an optimal private key size (16 bytes for 128 bit security and 32 bytes for 256 bit security) and one of the most signature sizes of just 33 bytes. Unfortunately, like other multivariant methods, it produces a relatively large public key: 352,188 bytes (for 128 bit security) and 1,237,964 bytes (for 192-bit security). At present, it is a finalist for the alterative digital signature for the NIST PQC (Post Quantum Cryptography) competition. Overall the HFEv- method can only be used for digital signatures as there are more variables than equations. In this case we will implement GeMSS 128 can which has parameters of \((q, n, v, D, a)\) and which map to (2, 174, 12, 513, 12).
GeMSS - Digital Signature |
Outline
The following provides an analysis of the PCQ methods for digital signing:
Method Public key size Private key size Signature size Security level ------------------------------------------------------------------------------------------------------ Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice Rainbow Level Ia (Oil-and-Vineger) 161,600 103,648 66 1 (128-bit) Multivariate (UOV) Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) Multivariate (UOV) Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) Multivariate (UOV) Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based Picnic 3 Full 49 73 71,179 3 (192-bit) Symmetric GeMSS 128 352,188 16 33 1 (128-bit) Multivariate (HFEv-) GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate (HFEv-) RSA-2048 256 256 256 ECC 256-bit 64 32 256
For performance on M4 (ARM Cortex-M4 dev) [2] and measured in CPU operations per second. Note, no GeMMS assessment has been performed in [2], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Key Generation Sign Verify ------------------------------------------------------------------------------------------------------ Crystals Dilithium 2 1,400,412 6,157,001 1,461,284 1 (128-bit) Lattice Crystals Dilithium 3 2,282,485 9,289,499 2,228,898 3 (192-bit) Lattice Crystals Dilithium 5 3,097,421 8,469,805 3,173,500 5 (256-bit) Lattice Falcon 512 (Lattice) 197,793,925 38,090,446 474,052 1 (128-bit) Lattice Falcon 1024 480,910,965 83,482,883 977,140 3 (256-bit) Lattice Rainbow Level Ia 41,347,565 101,874,410 77,433,705 1 (128-bit) UOV Rainbow Level IIIa 66,072,054 123,878,322 95,330,045 3 (192-bit) UOV Rainbow Level Vc 109,063,616 405,205,796 269,012,028 5 (256-bit) UOV Sphincs SHA256-128f Simple 16,552,135 521,963,206 20,850,719 1 (128-bit) Hash-based Sphincs SHA256-192f Simple 24,355,501 687,693,467 35,097,457 3 (128-bit) Hash-based Sphincs SHA256-256f Simple 64,184,968 1,554,168,401 36,182,488 5 (128-bit) Hash-based
For stack memory size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no GeMSS assessment has been performed in [2], as GeMSS would take up too much memory:
Method Key generation Sign Verify ---------------------------------------------------------------- Crystals Dilithium 2 (Lattice) 36,424 61,312 40,664 Crystals Dilithium 3 50,752 81,792 55,000 Crystals Dilithium 5 67,136 104,408 71,472 Falcon 512 (Lattice) 1,680 2,484 512 Falcon 1024 1,680 2,452 512 Rainbow Level Ia (Oil-and-Vineger) 2,969 4,720 2,732 Rainbow Level IIIa 3,216 3,224 1,440 Rainbow Level Vc 3,736 6,896 4,928 Sphincs SHA256-128f Simple 2,192 2,248 2,544 Sphincs SHA256-192f Simple 3,512 3,640 3,872 Sphincs SHA256-256f Simple 5,600 5,560 5,184
Method
With multivariate cryptography, we have \(n\) variables within polynomial equations. For example if we have four variables (\(w, x, y, z\)) and an order of two, we could have [here]:
\(w^2 + 4wx + 3x^2 + 2 wy - 4wz + 2wx + 6xz = 387\)
In this case I know that the solution is \(w=7, x=4, y=5, z=6\). For a matrix form we could represent this as:
\begin{multline} M =\begin{pmatrix} w & x & y & z \end{pmatrix} \begin{pmatrix} 1 & 2 & 1 & 1\\ 2 & 3 & 3 & -2\\ 1 & 3 & 0 & 0\\ 1 & -2 & 0 & 0\\ \end{pmatrix} \begin{pmatrix} w\\ x\\ y\\ z\\ \end{pmatrix} \end{multline}
In order to contrain the values we get, we normally perform \(\pmod p\) operation and where \(p\) is a prime number. This is known as finite field, and are numbers are always constrained between \(0\) and \(p-1\). For example if we select \(p=97\) we have:
\(w^2 + 4wx + 3x^2 + 2 wy - 4wz + 2wx + 6xz = 5 \pmod {97}\)
Now there are multiple solutions to this now for \(w, x, y, z\), so we define \(n\) multivariate polynomials. For example:
\(w^2 + 4wx + 3x^2 + 2wy -4xz + 2wx + 6xy = 96 \pmod{97}\)
\(5w^2 + 3wx + 3x^2 + 4wy -xz + 8wx + 4xy = 36 \pmod{97}\)
\(4w^2 + 5wx + 3x^2 + 2wy -5xz + 3wx + 6xy = 95 \pmod{97}\)
\(6w^2 + 7wx + 4x^2 + 2wy -8xz + 2wx + 9xy = 17 \pmod{97}\)
The solution to this is: \(w=7, x=4, y=5, z=6\), but it is extremely difficult to solve. Here is the code to prove the values:
import numpy as np p=97 w=7 x=4 y=5 z=6 def printM(M): rtn = ""+str(M[0][0])+"w^2 + "+str(M[0][1]+M[1][0])+"wx + "+str(M[1][1])+"x^2 + "+str(M[0][2]+M[2][0])+"wy + "+str(M[1][3]+M[3][1])+"xz + " +str(M[0][3]+M[3][0])+"wz + "+str(M[1][2]+M[2][1])+"xy" return rtn m=[w,x,y,z] m_dash = np.transpose(m) M0=[[1,2,1,1],[2,3,3,-2],[1,3,0,0],[1,-2,0,0]] M1=[[5,2,1,2],[1,3,2,2],[3,2,0,0],[6,-3,0,0]] M2=[[4,2,2,1],[3,3,3,-2],[0,3,0,0],[2,-3,0,0]] M3=[[6,2,1,1],[5,4,3,-3],[1,6,0,0],[1,-5,0,0]] print ("p=",p) print ("\nm=",m) print ("m^T=",m_dash) print ("\nM0:",M0) print ("M1:",M1) print ("M2:",M2) print ("M3:",M3) # res = m . M0 . m^{-1} res1= np.dot(np.dot(m,M0),m_dash) % p res2= np.dot(np.dot(m,M1),m_dash) % p res3= np.dot(np.dot(m,M2),m_dash) % p res4= np.dot(np.dot(m,M3),m_dash) % p print () print ("M0=",printM(M0)) print ("M1=",printM(M1)) print ("M2=",printM(M2)) print ("M3=",printM(M3)) print ("\nRes0=",res1) print ("Res1=",res2) print ("Res2=",res3) print ("Res2=",res4)
and here is a sample run:
p= 97 m= [7, 4, 5, 6] m^T= [7 4 5 6] M0: [[1, 2, 1, 1], [2, 3, 3, -2], [1, 3, 0, 0], [1, -2, 0, 0]] M1: [[5, 2, 1, 2], [1, 3, 2, 2], [3, 2, 0, 0], [6, -3, 0, 0]] M2: [[4, 2, 2, 1], [3, 3, 3, -2], [0, 3, 0, 0], [2, -3, 0, 0]] M3: [[6, 2, 1, 1], [5, 4, 3, -3], [1, 6, 0, 0], [1, -5, 0, 0]] M0= 1w^2 + 4wx + 3x^2 + 2wy + -4xz + 2wz + 6xy M1= 5w^2 + 3wx + 3x^2 + 4wy + -1xz + 8wz + 4xy M2= 4w^2 + 5wx + 3x^2 + 2wy + -5xz + 3wz + 6xy M3= 6w^2 + 7wx + 4x^2 + 2wy + -8xz + 2wz + 9xy Res0= 96 Res1= 36 Res2= 95 Res2= 17
Oil and Vineger method
Method
With multivariate cryptography, we have \(n\) variables within polynomial equations. For example if we have four variables (\(w, x, y, z\)) and an order of two, we could have [here]:
\(w^2 + 4wx + 3x^2 + 2 wy - 4wz + 2wx + 6xz = 387 \)
In this case I know that the solution is \(w=7\), \(x=4\), \(y=5\) and \(z=6\). For a matrix form we could represent this as:
\begin{multline} M =\begin{pmatrix} w & x & y & z \end{pmatrix} \begin{pmatrix} 1 & 2 & 1 & 1\\ 2 & 3 & 3 & -2\\ 1 & 3 & 0 & 0\\ 1 & -2 & 0 & 0\\ \end{pmatrix} \begin{pmatrix} w\\ x\\ y\\ z\\ \end{pmatrix} \end{multline}
This matrix has a trapdoor, and where we define our vinegar and oil variables. The vinegar variables are secret and which we will only know, and the oil ones will be discovered if we know the vinegar variables. The trap door is that we do not let the oil variables mix, and where they do mix in the matrix we will have zeros (the trap door):
In order to constrain the values we get, we normally perform \(\pmod p\) operation and where \(p\) is a prime number. This is known as finite field, and are numbers are always constrained between \(0\) and \(p-1\). For example if we select \(p=97\) we have:
\(w^2 + 4wx + 3x^2 + 2 wy - 4wz + 2wx + 6xz = 5 \pmod {97}\)
Now there are multiple solutions to this now for \(w, x, y, z\), so we define \(n\) multivariate polynomials. For example:
\(w^2 + 4wx + 3x^2 + 2wy -4xz + 2wx + 6xy = 96 \pmod{97}\)
\(5w^2 + 3wx + 3x^2 + 4wy -xz + 8wx + 4xy = 36 \pmod{97}\)
\(4w^2 + 5wx + 3x^2 + 2wy -5xz + 3wx + 6xy = 95 \pmod{97}\)
\(6w^2 + 7wx + 4x^2 + 2wy -8xz + 2wx + 9xy = 17 \pmod{97}\)
Now we have vinegar variables of \(w\) and \(x\) and oil variables of \(y\) and \(z\). If we know \(w\) and \(x\) it will now become easy to determine oil variables. For example if \(w=7\) and \(x=4\), we get:
\(49 + 112 + 48 + 14y -16z + 14z + 24y = 96 \pmod{97}\)
\(245 + 84 + 48 + 28y -4z + 56z + 16y = 36 \pmod{97}\)
and gives:
\(209 + 38y -2z = 96 \pmod{97}\)
\(377 + 44y + 52z = 36 \pmod{97}\)
and gives:
\(38 y + 95 z = -113 \pmod{97}\)
\(44 y + 52 z = -341 \pmod{97}\)
and gives:
\(38 y + 95 z = 81 \pmod{97}\)
\(44 y + 52 z = 47 \pmod{97}\)
In a matrix form this becomes:
\begin{multline} \begin{pmatrix} 38 & 95\\ 44 & 52\\ \end{pmatrix} \begin{pmatrix} y\\ z \end{pmatrix} =\begin{pmatrix} 81\\ 47 \end{pmatrix} \pmod {97} \end{multline}
and we can solve for \(y\) and \(z\) with:
\begin{multline} \begin{pmatrix} y\\ z \end{pmatrix} = {\begin{pmatrix} 38 & 95\\ 44 & 52\\ \end{pmatrix}}^{-1} \begin{pmatrix} 81\\ 47 \end{pmatrix} \pmod {97} \end{multline}
We can now easily solve this to get \(y=5\) and \(z=6\). Here is the code:
Coding
The following is an implementation of GeMMS:
#include stdio.h #include stdint.h #include stdlib.h #include time.h #include "api.h" #define MLEN 59 char *showhex(uint8_t a[], int size) ; // int randombytes (unsigned char* random_array, unsigned long long num_bytes); char *showhex(uint8_t a[], int size) { char *s =malloc(size * 2 + 1); for (int i = 0; i < size; i++) sprintf(s + i * 2, "%02x", a[i]); return(s); } int main(void) { size_t j; int ret; uint8_t b; uint8_t m[MLEN + CRYPTO_BYTES]; uint8_t m2[MLEN + CRYPTO_BYTES]; // uint8_t sm[MLEN + CRYPTO_BYTES]; uint8_t pk[CRYPTO_PUBLICKEYBYTES+1]; uint8_t sk[CRYPTO_SECRETKEYBYTES+1]; unsigned char sm[sizeof(m) + CRYPTO_BYTES]; long long unsigned int smlen = sizeof(sm); unsigned char mprime[50] = { 0 }; long long unsigned int mlen = sizeof(mprime); printf("NAME: %s\n", CRYPTO_ALGNAME); printf("CRYPTO_PUBLICKEYBYTES = %d\n", CRYPTO_PUBLICKEYBYTES); printf("CRYPTO_SECRETKEYBYTES = %d\n", CRYPTO_SECRETKEYBYTES); printf("CRYPTO_BYTES = %d\n", CRYPTO_BYTES); randombytes(m, MLEN); printf("\nMessage: %s\n",showhex(m,MLEN)); crypto_sign_keypair(pk, sk); crypto_sign(sm, &smlen, m, MLEN, sk); ret = crypto_sign_open(m2, &mlen, sm, smlen, pk); if(ret) { fprintf(stderr, "Verification failed\n"); return -1; } if(smlen != MLEN + CRYPTO_BYTES) { fprintf(stderr, "Signed message lengths wrong\n"); return -1; } if(mlen != MLEN) { fprintf(stderr, "Message lengths wrong\n"); return -1; } for(j = 0; j < MLEN; ++j) { if(m2[j] != m[j]) { fprintf(stderr, "Messages don't match\n"); return -1; } } printf("\nAlice Public key (Showing 1/1024th of signature): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/1024)); printf("Alice Secret key: %s\n",showhex(pk,CRYPTO_SECRETKEYBYTES)); printf("Signature: %s\n",showhex(sm,smlen)); return 0; } int randombytes (unsigned char* random_array, unsigned long long num_bytes) { // unsigned char *random_array = malloc (num_bytes); size_t i; srand ((unsigned int) time (NULL)); for (i = 0; i < num_bytes; i++) { random_array[i] = rand (); } return 0; }
A sample run of Picnic shows that the public key size is just 33 bytes, the secret key is 16 bytes, and the digital signature of 352,188 bytes:
NAME: GeMSS CRYPTO_PUBLICKEYBYTES = 352188 CRYPTO_SECRETKEYBYTES = 16 CRYPTO_BYTES = 33 Message: 3b258483e39733a336c865085f86b99d2cbb8531c04d287b88449c5c702b4b6556b82499beafed74c803db2c603e6036b524440cec93f72e15ae26 Alice Public key (Showing 1/1024th of signature): 801fbc47becd27cfe57f8541711247b8fd926f66f64ef1e6e9ff9e450b064c3ae435aa0640be216f06ba8a6076282eb1ac56a93fa9c0a0b86da2e881807844656ec1616357723a96ee7f7e3f218e207cf4947e7cf2592afaa9379cece8ad0ee63e4ff1db73173204c505ff45fb31d235aa1fe3d335b77ae9b85318c083526e348c3bc7b4943f823193613bd2049188a343f832649bc972e46f8801856c320b3ba8aeed9d87c8cb57bc1bf73ba7b3ac570cfc108166de4cea7c9ce696f835c4e672f998a17d74bd77700a37d6db215008c21069e611220a16b0dd5ccbe00a8b023f8dd06dc4681431f5023eb706a946e5f581e1e8d47ea71d0328bef7c2c3b888f883ff0f3a45a6f9cdad319eabd13c896b5a3a14a55c74d6977c78a8aa1142b1261255ec47fad6071e79ecf7627af4b33422c08cf8d1e2546dc771ae27de0c9ae5ca263d689ffd10928138970b552ed196f97abef0fff9 Alice Secret key: 801fbc47becd27cfe57f8541711247b8 Signature: 641a4b76ce9d0b79d09f9c6c5d9c1c7f35f2c497495fc50b95b90b63b4502f84013b258483e39733a336c865085f86b99d2cbb8531c04d287b88449c5c702b4b6556b82499beafed74c803db2c603e6036b524440cec93f72e15ae26
References
[1] Casanova, A., Faugere, J. C., Macario-Rat, G., Patarin, J., Perret, L., & Ryckeghem, J. (2017). GeMSS: a great multivariate short signature (Doctoral dissertation, UPMC-Paris 6 Sorbonne Universités; INRIA Paris Research Centre, MAMBA Team, F-75012, Paris, France; LIP6-Laboratoire d'Informatique de Paris 6) [paper].
[2] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [paper].
[3] Mohamed, M. S. E., & Petzoldt, A. (2016, December). The shortest signatures ever. In International Conference on Cryptology in India (pp. 61-77). Springer, Cham [here].
[4] Patarin, J., Courtois, N., & Goubin, L. (2001, April). Quartz, 128-bit long digital signatures. In Cryptographers’ Track at the RSA Conference (pp. 282-297). Springer, Berlin, Heidelberg [paper].