N1gh7ma12e的小站

你所热爱的就是你的生活

0%

油醋签名系统

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 8 分钟

今年碰到的关于油醋签名系统的题还挺多的，第一次听到油和醋的时候还感觉挺有趣的（再加上盐可以做饭了）。浅浅学习一下。

多变量密码

多变量密码是基于有限域$\mathbb{F}_{q}$上解多元二次方程组困难性（MQ问题）的公钥密码体制。下面描述一下MQ问题：
给定$F_{q}$中的多元二次方程组

已知$\text{y}=(f_{1}(\text{x}),f_{2}(\text{x}),\dots,f_{m}(\text{x}))$，求解满足方程组的解$\text{x}’=(x_{1}’,x_{2}’,\dots,x_{n}’)$。

多变量体制几乎都遵循一个统一的套路：$\mathcal{P}=\mathcal{S}\circ\mathcal{F}\circ\mathcal{T}$，其中$\mathcal{P}$为公钥，$(\mathcal{S},\mathcal{F},\mathcal{T})$为私钥。它核心则在于中心映射$\mathcal{F}:\mathbb{F}_{q}^n \to \mathbb{F}_{q}^{m},\mathcal{F}(\text{x})=(f_{1}(\text{x}),f_{2}(\text{x}),\dots,f_{m}(\text{x}))$，这里$\mathcal{F}$必须满足的一个条件就是$\mathcal{F}$的原像必须在计算上是容易找到的(也正因为$\mathcal{F}$存在某种这样的设计，所以多变量密码并非是provably secure)。$\mathcal{S},\mathcal{T}$则是两个随机可逆的线性映射，用于打乱多项式和变量对$\mathcal{F}$做混淆。这样对于公钥用户来说仅仅是看到经过混淆的$\mathcal{P}$，解$\mathcal{P}(\text{x})=y$是困难的。

根据上面所述，签名步骤就很显而易见了：对文件$m$进行签名，计算$\mathcal{S}^{-1}(m)=y,\mathcal{F}^{-1}(y)=z,\mathcal{T}^{-1}(z)=\text{x}$，则$\text{x}$即为$m$的签名。对其进行验证只需检查$\mathcal{P}(\text{x})$是否等于$m$即可。

油醋签名系统

首先是定义：令$o,v$为正整数，$n=o+v$。$x_{1},x_{2},\dots,x_{v}$为醋变量，$x_{v+1},x_{v+2},\dots,x_{n}$为油变量。
其中心映射$\mathcal{F}:\mathbb{F}_{q}^{n}\to \mathbb{F}_{q}^{o},\mathcal{F}(x_{1},x_{2},\dots,x_{n})=(f_{1}(x_{1},x_{2},\dots,x_{n}),\dots,f_{o}(x_{1},x_{2},\dots,x_{n}))$。每个$f_{i}$都有：

每一个$f_{i}$的二次项中都含有醋变量乘醋变量，醋变量乘油变量，但是不能含油变量乘油变量。这样的构造方便我们在给定$\text{z}=(z_{1},z_{2},\dots z_{n})$找到一个$z$的原像$\mathcal{F}^{-1}(\text{z})$。我们只需要随机给醋变量代入数值$x_{1}=\alpha_{1},x_{2}=\alpha_{2},\dots,x_{v}=\alpha_{v}$，这样整个系统就变成了一个含有$o$个油变量的$o$个方程的线性方程组（这也解释了为什么没有醋-醋项）。这样的方程大概率是有解的（如果没有解可以换一组）。

之后我们需要生成一个随机可逆的线性变换$\mathcal{T}:\mathbb{F}^{n}\to \mathbb{F}^{n}$用于打乱油变量和醋变量，使得公钥看不出任何油醋的结构。所以公钥即$\mathcal{P}=\mathcal{F}\circ\mathcal{T},\mathcal{P}(x_{1},x_{2},\dots,x_{n})=(p_{1}(x_{1},x_{2},\dots,x_{n}),\dots,p_{o}(x_{1},x_{2},\dots,x_{n}))$，私钥则是$\mathcal{T},\mathcal{F}$。签名步骤则如下：对文件$m$进行签名，计算$\mathcal{F}^{-1}(m)=z,\mathcal{T}^{-1}(z)=\text{x}$，则$\text{x}$即为$m$的签名。对其进行验证只需检查$\mathcal{P}(\text{x})$是否等于$m$即可。

Kipnis-Shamir 攻击

子空间和不变子空间

在讲之前，得先讲一些代数的内容。
子空间：在线性代数中，假设我们在一个向量空间$V$（比如$\mathbb{R}^n$）里。一个集合$W \subseteq V$，如果它本身在向量加法和数乘下也满足向量空间的公理，那么我们称$W$是$V$的子空间。
换句话来说，$W$是子空间的条件是：

  1. 零向量在$W$里
  2. 对加法和数乘封闭

不变子空间： 假设我们有一个线性算子（或者矩阵）$T:V\to V$即$T$把$V$中的向量映射回$V$中。如果$W\subseteq V$且是一个子空间，并且满足：$T(W)\subseteq W$，我们就称$W$是$T$的一个不变子空间。

攻击

在最基础的OV方案设计中，油变量的数量和醋变量是相同的。Kipnis和shamir两个神人对这此设计了一种有效的攻击，使得在醋变量和油变量平衡的时候变得极其不安全（这也使得后面产生了UOV）。

这个攻击的思想也很简单粗暴：既然你通过$\mathcal{T}$对$\mathcal{F}$做了混淆，那我只需要找到一个$\mathcal{\tilde{T}}$把被$\mathcal{T}$打乱的油和醋重新分离就好了。

我们这里先假设中心映射的多项式$f_{1},f_{2},\dots,f_{o}$中都仅仅含有二次项，而不含一次项和常数项（因为一次项和常数项并不会对安全性造成影响，之后会解释）此处我们有$o=v$，且仅考虑有限域$\mathbb{F}_{q}$的特征值非2。

每个多项式$f_{i}$都能表示成对称矩阵的形式，即：$f_{i}=\text{x}^{t}F_{i}\text{x}$，$F_{i}$即是对称矩阵，有如下的形式：
这应该也不难想象，其中的$F_{i_{1}}$即醋醋多项式的系数，$F_{i_{2}},F_{i_{3}}$都是油醋多项式的系数值的一半。$0$则是$o\times o$的零矩阵，是油油多项式的系数（因为不存在）。同理公钥$p_{i}$也能表示成对称矩阵的形式，有：$P_{i}=T^{t}F_{i}T$，其中$T$为线性变换$\mathcal{T}$的矩阵形式。

现在我们定义$\mathbb{F}^{n}$的子空间：

$O=\{\text{x}=(x_{1},x_{2},\dots,x_{n})\in \mathbb{F}^{n}\mid x_{1}=x_{2}=\dots=x_{v}=0\}$

$V=\{\text{x}=(x_{1},x_{2},\dots,x_{n})\in \mathbb{F}^{n}\mid x_{v+1}=x_{v+2}=\dots=x_{n}=0\}$

如果$E_{1}=\sum a_{i}F_{i},E_{2}=\sum b_{i}F_{i}$，且$E_{1}$可逆。设$x=\begin{pmatrix}0\\z\end{pmatrix}\in O$，对于$E_{2}$易知:

所以$E_{2}(O)\subseteq V$。又因$E_{1}$可逆，易知：

则有$E_{1}^{-1}\begin{pmatrix}u\\0\end{pmatrix}=\begin{pmatrix}0\\B_{1}^{-1}u\end{pmatrix}\subseteq O$，那么$O$是$E=E_{1}^{-1}E_{2}$的不变子空间。

如果$W_{1}=\sum c_{i}P_{i},W_{2}=\sum d_{i}P_{i}$，且$W_{1}$可逆。

由于$P_{i}=T^{t}F_{i}T$，所以有：$W_{1}=\sum c_{i}T^{t}F_{i}T=T^{t}\left( \sum c_{i}F_{i} \right)T=T^tE_{1}T$，同理有：$W_{2}=T^{t}E_{2}T$。

所以有$W=W_{1}^{-1}W_{2}=(T^{t}E_{1}T)^{-1}(T^{t}E_{2}T)=T^{-1}ET$，即$W$与$E$相似。又因为$O$是$E$的不变子空间，所以$\mathcal{T}^{-1}(O)$是$W=W_{1}^{-1}W_{2}$的不变子空间。

对于如何通过$W$去找到$\mathcal{T}^{-1}(O)$，我们只需要计算$W$的特征多项式$\mathcal{X}W(x)$，会发现它是一个完全平方式（为什么一定是，我还没太懂，有知道的和我说一下），即：$\mathcal{X}W(x)=(h(x))^{2}$，只需要求$h(W)$的kernel，这就是不变子空间$\mathcal{T}^{-1}(O)$里的所有向量的集合。后续只需据此和公钥恢复出私钥即可。