Connecting the Complexity of MQ- and Code-Based Cryptosystems

Zajac, Pavol

doi:10.1515/tmmp-2017-0025

Abstract

We study the connection between the MQ problem and the decoding problem, through the intermediate MRHS representation. The main goal of this study is to explicitly bound the complexity of solving MQ systems with decoding tools. The main observation is that although the MQ problem over GF(2) can be efficiently transformed to syndrome decoding, the existing general decoding methods are not suitable to solve the system as efficiently as expected from the MQ representation.

References

[1] AUGOT, D. FINIASZ, M. GABORIT, P. MANUEL, S. SEN DRIER, N.: Sha-3 proposal: FSB, Submission to NIST (2008), 81 85. https://www.rocq.inria.fr/secret/CBCrypto/fsbdoc.pdf
Search in Google Scholar Back to article
[2] BARDET, M. FAUGERE, J.-C. SALVY, B. SPAENLEHAUER, P.-.I.: On the com¬plexity of solving quadratic boolean systems, J. Complexity 29 (2013), 53 75.10.1016/j.jco.2012.07.001
Open DOI Search in Google Scholar Back to article
[3] BECKER, A. JOUX, A. MAY, A. MEURER, A.: Decoding random binary linear codes in, 2n/20.- How 1+1 = 0 improves information set decoding. In: Adv. in Cryptology EUROCRYPT 2012, Lect. Notes in Comput. Sci. Vol. 7237, Springer-Verlag, 2012, pp. 520 536.
Search in Google Scholar Back to article
[4] BERLEKAMP, E. MCELIECE, R. VAN TILBORG, H.: On the inherent intractability of certain coding problems (Corresp.), IEEE Trans. Inform. Theory 24 (1978), 384 386.10.1109/TIT.1978.1055873
Open DOI Search in Google Scholar Back to article
[5] BERNSTEIN, D. .1. LANGE, T. PETERS, C. SCHWABE, P.: Faster 2-Regular Information-Set Decoding. In: Coding and Cryptology: Third International Workshop, IWCC 2011, Qingdao, China, May 30-June 3, 2011. Proceedings (Y. M. Chee, Z. Guo, S. Ling, F. Shao, Y. Tang, H. Wang, C. Xing, eds.), Springer-Verlag, Berlin, 2011, pp. 81 98.
Search in Google Scholar Back to article
[6] BOYAR, .I. PERALTA, R. POCHUEV, D.: On the multiplicative complexity of boolean functions over the basis (A,0,1), Theoret. Computer Sci. 235 (2000), 43 57.10.1016/S0304-3975(99)00182-6
Search in Google Scholar Back to article
[7] COURTOIS, N. T. FINIASZ, M. SENDRIER, N.: How to achieve a McEliece-based digital signature scheme. In: International Conference on the Theory and Application of Cryptology and Information Security, Springer-Verlag, Berlin, 2001, pp. 157 174. 1 -rn
Search in Google Scholar Back to article
[8] COURTOIS, N. T. GOUBIN, L. PATARIN, .7.: Quartz, an asymmetric signature scheme for short signatures on PC, Primitive specification and supporting documen¬tation (second revised version) (2001). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.6603
Search in Google Scholar Back to article
[9] MISOCZKI, R. TILLICH, J.-P. SENDRIER, N. BARRETO, P. S.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In: IEEE International Symposium on Information Theory - ISIT 2013, Istanbul, Turkey, Information Theory Proceedings (ISIT), 2013, pp. 2069 2073.
Search in Google Scholar Back to article
[10] NIEBUHR, R. MEZIANI, M. BULYGIN, S. BUCHMANN, .1.: Selecting parameters for secure McEliece-based cryptosystems, Int. .1. Inf. Sec. 11 (2012), 137 147.10.1007/s10207-011-0153-2
Search in Google Scholar Back to article
[11] RADDUM, H. SEMAEV, I.: Solving Multiple Right Hand Sides linear equations, Design, Codes and Cryptography 49 (2008), 147 160.10.1007/s10623-008-9180-z
Search in Google Scholar Back to article
[12] RADDUM, H. ZA.IAC, P.: MR.HS Solver Based on Linear Algebra and Exhaustive Search. 2017. [https ://eprint. iacr .org/2018/111 .pdf
Search in Google Scholar Back to article
[13] YASUDA, T. DAHAN, X. HUANG, Y.-J. TAKAGI, T. SAKURAI, K.: MQ Chal¬lenge: Hardness Evaluation of Solving Multivariate Quadratic Problems., IACR Cryptol¬ogy ePrint Archive 2015 (2015), p. 275.
Search in Google Scholar Back to article
[14] ZA.IAC, P.: A new method, to solve MRHS equation systems and, its connection to group factorization, .1. Math. Ciyptol. 7 (2013), 367 381.10.1515/jmc-2013-5012
Search in Google Scholar Back to article
[15] MRHS equation systems that can, be solved, in polynomial time, Tatra MT. Math. Publ. 67 (2016), 205 219.10.1515/tmmp-2016-0040
Search in Google Scholar Back to article
[16] Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity, Des. Codes and Cryptogr. 82 (2017), 43 56.10.1007/s10623-016-0256-x
Search in Google Scholar Back to article

Connecting the Complexity of MQ- and Code-Based Cryptosystems

Abstract

Paradigm

My account