Picnic is one of the alternative finalists for the NIST standard for PQC (Post Quantum Cryptography) [1]. In the method, 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 knowlege of \(sk\) so that \(C= LowMC(sk, p)\), and where the message m and public key pk are integrated wit the proof for the signature. With this the signature is basically a proof of knowledge of \(sk\) using the message as nonce value. LowMC defines a family of block ciphers that can be used in multi-party computations (MPC) and fully homomorphic encryption methods [2].
Picnic using Bouncy Castle and C# |
Method
And then there were three: CRYSTALS Dilithium, Falcon and Rainbow. These are the finalists for the NIST standard for Post Quantum Cryptography (PQC) of digital signatures. Basically, they will replace RSA and ECC in an era of quantum computers, and provide the core of trust on the Internet. Dilithium and Falcon are lattice methods, and Rainbow uses multivariate quadratic polynomials. So while lattice looks like a winner because of its speed of computation and key size, there is a competition for an alternative winner.
Two of the alternative winner finalists are SPHINCS+ and Picnic. These methods have a core advantage of using symmetric key approaches to digital signing, and where symmetric key methods are robust against quantum computers and generally fast in their operation. With SPHINCS+ we use hashes to produce the signature, and with Picnic, we use symmetric key cipher blocks and hashes. So let’s go for a Picnic [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.
Figure 1: Generating the private key (sk) and the public key (pk)
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 [5] defines a family of block ciphers that can be used in multi-party computations (MPC) and fully homomorphic encryption methods.
Key pair generation/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.
Figure 2: Key generation and signing
MPC-in-a-head
With this we have \(N\) parties and a private input of \(x_i\), and we need to compute \(f(x_1, ..., x_n)\), so that if (\(n-1\)) entities share their details, it will not reveal anything. Thus to provide that Peggy knows \(x\) such that:
\(F(x)=1\)
we can select values to define that:
\(x_1 \oplus x_2 \oplus ... + x_n = x\)
We then run a MPC to compute:
\(F(x_1 \oplus x_2 \oplus ... + x_n)\)
The verifier (Victor) selects a value of \(i\) and the prover reveals all the values apart from \(i\).
Performance evaluation
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 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 256
For performance on M4 (ARM Cortex-M4 dev) [4] and measured in CPU operations per second. Note, no Rainbow assessment has been performed in [4], 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 Rainbow assessment has been performed in [4], 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 (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
For code size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no Rainbow assessment has been performed in [4], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Memory (Bytes) ------------------------------------------------- Crystals Dilithium 2 (Lattice) 13,948 Crystals Dilithium 3 13,756 Crystals Dilithium 5 13,852 Falcon 512 (Lattice) 117,271 Falcon 1024 157,207 Rainbow Level Ia (Oil-and-Vineger) 404,920 Rainbow Level IIIa 405,412 Rainbow Level Vc 405,730 Sphincs SHA256-128f Simple 4,668 Sphincs SHA256-192f Simple 4,676 Sphincs SHA256-256f Simple 5,084
Now let's implement LMS using the Bouncy Castle library:
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 gives:
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): 6A04928946459A24508281A56900061A4499A215522841846A9250A1AAA912029A2688495A92922A15A18656099595016845
and for Picnic 3 Full:
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): 5846585A22504805845008508A846400122A849809A5A98644689996565852221005188548264289226246696A5084428811
and Picnic 3l5:
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): 821949812850AA886590284650495096919012924860A48896A546A0412628018A90089868601824A12980982A2A96489851
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.
[5] Dinur, I., Kales, D., Promitzer, A., Ramacher, S., & Rechberger, C. (2019, May). Linear equivalence of block ciphers with partial non-linear layers: application to LowMC. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 343-372). Springer, Cham [paper].