Efficient S-repetition method for constructing an IND-CCA2 secure McEliece modification in the standard model.pdf 1. Introduction Currently, much effort is being devoted to the development of quantum computers. Therefore, the study of post-quantum cryptosystems is an important task. One suitable scheme in the post-quantum era is the McEliece cryptosystem [1]. Note that the McEliece cryptosystem does not use quantum mechanical properties. However, the original McEliece scheme is vulnerable to attacks on cyphertexts. To date, many approaches have been developed to modify the McEliece cryptosystem. One of the most successful approaches is based on the application of correlated products [2]. For instance, in [3, 4] authors presented IND-CCA2-secure modifications in the standard model. At the same time, the main idea of correlated products is not effective in practice, because it requires to transmit S encrypted blocks for one information message. Based on the ideas from [3], we offer a new IND-CCA2-secure modification of the McEliece cryptosystem in the standard model, which requires to transmit S encrypted blocks for S/2 information messages. 2. Preliminaries Let n, t be natural, 2t < n, [n] = {1,... , n}, в С [n], 2[n] is set of all subsets of [n], F2 be a Galois field of cardinality 2. The support of the vector m = (m1,... , mn) Е F^ is the set supp(m) = {i : mi = 0} and the Hamming weight of this vector is a number wt(m) = |supp(m)|. A function y : N ^ [0,1] is negligible of k, if Vc Е N 3kc Е N Vk > kc (7(k) ^ k-c). We will use the notations similarly to the [3]. If S is a finite set, then s ER S denotes the operation of picking an element at random and uniformly from S. Denote by En,t,e the subset of Fn such that any vector e = (e1,..., en) Е En,t,e has Hamming weight t and ei = 0 for any i Е в. We will write En,t when в = 0. Let us define a cryptosystem as triplet of algorithms, i.e. £ = (K, E, D), where: 1) K is a probabilistic polynomial-time key generation algorithm which takes as input a security parameter N Е N and outputs a pair of public-key and a secret-key (pk, sk); 2) E is probabilistic polynomial-time encryption algorithm which takes as input a public-key pk and a message m and outputs a ciphertext c; we will write {m}pfc as encryption of the message m with the key pk; 3) D is deterministic polynomial-time decryption algorithm which takes as input a secret-key sk and a ciphertext c and outputs either a message m or a symbol ± in the case, when the ciphertext is incorrect; decryption of the ciphertext c on the secret key sk we will denote {c}^fc. Let us define signature scheme (SS) and one-time strongly unforgeable feature in the same way as [3]. A signature scheme is triplet of algorithms SS = (Kss, Sign, Check), where K is key generation algorithm which takes as input a security parameter N Е N and outputs a signing-key dsk and a verification-key vk, Sign is signing algorithm which takes as input a signing-key dsk and a message m and outputs a signature a, Check is checking algorithm which takes as input a verification-key vk a message m and a signature a and outputs 1 if a is valid for m and 0 otherwise. It is important to note, that one-time strongly unforgeable signature scheme can be constructed using one-way functions (see [5, 6]). Consider the McEliece cryptosystem as a triplet of polynomial-time algorithms: McE = = (KmcE, EmcE, Dmce) on the linear [n, k,d]-code C С F^, where n is the length, k is the code dimension, and d is the minimum code distance. Let G be the generator matrix of the code C, t = |_(d - 1)/2J. A secret key sk is a pair (S,P), where S is a non-singular (k x k)-matrix over the field F2 and P is a permutation (n x n)-matrix. A public key pk is a pair (G = SGP,t). Encryption of a message m G F2 is performed according to the rule {m)MfccE = mG + e = c, e Gr £n>t. To decrypt the ciphertext c, one should use an effective decoder DecC : Fn ^ F^ of the code C and the secret key sk: {c}MfccE = Decc (cP-1)S-1. 3. Efficient S-repetition construction On the basis of the Randomized McEliece cryptosystem [7] we construct a new cryptosystem bMcEi = (KbMcEl, EbMcEl, DbMcEl) and call it the basic cryptosystem. For the vector m(G F^) and the ordered set w = {w1,...,wi} С [k], where w1 < ... < wi, we consider the projection operator Пш : F^ ^ f[w| acting according to the rule: Пш (m) = (шШ1,... ,mi ). For ш consider a subset G(w) of permutations group Sk acting on the elements of the set [k]: G(w) = {n G Sk : n(1) = wi,... , n(l) = wi}. With every permutation n from G(w) we associate a permutation (k x k)-matrix Rn. The encryption rule of basic McEliece bMcEi has the form {m}pbfcMf1 = {(m || ri)Rn}JkcE || {(m || r2)Rn}JkcE = ci || c2 = c, where m G Fq, w CR [k], |w| = /, r1 gr Fk-i, r2 is formed in accordance with the restriction supp(r1 - r2) = [k]\\w, n GR G(w). The error vectors e1 and e2, generated in McE-encryption, are chosen such that e1 gr En,t, e2 gr En)t)Supp(ei). From here, it follows that wt(e1) + wt(e2) = 2t. To decrypt the ciphertext c, one should calculate {c}bMcEl = Пп({c1}MkcE), П = [k] \\ supp({c1}MkcE - {c2}MkcE). (1) Using the one-time strongly unforgeable signature scheme SS = (Kss, Sign, Check) we will construct a new S-repetition McEliece cryptosystem as a triplet of polynomial-time algorithms: bMcEf = (KbMcE^, EbMcE^, DbMcE^). Key generation algorithm KbMcE^ takes as input a security parameter N G N and outputs a public-key pk and a secret key sk of the form pk = ((pki0,pk1))S=1, sk = ((ski0,sk1))S=1, where pkb, skb ^ Kmce(N), b G {0,1}, i G [s]. To define encryption algorithm, let us consider a message m = (m1 || ... || ms) where m, G F^. Encryption algorithm EbMcEs takes as input a public-key pk and a message m and outputs a ciphertext c: c = {mWk1 = c' 11 vk 11 О where (dsk, vk) ^ Kss(N ), vk = (vkb..., vks), о = Sign(dsk, c'), pkvk = (pkVkl,..., pkVks), and c' calculated as follows: c' = c1 || ... || cS =[c1,1 || c1>2] || ... || [cS,1 || c's>2], where cj = [cj 1 || c'7-2] = {m, }bMV

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