一、简介

多元公钥密码系统是后量子密码系统，其安全性依赖于解决有限域上多元多项式方程组的NP难问题。

多元公钥密码学（MPKC）是一系列密码系统，设计用于替代传统方案如RSA和DSA，尤其是在后量子时代。MPKC中的公钥是一组多元多项式，通常是二次的，定义在有限域上。MPKC的安全性基于解决这些系统的NP难度，使其能抵抗经典和量子攻击

优点：加解密、签名验证速度快，缺点：密钥存储的开销很高

二、基本概念

1、有限域上

$$设\mathbb F=\mathbb F_q是具有q个元素的有限域，常见的有\mathbb F_2,\mathbb F_{2^8},\mathbb F_{16},\mathbb F_{256}$$

2、多元二次方程MQ

$$设有n个变量x_1,x_2,…x_n，m个二元多项式P_1,P_2,…P_m$$

$$多项式表示为：P_i(x)=\sum_{j \leq k} R_{ijk}x_jx_k+\sum_j Q_{ij}x_j^2+\sum_jP_{ij}x_j$$

$$因此系统可表示为：P:\mathbb F_q^n \rightarrow \mathbb F_q^m，其中P(x)=(P_1(x),P_2(x),…P_m(x))$$

MQ****问题：

$$已知y=P(x)，求x \Leftrightarrow 求\begin {cases} P_1(x)=y_1 \ P_2(x)=y_2 \ \vdots\ P_m(x)=y_m \end {cases}$$

3、中心映射

$$本质上是一组多元多项式：F=(F_1,F_2,…,F_m$$

4、仿射变换

为了隐藏F的特殊结构，通常再加入两个秘密可逆仿射变换：

$$T：\mathbb F_q^n \rightarrow F_q^n和S:\mathbb F_q^m \rightarrow F_q^m$$

最终公钥为：P=S∘F∘T P(x)=S(F(T(x)))

三、原理

流程：$$x \rightarrow^Tu \rightarrow^Fv\rightarrow^Sy$$

先设计一个容易求逆的中心映射：F，然后随机生成两个可逆仿射映射：S、T，构造P=S∘F∘T P(x)=S(F(T(x)))

公钥：P 私钥：S,F,T

二次映射经过仿射变换后仍为二次映射，故而既可隐藏结构又不会改变公钥形式

四、主要类型

1、Oil-Vinegar

UOV Unbalanced Oil and Vinegar:

将变量分为：Vinegar variables和Vinegar variables

$$方程中只有v_iv_j和v_io_j没有o_io_j$$

$$先随机确定Vinega r:v_1,v_2,…v_n后所有关于oil的方程都会变成线性的，通过高斯校园直接求解oil$$

2、Rainbow

Baby tonight come with me 你的爱意像rainbow

多层UOV：$$V_1\rightarrow O_1 \rightarrow O_2 \rightarrow…$$

第一层解出O1后，变量又可作为下一层已知变量，解O2…逐层完成签名

3、HFE

Hidden Field Equations 隐藏域方程

$$利用扩域\mathbb F_{q^n}构造一个特殊的单变量多项式$$

$$F(x)=\sum a_{ij}x^{q^i+q^j}+\sum b_ix^{q^i}+c$$

HFE有很多变种：HFEv、HFE-、Quartz、GeMSS

五、缺陷与攻击

1、缺陷

公钥很大
参数设计困难
安全性分析负责

2、攻击手法

1、Gröbner Basis 攻击

$$已知目标：y=(y_1,y_2,….y_m), 构造f_i(x)=P_i(x) - y_i，得到： \begin {cases} f_1(x)=0 \ f_2(x)=0 \ \vdots \ f_m(x)=0 \end {cases}$$

$$构造多项式理想：I=(f_1,f_2,…f_m) ，计算Gröbner基：G=\lbrace g_1,g_2,…g_t \rbrace，消元得到： \begin {cases} g_1(x_n)=0 \ g_2(x_{n-1},x_n)=0 \ \vdots \ g_n(x_1,x_2,…x_n)=0 \end {cases}$$

逐个推到x_i