Page 266 - 《软件学报》2020年第11期

侯瑞涛 等:分级可逆的关系数据水印方案 3581

级提升所需的分区嵌入密钥,不会暴露剩余数据分区中水印的嵌入位置.

3 概率分析与参数选择
等级检测算法的基本原理是:从待检测元组中检测出匹配信息,然后将匹配总数与相应参数进行比较,根据
比较结果,得出检测结果.理论上,等级检测算法中的参数τ _i(0≤i≤γ−1)应等于其待检测元组的总数.但在实际
的应用中,水印可能会遭受攻击,所以τ_i(0≤i≤γ−1)一般小于或等于理论值.本节对τ_i(0≤i≤γ−1)进行了概率
分析,为其在实际应用中的选择提供参考.考虑τ_i(0≤i≤γ−1)的选择方式相同,本章的后续部分使用τ来泛指参
数τ_i(0≤i≤γ−1).
3.1 概率分析
假设使用等级检测算法对不包含水印的数据进行检测,则从待检测元组中检测到匹配信息的概率约为 1/2.
我们可以将从 n 个元组中检测到τ个匹配信息的过程看作是τ次成功的 n 重 Bernoulli 实验,每次实验的成功概
率为 1/2,其概率表示如公式(2)所示.
P τ [ matches = ] b τ ( ; ,1/ 2)n = ! n (1/ 2) n (2)
τ !(n τ − )!
令ϕ=τ/n,表示检测到匹配信息的元组比例,则ϕ的概率分布 P(ϕ)满足二项分布,其分布曲线如图 2 所示.

Fig.2 Probability distribution of ϕ with the original data
图 2 原始数据中ϕ的概率分布

假设ϕ min =τ min /n,则由图 1 可知,ϕ位于区间[ϕ min ,1]的概率 P{ϕ min ≤ϕ≤1}=α,而 P{ϕ min ≤ϕ≤1}的概率表示
如公式(3)所示.
n n ! n
ϕ
P {ϕ ≤≤ 1} = b τ∑ ( ; ,1/ 2)n = ∑ (1/ 2) n (3)
min τ !(n τ − )!
ττ= min ττ= min
所以,根据概率论中的“小概率原理”,当α很小时,ϕ几乎不可能落在区间[ϕ min ,1]内.也就是说,从不包含水印
的数据中至少检测出τ min 个匹配信息几乎是不可能发生的.而水印嵌入的目的即改变这种概率分布,使得从嵌
有水印的数据中检测出超过τ min 的匹配信息成为非偶然事件.所以,τ是否落在区间[τ min ,n]即可作为判定数据中
是否包含水印的依据.
3.2 参数选择

由第 3.1 节可知,τ的取值取决于 n 和α.其中,n 由关系数据的元组总数和水印嵌入比例决定,无法随意修改.
所以,此处主要讨论α的取值对τ的影响.
假设 ar 表示某包含水印的关系数据允许被修改的元组比例,其计算公式如公式(4)所示.
n τ−
−
ar = min = 1 ϕ min (4)
n
改变α,ar 的变化如图 3 所示.