基于时代可撤销的变色龙哈希.pdf

收稿日期:修回日期:基金项目:国家自然科学基金资助项目()作者简介:郝增航()男硕士生主要研究方向为应用密码学:.:/基于时代可撤销的变色龙哈希郝增航 陈 越 魏江宏 张万里(信息工程大学河南 郑州)摘要:变色龙哈希函数是带有陷门的单向哈希函数现已成为实现可编辑区块链的主要技术为解决可编辑区块链中变色龙哈希函数陷门滥用的问题提出了基于时代可撤销的变色龙哈希函数其中一个时代为一个具体的时间周期 该函数使得陷门具有时效性将随时代变更失效以达到撤销陷门的目的 定义了其安全模型并给出了具体的方案实例方案在标准的困难假设下被证明是安全的 理论分析和实验表明相比于同类型的方案所提方案在安全性上具有优势且具有较小的额外开销具备一定实用性关键词:可编辑区块链变色龙哈希陷门撤销中图分类号:.文献标识码:文章编号:().区块链作为去中心化的分布式账本存储区块链网络节点发布的各种数据 被写入到区块链上的数据通常被认为是不可篡改的不能编辑这些数据一般被称为交易或事务不可篡改性在确保链上数据真实性的同时也带来了数据监管上的困难 依据数据安全法需要区块链具备上链数据的监管和补救手段 可编辑区块链为解决上述问题提供了有效的技术手段主要通过变色龙哈希()函数实现由文献首次提出 文献在文献的基础上分别结合属性加密、黑盒问责机制等技术对事务级编辑、问责机制和去中心化等方面进行了研究 文献提出了一个 次修改和基于时代的方案能够限制编辑次数以上方案缺少编辑权限的撤销属性即陷门撤销 恶意编辑者可以使用陷门无限期地编辑事务有滥用编辑权限的倾向 文献提出了第一个可撤销的具有临时陷门的变色龙哈希(第 卷第 期 年 月信 息 工 程 大 学 学 报 .)文献在文献的基础上进行改进在每次计算 的碰撞后陷门将被立即更新以避免陷门暴露问题 文献通过可撤销属性加密与 结合来实现可撤销属性 文献通过 的嵌套结构实现可撤销属性允许事务发布者管理自己发布的事务并通过半可信的监管机构对事务发布者的编辑权限进行撤销目前具有可撤销属性的可编辑区块链方案缺少更细粒度的编辑限制如设置陷门的使用期限来进一步防止编辑权限的滥用 尽管在文献中通过时间戳返回函数和预设的时间期限构建陷门使得一旦返回的时间戳超出预设的时间期限陷门将失效但忽略了因此导致的哈希值也无法验证的问题 在其他方案中虽然可以通过定期撤销陷门的方式来使陷门失效但基于复杂的密码学原语会严重消耗系统资源本文考虑了文献基于时代的思想改进了文献的方案提出基于时代可撤销的变色龙哈 希()函数的概念 其具有可撤销属性并能够限制陷门使用期限即在前一个时代发布的陷门将在下一个时代到来时失效被撤销无需复杂的密码学原语能够有效降低系统开销 其中一个时代表示一个具有起止时间的时间周期多个时代之间具有先后顺序并离散地链接在一起 基于双线性映射给出了 的实例依据给出的 实例严格证明了安全性通过对现有方案的性能对比说明了本方案具有的安全优势通过实验分析验证了其实际可用性 预备知识.变色龙哈希一个定义在消息空间 的 函数由以下 个算法组成)():公共参数生成算法 输入一个安全参数 输出公共参数 并假设 作为其他算法的隐式输入)()():陷门生成算法 以公共参数 作为输入输出陷门与公钥()()():哈希算法 输入公钥 消息 输出哈希值 以及随机字符串)():验证算法输入公钥 一个包含哈希值、消息 和随机字符串 的三元组检查()是否与消息 匹配若是输出 否则输出)():修改算法 输入陷门 一个包含哈希值、消息 和随机字符串 的三元组新消息 输出一个新随机字符串.双线性映射设、和是阶为素数 的乘法循环群是双线性映射满足下述性质)双线性:对于任给的 满足()()()非退化性:存在 使得()可计算性:任给 存在有效算法计算().困难问题假设设一个乘法循环群 的阶为 生成元为 给定 其中)计算迪菲赫尔曼问题():计算 是困难的)可分计算迪菲赫尔曼问题():计算/是困难的 基于时代可撤销的变色龙哈希.形式化定义 具有一组有限的、被称为时代的连续时间周期其中 表示最大时代数 假设每个时代 都有独立的持续时间且已知具有不同的公钥 其中 被称为时代号 具有双陷门结构包含从陷门和主陷门 时代发布的从陷门将在 时代到来时失效主陷门用于发布当前时代的从陷门 相比于 函数 新增了两个算法:用于生成当前时代从陷门的 算法使用当前时代的公钥进行哈希值验证的 算法 具体而言 的形式化定义如下:)():系统参数生成算法 输入一个安全参数 输出一个系统参数 并作为其他算法的隐式输入)()():主陷门生成算法输入系统参数 和最大时代数 生成主陷门 和 个时代的公钥 输出主陷门对()()():哈希算法 第 期郝增航等:基于时代可撤销的变色龙哈希 输入当前时代 的公钥 一个消息 自定义身份 当前时间 输出哈希值 和一个随机字符串 其中 包含 和)():验证算法 输入随机字符串 包含的 对应的时代公钥一个包含哈希值、消息 随机字符串 的三元组如果()有效则输出 否则输出)()():从陷门生成算法 输入主陷门 一个三元组()当前时间 输出当前时代 对应的从陷门 和新随机字符串 其中 包含)():修改算法 输入从陷门 一个三元组()一个新消息 输出新随机字符串 其中 为随机字符串 中包含的时间 所对应时代的从陷门)():编辑算法 输入当前时代的公钥 一个三元组()如果()有效则输出 否则输出 上述定义中 算法输入 和 其中 是自定义的身份字符串在区块链中可以是用户钱包地址的哈希值不与区块链的匿名性冲突用于实现类似文献的问责机制包含 是为了将时间写入到哈希值中由于时代的持续时间是已知的因此根据 可以找到对应的时代进而找到对应的公钥 用于 算法的验证 算法与 算法的不同之处在于 总是使用当前时代的公钥验证而 是根据随机字符串中时间 对应的公钥进行验证 随着时代的更迭 算法和 算法的输出结果将不能通过 算法 换言之随着时代的更迭作为算法输入的从陷门 将失效而能将时间 改写的算法只有 其需要输入主密钥 输出一个当前时代的新从陷门.安全性定义 的安全性定义主要依据文献中给出的安全模型 此外假设与时代相关的公共参数是无法被改变的即游戏中的任何一方对于时代的视图是相同的 这些参数信息包括当前时代的时代号以及全部时代的公钥定义 安全的 若一个 方案满足正确性、可撤销性、主陷门抗碰撞性、从陷门抗碰撞性则称它是安全的.正确性正确性一方面要求所有通过、算法正确生成的结果都能通过 算法另一方面要求当输出的随机字符串所包含的时间 属于当前时代时、算法输出的结果都能通过 算法 算法 给出了 的正确性实验定义了两个理想函数()()其中()即给定随机字符串 计算其中包含的时间 对应的公钥()即函数直接获得 当 前 时 代 的 公 钥 其 中 变 量()通过敌手的查询而改变当 时不允许进行查询 当输出信号 后实验结束若输出 则说明 满足正确性否则失败算法 正确性实验输入:能查询和的敌手输出:或者.初始化:()()():/挑战者计算和公开以上参数其中 为敌手可查询的变量/.()():()/挑战者计算哈希值并设置公开变量 的值/.:/设置查询信号为/.()/敌手查询跳转 查跳转 不查询将查询信号置为/.提取()()()()输出 ()输出.()():提取()返回步骤 ()():()返回步骤.()():返回步骤 提取()():()返回步骤.可撤销性可撤销性要求在时代 发布的从陷门 将在 信 息 工 程 大 学 学 报 年时代到来时失效即计算的碰撞结果不能通过 算法 此外当使用 算法发布后续时间的新从陷门后 计算碰撞的能力将被撤销即碰撞结果不能通过 算法 算法 给出了 可撤销性实验定义了理想函数()即给定时间 函数()输出 对应的时代 允许敌手对查询多次表将记录每次查询得到的从陷门 表记录查询过的()可以使用 任意计算碰撞 一旦决定挑战将输出挑战信息()中包含的自定义身份为 时间为 为属于当前时代随机选取的挑战时间为表中的从陷门为挑战 算法的新消息若实验输出 的概率可以忽略不计则说明 满足可撤销性否则失败算法 可撤销性实验输入:能查询的敌手输出:或者.初始化:()()()/挑战者计算和公开以上参数/.()()/敌手查询若查询则跳转至 不查询输出挑战信息/.()()输出 ()()()()()()()()输出 输出.()():返回步骤 ()返回步骤 ()()()()返回()返回步骤.主陷门抗碰撞性主陷门抗碰撞性要求非主陷门 的持有者不能通过 算法计算任何碰撞 对于任意有效的三元组()要求敌手输出有效的随机字符串和从陷门对()的概率是忽略不计的 算法 给出主陷门抗碰撞性实验允许敌手查询获得多组碰撞结果和从陷门 一旦决定挑战输出挑战信息()其中()、()分别为、包含的身份字符串和时间若实验输出 的概率可以忽略不计则说明 满足主陷门抗碰撞性否则失败算法 主陷门抗碰撞性实验输入:能查询的敌手输出:或者.初始化:()()().()()/敌手查询若查询则跳转至 不查询输出挑战信息/.()()输出 ()()()()输出 ()()输出.()():返回步骤 ()返回步骤 ()()()()返回()返回步骤.从陷门抗碰撞性从陷门抗碰撞性要求非从陷门 的持有者不能通过 算法计算任何碰撞安全模型类似于文献定义的标准抗碰撞性()算法 给出了从陷门抗碰撞性实验允许敌手查询使用表 记录查询信息 和 一旦敌手决定挑战对于任意有效的三元组()输出未在表 中记录的 的有效碰撞值通过 算法则输出 否则输出 算法 从陷门抗碰撞性实验输入:能查询的敌手输出:或者.初始化:()().()()/敌手查询若查询则跳转至 不查询输出挑战信息/.()()第 期郝增航等:基于时代可撤销的变色龙哈希)输出.()():()返回步骤 ()返回 返回步骤.具体构造本节给出 的具体构造为了简化说明假设给定的时代 包含了持续时间)():算法输入安全参数 设置双线性映射:其中和是生成元为、阶为 的乘法循环群设置一组有限的时代其中 为最大时代数 算法选择哈希函数:理想函数()()和()输出()()():密钥生成算法输入公共参数 和最大时代数 生成 个互不相等的随机数()并计算()令主陷门 为()公 钥 ()输出()()():哈希生成算法输入当前时代的公钥 ()消息自定义身份 当前时间戳 选择随机数()计算 和哈希值()()()()令随机字符串 ()输出()():验证算法输入随机字符串 ()消息 和哈希值 通过()得到 中包含时间戳 对应的时代公钥()检查是否有 ()()()()若是则输出 否则输出)()():从陷门生成算法输入主陷门 包括消息、随机字符串()和哈希值 的有效三元组当前时间戳 根据 对应的时代 和计算从陷门()和碰撞值()()()/输出新字符串()():修改算法输入从陷门()有效三元组()()和新消息计算碰撞值()()()/输出新字符串()():编辑算法通过理想函数()获取当前时代的公钥()输入消息 哈希值 和随机字符串()检查是否有哈希值()()()()成立若是则输出 否则输出.安全性证明.正确性根据正确性定义意味着、和 算法正确输出的结果可以重构哈希值 首先考虑 算法证明如下)对于 算法的输出结果包括哈希值()()()()、随机字符串()和消息 由 对应的时代公钥()()使用 算法的输出结果重构 是显然的)对于 算法输出结果包括哈希值 随机字符串 ()和消息 其中()()()/由 对应的时代公钥()()重构如下()()()()()()()()()()()/)()()()()()()()()()由 证毕)对于 算法输出结果包括哈希值 随机字符串()和消息 其中()()()/由 对应的时代公钥()()重构 如下()()()()()()()()()()/)()()()()()()()()()()由 证毕 信 息 工 程 大 学 学 报 年另一方面考虑 算法 由于 算法在验证时总是使用当前时代的公钥 因此依据安全性实验当有()()时即随机字符串 包括的 对应的时代公钥与当前时代公钥相同时算法与 算法是等价的以上 个算法的结果显然都能通过 算法.可撤销性首先证明从陷门 将随时代变更失效 对于在时代 生成的任意有效三元组()在通过 算法验证时使用的公钥为 在后续时代 到来时该三元组显然不能通过 算法否则下式成立()()()()()()()()()有 与 互不相等矛盾由于从陷门 在计算碰撞时不改变 因此产生的新碰撞结果也不能通过 算法证毕 这样在实验 中的 值不为敌手赢得挑战的条件是在发布新从陷门 后使用 输出一组有效碰撞证明如下定理 若 假设成立则满足可撤销性证明 在挑战者 与敌手、的博弈中证明上述定理假设存在多项式时间的敌手能赢得可撤销性实验则能构建一个敌手 利用的输出结果攻击 假设)设置阶段:挑战者 输出()给 敌手使用构建 其他初始参数则按照可撤销性实验设置)查询阶段:允许敌手查询的次数为 查询 的次数为 假设不会对 发起两次相同的询问如果将()作为挑战信息或进行询问则它之前已经查询过()和()对于 查询敌手使用表 存储询问值 敌手 随机选择两个不同的猜测值 这两次的 查询将与挑战信息对应不失一般性假设时间 若在表 中 以 作为应答值 否则选择随机数 若 计算 作为应答值并存入表若分别计算和 作为应答值在查询上需要对猜测值 至少查询次且不能查询 否则 无法利用 对于有效的查询值()敌手检查表中是否有()()若没有则将其加入到表中计算()()检查 是否在表中若没有将其加入到表 敌手 计算碰撞值 返回()给)挑战阶段:一旦决定挑战输出挑战信息()若()和()对应的 查询值不为 和 则无法利用否则 通过 算法检查三元组()的 有 效 性 是 否 有 且()不在表中检查 是否在表中 若以上条件都满足通过 算法计算和 现在有()使用 通过 算法计算得到 的碰撞值 验证是否有()等于 不失一般性令()()对应的时代为()对应()输出/给挑战者 若有不可忽略的优势 赢得挑战则有()()()()()()()()()()()()()()()()/)()()上式化简可以得到()()()()()()()()()有()()因为有()()于是有 获得/赢得挑战在以上游戏中若 猜测正确且不中断的视图与真实攻击同分布由于 的随机性是随机均匀的与 的结果同分布猜测正确的概率为/()赢 得 挑 战 的 概 率 为()().主陷门抗碰撞性主陷门抗碰撞性要求非主陷门持有者不能通过 算法输出任何有效碰撞或新从陷门定理 若 和 假设成立则 满足主陷门抗碰撞性证明 在挑战者 与敌手、的博弈中证明 第 期郝增航等:基于时代可撤销的变色龙哈希上述定理)设置阶段:挑战者将()输出给敌手要求 输出 或/敌手 生成 个互不相等的随机数()令时代公钥集合为()其他初始参数按照主陷门抗碰撞实验设置)查询阶段:允许敌手进行 和查询的次数分别为 和 设 不会对 发起两次相同的询问如果将(/)作为挑战信息或进行询问则它之前已经查询过()和()选择一个随机猜测值 第 次 查询的结果将与挑战信息对应对于 查询与可撤销性实验类似当 第 次查询时 返还 作为应答值否则返还 其中 将查询结果存入表 对于与可撤销性实验类似输入有效查询值()若将第 次 查询对应的()作为输入则 无法利用否则 计算 和碰撞值 返回()给将 加入到表中将()()加入到表中)挑战阶段:一旦决定挑战输出挑战信息()设上述挑战信息中和 对应的时代为()()有 ()和 ()设()和()分别对应表 中的()和()通过 算法检查三元组()的有效性检查是否有 且集合()()不为表的子集检查 是否不在表 若以上条件都满足 计算式为 ()()使用 和 计算三元组()的一组新碰撞()计算过程为 ()()()()使用()重构 令挑战信息中的()()()若有 则()()()()()()()/)()()()()()化简可以得到)输出式()和/给挑战者 在上述过程中若()对应的 查询值不为 则 无法利用 若有不可忽略的优势 赢得挑战且式()中的/或有 /获得/或成功攻击 假设或 假设猜测正确的概率为/赢得挑战的概率为/(/).从陷门抗碰撞性定理 若 假设成立则 满足从陷门抗碰撞性证明 在挑战者 与敌手、的博弈中证明上述定理)设置阶段:挑战者将()输出给敌手要求 输出/敌手 生成()个互不相等的随机数()令时代公钥集合为()其他初始参数按照从陷门抗碰撞实验设置)查询阶段:允许敌手进行 和查询的次数分别为 和 设置猜测值 在第 次查询时返还 否则返还 将相应值记录到表 在查询中根据有效的()和 返还碰撞值 并将 记录到表中 要求挑战时使用猜测值 生成 否则无法利用)挑战阶段:通过 算法检查三元组()和()的有效性检查是否不在表中 设 和 对应的时代为若都满足 得到()()()输出/给挑战者 若 有不可忽略的优势 赢得挑战且 有/成功攻击 假设猜测正确的概率为/赢得挑战的概率为(/)/性能分析.理论分析表 将 与文献方案进行对比从表中可见 不存在陷门暴露的问题所谓陷门暴露是指敌手在观察多组 的碰撞结果后能 信 息 工 程 大 学 学 报 年够反向推出陷门进而计算任意碰撞 文献存在这个问题文献通过在每次计算碰撞后立即撤销陷门来解决此问题考虑计算大量碰撞的情况下开销无疑是巨大的 由于在.节的主、从陷门抗碰撞性证明中在允许敌手查询多组碰撞结果的情况下仍能证明安全性因而解决了这个问题表 不同方案的对比方案困难假设 陷门暴露陷门时效性哈希时效性陷门撤销方式文献有无无仅固定时间文献无无有仅每次计算碰撞后/无有无随时代/任意时间在文献的可撤销方案中陷门都与时间有关本文相较于以上两者的优势有以下几点:一是陷门具有时效性无需任何陷门撤销操作前一时代发布的陷门将在下一时代失效(无法通过 算法)二是哈希无时效性文献方案中生成的哈希值将随时间失效无法验证其正确性在区块链环境下将导致链的中断三是陷门撤销的方式灵活既可以不进行任何操作使陷门随时代更替失效也可以运行 算法在任意时间撤销陷门 表 将本文算法与文献算法的计算复杂性进行比较其中:表示群指数表示群乘法表示生成元的逆运算表示双线性配对操作表 不同方案算法的计算复杂性方案算法文献文献对比结果表明方案在 算法上需要更多双线性配对操作在 和 算法上具有较少的群指数和群乘法操作计算复杂性较低.的性能在具有 内存和 .的 上进行仿真实验 在 框架下使用嵌入度为 的超奇异曲线 模拟实例图 给出了 各算法的实际运行时间取 次实验结果的平均值其中消息 大小为 图 将 和文献在、和 算法的运行时间上进行了比较 从图 中可见 在 和 算法上运行时间更少在其他算法上带来的额外开销也较小图 算法的运行时间图 不同算法运行时间对比图 主要考虑 和 算法多次运行的时间是因为 和 可以本地进行计算在区块链环境下矿工(区块链中生成区块的用户)主要运行 和/算法而 和 算法的运行时间是相当的 从实验结果可见在仅考虑以上两种算法时本方案相较于文献具有更少的时间成本效率更高图 多次运行 和 算法的时间成本 结束语可编辑区块链为解决链上的数据安全问题提 第 期郝增航等:基于时代可撤销的变色龙哈希供有效技术手段 针对现有带可撤销性的可编辑区块链方案缺少更细粒度的编辑限制的问题为防止编辑权限的滥用实现陷门的时效性本文提出了基于时代可撤销的变色龙哈希函数的概念和安全模型基于双线性映射给出了一个具体构造并给出了该构造的安全证明 通过理论分析和仿真实验表明相较于现有方案 以较小的计算代价实现了更高的安全性保证具有一定的实际可用性参考文献:.:.:.:.:.:.:.:.:.():.():.:.:.:.:.:.:.:.():.():.(编辑:刘彦茹)信 息 工 程 大 学 学 报 年