一、简介

UOV是一种数字签名方案，即使在量子计算机面前也能保持安全。它基于陷门多元二次映射，遵循哈希和符号范式构建。

二、基本概念

Oil和Vinegar

$$设总共有n个变量，m个Oil变量：o_1,o_2,…,o_m，v个Vinegar变量v_1,v_2,…,v_v$$

$$UOV限制：没有OO项，只有VV和VO项$$

Unbalanced

UOV 设置 v>m 通过增加Vinegar变量隐藏Oil子空间，提高对结构恢复攻击的抵抗能力

三、算法原理

$$UOV流程：KeyGen \rightarrow Sign \rightarrow Verify$$

1、密钥生成 KeyGen

$$首先构造秘密中心映射：F=(f_1,f_2,…,f_m) \quad f_i满足OO=0$$

$$那么F(v,o)=VV+VO+一次项，然后生成秘密可逆线性变换：T \in GL_n(\mathbb F_q)$$

$$构造公开映射： P=F∘T，因此P(x)=F(T(x))$$

$$最终sk=(F,T) \quad pk=$$

2、签名 Sign

$$先计算：y=H(M) \in \mathbb F^m_q ，目标：找出u=(v,o)满足F(u)=y$$

1、随机选择Vinegar

$$随机确定v后v_iv_j变为常数，v_io_j变为oil的一次项$$

$$故而F(v,o)变成了关于o的线性方程组：L(v)o=y-c(v)$$

$$若L(v)可逆则o=L(v)^{-1}(y-c(v)) 则u=(v,o)$$

$$若detL(v)=0则重新随机选择Vinegar$$

2、撤销秘密变换

$$P=F∘T \Rightarrow s=T^{-1}u$$

3、验证 Verify

$$P(s)=F(Tu)=F(TT^{-1}u)=F(u)=H(M)$$

四、主要类型

类型 特点 代价
Classic 公私钥直接展开 Key大，但签名验证快
PKC 公钥压缩 公钥更小，验证更慢
PKC+SKC 公钥和私钥均压缩 Key最小，签名和验证都需要展开

改进：MAYO、QR-UOV、SNOVA 都试图解决UOV公钥太大的问题

UOV优点：签名短，签名、验证速度快、不依赖离散对数、不依赖格困难问题

五、攻击手法

通常分为直接伪造和恢复oil秘密结构

1、直接签名伪造

$$不管Oil、Vinegar的结构，直接求：P(x)=H(M)$$

常见算法：XL,F4,F5,Gro¨bner Basis

2、Kipnis-Shamir Attack

UOV真正的陷门不是单纯的几个变量，而是一个隐藏的Oil子空间O

$$攻击者从公开二次型矩阵：P_1,P_2,…,P_m中恢复O，进而可模仿合法签名过程$$

早期平衡OV时就因为这种隐藏子空间结构过于明显，因此UOV增加了Vinegar数量

3、Intersection Attack

$$对于公开二次型的极化矩阵M_i，Oil空间会产生特殊的像空间M_iO$$

$$利用MiO∩MjO或者 ⋂_iMiO 这些异常交空间恢复Oil子空间$$

4、MinRank Attack

$$寻找公开矩阵的线性组合：M=\sum ^m_{i-1} \lambda_iP_i使得rank(M)非常低，这种低秩结构会泄露隐藏oil空间$$

常见参数

参数组 NIST安全级别 q n m v=n−m
UOV-Ip Level 1 256 112 44 68
UOV-Is Level 1 16 160 64 96
UOV-III Level 3 256 184 72 112
UOV-V Level 5 256 244 96 148