係数の掛け算問題

割り算ができない世界では次のような未証明の仮説がある。

• 数 $${na, ma, a}$$ から $${nma}$$ を計算できない

割り算のできない世界では、この仮説を係数の掛け算問題と呼んでいる。割り算が使えれば $${nma = (na \div a)ma}$$ もしくは $${nma =mna = (ma \div a)na}$$ (この世界でも掛け算は可逆）とすればいいが、実はそれ以外に計算方法が無いのかもしれないということがこの仮説が未証明だと言うことである。

公開鍵暗号

世界中の数学者が取り組んできたのにも関わらず、この係数の掛け算問題は今のところ否定されていないので、割り算のできない世界ではこの仮説は事実上真として扱われている。

係数の掛け算問題を真として扱っている技術としては、次のような公開鍵暗号アルゴリズムがある。

• 秘密鍵 ランダムに選んだ数 $${n}$$

• 公開鍵 ランダムに選んだ数 $${a}$$ と $${na}$$ のペア $${(a, na)}$$

• 暗号化 平文を数 $${m}$$ とし、ランダムに選んだ数 $${r}$$ と公開鍵を使った、ペア $${(ra, m + rna)}$$

• 復号化 秘密鍵 $${n}$$ を使って、暗号文の $${ra}$$ から $${n(ra) = rna}$$ を計算し、$${m = (m + rna) - rna}$$ で平文を得る

復号化には $${rna}$$ が必要なのだが、秘密鍵を知らない第三者が $${rna}$$ を計算するためには、公開されているうちで意味のある情報 $${a, na, ra}$$ から計算する必要がある。これはまさに係数の掛け算問題を解く必要があるということなので、秘密鍵を知らない第三者は暗号を解読できない。

Elgamal暗号

ところで、この公開鍵暗号の説明は、巡回群のアルゴリズムとして一般化したElgamal暗号を加法的に説明したものである。群論を知らない人は何を言っているのかは分からないと思うが、要するに巡回群という数学を使えば、割り算ができない世界（割り算が難しい世界）というのが実際に作れるので、上の公開鍵暗号は実際に使えるというわけである。

具体的には巡回群というのは複数あって、その中に都合のいい性質をもったものがあるという話である。割り算が難しいという性質はその巡回群上の離散対数問題と呼ばれ、上で係数の掛け算問題と呼んだ問題が難しいという仮定はその巡回群上でのCDH仮定と呼ばれる。

また、Elgamal暗号が本当に安全と言えるためにはDDH仮定というものもいるのだが、これは微妙な話なのでここでは割愛する。

対数のできない世界

ところで離散対数問題の離散というのは巡回群のある性質を表しているのだが、なぜ割り算が難しいのに対数なのかというと、この記事で説明した足し算は普通は掛け算、引き算は割り算として紹介されるからである。この記事での割り算というのは単に引き算の連続としての意味で使っていたので、普通の説明では割り算の連続、対数の計算になるというわけだ。

つまり、この記事の割り算ができない世界とは普通は対数のできない世界として説明されるものだというわけだが、この辺りのことに興味がある人は実際にElgamal暗号の説明を見てほしい。もちろんこの記事と違って掛け算で説明されているのだが、実はElgamal暗号は指数法則によって掛け算を指数同士の足し算としても捉えられるので、そこに注目すればこの記事内容は結構役に立つと思う。