連載
» 2015年08月13日 05時00分 公開

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

[光成滋生,@IT]
前のページへ 1|2       

完全準同型暗号

 前節で紹介したのは加法準同型暗号でした。これと同様に、暗号化したまま乗算ができる「乗法準同型暗号」というものもあります。しかし、「加法と乗法の両方を同時に実現する」準同型暗号は長らく実現していませんでした。そのような暗号を「完全準同型暗号(FHE:Fully HE)」といいます。

 0と1からなる「2で割った余りの世界」では、乗算は論理積(AND)、加法は排他的論理和(XOR)に相当し、ANDとXORの組み合わせだけで任意の演算を構成できることが知られています。そのため、加法と乗算の両方ができると、“完全”準同型暗号といわれるのです。式で書くと任意の関数fに対して、

 f(Enc(m))=Enc(f(m))

と表現できます。

表1 0と1のANDとXOR
AND(×) 0 1
      0 0 0
      1 0 1

XOR(+) 0 1
     0 0 1
     1 1 0

 2009年、暗号研究者たちの夢であったこのFHEを、クレイグ・ジェントリー(Craig Gentry)氏が初めて実現しました。ジェントリー氏の作ったFHEは、鍵や暗号文が数百MバイトからGバイト単位と巨大で、実用的とはとても呼べませんでしたが、このブレークスルー以降、研究は急速に進んでいます。とはいえ、任意回の加法と乗算が可能という性質を実現するのはなかなか大変で、気軽に利用できるようになるのはまだしばらく先でしょう。

 ところで、準同型暗号の応用例を考えると、分散、相関、ベクトルの内積などを暗号化したまま処理したい場面が多いことが分かりました。これらの計算は、以下のように、2個の数値を一度だけ乗算したものを足し込むという操作で表現できます。

 (a1,…,an)・(b1,…,bn)=a1・b1+a2・b2+…+an・bn

 そこで、これらの処理だけはできるような制限付きの「ちょっとだけ準同型暗号(SHE:Somewhat HE)」にターゲットを絞った研究もされています。表2は各暗号において可能な演算と性能をまとめたものです。可能な乗算回数が増えるほど、できる計算の種類は増えますが、処理性能が悪くなります。

表2 準同型暗号の比較
加算回数 乗算回数 処理性能 計算
従来の暗号 × × 暗号化のみ
加法HE 任意回 × 平均など
SHE 十分な回数 数回 分散、内積など
FHE 任意回 任意回 × 任意の演算

 SHEやFHEの実用化を目指した研究としては、例えば次のようなものがあります(各大学、研究所が活発に研究していますので、ここで挙げたものはそのごく一部です)。

表3 SHE、FHEに関する近年の研究例
発表年 組織 概要
2013 富士通研究所 『世界初!暗号化したまま統計計算や生体認証などを可能にする準同型暗号の高速化技術を開発』
指紋や静脈データといった生体認証の照合に必要な内積演算を高速化しています。複数の企業間での医療や生化学データなどの機密情報のデータ分析にも利用できるだろうとのことです。
http://pr.fujitsu.com/jp/news/2013/08/28.html
2014 NTTセキュアプラットフォーム研究所 『整数上完全準同型暗号の研究』
アルゴリズムを改良した高速なFHEを提案、実装しています。例えば、FHEを使用して作ったAESの回路に、FHEで暗号化したデータを入力し、「FHEで暗号化したデータをさらにAESで暗号化したもの」を出力するということも、数十秒程度で可能だそうです。
http://www.ntt.co.jp/journal/1403/files/jn201403071.pdf
2015 情報通信研究機構(NICT) 『暗号化状態でセキュリティレベルの更新と演算の両方ができる準同型暗号方式を開発』
暗号化したままデータのセキュリティレベルを更新することを可能にしています。従来、データの暗号方式を更新するには、データを一度ダウンロードして復号し、新しい方式で暗号化し直してからアップロードする必要がありました。NICTの手法では、データを暗号化したまま、クラウド上で鍵長を長く暗号化し直せるとのことです。
http://www.nict.go.jp/press/2015/01/19-1.html

「格子暗号」――SHE、FHEの実現方法

 今のところ、SHEやFHEは「格子」を使って実現されるものが主流です。格子とは、障子やジャングルジムなどのように空間を等間隔に区切ったものです(直角である必要はありません)。

図3 2次元格子と誤差付きベクトルの加算

 非常に大ざっぱで厳密ではないのですが、概要を説明します。格子を使った準同型暗号は、暗号文を格子点の上で表現するときに誤差を付与します。xを平文の情報を正しく持つきれいな値、ϵを誤差とすると、暗号文はx+ϵの形をしています。秘密鍵を持っている人は誤差を取り除いて元の平文を復号できますが、秘密鍵を知らない人は誤差を取り除くことが困難で、解読できません。

 さて、2個の暗号文x+ϵ1、y+ϵ2を用意して、これらを足します。

 (x+ϵ1)+(y+ϵ2)=(x+y)+(ϵ12)

 これは正しい値(x+y)と誤差(ϵ12)の形をしています。そこで秘密鍵を使うと、x+yを取り出せます。これが加法準同型暗号に相当します。

 次に、これらの暗号文を掛けてみます。

 (x+ϵ1)(y+ϵ2)=(xy)+(ϵ1y+ϵ2x+ϵ1ϵ2)

 ϵ1、ϵ2がx、yに比べて小さければ、これも正しい値(xy)と誤差の和という形です。秘密鍵を使えばxyを取り出せます。これが乗法準同型暗号に相当します。加法と乗法ができるので完全準同型を構成できるというわけです。

 この方式は、何度も計算すると誤差が蓄積してうまく復号できなくなります。そのため、演算回数に制約が発生します。その制約のまま使うのがSHE、さまざまな手法を用いて制約を取り払ったものがFHEです。

 最後に、量子コンピューターとの関係についても紹介します。RSAや楕円曲線を使った暗号は、将来量子コンピューターが登場すると、効率のよいアルゴリズムを用いて破られるといわれています。しかし格子暗号は、量子コンピューターに対しても安全とされています。そのため格子暗号は、完全準同型を実現できるというだけでなく、耐量子コンピューター暗号としても注目されているのです。

今回のまとめ

  • 準同型暗号は暗号化したまま計算できるためクラウドと相性がよい。
  • 楕円曲線を用いて加法準同型暗号、格子を用いて完全準同型暗号を構築できる。
  • 格子暗号は耐量子コンピューター暗号としても注目されている。

参考文献――より詳しく学びたい人のために

準同型暗号や格子暗号を一般向けに解説したテキストはまだあまりありません。Web上で閲覧できるものや書籍として入手できるものとしては、以下のようなものがあります。


光成滋生(みつなり しげお)

サイボウズ・ラボ株式会社

 サイボウズ・ラボ株式会社にてセキュリティとインフラ周りの研究開発に携わる。「数論アルゴリズムとその応用」研究部会(JANT)幹事。

  • 2004年放送型暗号の実装でIPA未踏スーパークリエータ認定
  • 2005年ストリーム暗号Toyocryptの解読で情報化月間推進会議議長表彰
  • 2010年ベクトル分解問題についての論文で電子情報通信学会論文賞受賞
  • 2015年 Microsoft MVPアワード Developer Securityを受賞

 近著に「応用数理ハンドブック」(朝倉書店、2013:楕円曲線暗号、ペアリング暗号の項目担当)、「クラウドを支えるこれからの暗号技術」(秀和システム、2015)がある。


前のページへ 1|2       

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。