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

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

Dates:

Published print:	Dec 25, 2024
Published online:	Dec 25, 2024

Identifiers:

Web of science:	WOS:001483917200010
Elibrary:	75174935
OpenAlex:	W4405675502

Citing: Пока нет цитирований

Altmetrics: