BobH 博客

[BobH 博客引流](https://bobh.mkaliez.com/)  [题解 CF1225D 【Power Products】](https://bobh.mkaliez.com/archives/70/) [BobH的gal引擎](https://bobh.mkaliez.com/archives/67/) [长沙十天集训总结](https://bobh.mkaliez.com/archives/66/) [长郡第3次集训总结](https://bobh.mkaliez.com/archives/65/) [2019.3 长郡省选集训算法总结](https://bobh.mkaliez.com/archives/64/) [使用PHP搭建一个自己的英文句式搜索引擎](https://bobh.mkaliez.com/archives/62/) [Vue学习笔记](https://bobh.mkaliez.com/archives/40/) [如何使Typecho博客快速被百度收录](https://bobh.mkaliez.com/archives/38/) [数列的递推形式](https://bobh.mkaliez.com/archives/28/) [斜率优化学习笔记](https://bobh.mkaliez.com/archives/22/) [高等数学学习笔记](https://bobh.mkaliez.com/archives/21/) [使用docker安装gitlab中文版记录](https://bobh.mkaliez.com/archives/19/) 一下内容为无关项： # 5-8段翻译 ## 执行 **任波翰** ## 2.个性化的匿名 ### 2.x **前面的人翻译** ### 2.3.2 非主要案例 ​ 我们继续来分析 $T.Ai$ 不是 T 的主键的情况，即每个人在 T 中可以出现任意次数。之前的工作没有解决过这种情况。 ​ 定义10.（非主要可能的重建）在非主要情况下，给定个体**o**，一个可能的,对基本 $QI-groupEG(o)$ 的重建包括以下几点： ​ (1) 一个个体的可重集合 {$o_1,...,o_m$} (可以有重复)，其中不同的元素构成 $Sext（o）$的子集 ​ (2) m 叶子节点的敏感度 $v_1,...,v_m$,比如 $v_j(1 ≤ j ≤ m)$ 在 $SUBTR(t_j^* . A^s)$ ​ 例子2.让我们重新审视对手获得的 $Sext(Ken) = \{Andy,Bill,Ken,Nash,Mike\}$ . $m,n,t_1^*,...,$ and $ t_4^*$ 和例子1是一样的 ​ 在可能的重建中，攻击者可以将所有 $o1，...，o4$ 设置为 $Ken$（在主要情况下不允许）。确定 $v1，...，v4$ 的方式与例1中的相同，让我们假设 $v_1 = gastric-ulce$ , $v_2 = dyspepsia$ , $v_3 = flu$ , $v_4 = bronchitis$。通过这次重建，对手认为 $Ken$ 收缩了所有这四种疾病。 显然，猜想没有正确反映微观数据，但它导致了图1a中元组3的隐私泄露。  ​ 由于 $o1，...，o4$ 中的每一个可以独立地是 $\{Andy，Bill，Ken，Nash，Mike\}$ 中的任何一个，因此存在54 = 625个选择来决定 $o1，...，o4$。 鉴于每个决定，由于实施例1中给出的原因，有9种方法来制定 $v1，...，v4$ 。 因此，可能的重建总数等于 $625×9 = 5625$。 ​ 当且仅当 $Ken$ 被分配到$o3$或$o4$时，重建违反了微数据中元组3的隐私约束。如果 $o3 = Ken$，$o1，o2，o4$ 可以是 $Sext（Ken）$ 中的任何人，因此可以以 $53 = 125$ 种方式分配。 无论分配如何，$ v1，...，v4$ 可以以9种方式设置，导致 $125×9 = 1125 $ 种不同的重建。 同样，如果 $o4 = Ken$ ，则存在另一个$1125$，但其中一些（其中$o3 = o4 = Ken$ ）已被计数两次。 具体而言，如果$ o3 = o4 = Ken$ ，则确定$o1$和$o2$有25种可能性，而对于每种可能性，存在9种用于决定$v1，...，v4$的选择。 因此，重复计算的重建次数等于$25×9 = 225$。 ​ 因此，总共 $1125 + 1125-225 = 2025$ 次重建违反了图1a中元组3的隐私。因此，元组的违反概率等于$2025/5625 = 9/25$。 ​ 通过上述程序获得违规的概率非常麻烦。 在下一节中，我们将展示直接返回概率的闭合公式。 然后，验证图3的表是否允许图1a中的元组在不超过50％的概率情况下被破坏将变得简单。 ## 3.理论基础 ​ 在本节中，我们解决了在定义3中制定的概率$P_{breach}(ttar) $，其中 $t_{tar}$ 是$T$中的任意元组(下标表示“目标”).显然，如果$t_{tar}$的保护节点$t_{tar}.G.N$ 是空集，$P_{breach}(t_{tar})$ = 0, $i.e.$ ,隐私控制是必需的。接下来，我们聚焦在$t_{tar}.G.N$ 不是空集的情况上。 ​ 第3.1节首先阐述了符号及其属性，这些符号将在我们的推导中使用。然后，第3.2节将$P_{breach}(t_{tar})$解析为闭合公式，基于此，第3.3节指出了 $k-anonymity$ 的缺陷。 ### 3.1 符号和基本属性 ​ 按照2.3节中的符号，我们使用 $o_{tar}$ 来表示$t_{tar}.A^i$标识的人，以及 $t_{tar}$ 的广义元组的$t_{tar}^*$。此外，令 $m$ 为相应的基本 $ QI-groupEG（o_{tar}）$（定义7）的大小，其元组分别表示为$t_1^*，...，t _m^*$（其中一个是$t^*_{tar}$）。$S_{real}(o_{tar})$指的是一组个体，其记录（在微观数据T中）被推广到 $EG(o_{tar})$。最后，我们为 $Sext(o_{tar})$（定义8）的基数部署n。 ​ 作为一级方程式的直接推论，我们有：$ n ≥ |S_{real}(o_{tar})| $ 在主要情况下，$ |S_{real}(o_{tar})| $始终等于$m$，因为 $EG(o_{tar})$中的每个元组都由不同的人拥有。但是，在非主要情况下，$ |S_{real}(o_{tar})| $ 可以是 $[1，m]$中的任何值。此外，无论$EG(o_{tar})$的大小，$ |S_{real}(o_{tar})| $ 可以取最小值1，如果$EG(o_{tar})$中的所有元组都属于同一个人，则会发生这种情况。 ​ 我们在$EG(o_{tar})$中引入b作为元组 $t ^ *_ j（1≤j≤m）$的数量，使得 $SUBTR（t ^* _j.A^s）$与 $ SUBTR（t_{tar}.GN）$重叠。例如，假设$t_{tar}$是元组 图1a中的1，即 $t_{tar}.GN = stomach-disease$。 因此，在图3中，$EG（o_{tar}）$ 涉及元组1-4，并且$m = 4$.由于$SUBTR（t_{tar}.GN）$与$EG（o_{tar}）$中元组1和2的$A^s$值的子树重叠，因此我们$b = 2$。 ​ 我们定义了与$F_{subsize}$和$F_{percent}$相关的两个函数元组,具体而言$F_{subsize}(t^*)$等于数量$SUBTR(t^*.A^s)$中的叶子值(例如$SUBTR(t^*.A^s)=3 $ 如果 $t^*.A^s =respiratory-infection $)，另一方面: ​ (1) $F_{percent}（t^*,t_{tar}）$ 等于$SUBTR(t^*.A^s) $ 中叶子值的百分比，他们也在$SUBTR(t_{tar}.GN) $中 ​ 因此，它遵循 ​ (1) $F_{percent}（t^*,t_{tar}）=1$ 如果 $t^*.A^s$ 在 $SUBTR(t_{tar}.GN) $中 ​ (2) $F_{percent}（t^*,t_{tar}）=0$ 如果 $SUBTR(t^*.A^s) $ 与 $SUBTR(t_{tar}.GN) $ 不相交 ​ 我们举例说明$F_{percent}$，假设$t_{tar}.GN= respiratoryinfection $。如果$t^* .A^s = respiratory-system-problem $，那么$F_{percent}（t^*，t_{tar}）= 50％$，因为$t^*.A^s$有6种叶子病，其中一半位于$SUBTR（t_{tar}.GN）$。 作为另一个例子，如果$t^* .A^s$是flu，它在$SUBTR（t_{tar}.GN）$中; 因此，$F_{percent}（t^*，t_{tar}）= 100％$。 最后，给定$t^* .A^s =stomach-disease $（其子树与$SUBTR（t_{tar}.GN）$不相交），$F_{percent}（t^*，t_{tar}）= 0$。 ​ **引理1**.对于$EG（o_{tar}）$中的所有元组$t^*_j$（$1≤j≤m$），$F_{percent}（t ^* _j，t_{tar}）$等于0或常数. ​ **证明**（草图）通过对称性，足以证明引理对于$j = 1$.如前所述，如果$SUBTR（t^* _1.A^s）$不重叠$SUBTR（t_{tar}.GN）$，$F_{percent}（t ^* _1，t_{tar}）= 0$.否则，我们区分两种情况：（i）$t^ * _1.A^s$是$t_{tar}.GN$的祖先，或者（ii）它在$SUBTR（t_{tar}.GN）$。 由于空间限制，我们讨论只有第一个场景。 ​ 考虑任何其他元组$t^ *_ j（2≤j≤m）$。 如果是$SUBTR（t ^*_ j .A^s）$与$SUBTR（t_{tar}.GN）$不相交，$F_{percent}（t ^*_ j，t_{tar}）= 0$.如果没有,我们将证明 $t ^*_j .A^s = t ^* _1.A^s$，因此，$F_{percent}（t^ *_ j，t_{tar}）= F_{percent}（t ^* _1，t_{tar}）$。相反，假设$t^ *_ j .A^s = t^ *_ 1.A^s$.回想一下，$SUBTR（t^ *_ 1.A^s）$涵盖了整个$SUBTR（t_{tar}.GN）$。因此，如果$t^ *_ j .A^s$有一个子树重叠$SUBTR（t_{tar}.GN）$，$T ^*_j .A^s$和$t ^* _1.A^s$成为一般的两个交叉分区$A^s$的域名。 这是不可能的，因为所有分区都必须不相交。 ​ 因此，在续集中，我们避免使用$F_{percent}$的符号用c表示$F_{percent}（t ^*_ 1，t_{tar}），...，F_{percent}（t ^*_ m，t_{tar}）$的非零值 ### 3.2 违约概率的推导 ​ 如第**2.3**节所述，为了推断$o_{tar}$的$A^s$值，对手根据**定义9（或10）**重建$EG（o_{tar}）$原始（或非原始）场景。 无论如何，我们使用$n_{recon}$来捕获可能的重建和$n_{breach}$的总数对于违反隐私约束的重建次数由$t_{tar}.GN$强制执行。 它遵循 $P_{breach}(t_{tar}) = n_{breach}/n_{recon}$ (3) ​ 接下来的两个定理分别解决了原始和非主要情况的$P_{breach}（t_{tar}）$ ​ **结论1**.在主要案例中，$P_{breach}（t_{tar}）= \begin{cases}b/n&如果\; t_{tar}^*.A^s在 SUBTR(t_{tar}.GN)里面\\b.c/n&否则\end{cases}$ ​ **证明** （草图）我们关注的是$t_{tar}.A^s$在$SUBTR（t_{tar}.GN）$中的场景，因为推理也扩展到了其他场景。有很多种方法可以将$o_1，…，o_m$（**定义9**中定义）设置为m个性别的人（$o_tar$），大小为n。独立而言，每个$v_j（1≤j≤m）$都有$F_{subsize}（t_j^*）$选项。因此，$n_{recon}=Permu（n，m）. \prod_{j=1}^mF_{subsize}(t_j^*)$子尺寸（$t_ j$）。 ​ 让$t_1^*，…，t_b^*$是$EG（o_{tar}）$中的所有元组，这样它们的$A^s$值的子树与$SUBTR（t_{tar}.GN）$重叠。在可能违反$t_{tar}$隐私要求的重建中，必须选择$o_{tar}$作为$o_1，…，o_b$之一。对于每个选择，$o_1，…，o_m$的其他元素可以以$Permu（n-1，m-1）$方式设置为S_{ext}（o_{tar}）$中的$m-1$个个体。因此： $n_{breach}=b.Permu(n-1,m-1)·\prod_{j=1}^mF_{subsize}(t_j^*)$ ​ 然后，等式3可以求解为 $P_{breach}（t_{tar}）= b / n$ ​ 例3.我们用图1a，1b说明了这个定理，3.假设ttar（或t * tar）是图1a（或图3）中的元组3。 因此，t *tar.As= ttar.GN =呼吸道感染，和EG（otar）涉及图3中的前4个元组图1b，Andy，Bill，Ken，Nash，Mike可能参与其中在EG（otar）中，渲染n = 5.此外，b = 2，因为元组3,4中的As值的子树（图3）重叠SUBTR（ttar.GN）。 因为t * tar.As在SUBTR（ttar.GN）中，所以定理1，Pbreach（ttar）= b / n = 2/5，证实了分析在例1中。