セキュリティパラメータを1進法で渡す理由

2025年9月6日

よくある誤解

❓「セキュリティパラメータが128なら、128と渡せばよくない？」と思われがちです。
実は、理論の世界では「その渡し方」が問題になるのです。

セキュリティパラメータとは？

セキュリティパラメータk（あるいはλ）とは、暗号アルゴリズムにおける「安全性の強さ」を調整するための整数です。

たとえば

• 「k=128」ならば、128ビットのセキュリティ（一般的な現代暗号の標準）
• 「k=256」ならば、より高いセキュリティ（すなわち量子コンピューターの存在を仮定しても安全にするために使用）

kの役割は2つある

• 役割①：安全性の指標
  • 鍵長・ブロック長・乱数のサイズなどがkに応じて決定される。
• 役割②：計算量の尺度
  • アルゴリズムが「kに対してどの程度の時間・空間で動作するか」を分析する基準になる。

入力サイズとは？

コンピューターに何か仕事（問題解決）をさせるとき、入力が必要です。

たとえば、以下が挙げられます。

• 整数を並べたリスト
• 暗号化したいメッセージ
• グラフ構造のデータ

これらをビット列に変換したときの「長さ」が、入力サイズnです。

つまり、コンピューターに渡された情報の量（ビット数や要素数）がnになります。

実行時間の増え方

入力サイズが大きくなればなるほど、処理にかかる時間も増えます。

このとき、「どのくらい速く・遅くなるか」を数式で表すのが時間計算量（Time Complexity）です。

多項式時間（Polynomial Time）とは？

これは、入力サイズnに対して、処理時間がn^c（たとえばn², n³, n⁵など）で増えるという意味です。

たとえば

• O(n)：リストの長さに比例（非常に速い）
• O(n²)：リストの全組み合わせを調べる（中くらい）
• O(n¹⁰)：あまりに遅いが、それでも「多項式」には入る

これらはすべて多項式時間（Polynomial Time）と呼ばれます。P時間と表記されることもあります。

計算量理論では、「現実的に計算可能な処理時間」とみなされるのがこのクラス（＝多項式時間）です。

入力サイズnに対して、実行時間が O(n^c) のように多項式で増えるなら多項式時間（効率的）とみなす。

このときの「入力サイズn」とは、アルゴリズムに渡されるビット列の長さを意味します。

対して、指数時間（Exponential Time）とは？

これは、入力サイズnに対して、処理時間が2ⁿ, 3ⁿ, n!など急激に増えるということです。

例：

• n=10のとき⇒2¹⁰ =1,024
• n=50のとき⇒2⁵⁰≒1京（非常に大きい！）

指数時間のアルゴリズムは、現実のコンピューターではすぐ限界を迎えるため、「非効率（実用的ではない）」と評価されます。

計算量理論では入力サイズが重要になる

計算量理論（理論計算機科学）の世界でアルゴリズムの効率を語るとき、単に「速い・遅い」でなく、「入力の大きさに対してどれくらい時間がかかるか？」で判断するのが計算量理論です。

特に、入力サイズ nに対して処理時間がn²やn³のように増えるなら、それは「多項式時間」（＝効率的）とみなされます。

kを数値で渡すと、理論上おかしくなる

アルゴリズムにkという数値を渡したとき、入力サイズはlog(k)しかありません。

たとえば、セキュリティパラメータk=128を普通に2進数で渡すと、8ビットの1000 0000bになります。

このとき、アルゴリズムが「kに対してO(k²) の時間」で動いたとしても、計算量理論的には「8ビットの入力に対して16,000 ステップかかっている」と見なされ、指数時間アルゴリズムと誤解されることになります。

【解決法】1^k（1が k 個並んだビット列）として渡す

この誤解を避けるために使われるのが、1進法による入力です。

先ほどの例でいえば、k=128なので1^k=1¹²⁸=111…1（1が128個）として渡します。

このとき入力サイズは明確に128ビットになります。

アルゴリズムがO(k²)で動作するなら、これは「入力サイズに対して多項式時間」なので理論的にもOKです。

【初学者向け解説】「荷物を持って階段を登る」というたとえ話で理解する

想像してください。あなたが階段を登る仕事をしているとします。

• 荷物の重さ：セキュリティパラメータk
• 渡されるメモ：「この荷物は128kgです」とだけ書かれている（2進数で渡された場合）
  • でも見た目には、そのメモはたった8文字くらいの小さな紙切れ

アルゴリズム（＝あなた）は、「紙のサイズ＝情報の大きさ（入力サイズ）」しか見ていないとすると、「これだけ小さい紙なら、登るのにそんな時間かからないでしょ？」と判断してしまいます。

ところが、実際には荷物は128kgの重さがあります！

だから、登るにはそれなりに時間も力も必要です。

一方で、「1kgのレンガを128個持ってきたよ」と言えばどうでしょう？

この場合、荷物の見た目（＝入力の長さ）は明らかに128個分になります。アルゴリズムもそれを見て、「なるほど、これなら時間がかかって当然だね」と納得してくれます。

まとめるとこうなります（セキュリティパラメータk=128の場合）。

数値で渡す	入力長=8ビット（2進数の「1000 0000b」）	👎 計算量評価で不利
1進法で渡す	入力長=128ビット（1を128個）	✅ 正しく評価される

以上のように、「数値として短く伝えた情報」と「内容の重さや意味」のギャップがあると、アルゴリズムの計算時間を誤って評価してしまうのです。それを避けるために、セキュリティパラメータkは「1をk個並べる」という形で渡されるのです。

チューリングマシンと、その入力サイズ

チューリングマシンでは、入力は1本のテープ上に書かれたビット列で与えられます。

• たとえば、入力xが1000 0000b（8ビット）なら、チューリングマシンはそれを「8ビットの入力」として処理します。
• アルゴリズムの実行時間は、このビット列の長さnに対する関数O(f(n))として定義されます。

以下が重要になります。

✔️ 「値」ではなく、「ビット長」でしか入力の大きさを評価できない。
チューリングマシンは、入力が「128」なのか「8ビットの何か」なのか、見た目（長さ）でしか判断しません。

鍵生成アルゴリズム以外では1進数で渡す必要がない理由

鍵生成アルゴリズム以外（たとえば暗号化・復号・検証など）においては、セキュリティパラメータを1進法で渡す必要はありません。

なぜ鍵生成アルゴリズムだけが特別か？

鍵生成アルゴリズムにおいて2進法が使われるのは、「入力サイズとセキュリティパラメータkを一致させるため」です。

これはこれまでの説明通り、「アルゴリズムの実行時間をkに対して多項式時間として評価したい」という理論的な目的があるからです。

そのためには、「入力サイズ=k」に見せる必要があります。

そのため、1^kのような「長さkのビット列」を渡すわけです。

これにより、形式的に「多項式時間アルゴリズム」と認められるのです。

暗号化・復号アルゴリズムでは1進法が不要な理由

一方で、暗号化アルゴリズムや復号アルゴリズムにkを1進法で渡さなくてもよいのは、1進法でわざわざkを渡さなくても、入力サイズはすでにk相当であるからです。

これらのアルゴリズムはすでに鍵（pkやsk）を受け取っており、そのビット長がkに相当します。

したがって、アルゴリズムの入力サイズは自然にkに比例しています。

[例]「鍵長が2,048ビットのRSA公開鍵pkを渡す」⇒「pk自体がすでに2,046ビットある」

それを使って暗号化しても、入力サイズのオーダーはO(k)なので、時間計算量の評価に問題ありません。

教科書・論文でも一進法が使われるのは鍵生成アルゴリズムだけ【まとめ】

多くの暗号理論の教科書では、以下のような形式で統一されています。

• 鍵生成：Gen(1^k) ← 1進法
• 暗号化：Enc(pk, m) ← 通常の入力
• 復号：Dec(sk, c) ← 通常の入力

これは単に慣習ではなく、理論的にも合理的な構造になります。

用途	k の渡し方	入力サイズの意味	一進法が必要か？
鍵生成アルゴリズム	1^k	入力サイズ = k を明示	✅ 必要
暗号化・復号など	通常の入力	鍵やメッセージの長さに依存	❌ 不要

鍵生成アルゴリズムにkを直接渡す表記を見かけた場合

読者の理解を優先したり、実装寄りに寄せたい場合には、あえてkを数値として渡す書き方をすることもあります。

シーン	表現	注意書きの有無
教科書・論文的記述	Gen(1k)	正確な記述
初学者向け解説	Gen(k)	一般に注意書きや口頭での説明がある。 なくても、1がk個ならんだビット列を渡していると脳内置換する。 ※直感的にはセキュリティパラメータkを渡していると捉えてよい。
実装寄りの擬似コード	Gen(k)	Genの具体的な実装次第。 Genの引数の条件をチェックして、適切なkを与える。 注意書きがなければ、引数はセキュリティパラメータkそのもの。

『暗号技術のすべて』（あるいは私の発表スライド）の場合

たとえば『暗号技術のすべて』では、注略で「1^kではなくkを採用する」という旨を記述しています。

その理由は、初学者にとって「kじゃなくてなんで1^kなんだろう？」と暗号理論の本質とは違うところでつまづいて欲しくないための配慮です。

一般向け（ITエンジニアや中高生向けを含む）を対象に発表する際にも、同様の配慮をしています。

※アカデミックな発表の場合は正確に1^kを採用しています。

実装上はどうしてるのか？

実際のプログラム（PythonやCなど）では、k =128のように数値として渡すのが普通です。これは実用上、問題が起きないからです。

ただし、理論的に「このアルゴリズムはkに対して多項式時間です」と主張したいときには、入力形式を1^kとすることで、計算量評価の整合性が保たれます。