Secure Computing (SC) 班

セキュアコンピューティング(SC)グループでは、データを暗号化したままで演算(秘匿計算)する技術についての研究を中心に取り組んでいます。

秘匿計算の一例として、ある企業が自社内にもつデータを解析して何らかの知見を得たい場合に、解析ノウハウがない・計算資源がない等の理由から、解析のための計算をクラウドサービスなどの第三者に依頼することが考えられます。その際、データそのものに企業利益につながるような内容や個人情報が含まれる場合、実際に計算を行う第三者や悪意のある攻撃者にデータ内容を知られる恐れがあります。秘匿計算では、依頼主がデータを暗号化してから第三者に依頼することで、第三者がデータを復号化することなく(つまり、中身を知ることなく)計算を行い、結果のみを依頼主が復号することができるため上述のリスクを回避することができます。

秘匿計算を可能とする従来の暗号化方式には速度面に問題があるため、暗号グループでは秘匿計算の高速化に取り組んでいます。秘匿計算のアルゴリズムを考える作業はパズルを解く感覚です。

本プロジェクトでは完全準同型暗号に対してコンピュータアーキテクチャ・暗号理論を考慮したソフトウェアの両面からの最適化を行うことで1000倍以上の高速化を目指しています。他拠点との連携により実用的に使用可能な秘匿計算によるオープンソースライブラリ構築を目標としています。
プロジェクトページはこちら

研究紹介

再利用性を備えた暗号文上での大小比較演算

準同型暗号にて暗号化された2整数の大小比較結果をもとに何らかの演算を行うためには、各整数をビット単位で暗号化する必要がある。しかし、ビット単位の暗号化では大小比較後に算術演算回路で表される演算を準同型評価する必要があり効率が悪い。(例えば、ビット毎の暗号文を使用して整数の加乗算を行うためには、加乗算器を準同型評価しなければならない。)本研究では、比較後演算において多項式上での任意演算(加算・乗算)をビット単位暗号化をすることなく実行できることを示した。
さらに、大小比較に要する演算回路の深さは従来手法の中で最小となることを示した。


Relinearize Problem

Ring-LWEベースの準同型暗号では,準同型乗算することで暗号長が長くなり,暗号長が長くなるほど,計算コストが線形増加する.これを回避するために,Relinearizationと呼ばれる暗号長を短くする処理がある.Relinearizationは準同型乗算と同程度の計算コスト(数百ms)を要する.したがって,Relinearizationを行うタイミングを最適化することで全体の処理時間を高速化ができる.この最適化問題はRelinearize Problemと呼ばれており,NP困難であることが知られている.本提案手法では,Relinearize Problemに対して,線形時間で近似解を求めることができ,さらに特定条件下では最適解を得ることができる.


Privacy-Preserving Data Classification

機械学習は様々な場面に応用できます。近年ではデータ量が増加しており、一つのデータに含まれているデータ数も増えているためデータを分類するのに掛かる時間が増加しています。その様な分類タスクをクラウドなどに委託する事によってクライアントでの負担を軽減できます。FHEを応用する事によってデータを秘匿したままクラウドサーバーにて分類を行えます。本研究では分類モデル、クライアントのデータおよび結果を秘匿したままクラウドにてデータの分類を行うことができる。


表探索による準同型暗号の関数計算

スマートグリッドのプライバシー保護異常検出システムを完全準同型暗号技術で実現します.準同型暗号技術で暗号化したままデータの解析や計算が可能ですが,処理速度が遅いため,ビッグデータの要求に適応できません.この問題に対して,計算量削減のために,準同型暗号のテーブル探索に置き換える事を提案します.計算したい関数の入力値と出力結果をテーブルに保存すると,テーブル探索して計算結果を得ます.


Privacy-Preserving Recommendation for Location-Based Service

近年、人工知能などを用いてビックデータを分析することで価値のある情報を抽出する技術が注目されています。一方で、 セキュリティ要求が高い銀行や病院以外の領域では、セキュリティの重要性が世の中に未だ十分に認識されていません。現在google mapや食べログなどの位置情報を用いたサービスがユーザーの個人情報を大量に保有しています。膨大に蓄積されたデータが暗号化されずに平文の状態のまま保存や分析をされてしまうと、将来的に重大な社会問題を引き起こす危険性があると考えています。ですので、この研究内容は、暗号化技術を用いて、サービス側がユーザーの位置情報や検索内容の中身を知ることなく、ユーザーへの質の高い推薦を可能にするサービスの新たしい仕組みです。


完全準同型暗号を用いた Apriori(頻出アイテムセットマイニング)

あるアイテムリストの中から、頻出して出現するアイテムを暗号化したまま計算する研究。
例えば製薬企業が、大量の種類の薬品群の中から副作用の頻繁におこる薬品を調査したいとき、計算委託はしたいが、薬品ごとの副作用の頻度は企業秘密のため情報流出は避けたいと考える。様々な制約の中で、いかに復号結果の整合性をたもったままプロトコルを構築できるかがポイント。


完全準同型暗号を用いた秘匿ゲノム検索

DNA配列検索は生物学的・医学的知見取得のために、有効である。しかしながら、DNA配列は個人の特徴を反映するだけでなく、個人の識別子(ID)ともなりうる。そのような背景から複数拠点にまたがって存在するDNA配列を活用するためには、暗号化したままのDNA配列検索が望まれる。暗号化したままの検索でどのようにアルゴリズムを構築するかがポイント。

完全準同型暗号を用いたoutsourced private set intersection cardinality

2つの異なる機関が所有するパーソナルデータ集合の共通部分集合の要素数を、クラウド上で暗号化したまま求める研究である。例えば、研究者が病院と航空会社の所有するデータベースを用いて、ある病気の感染地域を特定する際に必要なデータベースの結合処理に応用できる。この処理の過程で、データベースのデータの情報を、クラウドから隠したまま計算処理が可能なプロトコルを構築する。

計算回路上でのbootstrapping配置の最適化

完全準同型暗号の一種であるleveled完全準同型暗号では、一定回数の暗号文同士の演算を行うたびにbootstrappingと呼ばれる時間のかかる処理が必要になります。ここで、事前に計算したい演算が回路の形で表現されているとき、回路上のどのタイミングでbootstrappingを実行するかを適切に選択すると、計算全体でみてbootstrappingの必要回数を減らすことが可能です。複数の制約条件の中で適切な配置を探す必要があります。

メニーコア・共有マシンにおけるスケーラブルなメモリアロケータ

マルチコアシステム上で多数のスレッドが同時に実行される場合(e.g. 完全準同型暗号の演算処理),メモリアロケーションが処理時間のボトルネックになり,スケーラビリティが低下する場合がある.これはマルチスレッドでシステムコールが同時に呼ばれ,ロック競合が発生することに起因する.そこで,そのロック競合の回数を削減し,高速化を実現する.具体的には,システムコールの頻度を下げ,極力ユーザ領域でメモリを管理する方針をとる.