Fingerprinting
1. Polynomial Identity Testing (PIT)
- 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$个根, 所以算法结果错误的概率上界为
- 如果取$|S|=2d$, 则错误率至多1/2. 想要错误率小于任意常数$\delta$, 只需要重复$\log_2 \delta$次
1.1 相等问题的通信复杂度
- 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$, trival way: Bob把整个b传给Alice, Alice判断是否$a=b$. 需要$n$传输位
| Theorem (yao 1979) |
| —————————————————————————————— |
| 所有的计算两个n位串是否相等的确定通信协议, 最坏情况下, 需要n传输位 |
随机算法
准备工作
- 用两个度至多为$n-1$的单变量多项式来表示$a, b$,
- $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’
- Bob:
- 通讯复杂度$O(\log p)$
- 错误情况: $f\not\equiv g$但是$f(r)=g(r)$. 因为$f, g$的度至多为$n-1$, $r$是从$p$个数中随机选取, 所以
- 通过选取$p\in[n^2, 2n^2]$(根据切比雪夫, 这样的素数一定存在), 上述错误率至多$O(1/n)$, 通讯复杂度$O(\log n)$, 比确定性算法提升较大
1.2 Schwartz-Zippel Theorem
- | 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}$
- 注意多元多项式中的度为所有变量的指数之和
证明(数归)
- Induction basis:
- $n=1$为单变量情况, 上面已经讨论过
- Induction hypothesis:
- 假设定理对于所有$m$元多项式($m<n$)成立
- Induction step:
- 对于任意至多$d$阶的$n$元多项式$f(x_1,x_2, \cdots, x_n)$, 将$f$写成其中$k$为$x_n$的最高度, 也就是$f_k$的度至多为$d-k$, 且$f_k\not\equiv 0$
- 具体的, 把$f$分成两部分:其中:
- $f_k\not\equiv0$定义如上, 度至多$d-k$
- $\bar f(x_1,x_2,\cdots, x_n)=\sum_{i=0}^{k-1}x_n^i f_i(x_1,x_2,\cdots, x_{n-1})$, 因此$\bar f$中没有带$x_n^k$的项
- 其中$f_k(r_1,r_2,\cdots, r_{n-1})$是$n-1$变量$d-k$阶多项式, 且$f_k\not\equiv 0$. 根据猜想, 我们有
- 考虑条件$f_k(r_1,r_2, \cdots, r_{n-1})\ne 0$.该条件保证了是一个非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|}$
- 因此
- 因此得证.
2. Fingerprinting
使用指纹的相等判断的通信协议
- 使用指纹函数$FING(\cdot)$来判断
2.1 Fingerprinting by PIT
- $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$,
2.2 Fingerprinting by randomized checksum
- $a,b\in [2^n]$
- $FING(x)=x\mod p$, $p$为$[k]$中素数, $k$待定
- 通信$O(\log k)$bits
- $\pi(k)$为小于$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$个素因子,
3 Checking distinctness
3.1 Fingerprinting multisets
- 问题: 两个多重集$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)$
- 分两种情况: