Рассматривается схема построения возможно односторонней функции в группес разрешимой проблемой равенства и неразрешимой проблемой эндоморфной сводимости. Анализируются предпосылки криптографической стойкости предлагаемой схемы. В качестве приложения предлагается схема аутентификации с нулевым разглашением пользователей в системе. Отмечается, что для её криптостойкости требуется неразрешимость более сильной проблемы двукратной эндоморфной сводимости.
Скачать электронную версию публикации
Загружен, раз: 82
- Title О построении возможно одностороннихфункций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах
- Headline О построении возможно одностороннихфункций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(17)
- Date:
- DOI
Ключевые слова
протокол проверки подлинности, проблема эндоморфизма, односторонняя функция, authentication protocol, endomorphism problem, one-way functionАвторы
Ссылки
Ерофеев С. Ю. Схемы построения двушагово односторонних функций / / Вестник Омского университета. 2011. №4. С. 15-18.
Grigoriev D. and Shpilrain V. Zero-knowledge autentification schemes from actions on graphs, groups and rings / / Ann. Pure Appl. Logic. 2010. V. 162. P. 194-200.
Рыбалов А. Н. О генерической неразрешимости десятой проблемы Гильберта / / Вестник Омского университета. 2011. №4. С. 19-22.
Kapovich I., Myasnikov A., Shupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks / / J. Algebra. 2003. V. 264. P. 665-694.
Segal D. Words: notes on verbal width in groups / / London Math. Soc. Lect. Notes. Cambridge: Cambridge Univ. Press, 2009. V. 361. 215 p.
Холл М. Теория групп. М.: ИЛ, 1962. 467 с.
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Лань, 2009. 288 с.
Курош А. Г. Теория групп. М.: Физматгиз, 2008. 808 с.
Hall P. Nilpotent groups / / Canad. Math. Cong. Summer Sem. Vankuver: University of Alberta, 1957. P. 12-30.
Jones J. Universal diophantine equation / / J. Symbolic Logic. 1982. V. 47. No. 3. P. 549-571.
Нейман Х. Многообразия групп. М.: Мир, 1974. 264 с.
Маканин Г. С. Уравнения в свободной группе / / Изв. АН СССР. Сер. матем. 1982. T. 46. №6. C. 1199-1273.
Matijasevich Y. V. Some purely mathematical results inspired by mathematical logic / / Proc. Fifth Intern. Congr. Logic, Methodology and Philos. of Sci.(London, Ont.). Dordrecht, Reidel, Holland. 1977. P. 121-127.
Matijasevich Y. V. and Robinson J. Reduction of an arbitrary diophantine equation to one in 13 unknowns / / Acta Arithmetica. 1975. V.27. P. 521-553.
Романьков В. А. Введение в криптографию. Курс лекций. М.: Форум, 2012. 240 с.
Menezes A. J., van Oorschot P. C., and Vanstone S. A. Handbook of Applied Cryptography. CRC Press, 1996. 816 p.
Ерофеев С. Ю. Диофантовость дискретного логарифма / / Вестник Омского университета. 2010. №4. С. 13-15.
Ерофеев С. Ю. Диофантовость дискретного логарифма / / Прикладная дискретная математика. Приложение. 2011. №4. С. 31-32.
Scheimer S. Polynomial-time word problems / / Comment. Math. Helv. 2008. V. 83. No. 4. P. 741-765.
Lohrey M. and Schleimer S. Efficient computation in groups via compression / / LNCS. 2007. V. 4649. P. 249-258.
Lohrey M. Word problems on compressed words / / Automata, Languages and Programming. LNCS. 2004. V. 3142. P. 906-918.
Birget J.-C., Magliveras S., and Sramka M. On public-key cryptosystems based on combinatorial group theory / / Tatra Mount. Math. Publ. 2006. V.33. P. 137-148.
Kurt Y. A new key exchange primitive based on the triple decomposition problem / / Preprint: http://eprint.iacr.org/2006/378
Shpilrain V. and Zapata G. Combinatorial group theory and public key cryptography // Applicab. Alg. Eng. Comm. Comp. 2006. V. 17. P. 291-302.
Shpilrain V. and Zapata G. Using the subgroup membership problem in public key cryptography / / Contemp. Math. V. 418. Providence, RI: Amer. Math. Soc., 2006. P. 169-179.
Shpilrain V. and Zapata G. Using decision problems in public key cryptography / / Groups. Complexity. Cryptology. 2009. V. 1. P. 33-40.
Матиясевич Ю. В. Десятая проблема Гильберта. М.: Наука, 1993. 223 с.
Матиясевич Ю. В. Диофантово представление перечислимых предикатов / / Изв. АН СССР. Сер. матем. 1971. №35. С. 3-30.
Матиясевич Ю. В. Диофантовость перечислимых множеств / / Докл. АН СССР. 1970. Т. 191. №2. С. 279-282.
Романьков В. А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах / / Алгебра и логика. 1977. Т. 16. №4. С.457-471.
Романьков В. А. Об уравнениях в свободных метабелевых группах / / Сибирский математический журнал. 1979. T.20. №3. С. 671-673.
Кожевников А. А., Николенко С. И. О полных односторонних функциях / / Проблемы передачи информации. 2009. T.45. №2. C. 101-118.
Sipser M. Introduction to the theory of computation. PWS Publishing, 1997. 416 p.
Levin L. A. One-way Functions and Pseudorandom Generators / / Combinatorica. 1987. V. 7. No. 4. P. 357-363.
Левин Л. А. Односторонние функции / / Проблемы передачи информации. 2003. T. 39. №1. C. 103-117.
Goldwasser S. and Bellare M. Lecture Notes on Cryptography. Cambridge: MIT, 2008.
Goldreich O. Foundations of cryptography. Cambridge: Cambridge Univ. Press, 2001. V. 1. 451 p.; 2004. V.2. 798 p.
Романьков В. А. Диофантова криптография на бесконечных группах / / Прикладная дискретная математика. 2012. №2. С. 15-42.
Myasnikov A., Shpilrain V., and Ushakov A. Non-commutative cryptography and complexity of group-theoretic problems. (Amer. Math. Soc. Surveys and Monographs). Providence, RI: Amer. Math. Soc., 2011. 385 p.
Myasnikov A., Shpilrain V., and Ushakov A. Group-based cryptography. (Advances courses in Math., CRM, Barselona). Basel, Berlin, New York: Birkhauser Verlag, 2008. 183 p.
О построении возможно одностороннихфункций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах | Прикладная дискретная математика. 2012. № 3(17).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 248