特許ウォッチ

公開番号2025133672
公報種別公開特許公報(A)
公開日2025-09-11
出願番号2024111959
出願日2024-07-11
発明の名称秘匿計算システム及び秘匿計算方法
出願人NTT株式会社,サイボウズ・ラボ株式会社
代理人弁理士法人ITOH
主分類G09C 1/00 20060101AFI20250904BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】準同型暗号を利用して、内積の近似値を効率的に計算する秘匿計算方法及びシステムを提供する。
【解決手段】秘匿計算システムにおいて、クライアントとサーバは整数値Sを共有し、クライアントは、所持する整数ベクトルxの各要素x_iをS^w+1,・・・,Sにより順次除算して整数集合(a_i1,a_i2,・・・,a_iw+1)に分割し、整数集合(a_i1,a_i2,・・・,a_iw+1)を準同型暗号により暗号化した暗号文Enc(a_ij)を送信し、サーバは、整数ベクトルyの各要素y_iをS^w+1,・・・,Sにより順次除算して整数集合(a_i1',a_i2',・・・,a_iw+1')に分割し、暗号文Enc(a_ij)(1≦j≦w+1)と、整数集合(a_i1',a_i2',・・・,a_iw+1')とを用いて、整数ベクトルxと整数ベクトルyとの内積の近似値の暗号文c_x'yを計算し、暗号文c_x'yをクライアント送信する。
【選択図】図4
特許請求の範囲【請求項１】
整数値を取る要素ｘ
ｉ
（ただし、Ｄを予め決められた１以上の整数として、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｘを所持する第１の情報処理装置と、整数値を取る要素ｙ
ｉ
（ただし、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｙを所持する第２の情報処理装置とが含まれる秘匿計算システムであって、
前記第１の情報処理装置は、
前記第２の情報処理装置と共有する整数値Ｓを用いて、前記整数ベクトルｘの各要素ｘ
ｉ
をＳ
ｗ＋１
，・・・，Ｓ（ただし、ｗは予め決められた１以上の整数）により順次除算することにより整数集合（ａ
ｉ１
，ａ
ｉ２
，・・・，ａ
ｉｗ＋１
）に分割し、
前記整数集合（ａ
ｉ１
，ａ
ｉ２
，・・・，ａ
ｉｗ＋１
）をそれぞれ準同型暗号により暗号化した暗号文Ｅｎｃ（ａ
ｉｊ
）（１≦ｊ≦ｗ＋１）を前記第２の情報処理装置に送信し、
前記第２の情報処理装置は、
前記整数値Ｓを用いて、前記整数ベクトルｙの各要素ｙ
ｉ
をＳ
ｗ＋１
，・・・，Ｓにより順次除算することにより整数集合（ａ
ｉ１
'，ａ
ｉ２
'，・・・，ａ
ｉｗ＋１
'）に分割し、
前記暗号文Ｅｎｃ（ａ
ｉｊ
）（１≦ｊ≦ｗ＋１）と、前記整数集合（ａ
ｉ１
'，ａ
ｉ２
'，・・・，ａ
ｉｗ＋１
'）とを用いて、前記整数ベクトルｘと前記整数ベクトルｙとの内積の近似値の暗号文ｃ
ｘ
'ｙを計算し、
前記暗号文ｃ
ｘ
'ｙを前記第１の情報処理装置に送信する、
秘匿計算システム。
続きを表示（約 3,400 文字）【請求項２】
前記第２の情報処理装置は、
ｘ
ｉ
ｙ
ｉ
／Ｓ
ｗ＋１
の近似値の暗号文のｉに関する総和を前記暗号文ｃ
ｘ
'ｙとして計算する、請求項１に記載の秘匿計算システム。
【請求項３】
前記第２の情報処理装置は、
Ｓ
ｗ＋１
，・・・，Ｓの各々により事前に計算された値を更に用いて、ｘ
ｉ
ｙ
ｉ
／Ｓ
ｗ＋１
の近似値の暗号文のｉに関する総和を前記暗号文ｃ
ｘ
'ｙとして計算する、請求項１又は２に記載の秘匿計算システム。
【請求項４】
整数値を取る要素ｘ
ｉ
（ただし、Ｄを予め決められた１以上の整数として、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｘを所持する第１の情報処理装置と、整数値を取る要素ｙ
ｉ
（ただし、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｙを所持する第２の情報処理装置とが含まれる秘匿計算システムであって、
前記第１の情報処理装置は、
前記整数ベクトルｘの各要素ｘ
ｉ
を二進数展開することにより係数｛ｘ
ｉｊ
｝
ｊ＝０，・・・，ｎ
を算出し、
前記係数｛ｘ
ｉｊ
｝
ｊ＝０，・・・，ｎ
をそれぞれ準同型暗号により暗号化した暗号文Ｅｎｃ（ｘ
ｉｊ
）（０≦ｊ≦ｎ）を前記第２の情報処理装置に送信し、
前記第２の情報処理装置は、
前記整数ベクトルｙの各要素ｙ
ｉ
を二進数展開することにより係数｛ｙ
ｉｊ
｝
ｊ＝０，・・・，ｎ
を算出し、
前記係数｛ｙ
ｉｊ
｝
ｊ＝０，・・・，ｎ
と、前記暗号文Ｅｎｃ（ｘ
ｉｊ
）（０≦ｊ≦ｎ）とを用いて、ｘ・ｙ／２
ｎ
の近似値の暗号文ｃ
ｘ
'ｙを計算し、
前記暗号文ｃ
ｘ
'ｙを前記第１の情報処理装置に送信する、
秘匿計算システム。
【請求項５】
前記第１の情報処理装置は、
前記整数ベクトルｘの各要素ｘ
ｉ
を、ｒｏｕｎｄ関数を使用した二進数展開である修正二進数展開することにより前記係数｛ｘ
ｉｊ
｝
ｊ＝０，・・・，ｎ
を算出し、
前記第２の情報処理装置は、
前記整数ベクトルｙの各要素ｙ
ｉ
を、前記修正二進数展開することにより前記係数｛ｙ
ｉｊ
｝
ｊ＝０，・・・，ｎ
を算出し、
前記係数｛ｙ
ｉｊ
｝
ｊ＝０，・・・，ｎ
と、前記暗号文Ｅｎｃ（ｘ
ｉｊ
）（０≦ｊ≦ｎ）とを用いて、ｉ＝０，・・・，Ｄ－１に関するｍｕｌ
Ｈ
（Ｅｎｃ（ｘ
ｉ
'），ｙ
ｉ
）：＝Ｅｎｃ（ｘ
ｉ，ｎ
）ｙ
ｉ
＋Ｅｎｃ（ｘ
ｉ，ｎ－１
）ｆｏｏｒ（ｙ
ｉ
／２
１
）＋・・・＋Ｅｎｃ（ｘ
ｉ，０
）ｆｏｏｒ（ｙ
ｉ
／２
ｎ
）の和ｃ
Ｈ
を、ｉ＝０，・・・，Ｄ－１に関するｍｕｌ
Ｌ
（Ｅｎｃ（ｘ
ｉ
'），ｙ
ｉ
）：＝Ｅｎｃ（ｘ
ｉ，０
）ｙ
ｉ，ｎ－１
＋Ｅｎｃ（ｘ
ｉ，１
）ｙ
ｉ，ｎ－２
＋・・・＋Ｅｎｃ（ｘ
ｉ，ｎ－１
）ｙ
ｉ，０
の和ｃ
Ｌ
に基づく値で補正することにより、ｘ・ｙ／２
ｎ
の近似値の暗号文ｃ
ｘ
'ｙを計算する、請求項４に記載の秘匿計算システム。
【請求項６】
整数値を取る要素ｘ
ｉ
（ただし、Ｄを予め決められた１以上の整数として、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｘを所持する第１の情報処理装置と、整数値を取る要素ｙ
ｉ
（ただし、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｙを所持する第２の情報処理装置とが含まれる秘匿計算システムに用いられる秘匿計算方法であって、
前記第１の情報処理装置が、
前記第２の情報処理装置と共有する整数値Ｓを用いて、前記整数ベクトルｘの各要素ｘ
ｉ
をＳ
ｗ＋１
，・・・，Ｓ（ただし、ｗは予め決められた１以上の整数）により順次除算することにより整数集合（ａ
ｉ１
，ａ
ｉ２
，・・・，ａ
ｉｗ＋１
）に分割するステップと、
前記整数集合（ａ
ｉ１
，ａ
ｉ２
，・・・，ａ
ｉｗ＋１
）をそれぞれ準同型暗号により暗号化した暗号文Ｅｎｃ（ａ
ｉｊ
）（１≦ｊ≦ｗ＋１）を前記第２の情報処理装置に送信するステップと、を実行し、
前記第２の情報処理装置が、
前記整数値Ｓを用いて、前記整数ベクトルｙの各要素ｙ
ｉ
をＳ
ｗ＋１
，・・・，Ｓにより順次除算することにより整数集合（ａ
ｉ１
'，ａ
ｉ２
'，・・・，ａ
ｉｗ＋１
'）に分割するステップと、
前記暗号文Ｅｎｃ（ａ
ｉｊ
）（１≦ｊ≦ｗ＋１）と、前記整数集合（ａ
ｉ１
'，ａ
ｉ２
'，・・・，ａ
ｉｗ＋１
'）とを用いて、前記整数ベクトルｘと前記整数ベクトルｙとの内積の近似値の暗号文ｃ
ｘ
'ｙを計算するステップと、
前記暗号文ｃ
ｘ
'ｙを前記第１の情報処理装置に送信するステップと、を実行する、
秘匿計算方法。
【請求項７】
整数値を取る要素ｘ
ｉ
（ただし、Ｄを予め決められた１以上の整数として、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｘを所持する第１の情報処理装置と、整数値を取る要素ｙ
ｉ
（ただし、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｙを所持する第２の情報処理装置とが含まれる秘匿計算システムに用いられる秘匿計算方法であって、
前記第１の情報処理装置が、
前記整数ベクトルｘの各要素ｘ
ｉ
を二進数展開することにより係数｛ｘ
ｉｊ
｝
ｊ＝０，・・・，ｎ
を算出するステップと、
前記係数｛ｘ
ｉｊ
｝
ｊ＝０，・・・，ｎ
をそれぞれ準同型暗号により暗号化した暗号文Ｅｎｃ（ｘ
ｉｊ
）（０≦ｊ≦ｎ）を前記第２の情報処理装置に送信するステップと、を実行し、
前記第２の情報処理装置が、
前記整数ベクトルｙの各要素ｙ
ｉ
を二進数展開することにより係数｛ｙ
ｉｊ
｝
ｊ＝０，・・・，ｎ
を算出するステップと、
前記係数｛ｙ
ｉｊ
｝
ｊ＝０，・・・，ｎ
と、前記暗号文Ｅｎｃ（ｘ
ｉｊ
）（０≦ｊ≦ｎ）とを用いて、ｘ・ｙ／２
ｎ
の近似値の暗号文ｃ
ｘ
'ｙを計算するステップと、
前記暗号文ｃ
ｘ
'ｙを前記第１の情報処理装置に送信するステップと、を実行する、
秘匿計算方法。

発明の詳細な説明【技術分野】
【０００１】
本開示は、秘匿計算システム及び秘匿計算方法に関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
準同型暗号は暗号化されたデータに対する演算を秘密鍵なしで行うことができる公開鍵暗号方式である（非特許文献１）。準同型暗号を利用することにより、暗号化したまま内積計算を行うことができる。例えば、クライアントＡとサーバＢの２パーティが存在し、クライアントＡはベクトルｘ、サーバＢはベクトルｙを所持しているものとする。このとき、準同型暗号を利用することにより、クライアントＡは、ベクトルｘの平文をサーバＢに与えることなく、内積ｘ・ｙの計算結果を得ることが可能となる。
【先行技術文献】
【非特許文献】
【０００３】
光成滋生, 「クラウドを支えるこれからの暗号技術」, 秀和システム, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、準同型暗号を利用した内積計算では乗算を多く行う必要があるが、乗算によってデータサイズが大きくなる場合があるという問題がある。
【０００５】
本開示は、上記の点に鑑みてなされたもので、準同型暗号を利用して、内積の近似値を効率的に計算することを目的とする。
【課題を解決するための手段】
【０００６】
本開示の一態様による秘匿計算システムは、整数値を取る要素ｘ
ｉ
（ただし、Ｄを予め決められた１以上の整数として、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｘを所持する第１の情報処理装置と、整数値を取る要素ｙ
ｉ
（ただし、ｉは０以上Ｄ－１以下の整数値）で構成される整数ベクトルｙを所持する第２の情報処理装置とが含まれる秘匿計算システムであって、前記第１の情報処理装置は、前記第２の情報処理装置と共有する整数値Ｓを用いて、前記整数ベクトルｘの各要素ｘ
ｉ
をＳ
ｗ＋１
，・・・，Ｓ（ただし、ｗは予め決められた１以上の整数）により順次除算することにより整数集合（ａ
ｉ１
，ａ
ｉ２
，・・・，ａ
ｉｗ＋１
）に分割し、前記整数集合（ａ
ｉ１
，ａ
ｉ２
，・・・，ａ
ｉｗ＋１
）をそれぞれ準同型暗号により暗号化した暗号文Ｅｎｃ（ａ
ｉｊ
）（１≦ｊ≦ｗ＋１）を前記第２の情報処理装置に送信し、前記第２の情報処理装置は、前記整数値Ｓを用いて、前記整数ベクトルｙの各要素ｙ
ｉ
をＳ
ｗ＋１
，・・・，Ｓにより順次除算することにより整数集合（ａ
ｉ１
'，ａ
ｉ２
'，・・・，ａ
ｉｗ＋１
'）に分割し、前記暗号文Ｅｎｃ（ａ
ｉｊ
）（１≦ｊ≦ｗ＋１）と、前記整数集合（ａ
ｉ１
'，ａ
ｉ２
'，・・・，ａ
ｉｗ＋１
'）とを用いて、前記整数ベクトルｘと前記整数ベクトルｙとの内積の近似値の暗号文ｃ
ｘ
'ｙを計算し、前記暗号文ｃ
ｘ
'ｙを前記第１の情報処理装置に送信する。
【発明の効果】
【０００７】
準同型暗号を利用して、内積の近似値を効率的に計算することができる。
【図面の簡単な説明】
【０００８】
本実施形態に係る秘匿計算システムの全体構成の一例を示す図である。
本実施形態に係るクライアントの機能構成の一例を示す図である。
本実施形態に係るサーバの機能構成の一例を示す図である。
実施例１における秘匿計算処理の一例を示すシーケンス図である。
実施例２における秘匿計算処理の一例を示すシーケンス図である。
実施例３における秘匿計算処理の一例を示すシーケンス図である。
実施例４における秘匿計算処理の一例を示すシーケンス図である。
コンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【０００９】
以下、本発明の一実施形態について、図面を参照しながら詳細に説明する。
【００１０】
＜従来技術とその課題＞
≪準同型暗号≫
準同型暗号（Homomorphic Encryption, HE）とは準同型性を持つ暗号方式のことであり、２つの暗号文が与えられた際に、平文や秘密鍵なしで演算を行うことができ、かつ、その演算結果が正常に復号できるという性質を持つ。準同型暗号は、基本的に、鍵生成関数Ｇｅｎ、暗号化関数Ｅｎｃ、復号関数Ｄｅｃ、準同型演算関数Ｅｖａｌで構成される。
（【００１１】以降は省略されています）

関連特許