特許ウォッチ

公開番号2025082508
公報種別公開特許公報(A)
公開日2025-05-29
出願番号2023195885
出願日2023-11-17
発明の名称演算装置、演算方法及び演算プログラム
出願人KDDI株式会社
代理人個人,個人
主分類G09C 1/00 20060101AFI20250522BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】効率的なアルゴリズムにより、任意の関数の準同型演算を実行できる演算装置、演算方法及び演算プログラムを提供すること。
【解決手段】演算装置1は、dビットの入力値候補それぞれに対して、関数の出力値の所定のビットである実現値を対応付けたテーブルを記憶する記憶部20と、関数に対する入力値を示すd個のバイナリ値の暗号文を受け付ける入力部11と、テーブルにおける入力値候補のうち、実現値が0となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが0のとき対応するバイナリ値そのものを、各ビットが1のとき対応するバイナリ値の反転を、全て足し合わせた総和を暗号文上で算出する加算部12と、特定の入力値候補それぞれに対して算出された総和を、全て掛け合わせた総積を暗号文上で算出する乗算部13と、総積を入力値に対する関数値として出力する出力部14とを備える。
【選択図】図1
特許請求の範囲【請求項１】
ｄビットの入力値候補それぞれに対して、関数の出力値の所定のビットである実現値を対応付けたテーブルを記憶する記憶部と、
前記関数に対する入力値を示すｄ個のバイナリ値の暗号文を受け付ける入力部と、
前記テーブルにおける前記入力値候補のうち、前記実現値が０となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出する加算部と、
前記特定の入力値候補それぞれに対して算出された前記総和を、全て掛け合わせた総積を暗号文上で算出する乗算部と、
前記総積を前記入力値に対する前記関数の値として出力する出力部と、を備える演算装置。
続きを表示（約 990 文字）【請求項２】
前記テーブルにおいて、前記実現値が０である割合が半分以下の場合に、
前記加算部は、前記テーブルにおける前記入力値候補のうち、前記実現値が０となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出し、
前記出力部は、前記総積を前記入力値に対する前記関数の値として出力し、
前記テーブルにおいて、前記実現値が０である割合が半分を超えている場合に、
前記加算部は、前記テーブルにおける前記入力値候補のうち、前記実現値が１となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出し、
前記出力部は、前記総積を反転した値を暗号文上で計算し、前記入力値に対する前記関数の値として出力する請求項１に記載の演算装置。
【請求項３】
前記乗算部は、複数の前記総和を木構造に配置し、各深さの乗算をそれぞれ並列に実行して前記総積を計算する請求項１又は請求項２に記載の演算装置。
【請求項４】
コンピュータがｄビットの入力値候補それぞれに対して、関数の出力値の所定のビットである実現値を対応付けたテーブルを記憶し、
前記関数に対する入力値を示すｄ個のバイナリ値の暗号文を受け付ける入力ステップと、
前記テーブルにおける前記入力値候補のうち、前記実現値が０となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出する加算ステップと、
前記特定の入力値候補それぞれに対して算出された前記総和を、全て掛け合わせた総積を暗号文上で算出する乗算ステップと、
前記総積を前記入力値に対する前記関数の値として出力する出力ステップと、を実行する演算方法。
【請求項５】
請求項１又は請求項２に記載の演算装置としてコンピュータを機能させるための演算プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、関数の準同型演算を行う演算装置、演算方法及び演算プログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
秘密計算は、データを暗号化したまま統計解析等を可能にする技術である。ビッグデータを用いたサービスの台頭に伴い、個人情報保護の重要性も増していることから、秘密計算は、配慮が必要な個人情報等の機微なデータを秘匿するための応用が期待されている。完全準同型暗号方式（ＦＨＥ）は、データを暗号化したまま任意の計算が実行可能な暗号方式であり、秘密計算でＡＩ等の高度な統計解析を行う際に必要な技術である（例えば、非特許文献１～３参照）。
【０００３】
ところで、ＦＨＥには、準同型加算は効率的に実行できるが、準同型乗算は非常に非効率であるという特徴がある。そこで、非特許文献３において、任意の関数の準同型演算をＬｏｏｋ－ｕｐＴａｂｌｅ（ＬＵＴ）を用いて実行するアルゴリズムが提案されている。
【先行技術文献】
【非特許文献】
【０００４】
C. Gentry. "Fully Homomorphic Encryption Using Ideal Lattices". STOC 2009. 2009, pp. 169-178.
J. H. Cheon, A. Kim, M. Kim, Y. Song. "Homomorphic Encryption for Arithmetic of Approximate Numbers". ASIACRYPT 2017. 2017, pp. 409-437.
I. Chillotti, N. Gama, M. Georgieva, M. Izabachene. "TFHE: Fast Fully Homomorphic Encryption Over the Torus". Journal of Cryptology. 33.1 (2020), pp. 34-91.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＬＵＴを用いた従来のアルゴリズムにおいても、Ｃｍｕｘ演算における乗算の回数が多いため、さらなる効率化が望まれている。
【０００６】
本発明は、従来のＬＵＴアルゴリズムより乗算回数が少ない効率的なアルゴリズムにより、任意の関数の準同型演算を実行できる演算装置、演算方法及び演算プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る演算装置は、ｄビットの入力値候補それぞれに対して、関数の出力値の所定のビットである実現値を対応付けたテーブルを記憶する記憶部と、前記関数に対する入力値を示すｄ個のバイナリ値の暗号文を受け付ける入力部と、前記テーブルにおける前記入力値候補のうち、前記実現値が０となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出する加算部と、前記特定の入力値候補それぞれに対して算出された前記総和を、全て掛け合わせた総積を暗号文上で算出する乗算部と、前記総積を前記入力値に対する前記関数の値として出力する出力部と、を備える。
【０００８】
前記テーブルにおいて、前記実現値が０である割合が半分以下の場合に、前記加算部は、前記テーブルにおける前記入力値候補のうち、前記実現値が０となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出し、前記出力部は、前記総積を前記入力値に対する前記関数の値として出力し、前記テーブルにおいて、前記実現値が０である割合が半分を超えている場合に、前記加算部は、前記テーブルにおける前記入力値候補のうち、前記実現値が１となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出し、前記出力部は、前記総積を反転した値を暗号文上で計算し、前記入力値に対する前記関数の値として出力してもよい。
【０００９】
前記乗算部は、複数の前記総和を木構造に配置し、各深さの乗算をそれぞれ並列に実行して前記総積を計算してもよい。
【００１０】
本発明に係る演算方法は、コンピュータがｄビットの入力値候補それぞれに対して、関数の出力値の所定のビットである実現値を対応付けたテーブルを記憶し、前記関数に対する入力値を示すｄ個のバイナリ値の暗号文を受け付ける入力ステップと、前記テーブルにおける前記入力値候補のうち、前記実現値が０となる特定の入力値候補それぞれについて、当該入力値候補の各ビットが０のとき対応する前記バイナリ値そのものを、各ビットが１のとき対応する前記バイナリ値の反転を、全て足し合わせた総和を暗号文上で算出する加算ステップと、前記特定の入力値候補それぞれに対して算出された前記総和を、全て掛け合わせた総積を暗号文上で算出する乗算ステップと、前記総積を前記入力値に対する前記関数の値として出力する出力ステップと、を実行する。
（【００１１】以降は省略されています）

関連特許