Complexity of hidden abelian group action problem in quantum computing

Authors

  • Андрій В’ячеславович Фесенко National Technical University of Ukraine “Kyiv Polytechnic Institute” Peremogy 37, Kiev, Ukraine, 03056, Ukraine

DOI:

https://doi.org/10.15587/1729-4061.2013.18345

Keywords:

quantum computation model, hidden shift problem, one-way function

Abstract

The paper first examines the Hidden Abelian Group Action problem’s complexity in quantum computing model. This algebraic problem is fundamental in determining the hardness of a one-way function constructed on the basis of commutative and locally commutative maps and ciphers. In fact, finding new one-way functions that will be resistant in quantum computing model is very important for modern cryptography. The main objective of the study is to assess the complexity of the Hidden Abelian Group Action problem by using a reduction to already known problems, such as the Hidden Subgroup problem and the Hidden Shift problem. In this paper, reduction of the Hidden Abelian Group Action problem to the Hidden Shift problem was first shown, and limitations that distinguish them were first demonstrated. As a result, on the one hand, the existing partial solutions to the Hidden Shift problem, and general Kuperberg’s subexponential algorithm can be extended to the case of the Hidden Abelian Group Action problem. Moreover, more limitations give more chances to effective general solution to this problem. On the other hand, the reduction and similarity to a known challenge in quantum computing model also indicate the complexity of the Hidden Abelian Group Action problem, which leaves a chance for making a real stand one-way function in quantum computing model based on a locally commutative mapping.

Author Biography

Андрій В’ячеславович Фесенко, National Technical University of Ukraine “Kyiv Polytechnic Institute” Peremogy 37, Kiev, Ukraine, 03056

Assistant

Department of Mathematical Information security methods

Institute of Physics and Technology

References

  1. Shor, P. W. Algorithms For Quantum Computation: Discrete Logs and Factoring [Текст] / P. W. Shor // Proceedings of the 35th Symposium on the Foundations of Computer Science. - 1994. - C. 124-134.
  2. Nielsen, M. A. Quantum Computation and Quantum Information [Текст] / M. A. Nielsen, I. L. Chuang - Cambridge University Press, Cambridge, 2000. - 702 C. - ISBN 978-1107002173.
  3. Aaronson, S. NP-complete problems and physical reality [Текст] / S. Aaronson // ACM SIGACT News. - 2005. - T. 36(1). - C. 30-52.
  4. Kitaev, A. Quantum measurements and the Abelian stabiliser problem [Електронний ресурс] / A. Yu Kitaev // Режим доступа : WWW/ URL: http://arxiv.org/abs/quant-ph/9511026, 1995.
  5. van Dam, W. Quantum algorithms for some hidden shift problems [Текст] / W. van Dam, S. Hallgren, L. Ip // In: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms. - 2003. - C. 489-498.
  6. Gavinsky, D. Quantum algorithm for the Boolean hidden shift problem [Текст] / D. Gavinsky, M. Roetteler, J. Roland // Proceedings of the 17th annual international conference on Computing and combinatorics. - 2011. - C. 158-167.
  7. Kuperberg, G. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem [Текст] / G. Kuperberg // SIAM Journal on Computing. - 2005. - T. 35(№1). - C. 170-188.
  8. Regev, O. A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space [Електронний ресурс] / O. Regev // Режим доступа : WWW/ URL: http://arxiv.org/abs/quant-ph/0406151, 2004.
  9. Regev, O. On the complexity of lattice problems with polynomial approximation factors [Текст] / O. Regev // In Phong Q. Nguyen and Brigitte Valle, editors, The LLL Algorithm, Information Security and Cryptography. - 2010. - C. 475-496.
  10. Childs, A. M. Constructing elliptic curve isogenies in quantum subexponential time [Електронний ресурс] / A. M. Childs, D. Jao, V. Soukharev // Режим доступа : WWW/ URL: http://arxiv.org/abs/1012.4019, 2010.
  11. Савчук, М. М. Симетричні комутативні та локально комутативні шифри для побудови класичних та постквантових криптографічних протоколів [Текст] / М. М. Савчук, А. В. Фесенко // Інформаційні технології та комп’ютерна інженерія. - 2008. - T. №2(12). - С. 43-51.
  12. Shor, P. W. (1994). Algorithms For Quantum Computation: Discrete Logs and Factoring Proceedings of the 35th Symposium on the Foundations of Computer Science, 124-134.
  13. Nielsen, M. A., Chuang I. L. (2000). Quantum Computation and Quantum Information Cambridge University Press, Cambridge, 702, ISBN 978-1107002173.
  14. Aaronson, S. (2005). NP-complete problems and physical reality ACM SIGACT News, 36(1), 30-52.
  15. Kitaev, A. (1995). Quantum measurements and the Abelian stabiliser problem, http://arxiv.org/abs/quant-ph/9511026.
  16. van Dam, W., Hallgren S., Ip L. (2003). Quantum algorithms for some hidden shift problems In: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms, 489-498.
  17. Gavinsky, D., Roetteler M., Roland J. (2011). Quantum algorithm for the Boolean hidden shift problem Proceedings of the 17th annual international conference on Computing and combinatorics, 158-167.
  18. Kuperberg, G. (2005). A subexponential-time quantum algorithm for the dihedral hidden subgroup problem SIAM Journal on Computing, 35(№1), 170-188.
  19. Regev, O. (2004). A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space, http://arxiv.org/abs/quant-ph/0406151.
  20. Regev, O. (2010). On the complexity of lattice problems with polynomial approximation factors In Phong Q. Nguyen and Brigitte Valle, editors, The LLL Algorithm, Information Security and Cryptography, 475-496.
  21. Childs, A. M., Jao D., Soukharev V. (2010). Constructing elliptic curve isogenies in quantum subexponential time, http://arxiv.org/abs/1012.4019.
  22. Savchuk, М., Fesenko А. (2008). Using Symmetric Commutative and Locally Commutative Ciphers to Construct Classical and Post-Quantum Cryptographic Protocols Information Technology and Computer Engineering, №2(12), 43-51.

Downloads

Published

2013-10-29

How to Cite

Фесенко, А. В. (2013). Complexity of hidden abelian group action problem in quantum computing. Eastern-European Journal of Enterprise Technologies, 5(4(65), 45–49. https://doi.org/10.15587/1729-4061.2013.18345

Issue

Vol. 5 No. 4(65) (2013): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2014 Андрій В’ячеславович Фесенко

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.