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

Библиографическая ссылка: Рыбалов А.Н.
Генерический анализ проблемы рюкзака в криптосистеме Шора-Ривеста
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2026. №73. С.113-119. DOI: 10.17223/20710410/73/7

Даты:

Поступила в редакцию:	1 июн. 2026 г.
Принята к публикации:	20 июл. 2026 г.
Опубликована в печати:	1 сент. 2026 г.
Опубликована online:	1 сент. 2026 г.

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

Альметрики: