О криптосистеме паросочетаний и задаче о чередующемся взвешенном пути

В докладе будет представлена новая система шифрования с открытым ключом рюкзачного типа — система Болотникова-Ирматова (криптосистема паросочетаний). В основе устойчивости системы лежит NP-полнота задачи о чередующемся взвешенном пути. В рамках доклада будет сформулирована задача о чередующемся взвешенном пути, и будет представлена конструкция, с помощью которой была доказана её NP-полнота.
Поскольку задачи о чередующемся взвешенном пути, которые можно решить за полиномиальное время, являются важной частью скрытого ключа построенной системы шифрования, то возникает проблема конструктивного описания подмножества таких задач. В докладе будет приведен один пример такого подмножества.
Идентификатор: 832 7188 7890 Код: 991937