Connecting the Complexity of MQ- and Code-Based Cryptosystems

Pavol Zajac

doi:10.1515/tmmp-2017-0025

.blurhash-client-img { display: none !important; }

Connecting the Complexity of MQ- and Code-Based Cryptosystems

Tatra Mountains Mathematical Publications

Volume 70 (2017): Issue 1 (September 2017)

By: Pavol Zajac

Open Access

|Mar 2018

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

Articles in this issue

DOI: https://doi.org/10.1515/tmmp-2017-0025 | Journal eISSN: 1338-9750 | Journal ISSN: 1210-3195

Journal RSS Feed

Language: English

Page range: 163 - 177

Submitted on: May 24, 2017

Published on: Mar 23, 2018

Published by: Slovak Academy of Sciences, Mathematical Institute

In partnership with: Paradigm Publishing Services

Publication frequency: 1 issue per year

Keywords:

94A60,

68P25,

06E30

Related subjects:

Mathematics,

General mathematics

© 2018 Pavol Zajac, published by Slovak Academy of Sciences, Mathematical Institute
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 70 (2017): Issue 1 (September 2017)