Mixing Oil and Vinegar Works in a Post-Quantum World
Dilithium (aka ML-DSA — FIPS 204), Falcon, and SPHINCS+ (aka SLH-DSA — FIPS 205) have been approved for the NIST PQC standardisation. Now they are reviewing an additional round of signatures, and with Round 2, we now have:
- Multivariate Signatures (4): MAYO, QR-UOV, SNOVA, and UOV (Unbalanced Oil and Vinegar).
- MPC-in-the-Head Signatures (5): MIRA/MiRitH (MinRank in the Head), MQOM (MQ on my Mind), PERK, RYDE, and SDitH (Syndrome Decoding in the Head).
- Lattice-based Signatures (1): HAWK.
- Code-based Signatures (2): CROSS (Codes and Restricted Objects Signature), and LESS (Linear Equivalence)
- Symmetric-based Signatures (1): FAEST.
- Isogeny Signatures (1): SQIsign.
We can see we have four multivariate methods that are based on the Oil and Vineger approaches. Unfortunately, within Round 1 of the NIST PQC digital assessment, the parameters set in the original specification for Rainbow were cracked [here] and took around 50 hours on an eight-core laptop. Overall, Rainbow has a multivariate cryptography approach but does not have strong security proofs and a weak parameter set.
PROV (PRovable unbalanced Oil and Vinegar) [1] uses a multivariate cryptography-based approach to create a Post Quantum Robust (PQC) digital signature. While there have been recent attacks on multivariate methods, PROV provides security proof. The proof is similar to the MAYO signature scheme where there is a larger oil space than the output of the scheme (defined often as UOV (Unbalanced Oil and Vinegar). The UOV approach was first defined by Kipnis, Patarin and Goubin [2] and integrates a hash-and-sign signature scheme into the GPV framework [3]. It was adapted in [4] for multivariate cryptography methods.
Generally, multivariate cryptography generates relatively short signatures but has relatively long public and private keys.
The multivariate polynomial problem
The multivariate polynomial problem is now being applied in quantum robust cryptography, where we create a trap door to allow us to quickly solve the n variables with m equations (which are multivariate polynomials).
One scheme that can be used is the Unbalanced Oil and Vinegar scheme and was created by J. Patarin. A signature is created with a number of equations:
y1=f(x1,x2…xn)
y2=f(x1,x2…xn)…
ym=f(x1,x2…xn)
where y1,y2,…ym is the message that is to be signed, and where x1,x2…xn is the signature for the message.
So a simple example:
5 x+ 4y + 10 w + 9 z = 99
6 x + 3 y + 2 w + 3 z =38
8 x + 2 y + 7 w + z = 51
x + 9 y + 4 w + 6 z =57The message is 99, 38, 51 and 57, and the signature is then 5, 4, 10 … 6.
Oil and Vinegar
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²+4wx+3x²+2wy−4wz+2wx+6xz=387
Generally, this is a hard problem to solve, so we want to make it easy if we know a secret. 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:
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 contain the values we get, we normally perform (mod p) operation and where p is a prime number. This is known as a finite field, and the numbers are always constrained between 0 and p−1. For example, if we select p=97 we have:
w²+4wx+3x²+2wy−4wz+2wx+6xz=5 (mod 97)
Now, there are multiple solutions to this for w,x,y, and z, so we define n multivariate polynomials. For example:
w²+4wx+3x²+2wy−4xz+2wx+6xy=96 (mod 97)
5w²+3wx+3x²+4wy−xz+8wx+4xy=36 (mod 97)
4w²+5wx+3x²+2wy−5xz+3wx+6xy=95 (mod 97)
6w²+7wx+4x²+2wy−8xz+2wx+9xy=17 (mod 97)
With large values of the variables, this is a known hard problem to solve. So now we define our 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 (mod 97)
245+84+48+28y−4z+56z+16y=36 (mod 97)
and gives:
209+38y−2z=96 (mod 97)
377+44y+52z=36 (mod 97)
and gives:
38y+95z=−113 (mod 97)
44y+52z=−341 (mod 97)
and gives:
38y+95z=81 (mod 97)
44y+52z=47 (mod 97)
This is now a simple linear equation (in a modulo form), and which can be easily solved. In a matrix form this becomes:
and we can solve for y and z with:
We can now easily solve this with y=5 and z=6. Here is the code [here]:
import numpy as np
from inv import modMatInv
import sysp=97w=7
x=4
if (len(sys.argv)>1):
w=int(sys.argv[1])
if (len(sys.argv)>2):
x=int(sys.argv[2])if (len(sys.argv)>3):
p=int(sys.argv[3])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 rtndef revealM(M,w,x):
rtn = ""+str(M[0][0]*w*w) +" + "+str((M[0][1]+M[1][0])*w*x)+" + "+str(M[1][1]*x*x)+" + "+str((M[0][2]+M[2][0])*w)+"y + "+str((M[1][3]+M[3][1])*x)+"z + " +str((M[0][3]+M[3][0])*w)+"z + "+str((M[1][2]+M[2][1])*x)+"y"
return rtn
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 ("\nM0:",M0)
print ("M1:",M1)
print ("M2:",M2)
print ("M3:",M3)# res = m . M0 . m^{-1}
res0=96
res1=36
res2=95
res3=17a=(res0-(M0[0][0]*(w*w)+(M0[0][1]+M0[1][0])*w*x + (M0[1][1])*x*x ) ) %p
b=(res1-(M1[0][0]*(w*w)+(M1[0][1]+M1[1][0])*w*x + (M1[1][1])*x*x ) ) %pfactor1=( ((M0[0][2]+M0[2][0])*w) + ((M0[1][2]+M0[2][1]) *x) ) %p
factor2=( ((M0[0][3]+M0[3][0])*w) + ((M0[1][3]+M0[3][1]) *x) ) %p
factor3=( (M1[0][2]+M1[2][0])*w) + ((M1[1][2]+M1[2][1]) *x) %p
factor4=( ((M1[0][3]+M1[3][0])*w) + ((M1[1][3]+M1[3][1])*x)) %pprint ("w=",w)
print ("x=",x)
print (printM(M0))
print (printM(M1))
print ()
print (revealM(M0,w,x))
print (revealM(M1,w,x))
print ()
print (str(factor1)+"y+"+str(factor2)+"z="+str(a))
print (str(factor3)+"y+"+str(factor4)+"z="+str(b))
print ()
A = np.array([[factor1,factor2], [factor3,factor4]])
B = np.array([a,b])invA = modMatInv(A,p)print (invA)res = np.dot(invA,B) % p
print ("y=",res[0])
print ("z=",res[1])And a sample run [here]:
p= 97M0: [[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]]
w= 7
x= 4
1w^2 + 4wx + 3x^2 + 2wy + -4xz + 2wz + 6xy
5w^2 + 3wx + 3x^2 + 4wy + -1xz + 8wz + 4xy49 + 112 + 48 + 14y + -16z + 14z + 24y
245 + 84 + 48 + 28y + -4z + 56z + 16y38y+95z=81
44y+52z=47Inverse matrix:
[[63. 36.]
[81. 5.]]
y= 5.0
z= 6.0Some implementations
An implementation of PROV is:
https://asecuritysite.com/pqc/prov_sign
For the key sizes of Dilithium, Falcon and SPHINCS+ compared with a range of additional Round 1 signatures compared with PROV, we can see that the public and private key is much larger than Dilithium, Falcon and SPHINCS+, but a much smaller signature [here]:
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
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
PROV-1 68,326 203,752 160 1 (128-bit) Multivariate
PROV-2 215,694 666,216 232 3 (192-bit) Multivariate
PROV-3 524,192 1,597,568 304 5 (256-bit) MultivarThe performance for PROV is much weaker than Dilithium and Falcon (for cycles for operation):
Method Keygen Sign Verify
------------------------------------------------------------
Dilithium 2 300,751 1,081,174 327,362 (Unoptimized, Ref, Skylake)
Dilithium 3 544,232 1,713,783 522,267
Dilithium 5 819,475 2,383,399 871,609
Falcon-512 19,872,000 386,678 82,339 (Intel e5-8259U 2.3GHz)
Falcon-1024 63,135,000 961,208 205,128
PROV-1 1,171,537,400 38,962,000 52,797,800 Intel Core i5-7260U CPU at 2.20GHz
PROV-3 5,558,390,200 129,890,200 173,978,200
PROV-5 16,845,708,000 300,641,000 401,456,000For UOV:
Overall the key sizes are:
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
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
RSA-2048 256 256 256
ECC 256-bit 64 32 256
NIST Round 1 Additional Signatures (Multivariate)
-----------------------------------
UOV Level I 278,432 237,896 128 1 (128-bit) Multivariate
UOV Level III 1,225,440 1,044,320 200 3 (192-bit) Multivariate
UOV Level V 2,869,440 2,436,704 260 5 (256-bit) Multivariate
dme-3rnds-8vars-32bits-sign 1449 369 32 1 (128-bit) Multivariate
dme-3rnds-8vars-48bits-sign 2169 545 48 1 (128-bit) Multivariate
dme-3rnds-8vars-64bits-sign 2880 721 64 1 (128-bit) Multivariate
PROV-1 68,326 203,752 160 1 (128-bit) Multivariate
PROV-2 215,694 666,216 232 3 (192-bit) Multivariate
PROV-3 524,192 1,597,568 304 5 (256-bit) Multivariate
QR-UOV-I 20,657 256 331 1 (128-bit) Multivariate
QR-UOV-III 55,173 385 489 3 (192-bit) Multivariate
QR-UOV-V 135,439 512 662 5 (256-bit) Multivariate
SNOVA-I 1,016 48 240 1 (128-bit) Multivariate
SNOVA-III 4,104 64 376 3 (192-bit) Multivariate
SNOVA-IV 8,016 80 576 5 (256-bit) Multivariate
TUOV-I 278,432 239,391 112 1 (128-bit) Multivariate
TUOV-III 1,048,279 1,225,440 184 3 (128-bit) Multivariate
TUOV-V 2,869,440 2,443,711 244 5 (128-bit) Multivariate
VOX-128 9,104 35,120 102 1 (128-bit) Multivariate
VOX-192 30,351 111,297 184 3 (192-bit) Multivariate
VOX-256 82,400 292,160 300 5 (256-bit) MultivariateConclusions
It looks likely that multivariate methods will be stronger in the NIST competition this time.
References
[1] Faugere, J. C., Fouque, P. A., Macario-Rat, G., Minaud, B., & Patarin, J. PROV: PRovable unbalanced Oil and Vinegar Specification v1. 0–06/01/2023..
[2] Kipnis, A., Patarin, J., & Goubin, L. (1999, April). Unbalanced oil and vinegar signature schemes. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 206–222). Berlin, Heidelberg: Springer Berlin Heidelberg.
[3] Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008, May). Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing (pp. 197–206).
[4] Kosuge, H., & Xagawa, K. (2024, April). Probabilistic hash-and-sign with retry in the quantum random oracle model. In IACR International Conference on Public-Key Cryptography (pp. 259–288). Cham: Springer Nature Switzerland.
[5] PROV GitHub here
