Fingerprinting

1. Polynomial Identity Testing (PIT)

问题
- 输入: 两个多项式$f$, $g\in \mathbb F [x]$(单变量域(filed)), 度都为$d$(最高次项次数)
- 确定是否有$f\equiv g$
度为$d$的多项式$f\in \mathbb F[x]$为$f(x)=\sum_{i=0}^d a_ix^i$, $a_i\in \mathbb F$
假设$f$为黑盒, 因此不能直接判断$a_i$是否为0
确定性解法
- 从$\mathbb F$中取$x_1, x_2, \cdots, x_{d+1}$, 判断$f(x_1), f(x_2), \cdots, f(x_{d+1})$是否都为0
- 根据:
  
  | 算数基本定理 |
  | ——————————————————— |
  | 任意度为$d$的单变量多项式至多有$d$个根 |

算法:
- 假设有有限集$S\subseteq \mathbb F$
- 随机选取$r\in S$
- 如果$f(r)=0$返回’yes’, 否则返回’no’
若$f=0$, 必定返回’yes’, 正确
若$f\neq 0$, 也有可能返回’yes’. 但是因为$f$至多有$d$个根, 所以算法结果错误的概率上界为
$Pr[f(r)=0]\le \frac{d}{|S|}$
如果取$|S|=2d$, 则错误率至多1/2. 想要错误率小于任意常数$\delta$, 只需要重复$\log_2 \delta$次

Alice有私密输入a, Bob有私密输入b, 他们希望通过通信协议来计算函数$f(a,b)$. 通信复杂度是最坏情况下Alice和Bob之间需要传输的bit数
判断相等性的函数为$EQ: \{0,1\}^n\times \{0,1\}^n\to \{0,1\}$

对于任意$a, b\in\{0,1\}^n$,
$EQ(a,b)=\begin{cases} 0 & a=b \\ 1 & a\ne b \end{cases}$
trival way: Bob把整个b传给Alice, Alice判断是否$a=b$. 需要$n$传输位

| Theorem (yao 1979) |
| —————————————————————————————— |
| 所有的计算两个n位串是否相等的确定通信协议, 最坏情况下, 需要n传输位 |

准备工作
- 用两个度至多为$n-1$的单变量多项式来表示$a, b$,
  $f(x)=\sum_{i=0}^{n-1}a_ix^i, g(x)=\sum_{i=0}^{n-1}b_ix^i$
- $f$和$g$定义在有限域$\mathbb Z_p=\{0,1,\cdots, p-1\}$上, $p$为合适的素数
A randomized protocol for EQ
- Bob:
  - 随机选择$r\in \mathbb Z_p$
  - 发送$r$和$g(r)$给Alice
- Alice收到后
  - 计算$f(r)$
  - 如果$f(r)=g(r)$返回’yes’; 否则返回’no’
通讯复杂度$O(\log p)$
错误情况: $f\not\equiv g$但是$f(r)=g(r)$. 因为$f, g$的度至多为$n-1$, $r$是从$p$个数中随机选取, 所以
$Pr[f(r)=g(r)]\le \frac{n-1}{p}$
通过选取$p\in[n^2, 2n^2]$(根据切比雪夫, 这样的素数一定存在), 上述错误率至多$O(1/n)$, 通讯复杂度$O(\log n)$, 比确定性算法提升较大

| Schwartz-Zippel Theorem |
| —————————————————————————————— |
| 令$f\in \mathbb [x_1,x_2, \cdots, x_n]$为$\mathbb F$中度为$d$的多元多项式. 如果$f\not\equiv 0$, 那么对于任意有限集合$S\subset F$, 随机选取$r_1, r_2, \cdots, r_n\in S$, $Pr[f(r_1, r_2, \cdots, r_n)=0]\le \frac{d}{|S|}$. |
Schwartz-Zippel Theorem定理说明对于任何非0的$n$变量度为$d$的多项式, 在任意立方体$S^n$中的根的数量至多为$d\cdot |S|^{n-1}$
注意多元多项式中的度为所有变量的指数之和

$Pr[f(r_1,r_2,\cdots,r_n)=0]\\= Pr[f(\vec r)=0|f_k(r_1,r_2,\cdots, r_{n-1})=0] \cdot Pr[f_k(r_1,r_2,\cdots, r_{n-1})=0]\\ + Pr[f(\vec r)=0|f_k(r_1,r_2,\cdots, r_{n-1})\ne 0] \cdot Pr[f_k(r_1,r_2,\cdots, r_{n-1})\ne 0]$
其中$f_k(r_1,r_2,\cdots, r_{n-1})$是$n-1$变量$d-k$阶多项式, 且$f_k\not\equiv 0$. 根据猜想, 我们有
$Pr[f_k(r_1,r_2\cdots,r_{n-1})=0]\le \frac{d-k}{|S|}$
考虑条件$f_k(r_1,r_2, \cdots, r_{n-1})\ne 0$.该条件保证了
$f(r_1,\cdots, r_{n-1},x_n)=x_n^kf_k(r_1,r_2,\cdots,r_{n-1})+\bar f(r_1,r_2,\cdots,r_{n-1},x_n)=g_{r_1\cdots r_{n-1}}(x_n)$
是一个非0的单变量$x_n$的多项式, 且度为k, 且$g_{r_1\cdots r_{n-1}}\not\equiv 0$. 因此$g_{r_1\cdots r_{n-1}}(r_n) =0$的概率至多$\frac{k}{|S|}$
因此
$\begin{aligned} &Pr[f(\vec r)=0|f_k(r_1,r_2,\cdots, r_{n-1})\ne 0] \\ =&Pr[g_{r_1\cdots r_{n-1}}(r_n) =0|f_k(r_1,r_2,\cdots, r_{n-1})\ne 0] \le \frac{k}{|S|} \end{aligned}$
因此
$Pr[f(r_1,r_2,\cdots,r_n)=0]\le \frac{d-k}{|S|}+\frac{k}{|S|}=\frac{d}{|S|}$
得证.

使用指纹的相等判断的通信协议

$FING(x)=\sum_{i=1}^n x_ir^i$, 运算都在$\mathbb Z_p$中, $r$是$\mathbb Z_p$中的均匀随机数, $p$是合适的$[n^2, 2n^2]$的素数
只需要$O(\log p)=O(\log n)$bits
对于不同的$x$和$y$,
$Pr[FING(x)=FING(y)]\le \frac{n-1}{p}\le \frac{1}{n}$

$a,b\in [2^n]$
$FING(x)=x\mod p$, $p$为$[k]$中素数, $k$待定
通信$O(\log k)$bits
$\pi(k)$为小于$k$的素数的数量, 有
$\pi(k)\sim \frac{k}{\ln k}$
对于$x\ne y$, $Pr[x\equiv y\mod p]=Pr[z \mod p=0]\le$ z的素因子数/$[k]$的素数数
选择$k=2n^2\ln n$, $0<z<2^n$至多$n$个素因子,
$Pr[z\mod p = 0]\le \frac{n}{\pi(k)}\sim \frac{1}{n}$

问题: 两个多重集$A=\{a_1,a_2,\cdots,a_n\}$, $B=\{b_1,b_2,\cdots, b_n\}$, $a_i,b_i\in\{1,2,\cdots,n\}$ , 判断是否$A=B$
选择素数$p\in [(n\log n)^2, 2(n\log n)^2]$. $Z_p=[p]$. 对于多重集$A$, 定义$\mathbb Z_p$上单变量多项式$f_A\in\mathbb Z_p[x]$: $f_A(x)=\prod_{i=1}^n(x-a_i)$, 其中运算都是$\mathbb Z_p$中的. 定义$FING(A)=f_A(r)=\prod_{i=1}^n(r-a_i)$, 其中$r$是$\mathbb Z_p$中随机数
$A\neq B$的情况下, $Pr[FING(A)=FING(B)]=O(\frac{1}{n})$
- 分两种情况:
  - $f_A\equiv f_B$(模p后), 说明至少有一组不同的系数($\le n^n$)模p后相等, 概率$\le \frac{n\log_2 n}{\text{区间内素数数}}=O(1/n)$
  - $f_A\not\equiv f_B$但是$f_A(r)=f_B(r)$, 根据Schwartz-Zippel Theorem, 概率$\le n/p=O(1/n)$