(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210890065.2 (22)申请日 2022.07.27 (71)申请人 南京航空航天大 学 地址 210016 江苏省南京市秦淮区御道街 29号 (72)发明人 朱友文　金严　 (74)专利代理 机构 南京合砺 专利商标代理事务 所(普通合伙) 32518 专利代理师 许云花 (51)Int.Cl. G06F 21/60(2013.01) G06F 21/62(2013.01) G06F 21/64(2013.01) (54)发明名称 一种基于拉格朗日插值法的数据库水印方 法 (57)摘要 本发明公开了一种基于拉格朗日插值法的 数据库水印方法， 分割二进制水印信息并以此作 为多项式系数来确定有限域上的多项式， 嵌入数 据库中的是该多项式上的点集。 根据数据库的属 性名对属性进行排序、 根据密钥和数据库中元组 的主键对元 组分组； 同一分组 内的元组嵌入相同 的点； 然后可发布共享数据库， 从发布的数据库 中提取水印用于保护版权和验证数据完整性。 本 发明基于拉格朗日插值法， 在强删除攻击下仍可 正确提取 水印， 对删除攻击有很高的鲁棒 性。 权利要求书2页 说明书7页 附图4页 CN 115481412 A 2022.12.16 CN 115481412 A 1.一种基于拉格朗日插值法的数据库水印方法， 其特征在于： 所述方法包括将水印明 文转为二进制串， 然后 分割该二进制串得到若干个数， 由该数作为系数， 确 定有限域GF(p) 上的多项式f(x)， 由多项式中的若干个点 嵌入数据， 水印提取时， 通过拉格朗日插值法还原 多项式以实现。 2.根据权利要求1所述的基于拉格朗日插值法的数据库 水印方法， 其特征在于： 该方法 包括建立数据库用于水印的嵌入和提取， 步骤如下： S1、 水印编码： 用户向水印嵌入系统提交水印明文， 并将水印明文转为二进制串， 分割 该二进制串得到若干个数， 以分割得到的数作为系数， 确定有限域GF(p)上的多 项式f(x)； S2、 预处理： 对属性按照属性名进行排序， 依据密钥和主键值对数据库内的每条元组进 行分组； S3、 嵌入水 印： 嵌入多项式f(x)上点(x， y)， 每条元组中， 依据密钥和主键值分别选择嵌 入x、 y的属性， 各个分组内各 元组嵌入相同的点； S4、 预处理： 用户向水印提取系统提交嵌入水印的数据库， 水印提取系统对该数据库的 属性按照属性名进行排序， 依据密钥和主键值对数据库内的每条 元组进行分组； S5、 提取水印： 对每条元组， 先依据密钥和主键值分别选择嵌入点的属性， 再提取该元 组中蕴含的点， 组内按照投票机制 选择出现次数最多的点作为该组蕴含的点， 每个分组都 可得到一个点； S6、 水印解码： 由提取到的点集根据拉格朗日插值法还原多项式， 多项式系数转为二进 制并拼接可 得到二进制的水印， 再将该比特串解码可 得到水印明文。 3.根据权利要求2所述的基于拉格朗日插值法的数据库水印方法， 其特征在于： 步骤S1 水印编码的具体步骤如下： (1)水印嵌入系统将水印明文转 为长为l的二进制比特串； (2)长为l的比特串平均分割为m组， 确定有限域GF(p)上的m ‑1次多项式f(x)， 在删除比 例为r时， 按如下公式得到有限域大小p、 分割组数m， 上式中， M是l的因子的集合， next_prime(x)表示大于x的最小的素数， 遍历M， 找到使得 h(m)最小的m， 该m即为最优的分割组数， 每组长度为g＝l/ m， 得到函数最小值q， 计算 嵌入属 性中的比特 数， 即 比特， 接下来可确定有限域大小p， 表达式如下： p＝next_prime(2t‑1)。 4.根据权利要求1所述的基于拉格朗日插值法的数据库 水印方法， 其特征在于： 在步骤 S2中依据密钥和主键值对数据库进行分组， 包括遍历数据库的各元组， 计算数据中各元组 的组号， 计算表达式如下 所示： H(ks||H(ks||tu.PK))mod p 上式中H(·)为哈希函数， ks为密钥， tu.PK为元组tu的主键值。 5.根据权利要求1所述的基于拉格朗日插值法的数据库水印方法， 其特征在于： 步骤S3 中， 嵌入水印的过程如下： 各元组中， 选择嵌入水印(多 项式f(x)上的点(x， y) )的属性， 嵌入 x的属性索引为： xindex＝H(ks||H(ks||tu.PK))mod attribute_num权　利　要　求　书 1/2 页 2 CN 115481412 A 2嵌入y的属性索引为： yindex＝(xindex+1)mod attribute_num 上述索引均为属性 排序后的索引； 其中， 对于不同的数据类型的水印嵌入方式包括如下三种情况： (a)若数据类型为字符串， 则在字符串末尾添加空白字符以嵌入点， 使用32个空白字 符， 一个空白字符可表示5bit信息， 数据尾嵌入 个空白字符； (b)若数据类型为整数， 则转换为 二进制并修改最后t比特以嵌入点； (c)若数据类型为 浮点数， 则将小数部分转换为 二进制并修改最后t比特以嵌入点。 6.根据权利要求1所述的基于拉格朗日插值法的数据库 水印方法， 其特征在于： 在步骤 S5中， 提取 水印过程如下： 各元组中， 选择待提取 水印(点(x， y) )的属性， 嵌入 x的属性索引为： xindex＝H(ks||H(ks||tu.PK))mod attribute_num 嵌入y的属性索引为： yindex＝(xindex+1)mod attribute_num 上述索引均为属性 排序后的索引； 其中， 对于不同的数据类型的水印提取 方式包括如下三种情况： (a)若数据类型为字符串， 读取字符串末尾的 个空白字符， 并转换为十进制得到 点； (b)若数据类型为整数， 则转换为 二进制并取最后t比特转换为十进制得到点； (c)若数据类型为浮点数， 将小数部分转换为二进制并取最后t比特转换为十进制得到 点； 最后， 每组内统计不同点的出现次数， 选择出现次数最多的点作为从该组提取得到的 点， 若该组出现不止一种点， 则说明数据被篡改。 7.根据权利要求1所述的基于拉格朗日插值法的数据库 水印方法， 其特征在于： 在步骤 S6中， 水印解码的运行步骤为： 首先根据步骤S5提取得到的点中抽样选取m个点， 利用拉格朗日插值法可还原m ‑1次多 项式f′(x)， 计算如下： 接着， f′(x)的各个系数分别转 为g位的比特串并拼接， 最终得到l 位的水印比特串。权　利　要　求　书 2/2 页 3 CN 115481412 A 3