PQC: Multivariate Cryptography
- overview
- UOV : Unbalanced Oil and Vinegar signature scheme
- Rainbow Signature
- SimpleMatrix (ABC) Encryption
overview
public key cryptography Multivariate crypto
Current State of Multivariate Cryptography
S : m -> m 的映射
F : n -> m 的映射，一元二次方程组
T : n -> n 的映射
公钥 P = S . F . T : n -> m 的映射
UOV : Unbalanced Oil and Vinegar signature scheme
n = o + v
V = { 1, …, v }
O = { v+1, …, n }
如果 o = v ，称为 Balanced Oil and Vinegar
如果 v > o，称为 Unbalanced Oil and Vinegar
center map , F : n -> o
注意多项式中的x_i*x_j项，要么是 i, j均属于V，要么是i属于V且j属于O。
仅有T，没有S。
公钥 P = F . T
F^-1求解时，例如已知y ( y_1, …, y_o)，随机选择 x_1, …, x_v，可代入求解得到 x_v+1 , …, x_n
签名计算：hash(message) = w, 通过w求F^-1的逆x，再求解T^-1的逆z，z即为签名。
签名校验：w’ = P(z)，比较w = w’
Rainbow Signature
分多个Vinegar + Oil层
0 < v_1 < v_2 < … < v_u+1 = n
V_1 : { 1, …, v_1 }, O_1: { v_1 + 1, …, v_2 }
V_2 : { 1, …, v_2 }, O_2: { v_2 + 1, …, v_3 }
可见V_2迭代覆盖 V_1 + O_1
m = n - v_1
l = 1, …, u
每个l对应的V_l + O_l都对应一个方程
迭代求解时，例如已知 y (y_1, …, y_m)， 随机选择x_1, …, x_v1
根据 y1, …, y_v2-v1 求得 x_v1+1, …, x_v2
根据 y_v2-v1+1, …, y_v3-v1 求得 x_v2+1, …, x_v3
其他与UOV一致
HFE: Hidden Fields Equations
Solving Systems of Quadratic Equation
F 为有限域多项式
SimpleMatrix (ABC) Encryption
Simple Matrix Scheme for Encryption
Simple Matrix – A Multivariate Public Key Cryptosystem (MPKC) for Encryption
n = s^2
m = 2*n
A, B, C 为3个 s x s 的矩阵
E1 = A . C, E2 = B . C
central map F : 由E1, E2拼成，m个方程
公钥 P = S . F . T ， n -> m
加密：w = P(z)
解密：
x = S^-1 (w)
F(y) = x
将 x = (x_1, …, x_m) 拆入 E1, E2，其中，x_1, …, x_n 为E1的对角线，x_n+1, …, x_m 为E2的对角线
根据E1, E2, A的可逆状况，分类型求解。
例如，如果A可逆，
求解 A^-1 . E1 - B = 0, A^-1 . E2 - C = 0
得到 A^-1 的 r_1, ..., r_n
r1, ..., r_n, y_1, ..., y_n 结合得到m元，运用高斯消元，恢复 y_1, ..., y_n
问题
E1, E2, A 如果都不可逆，解密就会失败
