Logical cryptanalysis as part of strength research into particular codebased signature scheme

Ivan Chizhov, Nataliia Tashevtseva

Abstract


The authors propose an algorithm, which converts input for the cryptoanalyst problem of revealing secret keys of CodeBased Signature Scheme pqsigRM to an equal input for the SATISFIABILITY problem. It is proved in the paper, that the proposed attack is polynomial. The set of parameters of resulting CNF – length and the number of used variables, are theoretically assessed. The practical implementation of the proposed algorithm on Python is developed, which effectively creates the desired CNF in DIMACS format based on arbitrary pgsigRM scheme parameters r,m. Furthermore, the article contains experiment results, including execution results of the designed program for some values of r and m and performance of several opensource SATsolvers, winners of SAT Competition 2018 and SAT Race 2019 combined with other solvers used earlier for McEliece cryptosystem analysis, on solving the satisfiability problem for the resulting CNF for some values of r,m parameters of original cryptoanalyst problem. A set of parameters for which attack can be


Full Text:

PDF (Russian)

References


P. W. Shor, «Algorithms for quantum computation: Discrete logarithms and factoring», SFCS ’94, pp. 124–134, 1994. doi: 10.1109/SFCS.1994.365700.

F. Arute, K. Arya, Babbush, and et al, «Quantum supremacy using a programmable superconducting processor», Nature, no. 574, pp. 505–510, 2019, https://doi.org/10.1038/s41586-019-1666-5.

National Academies of Sciences, Engineering, and Medicine, Quantum Computing: Progress and Prospects, E. Grumbling and M. Horowitz, Eds.

Washington, DC: The National Academies Press, 2019. doi: 10 . 17226 / 25196. [Online]. Available: https : / / www . nap . edu / catalog / 25196 / quantum - computing-progress-and-prospects.

L. Fedichkin, «Kvantovye komp’yutery [Quantum computers]», Nauka i zhizn’ [Science and Life], no. 1, 2001.

T. Folger, «Kvantovyy Vzlom [Quantum Hack]», V mire nauki [In the world of science], no. 4, pp. 94–102, 2016.

R. J. McEliece, «A public key cryptosystem based on algebraic coding theory», 1978.

A. Barg, Complexity Issues in Coding Theory, 1997.

Yuan Xing Li, R. H. Deng, and Xin Mei Wang, «On the equivalence of McEliece’s and Niederreiter’s public-key cryptosystems», IEEE Transactions on Information Theory, vol. 40, no. 1, pp. 271–273, 1994.

V. Sidelnikov and S. Shestakov, «O sisteme shifrovaniya, postroennoy na osnove obobshchennykh kodov Rida-Solomona [On an encoding system constructed on the basis of generalized Reed-Solomon codes]», Diskretnaya matematika [Discrete mathematics], vol. 4, no. 3, pp. 57– 63, 1992.

V. Sidelnikov, «Otkrytoe shifrovanie na osnove dvoichnykh kodov Rida–Mallera [A public key cryptosystem based on Reed-Muller binary codes]», Diskretnaya matematika [Discrete mathematics], vol. 6, no. 3, pp. 3–20, 1994.

L. Minder and A. Shokrollahi, «Cryptanalysis of the Sidelnikov Cryptosystem», EUROCRYPT ’07, pp. 347–360, 2007. doi: 10.1007/978-3-540-72540-4_20.

M. A. Borodin and I. V. Chizhov, «Effektivnaya ataka na kriptosistemu Mak-Elisa, postroennuyu na osnove kodov Rida - Mallera [Effective attack on the McEliece cryptosystem based on Reed–Muller

codes]», Diskretnaya matematika [Discrete mathematics], vol. 26, pp. 10–20, Jan. 2014. doi: 10 . 4213 /dm1264.

Y. Lee, W. Lee, Y.-S. Kim, and J.-S. No, A Modified pqsigRM: RM Code-Based Signature Scheme, Cryptology ePrint Archive, Report 2019/678, https://eprint. iacr.org/2019/678, 2019.

N. T. Courtois, M. Finiasz, and N. Sendrier, «How to Achieve a McEliece-Based Digital Signature Scheme», in Advances in Cryptology — ASIACRYPT 2001, C. Boyd, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 157–174.

S. A. Cook, «Slozhnost’ protsedur vyvoda teorem [The complexity of theorem-proving procedures]», Kiberneticheskiy sbornik [Cybernetic collection], no. 12, pp. 5–15, 1971.

I. V. Chizhov and M. A. Borodin, «Zadacha VYPOLNIMOST” i vosstanovlenie sekretnogo klyucha kriptosistemy Mak-Elisa na osnove kodov Rida-Mallera [SATISFIABILITY problem and recovering of secret keys of McElice cryptosystem based on Reed-Muller codes]», Russian, in Tikhonovskie chteniya: Nauchnaya konferentsiya, MGU imeni M.V. Lomonosova, 29-31 oktyabrya 2012 g.: Tezisy dokladov, sektsiya Vychislitel’naya matematika i kibernetika [Tikhonov readings: Science conference, MSU named after M.V.Lomonosov, 29-31 of October 2012: Report abstracts, Computational mathematics and cybernetics], MAKS Press Moskva [MAKS Press Moscow], 2012, pp. 131–133.

F. MacWilliams and N. Sloane, Teoriya kodov, ispravlyayushchikh oshibki [The Theory of ErrorCorrecting Codes]. 1979.

I. Dumer, «Recursive decoding and its performance for low-rate Reed-Muller codes», IEEE Transactions on Information Theory, vol. 50, no. 5, pp. 811–823, 2004. doi: 10.1109/TIT.2004.826632.

G. V. Bard, N. T. Courtois, and C. Jefferson., Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers, https://eprint.iacr.org/2007/ 024, 2007.

N. Creignou and H. Daude, «Satisfiability threshold for random XOR-CNF formulas», Discrete Applied Mathematics, vol. 96-97, pp. 41–53, Oct. 1999. doi: 10.1016/S0166-218X(99)00032-3.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162