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

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

Dates:

Submitted:	Jun 1, 2026
Accepted:	Jul 20, 2026
Published print:	Sep 1, 2026
Published online:	Sep 1, 2026

Identifiers: No identifiers

Altmetrics: