基于有向哈希树的认证跳表算法_徐剑1
需积分: 0 181 浏览量
2022-08-04
16:13:07
上传
评论
收藏 573KB PDF 举报
第
３８
卷
第
９
期
２０１１
年
９
月
计 算 机 科 学
Ｃｏｍ
ｐ
ｕｔｅｒ
Ｓｃｉｅｎｃｅ
Ｖｏｌ．３８Ｎｏ．９
Ｓｅ
ｐ
２０１１
到稿日期
：
２０１０
－
１０
－
０９
返修日期
：
２０１０
－
１２
－
１６
本文受国家高技术研究发展计划
８６３
项目
（
２００９ＡＡ０１Ｚ１２２
），
沈阳市自然科学基金项目
（
Ｆ１０
－
２０５
－
１
－
１２
）
资助
。
徐
剑
（
１９７８－
），
博士生
，
助教
，
主要研究领域为密码学与网络安全
、
数据与身份认证技术
，
Ｅ
－
ｍａｉｌ
：
ｘｕ
ｊ
＠
ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ
；
陈
旭
（
１９８４－
），
女
，
硕士生
，
主要研究领域为密码学与网络安全
；
李福祥
（
１９８４－
），
男
，
硕士生
，
主要研究领域为密码学与网络安全
；
周福才
（
１９６４－
），
男
，
博士
，
教授
，
博士生导师
，
主要研究领域为网络与信息安全
、
可信计算
、
电子商务基础理论及关键技术
。
基于有向哈希树的认证跳表算法
徐
剑
１
，
２
陈
旭
１
李福祥
１
周福才
１
（
东北大学信息科学与工程学院
沈阳
１１０８１９
）
１
（
东北大学软件学院
沈阳
１１０８１９
）
２
摘
要
作为一种重要的认证数据结构
，
认证跳表在数据认证机制中有着广泛的应用
。
由于哈希模式对认证跳表的
代价有显著的影响
，
因此提出哈希模式和数据存储模式分离的思想
，
设计了一种新的认证哈希模式
———
有向哈希树
，
并在其基础上设计了新的认证跳表算法
。
应用分层数据处理
、
概率分析等数学方法对所提出算法的代价进行了理论
分析
，
并与已有的认证跳表算法做了性能比较
。
结果表明
，
本算法在时间
、
通信和存储代价方面有了较大的改进
。
关键词
认证跳表
，
认证哈希模式
，
有向哈希树
，
认证数据结构
中图法分类号
ＴＰ３０９
文献标识码
Ａ
Ａｌ
ｇ
ｏｒｉｔｈｍ
ｏｆ
Ａｕｔｈｅｎｔｉｃａｔｅｄ
Ｓｋｉ
ｐ
Ｌｉｓｔ
Ｂａｓｅｄ
ｏｎ
Ｄｉｒｅｃｔｅｄ
Ｈａｓｈ
Ｔｒｅｅ
ＸＵ
Ｊｉａｎ
１
，
２
ＣＨＥＮ
Ｘｕ
１
ＬＩ
Ｆｕ
－
ｘｉａｎ
ｇ
１
ＺＨＯＵ
Ｆｕ
－
ｃａｉ
１
（
Ｓｃｈｏｏｌ
ｏｆ
Ｉｎｆｏｒｍａｔｉｏｎ
Ｓｃｉｅｎｃｅ
ａｎｄ
Ｅｎ
ｇ
ｉｎｅｅｒｉｎ
ｇ
，
Ｎｏｒｔｈｅａｓｔｅｒｎ
Ｕｎｉｖｅｒｓｉｔ
ｙ
，
Ｓｈｅｎ
ｙ
ａｎ
ｇ
１１０８１９
，
Ｃｈｉｎａ
）
１
（
Ｓｏｆｔｗａｒｅ
Ｃｏｌｌｅ
ｇ
ｅ
，
Ｎｏｒｔｈｅａｓｔｅｒｎ
Ｕｎｉｖｅｒｓｉｔ
ｙ
，
Ｓｈｅｎ
ｙ
ａｎ
ｇ
１１０８１９
，
Ｃｈｉｎａ
）
２
Ａｂｓｔｒａｃｔ
Ａｕｔｈｅｎｔｉｃａｔｅｄ
ｓｋｉ
ｐ
ｌｉｓｔ
ｉｓ
ａｎ
ｉｍ
ｐ
ｏｒｔａｎｔ
ａｕｔｈｅｎｔｉｃａｔｅｄ
ｄａｔａ
ｓｔｒｕｃｔｕｒｅｓ．Ｉｔ
ｈａｓ
ｂｅｅｎ
ｗｉｄｅｌ
ｙ
ｕｓｅｄ
ｉｎ
ｄａｔａ
ａｕｔｈｅｎｔｉ
－
ｃａｔｉｏｎ．Ｓｉｎｃｅ
ｔｈｅ
ｈａｓｈ
ｓｃｈｅｍｅ
ｈａｓ
ｔｈｅ
ｉｍ
ｐ
ｏｒｔａｎｔ
ｉｎｆｌｕｅｎｃｅ
ｏｎ
ｔｈｅ
ｃｏｓｔ
ｏｆ
ｔｈｅ
ａｕｔｈｅｎｔｉｃａｔｅｄ
ｓｋｉ
ｐ
ｌｉｓｔ
，
ａ
ｎｅｗ
ｈａｓｈ
ｓｃｈｅｍｅ
ｗｈｉｃｈ
ｉｓ
ｂａｓｅｄ
ｏｎ
ｔｈｅ
ｉｄｅａ
ｏｆ
ｓｅ
ｐ
ａｒａｔｉｎ
ｇ
ｔｈｅ
ｈａｓｈ
ｓｃｈｅｍｅ
ａｎｄ
ｄａｔａ
ｓｔｏｒａ
ｇ
ｅ
ｓｃｈｅｍｅ
ｗａｓ
ｐ
ｒｏ
ｐ
ｏｓｅｄ
ｉｎ
ｔｈｉｓ
ｐ
ａ
ｐ
ｅｒ．Ａｎｄ
ｔｈｅ
ｎｅｗ
ａｌ
ｇ
ｏｒｉｔｈｍ
ｏｆ
ａｕｔｈｅｎｔｉｃａｔｅｄ
ｓｋｉ
ｐ
ｌｉｓｔ
（
ＡＳＬ
－
ＤＨＴ
ｆｏｒ
ｓｈｏｒｔ
）
ｂａｓｅｄ
ｏｎ
ｄｉｒｅｃｔｅｄ
ｈａｓｈ
ｔｒｅｅ
ｗａｓ
ａｌｓｏ
ｐ
ｒｏ
ｐ
ｏｓｅｄ．Ｗｅ
ａ
ｐ
－
ｐ
ｌｉｅｄ
ｈｉｅｒａｒｃｈｉｃａｌ
ｄａｔａ
ｐ
ｒｏｃｅｓｓｉｎ
ｇ
ａｎｄ
ｐ
ｒｏｂａｂｉｌｉｔ
ｙ
ａｎａｌ
ｙ
ｓｉｓ
ｍｅｔｈｏｄｓ
ｔｏ
ａｎａｌ
ｙ
ｚｅ
ｔｈｅ
ｃｏｓｔ
ｏｆ
ＡＳＬ
－
ＤＨＴ
，
ａｎｄ
ａｌｓｏ
ｍａｄｅ
ａｎ
ａｌ
ｇ
ｏｒｉｔｈｍ
ｓｉｍｕｌａｔｉｏｎ
ｔｏ
ｃｏｍ
ｐ
ａｒｅ
ｗｉｔｈ
ｔｈａｔ
ｏｆ
ｔｈｅ
ｏｒｉ
ｇ
ｉｎａｌ
ａｕｔｈｅｎｔｉｃａｔｅｄ
ｓｋｉ
ｐ
ｌｉｓｔ．Ｔｈｅ
ｒｅｓｕｌｔｓ
ｓｈｏｗ
ｔｈａｔ
，
ＡＳＬ
－
ＤＨＴ
ａｌ
ｇ
ｏ
－
ｒｉｔｈｍ
ｈａｓ
ｇ
ｏｔ
ｇ
ｒｅａｔ
ｉｍ
ｐ
ｒｏｖｅｍｅｎｔ
ｏｎ
ｓｔｏｒａ
ｇ
ｅ
ｃｏｓｔ
，
ｃｏｍｍｕｎｉｃａｔｉｏｎ
ｃｏｓｔ
，
ａｎｄ
ｔｉｍｅ
ｃｏｓｔ．
Ｋｅ
ｙ
ｗｏｒｄｓ
Ａｕｔｈｅｎｔｉｃａｔｅｄ
ｓｋｉ
ｐ
ｌｉｓｔ
，
Ａｕｔｈｅｎｔｉｃａｔｅｄ
ｈａｓｈ
ｓｃｈｅｍｅ
，
Ｄｉｒｅｃｔｅｄ
ｈａｓｈ
ｔｒｅｅ
，
Ａｕｔｈｅｎｔｉｃａｔｅｄ
ｄａｔａ
ｓｔｒｕｃｔｕｒｅｓ
认证 数据 结构
［
１
，
２
］
（
Ａｕｔｈｅｎｔｉｃａｔｅｄ
Ｄａｔａ
Ｓｔｒｕｃｔｕｒｅ
，
ＡＤＳ
）
是在认证字典
［
３
，
４
］
基础上发展起来的一种分布式计算模型
，
它可以保证数据的完整性以及端到端可信性
，
已 在 证 书 撤
销
［
５
］
、
数字时间戳
［
６
］
以及数据库外包
［
７
，
８
］
中得到广泛应用
。
认证跳表
［
９
］
是实现
ＡＤＳ
的一种重要数据结构
。
它是 在
跳表
［
１０
］
基础上
，
利用跳表节点存储数据元素的哈希值
，
并通
过相应的哈希计算来实现数据认证
。
与以往跳表不同
，
认证
跳表在跳表节点中存储数据元素的哈希值
，
同时定义了一些
密码学计算方法来实现数据认证
。
目前的认证跳表算法大都
采用
Ｇｏｏｄｒｉｃｈ
等人提出的算法
［
９
］
，
在该算法中数据的存储模
式和哈希模式是一致的
，
因此其计算代价和存储代价都较高
。
本文提出数据存储模式和哈希模式相分离的设计思想
，
即通过计算和保存存储模式中某些特定节点的哈希值
，
来有
效降低算法的存储和计算代价
。
为实现数据的存储模式和哈
希模式相分离的思想
，
设计了与跳表存储模式相分离的有向
哈希树
（
Ｄｉｒｅｃｔｅｄ
Ｈａｓｈ
Ｔｒｅｅ
，
ＤＨＴ
），
即 在
ＤＨＴ
中 只存 储 跳
表中部分节点的哈希值
，
因此其存储代价和哈希代价降低为
Ｏ
（
ｌｏ
ｇ
ｎ
）。
在
ＤＨＴ
基 础 上
，
设计了认证跳表的新的实现算
法
———
ＡＳＬ
－
ＤＨＴ
，
它在数据的存储方式上与
Ｇｏｏｄｒｉｃｈ
认 证
跳表一致
，
只是在哈希模式方面采用本文设计的
ＤＨＴ
。
由于
采用了
ＤＨＴ
，
ＡＳＬ
－
ＤＨＴ
在时 间
、
通信和存储代价方面有了
很大的改进
。
本文第
１
节给出了有向哈希树的分析和设计思想
，
包括
ＤＨＴ
的构建算法
；
第
２
节给出了
ＡＳＬ
－
ＤＨＴ
算法设计
，
包括
ＡＳＬ
－
ＤＨＴ
算法中的节 点 插 入
、
节 点删 除 和
ＡＳＬ
－
ＤＨＴ
特 征
值计算
；
第
３
节利用分层数据 处理
［
１１
，
１２
］
及概率分析方法对算
法的计算复杂度进行分析
，
通过 实验将
ＡＳＬ
－
ＤＨＴ
算法 和已
有跳表算法进行性能比较
；
最后是全文总结
。
１
有向哈希树分析与设计
１．１
认证哈希模式定义
本小节首先给出认证哈希模式和认证跳表中认证代价的
定义
。
定义
１
认 证 哈 希 模 式
（
Ａｕｔｈｅｎｔｉｃａｔｅｄ
Ｈａｓｈ
Ｓｃｈｅｍｅ
，
·
２３
·
评论0
最新资源