小特集 2. 完全準同形暗号の構成方法

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.99 No.12 (2016/12) 目次へ

前の記事へ次の記事へ


小特集 2.

完全準同形暗号の構成方法

How to Construct Fully Homomorphic Encryption

Mehdi TIBOUCHI

Mehdi TIBOUCHI 日本電信電話株式会社NTTセキュアプラットフォーム研究所

Mehdi TIBOUCHI, Nonmember (NTT Secure Platform Laboratories, NIPPON TELEGRAPH AND TELEPHONE CORPORATION, Musashino-shi, 180-8585 Japan).

電子情報通信学会誌 Vol.99 No.12 pp.1159-1166 2016年12月

©電子情報通信学会2016

abstract

 完全準同形暗号(FHE)とは,暗号化したままデータの処理を可能にする暗号技術であり,概念として40年ほど前に提案されたが長い間実現方法が見つからなかった.しかし2009年にスタンフォード大学のGentryが初めて構成法を考案し大躍進を果たした.本稿では,Gentryの2009年の論文と後続研究における構成方法の主なアイデアを紹介する.特に次の3点に焦点を絞る.まずは低次数関数の準同形評価に対応する,いわゆるSomewhat準同形暗号(SHE)方式の構成について述べる.次にGentryの提案したSHEからFHEへの変換手法・ブートストラップの説明を行う.そして最後に,ブートストラップよりコストの低いモジュラス切換手法について紹介する.

キーワード:完全準同形暗号,ブートストラップ,格子ベース暗号,近似最大公約数問題

1.は じ め に

 本小特集第1章の記事で説明されているように,完全準同形暗号(FHE: Fully Homomorphic Encryption)とは,暗号文に対し任意の効率的な関数の計算を復号せずに行うことができる暗号方式であり,公開鍵暗号の発明後間もなく発表されたRivest, AdlemanとDertouzosの論文(1)において概念として提案された.しかし,その実現は困難であり30年間も未解決問題のままであった.その後,2009年のCraig Gentryの論文(2)で初めて構成方法が紹介され,暗号学の画期的な進歩とみなされている.本稿ではその具体的な構成方法,及びより最近の論文で提案された改良について説明する.

1.1 任意の関数の準同形評価の対応

 公開鍵・共通鍵を問わず,暗号方式(Gen(用語),Enc(用語),Dec(用語))がある関数mathの準同形評価に対応するということは,平文mathを暗号化した暗号文mathを入力とした効率的アルゴリズムmathがあって,そのアルゴリズムが秘密鍵mathを持たずに平文mathを暗号化した新たな暗号文mathを計算できることを意味する(図1).つまりmathが次式を満たす.

math

fig_1.png

 例えば,エルガマル暗号(3)は掛算の準同形評価に対応しており乗法準同形暗号方式という.なぜなら,エルガマル公開鍵をmathで示すとmathの暗号文はmathmathという形式があって,同形の暗号文mathmathと成分ごとに掛算することによってmathの暗号文mathが求められるからである.同様に,Paillier暗号(4)は足し算の準同形評価に対応しており加法準同形暗号方式という.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

「電信情報通信学会 - IEICE会誌」アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。