Multivariate Cryptography

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层

\[ \begin{align}\begin{aligned}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 }\end{aligned}\end{align} \]

可见 \(V_2\) 迭代覆盖 \(V_1 + O_1\)

\[ \begin{align}\begin{aligned}m = n - v_1\\l = 1, ..., u\end{aligned}\end{align} \]

每个l对应的 \(V_l + O_l\) 都对应一个方程

迭代求解时，例如已知 \(y (y_1, ..., y_m)\) ，随机选择 \(x_1, ..., x_{v1}\)

根据 \(y_1, ..., 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

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)

解密：

\[ \begin{align}\begin{aligned}x = S^{-1} (w)\\F(y) = x\end{aligned}\end{align} \]

将 \(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 如果都不可逆，解密就会失败