BMQE SYSTEM - A MQ Equations System based on Ergodic Matrix

Xiaoyi Zhou, Jixin Ma, Wencai Du, Bo Zhao, Miltos Petridis, Yongzhe Zhao

2010

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 F^q, 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.

Paper Citation

in Harvard Style

Zhou X., Ma J., Du W., Zhao B., Petridis M. and Zhao Y. (2010). BMQE SYSTEM - A MQ Equations System based on Ergodic Matrix . In Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2010) ISBN 978-989-8425-18-8, pages 431-435. DOI: 10.5220/0002992304310435

in Bibtex Style

@conference{secrypt10,
author={Xiaoyi Zhou and Jixin Ma and Wencai Du and Bo Zhao and Miltos Petridis and Yongzhe Zhao},
title={BMQE SYSTEM - A MQ Equations System based on Ergodic Matrix},
booktitle={Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2010)},
year={2010},
pages={431-435},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002992304310435},
isbn={978-989-8425-18-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2010)
TI - BMQE SYSTEM - A MQ Equations System based on Ergodic Matrix
SN - 978-989-8425-18-8
AU - Zhou X.
AU - Ma J.
AU - Du W.
AU - Zhao B.
AU - Petridis M.
AU - Zhao Y.
PY - 2010
SP - 431
EP - 435
DO - 10.5220/0002992304310435