文献

J-GLOBAL ID：201802232249100377   整理番号：18A1365332

完全準同型暗号による秘密計算回路のループ最適化と最近傍法への適用

Loop Circuit Optimization with Bootstrapping over Fully Homomorphic Encryption and its Application to Nearest Neighbor

著者 (4件)： 佐藤宏樹 (早稲田大 大学院基幹理工学研究科) ,  馬屋原昂 (早稲田大 大学院基幹理工学研究科) ,  石巻優 (早稲田大 大学院基幹理工学研究科) ,  山名早人 (早稲田大 理工学術院)
資料名： 日本データベース学会和文論文誌(Web)  (DBSJ Japanese Journal (Web))
巻： 16-J  ページ： ROMBUNNO.12 (WEB ONLY)  発行年： 2018年03月 
JST資料番号： U0795A  ISSN： 2189-0374  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,計算資源としてクラウドを使用するケースが増加する一方,第三者のサーバ上でデータ処理を行う場合は個人情報や機密情報の漏洩が懸念される。データの秘密を保持したまま解析を行う技術は秘密計算と呼ばれ,その1つに完全準同型暗号を用いた手法がある。完全準同型暗号では,計算を繰り返し行うためにbootstrapと呼ばれる処理が必要となるが,bootstrapは膨大な計算量を要する。このため,ある計算のデータフローグラフが与えられたとき,bootstrapを行う回数を最小化することは全体の処理時間を削減することに直結する。Bootstrapを行う回数を最小化する問題に対する既存研究は対象のデータフローグラフをDAGに限定しており,ループにおけるイテレーション間の関係を扱うことができない。そこで,本稿ではループを含む計算回路において,ループアンローリングを用いながら全体の実行時間を最小化するbootstrapの配置決定手法を提案する。2種類の回路に対して提案手法を適用し,評価実験を行った結果,イテレーションあたりのbootstrap回数を,ナイーブな場合の25%~63%に減らした。また,提案手法で得た結果を最近傍法へ適用し,ナイーブ手法と比較して2.67倍の高速化を達成した。(著者抄録)

シソーラス用語： *暗号 ,  計算 ,  *最適化 ,  アルゴリズム ,  情報セキュリティ ,  計算量 ,  データフローグラフ ,  高速化 ,  *ループ回路 ,  実験 ,  有向グラフ ,  最近傍法 ,  評価実験 ,  *改変
準シソーラス用語： bootstrap問題 ,  DAG【グラフ】 ,  完全準同型暗号 ,  秘密計算

分類 (1件)： データ保護  (JD01020V)

引用文献 (10件)：

• Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proc. of Ann. ACM Symp. on Thory of Computing (STOC 2009), Vol. 9, pp. 169-178, 2009.
• Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. In Proc. of the 52nd Ann. Symp. on Foundations of Computer Science (FOCS 2011), pp. 97-106, 2011.
• Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical gapsvp. In Advances in Cryptology-CRYPTO 2012, LNCS, Vol. 7417, pp. 868-886, 2012.
• Tancrède Lepoint and Pascal Paillier. On the minimal number of bootstrappings in homomorphic circuits. In Financial Cryptography and Data Security: FC 2013 Workshops, USEC and WAHC 2013, LNCS, Vol. 7862, pp. 189-200, 2013.
• Marie Paindavoine and Bastien Vialla. Minimizing the number of bootstrappings in fully homomorphic encryption. In Proc. of the 22nd Int’l Conf. on Selected Areas in Cryptography, SAC 2015, LNCS, Vol. 7839, pp. 25-43, 2015.

タイトルに関連する用語 (5件)： 暗号 ,  秘密計算 ,  ループ ,  最適化 ,  最近傍法