特許ウォッチ

公開番号2025094776
公報種別公開特許公報(A)
公開日2025-06-25
出願番号2023210521
出願日2023-12-13
発明の名称暗号化データ計算装置、暗号システム、暗号化データ計算方法、および暗号化データ計算プログラム
出願人日本電気株式会社
代理人個人,個人
主分類G09C 1/00 20060101AFI20250618BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】整数型準同型暗号を用いた汎用的な2変数非線形演算において計算を効率化することに寄与すること。
【解決手段】暗号化データ計算装置は、第1変数と第2変数の値の取り得る全ての組み合わせに関する2変数非線形演算の結果を事前に計算した平文をN×Nのルックアップテーブル行列として保持し、第1インジケータベクトル暗号文をルックアップテーブル行列に作用させることで、ルックアップテーブル行列における第1変数の値の行を抽出するLUT行列演算部と、ルックアップテーブル行列における第1変数の値の行を抽出したベクトル暗号文と第2インジケータベクトル暗号文とを乗算する乗算演算部と、乗算演算部の結果のベクトル暗号文の各スロットが全スロットの値の総和となる計算を行うEvalSum演算部と、を備える。
【選択図】図1
特許請求の範囲【請求項１】
０以上Ｎ－１以下の整数に値を有する第１変数と第２変数の暗号文から２変数非線形演算の結果の暗号文を計算する暗号化データ計算装置であって、
前記第１変数の暗号文を、前記第１変数の値の成分のみが１でありその他の成分が０であるＮ次元の第１インジケータベクトル暗号文に変換する第１One-HotSlot演算部と、
前記第２変数の暗号文を、前記第２変数の値の成分のみが１でありその他の成分が０であるＮ次元の第２インジケータベクトル暗号文に変換する第２One-HotSlot演算部と、
前記第１変数と前記第２変数の値の取り得る全ての組み合わせに関する前記２変数非線形演算の結果を事前に計算した平文をＮ×Ｎのルックアップテーブル行列として保持し、前記第１インジケータベクトル暗号文を前記ルックアップテーブル行列に作用させることで、前記ルックアップテーブル行列における前記第１変数の値の行を抽出するLUT行列演算部と、
前記ルックアップテーブル行列における前記第１変数の値の行を抽出したベクトル暗号文と前記第２インジケータベクトル暗号文とを乗算する乗算演算部と、
前記乗算演算部の結果のベクトル暗号文の各スロットが全スロットの値の総和となる計算を行うEvalSum演算部と、
を備える暗号化データ計算装置。
続きを表示（約 1,900 文字）【請求項２】
前記第１変数および前記第２変数の暗号文は、Ｎ個の全てのスロットに前記第１変数および前記第２変数の同じ値を割り当てて有限体係数の多項式環にパッキングしたものを準同型暗号で暗号化したものである請求項１に記載の暗号化データ計算装置。
【請求項３】
暗号文を暗号化したまま平文に対する和算と乗算を行うための演算鍵を保持し、前記第１変数と前記第２変数の暗号文から２変数非線形演算の結果の暗号文を演算するまでの処理を、前記演算鍵を用いて暗号文を暗号化したまま行う請求項１または請求項２に記載の暗号化データ計算装置。
【請求項４】
請求項１に記載の暗号化データ計算装置と、
暗号文を復号するための復号鍵と、平文から暗号文を計算するための暗号化鍵と、暗号文を暗号化したまま平文に対する和算と乗算を行うための演算鍵とを生成し、前記演算鍵を前記暗号化データ計算装置に送信する鍵生成装置と、
０以上Ｎ－１以下の整数に値を有する第１変数と第２変数から、前記暗号化鍵を用いて前記第１変数と前記第２変数の暗号文を計算し、前記第１変数と前記第２変数の暗号文を前記暗号化データ計算装置に送信する暗号化装置と、
を備える暗号システム。
【請求項５】
前記暗号化装置は、Ｎ個の全てのスロットに前記第１変数および前記第２変数の同じ値を割り当てて有限体係数の多項式環にパッキングしたものを、前記暗号化鍵を用いて準同型暗号で暗号化する請求項４に記載の暗号システム。
【請求項６】
前記暗号化データ計算装置から受信した前記２変数非線形演算の結果の暗号文を、前記復号鍵を用いて復号する復号装置をさらに備える請求項４に記載の暗号システム。
【請求項７】
０以上Ｎ－１以下の整数に値を有する第１変数と第２変数の暗号文から２変数非線形演算の結果の暗号文を計算する暗号化データ計算方法であって、
前記第１変数の暗号文を、前記第１変数の値の成分のみが１でありその他の成分が０であるＮ次元の第１インジケータベクトル暗号文に変換する第１One-HotSlot演算と、
前記第２変数の暗号文を、前記第２変数の値の成分のみが１でありその他の成分が０であるＮ次元の第２インジケータベクトル暗号文に変換する第２One-HotSlot演算と、
前記第１変数と前記第２変数の値の取り得る全ての組み合わせに関する前記２変数非線形演算の結果を事前に計算した平文をＮ×Ｎのルックアップテーブル行列として保持し、前記第１インジケータベクトル暗号文を前記ルックアップテーブル行列に作用させることで、前記ルックアップテーブル行列における前記第１変数の値の行を抽出するLUT行列演算と、
前記ルックアップテーブル行列における前記第１変数の値の行を抽出したベクトル暗号文と前記第２インジケータベクトル暗号文とを乗算する乗算演算と、
前記乗算演算の結果のベクトル暗号文の各スロットが全スロットの値の総和となる計算を行うEvalSum演算と、
を含む暗号化データ計算方法。
【請求項８】
０以上Ｎ－１以下の整数に値を有する第１変数と第２変数の暗号文から２変数非線形演算の結果の暗号文を計算する処理をコンピュータに実行させる暗号化データ計算プログラムであって、
前記第１変数の暗号文を、前記第１変数の値の成分のみが１でありその他の成分が０であるＮ次元の第１インジケータベクトル暗号文に変換する第１One-HotSlot演算処理と、
前記第２変数の暗号文を、前記第２変数の値の成分のみが１でありその他の成分が０であるＮ次元の第２インジケータベクトル暗号文に変換する第２One-HotSlot演算処理と、
前記第１変数と前記第２変数の値の取り得る全ての組み合わせに関する前記２変数非線形演算の結果を事前に計算した平文をＮ×Ｎのルックアップテーブル行列として保持し、前記第１インジケータベクトル暗号文を前記ルックアップテーブル行列に作用させることで、前記ルックアップテーブル行列における前記第１変数の値の行を抽出するLUT行列演算処理と、
前記ルックアップテーブル行列における前記第１変数の値の行を抽出したベクトル暗号文と前記第２インジケータベクトル暗号文とを乗算する乗算演算処理と、
前記乗算演算処理の結果のベクトル暗号文の各スロットが全スロットの値の総和となる計算を行うEvalSum演算処理と、
を含む暗号化データ計算プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、暗号化データ計算装置、暗号システム、暗号化データ計算方法、および暗号化データ計算プログラムに関するものである。
続きを表示（約 2,900 文字）【背景技術】
【０００２】
計算サーバ上でデータを復号することなく計算することが可能な技術として準同型暗号という特殊な暗号技術が知られている。また、準同型暗号技術の中でも整数平文に関する加算・乗算を行えるものは整数型準同型暗号と呼ばれる。
【０００３】
除算や比較演算などの、加算と乗算によって容易には実現できない２変数の計算処理を２変数非線形演算と呼び、暗号化データベース演算（検索処理）や暗号化状態での異常検知などの応用において活用されている。２変数非線形演算は、加算と乗算によって容易には実現できないので、整数型準同型暗号で実現することもまた容易ではないが、２変数非線形演算を整数型準同型暗号で実現する方法として、ラグランジュ補間多項式を用いた手法が知られている（非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００４】
D. Maeda, et al., “Efficient Homomorphic Evaluation of Arbitrary Uni/Bivariate Integer Functions and Their Applications”, WAHC2022, 2022
S. Halevi, V. Shoup, “Faster Homomorphic Linear Transformations in HElib”, CRYPTO 2018, 2018
J. Bossuat, et al., “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys”, EUROCRYPT 2021, 2021
J. Fan, F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption”, Cryptology ePrint Archive, Paper 2012/144，2012
Z. Brakerski, C. Gentry, V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping”, ITCS '12，2012
【発明の概要】
【発明が解決しようとする課題】
【０００５】
なお、上記先行技術文献の各開示を、本書に引用をもって組み込むものとする。以下の分析は、本発明者らによってなされたものである。
【０００６】
ところで、ラグランジュ補間多項式を用いる計算は大きな時間計算量を必要とする。具体的には、２変数非線形演算に用いる変数の取り得る範囲を０以上Ｎ－1以下とすると、ラグランジュ補間多項式を用いる計算は、漸近的にＯ（√Ｎ）回の数論変換/逆数論変換が必要となる。つまり、２変数非線形演算に用いる変数の取り得る範囲が大きくなるほど、ラグランジュ補間多項式を用いる計算は大きな時間計算量を必要としてしまう。そこで、整数型準同型暗号を用いた汎用的な２変数非線形演算において計算の効率化が求められる。
【０００７】
本発明の目的は、上述した課題を鑑み、整数型準同型暗号を用いた汎用的な２変数非線形演算において計算を効率化することに寄与する暗号化データ計算装置、暗号システム、暗号化データ計算方法、および暗号化データ計算プログラムを提供することである。
【課題を解決するための手段】
【０００８】
本発明の第１の視点では、０以上Ｎ－１以下の整数に値を有する第１変数と第２変数の暗号文から２変数非線形演算の結果の暗号文を計算する暗号化データ計算装置であって、前記第１変数の暗号文を、前記第１変数の値の成分のみが１でありその他の成分が０であるＮ次元の第１インジケータベクトル暗号文に変換する第１One-HotSlot演算部と、前記第２変数の暗号文を、前記第２変数の値の成分のみが１でありその他の成分が０であるＮ次元の第２インジケータベクトル暗号文に変換する第２One-HotSlot演算部と、前記第１変数と前記第２変数の値の取り得る全ての組み合わせに関する前記２変数非線形演算の結果を事前に計算した平文をＮ×Ｎのルックアップテーブル行列として保持し、前記第１インジケータベクトル暗号文を前記ルックアップテーブル行列に作用させることで、前記ルックアップテーブル行列における前記第１変数の値の行を抽出するLUT行列演算部と、前記ルックアップテーブル行列における前記第１変数の値の行を抽出したベクトル暗号文と前記第２インジケータベクトル暗号文とを乗算する乗算演算部と、前記乗算演算部の結果のベクトル暗号文の各スロットが全スロットの値の総和となる計算を行うEvalSum演算部と、を備える暗号化データ計算装置が提供される。
【０００９】
本発明の第２の視点では、上記の暗号化データ計算装置と、暗号文を復号するための復号鍵と、平文から暗号文を計算するための暗号化鍵と、暗号文を暗号化したまま平文に対する和算と乗算を行うための演算鍵とを生成し、前記演算鍵を前記暗号化データ計算装置に送信する鍵生成装置と、０以上Ｎ－１以下の整数に値を有する第１変数と第２変数から、前記暗号化鍵を用いて前記第１変数と前記第２変数の暗号文を計算し、前記第１変数と前記第２変数の暗号文を前記暗号化データ計算装置に送信する暗号化装置と、を備える暗号システムが提供される。
【００１０】
本発明の第３の視点では、０以上Ｎ－１以下の整数に値を有する第１変数と第２変数の暗号文から２変数非線形演算の結果の暗号文を計算する暗号化データ計算方法であって、前記第１変数の暗号文を、前記第１変数の値の成分のみが１でありその他の成分が０であるＮ次元の第１インジケータベクトル暗号文に変換する第１One-HotSlot演算と、前記第２変数の暗号文を、前記第２変数の値の成分のみが１でありその他の成分が０であるＮ次元の第２インジケータベクトル暗号文に変換する第２One-HotSlot演算と、前記第１変数と前記第２変数の値の取り得る全ての組み合わせに関する前記２変数非線形演算の結果を事前に計算した暗号文をＮ×Ｎのルックアップテーブル行列として保持し、前記第１インジケータベクトル暗号文を前記ルックアップテーブル行列に作用させることで、前記ルックアップテーブル行列における前記第１変数の値の行を抽出するLUT行列演算と、前記ルックアップテーブル行列における前記第１変数の値の行を抽出したベクトル暗号文と前記第２インジケータベクトル暗号文とを乗算する乗算演算と、前記乗算演算の結果のベクトル暗号文の各スロットが全スロットの値の総和となる計算を行うEvalSum演算と、を含む暗号化データ計算方法が提供される。
（【００１１】以降は省略されています）

関連特許