暗号化されたインデックスとは、暗号化されたキーワードが並んだものです。
同じ平文(キーワード)から同じ暗号文が生成されると、攻撃者は暗号化されたインデックスを見てそれらが同じキーワードだと分かってしまいます。例えば図3では、「文章1と文章3には同じキーワードが登録されている」と分かります。
従って、同じキーワードであっても、暗号化すると異なる暗号文になる方が望ましいといえます。同様に、同じクエリであっても暗号文は毎回異なる方がよいでしょう。これは公開鍵暗号を使うか、共通鍵暗号ならsaltを指定することで可能です。
しかし、そのようにすると、今度は検索の際に暗号化されたキーワード同士の一致判定ができません。第2回で紹介したように、強秘匿性を持った暗号は、「二つの暗号文を見比べても元の平文が同じかどうか分からない」ようになっているからです。
そこでPEKSでは、暗号化されたインデックスから暗号化されたキーワードを探すときに、「落とし戸(トラップドア)関数」というものを使います。
検索を依頼する人は落とし戸関数を使ってキーワードを秘密鍵で暗号化し、生成されたトラップドアの値をサーバーに送ります。サーバーはトラップドアと暗号化されたキーワードからある種の計算をすることで、復号することなく二つのキーワードが一致しているかを判定します。詳細はここでは省略しますが、その計算では第5回で紹介したペアリングが用いられます。こうして検索対象を見つけることができるのです(落とし戸関数の具体的な構成方法については、拙著の中でも紹介しています。興味のある方はご一読いただければ幸いです)。
マイナンバーの扱いには特に注意が求められています。そういった値をコンピューターに保存するときは、ハッシュを使えばよいのではと思われる方がいらっしゃるかもしれません。しかし「安全性を高める」という目的のためにそれをしてはいけません。なぜなら最近のGPGPU(General-Purpose computing on GPU)のハッシュを求める計算能力は極めて高いからです。例えば「GeForce GTX Titan X」というGPU8個のシステムでは、1秒間にSHA-1ハッシュ関数を4.2×1010回計算できるそうです(参考リンク)。
マイナンバーは12桁の数字からなります。ということはGeForce GTX Titan X を使えば、最大1012種類しかないマイナンバーの全パターンをチェックするのに、24秒しかかからないということになります。マイナンバーのSHA-1ハッシュ値が分かると、その程度の時間で元の値が分かってしまうのです。最新のSHA-3を使ったとしても、やはり5分足らずで元の値が見つかってしまいます。
「ハッシュしたから大丈夫」という考えは、入力値の種類が少ないときには危険であることを把握しておきましょう。
検索可能暗号の応用例として、いくつかの企業のニュースリリースを紹介しましょう。2012年、日立製作所は共通鍵暗号をベースに、第4回で紹介した「加法準同型暗号」を組み合わせた検索可能暗号システムを提案しています(参考リンク)。冒頭で紹介したマイナンバーのシステムでも、この技術を利用しているようです。
そして2014年にはそのシステムを応用し、「相関ルール分析」が可能な方式も提案しています(参考リンク)。相関ルール分析を用いると、顧客の購買履歴の中から、「商品Aを購入した人は商品Bも購入することが多い」といった相関ルールを暗号化したまま計算することができます。
2013年には、三菱電機が公開鍵暗号ベースの秘匿検索基盤ソフトウエアを開発しています(参考リンク)。このソフトウエアでは、PEKSの処理速度の問題に対して、数ビットの情報漏れを許容することで高速な検索を可能にしています。
なお、今回紹介したものとは異なる技法を使ったものとして、以下のような技術も開発されています。
2013年、NECはデータベースの情報を暗号化したまま処理できる秘匿計算技術を開発しました(参考リンク)。二つの平文m1、m2にm1<m2という順序が成り立っているとき、それらの暗号文に対してEnc(m1)<Enc(m2)という関係が成り立つ暗号方式を、「順序を保つ暗号方式(OPE:Order-Preserving Encryption)」といいます。OPEは検索の絞り込みが高速になり有用なのですが、一般に安全ではありません。NECが開発した技術では、特定の条件が成り立つときのみ比較を可能にすることで、安全性を考慮しつつ、暗号文を比較することを可能にしています。
また、2014年には、富士通研究所が暗号化したまま検索が可能な秘匿検索技術を開発しています(参考リンク)。これはどちらかというと、第4回で紹介した準同型暗号を応用した方式になっています。
このように、さまざまな企業や研究所が検索可能暗号の技術を提案していますが、その仕組みや、技術によって実現されることはそれぞれ異なっています。そのため、どの技術が良いのかを互いに比較するのは難しいというのが現状です。また、転置インデックスなど、従来の暗号化されていない検索サーバーのような性能を実現するのはまだまだこれからという段階です。今後の動向が注目されます。
属性ベース暗号や関数型暗号についてより詳しく学びたい人のために、Web上で閲覧できるものや書籍として入手できる参考文献を紹介します。
サイボウズ・ラボ株式会社にてセキュリティとインフラ周りの研究開発に携わる。「数論アルゴリズムとその応用」研究部会(JANT)幹事。
近著に「応用数理ハンドブック」(朝倉書店、2013:だ円曲線暗号、ペアリング暗号の項目担当)、「クラウドを支えるこれからの暗号技術」(秀和システム、2015)がある。
Copyright © ITmedia, Inc. All Rights Reserved.