我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 知识复杂性 >

第二章预备知识粗略地说多项式算法被认为是有效的算法 而非多项

归档日期:07-20       文本归类:知识复杂性      文章编辑:爱尚语录

  第二章预备知识粗略地说多项式算法被认为是有效的算法 而非多项式算法被认为是无效的或者在现实不可行的 如果一个问题是非多项式时间内可解的 那么我们通常假设该问题是困难的。定义 指数时间算法 一个指数时间算法是指时间复杂性为 指输入规模的多项式函数 七为大于 的常数。在本论文中还会用到的其他复杂性理论方

  第二章预备知识粗略地说多项式算法被认为是有效的算法 而非多项式算法被认为是无效的或者在现实不可行的 如果一个问题是非多项式时间内可解的 那么我们通常假设该问题是困难的。定义 指数时间算法 一个指数时间算法是指时间复杂性为 指输入规模的多项式函数 七为大于 的常数。在本论文中还会用到的其他复杂性理论方面的相关概念还有 定义 可忽略量 如果对于一个正多项式 存在 丽则称函数是可忽略的。计算不可区分的概念最初由 】等人提出。在密码学中对于各类密码学体制多项式时间不可区分是一条重要的安全准则。定义 多项式时间不可区分 两个概率总体 是多项式时间不可区分的如果对于每个以 为输入的概率时间算法其中 输出属于的一比特信息。当 输出那么对于任一正多项 存在 双线性配对及相关复杂性假设目前主要的身份基加密方案】和属性基加密方案 均用到了双线性配对这个代数结构。它的主要定义和性质如卜 为两个阶为素数的群。定义一个可有效计算的双线性映射芭 。这个映射必须要满足下面条件 双线性 若对于所有的 和所有的 满足乏 具有双线性。非退化性 存在 。如果在中的群运算与双线性映射芭 均为可有效计算的 我们称 为双线性群。注意 是对称的因此如下等式芭 成立。奉论文中所构造的方案均基于双线性配对上的某些难题 这里介绍一下基 双线性配对的常见问题和假设。一一上海交通大学博士学位论文定义 双线性 参数生成器 同文献 】中一样若一个以安全参数 的多项式时间内运行输出关于两个群 的描述、它们共同的素数阶以及一个双线性配对芭 的描述 则我们称这个算法为一个 参数生成器。定义 计算性双线性 计算性问题 假设群 中的生成元及仑的为上面所定义的参数。 问题定义如下给定 其中随机元素 。定义判定性双线性 问题或判定’ 以及乏为如上所述参数生成器的输出 问题为随机选取三个整数 以及随机元素 给定 是否成立。注若此等式成立 则元组 元组。定义判定性双线性 假设判定性双线性 问题是困难的。定义 判定性双线性 问题或判定性 问题 问题为随机选取三个整数 以及随机元素 给定 判断等式一十 是否成立。注 若此等式成立 则元组 被称为一个一元组。定义 判定性双线性 假设判定性双线性 问题是困难的。常见的安全模型 哈希函数 在现代密码学中 哈希函数 有着非常重要的角色 它在对消息进行处理时 通常将任意长度的消息压缩成为固定长度的消息摘要 不仅大大提高了密码算法的效率 另一方面也提供了数据的完整性 使体制免受适应性攻击。定义 哈希函数 存密码系统中 哈希函数通常为 个确定的函数 它将任意长度的比特串压缩映射到固定长度的比特串的函数。我们设 ”为一个输出长度为 的哈希函数 它满足以下安全性质 对于任意的输入输出的哈希值 应当和区间 】中均匀分布的二进制串在计算上是不可区分的。 抗强碰撞性 找出两个不同的输入 在计算上是不可行的。抗弱碰撞性 给定一个输入 找出另外一个不同的输入 使得在计算上是不可行的。 单向性 已知一个哈希值 找出一个输入串 使得 在计算上是不可行的。 有效性 给定一个输入串 哈希值日 的计算可以在关于 的长度规模的低阶多项式 理想情况是线性的 时间内完成。 随机预言模型在密码学中 有很多密码体制都要用到哈希函数 比如 或者美国标准 。随着密码学不断发展哈希函数不仅仅被用在提高方案效率上 还逐渐成为安全性证明中的重要角色。哈希函数在安全性讨论中 被假设为一个随机函数。最初 形式化定义了这种思想抽象出了随机预言机模型。随机预言机模型在构造 ‘证安全密码体制时主要思想在于哈希函数首先被考虑为随机函数一随机预言机。在体制开始设计的时候 系统中的各个角色共享随机预言机完成操作。当体制设计完成之后 再用实际的哈希函数将此随机预言机替换掉 】。定义 随机预言机 函数 ”如果满足以下性质均匀性 预言机日的输出在 “上均匀分布 确定性 对于相同的输入 预言机日的输出值必定是相同的 有效性 给定一个输入串 的计算可以在关于 的长度规模的低阶多项式 理想情况是线性的 时问内完成。其称为随机预言机。定义 随机预言机模型 存证明密码体制的安全性时 如果利用随机预言机的上述性质 那么这样的证明模型成为随机预言机模型【 一上海交通大学博士学位论文标准模型最初人们认为在随机预言模型下可证安全的方案自身结构是没有任何缺点和漏洞的 攻击者只有在找出哈希函数的问题情况下才可能找出密码系统的漏洞。然而 在近期指出一些具体的方案在随机预言模型下可证安全但在实际环境中 尽管所基于的假设成立 攻击者无需找出哈希函数的任何漏洞也能成功攻击方案。标准模型 是指不需要用随机预言机假设的安全模型。标准模型中安全的加密方案在上世纪 年代就已经出现 例如关于加密的文章 】。但是 由于不用随机预言机 此类方案的效率不理想且往往扩展性较差。但从安全性角度考虑 标准模型下可证安全的方案确实比随机预言模型下可证安全的方案更为可靠 因此近年来密码学界对标准模型下可证安全的密码学做了大量的研究 并且构造了很多在标准模型下可证安全的密码方案【 】。本论文中所构造的方案均为标准模型下可证安全的。 形式化定义及安全模型这个小节介绍公钥加密方案和身份基加密方案的形式化定义及相关安全模型。属性基加密方案为身份基加密方案的推广 因此很多形式化定义和安全性模型均与身份基加密方案中的形式化定义和安全模型相似。 公钥加密方案传统的公钥加密方案 的定义如下 定义 公钥加密 方案 一个 方案由下面的五个算法组成 系统初始化 它是一个概率算法 以一个安全参数作为输入 输出系统公共参数印。 密钥生成 它是一个概率算法 以系统公共参数印作为输入 用户的公私钥对 。其中础为用户公钥 后为用户私钥 也即解密密钥。 加密 它是一个概率算法 输入为一个消息 、系统公共参数即、某个接收者的公钥础 输出为密文 解密它是一个确定性算法 输入为一个密文 以及用户私钥 输出明文或者“上” 为不合法密文时。在传统的公钥加密方案中 公钥和私钥‘ ‘对应。因此其正确性定义为当私钥 后为础所对应的私钥时 解密算法可以正确的恢复合法密文 中的消息 。我们通过一个挑战者 和攻击者 之间的攻击游戏 来定义一个公钥加密方案的“语义安全性” 也称为选择明文攻击安全 】。因此下面的这个攻击游戏也被称为 游戏 一第二章预备知识建立阶段 挑战者 选取一个安全参数 运行系统初始化算法 和密钥生成算法 然后将生成的系统公共参数即及用户公钥砧全部交给攻击者 并保密用户私钥 挑战攻击者月向挑战者提交两个等长度的消息 尬。挑战者 随机选取一个比特 并将挑战密文设置为 。然后将该密文交给攻击者 输出最后 攻击者 输出一个猜测 攻击者。攻击者在上述针对 方案的 攻击游戏中的优势定义为安全参数 的一个函数 。定义方案的选择明文安全性 若任何 攻击者在上述游戏中的优势都是可忽略的 那么我们称该 方案是 安全的。上述攻击游戏中 攻击者不能进行解密查询 而在现实世界中 攻击者很可能获得来自用户的解密服务。冈此 如果上述 攻击模型中加入解密预言机则该游戏为选择密文攻击游戏 。这种强化模型下的安全性被称为选择密文攻击安全 简称选择密文安全。本文重点关注构造选择明文安全的加密方案。 身份基加密方案身份基加密 这个概念最早 年提出其形式化的定义及安全模型则由 给出。在身份基加密方案中 私钥生成中 为每个用户身份生成相应的私钥。定义方案 一个 方案由下面的四个算法组成 系统初始化 它是一个由私钥生成中心 运行的概率算法 以一个安全参数 作为输入 输出 的主密钥 即一对公 私钥 。其中础是系统公钥 为“主私钥”。 公布系统公钥 保密主私钥。 私钥抽取 它是一个山 运行的密钥生成算法 用来为用户生成 解密 私钥。它的输入为主私钥 和某个刖户的身份标识 输出为该用户的私钥 一上海交通大学博士学位论文加密 它是一个概率算法 输入为一个消息 、某个接收者的身份标识 以及系统公钥础 输出为密文 解密它是一个确定性算法 输入为一个密文 以及用户私钥 输出明文或者一个区分标识符号“上” 为不合法密文时。身份基加密方案的正确性定义为 当且仅当解密者身份 所对应的身份相等时 时解密成功。我们通过一个挑战者和攻击者一 之间的攻击游戏 来定义 方案的安全性。下面的攻击游戏最早由 在文献【】中给出。 建立阶段 挑战者 选取一个安全参数 运行 方案的系统初始化算法 然后将生成的系统公钥础交给攻击者一 并保密 主私钥 查找阶段攻击者 向挑战者 提出如下查询 一对某个身份标识 的私钥抽取查询 挑战者 运行密钥抽取算法后 将生成的用户私钥 交给攻击者。一解密查询 挑战者 首先获得相应用户的私钥 若对应于该身份标识的用户私钥还从未被抽取过 则运行密钥抽取算法 然后利用该私钥解密密文并将所得明文舰交给攻击者 挑战当攻击者 决定结束查找阶段后 它向挑战者提交两个等长度的明文 以及一个身份标识 称为挑战身份 。唯一的限制是 在查找阶段 攻击者 不曾查询过挑战身份 的私钥。挑战者 随机选取一个比特 并将挑战密文设置为 。然后 将该密文交给攻击者 猜测阶段在这一阶段 攻击者 可以提出更多像查找阶段一样的两类查询 不过受到如下限制 不能对挑战身份 进行私钥抽取查询 不能对身份一密文对 进行解密查询。 输出 最后 攻击者 输出一个猜测 我们称它赢得了游戏。上述攻击游戏中的攻击者被称为选择密文攻击者【 】。如果攻击者 被禁止进行解密查询 我们称它为一个选择明文 攻击者。如果攻击者被要求一开始公开挑战身份 且在接下来的查询中加入不能简单解密的限制 我们称它为一个选择身份攻击。很明显 选择身份的攻击要比非选择身份攻击 又称适应性攻击的强度要弱。攻击者在上述针对 方案的攻击游戏中的优势定义为安全参数圪的一个函数 一第二章预备知识定义方案的安全性 若任何 都是可忽略的那么我们称该 方案是 安全的。本章小结本章主要介绍了论文所需要的基础理论和预备知识 主要内容包括计算复杂性理论基础知识、抽象代数基础、双线性配对定义、相关复杂性假设。此外 我们还介绍了可证明安全中的哈希函数定义 随机预言机模型和标准模型 以及公钥加密方案和身份基加密方案的形式化定义及安全模型。一 一第三章无中央机构的多机构属性基加密方案 引言最早的多机构属性基加密 方案 年提出。该方案允许多个独立属性机构监测属性并分发相应的属性密钥。加密者对每个属性机构都选择一个数目和以及其管理的属性集合中的一个属性子集 在其选择的属性集合下对消息进行加密。若解密者对每个机构都拥有对应属性集合 中的至少个属性才能解密成功。 的方案主要采用了两项技术 首先每个用户都有一个全局标识 其次使用了一个完全可信的中央机构。中央机构负责提供一个中央私钥以整合用户从其他属性机构中所获得的属性密钥。但在 的方案中 由于中央机构掌握系统私钥 因此它能解密系统中产生的所有加密密文。换句话说 的方案中中央机构必须被假设是完全可信的。一旦中央机构被攻击者攻击成功 整个系统将毫无安全性可言。并且 系统中出现了这个中央机构意味着额外的计算和通信负担 系统的效率将相应地降低了。本章节中我们将考虑如何从多机构属性基加密方案中去除中央机构。这么做的难点在于如何在去除中央机构的同时防止共谋攻击。 的系统中中央机构负责将从其他属性机构中获得属性密钥整合从而保证最终的解密过程独立于用户所使用的标识。因此如何在不存在中央机构的情况下整合用户的私钥将是我们要克服的另一个凼难。本章的构造将 方案中所使用的伪随机生成函数替换成一个多项式。随后 我们的方案中使用了密钥分发技术和联合零秘密分享技术【 】米构造首个无中央机构的多机构属性基加密方案。在下述方案中 若解密者拥有加密密文所对应的至少 个的属性机构 所管理的属性集合 中的至少七个属性则解密成功 这里几指加密系统所含有的属性机构数 。在本章的方案中 所有这些属性机构只需在初始化阶段和其他属性机构进行通信 而且这些通信过程不涉及任何属性机构的隐私信息 且他们在方案的随后步骤中可以独立地运行。换句话说 这些相对低效的通信过程与系统用户无关 因此也不会给他们带来任何不便。本方案的安全性可以归约到所基于的分布式密钥分发协议 及联合零秘密分享协议 的保密件和标准判定件 假设上 定义见第二章 。本章将首先给出一个无中央机构的多机构模糊身份基加密方案 。此外本章节还将介绍上述方案的扩展 比如如何构造一个前摄 无中央机构的多机构属性基加密方案。在一个前摄无中央机构的多机构属性基加密方案中 每个属性机构所掌握的私钥周期性地得到更新 而其对应的公开参数无需任何改动。这种前摄系统将在一定程度上提 ——第三章无中央机构的多机构属性基加密方案高系统的安全性因为在这样的系统中攻击者必须在一个相对较短的周期内成功攻击系统 否则在系统更新之后 攻击者在攻击旧系统中所获得的信息将对攻击更新后的系统毫无片 预备知识通信模型本章的通信模型和分布式密钥生成协议及联合零秘密分享技术 所使用的模型一样。我们的计算模型由 个视为多项式时间图灵机的属性机构组成。这些机构之间通过一个保密信道组成的网络进行通信。此外 这螳机构都能访问一个专用的广播信道。这种广播信道能保证若参与方只广播一个消息 那么其它参与方均能接收到该消息并且知道该消息是由只发送的。本章还使用了一个部分同步的通信模型。换句话说 所有在保密信道或者广播信道中传输的消息都在一个预定时间内到达接受方。如果消息无法在规定时间内到达接受方则被当作发送方没能成功地发送该消息。为了便于讨论 我们假设所有的机构都有一个同步好的时钟。 分布式密钥生成协议 与联合零秘密分享协议 分布式密钥生成协议 】是本章所给出的构造的重要组成部分。在协议中 参与方共同为一个随机变量盯构造一个 的秘密分享方案 每个人拥有针对这个随机变量的碎片 。在这个协议结束时 每个参与方只都拥有一个碎片吼且满足 这里盯为统一分布变量协议将输出一个 群上的元素矿作为系统公钥。 协议中不存在一个全知全能的第 即传统的秘密分享方案中的信发牌者 这种可信发牌者掌握秘密分亨方案分享的主秘密仃。而在 协议中 这个主秘密只有在不少于 个诚实参与方合作的情况下才能被成功恢复 除外任何参与方都无法获得这个秘密。这个性质在我们构造方案中起到了至关重要的作用。 协议的具体构造如下 协议将输出公钥旷 每个参与方将最终持有秘密 限分享的一个碎片。每个参与方只作为发牌者执行一次随机变量 协议如下 只在乙选择 次的两个多项式五

本文链接:http://weblodge.net/zhishifuzaxing/331.html