はじめに

現在私たちが利用している暗号化技術は「安全」であることが保証されています．
では，この 「安全」 とはどのように定義されるのでしょうか？
今回から数回に渡る記事では公開鍵暗号方式の一つであるElGamal暗号を例に安全性を証明することで，情報セキュリティの暗号理論における安全とは何か，雰囲気だけでも掴んでもらうことを目標とします．

現代暗号に触れたことある人にとっては当たり前すぎる記事かもしれませんが，暗号理論を研究する身として安全性証明は非常に重要であり，なおかつ非常に難しいため，私自身の備忘録としてこの記事を書きます．

本当は1つの記事で安全性証明まで行うつもりでしたが，煩雑になりすぎるので分けることにしました．ごめんなさい．

今回の記事では「安全」という言葉を定義することをゴールとします．

ElGamal暗号の概要

まずどのような暗号なのか知るためにWikipediaの概要から見ていきます．

ElGamal暗号（エルガマルあんごう、ElGamal encryption）とは、位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。1984年Taher Elgamalが発表した。
(Wikipediaより引用)

今回の記事内では，ElGamal暗号の具体的なプロトコルには触れません．
安全性の根拠として非常に重要となる離散対数問題に触れていき，これを説明します．(群論などの一般的な代数学の説明は省きます)

離散対数問題(Discrete Logarithm Problem: DLP)

素数$p$，位数が$p$となる乗法巡回群$\mathbb{G}$の生成元$g$が与えられた時に，$g^a\ {\rm{mod}} \ p$となる$a$を求めよ

離散対数問題の具体例はこちらの記事が参考になります．

そして，暗号理論の文脈では以下の仮定を利用します．

離散対数問題の仮定

離散対数問題を多項式時間で求めるアルゴリズムが存在しない(と仮定する)

仮定の妥当性

この仮定の妥当性を見ていきます．
実際には離散対数問題が多項式時間で解けるかどうかは判明していません．しかし，現在までに多項式時間で離散対数問題を解くアルゴリズムが発見されていないことから，存在しないことを前提とした安全性を示しています．
計算量理論の観点で言えばこの問題がPクラスの問題かもしれませんし，もっと上のクラスの問題かもしれません．

仮定の意味を考える

ElGamal暗号の概要から，次の一文を取り出します．
位数が大きな群の離散対数問題が困難であることを安全性の根拠とした公開鍵暗号の一つである

上記の文における「離散対数問題が困難である」が意味することは，先程の仮定における「離散対数問題を多項式時間で求めるアルゴリズムが存在しない」に該当します．
ここから反対に，「ある問題(を解くこと)が効率的である」とは「ある問題を多項式時間で求めるアルゴリズムが存在する」となります．

離散対数問題の一般的な説明では
「$(g,a,p)$から$g^a\ {\rm{mod}} \ p $を求めることは容易で，$(g,p,g^a\ {\rm{mod}} \ p)$から$a$を求めることは困難である」
などのように説明されていることが多いと思います．説明の中に含まれる 「容易」，「困難」 という言葉の裏には求解アルゴリズムの計算量が関係しています．

「安全」の本質

以上をまとめると安全性とはどのように定義されているのか見えてきます．

暗号プロトコル上のある公開の情報から秘密の情報(例えば，公開鍵から秘密鍵，暗号文から平文など)を求めることが困難である．すなわち，ある公開の情報から秘密の情報を多項式時間で求める事ができない．

これが「安全」という言葉の定義となります．

今回のまとめ

ElGamal暗号における安全性の根拠となる離散対数問題の仮定を例に「安全」とはどのように定義されているのか触れていきました．
今回の内容は自然言語による定義で，「理論といえば数式！」のような話はあまり出てきませんでしたが，次回以降は数式による定義が増えていきます．

次回の記事ではElGamal暗号のプロトコルを説明し，実際に「安全」であることを証明していきます．