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 - Digital Signature |
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 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) [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
Coding
The following is an implementation of Picnic:
#include stdio.h #include stdint.h #include stdlib.h #include time.h #include "api.h" #include "picnic.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 m[MLEN + CRYPTO_BYTES]; uint8_t m2[MLEN + CRYPTO_BYTES]; // uint8_t sm[MLEN + CRYPTO_BYTES]; uint8_t pk[CRYPTO_PUBLICKEYBYTES]; uint8_t sk[CRYPTO_SECRETKEYBYTES]; 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); randombytes(m, MLEN); crypto_sign_keypair(pk, sk); 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); // printf("Signature Length + Msg = %ld\n", smlen); printf("\nAlice Public key: %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES)); printf("Alice Secret key: %s\n",showhex(sk,CRYPTO_SECRETKEYBYTES)); printf("\nMessage: %s\n",showhex(m,MLEN)); 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("Signature (Showing 1/128th of signature): %s\n",showhex(sm,smlen/128)); 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 49 bytes, the secret key is 73 bytes, and the digital signature of 71,1179 bytes:
NAME: picnicl3full CRYPTO_PUBLICKEYBYTES = 49 CRYPTO_SECRETKEYBYTES = 73 CRYPTO_BYTES = 71179 Alice Public key: 0befe6cd9b6298fb28b875877bd0197f1f0306846d6acfcf490c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40e Alice Secret key: 0b0c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eefe6cd9b6298fb28b875877bd0197f1f0306846d6acfcf490c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40e Message: 0c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eff304211c2c13f45e17723c80e0b50bfec679df8226606ceaddba24d7ad4d5973420c6 Signature (Showing 1/128th of signature): 3b0d01000c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eff304211c2c13f45e17723c80e0b50bfec679df8226606ceaddba24d7ad4d5973420c699185102220a6a94a04222064298054622469652911926a189665595aa5a068a0818291a0a4416614860502659552996666282151692a666a86a0a92486954282522809a11a4606418664665a4281856969140c99a5ce4f10595cc914919cbb542f391d5a3b603942cb1cbc0c2413e5c9e7f92a3f03b2e9733773beecdaadf9d89195c4548dc011be0a67ed282a1c10e09fc5285ebf68936196c058fdc0805b5695eb54daeb50ef5f8c550dda600173f344c7fd29f2b17821d7aa662c10b8cfbdedff941d2ed143c512e4732e1932a28cab803bcf4455e83401e1cef9684fcebb29cef2b05f39491b7d8499099e4e824504273cd59a47f0eed02fada506e2fc93f465fa799e022f593fdbaa16f9b7504c8ddc0c90a873588ae3b61bd2c81fd86c4c9f9200fb4876a37de821bc80191304f0d5509ec8828def45e2a14c49bab2f3a3649a2d6dcf36a67a06188730d4c5e667fb2bd691073e9e13e62fee98a8501f789d23b3ed8858d333ff89085c9152992c384984cf39f38be3b05b10b4fb20a79b54183be611e7668df5b02b28cfc1829a60ed02d3b8c65d2db619c1e12a53198a924c34978efdfd284b5b5b35a7867d8b3b415dfb349f4a80a7b5e0aad036b9d132aa2488653297d69f6835b2d478969c180a4d1ceec282ee087
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].