Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings-猫眼课题宝

DOI：

10.1007/978-3-031-62746-0_6

发表时间：

2021-12

期刊：

IACR Cryptol. ePrint Arch.

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Hiroki Furue;Momonari Kudo

求解有限域上多元二次方程组(MQ问题)是计算机科学理论中的重要问题之一。XL算法(简称XL算法)是解决系数域上线性化MQ问题的主要方法。此外，XL(h-XL)的混合方法是XL的一种变体，它预先猜测了一些变量。在这篇文章中，我们提出了h-XL的一个变种，我们称之为多项式XL(PXL)。在PXL中，将整个变量分为待修复的tokVariables和剩余的\Documentclass[12pt]{Minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemarin}{-69pt}\Begin{Document}$$n-k$\end{Document}变量，并且我们生成关于以下内容的Macaulay矩阵：\DocentClass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$n-k$\end{Document}main变量。通过在猜测k个变量之前消除多项式环上的Macaulay矩阵的一些列，与h-xL相比，每个猜测值所需的运算量可以减少。我们对PXL的复杂性分析(在一些实际的假设和启发下)给出了一个新的理论界限，它表明在满足以下条件的随机系统上，PXL在理论上可能比其他算法更有效：\Docentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{waysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$n=m$\end{Document这是一般多变量签名的情况。例如,在有限域上具有以下元素的系统上：\Docentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\{Begin{Document}$$\end{Document}元素\DocumentClass[12pt]{Minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsFonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$n=m=80$\end{Document}，从XL和Wiedemann XL、杂交和PXL与最优的混合方法的理论界中推导出的运算数估计为：\DocentClass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setlong{\oddsidemarin}{-69pt}\Begin{Document}$2^{252}$\end{document}，\Docentclass[12pt]{Minimum}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$2^{234}$\end{文档}，\DocumentClass[12pt]{Minimal}\usepackage{amsath}\usepackage{waysym}\usepackage{amsFonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathsfs/…

Solving a system ofmmultivariate quadratic equations innvariables over finite fields (the MQ problem) is one of the important problems in the theory of computer science. The XL algorithm (XL for short) is a major approach for solving the MQ problem with linearization over a coefficient field. Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing some variables beforehand. In this paper, we present a variant of h-XL, which we call thepolynomial XL (PXL). In PXL, the wholenvariables are divided intokvariables to be fixed and the remaining \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-k$$\end{document} variables as “main variables”, and we generate a Macaulay matrix with respect to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-k$$\end{document} main variables over a polynomial ring of thek(sub-)variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessingkvariables, the amount of operations required for each guessed value can be reduced compared with h-XL. Our complexity analysis of PXL (under some practical assumptions and heuristics) gives a new theoretical bound, and it indicates that PXL could be more efficient than other algorithms in theory on the random system with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=m$$\end{document}, which is the case of general multivariate signatures. For example, on systems over the finite field with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^8}$$\end{document} elements with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=m=80$$\end{document}, the numbers of operations deduced from the theoretical bounds of the hybrid approaches with XL and Wiedemann XL, Crossbred, and PXL with optimalkare estimated as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{252}$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{234}$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs …

Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings

文献摘要

相似文献