Эффективный метод S-повторений для построения IND-CCA2 безопасной модификации криптосистемы Мак-Элиса в стандартной модели | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/24

Эффективный метод S-повторений для построения IND-CCA2 безопасной модификации криптосистемы Мак-Элиса в стандартной модели

Предлагаемая безопасная модификации криптосистемы Мак-Элиса использует S-повторенное шифрование S/2 различных сообщений с одной общей секретной перестановкой, в отличие от других модификаций, использующих S-повторенное шифрование одного сообщения. Таким образом, данная модификация обеспечивает IND-CCA2 безопасность с эффективной скоростью передачи данных.

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

Ключевые слова

post-quantum cryptography, McEliece-type cryptosystem, IND-CCA2-security, S-repetition encryption, постквановая криптография, криптосистема типа Мак-Элиса, IND-CCA2 безопасность, S-повторенное шифрование

Авторы

ФИООрганизацияДополнительноE-mail
Косолапов Юрий ВладимировичЮжный федеральный университеткандидат технических наук, доцентitaim@mail.ru
Турченко Олег ЮрьевичЮжный федеральный университетаспирантolegmmcs@gmail.com
Всего: 2

Ссылки

McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report. 1978. P. 42-44.
Rosen A. and Segev G. Chosen-ciphertext security via correlated products // LNCS. 2009. V. 5444. P. 419-436.
Dottling N., Dowsley R., Quade J. M., and Nascimento A. C. A. A CCA2 secure variant of the McEliece cryptosystem // IEEE Trans. Inform. Theory. 2012. V. 58(10). P. 6672-6680.
Persichetti E. On a CCA2-secure variant of McEliece in the standard model // Provable Security. 2018. V. 11192. P. 165-181.
Lamport L. Constructing Digital Signatures from One-Way Functions. SRI International, 1979. https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/
Naor M. and Yung M. Universal One-Way Hash Functions and their Cryptographic Applications // Proc. STOC'89. N.Y.: ACM, 1989. P. 33-43.
Nojima R., Imai H., Kobara K., et al. Semantic security for the McEliece cryptosystem without random oracles // Designs, Codes and Cryptography. 2008. V. 49. P. 289-305.
Berlekamp E. R., McEliece R. J., and van Tilborg H. C. On the inherent intractability of certain coding problems // IEEE Trans. Inform. Theory. 1978. V.24. No.3. P. 384-386.
Kobara K. and Imai H. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC // IEEE Trans. Inform. Theory. 2003. V.49. No. 12. P. 3160-3168.
 Эффективный метод S-повторений для построения IND-CCA2 безопасной модификации криптосистемы Мак-Элиса в стандартной модели | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/24

Эффективный метод S-повторений для построения IND-CCA2 безопасной модификации криптосистемы Мак-Элиса в стандартной модели | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/24