特許ウォッチ

公開番号2025133348
公報種別公開特許公報(A)
公開日2025-09-11
出願番号2024031245
出願日2024-03-01
発明の名称秘匿計算システム及び秘匿計算方法
出願人NTT株式会社,サイボウズ・ラボ株式会社
代理人弁理士法人ITOH,個人,個人,個人
主分類G09C 1/00 20060101AFI20250904BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】準同型暗号を利用したargmax計算を効率化する秘匿計算方法及び秘匿計算システムを提供する。
【解決手段】秘匿計算処理において、クライアントは、入力配列v[0],・・・,v[N-1]を暗号化した暗号文配列c[0]=Enc(v[0]),・・・,c[N-1]=Enc(v[N-1])を生成し、暗号文配列c[0],・・・,c[N-1]をサーバに送信する。サーバは、暗号文配列c[0],・・・,c[N-1]と、EOHV(v[i]-v[j])とを用いて、c=Enc(H(v[i]-v[j]))を計算し、f((c,i_k,j_k))=sel(c,i_k,j_k)を用いて、Enc(f((c,i_k,j_k)))によりEnc(argmax(v[i],v[j]))を計算し、sel(c,i_k,j_k)が、ビット値i_k,j_kに対してc=Enc(1)の場合は、Enc(i_k)を、c=Enc(0)の場合はEnc(j_k)を返す。
【選択図】図6
特許請求の範囲【請求項１】
整数値を取る入力配列ｖ［０］，・・・，ｖ［Ｎ－１］を所持する第１の情報処理装置と、前記入力配列ｖ［０］，・・・，ｖ［Ｎ－１］の最大値を与えるインデックスの暗号文を計算する第２の情報処理装置とが含まれる秘匿計算システムであって、
前記第１の情報処理装置は、
前記入力配列ｖ［０］，・・・，ｖ［Ｎ－１］をそれぞれ準同型暗号により暗号化した暗号文配列ｃ［０］＝Ｅｎｃ（ｖ［０］），・・・，ｃ［Ｎ－１］＝Ｅｎｃ（ｖ［Ｎ－１］）を生成し、
前記暗号文配列ｃ［０］，・・・，ｃ［Ｎ－１］を前記第２の情報処理装置に送信し、
前記第２の情報処理装置は、
前記暗号文配列ｃ［０］，・・・，ｃ［Ｎ－１］と、ＥＯＨＶ（ｖ［ｉ］－ｖ［ｊ］）（ただし、ｉ，ｊ∈｛０，・・・，Ｎ－１｝、ｉ＜ｊ）とを用いて、ｃ＝Ｅｎｃ（Ｈ（ｖ［ｉ］－ｖ［ｊ］））（ただし、Ｈ（ｘ）はｘ≧０である場合は１、ｘ＜０である場合は０を返す関数）を計算し、
ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
））＝ｓｅｌ（ｃ，ｉ
ｋ
，ｊ
ｋ
）を用いて、Ｅｎｃ（ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
）））によりＥｎｃ（ａｒｇｍａｘ（ｖ［ｉ］，ｖ［ｊ］））を計算し、
前記ｓｅｌ（ｃ，ｉ
ｋ
，ｊ
ｋ
）は、ｉ，ｊをそれぞれ２進数で表現したときのｋビット目のビット値ｉ
ｋ
，ｊ
ｋ
に対して、ｃ＝Ｅｎｃ（１）である場合はＥｎｃ（ｉ
ｋ
）、ｃ＝Ｅｎｃ（０）である場合はＥｎｃ（ｊ
ｋ
）を返す関数である、
秘匿計算システム。
続きを表示（約 1,400 文字）【請求項２】
前記準同型暗号は、素数位数ｐの加法巡回群ＧをベースとするＬｉｆｔｅｄ－ＥｌＧａｍａｌ暗号であり、
前記第２の情報処理装置は、
Ｘ：＝｛０，１｝×｛０，１｝×｛０，１｝に対して、｜Ｘ｜個の乱数ｒ
ｉ'
←
Ｒ
［０，ｐ－１］を選択し、（ｒ
ｉ'
（（ｃ［ｉ］－ｃ［ｊ］）－Ｅｎｃ（ｉ'）））
ｉ'∈Ｘ
をシャッフルした｜Ｘ｜個の暗号文配列ｃ'［ｉ'］を前記第１の情報処理装置に送信し、
前記第１の情報処理装置は、
前記暗号文配列ｃ'［ｉ'］を前記準同型暗号によりそれぞれ復号し、復号結果が０である場合はＥｎｃ（１）、復号結果が０でない場合はＥｎｃ（０）とした暗号文配列ｃ''［ｉ'］を前記第１の情報処理装置に送信し、
前記第２の情報処理装置は、
｜Ｘ｜個の前記暗号文配列ｃ''［ｉ'］に対して前記シャッフルの逆操作を行うことにより、前記ＥＯＨＶ（ｖ［ｉ］－ｖ［ｊ］）を作成する、請求項１に記載の秘匿計算システム。
【請求項３】
前記第２の情報処理装置は、
ｌｏｇ
２
（Ｎ）以上の最小の整数をＬとして、ｋ＝０，・・・，Ｌ－１に対して、前記Ｅｎｃ（ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
）））を計算することにより、前記Ｅｎｃ（ａｒｇｍａｘ（ｖ［ｉ］，ｖ［ｊ］））を計算する、請求項１又は２に記載の秘匿計算システム。
【請求項４】
整数値を取る入力配列ｖ［０］，・・・，ｖ［Ｎ－１］を所持する第１の情報処理装置と、前記入力配列ｖ［０］，・・・，ｖ［Ｎ－１］の最大値を与えるインデックスの暗号文を計算する第２の情報処理装置とが含まれる秘匿計算システムに用いられる秘匿計算方法であって、
前記第１の情報処理装置が、
前記入力配列ｖ［０］，・・・，ｖ［Ｎ－１］をそれぞれ準同型暗号により暗号化した暗号文配列ｃ［０］＝Ｅｎｃ（ｖ［０］），・・・，ｃ［Ｎ－１］＝Ｅｎｃ（ｖ［Ｎ－１］）を生成し、
前記暗号文配列ｃ［０］，・・・，ｃ［Ｎ－１］を前記第２の情報処理装置に送信し、
前記第２の情報処理装置が、
前記暗号文配列ｃ［０］，・・・，ｃ［Ｎ－１］と、ＥＯＨＶ（ｖ［ｉ］－ｖ［ｊ］）（ただし、ｉ，ｊ∈｛０，・・・，Ｎ－１｝、ｉ＜ｊ）とを用いて、ｃ＝Ｅｎｃ（Ｈ（ｖ［ｉ］－ｖ［ｊ］））（ただし、Ｈ（ｘ）はｘ≧０である場合は１、ｘ＜０である場合は０を返す関数）を計算し、
ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
））＝ｓｅｌ（ｃ，ｉ
ｋ
，ｊ
ｋ
）を用いて、Ｅｎｃ（ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
）））によりＥｎｃ（ａｒｇｍａｘ（ｖ［ｉ］，ｖ［ｊ］））を計算し、
前記ｓｅｌ（ｃ，ｉ
ｋ
，ｊ
ｋ
）は、ｉ，ｊをそれぞれ２進数で表現したときのｋビット目のビット値ｉ
ｋ
，ｊ
ｋ
に対して、ｃ＝Ｅｎｃ（１）である場合はＥｎｃ（ｉ
ｋ
）、ｃ＝Ｅｎｃ（０）である場合はＥｎｃ（ｊ
ｋ
）を返す関数である、
秘匿計算方法。

発明の詳細な説明【技術分野】
【０００１】
本開示は、秘匿計算システム及び秘匿計算方法に関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
ａ，ｂを実数としたとき、そのどちらが大きな値であるかはｍａｘ（ａ，ｂ）＝ｍａｘ（ａ－ｂ，０）＋ｂで求めることができる。これは、１つの要素のみが１で、それ以外の要素が０であるベクトルの各要素を暗号化した暗号化ベクトル（非特許文献１）を用いることにより、入力が準同型暗号文である場合にも適用することができる。以下、１つの要素のみが１で、それ以外の要素が０であるベクトルの各要素を暗号化した暗号化ベクトルをＥＯＨＶ（Encrypted One Hot Vector）と呼ぶことにする。
【０００３】
また、準同型暗号により暗号化された配列のうち、最大値を取る配列のインデックスを計算（つまり、ａｒｇｍａｘを計算）するには、選択関数と呼ばれる関数が用いられる。なお、選択関数とは、０又は１を取るｃと実数ａ，ｂとを入力として、ｃ＝１のときはａ、ｃ＝０のときはｂを返す関数である。
【先行技術文献】
【非特許文献】
【０００４】
K. Nuida, S. Ohata, S. Mitsunari, and N. Attrapadung., "Arbitrary univariate function evaluation and re-encryption protocols over lifted-elgamal type ciphertexts.", Cryptology ePrint Archive, Report 2019/1233, 2019. https://eprint.iacr.org/2019/1233.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、選択関数を加法準同型暗号で実装するには１変数関数への変換が必要になるが、この場合、ＥＯＨＶのサイズが配列のインデックスの大きさの２乗に比例するため効率が悪くなるという問題がある。
【０００６】
本開示は、上記の点に鑑みてなされたもので、準同型暗号を利用したａｒｇｍａｘ計算を効率化することを目的とする。
【課題を解決するための手段】
【０００７】
本開示の一態様による秘匿計算システムは、整数値を取る入力配列ｖ［０］，・・・，ｖ［Ｎ－１］を所持する第１の情報処理装置と、前記入力配列ｖ［０］，・・・，ｖ［Ｎ－１］の最大値を与えるインデックスの暗号文を計算する第２の情報処理装置とが含まれる秘匿計算システムであって、前記第１の情報処理装置は、前記入力配列ｖ［０］，・・・，ｖ［Ｎ－１］をそれぞれ準同型暗号により暗号化した暗号文配列ｃ［０］＝Ｅｎｃ（ｖ［０］），・・・，ｃ［Ｎ－１］＝Ｅｎｃ（ｖ［Ｎ－１］）を生成し、前記暗号文配列ｃ［０］，・・・，ｃ［Ｎ－１］を前記第２の情報処理装置に送信し、前記第２の情報処理装置は、前記暗号文配列ｃ［０］，・・・，ｃ［Ｎ－１］と、ＥＯＨＶ（ｖ［ｉ］－ｖ［ｊ］）（ただし、ｉ，ｊ∈｛０，・・・，Ｎ－１｝、ｉ＜ｊ）とを用いて、ｃ＝Ｅｎｃ（Ｈ（ｖ［ｉ］－ｖ［ｊ］））（ただし、Ｈ（ｘ）はｘ≧０である場合は１、ｘ＜０である場合は０を返す関数）を計算し、ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
））＝ｓｅｌ（ｃ，ｉ
ｋ
，ｊ
ｋ
）を用いて、Ｅｎｃ（ｆ（（ｃ，ｉ
ｋ
，ｊ
ｋ
）））によりＥｎｃ（ａｒｇｍａｘ（ｖ［ｉ］，ｖ［ｊ］））を計算し、前記ｓｅｌ（ｃ，ｉ
ｋ
，ｊ
ｋ
）は、ｉ，ｊをそれぞれ２進数で表現したときのｋビット目のビット値ｉ
ｋ
，ｊ
ｋ
に対して、ｃ＝Ｅｎｃ（１）である場合はＥｎｃ（ｉ
ｋ
）、ｃ＝Ｅｎｃ（０）である場合はＥｎｃ（ｊ
ｋ
）を返す関数である。
【発明の効果】
【０００８】
準同型暗号を利用したａｒｇｍａｘ計算を効率化することができる。
【図面の簡単な説明】
【０００９】
ａｒｇｍａｘの計算アルゴリズムの一例を示す図である。
ａｒｇｍａｘの秘匿計算アルゴリズムの一例を示す図である。
本実施形態に係る秘匿計算システムの全体構成の一例を示す図である。
本実施形態に係るクライアントの機能構成の一例を示す図である。
本実施形態に係るサーバの機能構成の一例を示す図である。
一実施例における秘匿計算処理の一例を示すシーケンス図である。
コンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の一実施形態について、図面を参照しながら詳細に説明する。
（【００１１】以降は省略されています）

関連特許