Quantum Collision-Resistance of Non-uniformly Distributed Functions

详细信息    查看全文

• 关键词：Quantum ; Collision ; Non ; uniform distribution ; Query complexity
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9606
• 期：1
• 页码：79-85
• 全文大小：183 KB
• 参考文献：[Amb00]Ambainis, A.: Quantum lower bounds by quantum arguments. In: Yao, F.F., Luks, E.M. (eds.) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21–23, Portland, OR, USA, pp. 636–643. ACM (2000)
  [Amb05]Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theor. Comput. 1(1), 37–46 (2005)CrossRef MathSciNet
  [Amb07]Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007)CrossRef MathSciNet MATH
  [AS04]Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595–605 (2004)CrossRef MathSciNet MATH
  [BHT97]Brassard, G., Høyer, P., Tapp, A.: Quantum algorithm for the collision problem. ACM SIGACT News (Cryptology Column) 28, 14–19 (1997)CrossRef
  [CW79]Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)CrossRef MathSciNet MATH
  [ETU15]Targhi, E.E., Unruh, D.: Quantum security of the Fujisaki-Okamoto transform (2015). http://​2015.​qcrypt.​net/​wp-content/​uploads/​2015/​09/​Poster10_​Ehsan-Ebrahimi.​pdf
  [FO99]Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999)CrossRef
  [HILL93]Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of a pseudo-random generator from any one-way function. SIAM J. Comput. 28, 12–24 (1993)
  [Yue14]Yuen, H.: A quantum lower bound for distinguishing random functions from random permutations. Quantum Inf. Comput. 14(13–14), 1089–1097 (2014)MathSciNet
  [Zha12]Zhandry, M.: How to construct quantum random functions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS , New Brunswick, NJ, USA, October 20–23, 2012, pp. 679–687. IEEE Computer Society (2012)
  [Zha15]Zhandry, M.: A note on the quantum collision and set equality problems. Quantum Inf. Comput. 15(7–8), 557–567 (2015)MathSciNet
  
• 作者单位：Ehsan Ebrahimi Targhi (14)
  Gelo Noel Tabia (14)
  Dominique Unruh (14)
  
  14. University of Tartu, Tartu, Estonia
  
• 丛书名：Post-Quantum Cryptography
• ISBN：978-3-319-29360-8
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a distribution with min-entropy k. We prove that \(\varOmega (2^{k/9})\) quantum queries are necessary to find a collision for function f. This is needed in some security proofs in the quantum random oracle model (e.g. Fujisaki-Okamoto transform).