Improving the efficiency of quantum hash function by dense coding of coin operators in discrete-time quantum walk

YuGuang Yang; YuChen Zhang; Gang Xu; XiuBo Chen; Yi-Hua Zhou; WeiMin Shi

doi:10.1007/s11433-017-9132-y

SCIENCE CHINA Physics, Mechanics & Astronomy

SCIENCE CHINA Physics, Mechanics & Astronomy, Volume 61, Issue 3: 030312(2018) https://doi.org/10.1007/s11433-017-9132-y

Improving the efficiency of quantum hash function by dense coding of coin operators in discrete-time quantum walk

YuGuang Yang^1,*, YuChen Zhang¹, Gang Xu², XiuBo Chen², Yi-Hua Zhou¹, WeiMin Shi¹

More info

ReceivedOct 3, 2017
AcceptedNov 8, 2017
PublishedJan 18, 2018

PACS numbers

Previous Table of Contents Next

Rating

Abstract

Li et al. first proposed a quantum hash function (QHF) in a quantum-walk architecture. In their scheme, two two-particle interactions, i.e., I interaction and π-phase interaction are introduced and the choice of I or π-phase interactions at each iteration depends on a message bit. In this paper, we propose an efficient QHF by dense coding of coin operators in discrete-time quantum walk. Compared with existing QHFs, our protocol has the following advantages: the efficiency of the QHF can be doubled and even more; only one particle is enough and two-particle interactions are unnecessary so that quantum resources are saved. It is a clue to apply the dense coding technique to quantum cryptographic protocols, especially to the applications with restricted quantum resources.

Funded by

and Beijing Natural Science Foundation(Grant)

the National Natural Science Foundation of China(Grant)

Acknowledgment

This work was supported by the National Natural Science Foundation of China (Grant Nos. 61572053, 61671087, U1636106, and 61602019), and Beijing Natural Science Foundation (Grant No. 4162005).

References

[1] D. Knuth, The Art of Computer Programming, Sorting and Searching (Addison-Wesley, New Jersey, 1998). Google Scholar

[2] X. Wang, D. Feng, X. Lai, and H. Yu, in Rump Session of Crypto’04 E-print, Santa Barbara, 2004. Google Scholar

[3] X. Wang, X. Lai, D. Feng, X. Yu, and X. Yu, in Proceedings of Eurocrypt’05, Aarhus, 2005. pp. 1-18. Google Scholar

[4] X. Wang, and H. Yu, in Proceedings of Eurocrypt’05, Aarhus, 2005. p. 19-35. Google Scholar

[5] Shen J., Liu D., Shen J., Liu Q., Sun X.. Pervasive Mobile Computing, 2017, 41: 219 CrossRef Google Scholar

[6] Fu Z., Ren K., Shu J., Sun X., Huang F.. IEEE Trans. Parallel. Distrib. Syst., 2016, 27: 2546 CrossRef Google Scholar

[7] Fu Z., Wu X., Guan C., Sun X., Ren K.. IEEE Trans. Inform. Foren. Secur., 2016, 11: 2706 CrossRef Google Scholar

[8] Fu Z., Huang F., Ren K., Weng J., Wang C.. IEEE Trans. Inform. Foren. Secur., 2017, 12: 1874 CrossRef Google Scholar

[9] P. W. Shor, in Proceedings of 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, 1994, pp. 124-134. Google Scholar

[10] L. K. Grover, in Proceedings of 28th Annual ACM Symposium on Theory of Computing, New York, 1996, pp. 212-218. Google Scholar

[11] C. H. Bennett, and G. Brassard, in Proceedings of IEEE International Conference on Computers, Systems and Signal, Bangalore, 1984, pp.175-179. Google Scholar

[12] Gisin N., Ribordy G., Tittel W., Zbinden H.. Rev. Mod. Phys., 2002, 74: 145 CrossRef ADS Google Scholar

[13] Buhrman H., Cleve R., Watrous J., de Wolf R.. Phys. Rev. Lett., 2001, 87: 167902 CrossRef PubMed ADS Google Scholar

[14] D. Gavinsky, and T. Ito, Quantum Fingerprints that Keep Secrets. Technical Report (Cornell University Library, 2010). Google Scholar

[15] Ablayev F. M., Vasiliev A. V.. Laser Phys. Lett., 2014, 11: 025202 CrossRef ADS Google Scholar

[16] Ablayev F., Ablayev M., Vasiliev A.. J. Phys.-Conf. Ser., 2016, 681: 012019 CrossRef ADS Google Scholar

[17] M. Ziatdinov. arXiv Google Scholar

[18] Ziatdinov M.. Lobachev. J. Math., 2016, 37: 705 CrossRef Google Scholar

[19] Vasiliev A.. Lobachev. J. Math., 2016, 37: 753 CrossRef Google Scholar

[20] D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, in Proceedings of the 33rd ACM Symposium on Theory of Computing, Crete, 2001, pp. 50-59. Google Scholar

[21] Ambainis A.. SIAM J. Comput., 2007, 37: 210 CrossRef Google Scholar

[22] Magniez F., Santha M., Szegedy M.. SIAM J. Comput., 2007, 37: 413 CrossRef Google Scholar

[23] Tamascelli D., Zanetti L.. J. Phys. A-Math. Theor., 2014, 47: 325302 CrossRef ADS arXiv Google Scholar

[24] Li D., Zhang J., Guo F. Z., Huang W., Wen Q. Y., Chen H.. Quantum Inf. Process., 2013, 12: 1501 CrossRef ADS Google Scholar

[25] Yang Y. G., Xu P., Yang R., Zhou Y. H., Shi W. M.. Sci. Rep., 2016, 6: 19788 CrossRef PubMed ADS Google Scholar

[26] D. Li, Y.-G. Yang, J.-L. Bi, J.-B. Yuan, and J. Xu. arXiv Google Scholar

[27] Xue P., Sanders B. C.. Phys. Rev. A, 2012, 85: 022307 CrossRef ADS arXiv Google Scholar

[28] ?tefaňák M., Barnett S. M., Kollár B., Kiss T., Jex I.. New J. Phys., 2011, 13: 033029 CrossRef ADS arXiv Google Scholar

[29] Lo H. K., Chau H. F.. Science, 1999, 283: 2050 CrossRef ADS Google Scholar

[30] Yang Y. G., Liu Z. C., Li J., Chen X. B., Zuo H. J., Zhou Y. H., Shi W. M.. Quantum Inf. Process., 2017, 16: 12 CrossRef ADS Google Scholar

[31] Yang Y. G., Lei H., Liu Z. C., Zhou Y. H., Shi W. M.. Quantum Inf. Process., 2016, 15: 2487 CrossRef ADS Google Scholar

[32] Wang T. Y., Wei Z. L.. Quantum Inf. Process., 2012, 11: 455 CrossRef Google Scholar

[33] Wang T. Y., Cai X. Q., Ren Y. L., Zhang R. L.. Sci. Rep., 2015, 5: 9231 CrossRef PubMed ADS Google Scholar

[34] Yang Y. G., Wen Q. Y.. J. Phys. A-Math. Theor., 2009, 42: 055305 CrossRef ADS Google Scholar

[35] Yang Y. G., Cao W. F., Wen Q. Y.. Phys. Scr., 2009, 80: 065002 CrossRef ADS Google Scholar

[36] Chen X. B., Xu G., Niu X. X., Wen Q. Y., Yang Y. X.. Opt. Commun., 2010, 283: 1561 CrossRef ADS Google Scholar

[37] He Y. F., Ma W. P.. Quantum Inf. Process., 2016, 15: 5023 CrossRef ADS Google Scholar

[38] Liu B., Gao F., Huang W., Wen Q.. Quantum Inf. Process., 2013, 12: 1797 CrossRef ADS Google Scholar

[39] Gao F., Liu B., Huang W., Wen Q. Y.. IEEE J. Sel. Top. Quantum Electron., 2015, 21: 98 CrossRef Google Scholar

[40] Wei C. Y., Wang T. Y., Gao F.. Phys. Rev. A, 2016, 93: 042318 CrossRef ADS Google Scholar

[41] Yang Y. G., Liu Z. C., Chen X. B., Zhou Y. H., Shi W. M.. Sci. China-Phys. Mech. Astron., 2017, 60: 120311 CrossRef Google Scholar

[42] Yang Y. G., Liu Z. C., Li J., Chen X. B., Zuo H. J., Zhou Y. H., Shi W. M.. Phys. Lett. A, 2016, 380: 4033 CrossRef ADS Google Scholar

Click to view Download high-quality image

Figure 1
Circuit representation of the unitary operation at the ith iteration in the first QHF. The top n lines are the quantum register for storing the information about the position. The two lower lines are the two-bit message $m_{2 i ? 1} m_{2 i}$ , and the other line is the quantum register for storing the information about the coin.
Click to view Download high-quality image

Figure 2
(Color online) Hash values of C1, C2, C3, C4, C5.
Click to view Download high-quality image

Figure 3
Circuit representation of the unitary operation at the ith iteration in the second QHF. The top n lines are the quantum register for storing the information about the position. The three lower lines are the three-bit message, and the other line is the quantum register for storing the information about the coin.
Click to view Download high-quality image

Figure 4
(Color online) Hash values of C1, C2, C3, C4, C5.

Table Results for diffusion and confusion tests in the first QHF

	N=1024	N=2048	N=10000	Mean
$\overset{ˉ}{B}$	38.8545	38.5542	38.5839	38.6642
$\overset{ˉ}{A}$	69.2021	69.2085	69.1016	69.1707
$\overset{ˉ}{T}$	108.0566	107.7627	107.6855	107.8349
P (%)	48.8944	48.7614	48.7265	48.7941
ΔT	6.9318	6.4671	6.4822	6.6270
ΔP	3.1366	2.9263	2.9331	2.9987

Table Results for diffusion and confusion tests in the second QHF

	N=1024	N=2048	N=10000	Mean
$\overset{ˉ}{B}$	41.4688	41.3569	42.5407	41.7888
$\overset{ˉ}{A}$	70.2764	70.1060	70.2384	70.2069
$\overset{ˉ}{T}$	111.7452	111.4629	112.7791	111.9957
P (%)	50.5634	50.4357	51.0313	50.6768
ΔT	7.8213	8.5069	8.2029	8.1770
ΔP	3.5391	3.8493	3.7117	3.7000

Table Comparison between our schemes and other QW-based QHFs in terms of collision resistance

No collision
One collision
Two collisions
More collisions
ref. [24]
7688
375
1662
275
ref. [25]
9367
617
16
0
ref. [26]
9068
889
42
1
Our first scheme
9914
86
0
0
Our second scheme
9854
71
0
75
Table Comparison between our schemes and other QW-based QHFs in terms of resource consumption. Here, $C_{2}$ , $C_{v}$ and $C_{w}$ are 2×2 coin operators, and $C_{4}$ is a 4×4 coin operator

The number of the particles
Quantum operation
The number of message bits
ref. [24]
2
$S_{x y} (I ? C_{2} ? C_{2})$
1
ref. [25]
2
$S_{x y} (I ? C_{4})$
1
ref. [26]
1
$S_{y} C_{2} S_{x} C_{2}$
1
Our first scheme
1
$S_{c} (I ? C_{v})$
2
Our second scheme
1
$S_{c} (I ? C_{w})$
3

2

Citations
0

Altmetric
Article metrics

Email
Export


03.67.Dd	Quantum cryptography and communication security
03.67.Hk	Quantum communication
03.67.Lx	Quantum computation architectures and implementation

Improving the efficiency of quantum hash function by dense coding of coin operators in discrete-time quantum walk

Abstract

Funded by

Acknowledgment

References

2

0

Interesting search

Top 5Related Articles

	No collision	One collision	Two collisions	More collisions
ref. [24]	7688	375	1662	275
ref. [25]	9367	617	16	0
ref. [26]	9068	889	42	1
Our first scheme	9914	86	0	0
Our second scheme	9854	71	0	75

	The number of the particles	Quantum operation	The number of message bits
ref. [24]	2	$S_{x y} (I ? C_{2} ? C_{2})$	1
ref. [25]	2	$S_{x y} (I ? C_{4})$	1
ref. [26]	1	$S_{y} C_{2} S_{x} C_{2}$	1
Our first scheme	1	$S_{c} (I ? C_{v})$	2
Our second scheme	1	$S_{c} (I ? C_{w})$	3