暗号コラム

暗号コラム

第5回 準同型暗号 -秘密にしたまま計算できる暗号-

2016.02.03
東京システムハウス

食べながら痩せたいあなたへ

こんにちは、鈴木です。 食べながら痩せる、運動せずに痩せる、寝ながら痩せるなど虫のいい話を信じて失敗した経験はありませんか? 私も消費カロリーと摂取カロリーのバランスを考慮したり栄養が偏らないようにしなければいけないとわかっているのに手を出して失敗してきました。

さて、ここは鈴木のダイエット事情を暴露する場ではなく暗号コラムです。 暗号は情報を秘匿するために使います。 何故秘匿するのか、それはばれてしまうと困ってしまうほど重要な情報だからなのです。 どうでもよい情報は別に隠す必要はありません。 世の中には、情報を秘密にしたままその情報を活用したいというニーズがあります。 ただえさえ情報を秘密にするのは手間が掛かるのに、その上そのまま活用したいとは 随分と虫のいい話のように聞こえます。きちんと栄養バランスのことを考えないといけません。

ところが、準同型暗号 をという暗号を使えば情報を秘密にしたままその情報を活用できます。 具体的には、準同型暗号を使えば「暗号化したまま計算」ができます。 本当でしょうか?今回は準同型暗号とその性質について書いてみたいと思います。

同型に準ずるとはこれ如何に

「準同型暗号」という名称と「暗号化したまま計算が出来る」という性質がすぐに結びつく人は 恐らく代数学を学んだことがあるのではないでしょうか。 私も準同型暗号というを初めて聞いた時になるほど確かにそうだねと思いました。

数学において 同型 とは2つの異なる集合(ものの集まり)の構造が全く同じということを意味します。 同型に準ずる、 準同型 とはざっくり言えばある数学的性質の構造が同じ、ということを意味しています。1 準同型暗号の場合、平文上での演算と暗号文上の演算が同じ構造をしている、ということになります。 見かけは全く異なっていても、性格や考え方が同じ人がいる…という経験はあったりしますよね。

実は数式からみるとわかりやすい

前回紹介したRSA暗号は準同型暗号としての性質を持ち合わせています。 RSA暗号の暗号化の手順を思い出してみましょう。 各パラメータの意味は「RSA暗号 後編」を参照してください。

暗号化
  1. 暗号化したいメッセージ(自然数)を m とする。ただし、m < n を満たす必要がある。
  2. c = meを計算し、 n で割った剰余を求める。
  3. c を暗号文とします。

ここで、平文を m1, m2と2つ用意してそれぞれ e と n を使って暗号化してみると、

  • c1 = m1e
  • c2 = m2e

となりますね。ここで、c1とc2同士を掛け合わせてみると、

  • c1 * c2 = m1e * m2e = (m1m2)e

となります。 指数の計算がよくわからない、という方は「指数法則」というキーワードで検索してみてください。

また、RSA暗号の復号の手順を思い出してみましょう。

復号化
  1. m' = cd を計算し、 n で割った剰余を求める。
  2. m' を復号文とする。正しい鍵の組み合わせならば m = m' となる。

n, e, d は正しい組み合わせを選択しているので c1 * c2 を復号すると m1 * m2 が求められます。

せっかくなので実例を見てみましょう。

  1. 公開鍵として(e,n)=(5, 21)の2つ組、秘密鍵として(d,m)=(17, 21)を選びます。
  2. 暗号化したいメッセージ(自然数)を m1=3, m2=4 とします。
  3. それぞれ暗号化すると c1=12 , c2=16となります。
  4. c1 * c2 = 192となります。
  5. 19217を21で割った余りは12となります。

ここで重要なのは 平文を m1, m2 を一切復号することなく その2つの積 m1 * m2の暗号文を得る事が出来る事です。 つまり、平文の中身を秘密にしたまま平文同士の計算が出来るのです。 これが準同型暗号のすばらしい性質です。 先程の「準同型」という言葉の観点から眺めると、「平文の世界(整数)における掛け算」と 「暗号文の世界(整数剰余)における掛け算」は似ている、ということです。

可能性、そして限界

準同型暗号を使えば「暗号化したまま計算」という便利なことが実現できます。 例えば、ある業界のライバル企業同士が自分の機密情報を隠したまま統計を取りたい、といったケースでも 準同型暗号を使えば機密情報を隠したまま統計値を算出できます。

また、準同型暗号を使えばセキュアな電子投票を実現できます。 選挙において、誰がどの候補者に投票したかを隠しつつ、最終的に投票数を集計する必要があります。 現実の選挙では選挙箱など物理的な手段で実現していますが、準同型暗号を使えば電子の世界でも投票を実現できます。 実際の電子投票を組み立てるにはもうすこし込み入った方法も必要になりますが、イメージは浮かぶと思います。

虫のいい話をつらつらと述べてきましたが、準同型暗号には限界もあります。 「暗号化したまま計算」というと暗号化したまま四則演算ができるのでは、と思いがちですが、 実は知られている準同型暗号の大体は足し算だけ、掛け算だけ、といった1つの演算だけ可能という場合がほとんどです。 例えば先程のRSA暗号は掛け算はできますが足し算ができません。 Paillier(ペリエ)暗号という公開鍵暗号は足し算は出来ますが掛け算が出来ません。 最近、足し算と掛け算が両方出来る準同型暗号が発見されましたが計算速度が非常に遅くて実用に耐えないものでした。

準同型暗号は現実に役に立ちそうな性質を備えていますが実際に活用されているとは言いがたいです。 理論が美しいのはそれだけでもよいのですがやはり現実世界への応用があるとよりよいです。 そのような応用を目指して我々はおいしいものを食べて日々頑張って生活していきます。

参考文献

  • 楫元 『工科系のための初等整数論入門』 培風館 2000

  1. 厳密には、2つの集合の間に準同型写像がある、とか同型写像がある、ということを意味します。