基于(t,n)门限和划分树的可再生散列链构造方案

doi:10.3969/j.issn.1000-436x.2013.04.008

通信学报 ›› 2013, Vol. 34 ›› Issue (4): 70-81.doi: 10.3969/j.issn.1000-436x.2013.04.008

基于(t,n)门限和划分树的可再生散列链构造方案

黄海平^1,^2,⁴,戴庭^1,²,王汝传^1,^2,³,秦小麟⁴,陈九天¹

¹ 南京邮电大学计算机学院，江苏南京 210003
² 江苏省无线传感网高技术研究重点实验室，江苏南京 210003
³ 宽带无线通信与传感网技术教育部重点实验室，江苏南京 210003
⁴ 南京航空航天大学计算机科学与技术学院，江苏南京 210016

出版日期:2013-04-25 发布日期:2017-07-17
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;江苏省科技支撑计划（工业）基金资助项目;江苏省属高校自然科学研究重大基金资助项目;国家博士后基金资助项目;江苏省博士后基金资助项目;江苏高校科技创新计划基金资助项目;江苏高校优势学科建设工程基金资助项目;江苏高校优势学科建设工程基金资助项目

Novel self-renewal hash chain scheme based on (t,n) threshold and division tree

Hai-ping HUANG^1,^2,⁴,Ting DAI^1,²,Ru-chuan WANG^1,^2,³,Xiao-lin QIN⁴,Jiu-tian CHEN¹

¹ College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China
² Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks,Nanjing 210003,China
³ Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education,Nanjing 210003,China
⁴ College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

Online:2013-04-25 Published:2017-07-17
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;Scientific ＆ Technological Support Project (Industry) of Jiangsu Province;The Natural Science Key Fund for Colleges and Universities of Jiangsu Province;Postdoctoral Foundation of China;Postdoctoral Foundation of Jiangsu Province;Science ＆ Technology Innovation Fund for Higher Educat Institutions of Jiangsu Province;The Priority Academic Program Development of Jiangsu Higher Education Institutions;The Priority Academic Program Development of Jiangsu Higher Education Institutions

摘要/Abstract

摘要：

针对可再生散列链解决了资源受限的缺点，但现有构造方案在安全性和复杂性等方面存在缺陷这一问题，提出“重复”、“划分”和“划分树”的定义，以及基于(t,n )-Mignotte's门限的中国剩余定理秘密共享方案，设计了一种新的可再生散列链构造方法。从明文空间、双重认证和可证明安全3个方面论证了新构造方案能确保新链中种子值的安全再生并有效抵制中间人攻击。仿真实验表明新构造方案在通信、计算和存储开销等方面相比于传统方案具有相同甚至更佳的性能。

关键词: 划分树, 可再生散列链, (t,n)-Mignotte's门限方案, 中国剩余定理

Abstract:

The introduction of renewal hash chain overcame resource-constrained defect in traditional hash chains,but the existing renewable schemes had still held unsatisfactory performance especially on security and complexity.The definitions of repetition,division and division-tree was proposed,and then a novel self-renewable hash chain construction scheme was put forward based on division and (,t n)-Mignotte's threshold Chinese remainder theorem secret sharing scheme.From three aspects of key space,twice authent ion and provable security,it theoretically proves that the proposed hash scheme could ensure the novel seed value regenerated safely and resisting the middle-man attack effectively.Simulation experiments demonstrate that the novel scheme obtains equal or more satisfactory performances on the costs of communication,computation and storage than typical schemes.

Key words: division-tree, renewal hash chain, (t,n )-Mignotte's threshold, Chinese remainder theorem

黄海平,戴庭,王汝传,秦小麟,陈九天. 基于(t,n)门限和划分树的可再生散列链构造方案[J]. 通信学报, 2013, 34(4): 70-81.

Hai-ping HUANG,Ting DAI,Ru-chuan WANG,Xiao-lin QIN,Jiu-tian CHEN. Novel self-renewal hash chain scheme based on (t,n) threshold and division tree[J]. Journal on Communications, 2013, 34(4): 70-81.

图/表 7

图1

图2

图3

表1

(32,q )划分中q取不同值的概率统计"

q	Test 1	Test 2	Test 3	Test 4	Test 5	Test 6	Test 7	Test 8	Test 9	Test 10	$p_{A v g_{q = j}} = \frac{1}{10} \times \sum_{i = 1}^{10} p_{i j}$
10	0.001 3	0.001 3	0.001 4	0.001 2	0.001 2	0.001 2	0.001 6	0.001 6	0.001 3	0.001 3	0.001 3
11	0.017 6	0.016 8	0.015 9	0.014 2	0.013 3	0.013 5	0.013 7	0.015 3	0.015 3	0.015 5	0.015 1
12	0.078 1	0.080 6	0.081 5	0.082 1	0.080 7	0.079 3	0.078 4	0.078 5	0.079 3	0.078 3	0.079 7
13	0.222 7	0.225 1	0.225 9	0.227 6	0.228 9	0.230 2	0.229 6	0.228 5	0.225 5	0.223 1	0.226 7
14	0.348 0	0.344 8	0.346 6	0.344 5	0.343 8	0.341 8	0.343 5	0.344 0	0.346 4	0.350 6	0.345 4
15	0.258 0	0.256 5	0.255 6	0.259 7	0.261 0	0.261 3	0.259 8	0.256 1	0.256 2	0.256 2	0.258 0
16	0.074 3	0.074 9	0.073 1	0.070 7	0.071 1	0.072 7	0.073 4	0.076 0	0.076 0	0.075 0	0.073 7

表1

表2

一般RHC的key space与SRHC-TD的key space对比（RHC、ERHC、SUHC、SRHC没有salt值的key space记为：KSu,SRHC-TD有salt值的key space记为：KSa）"

q	key space		倍数
10	KSu₁₀	553 333 286 463 413 155 119 380 296 207 872 000	143 020 679 939 872 390 880 211 676 554 285
10	KSa₁₀	79 138 102 863 361 537 004 679 285 453 617 238 668 120 868 942 959 692 426 007 139 840 000	143 020 679 939 872 390 880 211 676 554 285
11	KSu₁₁	5 187 080 514 550 099 279 678 121 388 076 646 400	3 661 891 040 325 389 282 674 949 544 144 523
11	KSa₁₁	18 994 523 661 677 418 591 170 431 781 409 944 281 563 099 229 921 542 416 319 529 347 072 000	3 661 891 040 325 389 282 674 949 544 144 523
12	KSu₁₂	26 806 046 942 907 604 997 886 958 590 845 952 000	75 742 751 459 000 734 383 329 857 043 540 793
12	KSa₁₂	2 030 363 751 194 957 174 069 912 361 433 154 199 951 665 857 317 337 853 414 530 889 487 360 000	75 742 751 459 000 734 383 329 857 043 540 793
13	KSu₁₃	76 637 826 616 149 945 551 514 260 280 729 600 000	1 324 110 606 676 344 898 872 293 485 267 251 454
13	KSa₁₃	101 476 959 095 066 836 883 574 848 357 011 830 828 587 992 686 398 439 770 172 405 579 571 200 000	1 324 110 606 676 344 898 872 293 485 267 251 454
14	KSu₁₄	117 608 245 430 622 401 776 527 064 367 308 800 000	20 264 471 610 378 457 664 64 760 637 922 372 791
14	KSa₁₄	2 383 268 950 675 269 627 341 439 620 767 777 205 252 014 589 252 078 877 364 719 119 523 225 600 000	20 264 471 610 378 457 664 64 760 637 922 372 791
15	KSu₁₅	88 465 874 655 133 624 601 621 999 967 436 800 000	279 240 713 721 406 725 647 529 271 034 190 240 345
15	KSa₁₅	24 703 273 978 688 019 410 535 964 115 469 307 361 564 474 752 449 796 080 640 681 676 767 395 840 000	279 240 713 721 406 725 647 529 271 034 190 240 345
16	KSu₁₆	24 991 467 359 322 430 689 958 992 833 556 480 000	3 545 290 824 160 424 396 558 195 520 471 044 725 362
16	KSa₁₆	88 602 019 911 310 565 452 710 747 271 750 192 445 143 064 404 384 392 174 672 129 629 351 424 000 000	3 545 290 824 160 424 396 558 195 520 471 044 725 362
$\begin{array}{l} K S u_{A v g} = \\ \sum_{q = 10}^{16} (p_{A v g_{q}} \cdot K S u_{q}) \end{array}$		84 877 236 261 416 553 573 765 570 028 577 116 785	161 995 868 252 801 528 012 638 215 965 348 282 400
$\begin{array}{l} K S a_{A v g} = \\ \sum_{q = 10}^{16} (p_{A v g_{q}} \cdot K S a_{q}) \end{array}$		13 749 761 583 066 344 526 126 464 575 649 604 504 003 162 279 445 035 355 884 359 119 207 993 553 972	161 995 868 252 801 528 012 638 215 965 348 282 400

表2

表3

RHC、ERHC、SUHC、SRHC、SRHC-TD复杂性比较(1)"

方案	散列链保存方法		保存整条链	只保存种子值
RHC	初始化	计算	(2L+3)H +2R	(3L+2)H +2R
		通信	2len_H	2len_H
		存储	2(le n_s+len_r )+(L+4)len_H	2(len_s+len_r)+4len_H
	发送认证重组——	计算	(2L+3)H +2R	$\frac{1}{2} (L^{2} + 3 L - 4) H + 2 (L - 1) R$
		通信	2L len_r+(6L?2)len_H	2Llen_r+(6L?2)len_H
		存储	2(len_s+len_r )+(L+4)len_H	len_r+ (L+2)len_H+L
ERHC	初始化	计算	$2 (n + L + ⌊ 1 b L ⌋ + 1) H + 2 (L + ⌊ 1 b L ⌋ + 1) R + 2 U$	2( n+L+? 1bL ?+1 )H+2( L+? 1bL ?+1 )R+2U
		通信	0	0
		存储	(n+2L+1)len_H+2Llenr	(2L+1)len_H+2Llen_r
	发送认证重组——	计算	$\frac{1}{2} (2 n + L + ⌊ 1 b L ⌋ + 1) H$	$\frac{1}{2} (n^{2} + n + L + ⌊ 1 b L ⌋ + 1) H$
		通信	$2 (n + L + ⌊ 1 b L ⌋ + 1) l e n_{H} + (L + ⌊ 1 b L ⌋ + 1) l e n_{r}$	$2 (n + L + ⌊ 1 b L ⌋ + 1) l e n_{H} + (L + ⌊ 1 b L ⌋ + 1) l e n_{r}$
		存储	$(n + L + ⌊ 1 b L ⌋ + 1) l e n_{H} + L$	$(n + L + ⌊ 1 b L ⌋ + 1) l e n_{H} + L$
SUHC	初始化	计算	2(L+1)H +R_B	(3L+1)H +R_B
		通信	2len_H	2len_H
		存储	2len_s+len_r+(L+3)len_H	2len_s+len_r+4len_H
	发送认证重组——	计算	(5L?2)H +(L?1)R_B+L_B	$\frac{1}{2} (L^{2} + 6 L - 4) H + (L - 1) R_{B} + L_{B}$
		通信	(6L?3)len_H+2Llen_r	(6L?3)len_H+2Llen_r
		存储	(L+2)len_H+len_r+L	(L+2)len_H+len_r+L
SRHC	初始化	计算	(2L+1)H +R_B′	3LH +R_B′
		通信	2len_H	2len_H
		存储	2len_s+len_r+(L+2)len_H	2len_s+len_r+3len_H
	发送认证重组——	计算	(3L?1)H +(L?1)R_B′+L_B′	$\frac{1}{2} (L^{2} + 5 L - 2) H + (L - 1) R_{B'} + L_{B'}$
		通信	(4L?2)len_H+2Llen_r	(4L?2)len_H+2Llen_r
		存储	Llen_H+2len_r+L	Llen_H+2len_r+L
SRHC-TD	初始化	计算	2(n+m)H +2mR_{t m}+2U +mI	2(n+m)H +2mR_{t m}+2U +m_I
		通信	0	0
		存储	(n+2m+1)len_H+2mlen_r′+mlen_I	(2m+1)len_H+2mlen_r′+mlen_I
	发送认证重组——	计算	3nH +2nM +2nP_r+C	$\frac{1}{2} (n^{2} + 5 n) H + 2 n M + 2 n P_{r} + C$
		通信	4nlen_H +2nlen_r′+2nlen_I	4nlen_H +2nlen_r′+2nlen_I
		存储	(n+2m)len_H+nlen_r′+nlen_I+L	(n+2m)len_H+nlen_r′+nlen_I+L

表3

表4

参考文献 17

[1]	MOHAMED H E , MUHAMMAD K K , KHALED A . One-time password system with infinite nested hash chains[J]. Communications in Computer and Information Science, 2010,122: 161-170.
[2]	RAMKUMAR M , MEMON N . An efficient random key pre-distribution scheme[A]. IEEE Global Telecommunications Conference(GLOBECOM'04)[C]. Los Angeles,USA, 2004. 2218-2223.
[3]	SUN Y , CAO Y F , TANG L R . A multi-phase key pre-distribution scheme based on hash chain[A]. 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery(FSKD)[C]. Sichuan,China, 2012. 2061-2064.
[4]	CHEN L , ZHANG H J , LIU N . Authentication and micropayment protocols based on self-updating hash chains[A]. The Sixth International Conference on Grid and Cooperative Computing (GCC)[C]. Los Alamitos,CA,USA, 2007. 467-472.
[5]	LIU D G , NING P . Multi-level μ TESLA:broadcast authentication for distributed sensor networks[J]. ACM Transactions on Embedded Computing System (TECS), 2004,3(4): 800-836.
[6]	OSCAR D M , AMPARO F S , JOSE M S . A light-weight authentication scheme for wireless sensor networks[J]. Ad Hoc Networks, 2011,9(5): 727-735.
[7]	EMAD A , MOHAMMED B , HOSSAM A . Hash chain links resynchronization methods in video streaming security:performance comparison[J]. Journal of Mobile Multimedia, 2011,7(1): 89-112.
[8]	GABRIELE O , STEFANO C , ROBERTO D P , et al. Robust and efficient authentication of video stream broadcasting. ACM Transactions on Information and System Security (TISSEC), 2011,14(1): 1-25.
[9]	赵源超，李道本．可再生散列链的精巧构造．电子与信息学报, 2006,28(9):1717-1720. ZHAO Y , LI D B . An elegant construction of re-initializable hash chains[J]. Journal of Electronics ＆ Information Technoloy, 2006,28(9):1717-1720.
[10]	GOYAL V . How to re-initialize a hash chain[EB/OL]. , 2004.
[11]	ZHANG H J , ZHU Y F . Self-updating hash chains and their implementations. Lecture Notes in Computer Science, 2006,4255: 387-397.
[12]	ZHANG H J . A novel self-renewal hash chain and its implementation[A]. IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC'08)[C]. Shanghai,China, 2008. 144-149.
[13]	ZHANG M Q , DONG B , YANG X Y . A new self-updating hash chain scheme[A]. International Conference on Computational I telligence and Security (CIS'09)[C]. Beijing,China, 2009. 315-318.
[14]	ZHANG W . Self-updating hash chains based on erasure coding[A]. 2010 International Conference on Computer,Mechatronics,Control and Electronic Engineering (CMCE)[C]. Changchun,China, 2010. 173-175.
[15]	YANG X Y , WANG J J , CHEN J Y . A self-renewal hash chain scheme based on fair exchange idea (SRHC-FEI)[A]. 2010 3rd IEEE International Conference on Computer Science and Infor ion Technology (ICCSIT'10)[C]. Chengdu,China, 2010. 152-156.
[16]	ULUTAS M , NABIYEV V V , ULUTAS G . A new secret image sharing technique based on Asmuth Bloom's scheme[A]. International Conference on Application of Information and Communication Technologies(AICT)[C]. Baku,Azerbaijan, 2009. 1-5.
[17]	LEIN H , LIN C L . Strong (n,t,n) verifiable secret sharing scheme[J]. Information Sciences, 2010,180: 3059-3064.

散列链保存方法		保存整条链	只保存种子值
	计算	SRHC < SUHC < RHC < SRHC-TD < ERHC	SRHC < SUHC < RHC < SRHC-TD < ERHC
初始化	通信	ERHC = SRHC-TD < RHC = SRHC = SUHC	ERHC= SRHC-TD < RHC = SRHC = SUHC
	存储	SRHC < SUHC < RHC < SRHC-TD < ERHC	SRHC < SUHC < RHC < SRHC-TD < ERHC
	计算	ERHC < RHC < SRHC < SRHC-TD < SUHC	ERHC < RHC < SRHC < SRHC-TD < SUHC
发送—认证—重组	通信	SRHC-TD < SRHC < ERHC < RHC < SUHC	SRHC-TD < SRHC < ERHC < RHC < SUHC
	存储	SRHC < SUHC < RHC < SRHC-TD < ERHC	SRHC< SUHC = RHC < SRHC-TD < ERHC

基于(t,n)门限和划分树的可再生散列链构造方案

Novel self-renewal hash chain scheme based on (t,n) threshold and division tree

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 17

相关文章 6

Metrics

推荐阅读 0

[1]	张海波, 陈舟, 黄宏武, 贺晓帆. VANET系统中基于中国剩余定理的群内相互认证密钥协商协议[J]. 通信学报, 2022, 43(1): 182-193.
[2]	常相茂, 占俊, 王志伟. 低开销的NB-IoT节点群组身份安全认证协议[J]. 通信学报, 2021, 42(12): 152-162.
[3]	梁建武,刘晓书,程资. 基于图态和中国剩余定理的量子秘密共享方案[J]. 通信学报, 2018, 39(10): 72-78.
[4]	黄海平1,2,4，戴庭1,2，王汝传1,2,3，秦小麟4，陈九天1. 基于(t, n)门限和划分树的可再生Hash链构造方案[J]. 通信学报, 2013, 34(4): 8-81.
[5]	张国华,孙蓉,王新梅. 围长为8的QC-LDPC码的显式构造及其在CRT方法中的应用[J]. 通信学报, 2012, 33(3): 171-176.
[6]	刘修生. 卡氏积码的MDR码和自对偶码[J]. 通信学报, 2010, 31(3): 123-125.