О генерической сложности проблемы дискретного логарифма в последовательностях Люка

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