Nearly Optimal Property Preserving Hashing论文阅读

shenyt22 / 2023-05-14 / 原文

论文地址: https://doi.org/10.1007/978-3-031-15982-4_16.

基本概念

PPH族 安全参数\(\lambda\), 消息长度\(n = n(\lambda)\), 摘要长度\(m = m(\lambda)\)均为\(\lambda\)的多项式. 二值谓词\(P: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1,\perp\}\)输入为两个消息. 哈希函数族\(\mathcal{H} = \{h: \{0,1\}^n \rightarrow \{0,1\}^m\}\)对谓词\(P\)是\((n,m)\)-性质保留哈希(PPH)函数族. \(\mathcal{H}\)提供三个接口:

Sample(\(1^{\lambda}\)) \(\rightarrow h\): 取一个哈希函数h.
Hash(\(h, x\)) \(\rightarrow y\): 对消息\(x \in \{0,1\}^n\)计算摘要\(y \in \{0,1\}^m\).
Eval(\(h, y_1, y_2\)): 仅由两个摘要估计消息\(x_0\)和\(x_1\)的谓词结果.
\(\mathcal{H}\)必须满足: \(\forall x_1, x_2 \in \{0,1\}^n\),

\[\mathop{\text{Pr}}\limits_{h \leftarrow \text{Sample}(1^\lambda)} [P(x_1,x_2) \ne \perp \land Eval(h, y_1, y_2) \ne P(x_1,x_2)] = \text{negl}(\lambda). \]

robust PPH族 PPH族满足对适应性选择消息的概率多项式时间敌手, 找到错误的概率可忽略.

汉明谓词 消息长度为\(n\), 汉明距离阈值为\(t < n\), 汉明谓词

\[\text{HD}_{n,t}(x_1, x_2) = \begin{cases} 1, ||x_1 \oplus x_2||_0 \le t,\\ 0, \text{otherwise}. \end{cases} \]

通用哈希函数族 哈希族\(\mathcal{H}\)满足\(\forall x_1, x_2 \in \{0,1\}^n\)且\(x_1 \ne x_2\),

\[\text{Pr}[h(x_1) = h(x_2): h \leftarrow \mathcal{H}] \le 2^{-m}. \]

构造一种简单的通用哈希函数族: \(\mathcal{H}\)中的哈希函数\(h_A(x)\)用矩阵\(A \in \mathbb{Z}^{m \times n}_2\)表征, \(h_A(x) = A \cdot x\). 这样构造的\(\mathcal{H}\)的通用的且满足同态性质\(h_A(x_1) + h_A(x_2) = h_A(x_1 + x_2)\).

编码\(C\) 一个\([n, k]_q\)编码\(C\)是一个线性单射\(C: \mathbb{F}_q^k \rightarrow \mathbb{F}_q^n\). 每个映射值称为一个编码字.

奇偶校验 一个对于编码\(C: \mathbb{F}^k \rightarrow \mathbb{F}^n\)的奇偶校验矩阵\(P \in \mathbb{F}^{(n-k) \times n}\)满足\(c\)为一个编码字当且仅当\(P \cdot c = 0\).

列表解码 一个\([n,k]_q\)编码\(C\)为\(t\)错误下组合列表可解码的, 若\(\forall y \in \mathbb{F}_q^n\), 与\(y\)的汉明距离不大于\(t\)的所有编码字不多于poly(\(n\))个.

故障解码 \(C\)为一个\([n,k]_q\)编码且存在一个奇偶校验矩阵\(P\), \(C\)为\(t\)错误下组合故障列表可解码的, 若\(\forall S \in \mathbb{F}_q^{n-k}\), 满足\(P \cdot e = S\)且汉明重量不大于\(t\)的\(e \in \mathbb{F}_q^n\)不多于poly(\(n\))个.

对于一个编码, 可列表解码和可故障解码是等价的.

构造非robust的PPH族

令\(P\)为一个\([n, k]_2\)编码的奇偶校验矩阵, 可以有效在\(t\)错误下进行列表解码. 可以构造\((n, m)\)-PPH族如下:

Sample(\(1^\lambda\)): 随机取矩阵\(A \leftarrow \mathbb{F}_2^{\lambda \times n}\), 输出哈希函数\(h(x) = (P \cdot x, A \cdot x)\).
Eval(\(h, y_1, y_2\)): 令\(y_1 = (v_1, w_1)\), \(y_2 = (v_2, w_2)\). 对\(S = v_1 - v_2\)进行\(C\)的故障解码, 得到所有的\(e\)列表\(\mathcal{L}\). 若\(\exists e \in \mathcal{L}\), 满足\(A \cdot e = w_1 - w_2\), 则返回1; 否则返回0.