Изучается генерическая сложность проблемы дискретного логарифма в последовательностях Люка. Эта проблема была использована в 1990-е годы новозеландским криптографом П. Смитом для создания аналога классического протокола Диффи - Хеллмана, в котором возведение в степень по целому модулю заменяется на операцию сложения элементов последовательности Люка. Доказывается, что при условии трудноразрешимости проблемы дискретного логарифма в последовательностях Люка в худшем случае и Р = ВРР существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Таким образом, обосновано применение данной алгоритмической проблемы в криптографии с открытым ключом, где важна генерическая трудноразрешимость, то есть трудноразрешимость для почти всех входов. Для доказательства используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основным этапом этого метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково.
Скачать электронную версию публикации
Загружен, раз: 5
- Title О генерической сложности проблемы дискретного логарифма в последовательностях Люка
- Headline О генерической сложности проблемы дискретного логарифма в последовательностях Люка
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 66
- Date:
- DOI 10.17223/20710410/66/10
Ключевые слова
генерическая сложность, последовательности Люка, дискретный логарифмАвторы
Ссылки
Smith Р. J. and Lennon М. J. J. LUC: a new public key system // Proc. IFIP/Sec'93. Toronto, Canada, 1993. P. 103-117.
Smith P. and Skinner C. A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms // LNCS. 1995. V.917. P.355-364.
Bleichenbacher D., Bosma W., and Lenstra A. Some remarks on Lucas-based cryptosystems // LNCS. 1995. V.963. P.386-396.
Kapovich L., Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P. 665-694.
Рыбалов A. H. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2(28). С. 54-58.
Рыбалов А. Н. О генерической сложности проблемы дискретного логарифма // Прикладная дискретная математика. 2016. УЗ (33). С. 93-97.
Рыбалов А. Н. О генерической сложности проблемы извлечения корня в группах вычетов // Прикладная дискретная математика. 2017. У 38. С. 95-100.
Impagliazzo R. and Wigderson A. р = ВРР unless Е has subexponential circuits: Derandomizing the XOR Lemma. Proc. 29th STOC. El Paso, ACM, 1997. P.220-229.
Rosser J. B. and Schoenfeld L. Approximate formulas for some functions of prime numbers // Illinois J. Math. 1962. V.6. No. 1. P.64-94.
О генерической сложности проблемы дискретного логарифма в последовательностях Люка | Прикладная дискретная математика. 2024. № 66. DOI: 10.17223/20710410/66/10
Скачать полнотекстовую версию
Загружен, раз: 125