Choosing parameters for one IND-CCA2 secure McEliece modification in the standard model.pdf 1. Introduction The development of post-quantum cryptosystems resistant to adaptive chosen ciphertext attacks (IND-CCA2 secure cryptosystems) is currently relevant. In particular, NIST hold competitions for the formation of post-quantum cryptography standards [1]. One of the most successful candidates [2] is based on the idea of random oracle. However, since random oracle is only theoretical function, then the construction of IND-CCA2 secure post-quantum cryptosystems without random oracles (standard model) is also an interesting task. One of the ways to construct such scheme is to modify McEliece cryptosystem [3]. For instance, in [4-6] authors modified McEliece cryptosystem using correlated products method [7]. This paper is devoted to choosing practical parameters for cryptosystem from [5]. 2. Cryptosystem from [5] Let n, t be natural, [n] = {1,...,n}, в C [n], 2[n] is the set of all subsets of [n], F2 be a Galois field of cardinality 2. The support of the vector v = (v1, . . . , vn) G F2n is the set supp(v) = {i : vi = 0} and the Hamming weight of this vector is a number wt(v) = |supp(v)|. If S is a finite set, then s GR S denotes the operation of picking an element at random and uniformly from S. Denote by En,t,p the subset of Fn such that any vector e = (e1,..., en) G En,t,e has Hamming weight t and ei = 0 for any i G в. We will write En,t when в = 0. For the vector v G Fk and the ordered set w = {w1,..., wl} C [k], where w1 < ... < wl, we consider the projection operator IL : Fk FL acting according to the rule: IL(v) = (vW1,... ,viw). For w, consider a subset G(w) of symmetric group Sk acting on the elements of the set [k]: G(w) = {n G Sk : n(1) = W1,... , n(l) = wi}. With every permutation n from G(w) we associate a permutation (k x k)-matrix Rn. Now we consider construction from [5]. Recall that a public key cryptosystem is a triplet of algorithms, i.e., E = (K, E, D), where K is a generation algorithm, E is an encryption algorithm, D is a decryption algorithm. We will write {m}pk as encryption of the message m with the key pk and {c}sk as decryption of the ciphertext c on the secret key sk. For McEliece cryptosystem, we denote such triplet E as McE. In the cryptosystem E [5], key generation algorithm Ks takes as input two security parameters N, s G N and outputs a public-key pk and a secret key sk of the form pk = ((pki0, pki1))is=1, sk = ((ski0, ski1))is=1, where pkib, skib are generated by KMcE, b G {0, 1}, i G [s]. The encryption algorithm Es takes as input a message m = (m1 || ... || ms), where mi G Fz2, and a public-key pk. Then Es generates two keys dsk, vk for one-time strong unforgeable signature scheme, where vk = (vk1, . . . , vks), and outputs ciphertext c = c || vk || a, where c = c1 || ... || cs and a is a signature of vector c with the key dsk. Each ci has the form (1) ci = c1 || c2 = {(mi || rj/G}pkcEi H {(mi || г» Ф 1)Rn, where m. G Fz2, w CR [k], |w| = l, г» gr F2,-1, n GR G(w). The error vectors e1 and e2 generated in McE-encryption in the left and right parts, respectively, are chosen such that ei1 GR En,t, ei2 GR En,t,supp(e1). Decryption algorithm Ds takes as input a secret-key sk and a ciphertext c, and outputs either a message m G F2l or the error symbol ±. On the first step, Ds checks signature of the message. If check fails, then Ds outputs ±, otherwise it computes m = m1 || ... || ms, where mi = nni ({C1}MCE ), П = [k] \\ supp({c1}MEi c2 MCE {ci }skvki ). If n1 = ... = n«, then Ds outputs m else ±. Let us introduce additional notions. Denote public key pkvki from (1) as matrix Gi, 1 as all-ones vector from {0, 1}k-l, and 0 as all-zeroes vector from {0, 1}l. Then for matrix Gi and secret permutation (k x k)-matrix Rn, n G G(w), define (l x n)-matrix G1 and (k - l x n)-matrix Gi2 such that = Rn Gi. Then we can write Ci = c1 || c2 = {(mi || ri)RnGi Ф e1} || {(mi || r Ф 1)RnGi Ф e1} = = {miG1 Ф riG2 Ф e1} || {miG1 Ф (r Ф 1)G2 Ф e2}. (2) Now one can suggest security parameters. 3. Security parameters and experiments 3.1. S e c u r i t y p a r a m e t e r s Let us consider the general security parameters of the system: underlying linear [n, k, d]-code C, plaintext length l and one-time strong signature scheme. Since (pkib, skib) = = KMCE(N), b G {0, 1}, i G [s], then one can use known results of evaluating the code parameters of the original McEliece cryptosystem. In general, in [8] it is recommended to choose cryptosystem parameters with at least 86 security bits (for 2021 year). So, according to table 1.1 from [9] it is suggested to use [4096, 3604, 83]-code with 129 security bits. Then to prevent finding w from c1 Ф c2 = (0 || 1)RnGi Ф e1 Ф e2 = 1G2 Ф e1 Ф e2 (see (2)) we recommend to choose l with a restriction 14 C k - l C k - 14. Particularly, if l = 3604 - 14, /3590\\ then the adversary has to enumerate variants (about 129 bits) to find ш from 1Gi2. It is proposed to use an one-time strong signature scheme, on the one hand, resistant to quantum attacks, on the other hand, having a small public key size (since the number of repetitions s is equal to the size of the verification key). In [10] authors compared different signature schemes. So, according to table 2 from [10] we suggest to use Stern signature as a one-time strong signature scheme with a small public key size (347 bits). 3.2. E x p e r i m e n t s The theoretical proof of the security of the cryptosystem under consideration is based on the randomness of vectors 1Gi2 Ф ei1 Ф ei2 and riGi2 Ф ei1. Thus, the aim of experiments is to find a dependence of randomness of these vectors on the parameter l. It is important to note that in [11] authors consider similar vector to riGi2 Ф ei1. Based on time complexity for the “low weight codeword” attack, the authors suggest to use specific l. In our case, to implement such attack, an adversary has to find the set ш to determine the matrix Gi2. For l proposed above, the time complexity will be at least 2129. The experiments are carried out as follows. The NIST statistical test suite [12] is used to test the randomness of vectors. The encryption algorithm of our construction is implemented using C# language. To generate random vectors, we use a cryptographic generator from namespace System.Security.Cryptography of C#. Sincetheaimofexperimentsistofindthe dependence of randomness of cyphertexts on the parameter l, we generated several sets of random vectors from {0, 1}k having special weight. In the case when we test randomness of vector riG2 ф e1, we generate random vectors from {0,1}k having weight less or equal k - l. In case when we test randomness of vector 1G2 ф e1 ф e2, we generate random vectors from {0, 1}k having weight exactly k - l. In particular, we generate 10000 vectors for each message type and parameter l. For the purity of the experiment , we also present the number of test passes for random vectors v from {0, 1}k generated by cryptographic generator with fixed weight. The results of experiments are presented in the Table. Symbol “*” means that ri have weight exactly 1 (otherwise wt(ri) = 0 and riGi2 ф ei1 = ei1). Number of tests passed out of 10 000 conducted k l v, wt(v) = k - l ri G2 ф ei , wt(rj) < k - l 1G2 ф el ф e2 Average Minimum Average Minimum Average Minimum 1 714 0 9850* 9630* 9843 9610 14 1528 0 9852 9626 9852 9648 66 1859 0 9851 9636 9850 9611 112 2097 0 9852 9582 9860 9651 225 2103 0 9854 9625 9854 9650 450 2697 0 9851 9594 9847 9623 901 2756 0 9844 9606 9852 9602 1700 7302 598 9850 9601 9851 9620 1802 9881 9532 9849 9600 9844 9625 2703 2041 0 9848 9613 9853 9620 3604 714 0 9843 9576 9862 9406 Thus, the results obtained show that the considered ciphertexts pass similar number of tests for all possible values of the parameter l.

Скачать электронную версию публикации