Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

想像してみてください。あなたの手元には、小さな、バッテリー駆動のロボット（スマートセンサーやIoTデバイスのようなもの）の艦隊があります。これらは秘密のメッセージを送る必要があります。しかし、これらのロボットは非常に小さく、エネルギーも極めて乏しいため、重いバックパックを背負ったり、過酷なマラソンを走ったりすることはできません。彼らには、非常に安全でありながら、驚くほど軽く、高速な「鍵と錠前」のシステム（暗号技術）が必要です。

米国国立標準技術研究所（NIST）は、これら小さなロボットに最適な10種類の「錠前」を見つけるためのコンペティションを開催しました。彼らはこれらを現実の世界でテストしましたが、なぜ特定のアルゴリズムが紙の上での数値よりも速いのかを説明するための、統一された単一の数学的公式を持っていませんでした。

Najmul Hasan氏とPrashanth BusiReddyGari氏によるこの論文は、その空白を埋めるものです。彼らが何を行ったのかを、簡単に説明します。

1. 問題点：錠前の「重さ」を測ること

10個のファイナリストを、10種類の異なるバックパックだと考えてみてください。あるものは軽いフォーム素材で作られており、あるものは重いスチール製です。NISTはすでにスケールでそれらの重さを量っています（実証テスト）。しかし、著者たちは、中身を実際に詰め込むことなく、どれだけの荷物を入れたらバックパックがどれほど重くなるかを予測できる「レシピ」を書きたいと考えました。

彼らは「時間計算量」のマップを作ろうとしました。簡単に言えば、これは「メッセージが短い場合、その錠前はどれくらい速いのか？ メッセージが長くなると、どれくらい遅くなるのか？」を教えてくれる数式です。

2. 解決策：3段階の組み立てライン

著者たちは、10個のすべての暗号アルゴリズムを、工場の組み立てラインのように、3つのシンプルなステージに分解しました。

• ステージ1：初期化（セットアップ）： 何かを詰める前に、機械をセットアップする必要があります。キーと「nonce」（セッションごとの固有番号）を投入します。これには、メッセージの大きさに関わらず、一定の時間が必要です。これは車のエンジンを温めるようなもので、1マイル走るのも100マイル走るのも、かかる時間は同じです。
• ステージ2：データ処理（パッキング）： ここで、実際のメッセージと追加データが暗号化されます。これが重労働の部分です。ここにかかる時間は、データの量に完全に依存します。著者たちは、データのブロックごとに正確に何ステップ（数学的操作）が必要かを計算するための公式を作成しました。
• ステージ3：ファイナリゼーション（封印）： すべてを詰め終わったら、箱を封印し、改ざんされていないことを証明するためのセキュリティタグを取り付けます。これは、パッケージに最終的なステッカーを貼るような、もう一つの固定された作業です。

3. 結果：最も軽いのは誰か？

この3段階モデルを10個のファイナリストすべてに適用することで、著者たちは各アルゴリズムの「重さ」を記述する数式の「メニュー」（表Iに示されています）を作成しました。

彼らがこの新しい公式を用いて明らかにした興味深い発見は以下の通りです。

• 「単純な線形」のランナー： GIFT-COFB、Grain-128AEAD、ISAP のようなアルゴリズムは、一本の高速道路のようなものです。彼らの時間は、メッセージのサイズに完璧に連動して増大します。メッセージを2倍にすれば、時間も2倍になります。余計な「税金」や複雑な乗数は存在しません。GIFT-COFBは特にシンプルであり、大きなメッセージに対して非常に効率的です。
• 「ブロック」のランナー： TinyJambu や Romulus は、特定のサイズの箱しか受け付けないコンベアベルトのように機能します。メッセージが箱にぴったり収まらない場合、彼らは箱を満たすための「パディング（詰め物/空きスペース）」を追加しなければなりません。これは、特に小さなメッセージにおいて、わずかなオーバーヘッドを生じさせますが、非常に構造化されています。
• 「置換（パーミュテーション）」のランナー： NISTが最終的に選んだ ASCON や Xoodyak は、「シャッフル」の手法を使用しています。彼らはデータを取得し、特定のパターンで混ぜ合わせます。彼らの公式は、時間が主にデータをどれくらいの回数シャッフルする必要があるかによって決まることを示しており、非常に効率的です。
• 「ハイブリッド」のランナー： ISAP は異なるテクニックの混合です。セッションごとに一時的なキーを作成するため、わずかなセットアップ時間が加わりますが、これにより特定のハッキングに対して非常に強固になります。

4. なぜこれが重要なのか

この論文は単に「アルゴリズムAの方が速い」と言っているだけではありません。設計の背後にある数学を見ることで、その「理由」を説明しています。

• 設計の選択： 著者らは、アルゴリズムの「形」がその速度を決定することを示しています。あるものは単一車線の道路（ストリーム暗号）のように作られており、他のものは料金所のある多車線ハイウェイ（ブロック暗号）のように作られています。
• 予測可能性： これにより、これらの小さなデバイスを設計するエンジニアは、デバイスを製造する前に、アルゴリズムがどれだけのバッテリーを消費するかを正確に予測できるようになります。

結論

この論文は、暗号性能の**ユニバーサル・トランスレーター（普遍的な翻訳機）**を提供します。延々とテストを繰り返したり推測したりする代わりに、エンジニアはこれらの記号的な公式を使用して、自分の特定のロボットに最適な「錠前」を選ぶことができます。

• もし、巨大なメッセージに対して絶対的に最もシンプルで軽い経路が必要なら、数学は GIFT-COFB を指し示しています。
• もし、一般的な用途としてセキュリティと速度のバランスが必要なら、数学は ASCON を際立たせています。
• もし、フルブロックを待つことなくビット単位でデータを処理する必要があるなら、Grain-128AEAD が明確な選択肢となります。

著者らは、これらの理論的な「重さ」を理解することで、私たちの小さなデバイスがバッテリー切れを起こすことなく安全に保たれるよう、モノのインターネット（IoT）をより確実に保護できると結論付けています。彼らは、この数学が現実の世界でも通用するかどうかを確認するために、デジタルIDカードのような実世界のシナリオでこれらの公式をテストする予定です。