基于属性的可搜索加密方案

基于属性的可搜索加密方案李双）徐茂智）（北京工商大学理学院 北京 ）（北京大学数学科学学院 北京）摘 要年 ，等人利用匿名的基于身份的加密方案构造了一个公钥可搜索 加密方案 （），解 决了特定环境下对加密数据进行检索的这一困难问题 已有的可搜索加密方案 ，通 信模式往往是一对一的 ，关 键词密文也只能被特定的单个用户查询或解密 ，这样的通讯模 式在实际的系统中有很多局限性 作者首次给出了基于属性的 可搜索方案（）的定义和构造算法 此 方案与 的不同之处在于基于 属性的可搜索方案是适应群组 的公钥加密搜索方案 ，扩大了信息的共享性 ，节省了第三方信息存储的空间 作 者同时对此方案进行了一致性分析 和安全性证明关键词 可搜索加密 ；基于属性的加密 ；双 线性 问 题 ；安 全性证明 ；信 息安全 ；网 络安全中图法分类号号 ） ）（， ）（ ， ） ， （ ）， ， ； （） ， ， ；查询到所需 要 的 信 息，搜 索 工 具 变 得 异 常 重 要，如、百度已成 为我们日常学习 、生 活 的 工 具如 何使得搜索安全是一个重要的问题 ，于 是一些关于 加密数据的 搜 索 技 术 应 运 而 生 年， 等引言在网络迅猛发展、信息爆炸的今天，为了能快速收稿日期 ：；最终修改稿收到日期 ：本 课题得到国家自 然科 学基金 （，）、北京市属高等学校人才 强教计划 （，）、北 京市自然 科 学 基 金 （）、北京市哲学社会科学规划项目 （）资 助 李 双 ，女 ， 年 生 ，博 士 ，副 教授 ，主要研究方向为信息安全 、密 码算法 ：徐 茂智 ，男 ， 年生 ，博 士 ，教 授 ，主 要研 究 领域为信息安全 、密 码工程计算机学报年人利用匿名的基于身份的加密方案构造了一 个公钥可搜索 加 密 方 案 （），该 方 案 是 针 对 在 加 密 的邮件系统中邮件网关搜索带特定关键词邮件的应 用场景而提出的独 立于文献 中 的工作， 等人基于文献提 出了一个针对加密的审计日志 进行检索的公钥加密方案 等人提 出了两 个支持逻 辑 “与 ”的 检 索 功 能 的 可 搜 索 公 钥 加 密 方 案年，等人对公 钥可搜索加密方案 的一致性进行了重新定义 ，将其划分为计算的 、统计 的和完美的 三 个 类 别随 后，他们给出了将匿名的 基于身份的加密方案转化为具有计算一致性的可搜 索公 钥 加 密 方 案 的 通 用 方 法 ，并 基 于 和 的匿名的基于层级身份的加密方案在标准 模型中提出了一个基于身份的可搜索加密方案的一 般定义，但没有给出具体的算 法 年，等 人 针对云计算环境提出了一个基于通配符的模糊的可 搜索公 钥 加 密 方 案 年， 等 人提 出 了 一 个可以同时对多个关键词进行检索的可搜索公钥加 密方案已有可搜索加密方案大都是针对关键词密文与 查询方之间的关系是一对一的情形 ，在 越来越多的 信息共享的大背景下 ，这些方案显然不适合关键词 可被多方查询的需求 比 如数字电视、视 频点播、个 人微博、个人藏品展示等都可以存储在如 或 这 样的第三方服务器上 ，此 时数据与接收方 是一对多的关系，也就是说数据可 以被多个用户进 行查询，传统的可 搜索加密方案只能解决数据被唯 一对应用户查询访问的问题 此时 当加密方想要将 一个信息和 对 应 的 关 键 词 让 目 标的一群人得以分 享，以现在的系统 只能针对每一个人的私钥进行加 密，将不同的机密 结果在公共信道传送至对应的人 群查询者先是根据关键词查询到一些相关信息 ，然 后再将对应消息解密 在这种情况下用已有的可搜 索加密方案进行查询 ，无论是在效率上还是实际应 用都是难以让人满意的基于属性的加密体制 （）， 年首次被 提出在这种加密 体制中加密者无需知道每个解密 者的具体身份信息，而只需要掌握 解密者一系列描 述的属性，然后在 加密过程中用属性定义访问结构 对消息进行加密，当用户的密钥满 足这个访问结构 时就可以解密该密文因此我们利用基于属性的加密方案可以实现一 对多的通信特性提出基于属性的可搜索加密方案，给出了一般定义、具体算法构造、复杂度分析和安全性分析基于属性 的可搜索加密方案与基于身份的 可搜索加密方案相比 ，解 除了关键词密文只能被唯 一用户正确查询的限制 ，使得关键词密文可以被多 个用户共享检索，节省了网络存储空间，提高了检索 效率，特别适合网络迅猛发展下的各种应用 基础知识设， 是素数，和 分别是阶为， 的乘法循环群称映射： 为一个双线性对 ，如 果映射满足下述性质：（）双线性（）对于任意， 和， ，都有 （ ，）（，） 对于任意 ，有 （，）（，）（，）对于任意 ， ，* ，有 （，）（，）（，）（）非退化性（）存在，使得（，） 这里代表群的单位（）可计算性（）存在有效的 多 项 式 时间算法对任意的 ，计算（，）的值在群 上，作 为密码学的安全假 设 ，有 以 下 几个密码学困难问题定义计算 问 题 （）：给定三元组（， ，），其 中 ， 且 未 知， 为 循环群的一个生成元，计算 的值定义判定 问题（）：给定四元组 （， ，），其 中 ， 且 未 知，为循环群的一个生成元，判定（）是 否成立定义双线性问 题（）：给定四元组（， ，），其 中， 且未知，计算（，） 定义判 定 双 线 性 问 题（）：给 定 五 元 组 （， ，），其 中 ， 且未知， 为循环群的一个生成元， 判定是否（，） 目前仍未 有 解 决 的 有 效 算 法，所 以 普 遍 认为 是一个困难问题定义 访 问 结 构（）：一 个实体集 ， ，对 于 是 上 期李 双等：基于属性的可搜索加密方案 的一个非空子集，如果当 且 时，则有 ，那 么称集合 是单调的一 个访问 结构 （通 常 是 指 单 调 的 访 问 结 构 ）是 ， ，的一个非空子集合，即 包 含 于 中的 集 合 称 为 授 权 集 合 （），而（）（，）： （，）密钥生成中心 （）根 据 访 问 结 构 和 系 统 主密钥 生成用户的私钥 ，其 中 是由系统主密 钥 和 访 问 结 构 生 成 用 户 私 钥 的 概率多项式算法；（）（，）：（，）发送方 利 用 公 共 参 数 和 属 性 加 密 关 键 词 ，生成可搜索关键词的密文 ，只有 属性满足访 问结构 的 用 户 才 能 对 关 键 词 密 文 进 行 解 密 其 中 是由 系统公共参数 ，关 键 词 和 属 性 生成关键词密文的概率多项式算法；（）（，）： （，） 接收方 利 用 个 人 私 钥 计 算 查 询 关 键 词 ， 的 门 限 值 发 送 给 网 关 服 务 器，其 中不包 含 在中的集合称为非授权集 合 （）定义 表示一棵访问树，树 中每个非叶子节点表示的是一个由子节点和阈值所描述的门限假设 表示节点 的子节点数目， 表示节点 的阈值，则有 当 时，门 限 表 示 “或”门，而当 ，时，它表示“与”门另 外，树 中的叶子节点可以认为是一个属性且阈值 为了简化对访问树的操作 ，定义了一些函数 函数 （）表示 节 点 的 父 节 点如 果 是 叶 子 节点，则（）表 示 与 子 节 点 关 联 起 来 的 属 性 值访问树 对 每 个 节 点 的 子 节 点 进 行 编 号 ，即 子 节点的编号是从到 ，而 函数（）返 回节 点 的编号满足访问树：令表示 的根节点，而 表示是 访问树 中以 为根的子树，因 此 也可以表示为 （）表示属性 集合 满足访问树 我 们 可以通过以下方式递归去计算 （）的值如果 是 一个非叶子节点，则计算 所有子节点 的 （）， 当且仅当有至少 个子节点返回时， （）返回； 如果 是叶子节点并当且仅 当（），则 （） 返回是 由 用 户 私 钥 和 关 键 词 键词门限 的概率多项式算法；生 成 关（）（， ，）： （， ，）已知公共参数 ，一 个关键词 的 密文（，）和 关 键 词 的 门 限 值 （ ，），如 果 ，输 出，否 则，其中 是 判断密文 是否是门限 对应 关键词 的密文的概率多项式算法为了一致性，我们要求对所有的，所有的属 性 和所 有 关 键 词 ，有 （， （ ，），（，） 这里 的概率函数取遍所有公共参 数 ，主 密 钥 ；取遍所有概率算法和所有随机预言机模型 密钥管理中心由算法 根据 访问结构 为用户生成私钥 ，然后用户由个人私钥 和关键词 作为函数 的 输入生成关键词 的门限 ，并希望 服务器根据门限 可以查找基于属性可搜索加密方案的定义 算法定义首先给出基于属性的可搜索加密方案（ ，记 为 ）的 定 义 是在基于 属 性 的 加 密 方 案 （）的 基 础 上 提 出 来 的，基于属性的可搜索加密方案引入属性的概念 ，从 而使得满足相关属性的用户均可以对加密数据进行 查询，不同于基于身份的可搜索加密 ，每个关键词密 文与唯一查询用户对应到关键词 的密文服务器用给定的门限 作 为算法 的输入来 判断文件是否包含用户 指定的关键词 的密文且服 务器不知道所查询关键 词的明文 ，隐藏了查询信息的敏感性 由于每个用 户的密钥 与 属 性 有 关，所以拥有属性相 同 密 钥的用户可以对相同信息进行查询攻击游戏的 安全目标是在属性 集 合 模 型（）下 达到选 择关键词明文攻击的不可区分性安全 以 下是攻击 者和 挑 战 者 之 间 在 模 型 下 的 攻 击 游戏：（）攻 击 者 初 始 化：攻击者宣 布它想挑战的属 定义 一个基于属 性的 可搜索加密算法 由 个 多 项 式 时 间 随 机 算 法 、组成：（）（）：（，）（）其中 是系统参数是由系统参数 生成 公共参数 和主密钥 的概率多项式算法；计算机学报年性集，并告知挑战者；（）系统初始 化：挑 战者运行系统初始化算法， 并将公共参数发送给攻击者；（）第 阶 段：攻 击者可 以 选定一些访问结构 进行门限查询，其中对于所有 的 要求，攻 击者可以选择关键词 ，询问其门限值 ；（）挑战：攻击者提 交两个关键词 ，然 后 挑战者随机选择其中之一 （，）以属性集进行加密接着再将密文告诉攻击者 ；（）第阶段：此 阶段是重复第一阶段的操作 攻击者 可 以 询 问 更 多 关 键 词 的 门 限，限 制 条 件 是 ，；（）猜测：攻击者输出对 的猜测，如果，攻 击 者 就 获 胜该 攻 击 的 优 势 定义为算法 （）输入 ：，为属性集包含元素个数 输出 ：（，）， ， ， ， ， ， ， ， ， （）（） （ ， ， ， ， ，） （，） （，）算法描述：系 统初 始 化 （），首 先 选 取 两 个 随机数， ，令 ， ， 是随机 选取 的接 着 从 中 随 机 选 取 互 不 相 等 的 元 素 ，要 求 ，对 于 ， 其 中 ，同时定义一个函数 ，如下：定义 对于所有多项式时间的攻击者 ，如果 都 是 可 以 忽 略 不 计 的，那 么， （）（） 在 上 述 安 全 模 型 下 是 安全的（），其中 是 阶多项式 可以看作函数 输出公共 参 数： （， ）和主私钥： （，）算法 （，）输入 ：（，）为 公共参数 ，主 密钥 以及访问树输出 ：用 户密钥 （， ）算法构造在 方 案 中，我 们 的 目 标 是 实 现 查询方 发送一个关键词的门 限 值 ，这 个 门 限 值是利用 个人私钥和关键词 生成的网 络服 务器根据关键词门限值 搜索到所有包含关键词 的且属性满足访问结构的消息 ，服务器对关键词 一无所知，但是服 务器可以为满足属性的多个用户 查询相同关键词的密文 ， （） （）， （）（）（）（）（） ，（） ， （ ， ） （， ）算法描述：密 钥 生 成 （），该 算 法 以 访 问 树 ，公 共参数 和主私钥 作为输入，为 用 户（访问树中的节点 ）输出密 钥持 有这个密钥，用 户可以解密由属性集 加密的消息，只 要满足条件（）该算法执行的过程如下：首先，为 树 中 的 每 个 节 点 选 择 一 个 多 项 式 ，多项式的选择是从根节点 开始，以 自上而下的 方式进行选 择 的对 于 树 中 的 每 一 个 节 点，多 项 式 的阶数 与这个节点的额阀值 存在以下关系： 现 在 从 根 节 点 开 始，对 于 根 节 点 ，算法构造假设 双 线 性 问 题 （）是 难 解的我们的构 造是在 等 人的 基 于 属 性 的 加密 算 法 （）基础上提出来 的 设 双 线 性 对：，其 中 是 阶 为 的 乘 法 循 环 群， 为群的一个生成元是阶为 的乘法循环群，安全 参数 确 定 群 的 大 小同 时定义拉格朗日系数 ， ， 是 由 中 元 素 构 成，（） ，的集 合，每 个 属 性 唯 一 对 应 中 一 个 元 素，：， ，： ，是 两 个 函 数关 键令而 多 项 式在 其 他个 点 的 值 完 全词在一个属性集（由 属 性 集 中 个 元 素（） ， 组成）下进行加密， 由 个多项式时间算法构成：进行随 机 选 取往下的其他节点 ，令 （）（）（），而 其 他 个 点 的 值 随 机 定 义， 期李 双等：基于属性的可搜索加密方案 其中函 数 （）表 示 访 问 树 中 节 点 的 父节点经过上述操作所有多项式全部确定 而 对于每 个叶子节点 ，将秘密 信息， （ ， ）发 送值现 在 有 密 文 ，访 问 树 以 及 属 性 ，如 果（），则进行如下解密操作；否则返回“” 定义一个递归算法 （， ，），它的输入是密文 ，门 限 和树的一个节点，而 输出群 上的一个值或者“”具体操作如下：（）给用 户，其 中 （） ，（）； 令（），如果 是一个叶子节点，则有 ，其中对于每 个节点 对 应 的 都 是从 （ ，）中随机选取的，其中函数 （）表 示叶子节点 的，烄（ ，）（， ，），属 性；最 后 返 回 全 部 用 户 解 密 密 钥（， ）算法 （，）输入 ：（，），分 别为 公 共 参 数 、关 键 词 、和属性集输出 ：关 键词密文 ，（）， （，（）（ ，），（） ）（）算法描述：加 密关键词，假 设要加密关键词 ， 先计算 其 函 数 （）接 着，选 择 一 个 随 机 烅其他烆，其中（），） （ （） ， ）（，）（）（ ，（， （）如果 是非叶子节点，则考虑以下递归的情况算法 （， ，）具 体操作过程如下：对 （， ，）设存在一个随机的 大小为 的节点集合 且集合中的节点都是 的子节点，否则接下来，令）于节点 的所有子节点，令 （ ），（）： 计算： 值 ，计 算（ （），然 后 计 算 关 键 词 ）， （） 密文 ，并用属性集 标记：（，（）（，），（ ） （） （，），（）算法 （ ，） （ ）（） （，） ） ，输入 ：（ ，），分别为节点 私钥 和关键词输出 ：关 键词门限 （）， （）（，） ， （ （ ）， ， ）（，） （）（ ）算法描 述：生 成 门 限，消 息 的 接 收 方 （）由 个人私 钥 和 生 成 关 键 词 的 门 限 值 综上所述，现 在 已 经 得 出 了 函 数的完整定义，解密算法只需调用该函数在根节点的值所以，当 且仅当密文属性满足访问树，即（） ，；其中 （ ）， ，算法 （ ，）则可计算出：（， ，）（ ，）（， ）再 由 （）（， ），所 以 判断 算 法 根 据 （， ，）是 否 等 于（ ，）的值来给出判断值 计算一致性输入 ：（ ，），分别为关键词门限 、关 键 词 密 文 以及节点 输出 ：判 断值，对于节点 ，当（） ，根据前面分析有 （， ，）（， ，）（ ，） （）算法描述：判断，该算法以关键词的门限 、关 键词密文 和树的一个节点 作为输入，输 出判断（）（，）（）（，）又由关键词门限 和可计算（ ，）（），）（），）所以当 （ ，） 说明关键词门限 计算机学报年 与密文对应同一 个关键 词，且用户的属性满 足（） 复杂度分析基本操作记为： 表示双线性对， 表示椭圆曲 线群中的纯量乘法 ， 代表指数运算， 表示 函数假定关于访问树的运算预处理完成 ，我们用下 面的运算量 统 计 表 给 出 具 体 运 算 量 （设； 属性集 中的元素个数为，所 有比特长度以 中 一点 的 二进制表示的比 特长 为 一 个 单 位 ）其 中 表 示 加 密计 算 关 键 词 密 文 的 算 法； 表示解密验证 关键词门限值的算法； 表 示计算关键词门限值的算法； 表示 公共参数 （公 钥 ）比 特位数； 表示消 息关 键 词的比特位数；表示 密文的比特位数； 表示 关 键 词 门 限 的 比 特 位 数 表 示 算 法； 表 示 操 作； 基 于 属 性 的 加 密 方 案； 是基于 属 性 的 加 密 方 案 ； 是 可搜索加密方案表 运 算量统计表模型下 的 安 全 性，仍 然 采 用 规 约 化 的思想，最终规约为求解 问题定理 如 果 双 线 性 （）问题在群 上 是 难 解 的，则 在 基 于 属性的 攻击下是安全的证明 过程类似文献 假设存在一个多项 式时间算法 在 模 型 下 以 优 势 攻以 的优击 ，我们 构建一个算法 势可以 解 ，以 优 势 可 以 求 解 问题设 ，算法 是已知， ， ， ，目标是输出（，）真正的 挑战者随机 选 取 ，输 出 ，当 时，（，），当 时，随 机 选 取 算法 模拟挑战者和攻击者 之间的交互过程如下：初始化：算法 调 用 ，攻 击 者 选 择 属 性 集，包含 中 个元素的集合算法 设置公共参数 ，随机选取 次多项式（），计 算 ， 次多项 式 （）满 足：（） ，并 且 （） ，因为 （ ）和 是两个 次 多项式，所以它们至多有 个点相同，否则它们就是同一个多项式接下 来 算 法 设 （）（），其 中 ， ，因 为 （）是 次多项式，是 随机独立 （） （）选取的，我们有（）阶段攻击 者 询问一些属性集 不满足的访问结构假设 请求访问结构满足（） 的密 钥为了生成密钥， 必须要为访问树中每个非叶子 任意 任意 节点确定一个 次多项式 （ ）（ ， ）是一个确定访问树中节 点 的 多 项 式 （属 性 不 满 足 以 为 根 节 点 访 问 树，即 （）的 过 程，以 访 问 树 （ 为 根 节 点），属性集 和 作为 输入，其 中 首 先定义根节点 的 次多项式 ，满足 （） 因为 （）， 有少于 个子节点满足属性 ，设 是 的满足属性的子节点数对 于每个满足目前我们还没有看到关于基于属性的可搜索加密方 案，所 以 就 将 与 和 第 一 个 可搜索加密方案进 行比较，我 们看出 只是在计算关键词密文 步骤比 计算 量有所增加，其余步骤 计算量基本一致； 与 的计算量基本相当，说 明在增加少量计算 量的 情 况 下 实 现 了 对 加 密 关 键 词的多方可搜索 功能属性 的 的 子 节 点 ，随 机 选 取 ，令 （） ，然后随机选取 剩余的 个点，至此 完 全 确 定如此递归 的定义访问树中 不满足属性 的点注 意 当 已 知 （）时 （） 可由插值法得到，并且有 （） （）安全性分析下面 我 们 来 分 析 在 基 于 属 性 的 期李 双等：基于属性的可搜索加密方案 算法 调用（，）来定义树中每个节点 的多项式 ，满足（）对于访问树 的每个叶子节点，如果 满足属性集合，则 完全知算法可以攻击 ，所 占优势为，那 么 存在攻击算法可以优势求解 中的问题；在 可解的情况 下，求