Складність задачі про приховану дію абелевої групи в квантовій моделі обчислень

Автор(и)

  • Андрій В’ячеславович Фесенко Національний технічний університет України "КПІ", Україна

DOI:

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

Ключові слова:

квантова модель обчислень, задача про прихований зсув, одностороння функція

Анотація

Представлено алгебраїчну задачу про приховану дію абелевої групи, до якої зводяться питання стійкості використання локально комутативних відображень в якості криптографічних односторонніх функцій. Показано зведення цієї задачі до відомої в квантовій моделі обчислень задачі про прихований зсув, що дозволяє використовувати вже відомі часткові розв’язки навіть при відсутності ефективного загального методу рішення.

Біографія автора

Андрій В’ячеславович Фесенко, Національний технічний університет України "КПІ"

Асистент

Кафедра математичних методів захисту інформації

Посилання

  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.

##submission.downloads##

Опубліковано

2013-10-29

Як цитувати

Фесенко, А. В. (2013). Складність задачі про приховану дію абелевої групи в квантовій моделі обчислень. Eastern-European Journal of Enterprise Technologies, 5(4(65), 45–49. https://doi.org/10.15587/1729-4061.2013.18345

Номер

Том 5 № 4(65) (2013): Математика та кібернетика - прикладні аспекті

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

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

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.