ガウス整数を用いた巡回セールスマン暗号

摘要

NP完全問題の一つである巡回セールスマン問題を公開鍵暗号に応用し，各都市間の経路長たガウス整数を用いた場合についで検討する．セールスマンの辿った経路を平文とし，暗号文は各経路長の積と和の混合演算で定める．暗号文の生成に積と和の2つの演算を用いるのは，線形暗号に対する強力な解読法であるLLLアルゴリズムを適用できなくするためであり，経路長にガウス整数を用いるのは，公開鍵から秘密鍵を求めるShamirアルゴリズムに耐性を持たせるためである．