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). In the following example we sign a message with the private key and verify with the public key. In this case we use the Rainbow cryptography method [here]:
Unbalanced Oil and Vinegar (UOV) - Rainbow Method |
Outline
The RSA encryption method uses the multiplication of two prime numbers to create a public modulus (N). Unfortunately the factorization of N is fairly easy if we use a quantum computer. Thus NIST are now looking for contenders for the replacement of RSA, and other methods such as El Gamal, for a quantum computer age.
Currently we often use symmetric encryption (such as AES) for the main encryption, and then use asymmetric encryption (such as RSA) to protect the symmetric key and/or to prove identity. Often we use RSA to sign an identity, such as using the private key to sign, and then the associated public key to validate the signature.
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:
\(y_1 = f(x_1, x_2 ... x_n)\\ y_2 = f(x_1,x_2 ... x_n)\\ ...\\ y_m= f(x_1,x_2 ... x_n)\)
where \(y_1, y_2, ... y_m\) is the message that is to be signed, and where \(x_1, x_2 ... x_n\) 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 =57
The message is 99, 38, 51 and 57, and the signature is then 5, 4, 10 ... 6.
Code
The following provides an outline of the code, where we sign "Hello" with the private key and verify with the public key:
package rain; import java.math.BigInteger; import java.security.SecureRandom; import org.bouncycastle.crypto.AsymmetricCipherKeyPair; import org.bouncycastle.crypto.digests.SHA224Digest; import org.bouncycastle.crypto.params.ParametersWithRandom; import org.bouncycastle.pqc.crypto.DigestingMessageSigner; import org.bouncycastle.pqc.crypto.rainbow.RainbowKeyGenerationParameters; import org.bouncycastle.pqc.crypto.rainbow.RainbowKeyPairGenerator; import org.bouncycastle.pqc.crypto.rainbow.RainbowParameters; import org.bouncycastle.pqc.crypto.rainbow.RainbowSigner; public class rain { public static void main(String args[]){ SecureRandom keyRandom = new SecureRandom(); RainbowParameters params = new RainbowParameters(); RainbowKeyPairGenerator rainbowKeyGen = new RainbowKeyPairGenerator(); RainbowKeyGenerationParameters genParam = new RainbowKeyGenerationParameters(keyRandom, params); rainbowKeyGen.init(genParam); AsymmetricCipherKeyPair pair = rainbowKeyGen.generateKeyPair(); org.bouncycastle.pqc.crypto.rainbow.RainbowPrivateKeyParameters priv = (org.bouncycastle.pqc.crypto.rainbow.RainbowPrivateKeyParameters) pair.getPrivate(); org.bouncycastle.pqc.crypto.rainbow.RainbowPublicKeyParameters pub = (org.bouncycastle.pqc.crypto.rainbow.RainbowPublicKeyParameters) pair.getPublic(); System.out.println("Random:"+new BigInteger(130, keyRandom).toString(32)); System.out.println("\n----Private Key----"); System.out.println("Doc length:"+priv.getDocLength()); System.out.println("B1:"); showints(priv.getB1()); System.out.println("B2:"); showints(priv.getB2()); System.out.println("InvA1:"); showints(priv.getInvA1()); System.out.println("InvA1:"); showints(priv.getInvA2()); System.out.println("Vi:"); showints(priv.getVi()); System.out.println("\n----Public Key----"); System.out.println("Doc length:"+pub.getDocLength()); System.out.println("Coeff Quadratic:"); showints(pub.getCoeffQuadratic()); System.out.println("Coeff Scalar:"); showints(pub.getCoeffScalar()); System.out.println("Coeff Singlar:"); showints(pub.getCoeffSingular()); ParametersWithRandom param = new ParametersWithRandom(pair.getPrivate(), keyRandom); DigestingMessageSigner rainbowSigner = new DigestingMessageSigner(new RainbowSigner() , new SHA224Digest()); rainbowSigner.init(true, param); System.out.println("\n----Message and signing----"); String ex="hello"; if (args.length>1) ex = args[0]; byte[] message = ex.getBytes(); System.out.println("Message:"+ex); rainbowSigner.update(message, 0, message.length); byte[] sig = rainbowSigner.generateSignature(); System.out.println("Signature:"+getHexString(sig)); rainbowSigner.init(false, pair.getPublic()); rainbowSigner.update(message, 0, message.length); if (!rainbowSigner.verifySignature(sig)) { System.out.println("Failure in signature"); } else System.out.println("Success in signature"); } public static String getHexString(byte[] b) { String result = ""; for (int i=0; i < b.length; i++) { result += Integer.toString( ( b[i] & 0xff ) + 0x100, 16).substring( 1 ); } return result; } public static void showints(short [][] grid) { System.out.println("Dimension: [" + grid.length+"]["+grid[0].length+"] (Only displaying first few)"); int count=0; for(int r=0; r<grid.length; r++) { for(int c=0; c<grid[r].length; c++) { System.out.print(grid[r][c] + " "); count++; if (count>15) return; } System.out.println(); } } public static void showints(short [] grid) { for(int r=0; r<grid.length; r++) { System.out.print(grid[r] + " "); } System.out.println(); } public static void showints(int [] grid) { for(int r=0; r<grid.length; r++) { System.out.print(grid[r] + " "); } System.out.println(); } }
The variables used include:
- Doc - Number of polynomials in Rainbow.
- Vi - Number of Vinegar-variables per layer ({6, 12, 17, 22, 33})
- B1 - Translation part of the private quadratic map L1.
- InvA1 - Inverse matrix of A1.
- B2 - Translation part of the private quadratic map L2.
- InvA2 - Inverse matrix of A2.