紹介したのは加法準同型暗号でした。「加法と乗法の両方を同時に実現する」準同型暗号は長らく実現していませんでした。0と1からなる「2で割った余りの世界」では、乗算は論理積(AND)、加法は排他的論理和(XOR)に相当し、ANDとXORの組み合わせだけで任意の演算を構成できることが知られています。そのため、加法と乗算の両方ができると、“完全”準同型暗号といわれるのです。式で書くと任意の関数fに対して、f(Enc(m))=Enc(f(m))と表現できます。Gentry)氏が初めて実現しました。ジェントリー氏の作ったFHEは、鍵や暗号文が数百MバイトからGバイト単位と巨大で、実用的とはとても呼べませんでしたが、このブレークスルー以降、研究は急速に進んでいます。いえ、任意回の加法と乗算が可能という性質を実現するのはなかなか大変で、気軽に利用できるようになるのはまだしばらく先でしょう。ところで、準同型暗号の応用例を考えると、分散、相関、ベクトルの内積などを暗号化したまま処理したい場面が多いことが分かりました。これらの計算は、以下のように、2個の数値を一度だけ乗算したものを足し込むという操作で表現できます。HE)」にターゲットを絞った研究もされています。表2は各暗号において可能な演算と性能をまとめたものです。可能な乗算回数が増えるほど、できる計算の種類は増えますが、処理性能が悪くなります。任意の演算SHEやFHEの実用化を目指した研究としては、例えば次のようなものがあります(各大学、研究所が活発に研究していますので、ここで挙げたものはそのごく一部です)。指紋や静脈データといった生体認証の照合に必要な内積演算を高速化しています。複数の企業間での医療や生化学データなどの機密情報のデータ分析にも利用できるだろうとのことです。研究』アルゴリズムを改良した高速なFHEを提案、実装しています。FHEを使用して作ったAESの回路に、FHEで暗号化したデータを入力し、「FHEで暗号化したデータをさらにAESで暗号化したもの」を出力するということも、数十秒程度で可能だそうです。暗号化したままデータのセキュリティレベルを更新することを可能にしています。従来、データの暗号方式を更新するには、データを一度ダウンロードして復号し、新しい方式で暗号化し直してからアップロードする必要がありました。NICTの手法では、データを暗号化したまま、クラウド上で鍵長を長く暗号化し直せるとのことです。今のところ、SHEやFHEは「格子」を使って実現されるものが主流です。格子とは、障子やジャングルジムなどのように空間を等間隔に区切ったものです(直角である必要はありません)。非常に大ざっぱで厳密ではないのですが、概要を説明します。格子を使った準同型暗号は、暗号文を格子点の上で表現するときに誤差を付与します。xを平文の情報を正しく持つきれいな値、εを誤差とすると、暗号文はx+εの形をしています。秘密鍵を持っている人は誤差を取り除いて元の平文を復号できますが、秘密鍵を知らない人は誤差を取り除くことが困難で、解読できません。2個の暗号文x+ε1、y+ε2を用意して、これらを足します。(x+ε1)+(y+ε2)=(x+y)+(ε1+ε2)これは正しい値(x+y)と誤差(ε1+ε2)の形をしています。そこで秘密鍵を使うと、x+yを取り出せます。これが加法準同型暗号に相当します。次に、これらの暗号文を掛けてみます。(x+ε1)(y+ε2)=(xy)+(ε1y+ε2x+ε1ε2)ε1、ε2がx、yに比べて小さければ、これも正しい値(xy)と誤差の和という形です。秘密鍵を使えばxyを取り出せます。これが乗法準同型暗号に相当します。加法と乗法ができるので完全準同型を構成できるというわけです。この方式は、何度も計算すると誤差が蓄積してうまく復号できなくなります。そのため、演算回数に制約が発生します。その制約のまま使うのがSHE、さまざまな手法を用いて制約を取り払ったものがFHEです。最後に、量子コンピューターとの関係についても紹介します。RSAや楕円曲線を使った暗号は、将来量子コンピューターが登場すると、効率のよいアルゴリズムを用いて破られるといわれています。格子暗号は、量子コンピューターに対しても安全とされています。そのため格子暗号は、完全準同型を実現できるというだけでなく、耐量子コンピューター暗号としても注目されているのです。今回のまとめ:準同型暗号は暗号化したまま計算できるためクラウドと相性がよい。用いて完全準同型暗号を構築できる。格子暗号は耐量子コンピューター暗号としても注目されている。参考文献——より詳しく学びたい人のために:準同型暗号や格子暗号を一般向けに解説したテキストはまだあまりありません。Web上で閲覧できるものや書籍として入手できるものとしては、以下のようなものがあります。しげお)サイボウズ・ラボ株式会社サイボウズ・ラボ株式会社にてセキュリティとインフラ周りの研究開発に携わる。「数論アルゴリズムとその応用」研究部会(JANT)幹事。近著に「応用数理ハンドブック」(朝倉書店、2013:楕円曲線暗号、ペアリング暗号の項目担当)、「クラウドを支えるこれからの暗号技術」(秀和システム、2015)がある。メールマガジンをご購読ください。申し込みページへITmediaはアイティメディア株式会社の登録商標です。