Right Divisibility in Erasing Semi-Thue Systems: A Minimal View of Intruder Deduction

あなたは、特定の金庫を泥棒が開けられるかどうかを見極めようとしている熟練の鍵職人であると想像してください。デジタルセキュリティの世界では、メッセージは「ロックされた箱」のようなものです。そして、「泥棒（あるいは侵入者）」は、2つの箱をジップして結合したり、鍵でロックしたり、あるいはハッシュ化して指紋を作ったりといった、一連の操作ツールを持っています。大きな疑問は、「泥棒がすでに盗み出した箱があるとき、彼らはそれらのツールだけを使って、新しい特定の箱（例えば秘密の鍵）を作り出すことができるのか？」ということです。これは**侵入者推論問題（intruder deduction problem）**と呼ばれます。

この問題を解決するために、科学者たちはしばしば、これらの複雑な箱を単なる文字の列として扱います。形などの装飾的な要素をすべて取り除き、文字の順序だけに注目すると、この問題は言葉のパズルのゲームになります。あなたは開始となる単語と目標となる単語を持っており、単語の一部を切り取ったり並べ替えたりするというルールがリストされています。問いはこうです。「私は、開始の単語から目標の単語へと、切り貼りしながら辿り着けるだろうか？」この論文は、このゲームの非常に特殊で簡略化されたバージョンを深く掘り下げ、どの種類のルールがパズルを解ける状態にし、どのルールが答えを知ることを永遠に不可能にするのかを明らかにしています。

---

大いなる言葉のゲーム：切り取り、貼り付け、そして論理の限界

この論文において、著者である Raja O. P. Damanik と Alwen Tiu は、暗号メッセージの複雑な3D形状を見るのをやめ、代わりにそれらを単純な**「単語」**として見ることに決めました。すべてのメッセージが、ネックレスに連なったビーズの長い列であると考えてください。「ルール」とは、侵入者が従う魔法のハサミのようなものです。そのハサミは、ネックレスの「前」の部分を切り取ることはできますが、「真ん中」を切り取ることはできません。

著者たちはシンプルな問いを投げかけます。「もし私がネックレス ABC を持っていて、それを Z に変えたいとしたら、前方にビーズを付け足してから、前方の部分を切り取ることでそれは可能だろうか？」これは**右除算問題（right-divisibility problem）**と呼ばれます。これは簡単そうに聞こえますが、論理学の世界では地雷原です。ルールがあまりにトリッキーな場合、どんなに高速なコンピュータであっても、答えが「はい」か「いいえ」かを決して判断できないことがあります。この論文は、どのような種類のハサミ（ルール）がゲームを解けるものにし、どのようなものがゲームを完全に壊してしまうのかを示す地図なのです。

「接頭辞消去」のハサミ：イージーモード

まず、著者たちは**接頭辞消去（prefix-erasing）と呼ばれる特定の種類のルールに注目します。例えば、「もし単語の先頭に 'BA' という文字があれば、それを取り除け！」というルールを想像してください。つまり、BA-RED は RED になります。もしこれらのルールが「収束的（convergent）」（つまり、どの順番でハサミを適用しても、常に同じ最終的な単語に辿り着くこと）であれば、著者たちは素晴らしいことを証明しました。「あなたはパズルを解くことができる」**のです。

彼らは単に可能だと言っただけでなく、超高速のアルゴリズムを構築しました。2つの単語を与えれば、彼らの手法は、一瞬のうちに（具体的には、単語の長さに比例する時間で）、一方が他方に変換可能かどうかを判定できます。それは、特定のカットのシーケンスが機能するかどうかを即座に教えてくれる魔法の杖を持っているようなものです。これは、これらの「前方を切り取る」ルールについては、侵入者の推論問題が安全であり、解決可能であることを裏付けています。

「接尾辞消去」のハサミ：トリッキーモード

次に、彼らは立場を逆転させます。もしハサミが単語の「後ろ」の部分しか切り取れないとしたらどうでしょう？これは**接尾辞消去（suffix-erasing）**と呼ばれます。例えば、「単語が 'ED' で終わるなら、それを切り取れ！」というルールを想像してください。つまり、RED は R になります。

ここでは、ゲームは格段に難しくなります。著者たちは、このパズルを解くことは依然として可能であるものの、前方の切り取りバージョンほど簡単ではないことを示しています。彼らが見つけた手法は、出口から後ろ向きに歩いて迷路を解こうとするようなものです。多くの可能な経路を探索しなければならず、最悪の場合、経路の数は指数関数的に増大します（雪崩が丘を転がり落ちて巨大化していくように）。しかし、良いニュースは、これは解決可能であるということです。論文は、これらの「後方を切り取る」ルールについては、たとえ計算力が必要になったとしても、答えを導き出す方法が必ず存在することを証明しています。

「同時変数リフティング」の罠：ゲームオーバー

しかし、そこで著者たちはひねりを加えます。もし侵入者が超強力なツールを持っていたらどうでしょう？例えば、「ある単語を取り、その中間部分を切り取るが、前後部分は保持する。そして、これを2つの異なる箇所で同時に行う」というルールを想像してください。これは**同時変数リフティング（simultaneous variable-lifting）**と呼ばれます。

これは小さな変更のように聞こえますが、ゲームを完全に破壊します。著者たちは、もしこれらの同時切り取りルールを許可すると、問題が**決定不能（undecidable）**になることを証明しました。これは重大なことです。これは、この特定のタイプのルールについては、答えを保証できるアルゴリズムが存在しないことを意味します。どれほど多くの時間をコンピュータに与えたとしても、侵入者が目標の単語を構築できるかどうかを知ることなく、計算が永遠に続いてしまう可能性があるのです。

これを証明するために、彼らは単に推測したのではなく、この言葉のパズルを解くことが、**MPCP（Modified Post Correspondence Problem）**と呼ばれる有名な不可能問題の解決と全く同じであることを示しました。数学者はすでにMPCPが解決不可能であることを知っているため、彼らはこのバージョンの侵入者推論問題もまた不可能であることを証明したのです。

なぜこれが重要なのか

「単語を切り取ることが、一体誰の役に立つのか？」と思うかもしれません。答えは、「暗号を利用するすべての人」です。現実世界のセキュリティプロトコルは、こうした言葉のゲームのような複雑な数学を使用しています。問題をその骨組み（単なる単語と単純な切り取り）まで削ぎ落とすことで、著者たちは「解決可能」と「不可能」の間の正確な境界線を見つけ出しました。

彼らは、もしセキュリティルールが単純な前方切り取りや後方切り取りのハサミのようなものであれば、ハッカーが侵入できるかどうかを自動的にチェックするツールを構築できることを示しました。しかし、もしルールが複雑になりすぎ（複数の場所で同時に切り取りを行うなど）、あまりに混沌としたものになれば、現在のツールでは太刀打ちできない壁に突き当たることを示しました。これは、セキュリティの専門家に対し、どのような種類の暗号システムが自動分析に適しており、どのシステムが現在のツールでは扱いきれないほど複雑すぎるのかを知るための助けとなります。

要するに、この論文は論理の境界に関するガイドブックです。それは、私たちが多くの侵入者のパズルを解くことができる一方で、答えを知ることがどうしてもできない特定の複雑さが存在することを教えてくれます。そして、その境界線がどこにあるのかを知ることこそが、より安全なデジタルロックを構築するための第一歩なのです。