完全準同型暗号におけるbootstrap problem及びrelinearize problemの厳密解法の高速化

佐藤宏樹; 石巻優; 山名早人

文献

J-GLOBAL ID：202002257780870965 整理番号：20A1609714

完全準同型暗号におけるbootstrap problem及びrelinearize problemの厳密解法の高速化

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A1609714&from=J-GLOBAL&jstjournalNo=U0795A") }}

著者 (3件)： , ,
資料名：
巻： 18-J ページ： ROMBUNNO.17 (WEB ONLY) 発行年： 2020年03月
JST資料番号： U0795A ISSN： 2189-0374 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：日本語 (JA)

完全準同型暗号(FHE)は秘密鍵を用いることなく任意の演算が暗号文上で可能な暗号方式である.FHEは,データの秘密を保持したまま解析や検索を行う技術への応用が期待される.FHE上での演算は平文上での演算と特徴が異なるため,FHEに適したアルゴリズムや最適化が必要である.特に,暗号化状態での計算を継続的に行うためにはbootstrappingやrelinearizationと呼ばれる処理を暗号文に施す必要がある.bootstrappingやrelinearizationはFHEの中で計算量が大きいため,計算のデータフローグラフ上でのこれらの処理の実行スケジューリングは,FHEによる計算全体の処理時間に影響を与える.それぞれのスケジューリング問題はbootstrap problem,relinearize problemと呼ばれ,ともにNP困難であり,制約式を列挙すると整数線形計画問題(ILP)となる.変数と制約式の個数はデータフローグラフの辺と頂点の個数に比例するため,最適化対象のグラフが大きくなると厳密解を得ることが困難である.本稿では,出力されるILPの解は厳密解から変えずに,ILPの変数と制約式を削減し,本処理を適用しない場合よりも高速に解を求める手法を提案する.評価実験では,多くの場合で提案手法により頂点数を約3~4割削減し,厳密解を求める最適化の計算時間も約3~4割削減した.(著者抄録)

, , , , , , ,
, ,

記号処理

引用文献 (12件)：

Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, and Hang Zhou. Optimization of bootstrapping in circuits. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’17), pages 2423-2433, 2017.
Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homo-morphic encryption from (standard) lwe. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 97-106, 2011.
Hao Chen. Optimizing relinearization in circuits for homomorphic encryption. arXiv e-prints, October 2017.
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC ’09, pages 169-178. ACM, 2009.
Tancrède Lepoint and Pascal Paillier. On the minimal number of bootstrappings in homomorphic circuits. In Financial Cryptography and Data Security: FC 2013 Workshops, volume 7862, LNCS, pages 189-200, 2013.

, ,

前のページに戻る