クラウドサービスに最適な暗号方式とは？――暗号化したまま計算する「準同型暗号」：クラウド時代の暗号化技術論（4）（1/2 ページ）

情報漏えいの懸念があるクラウドの世界では、データを暗号化して保持するのが安全です。しかし従来の暗号方式では、暗号化されたデータを計算するときにいったん復号を行う必要があり、ネットワークやクライアントマシンに負荷がかかってしまいます。今回はこの問題を解決するための「準同型暗号」について解説します。

[光成滋生，＠IT]

連載目次

準同型暗号とは？

　今回からいよいよ近年の暗号技術を見ていきます。まず、「準同型暗号（HE：Homomorphic Encryption）」を取り上げます。“準同型”というのは耳慣れない言葉かもしれませんが、ここでは「暗号化したまま計算ができる方式」を意味します。

　例えば、ウエアラブルコンピューターを用いて身長、体重、心拍数などの個人情報を集約するサービスを考えます。これらのデータをそのまま外部のクラウドストレージに置くのは、情報漏えいのリスクがあり、不安です。安全のためには、データを暗号化する必要があります。

　ところが、データを暗号化してしまうと、平均や分散、相関などの計算処理ができません。従来の暗号方式の場合、一度データを手元にダウンロードし、復号してから計算する必要がありました。しかしデータが増えればネットワークの帯域が必要になりますし、クライアントの負荷も高まります。

　これに対して準同型暗号を使うと、クラウド上で暗号化したまま統計処理を行い、そのまま暗号化された結果だけを取得できます。あとはクライアントで復号するだけでよいのです。こうすれば、クラウドにストレージだけでなくCPU処理も委譲でき、通信量も減らせます。このように、準同型暗号はクラウドサービスにとってとても都合のよい暗号方式なのです。

図1 準同型暗号の利点

ヒントは第2回の「ElGamal暗号」

　準同型暗号の概略が分かったところで、その仕組みを紹介します。本来暗号化とは、元の平文の情報が一切漏れないように、情報を“ごちゃごちゃにかき混ぜる”ものです。そのように暗号化された情報をそのまま計算に使用するには、どうしたらよいのでしょうか。

　実は、ヒントは連載第2回の「頑強性」の話にありました。第2回のところで「ElGamal暗号は復号こそできないが、値を10倍にするなどの改ざんを許してしまう。つまり頑強性を持っておらず、安全ではない」という話をしたのを覚えていますか。これは裏を返せば、「暗号化したまま10倍できる」という準同型の性質ではありませんか！

　実際に、連載第3回で紹介した「楕円ElGamal暗号」を用いて、2個の平文M₁、M₂の暗号文を見てみましょう。M₁、M₂の暗号文は、楕円曲線の点Pと公開鍵K_A=aP、乱数r₁、r₂を用いて、

　Enc(M₁)=(r₁P,M₁+r₁K_A),
　Enc(M₂)=(r₂P,M₂+r₂K_A)

と表せました。r′=r₁+r₂とおいて暗号文のそれぞれの成分を足すと、

　Enc(M₁)+Enc(M₂)=(r′P,(M₁+M₂)+r′K_A)
　　　　　　　　　　= Enc(M₁+M₂)

となります。M₁とM₂の暗号文を足したら、M₁+M₂の暗号文になりました。このような性質を準同型といい、特に加法ができるので「加法準同型暗号」といいます。

加法準同型暗号の実用例

　このように、ElGamal暗号は加法準同型暗号として利用できます。例えば、各自が0か1を暗号化して投票し、暗号化したまま総和を取れば簡易電子投票を実現できます（実際にはいろいろ複雑なプロトコルを組み合わせる必要があります）。頑強性を持たないことは別の手段で補います。

　より実用的な例として、産業技術総合研究所（以下、産総研）の「化合物データベースの秘匿検索技術」を紹介します。

　企業の研究部門では、今何を研究しているのかを秘密にしたいという理由で、外部の検索サービスの利用を禁止しているところがあるそうです。検索キーワードから、現在の関心事をライバル会社に知られてしまう恐れがあるからです。

　新薬の研究においても、どのような化合物を考えているのか外部に知られるのは好ましくありません。例えば、化合物のさまざまな情報をデータベースにして販売している会社があります。研究者（クライアント）はそれらのデータベースが自分の研究に活用できるのかを検討したいのですが、データベースの販売会社に研究対象物を教えたくはありません。逆に販売会社（サーバー）は、可能な限りデータベースの中身を開示せずに売りたいと考えます。

図2 「化合物データベースの秘匿検索技術」の仕組み

　産総研の技術を利用すると、この相反する両者の要求に応えることができます。検索対象の化合物を秘密にしたまま、データベースの中にその化合物に類似したものがいくつあるかという情報だけを取得できるのです。類似物が多くあれば、研究者はそのデータベースの購入を検討するでしょう。

　この技術の中の、暗号化したまま類似度を計算する部分に加法準同型暗号が使われています。その実装には筆者も関わらせていただきました。加法準同型暗号を使用している部分の実装はGitHub上で公開されています。