特許ウォッチ

公開番号2025042949
公報種別公開特許公報(A)
公開日2025-03-28
出願番号2023150169
出願日2023-09-15
発明の名称秘匿演算装置、秘匿演算方法及び秘匿演算プログラム
出願人KDDI株式会社
代理人個人,個人
主分類G09C 1/00 20060101AFI20250321BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】TFHE上で任意のn-bit離散関数を効率的に評価できる秘匿演算装置、秘匿演算方法及び秘匿演算プログラムを提供すること。
【解決手段】秘匿演算装置1は、TFHE上で離散関数を評価するためのCMux Treeにおいて、最深部のCMuxゲートに代えて、当該最深部のCMuxゲートに対応するルックアップテーブルのバイナリ文字列の4種類のパターンそれぞれに対して、定数0若しくは1、又はセレクタxに応じた定数x若しくは1-xのいずれかの暗号文を設定する設定部11と、最深部のCMuxゲートより上位のCMuxゲートのみを実行する演算実行部12と、を備える。
【選択図】図1
特許請求の範囲【請求項１】
ＴＦＨＥ上で離散関数を評価するためのＣＭｕｘＴｒｅｅにおいて、
最深部のＣＭｕｘゲートに代えて、当該最深部のＣＭｕｘゲートに対応するルックアップテーブルのバイナリ文字列の４種類のパターンそれぞれに対して、定数０若しくは１、又はセレクタｘに応じた定数ｘ若しくは１－ｘのいずれかの暗号文を設定する設定部と、
前記最深部のＣＭｕｘゲートより上位のＣＭｕｘゲートのみを実行する演算実行部と、を備える秘匿演算装置。
続きを表示（約 610 文字）【請求項２】
前記演算実行部は、前記最深部より上位のＣＭｕｘゲートのそれぞれにおいて、当該ＣＭｕｘゲートに対応する前記ルックアップテーブルのバイナリ文字列が左右で等しい場合に、当該ＣＭｕｘゲートの実行を省略して下位からの２つの入力値の一方を出力する請求項１に記載の秘匿演算装置。
【請求項３】
前記演算実行部は、前記最深部より上位のＣＭｕｘゲートのそれぞれにおいて、当該ＣＭｕｘゲートに対応する前記ルックアップテーブルのバイナリ文字列が等しい他のＣＭｕｘゲートを実行済みの場合に、当該ＣＭｕｘゲートの実行を省略して前記他のＣＭｕｘゲートと同一の値を出力する請求項１又は請求項２に記載の秘匿演算装置。
【請求項４】
ＴＦＨＥ上で離散関数を評価するためのＣＭｕｘＴｒｅｅにおいて、
最深部のＣＭｕｘゲートに代えて、当該最深部のＣＭｕｘゲートに対応するルックアップテーブルのバイナリ文字列の４種類のパターンそれぞれに対して、定数０若しくは１、又はセレクタｘに応じた定数ｘ若しくは１－ｘのいずれかの暗号文を設定する設定ステップと、
前記最深部のＣＭｕｘゲートより上位のＣＭｕｘゲートのみを実行する演算実行ステップと、をコンピュータが実行する秘匿演算方法。
【請求項５】
請求項１に記載の秘匿演算装置としてコンピュータを機能させるための秘匿演算プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、完全準同型暗号（ＦＨＥ：ＦｕｌｌｙＨｏｍｏｍｏｒｐｈｉｃＥｎｃｒｙｐｔｉｏｎ）上で任意のｎ－ｂｉｔ離散関数を評価する手法に関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
ＦＨＥは、理論上では暗号文上で任意の計算を行うことが可能な暗号方式であり、プライバシ保護及び秘密計算の分野で重要な技術である。しかし、ＦＨＥ上での計算は、通常の平文上での計算と比較して負荷が大きいため、速度向上が課題である。
また、ＦＨＥは、安全性を保持するために暗号文中に一定量のノイズを含む。このため、暗号文に対して繰り返し計算を行うと、ノイズが増加する。暗号文に蓄積されたノイズを初期化する技術として、ＢＳ（Ｂｏｏｔｓｔｒａｐｐｉｎｇ）が知られているが、計算コストが高い。
【０００３】
効率的にＢＳを実施するＦＨＥ方式として、ＴＦＨＥ（非特許文献１参照）が知られている。ＴＦＨＥにおけるＢＳの特徴は、暗号文中のノイズを初期化すると同時に、追加コストなしで暗号文に対して任意の離散関数を適用できる点である。すなわち、ＴＦＨＥにおけるＢＳの入力は、１つの暗号文ｘであり、出力は、離散関数ｆが適用され、かつ、ノイズが初期化された暗号文ｆ（ｘ）である。このような性質を持つＴＦＨＥのＢＳは、ＰＢＳ（ＰｒｏｇｒａｍｍａｂｌｅＢＳ）と呼ばれる。ＰＢＳは、ＴＦＨＥが暗号文上で任意の計算を実現するために重要である。
【０００４】
しかしながら、ＴＦＨＥが１つの暗号文に格納できるデータ長は高々８ｂｉｔである。よって、任意の精度（ビット数ｎ）のｎ－ｂｉｔ離散関数を適用するためには、複数の暗号文を組み合わせなければならない。
ここで、平文でｎ－ｂｉｔ離散関数を適用する一般的な方法は、長さが２
ｎ
のＬＵＴ（Ｌｏｏｋ－ｕｐＴａｂｌｅ）を準備して、ＬＵＴの各ｉ（０≦ｉ≦２
ｎ
－１）にｎ－ｂｉｔの出力ｆ（ｉ）を格納し、必要時にＬＵＴを参照することである。この場合、Ｏ（２
ｎ
）の大きさのメモリとＯ（１）のクエリ時間が必要である。
一方、ＴＦＨＥにおいては、ＬＵＴを用いた空間計算量Ｏ（２
ｎ
）、時間計算量Ｏ（２
ｎ
）である以下の指数時間アルゴリズムが知られている。
ＣＭｕｘＴｒｅｅ（非特許文献１参照）
Ｔｒｅｅ－ｂａｓｅｄＰＢＳ（非特許文献２参照）
ＷｏＰ－ＰＢＳ（非特許文献３参照）
【先行技術文献】
【非特許文献】
【０００５】
Ilaria Chillotti et al., "TFHE: Fast Fully Homomorphic Encryption Over the Torus", Journal of Cryptology 33.1 (2020), pp. 34-91.
Florian Bourse et al., "Improved Secure Integer Comparison via Homomorphic Encryption", Topics in Cryptology - CT-RSA 2020, 2020, pp. 391-416.
Loris Bergerat et al., "Parameter Optimization & Larger Precision for (T)FHE", Cryptology ePrint Archive, Paper 2022/704, 2022.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、ＴＦＨＥ上で平文と同等の空間計算量Ｏ（２
ｎ
）、時間計算量Ｏ（１）で任意のｎ－ｂｉｔ離散関数を適用する方法はなく、既存手法より効率的な指数時間アルゴリズムが望まれている。
【０００７】
本発明は、ＴＦＨＥ上で任意のｎ－ｂｉｔ離散関数を効率的に評価できる秘匿演算装置、秘匿演算方法及び秘匿演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る秘匿演算装置は、ＴＦＨＥ上で離散関数を評価するためのＣＭｕｘＴｒｅｅにおいて、最深部のＣＭｕｘゲートに代えて、当該最深部のＣＭｕｘゲートに対応するルックアップテーブルのバイナリ文字列の４種類のパターンそれぞれに対して、定数０若しくは１、又はセレクタｘに応じた定数ｘ若しくは１－ｘのいずれかの暗号文を設定する設定部と、前記最深部のＣＭｕｘゲートより上位のＣＭｕｘゲートのみを実行する演算実行部と、を備える。
【０００９】
前記演算実行部は、前記最深部より上位のＣＭｕｘゲートのそれぞれにおいて、当該ＣＭｕｘゲートに対応する前記ルックアップテーブルのバイナリ文字列が左右で等しい場合に、当該ＣＭｕｘゲートの実行を省略して下位からの２つの入力値の一方を出力してもよい。
【００１０】
前記演算実行部は、前記最深部より上位のＣＭｕｘゲートのそれぞれにおいて、当該ＣＭｕｘゲートに対応する前記ルックアップテーブルのバイナリ文字列が等しい他のＣＭｕｘゲートを実行済みの場合に、当該ＣＭｕｘゲートの実行を省略して前記他のＣＭｕｘゲートと同一の値を出力してもよい。
（【００１１】以降は省略されています）

関連特許