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

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

Abstract

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

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.

Figures/Tables 7

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

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

方案	散列链保存方法		保存整条链	只保存种子值
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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

散列链保存方法		保存整条链	只保存种子值
	计算	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

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

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 7

References 17

Related Articles 7

Metrics

Recommended 0

[1]	Haibo ZHANG, Zhou CHEN, Hongwu HUANG, Xiaofan HE. Intra-group mutual authentication key agreement protocol based on Chinese remainder theorem in VANET system [J]. Journal on Communications, 2022, 43(1): 182-193.
[2]	Xiangmao CHANG, Jun ZHAN, Zhiwei WANG. Low-cost group-based identity security authentication protocol for NB-IoT nodes [J]. Journal on Communications, 2021, 42(12): 152-162.
[3]	Jianwu LIANG,Xiaoshu LIU,Zi CHENG. Quantum secret sharing with graph states based on Chinese remainder theorem [J]. Journal on Communications, 2018, 39(10): 72-78.
[4]	Xiang-dong HUANG,Hong-yu XIAN,Zi-yang YAN,Sen-xue JING. Joint estimation of frequency and DOA with spatio-temporal under sampling [J]. Journal on Communications, 2016, 37(5): 21-28.
[5]	. Novel self-renewal hash chain scheme based on (t, n) threshold and division tree [J]. Journal on Communications, 2013, 34(4): 8-81.
[6]	Guo-hua ZHANG,Rong SUN,Xin-mei WANG. Explicit construction of girth-eight QC-LDPC codes and its application in CRT method [J]. Journal on Communications, 2012, 33(3): 171-176.
[7]	Xiu-sheng LIU. MDR codes and self-dual codes on Cartesian product codes [J]. Journal on Communications, 2010, 31(3): 123-125.