第 卷 第 期年 月计 算 机 学 报收 稿 日 期 在 线 发 布 日 期 本课题得到国家自然科学基金项目 河 南省自然科学基金资助项目 河南省高等学校青年骨干教师培养计划项目 河南省教育厅高等学校重点科研 项 目 河南财经政法大学青年拔尖人才资助计划项目资助 张 啸 剑博 士副 教 授中 国 计 算 机 学 会 会 员主 要 研 究方向为差分隐私 数 据 库 付 楠硕 士 研 究 生 主 要 研 究 方 向 为 差 分 隐 私数 据 库孟 小 峰博 士教 授博 士 生 导 师 中国计算机学会 会 士主要研究领域为数据融合与知识融合大数据隐私管理 大 数 据 分 析 等基于本地差分隐私的键值数据精确收集方法张啸剑 付 楠 孟小峰河南财经政法大学计算机与信息工程学院 郑 州中国人民大学信息学院 北 京摘 要 基于本地差分隐私的键 值数据的收集与分析得到了研究者的广泛关注 键与值的值域大小 二 者 之 间 的关联 性报告给收集者的通信方式以及本地扰动机制直接制约着频率与均值估计的精度针 对 现 有 键值 数 据 本 地扰动方法存在的不足 该文提出了一种精确且有效的本地扰动方法该方法结合输入值域与输出值域之间的整体映射关系在较少通信代价与不分割隐私预算的情况下对 键值对进行统一处理 其 主 要 思 想 是 首先对每个用户所拥有的键值对进行统一离散化处理 结 合 每 个 用 户的离 散 化 结 果 利用伯努利采样技术随机地抽样一条键值对进行本地随机扰动 然后将扰动后的键值 对 报 告 给 收集 者收集者利用每个用户的报告值估计每个键的频率以及所对应值的均值 理 论 分 析 了 方 法 产 生 的 方差 与 最 大 偏 差 以 及 与 现 有 键值数据收集方法在真实与合成数据集上进行综合比较实 验 结 果 表 明 方 法均优于同类方法关 键 词 键值 数 据隐 私 保 护本 地 差 分 隐 私 频 率 估 计均 值 估 计中 图 法 分 类 号 号引 言大数据技术的迅猛发 展 键值存储已成为关联数据的主要管理范式 该范式通常被应用于数 据 系 统 中 键值数据类型普遍存在于移动设备网购与医疗平台 等 服 务 之 中每个用户所拥有的数据均 是 键值 对 的 一 个 集 合 因 此基于此类数据的收集与分析能够有效改善应用平台的服务质量 以及向用户提供较为全面的个性化体验然而当数据收集者不可信时 键值对中所包含的个人敏感信息有可能被泄露表 为某不可信购物网站收集用户的购买与评分记 录 通过该表中键的频率以及某键所对应值的均值 分 析 可以学习出用户的购物行为模式与 偏 好例 如商 品 的 频 率 为 所 对 应值的均值为 不可信收集者分析出 的 频 率 之后即可对表 中的用户进行统计攻击因 此在 此情景下用户通常无法掌控自己的隐私数据本地差分隐私 保 护 技 术 的 出 现 有 效 地 解 决 了 此 类 矛盾该技术允许每个用户采用随机应答机制或者拉普拉斯机制对自己所拥有的键值数据进行本地扰动再把扰动之后的结果报告给收集者 进而可以有效防止不可信收集者泄露自己的隐私表 键值 数 据 样 例用 户 商 品 与 评 分目前基于本地差分隐私的键值 数 据 收 集 与 分析研究 工 作 相 应 较 少文 献 结 合 与方 法 提 出 了与方法然而这两种方法却由于频繁分割隐私代价致使最终的频率与均值估计精度较低 文 献 结 合 方 法 的不足基于框 架提出了方 法然 而 该 方 法 却 忽 视 了 键值 整 个 值域的影响特别是键的值域比较大时 该方法最终的频率与均值的估计精度较低 结 合 文 献 可 知收集 与 分 析 键 值数据过程中存在的挑战包括计 算 机 学 报 年用户在设 计 本 地 扰 动 方 法 时如 何 维 持 键 与 值之间的关联性如果键与值经过扰动之后失去关联性则收集者估计出的键频率和该键所对应值的均值的精度会很 低 收集者如何以较小的噪音误差与通信代价收集所有用 户 的 键值 数 据如 果 用 户把扰动之后 的 键值根据整个值域的大小报告给收集者则收集者与用户之间的通信代价以及噪音误差会很高总而言之目前还没有一个行之有效且满足本地差分 隐 私 的 键 值收集与分析方法能够克服上述方法存在的问题 为此本文基于本地差分隐私技术提出了 一 种 键 值数据收集方法能够兼顾上述的问题需求本文主要贡献如下为了解决 挑 战 本 文 提 出 了 方法不同于 文 献 对 键 与 值 分 开 处 理 方法对键值对 进 行 统 一 本 地 扰 动进 而 维 持 了 键 值之间的关联性为了 有 效 解 决 挑 战 方 法 均 首先采用离散化操作对每个键所对应的值进行处理结合离散化结果 随机采样 一 个 键值对进行本地扰动然后将扰动结果报告给收集者理 论 分 析 了 方 法 满 足 本 地 差 分隐私以及频率与均值估计的误差边界通过合成数据与真实 数 据 实 验 分 析 方法具有较好的可用性相关工作当前本地差分隐私主要关注频率 直方图均值 频繁 项 集 估 计 以 及 图 发 布 等 方 面 的研究谷歌 浏 览 器 所 嵌 入 的 方 法结合 提出的 方 法 实 现 了 用 户 浏 览数据的本地保 护 然 而基 本 的 方 法 容 易 受到值域大小的影 响 大的值域会对该方法造成大的估计误差 与 通 信 代 价 改 进 的 方 法 利 用技术缩减值域大小来提高 估 计 精 度同时 方法利用哈希与矩阵投影技术将通信代价减 少 到 级 别此 外 方 法 与方法 分别利用一元编码与本地哈希技术来提高估计精度并且估计误差脱离了值域大小的影响不同于上述的频率估计 方 法 方 法 结 合方法 与离散化操作实现 了 区 间 上 的 均 值估计然而由于 方法输出结果是固定的两个离散 值进而使最终的估计结果偏离了 区间针对 方 法 的 不 足 方 法 能 够 将区间中的某个真实值扰动到一个受约束的联系区间 并在该连续区间中计算出该扰动值的左右边界尽管目前有多种频率与均值估计方法而涉及键值数据收集与分析的工作却很少 文 献结 合 与 提出了 与 方法来收集键值数据然而这两 种 方 法 却 由 于 频 繁 分割隐私代价导致较高的估计误差文献 同样结合方法提出 了 方 法然 而 该 方 法 由 于 继承了 方法的不足无法应对稀疏的键值 数 据因此针对上述方法的不足本文提出了一种基于离散化与随机 采 样 技 术 的 键值 收 集 方 法 该方法不但对键值数据进行整 体 考 虑 还 具 有 较 高 的频率与均值估计精度基础知识与问题描述本地差分隐私不 同 于 中 心 化 差 分 隐 私 技 术本地差分隐私技术通常要求用户在本地保护自己的数据 把 扰 动 之后的数据报告给不可信的收集者从而实现隐私不被泄露本地差分隐私的形式化定义如下所示定义 本地差分隐私 给 定 一 个 随 机 算 法及其定 义 域 和 值 域 若 算 法在任意两条不同元组 与 上 得到相同输出结果 的概率满足下列不等式则 满足 本地差分隐私其中 为 隐 私 预 算 该 值 的 大 小 直 接 决 定 着 隐 私 保护程度随机应答 机 制 是实现本地差分隐私的常用技术该机制的思想是用户在响应敏感的布尔问题时以概率 真 实 应 答 以 给 出 相 反 的 应 答为了使随机应答机制满足 本 地 差 分 隐 私 通 常 设置 或者其它值收集者获 得 所 有 应 答后即可对真实应答进行分析估计类似于中心化差分隐私本地差分隐私同样满足序列组合特性性 质 序列组合性质 给定数据集 和个随机算法 且 满 足本地差分隐私则在 上的序列 组 合 满 足 本 地 差分隐私且问题描述给定 个用户 每 个 用 户 拥期 张 啸 剑 等 基于本地差分隐私的键 值数据精确收集方法有不 同 的 键 值 对 为 键 的 值 域为键所对应值的值域为 用 户 的 键值 对 集 合其 中表示 的长度收集者收集所有用户的键值 数 据之后通常做两种基本的统计分析 即键所对应的频率以及对应值所对 应 的 均 值 具 体 计 算 如 式 与式 所示其中 表 示 集 合 中 拥 有 键 为的用户个数例如表 中拥 有 键 为 商 品 的 用 户 个数为 则其中 表示键为 所有对应值的和例如表中键为 商品所对应值的和为 则采用均方误差与 相对误差 度量 与 的估计精度本文要解决的问题是在设计满足本地差分隐私的频率与均值 估 计 方 法 同 时尽可能获得误差较小的估计结果键值数据收集方法方法类似于文献 结 合 键 的 值 域 值 域 大 小 为与每个用 户 所 拥 有 的 键 值 对 集 合 首 先 对中所有 对 进 行 编 码 操 作 生 成 一 个 长 度 为的新型向量其他根据式 可 知集 合 中 的 元 素 分 别 由与 组成其中 例如假设 键 的 值域经由式 编 码 后一种最直接的方法是分别采用现有满足本地差分隐私的频 率 与 均 值 估 计 方 法 对 中 的 元 素 进 行频率与均值估计 然而这种最直接的方法通常会打破 与 之间的关联性尽管 与方法的可用性优 于 最 直 接 方 法然而这两种由于分割隐私代价导致 最 终 的 可 用 性 较 低结 合 集 合 与方 法 可 知 扰 动 方 法 的 输 入 值 域 变 成 了而 扰 动 之 后 的 输 出值域为 基 于 此 分 析 本 文提出 了 一 种 频 率 与 其 所 对 应 值 的 均 值 估 计 方 法该方法在不分割隐私代价的情况下对键值对进行统一地扰动 该方法细节如算法 所示算法 算法输 入所 有 用 户 的 键 值 对 集 合 隐私 预 算 扰 动 概 率 与 键 的 值 域 为 以 及的 大 小输 出频 率 向 量 均 值 向 量算法是基于本 地 差 分 隐 私 整 体 考 虑 用户键值对的频率与均值估计问题 首 先 每 个 用 户 利用 方 法 本 地 扰动自己的键值对并报告给收集者步骤 步骤收集者聚集所有用户的报告值后计算并修正每个键所对 应 的 频 率 以 及 值 所 对 应 的 均 值 步 骤步骤 根据算法的第 行 可 知每个用户在不分割隐私预算 的 情 况 下 调 用 算 法 本 地 统 一 扰动自己的键值对由 于 每 个 用 户 利 用 算 法 仅扰动一组 键值 对 后 再 报 告 给 收 集 者 进 而 使 得 收集者与用户之间的通信代价为 接 下 来 阐 述算法的实现其具体实现细节如算法 所示计 算 机 学 报 年算法 算法输 入用 户 的 键值 集 合 隐 私 预 算输 出扰 动 之 后 的 值结合 算法每个用户首先利用式 对自己的键值对 进 行 编 码 转 换 步 骤 进 而 获 得为了减少收集者与用户之间的通信代价以及噪音误差在 中均匀随机地抽取一个键值 对 进行本地扰动步骤 步 骤 无 论 是还是 最终结果均以不同的概率扰动成以及 步骤 与步骤要实现 算法中的步 骤 与 步 骤 需 要 计算出概率 根 据 算 法 的 描 述 可 知 输 入 值的值域为 输 出 值 域为 与 因此可以把输入值域分成两种情况当输 入 值 为 与 时为 使与 三 种 输 出 结 果 满 足 本 地 差 分 隐私则下列三种不等式需成立输出值为 时则式 成立输出值为 时则式 成立输出值为 时则式 成立当输 入 值 为 与 时其 中 与互为近邻为使 与 三 种 输 出结果满足 本地 差 分 隐 私 同 样 下 列 三 种 不 等 式 需同时成立输出值为 时则式 成立输出值为 时则式 成立输出值为 时则式 成立从式 至式 可知以上六种不等式应同时满足根据本地差分 隐 私 定 义 可 知若 要 使 式 与式 同时成立则需要 式 中 的 式 中 的进而可得式通过观察式 与式 可知若要使这两种等式同 时 成 立 与 只 需 要 考 虑 取 极 值 情 况 即 可当 时式 取 得最大值则 由 式 可 知 当时式 取 得 最 大值则由式 可知 因 此结 合 上述两种 情 况 可 知 式 与 式 可以同时归结为根据式 和 式 以 及 可以计算出概 率 以 及获得 之后 算法以不同的概率将 扰动成 以及方法的隐私性与可用性分析本 小节主要从 本地差分隐私阐述 方法的隐私性以及从估计无偏性与方差阐述其可用性 方 法 中 只 有 算 法 花 销 因 此只要 算法满足 本地差分隐私则根据性质 可知 方法同样满足 本地差分隐私定理 算法满足 本地差分隐私证明 设 与 表 示 两 个 不 同 的输入 键值 对 表 示 与 经 过算 法 扰 动 之 后 的 结 果则已知可 分 三 种 情 况 证 明 算 法 满 足本地差分隐私期 张 啸 剑 等 基于本地差分隐私的键 值数据精确收集方法由定 义 以 及 式 至 式 分 析 可 知 当时概 率达到最大当 或 者时概 率 达到最小则或者由定 义 以 及 式 至 式 分 析 可 知 当时概率达到最大当 或者时概 率 达到最小则或者根据上述三种情况分析可知 算法满足 本地差分隐私尽管通过 算法可以估算出每个键的频率 以及所对应值的均值 但 是 由 于 算 法的本地扰动 与 会偏 离 于 原 始 值 而 我 们 期 望与 均 要 满 足 无 偏 性 因 此需 要 计 算 出 与的修正因子即算法 的步骤 与步骤定理 假设 与 分别为键 的估计频率与真实频率 与 分别为键 所对 应 值 的 估 计 均值与真实均值当 时无偏估计 成立证明 首先证明 设 与分别表示键 的估计计数以及真实计数根据式 可知 因此只要成立则 成 立设 表 示 收 集 者收 集到的键 为 的个数设 为键的值域大小 由于每个用户采用伯努利抽样随机抽取一个键 值 对进行 扰 动则 每 个 键值对被抽取的概率为 根据文献 可知给定 个用户响应键 为 的概率与响应 为的 概 率 分 别 为由 于无法获知真实的 需要求得对应的估计量根据两种响应概率可知 个用户的响应结果构成了符合二项分布的 个 序列结合该二项分布 构造相应的似然函数为则对 两侧取对数再对 求导即可 获 得的估计量为了证明 下列过程成立即可计 算 机 学 报 年则接下来证明 成立设 与 分 别 表示键 所对应某个值的真实值与扰动值根据式可知只要 成立则 成立根据算法 可知 的 输 出 结 果 的 值 域 为如果知道这三种值的输出概率 即可计算出 输 出的期望设 与 分别表示 的输出概率结合则下列等式成立则 可表示成如下公式若要使得等式 成 立则 应 当乘以 即其中 为修正 因 子根 据 可 推理出 成立根据定理 可 知修 正 因 子 可 以 使与 达到无偏然而由于利用 方 法 对用户的键值对进行本地扰动 在估计 与 时会产生相应的 误 差而 这 两 种 误 差 的 大 小 是 衡 量方法可用性的主要标准之一本文采用方差与 度量 方法产生的误差定理 假设 与 分别为键 的估计频率与真实频率当 时的方差为 当时 的最坏方差为证明 由定理 可知则当 时定理 假 设 与 分别为键 所对应值的估计均值与真实均值当时则其中 与 表示 和的真实计数证明 为了证明方便设置根 据 算 法 的 第 行 可 知 可 表 示 为则 的方差可表示为设则的期望为期 张 啸 剑 等 基于本地差分隐私的键 值数据精确收集方法同理可知 的期望为的方差为同理可知 的方差为此外将代入式 可知其中尽管通过定理 与定理 可 以 计 算 出 某 个 键的频率及其对应均值的方差而 如 何 度 量 与以及 与 之间的最大偏差是具有挑战性的问题接下来由定理 与定理 给出详细说明定理 假设 与 分别为键 的估计频率与真实频率当 时则至少以概率成立其中 为用户个数 为键 的值域大小证明 根据定理 可知下列等式成立其中 与 表 示 键 的估计计数和真实计数 与 表示第 个用 户 拥 有 键 的 真 实 值 与 估计值因此可知 为一个随机变量 根据定理可知其均值为 随机变量 的方差可以表示为由于 则进而可知根据 不等式可知结合上述不等式可知则可知 至少以概率 成立定理 设 与 分 别 为 键 所 对 应 值 的 估计均值与真实均值下列等式至少以概率 成立其 中 为 用 户 个 数为键 的频率证明 由算法 的第 行可知 对应值的估计均值 为 设根据式 可 知 以 及则成立根 据 定 理 可 知成立则 成立进而使 得下列不等式成立计 算 机 学 报 年则定理 成立定理 至 定 理 从 频 率 与 均 值 的 无 偏 性 方 差以及最大偏差的角度分析了 的可用性接下来结合当前基于整个值域的频率估计方法与 以及针 对 键值 数 据 的 均 值 与 频 率 估 计方 法 与 阐 述方法的可用性根据 方法的描述可知 该方法利用伯努利抽样技术随机抽取某一键值 对 进行本地扰动该操 作 减 少 了 方法的渐进误差给定键的值域大 小 以 及 用 户 转 化 后 的 键值 对集合 如果 方 法 对 中 的 每 个 键值 对 均 本地扰动则 分 别 利 用 此时的 与 代入定理 可知估计键 频率所产生的渐进 误 差 为 本 文 方 法利用伯努利抽样技 术 则 估 计 键 频率所产生的渐进误差为同理利 用 方 法 对 中 的 每 个 键 值对扰动则 估 计 键 频率所产生 的 渐 进 误 差 为 此 时方法产生的渐进误差大于本文的基于抽样技术的方法即此外利用 方法扰动 中所有键值对后估计键 频 率 所 产 生 的 渐 进 误 差 为 此时 方法 产 生 的 渐 进 误 差 大 于 方 法即根据上述分 析 可 知 如 果 方 法 与方法分别作用于 中的每个键值对则 产 生 的 频 率估计误差均高于 方法接下来利用定理 阐述附带 方法的 优于 现 有 键值 对 频 率 与均值估计方法 与定理 结合现有的键值对收集方法与 产 生 的 方 差 以 及 当 前 可 知优于这四种方法证 明 类 似 于 定 理 与 定 理 给 定 键以 及 方 法 估 计 键 频 率产生的误差为 方法估计键频率产 生 的 误 差 为 给 定 隐 私 预 算可知 则 在 基 于 键频率产生误差的情况下 方法优于以及 方法根据定理 可知 以及方法的均值方差为根 据 式 与 式 可 知 的 均 值 方差大 于 的 均 值 方 差 则 方 法 优 于与 方法同理基 于 定 理 可 知方法优于实验结果与分析实验平 台 是 核内存 系 统所有算法均采用 实现实验采用五个数据集和 其中 是从 与 移 动 应 用的 中收集而得该数据集包含 个设备和类应用程序 数 据 集 来 自 于 其 中包含 年 的 万 条 销 售 记 录 该 数 据 集 记 录了 年间 个用户对 个品牌的 万条 购 买 记 录 和 三 个 数 据 集期 张 啸 剑 等 基于本地差分隐私的键 值数据精确收集方法为合成数据集键和值分别遵循高斯 幂律和线性分布五种数据集具体细节如表 所示表 五种数据集信息描述数 据 集 分 布 用 户 数 数 量结合上述五种数 据 集 采 用 均 方 误 差 和 相对误差 度量以 及方 法 的 频 率 和 均 值 计 算 精 度其 中 是 单 值频 率 估 计 方 法 的 典 型 代 表 是 高 维 分 类数 据 与 数 值 型 数 据 下 估 计 频 率 与 均 值 的 典 型 代表键 与 值 所 对 应 的 均 方 误 差 可 以 表 示 为与 相 对 误 差可 表 示 为 其 中 表 示 的 真实 频 率 表 示 的 估 计 频 率 表 示 所 对 应 值的 真 实 均 值 表 示 所 对 应 值 的 估 计 均 值实 验 结 果 比 较隐 私 参 数 的 取 值 为实验中分别对五种数据集中的频率最高的的 键值 进 行 的 统计在每种情况下进行 次试验并求取平均值作为最终的计算结果基于 数据集的七种算法的和 值比较图 描 述 了以 及 算 法 值 和值的比较结果由图 的 验 结 果 可 以 发 现 当从 变 化 到 时六 种 方 法 的 值 均 减少而 方法的精度优于其它五种方法 当时 方 法 的 精 度 是 算法的近 倍是 和 算 法的将近 倍同时从 图 中 发 现当 固 定时键的数目从 增加到 六种方法的值 均 增 大 且 算 法 的 精 度 同 样 优 于 其 它四种方法其 原 因 在 于 随 着 键 值 个 数 增 加 累 计 的误差 也 就 越 多 导 致 精 度 越 差 图 是以 及方法关于均 值 的 值 比 较 结 果 从 实 验 结 果 可以发现 从 变 化 到 时六 种 方 法 关 于 均 值的 值 均 呈 现 下 降 趋 势 然 而 方 法 的均值精度明显优于其它五种方法并且其下降趋势明显大于其它 五 种 方 法 其 原 因 在 于 方 法将键值对看成一个整体进行编码扰动 避 免 了 隐 私预算的分割图 数据集频率和均值计算结果计 算 机 学 报 年基 于 数据集的七种算法的 和值比较图 描 述 了以 及 方 法 值 和值的比较结果由图 的实验结果可以发现当 从 变化到 时六种方法的 值均减少当 时 方 法 的 精 度 是算法的 近 倍是 和方法的将近 倍图 描 述 了以 及 方 法 有 关均值的 值 比 较从 实 验 结 果 发 现 当 从变化 到 时 方 法 的 均 值 精 度 优 于 其 它五种 方 法 当 时 方 法 的 精 度 是方法 的 近 倍是 算 法 的 近 倍其原 因 为 算法不仅避免了隐私预算的分割同时避免了 和 方法中对键所对应值的多次扰动基 于 数 据 集 的 七 种算法的 和 值比较图 图 分别描述了图 数据集频率和均值计算结果图 数据集频率和均值计算结果期 张 啸 剑 等 基于本地差分隐私的键 值数据精确收集方法图 数据集频率和均值计算结果图 数据集频率和均值计算结果以及 方法在数据集 上 的 值 和 值 的 比 较 结 果由实验 结 果 可 以 发 现当 从 变 化 到 时方 法 的 精 度 优 于 其 它 六 种 方 法 当 固 定键值的个数时从图 图 图 的 实 验 结果可以看出当 从 变化到 时六 种 算 法 在三种数据集上 的 值 均 下 降 当 时键值等于 时 方法的精度相对于方 法 较 数据集上达到了近 倍较数据集上达 到 了 近 倍在 数 据 集上达 到 了 近 倍其 主 要 原 因 为 方 法 将键值对看成一个整体进行编码扰动 减 少 了 隐 私 预算分割和扰动次数计 算 机 学 报 年总 结本文针 对 键值数据的收集与分析问题 提 出了一种 基 于 本 地 差 分 隐 私 的 键值 数 据 收 集 方 法该 方 法 在 不 分 割 隐 私 代 价 的 情 况 下 每 个用 户 利 用 离 散 化 本地扰动以及伯努利抽样技术统 一 保 护 了 自 己 的 键值 数 据 这几种操作既维护了 键 与 值 之 间 的 关 联 性 还 保 持 了 用 户 与 收 集 者之 间 较 小 的 通 信 代 价收 集 者 结 合 整 体 扰 动 的 结果对每个键的频率以及键所对应值的均值进行估 计从 理 论 角 度 分 析 了 方 法 估 计 频 率 与均值产生的误差 以 及 最 大 偏 差从实验角度分析了与同类 方 法 相 比 具 有 较 好 的 估 计 精 度 今后的研究考虑 如 下 两 个 方 面 如 何 利 用 直 方 图技术估计键的频 率 与 均 值 由 于 键值 的 值 域 通常比较稀疏如何设计高精度的本地扰动方法来克服此类问题参 考 文 献期 张 啸 剑 等 基于本地差分隐私的键 值数据精确收集方法计 算 机 学 报 年