Реферат: Изучается генерическая сложность проблемы дискретного логарифма в последовательностях Люка. Эта проблема была использована в 1990-е годы новозеландским криптографом П. Смитом для создания аналога классического протокола Диффи - Хеллмана, в котором возведение в степень по целому модулю заменяется на операцию сложения элементов последовательности Люка. Доказывается, что при условии трудноразрешимости проблемы дискретного логарифма в последовательностях Люка в худшем случае и Р = ВРР существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Таким образом, обосновано применение данной алгоритмической проблемы в криптографии с открытым ключом, где важна генерическая трудноразрешимость, то есть трудноразрешимость для почти всех входов. Для доказательства используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основным этапом этого метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково.

Библиографическая ссылка: Рыбалов А.Н.
О генерической сложности проблемы дискретного логарифма в последовательностях Люка
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. Т.66. С.116-122. DOI: 10.17223/20710410/66/10 WOS РИНЦ OpenAlex

Даты:

Опубликована в печати:	25 дек. 2024 г.
Опубликована online:	25 дек. 2024 г.

Идентификаторы БД:

Web of science:	WOS:001483917200010
РИНЦ:	75174935
OpenAlex:	W4405675502

Цитирование в БД: Пока нет цитирований

Альметрики: