このブログシリーズをグラントプロジェクトとしてサポートしてくださっているイーサリアム財団、また執筆に際してフィードバックとレビューをしてくださった末神奏宙さんに感謝します。
Special thanks to Ethereum Foundation for awarding grants to this blog post series, and Sora Suegami for feedback and review.

このブログシリーズは、ソフトウェアエンジニアに限らず、あらゆる日本の読者のみなさんに向けて、最先端の暗号技術とその重要性をわかりやすく説明するという趣旨で書かれています。それぞれ単体の記事としてもお読みいただけますが、順番に読み進めていくことでより理解が深まります。まだお読みでない方は、ブロックチェーンやコンセンサスアルゴリズムの仕組みについて解説しているVol.1を先に読むことをお勧めします。また内容に関する疑問点、加筆や修正の提案は、こちらから提出いただけます。

3. 現代の暗号技術

「自然は曲線を創り、人間は直線を創る。… 自然界には何故曲線ばかりが現れるか。その理由は簡単である。特別の理由なくして、偶然に直線が実現される確率は、その他の一般の曲線が実現される確率に比して無限に小さいからである。しからば人間は何故に直線を選ぶか。それが最も簡単な規則に従うという意味において、取り扱いに最も便利だからである。」

『自然と人間』・湯川秀樹（1907 - 1981）

秘密と暗号

暗号技術とは、暗号理論・暗号学（Cryptography）に関連する技術のことを指しますが、そもそも暗号とはどういったもので、我々はなぜ暗号を必要とするのでしょうか？暗号ときくと、日常生活からかけ離れたものというイメージを持つかもしれませんが、多くの方々は幼少期から知らず知らずのうちに暗号という概念に触れているかもしれません。例えば、家族や友達との間で、秘密の合言葉のようなものを共有した経験がある方は少なくないのではないでしょうか？ノックを3回して、正しい合言葉を伝えないと部屋に入れないというルールを作って友達と盛り上がったり、家族で秘密の質問を決めて詐欺電話に騙されないようにしたりと、親近感が湧くような経験は誰しもが少なからず持っていると想像します。具体的な合言葉や質問でなくても、誰かとなにかの秘密を共有したり、秘密とまではいかなくても、親しい間柄の友達とのみ話せる話題もあるでしょう。このように我々は、当事者たちにしか知り得ない秘密を共有することで集団（意識）を形成したり、お互いに秘密を共有することで人間関係を深めたりすることができます。

秘密（Secrecy）というものは、それが当事者以外の第三者的存在の手に渡らないという前提があってはじめて秘密と呼ぶことができます。さらにいうと、秘密があるという事実自体も当事者以外にとっては定かではないことが理想的です。ではなぜ秘密の存在やその中身を隠したいのか、つまり秘密を安全に所有したいのかということを考えてみると、秘密やその存在が外部に漏れたり悪用されるといろいろな不都合が生じるからといえます。前述の例をとってみると、家族内で決めた秘密の質問とその回答が悪意のある第三者に漏れてしまうと、家族以外の誰かが家族の一員になりすまして悪事を働くことの障壁が下がってしまうことに繋がるのです。そういった秘密の最も安全な所有方法は、秘密を紙などの物理的な記録として残すことなく当人たちの記憶だけに留めておくことといえますが、これはつまり秘密が流出する経路を最小限に抑える戦略と捉えることもできます。このように、あらゆる秘密に対してそれを悪用する敵対者がいると仮定したときに、秘密を安全に所有したいというニーズが暗号という概念に繋がってくるわけです。

人間の脳の記憶容量は、学説にも依るものの2.5ペタバイト（250万ギガバイト）程度あるとされています。これは非常に膨大な容量に思えますが、記憶にも短期記憶や長期記憶といった種別があるため一概にはいえず、また人間は物忘れを起こすことも多いため、実際に活用できている記憶容量は遥かに少なく、また記憶自体も不安定であるといえます。つまり、最も安全な秘密の所有方法として挙げた、秘密を記憶だけに留めておくという方針には、人間は忘れやすいという大きな弱点があるのです。そこで、人間の脳の代わりとなるより安定した記憶装置としてコンピューターが生み出され、コンピューター同士が通信することによってインターネットという地球規模の巨大なネットワークが作られてきたわけですが、コンピューターが人間の脳の代わりとして機能するインターネットにおいて、秘密を安全に所有することはできるのでしょうか？また、プライベートなチャットやクレジットカードなどの情報は、どのようにして悪意のあるユーザーから守られているのでしょうか？データという物理的な記録として残る媒体でしかやりとりをすることができないインターネットにおいて、秘密を安全に所有するための仕組みをつくることこそが、暗号理論や暗号技術が生み出された目的といえるでしょう。

インターネットと暗号技術

（図1: 人間のコミュニケーションとコンピューターの通信の比較）

暗号技術の実体を掴むためには、人間同士のコミュニケーションとコンピューター間の通信の共通点や違いを理解する必要があります。まず両者に共通していえることは、コミュニケーションや通信が成立するためには、何かしらのルールや取り決めがなければならないということです。人間同士の直接的なコミュニケーションであれば、日本語や英語といった自然言語（Narural Language）をお互いが理解していることが大前提であるといえるでしょう。またコンピューター間の通信においては、プロトコル（Protocol）と呼ばれる、通信に関する具体的なルールが定義されています。例えば、Ethereumのような世界規模のコンピューターネットワークが正常に動作し続けているのも、それを構成するコンピューター群が定められたプロトコルに沿って処理を行っているからに他なりません。

その一方で、両者の最も大きな違いとして挙げられるのは、コンピューター間の通信によって送受信されるデータは自然言語ではなく、エンコーディングスキーム（Encoding Scheme）と呼ばれるデータの変換や、プログラミング言語のような人工的に定義された形式言語（Formal Language）を介して、最終的には数（Number）として処理されるという点です。したがって暗号技術とは、無数のコンピューター間の通信から成り立つインターネットにおいて、数として表されたデータを悪意のある第三者的存在から守る手段を提供するための技術であるといえるでしょう。その歴史を少し遡ってみると、敵対者に通信内容を傍受されてはならない戦争の過程で開発された技術も数多く存在しますが、現在ではほとんどの暗号技術が公開されており、インターネット上の9割以上のWebサイトが有効化している通信プロトコルなどにも組み込まれたりしています。これらを踏まえると、暗号理論とはデータの秘匿性において有用な数学的性質を探求する学問領域であり、それらをエンジニアリングを通じて実用的なものにするための技術が暗号技術の実体であると捉えることができます。

さまざまな暗号プリミティブ

暗号技術というと非常に幅広い意味合いを持ちますが、これは厳密にはさまざまな暗号プリミティブ（Cryptographic Primitive）をまとめて指す言葉です。暗号プリミティブとは、暗号学的に有用な概念を実現する基礎的な仕組みを指し、それを元にして具体的な暗号スキーム（Cryptographic Scheme）が組み立てられています。また、暗号スキームの中でも特に複数のコンピューター間のやりとりに関するものは、暗号プロトコル（Cryptographic Protocol）とも呼ばれています。ここでは、代表的な暗号プリミティブにはどんなものがあるのかをみていきましょう。

（図2: 代表的な暗号プリミティブ）

疑似乱数生成器（Pseudo-Random Generator・PRG）

コンピューターで秘密を扱うためには、なにかしらの無作為性・ランダムネス（Randomness）がなければなりません。しかし、コンピューターにおけるあらゆる計算は決定的（Deterministic）であるため、熱などの外部からのエントロピー（Entropy）を利用しない限り、コンピューター単体ではランダムネスを表現することができません。そこで考え出されたのが疑似乱数生成器（Pseudo-Random Generator・PRG）という仕組みで、これはコンピューターの内部で疑似的にランダムネスを表現することを可能にしました。数あるPRGの中でも、ここでは暗号学的疑似乱数生成器（Cryptographically-Secure PRG・CSPRG）と呼ばれる暗号学的に有用な性質をもったPRGについて取り上げてみると、CSPRGは、シード値（Seed）と呼ばれるランダムなデータを（理想的にはコンピューターの外部からサンプルして）インプットとして受け取り、それを用いてシード値よりも長くランダムにみえるデータを生成し、アウトプットとして返す関数を指します。これはつまり、例えばCSPRGによって生成された10111010というデータと、一様分布（Uniform Distribution）に基づいて抽出された11101001という同じ長さのデータ（各位の数が50%の確率で0となり、50%の確率で1となるようなデータ）があったときに、どちらが疑似的に生成されたデータであるか見分けがつかないということが、CSPRGによって確率的に保証されるということを意味します。

ハッシュ関数（Hash Function・HF）

PRGと関連した暗号プリミティブとしては、ハッシュ関数（Hash Function・HF）と呼ばれる仕組みがあります。ここではPRGのときと同様に、暗号学的な性質を備えた暗号学的ハッシュ関数（Cryptographic HF・CHF）について取り上げます。ハッシュ関数を用いると、任意の文字列をハッシュ値（Hash Value）と呼ばれる一定の長さのランダムな文字列に変換（圧縮）することができ、このプロセスは一般的にハッシュ化（Hasing）と呼ばれています。例えば、SHA-256として知られるハッシュ関数に対してdogという文字列を渡すと、cd6357efdd966de8c0cb2f876cc89ec74ce35f0968e11743987084bd42fb8944という256ビットの文字列が返却され、dogsという文字列を渡すと23bcd2d83d4c0f270640ec65cbeb61a1784856255c3c98dd25ec340453458348という全く別の256ビットの文字列が返却されます。このように、たった一文字違うだけでも全く異なる結果となるのがハッシュ関数の特徴の一つであるわけですが、それに加えて、生成された文字列から元の文字列を割り出すことが難しいこと（Pre-Image Resistance）や、同じハッシュ値となる二つの文字列を見つけることが難しいこと（Collision Resistance）も満たされるべき重要な性質として定義されています。

暗号化（Encryption）

暗号技術ときいたときに最もイメージされやすい暗号プリミティブは、暗号化（Encryption）でしょう。暗号化とは、あるメッセージデータ（Plaintext）について、元のメッセージを判別できないような暗号文（Ciphertext）に変換することを指し、逆に暗号文を元のメッセージに戻すことを復号（Decryption）と呼びます。ここで、なぜメッセージを暗号化するのかという疑問は、なぜ手紙を封筒に入れるのかという質問と構造的に似ています。つまり、手紙の内容を関係のない第三者に知られないように、手紙自体を封筒に入れて郵便ポストに投函するのと同じく、デジタルなメッセージを暗号化した上で、パブリックなインターネットを通じて相手に届けているのです。復号についても同様に、封筒を開封してはじめて手紙を読むことができるように、暗号文を復号することで元のメッセージが読めるようになるというわけです。暗号化と復号には、鍵・キー（Cryptographic Key）というメッセージとは別のデータが必要になります。メッセージとキーを用いて暗号化して、暗号文とキーを用いて復号するというのが一般的な流れです。その中で、暗号化と復号に用いるキーが同一である場合とそうでない場合があり、前者を秘密鍵暗号（Secret-Key Encryption・SKE）あるいは対称暗号（Symmetric Encryption）、後者を公開鍵暗号（Public-Key Encryption・PKE）あるいは非対称暗号（Asymmetric Encryption）と呼びます。

認証（Authentication）

ハッシュ関数と暗号化の仕組みを組み合わせると、誰がメッセージを送ったのか、つまり誰がデータを所有しているのかという認証（Authentication）を行う暗号プリミティブをつくることができます。この仕組みは、メッセージ認証コード（Message Authentication Code・MAC）や電子署名アルゴリズム（Digital Signature Algorithm・DSA）として知られており、HTTPSと呼ばれる通信規格における通信の信頼性の担保や、Ethereumのトランザクションの検証などに用いられています。ハッシュ関数ベースのMACやDSAでは、ハッシュ化されたメッセージに対して電子署名を生成し、それをハッシュ化されていない元のメッセージと共に送ることで、通信途中で第三者によってメッセージが改竄されていないというデータの完全性（Data Integrity）を保証することができます。例えば、Ethereumのトランザクションには必ずECDSA（Elliptic Curve Digital Signature Algorithm）と呼ばれる形式の電子署名が含まれており、各バリデーターがトランザクションの実行前に署名の検証を行うことで、不正なユーザーによるなりすましや改竄などを防ぐ仕組みが構築されています。

秘密鍵暗号と公開鍵暗号

“We know the past but cannot control it. We control the future but cannot know it.”

Claude Shannon (1916 - 2001)


復号を伴う暗号化によるデータの秘匿を目的としたあらゆる暗号プリミティブは、秘密鍵暗号と公開鍵暗号のいずれかに分類することができます。ここからは、PRGやハッシュ関数が存在すること、つまりコンピューターで疑似的なランダムネスが生成できることを前提に、それぞれの仕組みや性質を掘り下げていきます。

秘密鍵暗号と公開鍵暗号の共通構造

まずは、秘密鍵暗号と公開鍵暗号に共通した構造的特徴を考えてみると、両者ともに、大まかには以下の3つのパートから構成されていると捉えることができます。

  1. キーの生成（Key Generation）

    暗号化や復号に必要なキーを生成する。秘密鍵暗号においてはシークレットキーのみを、公開鍵暗号においてはシークレットキーとパブリックキーのペアを生成する。シークレットキーとパブリックキーはそれぞれ文字通り、当事者以外に漏れてはいけないキーと、第三者に対して公開されても問題がないキーを意味する。

  2. 暗号化（Encryption）

    メッセージなどのデータを暗号化する。秘密鍵暗号ではシークレットキーを、公開鍵暗号ではパブリックキーを用いて暗号化を行う。

  3. 復号（Decryption）

    暗号化されたデータを復号する。シークレットキーを用いて暗号化されたデータは同一のシークレットキーのみで復号でき、パブリックキーを用いて暗号化されたデータは紐づいたシークレットキーのみで復号できる。

秘密鍵暗号

（図3: 秘密鍵暗号）

ワンタイムパッド（One-Time Pad・OTP）

1970年代後半に公開鍵暗号が生み出されるまでは、暗号化を目的としたあらゆる暗号スキームは秘密鍵暗号を元に組み立てられていました。現代でも使用されている最も古い秘密鍵暗号ベースのスキームは、19世紀の終わり頃〜20世紀初頭に考案されたワンタイムパッド（One-Time Pad・OTP）でしょう。OTPは、暗号化したいメッセージと同じ長さのシークレットキーを用意し、それを用いてメッセージや暗号文に対して排他的論理和（Exclusive Or・XOR）を計算することで、暗号化と復号を行うスキームです。XORというのは、2つの2進数（Binary Number）あるいはビット（Bit）に対する演算のひとつで、両方のビットが同じ値のときは0（偽・Falseとも呼ばれる）に、異なる値のときは1（真・Trueとも呼ばれる）とするという下記のような性質をもちます。

$A$ $B$ $A \oplus B\ (A\ XOR\ B)$
0 0 0
0 1 1
1 0 1
1 1 0
OTPを用いた暗号化

まずはじめに、OTPを使ってメッセージの暗号化と復号をしてみましょう。今回暗号化したいメッセージは、Unicodeと呼ばれるエンコーディングスキームで😴という絵文字を表す00011111011000110100とします。

  1. キーの生成

    まずは、暗号化したいメッセージと同じ長さのランダムなキーを生成する必要があります。今回のメッセージの長さは20ビットなので、11110101101110110101をランダムに生成されたシークレットキーとして使ってみるとします。

  2. 暗号化

    暗号化するメッセージを$M$、キーを$K$とすると、暗号文$C$は以下のように計算することができます。

    \[\begin{split} C &= M \oplus K \\ &= \begin{split} &00011111011000110100 \\ &\oplus 11110101101110110101 \\ \end{split} \\ &= 11101010110110000001 \\ \end{split}\]

  3. 復号

    では、暗号文として得られた11101010110110000001を同じキーを用いて復号してみましょう。

    \[\begin{split} &C \oplus K \\ &= \begin{split} &11101010110110000001 \\ &\oplus 11110101101110110101 \\ \end{split} \\ &= 00011111011000110100 \\ &= M \\ \end{split}\]

    暗号文を復号した値は、元のメッセージと一致しました。このように、元のメッセージと暗号文を復号した値とが同一であるということは、OTPの暗号化スキーム（Encryption Scheme）としての正しさ（Correctness）を示しています。事実、OTPは任意のメッセージについて、元のメッセージに正しく復号できる暗号化を可能にしており、$Enc$を暗号化、$Dec$を復号とすると、以下のように表現することができます。

    \[\begin{split} Dec(C, K) &= Dec(Enc(M, K), K) \\ &= Dec(M \oplus K, K) \\ &= M \oplus (K \oplus K) \\ &= M \oplus 0 \\ &= M \\ \end{split}\]

ここで、暗号化スキームの正しさとそれが安全であるということは別の意味合いを持ちます。暗号化スキームの安全性（Security）は、暗号文が悪意のある第三者的存在の手に渡ったときに、そこから元のメッセージを識別できる確率によって数学的に定義されるため、証明可能な安全性（Provable Security）と呼ばれています。具体的には、攻撃者が任意の2つのメッセージを暗号スキームに提出し、いずれかのメッセージの暗号文のみが返却されるという設定を考えます。このとき、攻撃者が提出するメッセージを選ぶ前に、任意の複数のメッセージを暗号化してその結果を確かめることができる（ただしここで用いたメッセージは提出できない）と仮定した場合に、どちらのメッセージが暗号化されているかを識別できない（Indistinguishability）ようなスキームは強安全性（Semantic Security）あるいはIND-CPA（INDistinguishability under Chosen Plaintext Ataack）を満たすとされています。また、それに加えて攻撃者が（返却される暗号文以外の）任意の暗号文を復号できることも仮定した場合の安全性はIND-CCA（INDistinguishability under Chosen Ciphertext Ataack）と定義されています。

では、OTPのセキュリティーについて考えてみましょう。OTPにおける暗号文$C$の計算式は、XORの性質から以下のように言い換えることができます。

\[\begin{split} C = M \oplus K \Leftrightarrow K = M \oplus C \end{split}\]

これはつまり、通信を傍受する盗聴者（Eavesdropper）が、暗号化によって$C$となるような$M$を推測しようとする試みを$Eave$とすると、任意のメッセージ$M$について盗聴者が正しい$M$を推測できる確率は、暗号化に使用されているキーを推測する確率と等しくなるということを意味します。

\[\begin{split} \Pr[Eave(M) = C] &= \Pr[K = M \oplus C] \\ 　　　&= \frac{1}{2^\lambda} \\ \end{split}\]

ここで、キーはランダムに生成されるため、キーの長さ（i.e., ビット長）を$\lambda$とするとその確率は$\frac{1}{2^{\lambda}}$となり、$\lambda$が大きければ大きいほど限りなくゼロに近い確率となります。このキーの長さを決定する$\lambda$という数は、暗号化スキームが確率的にどれだけ強力であるかを表すため、セキュリティーパラメーター（Security Parameter）と呼ばれています。さらに、同じ$C$となるメッセージとキーの組み合わせは$2^{\lambda}$通りあるため、攻撃者がどんなに強力な計算資源を使ったとしても、暗号文から元のメッセージを一意に求めることができないことが保証されます。OTPはこの性質から、十分な長さのキーをメッセージごとに生成して使った場合、完全安全性（Perfect Security）と呼ばれる最も強固な安全性をもつとされています。

OTPを用いた認証

次に、OTPを認証の用途に使用するケースを考えてみましょう。OTPを含め、暗号化スキーム自体には認証の仕組みがありません。例えば、上記のOTPの例において11101010110110000001という暗号文$C$が通信途中で11101010110110000000という別の暗号文$C’$に改竄されたとしても、受信側は元のシークレットキー11110101101110110101を使って以下のように元のメッセージを復号しようとします。しかし、最後の1ビットが異なるため元のメッセージが正しく復号できず（$M \neq M’$）、暗号化スキームとしての正しさが損なわれてしまいました。

\[\begin{split} &C' \oplus K \\ &= \begin{split} &11101010110110000000 \\ &\oplus 11110101101110110101 \\ \end{split} \\ &= 00011111011000110101 \\ &= M' \\ \end{split}\]

メッセージ認証コード（MAC）は、このような問題を解決するための暗号プリミティブです。MACは非常にシンプルで、シークレットキーを用いてメッセージに対して認証タグ（Authentication Tag）を生成し、それをメッセージと共に送ることで、受信者が同じシークレットキーを用いてタグを検証して通信途中のメッセージの改竄を検知できるようにする仕組みを実現します。ここで、暗号化とMACにおけるタグ生成の両方にOTPを用いる場合は、XORの性質として、同じメッセージに対して同じキーを二度用いると元のメッセージが明らかになってしまうため、それぞれ別のシークレットキーを生成して用いる必要があります。

では前述の例について、OTPベースのMACを用いて改竄を検知できるようにしてみましょう。暗号文を$C$、暗号化とタグ生成に用いるシークレットキーをそれぞれ$K_1 = 11110101101110110101$、$K_2 = 11001011111110011010$とすると、タグ$T$は以下のように計算されます。

\[\begin{split} T &= C \oplus K_2 \\ &= \begin{split} &11101010110110000001 \\ &\oplus 11001011111110011010 \\ \end{split} \\ &= 00100001001000011011 \\ \end{split}\]

ここで先ほどと同様に、暗号文$C$が通信途中で偽の暗号文$C’$に改竄され、上記とタグと共に送られてきた場合を考えてみると、タグの検証によって得られる値と送られてきたメッセージが異なる（$C \ne C’$）ため、メッセージの認証は失敗します。またタグ自体の改竄に関しても同様に認証が失敗することがわかるでしょう。

\[\begin{split} &T \oplus K_2 \\ &= \begin{split} &00100001001000011011 \\ &\oplus 11001011111110011010 \\ \end{split} \\ &= 11101010110110000001 \\ &= C \\ \end{split}\]

逆にメッセージの認証が成功した場合は、暗号文$C$に対して通常通り$K_1$を用いて復号を行うことで、元のメッセージを知ることができます。ちなみにより実用的なスキームとしては、メッセージのハッシュ値に対してタグを生成することで、任意の長さのメッセージについての認証を可能にしたHMAC（Hash-based MAC）などが知られています（ただしこの場合は復号はできません）。

公開鍵暗号

“If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is.”

John von Neumann (1903 - 1957)

（図4: 公開鍵暗号）

OTPのような秘密鍵暗号は1つのキーしか用いないため、非常にシンプルな仕組みですが、シークレットキー自体を安全に共有しなければならないという問題を含んでいました。一般的な金庫や家の鍵などの物理的な鍵の共有とは対照的に、デジタルなキーの共有を安全に行うのが難しいことは想像に難くありません。もちろん、キーを紙などに書き出して通信したい相手に物理的に届けて共有し、それを用いて暗号化して通信を行えば安全といえますが、キーが書かれた紙を紛失したり盗まれたりすると、また別のキーを生成して送り届ける必要があります。特にOTPに関しては、メッセージごとに違うシークレットキーを用いないと安全性が低くなってしまうため、このままでは利便性が低くなってしまうことは明らかでしょう。

そこで考案されたのが、シークレットキーとパブリックキーの2つのキーを用いる公開鍵暗号です。公開鍵暗号を用いると、パブリックキーを用いて暗号化を行い、シークレットキーを用いて復号を行う暗号化スキームであったり、シークレットキーを用いて電子署名を作成し、パブリックキーを用いて署名を認証する仕組みをつくることが可能になります。ここで、パブリックキーが第三者の手に渡っても暗号化スキームとしての安全性は保たれるわけですが、暗号化と復号など、2つキーは必ずペアとして使用されるため、何らかの形で紐づいていなければなりません。つまり、シークレットキーからパブリックキーは生成できるが、パブリックキーからシークレットキーを割り出すことはできないという関係性が必要になるというわけです。この一見すると不可能な繋がりを可能にしたのが、数学的な問題の計算複雑性に関する理論（Computational Complexity Theory）でした。

数学的な問題といわれるとイメージがつきにくいかもしれませんが、実はあらゆる物事は数学的な問題として表現できます。一番簡単な例をあげると、テーブルの上に大きなリンゴと小さなリンゴがあったとき、そのテーブルの上にリンゴはいくつあるのか、という問いがあったとします。この問いは、大小問わずリンゴを1という数学的な概念に置き換えると、1+1という整数の足し算の問題と捉えられるわけです。あるいは、与えられた辞書に特定の単語が含まれているかという問いは、いかに効率的に単語を探せるかという探索（Searching）に関する最適化問題として捉えることができるでしょう。ここで、あるなにかしらの問題が与えられた場合に、それを解くための具体的な手順のことをアルゴリズム（Algorithm）と呼びます。これまで述べてきたように、コンピューターは計算機械であるため、コンピューターで処理される問題は数学的に抽象化されている必要があり、それに対するアルゴリズムもまた数学的な解法でなければなりません。要するに、コンピューターにおけるプログラムというものは、突き詰めると、なにかしらのプログラミング言語を用いて、ある特定の問題に対するアルゴリズムを実装したものであるといえるのです。

さて、なにかしらの問題に対するアルゴリズムを実行するのはコンピューターであるわけですが、実行に要する時間やメモリー領域（RAM）が少ないほど効率的なアルゴリズムであるといえます。そこで、アルゴリズムの良し悪しを判断する基準として、時間計算量（Time Complexity）と空間計算量（Space Complexity）という指標が用いられています。時間計算量とは文字通り、あるアルゴリズムによって表された計算にかかる時間のことを指しますが、これは足し算などの基本的な演算やRAMへの読み書きなどの根本の処理にかかる時間を一定としたときに、アルゴリズムへの入力データのサイズに応じて、アルゴリズム全体としての実行時間がどのように増加するかを測るための指標です。また、空間計算量も同様に、入力データのサイズに対して、アルゴリズムの実行に必要となるメモリー領域がどのように増加するかを測るための指標です。どちらの指標も重要ではありますが、暗号領域においては、主に時間計算量に重きが置かれています。

（図5: 時間計算量）

図5は、アルゴリズムへの入力データのサイズを$n$としたときに、$n$の大きさに対する時間計算量$N$の増加率を示したグラフです。ここでは時間計算量の基準として、アルゴリズムの実行に最も時間がかかる場合を想定して、ビッグ・オー記法（Big O Notation）と呼ばれる記法で時間計算量を表すとします。例えば、$O(n)$というのは、サイズが$n$の入力に対して最悪の場合、$n$ステップ分の計算時間を要するということを示します。ここでグラフをよくみてみると、線形時間（Linear Time・$O(n)$）を中心として、対数時間（Logarithmic Time・$O(log_{2}n)$）の増加率は緩やかであるのに対し、指数時間（Exponential Time・$O(2^n)$）の増加率は非常に高くなっていることがわかるかと思います。計算複雑性理論においては、効率的なアルゴリズムとは多項式時間（Polynomial Time・$O(n^k)$）で実行できるアルゴリズムを指し、コンピューターで効率的に解くことができる問題（Tractable Problem）とは効率的なアルゴリズムが存在する問題と定義されています。これらを踏まえると、すべての問題は以下の3つに分類することができます。

  1. 効率的なアルゴリズムが存在する問題

    多項式時間で実行できるアルゴリズムが存在する問題は、コンピューターで効率的に解くことができる問題と言い換えることができます。例えば、データの並び替え（Sorting）の問題は、$O(nlog_{2}n)$といった多項式時間以下で実行できるアルゴリズムが多数存在するため、効率的に解くことができる問題とされています。

  2. コンピューターで解くことはできるが、効率的なアルゴリズムが存在しない問題

    他方で、多項式時間で解くことができないとされている問題も多数存在します。これらの問題は厳密にはさらに2つに分類することができ、前述のビッグ・オー記法（$O$）で表される最悪計算量が指数関数的なものと、ビッグ・シータ記法（$\Theta$）として表される平均計算量が指数関数的なものとに分けて考えられます。例えば、$9×9$という制約を$N×N$に緩めた数独などは前者に分類される問題とされていますが、一方でハッシュ関数などは後者のような問題をもとに設計されているため、より難しい問題であると捉えることができます。どちらも効率的なアルゴリズムが存在しないとされている問題ですが、これは別の表現をすると、現時点では多項式時間で解けるアルゴリズムは見つかっていないが、そういった効率的なアルゴリズムが存在しないかどうかは証明されていない問題であるということになります。つまり、2024年時点では効率的に解けないとされている問題も、30年後には効率的に解くことができる問題になっている可能性も（限りなくゼロに近いとされているものの）全くのゼロではないというわけです。

  3. コンピューターで解くことができない問題

    2に分類される問題は、たとえ時間がかかったとしてもコンピューターで解くことができるものですが、驚くことに、理論的にコンピューターで解くことができない問題も存在します。例えば、アラン・チューリング（Alan Turing）という数学者が考案した停止性問題（Halting Problem）においては、あるプログラムとそれに対する入力データが与えられた場合に、そのプログラムが停止するかどうかを判断できるアルゴリズムは存在しない、という証明がなされています。

公開鍵暗号に話を戻すと、上記の1と3に分類される問題については、暗号プリミティブとしては使えそうにありません。一方で、2に分類される問題を用いれば、公開鍵暗号の仕組みの実現に有用であることがわかりました。つまり、シークレットキーからパブリックキーを計算するのが簡単な問題であると同時に、パブリックキーからシークレットキーを計算するのは難しい問題であるような関係性が構築できれば、2つのキーの理想的な関係性が実現できることになるわけです。このように、一方向への計算は効率的にできても、逆方向への計算は効率的にできない性質を持った関数のことを一方向関数（One-way Function）と呼びます。一方向関数の存在は、公開鍵暗号だけでなく、PRGやハッシュ関数が仮定する前提でもあるわけですが、一方向関数の存在は厳密には証明されていないため、あくまでもそういった性質の関数が存在するという仮定に基づいて現代の暗号プリミティブは設計されている、ということを念頭においておく必要があります。ちなみに、一方向関数の存在が証明されると、$FP \neq FNP$や $P \neq NP$と呼ばれる証明に繋がり、計算複雑性理論の分野で長年証明されてこなかった重要な式が成立することになります。

RSA暗号（RSA Cryptosystem）

上記を踏まえて、ここからは公開鍵暗号の一例として、1970年代後半に公開されて以降2024年現在に至るまでの50年近くのあいだ、暗号化や電子署名（DSA）のスキームとして世界中で利用されている、RSA暗号（RSA Cryptosystem / RSA Algorithm）の仕組みをみていきます。RSA暗号は、その数学的不可逆性（Mathematical Hardness）を、十分に大きな半素数（2つの素数の積）の素因数分解（Semiprime Factorization）や、RSA問題（RSA Problem）と呼ばれる問題と、それに関連する一方向関数によって担保している暗号スキームです。ここでは、RSA暗号をDSAとして使用する場合の仕組みやその正しさをみていきましょう。

RSA署名の仕組み

  1. キーペアの生成

    RSA暗号におけるキー生成は、以下の4ステップに分けられます。

    1-A）半素数の生成

    まず、半素数$n$を計算するために、PRGを用いて十分に大きな2つの素数$p,q$をランダムに選び出します。OTPと同様に、$n$の大きさがキーの長さ、つまり暗号スキームの強度を示すセキュリティーパラメーターとなるわけですが、2024年現在は2048〜4096ビットとすることが推奨されています。ここでは、$n$のサイズを2048ビット、$p,q$のサイズをそれぞれ1024ビットとします。

    \[\begin {split} &p \leftarrow \{0,1\}^{1024} \\ &q \leftarrow \{0,1\}^{1024} \\ &n = pq \\ \end {split}\]

    1-B）オイラーのトーシェント関数あるいはカーマイケル関数の計算

    次に、オイラーのトーシェント関数（Euler’s Totient Function）と呼ばれる関数$\phi(n)$を計算します。$\phi(n)$は、整数$n$よりも小さく、$n$と互いに素（Relatively Prime / Co-prime）である正の整数がいくつあるかを計算する関数であるため、例えば、$n$が素数である場合は、$\phi(n) = n-1$となります。では、上記のステップで生成した半素数$n$に関する$\phi(n)$は、いくつになるでしょうか？$n$よりも小さい正の整数は$n-1$個あるわけですが、$n = pq$であるため、$p$の倍数と$q$の倍数は取り除かれなければなりません。ここで、$p$の倍数は$|\{p,\ 2p,\ 3p, \cdots ,\ (q-1)p\}|=q-1$個、$q$の倍数は$|\{q,\ 2q,\ 3q, \cdots ,\ (p-1)q\}|=p-1$個あるわけですが、$p$と$q$は互いに素であるので、これらだけが$n$よりも小さく、$n$と互いに素である正の整数であるといえます。つまり、$n = pq$の場合、$\phi(n)$は以下のように計算できるわけです。

    \[\begin {split} \phi(n) &= n - 1 - (q - 1) - (p - 1) \\ &= pq - p - q + 1 \\ &= (p - 1)(q - 1) \\ \end {split}\]

    ここで、正の整数$n$と互いに素である任意の整数$x$について、$\phi(n)$を用いると、以下の合同式が成り立つことが知られており、これはオイラーの定理（Euler’s Theorem）と呼ばれています。

    \[x^{\phi(n)} \equiv 1 \pmod n\]

    ちなみに、オイラーの定理は$n = pq$の場合も成り立つわけですが、$n$は$p$と$q$でそれぞれ割り切れることから、$x(p-1)(q-1) \equiv 1\ (mod\ pq)$は、以下の式に分解・展開することができます。

    \[\begin {cases} \begin {split} x^{(p - 1)(q - 1)} &\equiv (x^{p - 1})^{q - 1} \pmod p \\ &\equiv (1)^{q - 1} \pmod p \\ &\equiv 1 \pmod p \\ \end {split} \\ \begin {split} x^{(p - 1)(q - 1)} &\equiv (x^{q - 1})^{p - 1} \pmod q \\ &\equiv (1)^{p - 1} \pmod q \\ & \equiv 1 \pmod q \\ \end {split} \\ \end {cases}\]

    それぞれの式の展開時に、$x^{p-1} \equiv 1\ (mod\ p)$と$x^{q-1} \equiv 1\ (mod\ q)$という性質を利用していることに注目してください。このように、ある素数$p$と任意の整数$x$について、$x^{p-1}-1$は必ず$p$で割り切れるという性質は、フェルマーの小定理（Fermat’s Little Theorem）として知られています。また、上記の連立方程式に関して、中国の剰余定理（Chinese Remainder Theorem・CRT）と呼ばれる定理から、$x$はただ1つのユニークな解を持つことが証明されており、その値は$x^{(p-1)(q-1)} \equiv 1\ (mod\ pq)$となるというわけです。これらの式から、フェルマーの小定理はオイラーの定理における特殊なケースであって、逆にいうとオイラーの定理はフェルマーの小定理を一般化したものであるとも捉えられます。

    さて、初期のRSA暗号においては、大半の実装でオイラーのトーシェント関数$\phi(n)$が使用されていましたが、現在はカーマイケル関数（Carmichael Function）と呼ばれる、より効率的な関数$\lambda(n)$を使用する実装が多くなっています。ここでいう効率的とは、関数の計算結果が小さいということを意味しますが、これは$\lambda(n)$が以下の式で表されるように、オイラーの定理を満たす最小の指数（Exponent）を計算する関数であるということに起因します。

    \[x^{\lambda(n)} \equiv 1 \pmod n\]

    ここで、$\phi(n)$は$n$を法とする有限な整数の乗法群（Finite multiplicative group of integers modulo $n$）であるため、必ず$\lambda(n)$が存在することが知られています。つまり、$\phi(n)$と$\lambda(n)$の関係性は言い換えると、$\phi(n)$は必ず$\lambda(n)$で割り切れるということになり、ある正の整数$k$について、$\phi(n) = k\lambda(n)$という等式が成り立つことがわかります。

    では、$\phi(n)$のときと同じように、半素数$n$に関する$\lambda(n)$はいくつになるか計算してみましょう。$n = pq$であり、$p$と$q$はそれぞれ異なる素数であるため、任意の整数$a, b$の最小公倍数（Least Common Multiple）を$lcm(a, b)$とすると、$\lambda(n) = \lambda(pq) = lcm(\lambda(p),\ \lambda(q))$という式が成り立ちます。ここで任意の素数$p$に関する$\lambda(p)$は$\phi(p)$と等しいため、$\lambda(n)$は以下のように計算することができます。

    \[\begin {split} \lambda(n) &= \lambda(pq) \\ &= lcm(\lambda(p), \lambda(q)) \\ &= lcm(\phi(p), \phi(q)) \\ &= lcm(p - 1, q - 1) \\ \end {split}\]

    計算結果である$lcm(p-1,\ q-1)$に注目してみると、この値は必ず$(p-1)(q-1)$を割り切るため、$\phi(n)=k\lambda(n)$という関係性が保たれていることがわかります。また、ここで計算が必要になる最小公倍数については、日本の高校でも習うユークリッドの互除法（Euclidean Algorithm）を用いると効率的に計算できることが知られています。

    1-C）パブリックキーの選出

    オイラーのトーシェント関数$\phi(n)$またはカーマイケル関数$\lambda(n)$の計算が完了したら、$\phi(n)$または$\lambda(n)$よりも小さく、互いに素である整数$e$を選び出します。RSA暗号においては、$(n, e)$という値のペアがパブリックキーとなります。

    1-D）シークレットキーの計算

    最後に、以下の式を用いてシークレットキー$d$を計算します。$d$は、拡張ユークリッドの互除法（Extended Euclidean Algorithm）と呼ばれるアルゴリズムを用いて効率的に計算することができます（式は$\lambda(n)$を想定）。

    \[d \equiv e^{-1} \pmod {\lambda(n)}\]

    ここで、1-Dのステップにおいて、パブリックキーからシークレットキーを効率的に計算できないようにしなければならないのに、計算できてしまっているのは問題ではないのか、という疑問が湧いてくるかと思います。たしかにパブリックキー$e$からシークレットキー$d$を計算していますが、これは、$\phi(n)$または$\lambda(n)$が効率的に計算できなければ、$d$は効率的に計算できないという仮定に基づいており、最終的には$n$を素因数分解するという問題に繋がります。先述の通り、十分に大きな半素数の素因数分解は一方向関数であり、また$p,q$は公開されないため、RSA暗号で生成されるキーペアは、公開鍵暗号に必要な性質を満たしていると結論づけることができます。また、$e$, $d$は互いにモジュラー逆数（Modular Multiplicative Inverse）であり対称的な関係性にあるため、1-Cと1-Dのステップを逆にして、はじめに$d$をランダムに選び、そこから以下の式を用いて$e$を計算することも可能です（式は$\lambda(n)$を想定）。

    \[e \equiv d^{-1} \pmod {\lambda(n)}\]

  2. 暗号化（電子署名の生成）

    先述の通り、DSAにおいては、シークレットキーを用いて電子署名を生成します。これは言い換えると、シークレットキーを知っている存在のみが有効な電子署名を生成でき、その署名はパブリックキーを用いれば誰でも検証できる、ということを意味します。ここで、メッセージを$M$、使用するハッシュ関数を$H$としたとき、電子署名$Sig$は、前のステップで生成されたシークレットキー$d$、パブリックキーペアの一部である$n$を用いて、以下の式で生成することができます。

    \[\begin {split} &h = H(M) \\ &Sig = h^d \pmod n \end {split}\]

  3. 復号（電子署名の検証）

    シークレットキーを用いて生成された電子署名は、紐づいたパブリックキーでその有効性を検証することができます。電子署名$Sig$の検証は、パブリックキーペア$(n,\ e)$を用いて、以下のように行われます。

    \[Sig^e = (h^d)^e \equiv h \pmod n\]

    その後、電子署名の生成時と同じハッシュ関数を用いて、電子署名の添付されたメッセージのハッシュ値を計算し、上記の計算によって得られたハッシュ値と比較して同一の値であれば検証成功となります。

RSA署名の正しさと安全性

さて、ここからはOTPのときと同様に、上記のRSA暗号ベースのDSAに関する、暗号スキームとしての正しさをみていきましょう。今回のスキームでは、任意のメッセージについて、正しいパブリックキーを用いて電子署名の検証を行った際に、計算結果が元のメッセージのハッシュ値となることが証明できればよいということになります。つまり、$Sig^{e} \equiv h\ (mod\ n)$となることを証明すればよいわけですが、ここで、シークレットキー$d$とパブリックキー$e$について、以下のように表現することができます。

\[\begin {split} && d &\equiv e^{-1} \pmod {\lambda(n)} \\ \Leftrightarrow&&\ de &\equiv 1 \pmod {\lambda(n)} \\ \end {split}\]

上記の結果は、ある0以上の整数$k$を用いると、$de - 1 = k\lambda(n)$とも捉えることができます。よって、カーマイケル関数の定義から、RSA署名の正しさは以下のように証明することができます。

\[\begin {split} Sig^e &\equiv (h^d)^e \pmod n \\ &\equiv h^{de} \pmod n \\ &\equiv h^{k\lambda(n) + 1} \pmod n \\ &\equiv (h^{\lambda(n)})^kh \pmod n \\ &\equiv (1)^kh \pmod n \\ &\equiv h \pmod n \\ \end {split}\]

この証明が成立するのは、メッセージのハッシュ値$h$と半素数$n$が互いに素である場合のみですが、これは逆に捉えると、$h$と$n$が互いに素でない場合は証明が成立しないということを意味します。しかし、$h$と$n$がそのような（互いに素でない）ペアとなる確率は

\[\begin {split} 1 - \frac{\phi(n)}{n} &= \frac{pq - (p-1)(q-1)}{pq} \\ &= \frac{p+q-1}{pq} \\ &= \frac{1}{p} + \frac{1}{q} - \frac{1}{pq} \\ \end {split}\]

であり、$p$と$q$が十分に大きければ無視できるほど低い確率になるため、暗号スキームのセキュリティーとしては問題ありません。また、$\lambda(n)$を$\phi(n)$に置き換えても、オイラーの定理によって証明は同様に成立することがわかるでしょう。さらにRSAについては、パブリックキー$e$を暗号化に、シークレットキー$d$を復号に用いると、暗号化スキームとしても使用することができ、その正しさも同様の流れで証明することができます。ちなみに、実用的なRSA暗号の実装においては、暗号化や電子署名を行う前にパディング（Padding）と呼ばれる手法を用いて、元のメッセージにランダムネスを追加することが推奨されています。

続いてRSA暗号の安全性について、前述のような適切なパディングによってランダムネスを含むRSA暗号は、IND-CCAを満たすとされていますが、ここではその仮定（Security Assumption）を確認してみましょう。まず、RSAで使用されるキーペアについては、先述の通り、十分に大きな半素数の素因数分解に関する計算不可逆性に基づいて、パブリックキーからシークレットキーが割り出せないことが仮定されています。次に、RSAをDSAとして使用する場合は、生成された電子署名からシークレットキーが割り出せないこと、つまり$Sig = h^d\ (mod\ n)$に関して、$d$について効率的に解くことはできないという性質を利用しています。これは一般的に離散対数問題（Discrete Logarithm Problem・DLP）と呼ばれており、実数$a,b$に関して、$a^k = b$を満たす整数$k$を求める問題を指しますが、特殊な条件下においては、DLPを効率的に解けるアルゴリズムは存在しないという仮定があります。今回の場合は、$n$を効率的に$p$と$q$に素因数分解できない限り、離散対数、つまりシークレットキー$d$も効率的に求めることができないという仮定に基づいているといえるでしょう。最後に、RSAを暗号化に使用する場合は、暗号文から元のメッセージを計算することが難しいという性質が必要になりますが、これはRSA問題に関する計算不可逆性に基づいています。RSA問題はその名の通り、RSA暗号のために生み出された一方向関数で、暗号文$C$とパブリックキーペア$(n,\ e)$が与えられたときに、暗号化に用いられる計算である、$C = M^e\ (mod\ n)$を満たすようなメッセージ$M$を効率的に計算することが難しいことを仮定しています。

公開鍵暗号 + 秘密鍵暗号

（図6: ハイブリッド型暗号）

公開鍵暗号は、暗号化の前にシークレットキーを安全に共有しなければならないという秘密鍵暗号における最大の弱点を補うという点では、非常に有用な暗号の仕組みでした。しかし、前セクションの説明の長さからも推測できるように、公開鍵暗号は秘密鍵暗号と比べると計算が多く複雑で、長いメッセージを暗号化するために非常に大きなキーを必要とするなど、それ単独では理想的とはいえない側面も持っています。そこで考案されたのが、2つの暗号の仕組みを組み合わせたハイブリッドな暗号化スキームです。このハイブリッド型暗号では、キーの生成に公開鍵暗号を使い、その後の暗号化では生成したキーをシークレットキーとして秘密鍵暗号を使うことで、両者の弱点を補い合うような仕組みを実現しています。ここで、前者のような複数パーティーによるキーの生成を行う仕組みは、鍵交換アルゴリズム（Key Exchange Algorithm）と呼ばれています。鍵交換アルゴリズムは、予め秘密にしたいキーを生成しそれを暗号化して共有するのではなく、公開鍵暗号の仕組みを用いて、複数パーティーでキーを安全に計算することを可能にする仕組みであるため、これまで紹介してきたような通常の暗号化スキームとは用途が違うことに注意が必要です。

ディフィー・ヘルマン鍵交換アルゴリズム（Diffie-Hellman Key Exchange・DHKE）

ここからは、ディフィー・ヘルマン鍵交換アルゴリズム（Diffie-Hellman Key Exchange・DHKE）として知られる、公開鍵暗号をベースにした鍵交換アルゴリズムについてみていきます。実はDHKEはRSAよりも先に公開されており、1つのキーではなくキーペアを用いるという点で、公開鍵暗号の先駆けとして現在でも広く利用されている暗号スキームです。よって、まずはじめに秘密鍵暗号の欠点を補うスキームとしてDHKEが考案され、後にその仕組みを暗号化や電子署名（DSA）といった用途にも利用するために、RSAなどのスキームが提案されてきた、とした方が歴史的には正しい流れになります。DHKEは、特定の条件下における離散対数問題（DLP）の計算の難しさを中心に設計された暗号スキームで、複数パーティー間でお互いのシークレットキーを明らかにせずに、共通のキーを生成することを可能にします。ここでは、最もシンプルな2者間でのDHKEの仕組みや正しさ、安全性についてみていきましょう。

DHKEの仕組みと正しさ

  1. キーペアの生成

    DHKEにおけるキー生成は、以下の3ステップに分けられます。

    1-A）法と原始根の選出

    まず、DLPを解くのが難しくなるような群（Group）を選びます。例えば、十分に大きな素数$n$を法（Modulus）とした乗法群（Multiplicative group of integers modulo $n$）は、そのような性質を持つとされているため、2024ビットの長さの素数$n$などは適しているといえるでしょう。次にその群に関して、原始根$g$（Primitive Root）をひとつ選び出します。ここで、任意の素数に関する乗法群は、その群の要素（Element）から生成される巡回群（Cyclic Group）であり、巡回群には必ず原始根（Primitive root modulo $n$）が存在することが証明されています。この$(n,g)$のペアは、DHKEにおけるパブリックパラメーターとして、2者間で共有されます。

    1-B）シークレットキーの選出

    ここでDHKEを行うパーティーをそれぞれA、Bとすると、AとBはそれぞれのシークレットキー$d_A$と$d_B$を、上記で選ばれた共通の$n$と互いに素な正の整数（i.e., $n$未満の正の整数）からランダムに選び出します。

    \[\begin {split} d_A \leftarrow \{1, \dots, n - 1\} \\ d_B \leftarrow \{1, \dots, n - 1\} \\ \end {split}\]

    1-C）パブリックキーの計算

    そして、Aは$g^{d_A}\ (mod\ n)$を計算してBに送り、同様にBは$g^{d_B}\ (mod\ n)$を計算してAに送ります。つまり、$g^{d_A}\ (mod\ n)$と$g^{d_B}\ (mod\ n)$が、それぞれのパブリックキー$e_A$と$e_B$となるわけです。

    \[\begin {split} e_A = g^{d_A} \pmod n \\ e_B = g^{d_B} \pmod n \\ \end {split}\]

  2. 共通となるキーの計算

    AとBは、お互いに相手から受け取ったパブリックキーに対して、それぞれのシークレットキーを使って以下の計算を行います。

    \[\begin {split} k_A = (e_B)^{d_A} \equiv (g^{d_B})^{d_A} \pmod n \\ k_B = (e_A)^{d_B} \equiv (g^{d_A})^{d_B} \pmod n \\ \end {split}\]

    ここで、$k_A = g^{d_Bd_A} \equiv g^{d_Ad_B}\ (mod\ n) = k_B$となることから、AとBのあいだのみで共通のキーを計算することができた、ということになります。

DHKEの安全性と前方秘匿性（Forward Secrecy）

さて、DHKEの暗号スキームとしての正しさは上記のステップ2で述べた通りですが、その安全性については、パブリックパラメーター$(n,g)$と両者のパブリックキー$(e_A, e_B)$のみが与えられたときに、それらに紐づいたプライベートキー$d_A$または$d_B$を知らない限り、$k = k_A = k_B$を効率的に計算することができないという仮定に基づいています。これは言い換えると、$\{n, g, e\}$が与えられたときに$e=g^d\ (mod\ n)$を満たす$d$を求めることは難しく、$\{n, g, g^{d_A},g^{d_B}\}$からは$g^{d_{A}d_{B}}$を効率的に計算することができない、という2つの仮定が存在するということになります。ここで、前者はDLPとして、後者はディフィー・ヘルマン問題（Diffie-Hellman Problem・DHP）という不可逆性をもつとされる数学的問題として知られていますが、DLPが効率的に解けるとDHPが簡単に計算できる一方で、DHPが効率的に解けてもDLPが計算できるとは限りません。つまり、DHKEの根底にあるセキュリティーアサンプションは、特定のセッティング（e.g., 十分に大きな素数$n$を法とした乗法群とその原始根$g$）におけるDHPの計算複雑性に拠っていることになります。

これまでみてきたように、DHKEが生成するキーはプライベートキーの組み合わせによって決定されるため、通信・セッション（Session）が確立されるごとに異なるプライベートキーを使用すれば、毎回異なるキーを生成することができます。このように、セッションごとに違うキーを生成するようなスキームは、常に同じキーを使用するStatic-DHKE（S-DHKE）と対比して、Ephemeral-DHKE（E-DHKE）として知られており、特にE-DHKEでセッションごとに生成されるキーは、セッションキー（Session Key）あるいはエフェメラルキー（Ephemeral Key）と呼ばれています。E-DHKEは、前方秘匿性（Forward Secrecy）という性質を満たしており、これは、たとえセッションキーやセッションキーを生成するためのプライベートキーが悪意のある第三者に漏れてしまった場合でも、それ以前のセッションにおける暗号文が復号できないことを意味します。少し見方を変えると、秘密鍵暗号のみでは、シークレットキーが漏れてしまうと過去の暗号文も全て復号できてしまうという欠点を、E-DHKEなどの前方秘匿性を持った公開鍵暗号ベースの鍵交換アルゴリズムを使えば補うことができる、ということになるでしょう。

DHKEをキー生成のステップとして直接的に組み込んだ暗号スキームとしては、エルガマル暗号（ElGamal Encryption）と呼ばれる公開鍵暗号ベースの暗号化スキームが有名ですが、先に説明したワンタイムパッド（OTP）や、AES（Advanced Encryption Standard）と呼ばれる暗号規格を満たす暗号化スキームなど、あらゆる秘密鍵暗号ベースのスキームはDHKEと組み合わせて用いることができます。ただし、DHKEは認証の仕組みではないため、メッセージ認証コード（MAC）を用いたメッセージの認証や、RSAなどの電子署名アルゴリズム（DSA）と組み合わせることで、お互いに認証を行ったうえでキー生成を行うことができるようになります。例えば、HTTPSプロトコルで実際に使われているTLS（Transport Layer Security）として知られる暗号プロトコルでは、TLS証明書（TLS Certificate）と呼ばれる電子署名されたサーバーに関する証明書を用いて通信する相手が想定した相手であると確認したうえでキーの生成を行い、それ以降の通信ではそのキーを用いてメッセージの暗号化とMACによるメッセージの認証を行うという仕組みが採用されています。

二世代の暗号プリミティブ

“Works of art make rules; rules do not make works of art.”

Claude Debussy (1862 - 1918)

（図7: 二世代の暗号プリミティブとそれぞれの依存関係）

これまで紹介してきた暗号プリミティブや暗号スキームを振り返ってみると、暗号学的ハッシュ関数によるデータのランダム化や、タグや電子署名による認証、二者間を想定した暗号化など、限定された枠組みの中で設計されているものがほとんどでした。これは言い換えると、特定の目的に最適化することと引き換えに、スキーム自体の柔軟性が低くなり、結果として用途（i.e., ユースケース）が限定されてしまうことを意味します。もちろん、これらのスキームもうまく組み合わせることで、より細かいユースケースに対応することができますが、そうするとスキーム全体としての複雑性が増したり、セキュリティーアサンプションが増えるなど、理想的ではない側面も持ち合わせています。しかし、近年（特に2010年前後〜現在）における暗号理論とその実装技術の発展や、コンピューター自体の処理能力の向上によって、これまでは理論的にしか存在し得なかったような暗号プリミティブが次々と現実のものとなってきています。ここで、RSA暗号やディフィー・ヘルマン鍵交換（DHKE）に代表される、ユースケースを限定した暗号スキーム群を第一世代の暗号プリミティブとすると、それらのスキームの制約を緩めたり機能を拡張したりして、より汎用的な用途に利用できるようにした暗号スキーム群は第二世代の暗号プリミティブと捉えることができます。このブログシリーズのメインテーマであるゼロ知識証明（Zero-Knowledge Proof）も第二世代に分類できますが、これらの次世代の暗号プリミティブは、その汎用性と柔軟性の高さから、プログラム可能な暗号技術（Programmable Cryptography）と表現されることもあります。ここからは、第二世代の暗号プリミティブにはどのようなものがあるのかをみていきましょう。

マルチパーティー計算（Multi-Party Computation・MPC）

この記事の冒頭で述べたように、暗号という概念の根本的な目的は秘密を安全に所有することですが、秘密（コンピューターにおいては秘匿したいデータ）の所有とは、個人による所有と複数人による所有のふたつに大別でき、後者についてはさらに、1）同じデータを複数人がそれぞれ所有する方法と、2）ひとつのデータを分割して複数人でデータの一部を持ち合う方法とに分類できます。1については、これまで紹介してきたような暗号プリミティブで達成することができますが、2については、秘密分散（Secret Sharing）と呼ばれる暗号プリミティブが必要になります。秘密分散は様々なスキームで実現することができ、例えば加法的秘密分散（Additive Secret Sharing）と呼ばれる手法では、あるデータ$X$を$X = x_1 + \cdots + x_{n} = \sum_{i=1}^{n}x_i$で表されるような$n$個の$x_i$に分割します。このように秘密分散においては、分割されたデータに対して特定の演算を行うことで元のデータが復元できるという性質が担保されており、この暗号プリミティブを元にすると、秘匿マルチパーティー計算（Secure Multi-Party Computation・Secure MPC）あるいはより一般的にマルチパーティー計算（MPC）と呼ばれる暗号プリミティブを構築することができます。

MPCは、それぞれが持つデータを明らかにすることなく、複数人で何かしらの計算を正しく行うことを目的とした暗号プリミティブです。この仕組みは、紛失通信（Oblivious Transfer）や秘匿回路（Garbled Circuit）と呼ばれる暗号スキームを中心に設計されますが、これらのスキームはこれまで取り上げてきたスキームとは異なり、やりとりを行う当事者以外の第三者的な攻撃者だけでなく、やりとりを行う当事者内での攻撃者も想定する必要があります。この想定が必要となる背景は、例えばじゃんけんについて考えてみるとわかりやすいでしょう。人間同士が対面でじゃんけんを行うことは簡単ですが、コンピューター同士の通信を介すと、お互いに相手の出した手によって自分の手を変えるなどといった不正を行うことが可能になるのです。MPCのユースケースは幅広く、例えばDHKEについても、お互いのシークレットキーを明らかにすることなく共通のキーを計算する暗号スキームであると捉えると、MPCの一種であるといえます。また、閾値暗号（Threshold Encryption）と呼ばれる暗号化スキームでは、秘密分散を用いてシークレットキーを$N$人に分配し、$M\ (M \leq N)$人以上が復号に同意しないとシークレットキーが復元できず、暗号文の復号ができない、といった制約をつけることも可能になります。

完全準同型暗号（Fully Homomorphic Encryption・FHE）

RSA暗号について振り返ってみましょう。RSA暗号における暗号文は$C=M^e\ (mod\ n)$で計算されるため、暗号化したいメッセージを$M_A$と$M_B$とすると、暗号文$C_A$と$C_B$はそれぞれ以下のように計算されます。

\[\begin {split} C_A = (M_A)^e \pmod n \\ C_B = (M_B)^e \pmod n \\ \end {split}\]

ここで、元のメッセージ$M_A$と$M_B$を掛けた値に関する暗号文$C_{AB}$は、それぞれの暗号文$C_A$と$C_B$を掛けた値と同一になることがわかるでしょう。

\[\begin {split} C_{AB} &= (M_A * M_B)^e \pmod n \\ &\equiv (M_A)^e * (M_B)^e \pmod n \\ &= C_A * C_B \\ \end {split}\]

これは言い換えると、RSA暗号で暗号化したデータに対する乗算の結果を復号すると、元のデータに対する乗算の結果と等しくなる、つまり、RSA暗号は乗算に関して暗号化したままの正しい計算を可能にすることを意味します。この性質は、乗算に関する準同型写像あるいはホモモーフィズム（Multiplicative Homomorphism）と呼ばれ、同様に加算に関してのみホモモーフィック（Additively Homomorphic）であるパイエ暗号（Paillier Encryption）などの暗号化スキームも存在します。このホモモーフィズムという性質をより厳密に表現すると、2つの同じ数学的性質をもった構造（e.g., 群）のあいだで任意の演算の正しさが保持されることを指しますが、ここで暗号化を行う関数を$Enc$、暗号化するメッセージを$(x, y)$とすると、任意の計算 $\cdot$ について、以下のように一般化することができます。

\[Enc(x\ \cdot\ y) = Enc(x)\ \cdot\ Enc(y)\]

さて、上記の等式について、加算あるいは乗算のみに関して満たすような暗号スキームを部分準同型暗号（Partially Homomorphic Encryption・PHE）と呼びます。一方でより汎用的に、任意の長さの計算に関して少なくとも加算と乗算の2つの演算が構造間で保持されるような暗号スキームを完全準同型暗号（Fully Homomorphic Encryption・FHE）と呼びます。この性質から、FHEはデータを暗号化したまま任意の計算を正しく行うことを可能にする暗号スキームの総称として用いられており、これまでにRing-LWE（Ring Learning with Errors・RLWE）などの問題の数学的不可逆性をベースに、BGV/BFVやCKKS、TFHEといった複数のスキームが提案・実装されてきました。FHEのユースケースもMPCと同様に幅広く、例えば、あるAIのモデルに対してFHEで暗号化されたデータを与えることで、データを暗号化したままでもAIモデルによる予測や分類などができるようになります。また、FHEをベースにしてMPCの暗号スキームを構築できることも明らかでしょう。

ゼロ知識証明（Zero-Knowledge Proof・ZKP）

コンピューターにおける計算とは、あるインプットから何かしらのアウトプットを生成する関数の実行と捉えることができます。ここで、MPCとホモモーフィズムの仕組みを応用すると、任意の関数に対するインプットを秘匿しつつ、関数が定義された通りに正しく実行されたという検証可能な証明を生成することを可能にする暗号プリミティブを作ることができます。このようなスキーム群は、総称してゼロ知識証明（Zero-Knowledge Proof・ZKP）と呼ばれており、計算に用いるデータを秘匿しつつ、任意の計算に関する完全性（Computational Integrity）を保証できることから、トラストレスな環境であるブロックチェーンをはじめとして様々なユースケースに利用されています。

例えば、Ethereum（厳密にはEthereum上のL2チェーン）におけるゼロ知識ロールアップ（Zero-Knowledge Rollup・zkRollup）と呼ばれる仕組みでは、トランザクションによる状態遷移をEVM経由でオフチェーン（i.e., チェーン外）で計算し、その計算が正しく実行されたという証明のみをZKPとして検証できる形でオンチェーン（i.e., チェーン上）に載せることで、複数のトランザクションをひとつのトランザクションにまとめ、トランザクションの低コスト化とブロックチェーンとしてのスケーラビリティーの向上を実現しています。また、ブロックチェーン以外でも数多くのユースケースが考案されており、身分証明プロセス（e.g., KYC）において必要以上の情報を開示しないようにする仕組みであったり、FHEで暗号化されたデータに関する計算の証明と検証を可能にするVerifiable FHE（vFHE）という暗号スキームであったりと、その汎用性の高さから今後も新しいユースケースが生み出されていくことは想像に難くありません。

関数型暗号（Functional Encryption・FE）

これまで紹介してきた暗号化スキームでは、シークレットキーを用いると暗号化されたデータを復号することができました。しかしこれは別の見方をすると、シークレットキーさえあれば、暗号化されたすべてのデータを復号できるということになるため、想定するシチュエーションによっては、必要とされる以上のデータまで復号されてしまうという欠点にも繋がります。そこで復号の対象となるデータを絞り込むためには、あるひとつの暗号文に対して、それぞれ復号の結果が異なるような複数のシークレットキーが必要になることがわかるでしょう。ここで、暗号文とシークレットキーの関係性を任意の関数で表すことによって、より細かい粒度の復号を可能にする暗号化スキームを関数型暗号（Functional Encryption・FE）と呼びます。FEは、暗号化するメッセージを$M$、パブリックキーを$e$、暗号化を$Enc$、関数を$f$、関数$f$に関するシークレットキーを$d_f$、復号を$Dec$とすると、以下の式を満たすような暗号化スキームといえます。

\[Dec_{d_f}(Enc_e(M))=f(M)\]

これはつまり、FEにおいては、関数に対してシークレットキーが生成され、それを用いて復号を行うと、紐づいた関数の元のメッセージに関する計算結果のみが得られるということを意味します。ここで、復号の結果である$f(M)$自体は、FHEを用いて$Enc_e(M)$から$Enc_e(f(M))$を計算し復号することでも得られますが、FEで実現したいのは$M$を特定の関数で評価した結果のみが復号される（FHEのように$Enc_e(f(M))$は計算されない）仕組みであるので、両者は暗号スキームとしての意図が明確に異なります。FEの仕組みを応用すると、パスポート番号などの個人を識別できるユニークなIDを元に復号の粒度が管理できるIDベース暗号（Identity-Based Encryption・IBE）や、IBEをより一般化して特定の属性を満たしている場合のみ復号を可能にする属性ベース暗号（Attribute-Based Encryption・ABE）といった、より柔軟な復号ロジックを備えた暗号化スキームを実現することができます。

ウィットネス暗号（Witness Encryption・WE）

FEを含め、公開鍵暗号ベースの暗号化スキームでは、パブリックキーを用いれば誰でも暗号化を行うことができますが、一方で、復号を行うことができるのはシークレットキーを知っているものに限定されていました。このような公開鍵暗号におけるキーの保有という制約を緩め、特定の条件を満たすデータを持つものであれば誰でも復号できるという仕組みを可能にするのが、ウィットネス暗号（Witness Encryption・WE）と呼ばれる暗号化スキームです。WEは、先に述べたような計算不可逆性をもつとされている任意の数学的問題（厳密にはNPと呼ばれる計算複雑性クラスに属するYes/Noで回答可能な決定問題）とその解の関係性をもとに考案されたスキームで、NP問題に対するステートメント（問題の定義）をパブリックキーとして、NP問題に対する解をシークレットキーとして利用できるようにしたものです。しかし、2024年時点では、一部のNP問題に対する効率的な実装は存在するものの、任意のNP問題に対するプラクティカルな実装はなく、未だ理論的な範囲に留まっているといえます。WEは、公開鍵暗号におけるキーペアの関係性を汎用化した仕組みであるとも捉えられるため、その汎用的な実装が実現することによる暗号領域全体に対する影響は、非常に大きなものになると予測できます。

識別不可能性難読化（Indistiguishability Obfuscation・IO）

暗号学的ハッシュ関数は、いわば与えられたデータを元のデータが識別不能な形に変換するような暗号プリミティブです。一方で、任意の計算つまり関数について、関数自体の機能性を損なわずに、元の関数を表すアルゴリズムやプログラムが識別不能な形に変換することを、ソフトウェアの難読化（Software Obfuscation）と呼びます。あらゆる計算を難読化できる汎用的な難読化スキームが構築できないことは証明されていますが、他方で、制約を緩めるとそういった性質をもつ暗号プリミティブが構築できることも上記と同じ論文で示されており、そのようなプリミティブは識別不可能性難読化（Indistinguishability Obfuscation・IO）として知られています（また2020年には標準的な仮定に基づくIOの具体的なスキームも初めて示されました）。ここで、IOを可能にするソフトウェア$O$は、同じ機能性をもった同じサイズの任意の計算を表す2つの論理回路（Logical Circuit）である$C$と$C’$がインプットとして与えられたときに、（十分な計算資源をもつ攻撃者視点で）どちらがどの回路から生成されたものであるかを識別することができないような$O(C)$と$O(C’)$を生成することができるものと定義されます。

IOに関するプラクティカルな実装は現時点では存在しませんが、汎用的な実装が実現した暁には、ほぼ全ての暗号プリミティブに影響を与えるような暗号プリミティブとなると考えられています。例えば、シークレットキーのみを用いる秘密鍵暗号に対して、数学的な不可逆性を元にパブリックキーの概念を付け足したものが公開鍵暗号であるわけですが、この変換はIOの仕組みを用いても実装することができます。要するに、メッセージ$M$に対してパブリックキー$e$を用いた暗号化$Enc_e(M)$を計算する代わりに、$M$から（回路にハードコードされた）シークレットキー$d$を用いた暗号化$Enc_d(M)$への変換を行う回路$C$を難読化する$O(C)$をパブリックキーとして使用することで、秘密鍵暗号のスキームを公開鍵暗号のスキームへと変換できるようになるのです。さらにこの仕組みを応用すると、FHEやFEなどの暗号スキームもすべて、難読化を行う$O$を介して計算を変換することで柔軟に実現できることがわかるでしょう。このように、IOの仕組みは、現時点で想定できる暗号プリミティブの最後の欠けたピースを埋める役割を果たすとされていますが、先述の通りプラクティカルな実装がほとんど存在しないため、WEと同じく、未だ理論的な暗号プリミティブのひとつとして認識されています。

現代暗号技術と量子コンピューターの関係性

このセクションでは、第二世代として捉えられる汎用的な暗号プリミティブについてひと通り紹介してきましたが、最後に、二世代に共通する脅威である量子コンピューター（Quantum Computer）について触れておきましょう。多くの暗号化プリミティブは、何かしらの数学的問題に関して、古典的な（量子コンピューターでない）コンピューターの使用を想定した場合の計算不可逆性を元に設計されていますが、一部の問題については、量子コンピューターを用いると効率的に解けることが発見されています。そのような問題に依存する暗号化スキームは、量子コンピューターの存在によって安全性が損なわれる危険性を孕んでいるといえますが、逆に量子コンピューターに対する耐性（Quantum Resistance）をもつと信じられているRLWEなどの問題も数多く提案されています。ここで、量子コンピューター耐性をもった問題をベースに設計された暗号プリミティブをそれ以外と対比して、ポスト量子暗号（Post-Quantum Cryptography）と呼ぶことがあります。古典的な数学的問題に対する量子コンピューターアルゴリズムを効率的に実装できるような、実用的な量子コンピューターが誕生する未来がいつになるのかはわかりませんが、ポスト量子暗号であることは、すべての暗号プリミティブに共通する別の角度での改善点といえるでしょう。

Vol.2では、そもそも暗号とはなにかという素朴な疑問の考察から、現代の暗号技術の全体像や暗号プリミティブの分類、その仕組みと安全性の根拠を解説しました。暗号領域における独特な言い回しや概念、数学の登場機会も多く、理解し切るのに時間がかかるかもしれませんが、ここでカバーした内容は、第二世代として紹介した暗号スキームだけでなく、まだ考えられてもいないような未来の暗号技術への理解にも繋がるでしょう。Vol.3では、これまで解説してきたEthereumや現代の暗号技術に関するコンテキストを踏まえ、ゼロ知識証明（ZKP）について詳説します。特に、zkSNARK（Zero-Knowledge Succinct Non-interactive ARgument of Knowledge）やzkSTARK（Zero-Knowledge Scalable Transparent ARgument of Knowledge）として知られる2つのZKPのスキームを中心に、ZKPを構成する暗号プリミティブの性質や仕組み、ZKPとEthereumを組み合わせたユースケースや最新の最適化手法について深掘っていきます。

参考

このブログは、以下のリソースを参考にして書かれています。