基于代码的PKE与多元DSS的数学相似性与差异性

Question

在基于代码的公钥加密方案中，公钥是由矩阵-将2个线性矩阵相乘到一个容易解码的纠错码的左侧和右侧形成的，因此很难提取可用于解密密文的有用信息。

在多元数字签名方案中，公钥是通过将线性方程组组合到一个易于求解的多元(通常是二次型)方程系统的内部和外部部分来形成的，这样就不能轻易地逆转所产生的组合。

据我所知，线性系统的组合是基于代码的PKE和多元DSS之间最大的相似之处，我想知道：

1. 在其他方面，基于代码的密码系统和多元密码系统是否有相似之处？
2. 基于代码的密码系统和多元密码体制有什么重要的区别？

Answer 1

多元格式与中心多项式映射\mathcal{F}(X) : F_2^n \mapsto F_2^m巧妙地工作，该映射是定义n变量上的m二次方程的二次映射。然后选择T,S作为可逆仿射变换。公钥P(X) = T \circ F \circ S(X)以m二次型形式写入F_2上的n变量中。

然而，由于每个二次型q_i(X)=X^T Q_i X都可以用张量线性化，这是\overline{q_i}(x \otimes x)的一个点乘积，其中\overline{q_i}是矩阵q_i的n^2向量整形。

然后将公钥重写为m \times n^2矩阵\overline{P}，其中i第四行对二次窗体的i-th列进行编码。这是一个矩形矩阵，不允许攻击者从输出X计算输入值Y。从这里，我们的目标是试图通过获取仿射变换(T,S) (我们指多项式的同构(\mathcal{IP}) )来求解，解决F_2上潜在的非线性二次系统，这是PoSSo问题的一个子实例，称为\mathcal{MQ}问题，或者研究MinRank \mathcal{MR}问题。

例如，HFE公钥可以使用纯线性代数计算，而不需要在多项式环和有限域上工作。要么像我一样导出二次型，这里，要么使用张量。但是你仍然需要应用Berlekamp来在F_q上找到根。