Skip navigation

BMQE system: a MQ equations system based on ergodic matrix

BMQE system: a MQ equations system based on ergodic matrix

Zhou, Xiaoyi, Ma, Jixin, Du, Wencai, Zhao, Bo, Petridis, Miltos and Zhao, Yongzhe (2010) BMQE system: a MQ equations system based on ergodic matrix. In: SECRYPT 2010: Proceedings of the International Conference on Security and Cryptography. SciTePress – Science and Technology Publications, Portugal, pp. 431-435. ISBN 9789898425188

Full text not available from this repository.

Abstract

In this paper, we propose a multivariate quadratic (MQ) equation system based on ergodic matrix (EM) over a finite field with q elements (denoted as F^q). The system actually implicates a problem which is equivalent to the famous Graph Coloring problem, and therefore is NP complete for attackers. The complexity of bisectional multivariate quadratic equation (BMQE) system is determined by the number of the variables, of the equations and of the elements of Fq, which is denoted as n, m, and q, respectively. The paper shows that, if the number of the equations is larger or equal to twice the number of the variables, and qn is large enough, the system is complicated enough to prevent attacks from most of the existing attacking schemes.

Item Type: Conference Proceedings
Title of Proceedings: SECRYPT 2010: Proceedings of the International Conference on Security and Cryptography
Additional Information: [1] This poster was presented during sesssion on Cryptographic Techniques and Key Management at SECRYPT 2010 - International Conference on Security and Cryptography held from 26-28 July 2010 in Athens, Greece. [2] SECRYPT is part of ICETE - The International Joint Conference on e-Business and Telecommunications. [3] IEEE Conference Publications
Uncontrolled Keywords: ergodic matrix, bisectional, multivariate quadratic, fixing variables, NP-hard, complexity theory, Galois fields, polynomials, public key cryptography
Subjects: Q Science > QA Mathematics
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Computer Science
School of Computing & Mathematical Sciences > Department of Computer Systems Technology
Related URLs:
Last Modified: 14 Oct 2016 09:10
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/3885

Actions (login required)

View Item View Item