UtiliClear方案教学文档：隐私保护数据库指纹中的认证可用性保障

1. 方案概述

UtiliClear是一种支持修改范围可验证的隐私保护数据库指纹系统，旨在实现两个核心目标：

1. 允许数据库拥有者(DO)在数据库中嵌入指纹以追踪数据泄露源
2. 允许接收者验证DO在嵌入指纹时是否超出了设定的最大修改范围

方案通过结合FPV(模糊扰动验证)协议和Pedersen承诺机制，实现了：

• 对重要数据位的不可篡改承诺
• 对非重要数据位修改范围的模糊验证
• 指纹的唯一绑定和可提取性

2. 核心定义与协议

2.1 FPV协议定义

一个(n, t)-FPV协议由三个算法组成：

FPV.Setup(κ) → (pk, sk)

• 输入：安全参数κ
• 输出：公私钥对<pk, sk>
• 作用：初始化协议参数

FPV.Lock(sk, pk, x) → (y, vp)

• 输入：二进制串x∈{0,1}^n，私钥sk，公钥pk
• 输出：锁定字符串y，验证参数vp
• 作用：对x进行加锁，使后续可验证但无法推断原文

FPV.Verify(y, x′, vp, k, t) → (1/0)

• 输入：修改后的字符串x'，验证参数vp，编码参数k，容错阈值t，锁定字符串y
• 输出：验证结果(1通过/0失败)
• 作用：验证修改的比特数是否≤t

2.2 FPV协议安全性要求

Fuzzy-binding(模糊绑定)

• 保证修改后的比特串x'只有当Dis(x,x′) ≤ t时才可以通过验证
• 防止恶意证明者构造(x,x′,y′)使得Dis(x,x') > t但验证通过

Full-hiding(完全隐藏)

• 验证者无法识别x′与原始x的差异位置
• 只能知道改动是否超过t位，无法知道具体改动位置

3. UtiliClear核心算法

3.1 系统初始化

UtiliClear.Setup(κ) → (pp, kpo, kpr)

• 输入：安全参数κ
• 输出：
  • 公共参数pp
  • DO的公私钥对kpo = (pk, sk)
  • 接收者的签名密钥对kpr = (pksig, sksig)

3.2 预处理阶段

UtiliClear.Preproc(R, pp, kpo, nc, ng, P) → (Ψ, Φ, OP, VP)

• 输入：
  • 原始数据库R
  • 公共参数pp与DO密钥对kpo
  • 列数nc，每列分组数ng
  • 无关位范围集合P = {s_i, e_i}
• 输出：
  • 重要位的承诺集Ψ与验证参数OP
  • 无关位的锁定值Φ与验证参数VP

处理逻辑：

1. 对重要位使用Pedersen Commitment做不可篡改承诺
2. 对无关位使用FPV协议做模糊绑定

3.3 指纹嵌入

UtiliClear.Fingembed(R, kpr, nc, ng, P, t, sk, ID) → (f, 𝐑𝐑)

• 输入：
  • 原始数据库R
  • 接收者签名密钥kpr
  • 参数：列数nc，分组数ng，无关位范围P，可修改位数t
  • DO私钥sk，接收者身份ID
• 输出：
  • 指纹f
  • 指纹嵌入后的数据库𝐑𝐑

指纹生成过程：

1. 接收者随机选择ζ，生成签名sign_{ID‖ζ}
2. DO验证签名后计算指纹f = H(ID || ζ)
3. 将f嵌入到R的无关位中，得到𝐑𝐑

3.4 验证阶段

UtiliClear.Verify(𝐑𝐑, pp, nc, ng, k, t, P, Ψ, OP, Φ, VP) → (0/1)

• 输入：
  • 指纹数据库𝐑𝐑
  • 公共参数pp
  • 验证材料(Ψ, OP, Φ, VP)
  • ECC参数k，容错阈值t
• 输出：验证结果(1通过/0失败)

验证逻辑：

1. 重要位：通过Pedersen commitment验证是否未改动
2. 无关位：通过FPV.Verify验证修改是否≤t
3. 所有分组满足则通过，否则失败

3.5 指纹提取

UtiliClear.Fingextract(R, 𝐑𝐑, nc, ng, P, lf, t, sk) → (f′)

• 输入：
  • 原始数据库R与指纹数据库𝐑𝐑
  • 参数：列数nc，分组数ng，无关位范围P
  • 指纹长度lf，可修改位数t，DO私钥sk
• 输出：提取的指纹f'

提取过程：

1. 使用私钥和伪随机种子定位嵌入位置
2. 逐位比对恢复指纹f'
3. 用于识别数据泄露源

4. FPV协议技术实现

4.1 核心思想

通过构造嵌入式错误码字cw′ = x⊕x′⊕cw，将修改差异转移到纠错码字cw = ECₙ,ₜ(m)上：

• 检查cw′是否可正确解码(DCₙ,ₜ(cw′) = m)
• 验证x′和x之间最多相差t位

4.2 详细构造

初始化阶段

• 证明者执行FPV.Setup，调用GM.KeyGen(κ)生成公私钥⟨pk, sk⟩

锁定阶段

1. 证明者加密Cx = GM.Enc(x, pk)
2. 验证者生成扰动串u和置换种子δ
3. 验证者加密扰动串：Cu = GM.Enc(u, pk)
4. 计算扰动结果Cy = Perm(Cx ◦ Cu, δ)
5. 构造验证参数vp = ⟨u, δ⟩
6. 证明者解密Cy得到y = Perm(x⊕u, δ)

验证阶段

1. 验证者随机选取m ∈R {0,1}^k，生成cw = ECₙ,ₜ(m)
2. 生成z = Perm(x′⊕u, δ) ⊕ cw
3. 证明者还原cw' = y ⊕ z，解码m' = DCₙ,ₜ(cw′)
4. 验证者比较m′ == m，返回验证结果

5. 安全性与正确性分析

5.1 正确性

Dis(cw, cw′) = Dis(Perm(x,δ), Perm(x′,δ)) = Dis(x, x′)

• 成功解码m ⇒ 修改位数≤t
• 允许验证者准确检查修改程度

5.2 安全性

Fuzzy-binding保障

1. 扰动信息保密：u和δ不泄露给证明者
2. GM加密的语义安全性保障
3. 攻击者无法构造合法的y'和cw′
4. ECC仅在错误数≤t时成功

Full-hiding保障

1. 原始x被GM加密，语义安全
2. 验证过程不泄露x明文或差异位置
3. 验证者仅知改动是否超过t位

6. UtiliClear设计细节

6.1 指纹生成与验证

1. 接收者发送随机ζ、ID及签名sign_{ID‖ζ}给DO
2. DO验证签名后生成指纹f = H₂(ID‖ζ)
   • H₂: {0,1}* → {0,1}^l_f
3. 签名保证：
   • 指纹绑定唯一接收者
   • 防止DO预先嵌入无效指纹

6.2 分组处理机制

为解决大规模数据库处理问题：

1. 将每列属性拆分为若干等大小组
2. 每组分别处理：
   • 重要位：Pedersen承诺
   • 不重要位：FPV协议验证(≤t位)

6.3 验证流程

接收者验证数据库合法性：

1. 重要位：PC.Open检查与承诺一致性
2. 不重要位：FPV.Verify检查每组修改位数≤t

7. 理论分析

1. 指纹鲁棒性：通过伪随机嵌入和统计提取保证
2. 数据实用性：允许在限定范围内修改不重要位
3. 隐私保护：FPV协议确保不泄露具体修改位置
4. 安全性：结合GM加密、Pedersen承诺和数字签名

8. 效率评估

UtiliClear作为首个支持修改范围验证的指纹方案：

1. 计算效率：
   • 与分组数量ng和每组大小相关
   • 每个非重要位组需执行FPV.Verify
   • 每个重要位组需执行PC.Open
2. 通信开销：
   • 预处理阶段需交换锁定参数
   • 指纹生成需交换签名信息

9. 方案贡献

1. FPV协议：模糊扰动验证协议，支持修改数量验证而不泄露位置
2. UtiliClear指纹方案：
   • 接收方可指定并验证最大修改位数
   • 在保障指纹鲁棒性的同时维护数据可用性
   • 通过分组处理支持大规模数据库