巡回セールスマン暗号の安全性についての検討

摘要

巡回セールスマン暗号は，NP完全問題の一つである巡回セールス問題を暗号のアルゴリズ本に応用した公開鍵暗号である．この暗号の特色は公開鍵ベクトルの密度が1以上にすることが出来るためにLagarias-Odlyzko法による低密度攻撃での解読が難しいと考えられている事である．しかし，本当にこの巡回セールスマン暗号は解読することは出来ないのか，本当に安全なのかと言うことを調べるためLagarias-Odlyzko法やその変形型，また都市数を変えながら解読を計算機実験し暗号の解読率を求めた．この計算機実験で得られた解読率を基に巡回セールスマン暗号の安全性について数値的に検討を行う．