Abstract Boneh et al. [6] proposed an identification protocol in Asiacrypt 2011 that is secure in the classical random oracle model but insecure in the quantum random oracle model. This paper finds that a constant parameter plays a significant role in the security of the protocol and the variation of this parameter changes the security greatly. Therefore, an improved identification protocol that replaces a variable with this constant parameter is introduced. This study indicates that, when the variable is chosen appropriately, the improved identification protocol is secure in both the classical and the quantum random oracle models. Finally, we find the secure lower bound for this variable.

References

[1] Aaronson S., Quantum Copy-Protection and Quantum Money, in Proceeding of 24th Annual IEEE Conference on Computational Complexity, Washington DC, pp. 229-242, 2009.

[2] Bellare M., Kilian J., and Rogaway P., The Security of Cipher Block Chaining Message Authentication Code, Journal of Computer and System Sciences, vol. 61, no. 3, pp. 362-399, 1994.

[3] Bennett C., Bernstein E., Brassard G., and Vazirani U., Strengths and Weaknesses of Quantum Computing, SIAM Journal in Computing, vol. 26, no. 5, pp. 1510-1523, 1997.

[4] Bernstein D., Cost Analysis of Hash Collisions: Will Quantum Computers Make SHARCS Obsolete?, in Proceeding of 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, pp. 105-116, 2009.

[5] Boneh D. and Zhandry M., Quantum-secure Message Authentication Codes, in Proceeding (10) (11) (12) 3 ln 2ls pr npr 3 ln 2ls pr npr 32l Q Qs p r np r ln 32QQs p r np r ln 32l Improved Identification Protocol in the Quantum Random 345 of 32nd International Conference on the Theory and Applications of Cryptographic Techniques, Athens, pp. 592-608, 2013.

[6] Boneh D., Dagdelen ., Fischlin M., Lehmann A., Schaffner C., and Zhandry M., Random Oracles in a Quantum World, in Proceeding of 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, pp. 41-69, 2011.

[7] Brassard G., and Salvail L., Quantum Merkle Puzzles, in Proceeding of 2nd International Conference on Quantum, Nano and Micro Technologies, Washington, pp. 76-79, 2008.

[8] Brassard G., H yer P., and Tapp A., Theoretical Informatics, Springer, 1998.

[9] Brassard G., H yer P., Kalach K., Kaplan M., Laplante S., and Salvail L., Advances in Cryptology-CRYPTO, Springer, 2011.

[10] Daoud E., Quantum Computing for Solving a System of Nonlinear Equations over GF(q), the International Arab Journal of Information and Technolgy, vol. 4, no. 3, pp. 201-205, 2007.

[11] Grover L., A Fast Quantum Mechanical Algorithm for Database Search, in Proceeding of 28th Annual Symposium on the Theory of Computing, New York, pp. 212-219, 1996.

[12] Grover L., Quantum Search on Structured Problems, in Proceeding of Quantum Computing and Quantum Communications, vol. 1509, London, pp. 126-139, 1998.

[13] Mitzenmacher M. and Upfal E., Probability and Computing Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

[14] Nielsen M. and Chuang I., Quantum Computation and Quantum Information, Cambridge University Press, 2000.

[15] Shor P., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, vol. 26, no. 5, pp. 1484-1509, 1997.

[16] Zhandry M., How to Construct Quantum Random Functions, in Proceeding of FOCS 12, New Brunswick, pp. 679-687, 2012.

[17] Zhandry M., Secure Identity-based Encryption in the Quantum Random Oracle Model, International Journal of Quantum Information, vol. 13, no. 4, pp. 758-775, 2012. Wen Gao is a PhD student in Xidian University. She received her BS in Electronic Information Engineering from Henan University of Technology, China in 2011 and she takes a successive postgraduate and doctoral program. Her research interests include lattice-based cryptography and quantum computation and quantum attack. Yupu Hu is a professor and PhD supervisor of the School of Tele- communications Engineering, Xidian University, China. He received his PhD in cryptography from Xidian University, China in 1999, and received his MS and BS in mathematics from Xidian University, China in 1987 and 1982, respectively. His main research interests include public key cryptography based on lattices and the analysis and application of fully homomorphic encryption schemes. Baocang Wang is a professor and PhD supervisor of the School of Tele-communications Engineering, Xidian University, China. He received his PhD in cryptography from Xidian University, China in 2006, and received his MS and BS in mathematics from Xidian University in 2004 and 2001, respectively. His main research interests include public-key cryptography and wireless network security. Jia Xie is a PhD student in Xidian University. She received her BS in Electronic Information Engineering from Henan University of Technology, China in June, 2011. Her research interests include lattice-based cryptography and quantum computation and quantum information.