Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem
Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem
复制标题
DOI：
10.1007/978-3-030-81293-5_4
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hiroki Furue;Shuhei Nakamura;T. Takagi
中科院分区：
文献类型：
--
作者：
Hiroki Furue;Shuhei Nakamura;T. Takagi
多元二次多项式问题($$\mathcal MQ$$ mq问题是后量子密码学中的一个基本计算问题。我们用mq （q,n,m）表示 $$\mathcal MQ$$ 有限域上无变量M二次方程的mq问题 $$\mathbb {F}_q$$ F q。在PKC 2012上，提出了一种求解欠确定的有效算法 $$MQ(2^r,n,m)$$ mq (2r, n， M $$n>m$$ n b> m由Thomae和Wolf （TW算法）提出。具体来说，通过消去向量积项 $$\alpha $$ α二次多项式通过线性化， $$MQ(2^r,n,m)$$ mq （2r, n， M）可以简化为 $$MQ(2^r,m-k-\alpha ,m-\alpha )$$ mq （2r, M - k - α, M - α）式中为应用TW算法后混合方法中固定的变量数。然后，算法得到最小值 $$\mathcal MQ$$ 求解线性化系数最大的mq问题 $$\alpha =\lfloor \frac{n}{m} \rfloor - 1$$ α =⌊n m⌋- 1 $$\alpha $$ α，其中 $$\lfloor \cdot \rfloor $$ ⌊·⌋是地板函数。在本研究中，我们提出了一种提高线性化因子的算法 $$\alpha $$ α通过混合方法和TW算法相结合。特别地，该算法可以减少 $$MQ(2^r,n,m)$$ mq （2r, n， M）到 $$MQ(2^r,m-k-\alpha _k,m-\alpha _k)$$ mq (2r, M - k - α k，M - α k)和线性化因子 $$\alpha _k = \lfloor \frac{n-k}{m-k}\rfloor -1$$ α k =⌊n - k m - k⌋- 1。因为 $$\alpha _k \ge \alpha $$ α k≥α…
The multivariate quadratic polynomial problem ($$\mathcal MQ$$ M Q problem) is a fundamental computational problem in post-quantum cryptography. We denote byMQ(q,n,m) the $$\mathcal MQ$$ M Q problem ofmquadratic equations innvariables over finite field $$\mathbb {F}_q$$ F q . At PKC 2012, an efficient algorithm for solving the underdetermined $$MQ(2^r,n,m)$$ M Q ( 2 r , n , m ) for $$n>m$$ n > m was proposed by Thomae and Wolf (TW algorithm). Specifically, by eliminating the cross-product terms in $$\alpha $$ α quadratic polynomials through linearization, $$MQ(2^r,n,m)$$ M Q ( 2 r , n , m ) can be reduced to $$MQ(2^r,m-k-\alpha ,m-\alpha )$$ M Q ( 2 r , m - k - α , m - α ) , wherekis the number of variables fixed in the hybrid approach after the TW algorithm is applied. Then, the algorithm yields the smallest $$\mathcal MQ$$ M Q problem for the largest linearization factor $$\alpha =\lfloor \frac{n}{m} \rfloor - 1$$ α = ⌊ n m ⌋ - 1 among possible $$\alpha $$ α , where $$\lfloor \cdot \rfloor $$ ⌊ · ⌋ is the floor function.In this study, we propose an algorithm that improves the linearization factor $$\alpha $$ α by combining the hybrid approach and the TW algorithm. In particular, the proposed algorithm can reduce $$MQ(2^r,n,m)$$ M Q ( 2 r , n , m ) to $$MQ(2^r,m-k-\alpha _k,m-\alpha _k)$$ M Q ( 2 r , m - k - α k , m - α k ) with linearization factor $$\alpha _k = \lfloor \frac{n-k}{m-k}\rfloor -1$$ α k = ⌊ n - k m - k ⌋ - 1 . Because $$\alpha _k \ge \alpha $$ α k ≥ α …