Digital Signatures with Symmetric Key? Here’s Picnic and MPC-in-the-Head
Digital Signatures with Symmetric Key? Here’s Picnic and MPC-in-the-Head
Ad so NIST has set up Round 1 of the Additional Signatures for PQCs [here]. These are grouped as follows:
- Multivariate Signatures (10): 3WISE, DME-Sign, HPPC (Hidden Product of Polynomial Composition), MAYO, PROV (PRovable unbalanced
Oil and Vinegar), QR-UOV, SNOVA, TUOV (Triangular Unbalanced
Oil and Vinegar), UOV (Unbalanced Oil and Vinegar), and VOX. - MPC-in-the-Head Signatures (7): Biscuit, MIRA, MiRitH (MinRank in the Head), MQOM (MQ on my Mind), PERK, RYDE, and SDitH (Syndrome Decoding in the Head).
- Lattice-based Signatures (6): EagleSign, EHTv3 and EHTv4, HAETAE, HAWK, HuFu (Hash-and-Sign Signatures From Powerful Gadgets), and SQUIRRELS ( Square Unstructured Integer Euclidean Lattice Signature).
- Code-based Signatures (5): CROSS (Codes and Restricted Objects Signature), Enhanced pqsigRM, FuLeeca, LESS (Linear Equivalence), MEDS (Matrix Equivalence Digital Signature).
- Symmetric-based Signatures (4): AIMer, Ascon-Sign, FAEST, and SPHINCS-alpha.
- Other Signatures (4): ALTEQ, eMLE-Sig 2.0 (Embedded Multilayer Equations with Heavy Layer Randomization), KAZ-SIGN (Kriptografi Atasi Zarah), Preon, and Xifrat1-Sign.I
- Isogeny Signatures (1): SQIsign.
In the first round, two lattice methods were chosen (Dilithium and FALCON) and SPHINCS+ (hash-based signature). We can see that there are six lattice methods that have been put forward. As NIST are probably going to be looking for a non-lattice method to provide additional signatures. Thus the two most popular methods are multivariate signatures and MPC-in-a-head. My personal favouriate is multivariate signatures, and the basic theory is here:
Here’s my 6 am doodles from this morning on multivariate cryptography:billatnapier.medium.com
So, let’s have a look at the next most popular method: MPC-in-the-Head.
MPC-in-the-Head Signatures
In the previous round we saw Picnic and which is an MPC-in-the-Head approach [2, 3]. Picnic uses non-interactive zero-knowledge proofs of knowledge and MPC (Multiparty Computation). With MPC we can split a problem into a number of computing elements, and these can be worked on in order to produce the result, and where none of the elements can see the working out at intermediate stages. Overall, Picnic uses the MPC-in-the-head method defined in [1]. The great advantage of this method is that we only use symmetric key methods (block ciphers and hashing functions).
To generate her signing key, Peggy (the prover) generates a random symmetric key. This will be her private key (sk). She then creates a publicly available plaintext block and then encrypts this with her symmetric key into a public ciphertext block. These two elements become then become her public key, as illustrated in Figure 1.
While many zero-knowledge proof methods use the Fiat-Shamir or Schnorr approach, Picnic uses a MPC-in-the-head approach by using an MPC method where Peggy takes an arbitrary circuit (made up of AND and XOR gates) and where it goes through the main steps involved in the MPC, and then shows the working out to Victor (the verifier). The LowMC circuit has been selected as it allows Peggy to compute a zero-knowledge proof for Victor to show that she knows her secret key (sk). LowMC defines a family of block ciphers that can be used in multi-party computations (MPC) and fully homomorphic encryption methods.
Key pair generation and signing
In the method (as illustrated in Figure 2), we generate a random plaintext block (p), and a random secret key (sk). Next, we compute C=LowMC(sk,p), and then determine the public key of pk=(C,p). To sign, we define knowledge the knowledge of sk so that C=LowMC(sk,p), and where the message m and public key pk are integrated with the proof for the signature. With this, the signature is basically a proof of knowledge of sk using the message as a nonce value.
Speed
In terms of speed, we see that for key generation, Pinic is the fastest of all the methods in Round 1, but it is weaker for signing and verifying. The lattice method of Dilithium is a good all-rounder [here]:
With key sizes, we see that Picnic has small key sizes. With Picnic 1 we have 33 bytes for the public key, 49 bytes for the private key, but 34,036 bytes for the signature [here]:
Head-to-head
Picnic and SPHINCS+ both produce small public and private keys. For Picnic 3, we have a 49 byte public key and a 73 byte private key, and which easily beats Dilithium, Falcon and Rainbow. But the digital size for Picnic 1 is over 30KB:
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
GeMSS 128 352,188 16 33 1 (128-bit) Multivariate (HFEv-)
GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate (HFEv-)
Picnic 1 Full 35 52 30,956 1 (128-bit) Symmetric
Picnic 3 Full 49 73 68,539 3 (192-bit) Symmetric
Picnic 5 Full 65 97 121,486 5 (256-bit) Symmetric
RSA-2048 256 256 256
ECC 256-bit 64 32 256Now let’s implement LMS using the Bouncy Castle library [here]:
namespace Picnic
{
using Org.BouncyCastle.Pqc.Crypto.Picnic;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var msg="Hello";
var method="picnic3l1";
if (args.Length >0) msg=args[0];
if (args.Length >1) method=args[1];
var random = new SecureRandom();
var keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnic3l1);
if (method=="picnic3l1") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnic3l1);
else if (method=="picnic3l3") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnic3l3);
else if (method=="picnic3l5") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnic3l5);
else if (method=="picnicl1fs") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl1fs);
else if (method=="picnicl1full") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl1full);
else if (method=="picnicl1ur") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl1ur);
else if (method=="picnicl3fs") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl3fs);
else if (method=="picnicl3full") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl3full);
else if (method=="picnicl3ur") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl3ur);
else if (method=="picnicl5fs") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl5fs);
else if (method=="picnicl5full") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl5full);
else if (method=="picnicl5ur") keyGenParameters = new PicnicKeyGenerationParameters(random,PicnicParameters.picnicl5ur);
var keyPairGen = new PicnicKeyPairGenerator();
keyPairGen.Init(keyGenParameters);
var keyPair = keyPairGen.GenerateKeyPair();
var pubKey = (PicnicPublicKeyParameters)keyPair.Public;
var privKey = (PicnicPrivateKeyParameters)keyPair.Private;
// Signing
var aliceSign = new PicnicSigner();
aliceSign.Init(true, privKey);
var signature = aliceSign.GenerateSignature(System.Text.Encoding.UTF8.GetBytes(msg));
// verify signature
var bobVerify = new PicnicSigner();
bobVerify.Init(false, pubKey);
// var rtn = aliceSign.VerifySignature(System.Text.Encoding.UTF8.GetBytes(msg), signature);
Console.WriteLine("Message:\t{0}",msg);
Console.WriteLine("Method:\t\t{0}",method);
Console.WriteLine("\nPublic key (length):\t{0} bytes",pubKey.GetEncoded().Length);
Console.WriteLine("Alice Public key :\t{0}",Convert.ToHexString(pubKey.GetEncoded()));
Console.WriteLine("\nPrivate key (length):\t{0} bytes",privKey.GetEncoded().Length);
Console.WriteLine("Alice Private key:\t{0}",Convert.ToHexString(privKey.GetEncoded()));
Console.WriteLine("\nSignature (length):\t{0} bytes",signature.Length);
Console.WriteLine("Signature (first 50 bytes):\t\t{0}",Convert.ToHexString(signature)[..100]);
// Console.WriteLine("\nVerified:\t{0}",rtn);
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}A sample run with Picnic 1 Full (with 128-bit security) gives [here]:
Message: Post Quantum Crypto
Method: picnicl1full
Public key (length): 35 bytes
Alice Public key : 0AA41085875741F3C755D2B002F231AB1D80731F59E35FA9903396751CE8F7E9EE1280
Private key (length): 52 bytes
Alice Private key: 0AA6FCDB8CAB64197BD8B01AA3B136756500A41085875741F3C755D2B002F231AB1D80731F59E35FA9903396751CE8F7E9EE1280
Signature (length): 30956 bytes
Signature (first 50 bytes): 6A04928946459A24508281A56900061A4499A215522841846A9250A1AAA912029A2688495A92922A15A18656099595016845and for Picnic 3 Full (with 192-bit security): [here]:
Message: Post Quantum Crypto
Method: picnicl3full
Public key (length): 49 bytes
Alice Public key : 0B4E7E5A58C5858928B74A4EC5319E302C0F3734D6C18C9D2238E5E292BFF0DF6BF8732D6937873FF3ACFD762FC2272131
Private key (length): 73 bytes
Alice Private key: 0B11FA80D8D7DB9FA9D5EFEF8FA2E399A37AA8A2B434FB961E4E7E5A58C5858928B74A4EC5319E302C0F3734D6C18C9D2238E5E292BFF0DF6BF8732D6937873FF3ACFD762FC2272131
Signature (length): 68539 bytes
Signature (first 50 bytes): 5846585A22504805845008508A846400122A849809A5A98644689996565852221005188548264289226246696A5084428811and Picnic 5 Full (with 256-bit security) [here]:
Message: Post Quantum Crypto
Method: picnicl5full
Public key (length): 65 bytes
Alice Public key : 0CC4379CEE898F443E75EEBCD7DD81A6162BA3B052EBFCB5DC8692B195B83D21F61BCCB3765FC1FCF00E1159DE1D8ACAD4371389E97B72252A6F617D0F9636FE44
Private key (length): 97 bytes
Alice Private key: 0C7601B627358303F1EF45EB31264F492E590C149C059C4D8C04E4D46BE497FDACC4379CEE898F443E75EEBCD7DD81A6162BA3B052EBFCB5DC8692B195B83D21F61BCCB3765FC1FCF00E1159DE1D8ACAD4371389E97B72252A6F617D0F9636FE44
Signature (length): 121486 bytes
Signature (first 50 bytes): 821949812850AA886590284650495096919012924860A48896A546A0412628018A90089868601824A12980982A2A96489851Conclusions
Picnic is fairly fast and produces small keys, but the digital signature size is large. If we replace the RSA or ECDSA signature in TLS, then for a 34K signature, we would need over 23 packets to send the signature — which will have a large overhead. It is yet to be seen if the new MPC-in-the-head methods can reduce the signature size.
References
[1] Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2007, June). Zero-knowledge from secure multiparty computation. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (pp. 21–30).
[2] Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., … & Zaverucha, G. (2017, October). Post-quantum zero-knowledge and signatures from symmetric-key primitives. In Proceedings of the 2017 acm sigsac conference on computer and communications security (pp. 1825–1842). [here].
[3] Chase, M., Picnic Post-Quantum Signatures from Zero Knowledge Proofs [slides]
[4] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].