(57)【要約】  秘密計算による冪剰余をより少ない通信量、通信回数で実現する情報処理装置を提供する。情報処理装置は、部分冪剰余計算部と、部分冪剰余合成部と、を備える。部分冪剰余計算部は、入力された平文の底及び法と、分散された指数と、から平文の分散された指数の冪乗の剰余に関する分散値の組を部分冪剰余として計算する。部分冪剰余合成部は、部分冪乗余から平文の分散された指数の合計値の冪乗の剰余に関する分散値を冪乗余の分散値として計算する。
2020152831.tif 000002
【特許請求の範囲】
【請求項１】
入力された平文の底及び法と、分散された指数と、から前記平文の分散された指数の冪剰の剰余に関する分散値の組を部分冪剰余として計算する、部分冪剰余計算部と、
前記部分冪剰余から前記平文の前記分散された指数の合計値の冪剰の剰余に関する分散値を冪剰余の分散値として計算する、部分冪剰余合成部と、
を備える、情報処理装置。
【請求項２】
乗算の秘密計算を行う算術演算部をさらに備え、
前記部分冪剰余合成部は、前記算術演算部を用いて前記冪剰余の分散値を計算する、請求項１に記載の情報処理装置。
【請求項３】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部をさらに備える、請求項１又は２に記載の情報処理装置。
【請求項４】
平文とシェアを格納する、データ記憶部をさらに備える、請求項１乃至３のいずれか一項に記載の情報処理装置。
【請求項５】
前記部分冪剰余合成部は、前記部分冪剰余から前記平文の前記分散された指数の合計値の冪剰の剰余に関する分散値を仮冪剰余の分散値として計算し、
前記仮冪剰余の分散値から前記冪剰余の分散値を計算する、仮冪剰余補正部をさらに備える、請求項１乃至４のいずれか一項に記載の情報処理装置。
【請求項６】
少なくとも前記平文の分散された指数の最下位ビットの分散値を秘密計算によって計算する、論理演算部をさらに備える、請求項１乃至５のいずれか一項に記載の情報処理装置。
【請求項７】
前記冪剰余の分散値は、（２、３）閾値のアクセス構造を有する複製型秘密分散を用いた秘密計算により計算される、請求項１乃至６のいずれか一項に記載の情報処理装置。
【請求項８】
入力された平文の底及び法と、分散された指数と、から前記平文の分散された指数の冪剰の剰余に関する分散値の組を部分冪剰余として計算するステップと、
前記部分冪剰余から前記平文の前記分散された指数の合計値の冪剰の剰余に関する分散値を冪剰余の分散値として計算するステップと、
を含む、秘密計算方法。
【請求項９】
入力された平文の底及び法と、分散された指数と、から前記平文の分散された指数の冪剰の剰余に関する分散値の組を部分冪剰余として計算する処理と、
前記部分冪剰余から前記平文の前記分散された指数の合計値の冪剰の剰余に関する分散値を冪剰余の分散値として計算する処理と、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、秘密計算方法及びプログラムに関する。特に、複数の装置が互いに通信を介しながら計算することで与えられた関数の出力を計算する方法で、これらのいずれの装置も十分な数の多装置間で互いに扱うデータを共有しない限り、関数への入力や出力に関する情報を得ることができない方法に関する。
【背景技術】
【０００２】
秘密計算法は、関連する主体に対して計算過程と結果を秘匿することができる技術である。データをクラウドのような第３者が管理する複数サーバに分散して保管することで、データに対してあらゆる演算を実行することができる。第３者には、データ、計算過程、計算結果を知られることがないため、個人情報のような機微な情報に対する分析処理をアウトソースするために用いることができる。【０００３】
非特許文献１には、秘密計算に用いる乱数の生成が開示されている。非特許文献２には「ビット分解」と称される技術が開示されている。ビット分解の詳細は後述する。非特許文献３は、ＰＲＧ（Psudo Random Generator）を、鍵とインデックスを入力としてｎビットの数値列を出力する擬似乱数生成器を開示する。非特許文献３等に記載されている。非特許文献４には、ビット注入（ｂｉｔ  ｉｎｊｅｃｔｉｏｎ）と称される技術が開示されている。ビット注入の詳細は後述する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】軽量検証可能３  パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理  五十嵐大  千田浩司  濱田浩気  高橋克己  SCIS2011
【非特許文献２】少パーティの秘密分散ベース秘密計算のためのO(l)ビット通信ビット分解およびO(|p|’)ビット通信Modulus変換法  五十嵐大  濱田浩気  菊池亮  千田浩司  CSS2013
【非特許文献３】High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority, Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, Kazuma Ohara
【非特許文献４】Generalizing the SPDZ Compiler For Other Protocols, Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara, Hikaru Tsuchida
【発明の概要】
【発明が解決しようとする課題】
【０００５】
なお、上記先行技術文献の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者らによってなされたものである。【０００６】
ここで、冪剰余は、ある値ｘとａ、および法ｐを入力として、ｘ＾ａ  ｍｏｄ  ｐを計算する処理である。ここで、ｘは冪剰余の底、ａは指数である。【０００７】
冪剰余の秘密計算においては、
（１）ｘを秘匿する
（２）ａを秘匿する
（３）ｘとａの両方を秘匿する
という３つのパターンが考えられる。本願開示は、特に（２）の指数ａを秘匿したままｘ＾ａ  ｍｏｄ  ｐを計算する手法に関する。【０００８】
冪剰余は主に暗号要素技術において頻繁に用いられる処理の一つである。このとき、冪剰余の指数は暗号においてしばしば秘匿されるべき値として扱われることが多い。秘密計算で冪剰余を実行できると、分散システムにおいて暗号系処理を実現することができる。一例として、秘密鍵を保護したままデジタル署名を計算することが可能になり、ブロックチェーン等の分散ノード上での秘密鍵保護などの応用が考えられる。既知の冪剰余の計算方法は、数値演算と論理演算の組み合わせによって実現されるため、秘密計算では先に述べたビット分解等を用いてこれを実現できる。しかし、通信量および通信回数は未だに大きく、より効率のよいプロトコルが求められる。【０００９】
本発明は、秘密計算による冪剰余をより少ない通信量、通信回数で実現することに寄与する、情報処理装置、秘密計算方法及びプログラムを提供することを主たる目的とする。
【課題を解決するための手段】
【００１０】
本発明乃至開示の第１の視点によれば、入力された平文の底及び法と、分散された指数と、から前記平文の分散された指数の冪乗の剰余に関する分散値の組を部分冪乗余として計算する、部分冪乗余計算部と、前記部分冪乗余から前記平文の前記分散された指数の合計値の冪乗の剰余に関する分散値を冪乗余の分散値として計算する、部分冪乗余合成部と、を備える、情報処理装置が提供される。【００１１】
本発明乃至開示の第２の視点によれば、入力された平文の底及び法と、分散された指数と、から前記平文の分散された指数の冪乗の剰余に関する分散値の組を部分冪乗余として計算するステップと、前記部分冪乗余から前記平文の前記分散された指数の合計値の冪乗の剰余に関する分散値を冪乗余の分散値として計算するステップと、を含む、秘密計算方法が提供される。【００１２】
本発明乃至開示の第３の視点によれば、入力された平文の底及び法と、分散された指数と、から前記平文の分散された指数の冪乗の剰余に関する分散値の組を部分冪乗余として計算する処理と、前記部分冪乗余から前記平文の前記分散された指数の合計値の冪乗の剰余に関する分散値を冪乗余の分散値として計算する処理と、をコンピュータに実行させるプログラムが提供される。
なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。記憶媒体は、半導体メモリ、ハードディスク、磁気記録媒体、光記録媒体等の非トランジェント（non-transient）なものとすることができる。本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００１３】
本発明乃至開示の各視点によれば、秘密計算による冪剰余をより少ない通信量、通信回数で実現することに寄与する、情報処理装置、秘密計算方法及びプログラムが、提供される。
【図面の簡単な説明】
【００１４】
【図１】一実施形態の概要を説明するための図である。
【図２】第１の実施形態に係るサーバ装置の内部構成の一例を示すブロック図である。
【図３】第１の実施形態に係る冪剰余秘密計算システムの構成例を示すブロック図である。
【図４】第１の実施形態の動作の一例を表すフローチャートである。
【図５】第２の実施形態に係るサーバ装置の内部構成の一例を示すブロック図である。
【図６】第２の実施形態に係る冪剰余秘密計算システムの構成例を示すブロック図である。
【図７】第２の実施形態の動作の一例を表すフローチャートである。
【図８】サーバ装置１０のハードウェア構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１５】
初めに、一実施形態の概要について説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、この概要の記載はなんらの限定を意図するものではない。また、各図におけるブロック間の接続線は、双方向及び単方向の双方を含む。一方向矢印については、主たる信号（データ）の流れを模式的に示すものであり、双方向性を排除するものではない。さらに、本願開示に示す回路図、ブロック図、内部構成図、接続図などにおいて、明示は省略するが、入力ポート及び出力ポートが各接続線の入力端及び出力端のそれぞれに存在する。入出力インターフェイスも同様である。
【００１６】
一実施形態に係る情報処理装置１００は、部分冪乗余計算部１０１と、部分冪乗余合成部１０２と、を備える（図１参照）。部分冪乗余計算部１０１は、入力された平文の底及び法と、分散された指数と、から平文の分散された指数の冪乗の剰余に関する分散値の組を部分冪乗余として計算する。部分冪乗余合成部１０２は、部分冪乗余から平文の分散された指数の合計値の冪乗の剰余に関する分散値を冪乗余の分散値として計算する。
【００１７】
情報処理装置１００は、部分冪乗余を計算し、当該部分冪乗余から冪乗余の分散値を計算する。当該計算は、各装置が持つ指数ａの分散値と入力（平文）ｘから通信なしで実行できるので、（２、３）型ＲＳＳで分散された指数の値を明かすことなく、与えられた底と法に対する冪剰余の秘密計算が効率よく実行できる。即ち、（２、３）秘密分散を用いた３者間秘密計算にて冪剰余を計算する際、通信量、通信回数の点において効率のよい情報処理装置１００が提供される。
【００１８】
初めに、本願開示の前提技術について説明する。
【００１９】
本願開示は、（２、３）閾値のアクセス構造を有する複製型秘密分散（以降（２、３）型ＲＳＳと表記する）を用いた秘密計算に関する。以下、（２、３）型ＲＳＳの説明を行う。
【００２０】
（２、３）閾値型ＲＳＳとは、（２、３）秘密分散の実現方法のひとつである。（２、３）秘密分散とは、入力された値から３つの分散情報を生成する方法で、３つの分散情報は２つ以上からは元の値を復元できるが、１つ以下の分散情報からは元の情報がわからないという特徴を持つ値の分散方法である。
【００２１】
（２、３）型ＲＳＳは、０からｐ−１以下の値ｘを分散する際に、ｘ＝ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ｐ  となるような０からｐ−１以下の３つの値の組（ｒ１、ｒ２、ｒ３）を生成する。さらに、（２、３）型ＲＳＳは、３つの分散情報として、（ｒ１、ｒ２、ｒ３）から２つの値を異なる値を選んだ３組を用いることで、（２、３）秘密分散を実現する。なお、上記ｐは「法」と称される。
【００２２】
秘密分散によって分散された値に関する計算を復元すること無く実行する方法は秘密計算と呼ばれている。以降で、本願開示に関係する（２、３）複製型秘密分散によって分散された値に対する秘密計算法について説明する。まず、値の分散方法について説明し、次に加算、減算、乗算について説明する。ここでは、複数の値が３台の装置に対して分散され、その後、分散された値に対する秘密計算を行うという手順について説明する。３台の装置を、装置１、装置２、装置３と呼んで区別する。
【００２３】
［値の分散方法］
ｐを２以上の整数として、０以上ｐ未満の値ｗを分散する場合、ｗ＝ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ｐ  を満たすランダムに選ばれたｒ１、ｒ２、ｒ３を生成して、以下のように保管する。
装置１に、ｗの分散値として（ｒ１、ｒ２）を保管する。
装置２に、ｗの分散値として（ｒ２、ｒ３）を保管する。
装置３に、ｗの分散値として（ｒ３、ｒ１）を保管する。
どの組もｒ１、ｒ２、ｒ３の何れかが足りないためｗを得られないが、２台以上が保管している情報からならばｗを復元することができることが確認できる。
【００２４】
［加算処理］
先に示した方法によって、装置１、装置２、装置３に分散して保管されている値ｗと値ｗ’に関して実行される加算処理について説明する。なお、ｗ＝ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ｐ  ｗ’＝ｒ１’＋ｒ２’＋ｒ３’  ｍｏｄ  ｐとする。
【００２５】
装置１は、ｗの分散値として（ｓ１、ｔ１）＝（ｒ１、ｒ２）、ｗ’の分散値として（ｓ１’、ｔ１’）＝（ｒ１’、ｒ２’）を保管している。
装置２は、ｗの分散値として（ｓ２、ｔ２）＝（ｒ２、ｒ３）、ｗ’の分散値として（ｓ２’、ｔ２’）＝（ｒ２’、ｒ３’）を保管している。
装置３は、ｗの分散値として（ｓ３、ｔ３）＝（ｒ３、ｒ１）、ｗ’の分散値として（ｓ３’、ｔ３’）＝（ｒ３’、ｒ１’）を保管している。
【００２６】
各装置は、以下の手順に従った処理を行う。
【００２７】
装置１は（ｓ１’’、ｔ１’’）＝（ｒ１’’＝ｓ１＋ｓ１’  ｍｏｄ  ｐ、ｒ２’’＝ｔ１＋ｔ１’ｍｏｄ  ｐ）によって（ｓ１’’、ｔ１’’）を計算し、ｗ＋ｗ’の分散値として保管する。
【００２８】
装置２は（ｓ２’’、ｔ２’’）＝（ｒ２’’＝ｓ２＋ｓ２’  ｍｏｄ  ｐ、ｒ３’’＝ｔ２＋ｔ２’  ｍｏｄ  ｐ）によって（ｓ２’’、ｔ２’’）を計算し、ｗ＋ｗ’の分散値として保管する。
【００２９】
装置３は（ｓ３’’、ｔ３’’）＝（ｒ３’’＝ｓ３＋ｓ３’  ｍｏｄ  ｐ、ｒ１’’＝ｔ３＋ｔ３’  ｍｏｄ  ｐ）によって（ｓ３’’、ｔ３’’）を計算し、ｗ＋ｗ’の分散値として保管する。
【００３０】
それぞれの計算結果は、ｗ＋ｗ’をｗ＋ｗ’＝ｒ１’’＋ｒ２’’＋ｒ３’’ｍｏｄ  ｐとなるｒ１’’、ｒ２’’、ｒ３’’を用いて分散した値となっている。ｒ１’’＋ｒ２’’＋ｒ３’’＝（ｒ１＋ｒ２＋ｒ３）＋（ｒ１’＋ｒ２’＋ｒ３’）＝ｗ＋ｗ’  ｍｏｄ  ｐから確認できる。
【００３１】
［減算処理］
先に示した方法によって、装置１、装置２、装置３に分散して保管されている値ｗと値ｗ’に関して実行される減算処理について説明する。なお、ｗ＝ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ｐ、ｗ’＝ｒ１’＋ｒ２’＋ｒ３’  ｍｏｄ  ｐとする。
【００３２】
装置１は、ｗの分散値として（ｓ１、ｔ１）＝（ｒ１、ｒ２）、ｗ’の分散値として（ｓ１’、ｔ１’）＝（ｒ１’、ｒ２’）を保管している。
装置２は、ｗの分散値として（ｓ２、ｔ２）＝（ｒ２、ｒ３）、ｗ’の分散値として（ｓ２’、ｔ２’）＝（ｒ２’、ｒ３’）を保管している。
装置３は、ｗの分散値として（ｓ３、ｔ３）＝（ｒ３、ｒ１）、ｗ’の分散値として（ｓ３’、ｔ３’）＝（ｒ３’、ｒ１’）を保管している。
【００３３】
各装置は、以下の手順に従った処理を行う。
【００３４】
装置１は（ｓ１’’、ｔ１’’）＝（ｒ１’’＝ｓ１−ｓ１’  ｍｏｄ  ｐ、ｒ２’’＝ｔ１−ｔ１’ｍｏｄ  ｐ）によって（ｓ１’’、ｔ１’’）を計算し、ｗ−ｗ’の分散値として保管する。
装置２は（ｓ２’’、ｔ２’’）＝（ｒ２’’＝ｓ２−ｓ２’  ｍｏｄ  ｐ、ｒ３’’＝ｔ２−ｔ２’  ｍｏｄ  ｐ）によって（ｓ２’’、ｔ２’’）を計算し、ｗ−ｗ’の分散値として保管する。
装置３は（ｓ３’’、ｔ３’’）＝（ｒ３’’＝ｓ３−ｓ３’  ｍｏｄ  ｐ、ｒ１’’＝ｔ３−ｔ３’  ｍｏｄ  ｐ）によって（ｓ３’’、ｔ３’’）を計算し、ｗ−ｗ’の分散値として保管する。
【００３５】
それぞれの計算結果は、ｗ−ｗ’をｗ−ｗ’＝  ｒ１’’＋ｒ２’’＋ｒ３’’ｍｏｄ  ｐとなるｒ１’’、ｒ２’’、ｒ３’’を用いて分散した値となっている。ｒ１’’＋ｒ２’’＋ｒ３’’＝（ｒ１＋ｒ２＋ｒ３）−（ｒ１’＋ｒ２’＋ｒ３’）＝ｗ−ｗ’  ｍｏｄ  ｐから確認できる。
【００３６】
［乗算処理］
先に示した方法によって装置１、装置２、装置３に分散されて保管されているｗと値ｗ’に関して実行される乗算処理について説明する。
【００３７】
まず、各装置がどのような値を保管しているかを示す。ｒ１、ｒ２、ｒ３はｒ１＋ｒ２＋ｒ３  ＝  ｗ  ｍｏｄ  ｐを満たすランダムに選ばれた値であり、ｒ１’、ｒ２’、ｒ３’はｒ１’＋ｒ２’＋ｒ３’  ＝  ｗ’  ｍｏｄ  ２＾ｎ（ｎは正の整数）を満たすランダムに選ばれた値とする。
【００３８】
装置１は、ｗの分散値として（ｓ１、ｔ１）＝（ｒ１、ｒ２）、ｗ’の分散値として（ｓ１’、ｔ１’）＝（ｒ１’、ｒ２’）を保管する。
装置２は、ｗの分散値として（ｓ２、ｔ２）＝（ｒ２、ｒ３）、ｗ’の分散値として（ｓ２’、ｔ２’）＝（ｒ２’、ｒ３’）を保管する。
装置３は、ｗの分散値として（ｓ３、ｔ３）＝（ｒ３、ｒ１）、ｗ’の分散値として（ｓ３’、ｔ３’）＝（ｒ３’、ｒ１’）を保管する。
【００３９】
各装置は、以下の手順に従った処理を行う。
【００４０】
なお、ｒ１’’＋ｒ２’’＋ｒ３’’＝  ０  ｍｏｄ  ２＾ｎを満たすランダムに選ばれた値として、装置１はｒ１’’を、装置２はｒ２’’を、装置３はｒ３’’を保管しているものとする。このような性質を満たすｒ１’’、ｒ２’’、ｒ３’’は乗算を実行するたびに使い捨てで必要となる。このような３値を３装置が効率的に生成する方法については後述する。
【００４１】
装置１は、ｕ２＝ｓ１ｓ１’＋ｓ１ｔ１’＋ｔ１ｓ１’＋ｒ１’’  ｍｏｄ  ｐ計算し、ｕ１を装置２に送付する。
装置２は、ｕ３＝ｓ２ｓ２’＋ｓ２ｔ２’＋ｔ２ｓ２’＋ｒ２’’  ｍｏｄ  ｐを計算し、ｕ２を装置３に送付する。
装置３は、ｕ１＝ｓ３ｓ３’＋ｓ３ｔ３’＋ｔ３ｓ３’＋ｒ３’’  ｍｏｄ  ｐを計算し、ｕ３を装置１に送付する。
【００４２】
装置１は、（ｕ１、ｕ２）をｗｗ’の分散値として保管する。
装置２は、（ｕ２、ｕ３）をｗｗ’の分散値として保管する。
装置３は、（ｕ３、ｕ１）をｗｗ’の分散値として保管する。
【００４３】
まず、ｕ１＋ｕ２＋ｕ３＝ｒ１ｒ１’＋ｒ１ｒ２’＋ｒ２ｒ１’＋ｒ２ｒ２’＋ｒ２ｒ３’＋ｒ３ｒ２’＋ｒ３ｒ３’＋ｒ３ｒ１’＋ｒ１ｒ３’＋ｒ１’’＋ｒ２’’＋ｒ３’’＝（ｒ１＋ｒ２＋ｒ３）（ｒ１’＋ｒ２’＋ｒ３’）＋ｒ１’’＋ｒ２’’＋ｒ３’’  ＝ｗｗ’  ｍｏｄ  ｐとなっていることが確認できる。
【００４４】
装置１と装置２の保管する値からｗｗ’ｍｏｄ  ｐが同じ計算方法で計算できる。他の装置の組み合わせについても同様である。このような方法によれば、（２、３）型ＲＳＳで分散されているｗ、ｗ’に関する乗算が各値を復元することなく実行され、ｗｗ’を（２、３）型ＲＳＳで分散した値を共有することができる。
【００４５】
［乱数の生成について］
次に、ｒ１＋ｒ２＋ｒ３  ＝  ０  ｍｏｄ  ２＾ｎのように３つ足すと０となる値を、装置１、装置２、装置３が互いに通信することなく、また、各装置が所有する値を他の装置に知られることのない方法で大量に生成する方法について説明する。ここでは、ｒ［ｉ、１］＋ｒ［ｉ、２］＋ｒ［ｉ、３］＝０  ｍｏｄ  ２＾ｎなるｒ［ｉ、１］、ｒ［ｉ、２］、ｒ［ｉ，３］を多くのｉ＝１、…、Ｎに関して生成する方法を説明する。
【００４６】
ＰＲＧ（Psudo Random Generator）を、鍵とインデックスを入力としてｎビットの数値列を出力する擬似乱数生成器とする。インデックスは、カウンタなどで良い。当該方法は、非特許文献３等に記載されている。
【００４７】
まず、装置のセットアップ処理として、ＰＲＧの鍵Ｌ１、Ｌ２、Ｌ３を生成する。装置１にＬ１とＬ３を、装置２にＬ２とＬ１を、装置３にＬ３とＬ２を記憶させているものとする。
【００４８】
各装置はカウンタなどで同期されたインデックスｉｄｘを共有しているものとする。装置１は鍵Ｌ１とインデックスｉｄｘをＰＲＧに入力し、その出力であるｎビットの数値ｒ’［１］を生成する。また、装置１は、鍵Ｌ３とインデックスｉｄｘをＰＲＧに入力し、その出力であるｎビットの数値をｎビット毎に分割した値ｒ’［３］を生成する。そしてｒ［１］＝ｒ’［１］−ｒ’［３］  ｍｏｄ  ｐとする。
【００４９】
装置２は鍵Ｌ２とインデックスｉｄｘをＰＲＧに入力し、その出力であるｎビットの数値ｒ’［２］を生成する。また、装置２は、鍵Ｌ１をＰＲＧに入力し、その出力であるｎビットの数値ｒ’［１］を生成する。そしてｒ［２］＝ｒ’［２］−ｒ’［１］  ｍｏｄ  ｐとする。
【００５０】
装置３は鍵Ｌ３とインデックスｉｄｘをＰＲＧに入力し、その出力であるｎビットの数値ｒ’［３］を生成する。また、装置３は、鍵Ｌ２とインデックスｉｄｘをＰＲＧに入力し、その出力であるｎビットの数値ｒ’［２］を生成する。ｒ［３］＝ｒ’［３］−ｒ’［２］  ｍｏｄ  ｐとする。
【００５１】
ｒ［１］＋ｒ［２］＋ｒ［３］＝ｒ’［１］−ｒ’［３］＋ｒ’［２］−ｒ’［１］＋ｒ［３］−ｒ［２］＝  ０  ｍｏｄ  ｐとなっており、Ｎ組全てが条件を満たす。装置１が生成する値ｒ［１］＝ｒ’［１］−ｒ’［３］ｍｏｄ  ｐに着目すると、装置３はｒ’［１］を得られず、装置２はｒ’［３］を得られない。これより、装置１、装置２はｒ［１］を計算できないことがわかる。これは、ｒ［２］やｒ［３］についても同様である。セットアップ処理が済んでいれば、以上の処理は計算が行われる前などにも実行可能である。
【００５２】
このような（２、３）型ＲＳＳを用いた秘密計算において、ｐ＝２とすると、乗算はＡＮＤ処理、加算・減算は排他的論理和処理と捉えることができる。これによって、ｐ＝２とした場合には論理演算に適した秘密計算法となる。また装置１から３の分散情報をすべて（１、１）（１、１）（１、１）とすると、これは、ｒ１＝１、ｒ２＝１、ｒ３＝１として、１の分散情報になっており、論理積、排他的論理和、定数１によって完全系となり、任意の演算が実行可能となる。
【００５３】
以上の方法は非特許文献１等に記載されている。このような方法には種々のバリエーションを考えることができ、例えば、ｒ１＋ｒ２＋ｒ３＝ｗ  ｍｏｄ  ｐ  に関して、（ｒ１−ｒ２ｍｏｄｐ、ｒ２）、（ｒ２−ｒ３ｍｏｄｐ、ｒ３）、（ｒ３−ｒ１ｍｏｄｐ、ｒ１）を分散情報としても良い。３装置がｒ１、ｒ２、ｒ３のうち異なる二つの組に相当する情報を保有していれば、（２、３）型ＲＳＳ呼ぶことにする。
【００５４】
つまり、任意の演算は、ｐ＝２とした（２、３）型ＲＳＳを用いれば処理可能である。しかし、すべての処理を論理演算で実行することは非効率的であるので、乗算と加減算で構成できるものは、ｐを大きく設定した（２、３）型ＲＳＳを用いた秘密計算で実行するほうが良い。ｐの値としては，プロトコル設計における利便性や実装の都合などからＺ＿ｐ素数あるいは２＾ｍ（ｍは任意の整数）が選択されることが多い。
【００５５】
さらに、数値演算と論理演算を組み合わせたい場合もある。例として、それぞれ２＾４より小さい値であるａ、ｂ、ｃを入力として、ａ＊ｂ  ｍｏｄ  ２＾４＜ｃを処理する場合を考える。この場合、ａ＊ｂを数値演算として処理し、比較演算を論理演算として実行したい。まず数値演算としてａ＊ｂを計算したいが、これをｃと比較する処理を数値演算として表現することは難しい。
【００５６】
このような問題を解決するため、非特許文献２に記載の「ビット分解」と呼ばれる処理が知られている。ビット分解は、数値計算向けの分散情報を論理演算向けの分散情報に変換するための処理である。
【００５７】
法としてｐ＝８を用いた（２、３）型ＲＳＳによって値ｗ＝５を用いて分散し、装置１が（１、２）を記憶し、装置２が（２、２）を記憶し、装置３が（２、１）を記憶している場合を考える。ビット分解を用いれば、これらの情報から、５の２進表記である１と０と１の各ビットに対する分散情報を得ることができる。
【００５８】
具体的には、ビット分解が実行された後、
装置１は、１ビット目に関して（１、１）、２ビット目に関して、（０、１）、３ビット目に関して（１、０）、４ビット目に関して（０、０）所有する。
装置２は、１ビット目に関して（１、１）、２ビット目に関して、（１、１）、３ビット目に関して（０、０）、４ビット目に関して（０、０）を所有する。
装置３は、１ビット目に関して（１、１）、２ビット目に関して、（１、０）、３ビット目に関して（０、０）、４ビット目に関して（０、０）を所有する。
【００５９】
ビット分解に関する既存の技術として、以下に非特許文献２に記載の方法の概要を示す。この方法は以下のような手順でビット分解を実行する。ビット分解を実行したい数は、ｒ＝ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ｐとなるｒ１、ｒ２、ｒ３を用いて分散されているものとする。なお、非特許文献２では、ｐ＝２＾ｎ−１によって表されるメルセンヌ素数を用いる。メルセンヌ素数の性質は、手順２においてｓを効率的に計算することに作用している。
【００６０】
手順１：ｒ１２＝ｒ１＋ｒ２  ｍｏｄ  ｐ、ｒ３を分散する。
手順２：ｒ１２＋ｒ３がｐより大きいかどうかを判定し、大きい場合にはｓ＝１とし、それ以外の場合はｓ＝０となるような秘密計算を実行する。
手順３：ｒ１２＋ｒ３＋ｓ  ｍｏｄ  ２＾ｎの計算を下位桁からビット毎に全加算器の秘密計算を実行する。
【００６１】
非特許文献２の方法は、ｐがｎビットの素数であるとして１０ｎ＋４ビットの通信量によってビット分解を実行できると記載されている。
【００６２】
また、ビット分解の逆の変換、すなわち論理計算向けの分散値を数値計算向けの分散値に変換する方法として、ビット注入（ｂｉｔ  ｉｎｊｅｃｔｉｏｎ）が存在する。ビット注入に関する従来技術として、以下に非特許文献４の方法の概略を説明する。
【００６３】
ビット注入を実行したい数ｒはｒ＝ｒ１＋ｒ２＋ｒ３  ｍｏｄ  ２となるｒ１、ｒ２、ｒ３を用いて分散されているものとする。
手順１：装置１、装置２、装置３はそれぞれ自身の持つｒの分散値から、ローカルの計算によってｒ１、ｒ２、ｒ３の法ｐ上の分散値を計算する（詳細は後述する）。
手順２：装置１、装置２、装置３は、ｒ１、ｒ２、ｒ３の分散値から、法ｐ上の加算と乗算を用いてｒ１＋ｒ２＋ｒ３を計算し、ｒの法ｐ上の分散値を得る。
ここで、手順１の方法は以下のようにして実行される。なお、装置１は（ｒ１、ｒ２）を、装置２は（ｒ２、ｒ３）を、装置３は（ｒ３、ｒ１）を持っているものとする。
【００６４】
装置１は、（ｒ１、０）を自身のｒ１の分散値とし、（０、ｒ２）を自身のｒ２の分散値とし、（０、０）を自身のｒ３の分散値とする。
装置２は、（０、０）を自身のｒ１の分散値とし、（ｒ２、０）を自身のｒ２の分散値とし、（０、ｒ３）を自身のｒ３の分散値とする。
装置３は、（０、ｒ１）を自身のｒ１の分散値とし、（０、０）を自身のｒ２の分散値とし、（ｒ３、０）を自身のｒ３の分散値とする。
【００６５】
これはすなわち、ｒ１がｒ１＝ｒ１＋０＋０  ｍｏｄ  ２、ｒ２がｒ２＝０＋ｒ２＋０  ｍｏｄ  ２、ｒ３がｒ３＝０＋０＋ｒ３  ｍｏｄ  ２となるような値によって分散されているものと捉えることができる。各装置は、これらの分散値を自身の持つｒの分散値から通信なしで計算できる。ここで、ｒはもともとｍｏｄ  ２上の分散値（論理演算用の分散値）であったが、上記のｒ１、ｒ２、ｒ３の分散値の計算は、ｒ１＝ｒ１＋０＋０  ｍｏｄ  ｐ、ｒ２がｒ２＝０＋ｒ２＋０  ｍｏｄ  ｐ、ｒ３がｒ３＝０＋０＋ｒ３  ｍｏｄ  ｐであると捉えてもよい。すなわち、この計算によって得られるｒ１、ｒ２、ｒ３の分散値は数値演算向けの分散値として扱うことができる。この手法によって、論理演算の分散値を数値演算の分散値に変換することができるため、数値演算の秘密計算を組み合わせて所望の分散値を計算することが可能となる。
【００６６】
ここで、指数ａはａ＝ａ１＋ａ２＋ａ３  ｍｏｄ  ｐとなるようなａによって分散されているものとする。本願開示では、ある底ｘとａの分散値を用いてｘ＾ａ  ｍｏｄ  ｐの秘密計算を行う際、ｘ＾（ａ１）  ｍｏｄ  ｐ、ｘ＾（ａ２）  ｍｏｄ  ｐ、ｘ＾（ａ３）  ｍｏｄ  ｐの分散値を各装置にて他の装置と非通信で計算する。以下、これらｘ＾（ａ１）  ｍｏｄ  ｐ、ｘ＾（ａ２）  ｍｏｄ  ｐ、ｘ＾（ａ３）  ｍｏｄ  ｐの組をｘ＾ａの部分冪剰余と表記する。
【００６７】
各装置は、以下のような計算を行う。なお、装置１は（ａ１、ａ２）を、装置２は（ａ２、ａ３）を、装置３は（ａ３、ａ１）を所有しているものとする。
【００６８】
装置１は、（ｘ＾ａ１、０）を自身のｘ＾ａ１の分散値とし、（０、ｘ＾ａ２）を自身のｘ＾ａ２の分散値とし、（０、０）を自身のｘ＾ａ３の分散値とする。装置２は、（０、０）を自身のｘ＾ａ１の分散値とし、（ｘ＾ａ２、０）を自身のｘ＾ａ２の分散値とし、（０、ｘ＾ａ３）を自身のｘ＾ａ３の分散値とする。装置３は、（０、ｘ＾ａ１）を自身のｘ＾ａ１の分散値とし、（０、０）を自身のｘ＾ａ２の分散値とし、（ｘ＾ａ３、０）を自身のｘ＾ａ３の分散値とする。
【００６９】
上記の計算は、各装置が持つａの分散値とｘから通信なしで実行できることが確認できる。指数関数の性質により、ｓ＝ｘ＾ａ１・ｘ＾ａ２・ｘ＾ａ３  ｍｏｄ  ｐ＝  ｘ＾（ａ１＋ａ２＋ａ３）  ｍｏｄ  ｐとなるため、数値乗算の秘密計算２回によってｓ＝ｘ＾（ａ１＋ａ２＋ａ３）  ｍｏｄ  ｐを計算できる。
【００７０】
以下、部分冪剰余から上記の計算で得られるｓ＝ｘ＾（ａ１＋ａ２＋ａ３）  ｍｏｄ  ｐを仮冪剰余と表記する。
【００７１】
ここで、ａ＝ａ１＋ａ２＋ａ３  ｍｏｄ  ｐであったことを想起すると、計算したい所望の値はｓ’＝ｘ＾ａ＝ｘ＾（ａ１＋ａ２＋ａ３  ｍｏｄ  ｐ）  ｍｏｄ  ｐ  となる。ｘ＾（ａ１＋ａ２＋ａ３）  ｍｏｄ  ｐはａ１＋ａ２＋ａ３が法ｐを超える場合にはｘ＾（ａ１＋ａ２＋ａ３  ｍｏｄ  ｐ）  ｍｏｄ  ｐと同じではない。したがって、所望の冪剰余計算を完了するにはｘ＾ａ１・ｘ＾ａ２・ｘ＾ａ３の秘密計算の後にａ１＋ａ２＋ａ３が法ｐを超えた場合の追加処理を仮冪剰余に対して行う。当該処理に関しては、法ｐが素数の場合、及び、２＾ｍの場合で異なる実施形態を取り得る。
【００７２】
以下に具体的な実施の形態について、図面を参照してさらに詳しく説明する。なお、各実施形態において同一構成要素には同一の符号を付し、その説明を省略する。
【００７３】
［第１の実施形態］
第１の実施形態について、図面を用いてより詳細に説明する。
【００７４】
図２〜図４を参照しつつ、第１の実施形態に係る冪剰余秘密計算システムについて説明する。
【００７５】
図２は、第１の実施形態に係るサーバ装置１０の内部構成（処理構成）の一例を示すブロック図である。冪乗余秘密計算システムには、複数のサーバ装置（秘密計算サーバ装置）が含まれる。以降の説明において、個別の装置をサフィックスｉにより特定する。
【００７６】
図２に示す通り、第ｉのサーバ装置１０＿ｉは、第ｉの基本演算シード記憶部１１＿ｉと、第ｉのデータ記憶部１２＿ｉと、第ｉの部分冪剰余計算部１３＿ｉと、第ｉの部分冪剰余合成部１４＿ｉと、第ｉの算術演算部１５＿ｉと、を含む。なお、第ｉの基本演算シード記憶部１１＿ｉと、第＿ｉのデータ記憶部１２＿ｉと、第ｉの部分冪剰余計算部１３＿ｉと、第ｉの部分冪剰余合成部１４＿ｉと、第ｉの算術演算部１５＿ｉとはそれぞれ接続されている。
【００７７】
第ｉの基本演算シード記憶部１１＿ｉは、シェアについての演算を行う際の乱数を生成するためのシードを格納する。
【００７８】
第ｉのデータ記憶部１２＿ｉは、平文とシェアを格納する。
【００７９】
第ｉの部分冪剰余計算部１３＿ｉは、部分冪乗余を計算する。具体的には、第ｉの部分冪剰余計算部１３＿ｉは、入力された平文の底及び法と、分散された指数と、から平文の分散された指数の冪乗の剰余に関する分散値の組を計算する。上述の例では、ｘ＾（ａ１）  ｍｏｄ  ｐ、ｘ＾（ａ２）  ｍｏｄ  ｐ、ｘ＾（ａ３）  ｍｏｄ  ｐの組が「部分冪剰余」として計算される。
【００８０】
第ｉの部分冪剰余合成部１４＿ｉは、冪乗余の分散値を計算する。具体的には、部分冪乗余から平文の分散された指数の合計値の冪乗の剰余に関する分散値が、冪乗余の分散値として計算される。上述の例では、ｓ＝ｘ＾（ａ１＋ａ２＋ａ３）  ｍｏｄ  ｐが「冪乗余の分散値」として計算される。
【００８１】
第ｉの算術演算部１５＿ｉは、主として乗算の秘密計算を行う。
【００８２】
図３は、第１の実施形態に係る冪剰余秘密計算システムの構成例を示すブロック図である。図３を参照すると、第１の実施形態による冪剰余秘密計算システムは、図２で参照される第ｉ（ｉ＝１、２、３）のサーバ装置からなる。第１の実施形態による冪剰余秘密計算システムにおいて、サーバ装置１０＿１、１０＿２、１０＿３は自身と異なるサーバ装置とネットワーク経由で通信可能な方法で接続されている。
【００８３】
このような構成の冪剰余秘密計算においては、ｘ（ｘ∈｛０、…、ｐ−１｝）及びａの（２、３）ＲＳＳによる分散値、法ｐに対して、その入力と計算過程からａ（指数）の値を知られることなく冪乗余（ｘ＾ａ  ｍｏｄ  ｐ）の（２、３）ＲＳＳによる分散値が計算される。当該計算された分散値は、第１〜第３のデータ記憶部１２＿１〜１２＿３に記憶される。入力ｘは、第１〜第３のサーバ装置１０＿１〜１０＿３のいずれかの装置又は外部から入力される。指数ａは、第１〜第３のデータ記憶部１２＿１〜１２＿３に記憶されている又は外部から入力される。法ｐは、データ記憶部１２に保管されている。上記計算結果のシェアは、第１〜第３のサーバ装置１０＿１〜１０＿３とシェアを送受信することで復元してもよい。あるいは、第１〜第３のサーバ装置１０＿１〜１０＿３ではない外部にシェアを送信することで、復元してもよい。
【００８４】
図４は、第１の実施形態の動作の一例を表すフローチャートである。図４を参照しつつ、第１の実施形態に係る冪乗余秘密計算システムの動作を説明する。
【００８５】
データ記憶部１２＿ｉには、値ｐ、ｑおよび底ｘ∈｛０、…、ｐ−１｝、および法ｑによって分散された指数ａの（２、３）ＲＳＳによる分散値が記憶されているものとする。また、ａの（２、３）ＲＳＳはａ＝ａ１＋ａ２＋ａ３  ｍｏｄ  ｑとなるａ１、ａ２、ａ３によって構成されているものとする。ただし、ｐ、ｑ、ｘは以下の（１）と（２）のいずれかの条件を満たすものとする。
（１）ｐ、ｑは素数であり、法ｑはｐ＞＝３ｑ＋１を満たす値とする。この場合、ｘは０以上ｐ−１以下のどのような値でもよい。
（２）ｐ＝２＾ｎとして、ｘは奇数とする。ｑはｐ以下の任意の値とする。
【００８６】
ステップＡ１において、第１〜第３の部分冪剰余計算部１３＿１〜１３＿３のそれぞれは、データ記憶部１２＿１〜１２＿３に記憶されたｘおよびａの分散値から、ｘ＾ａ１  ｍｏｄ  ｐ、ｘ＾ａ２  ｍｏｄ  ｐ、ｘ＾ａ３  ｍｏｄ  ｐの（２、３）ＲＳＳによる分散値を計算する（部分冪剰余が計算される）。
【００８７】
ステップＡ２において、第１〜第３の部分冪剰余合成部１４＿１〜１４＿３のそれぞれは、乗算の秘密計算によってステップＡ１の部分冪剰余からｓ＝ｘ＾ａ１＋ａ２＋ａ３  ｍｏｄ  ｐの分散値を計算する。ここで、乗算の秘密計算は算術演算部１５＿１〜１５＿３を用いて非特許文献３の方法などを用いて実行される。算術演算部１５＿１〜１５＿３は基本演算シード記憶部１１＿１〜１１＿３に記憶されているシードを用いて、互いに通信を行う。
【００８８】
ステップＡ２において得られたｓは、所望の冪剰余の分散値となる。なぜならば、ｐ＞＝３ｑ＋１の条件下ではａ１＋ａ２＋ａ３  ｍｏｄ  ｑ  ＝  ａ  （ｍｏｄ  ｐ）である。また、ｘが奇数でかつｐ＝２＾ｎの場合には、オイラーの定理よりｂ＾｛２＾ｎ｝  ＝  １  （ｍｏｄ  ２＾ｎ）が成立するため、ａ＝ａ１＋ａ２＋ａ３  ｍｏｄ  ２＾ｎ  および  ａ’＝ａ１＋ａ２＋ａ３とすると、ｓ＝ｘ＾（ａ’）  ｍｏｄ  ２＾ｎ  ＝  ｘ＾ａ・ｘ＾｛ｋ・２＾ｎ｝  ｍｏｄ  ２＾ｎ  ＝  ｘ＾ａ  ｍｏｄ  ２＾ｎとなる。
【００８９】
最後に、各サーバ装置１０＿ｉ（ｉ＝１、２、３）はステップＡ２で得られたｘ＾ａ  ｍｏｄ  ｐの分散値をデータ記憶部１２＿ｉに保管する。また、データ記憶部１２＿ｉに保管する代わりに、サーバ装置１０＿１、１０＿２、１０＿３とは異なる外部のサーバに送信して分散値が復元されてもよい。
【００９０】
以上のように、第１の実施形態では、部分冪乗余が計算され、当該部分冪乗余から冪乗余の分散値が計算される。当該計算は、各装置が持つａの分散値とｘから通信なしで実行できるので、（２、３）型ＲＳＳで分散された指数の値を明かすことなく、与えられた底と法に対する冪剰余の秘密計算が効率よく実行できる。
【００９１】
［第２の実施形態］
続いて、第２の実施形態について図面を参照して詳細に説明する。
【００９２】
図５〜図７を参照しつつ、第２の実施形態に係る冪剰余秘密計算システムについて説明する。
【００９３】
図５は、第２の実施形態に係るサーバ装置１０の内部構成（処理構成）の一例を示すブロック図である。図５に示す通り、第ｉのサーバ装置１０＿ｉは、第ｉの基本演算シード記憶部１１＿ｉと、第ｉのデータ記憶部１２＿ｉと、第ｉの部分冪剰余計算部１３＿ｉと、第ｉの部分冪剰余合成部１４＿ｉと、第ｉの仮冪剰余補正部２１＿ｉと、第ｉの算術演算部１５＿ｉと、第ｉの論理演算部１６＿ｉと、第ｉの部分シェア分散値計算部２２＿ｉを含む。なお、第ｉの基本演算シード記憶部１１＿ｉと、第ｉのデータ記憶部１２＿ｉと、第ｉの部分冪剰余計算部１３＿ｉと、第ｉの部分冪剰余合成部１４＿ｉと、第ｉの仮冪剰余補正部２１＿ｉと、第ｉの算術演算部１５＿ｉと、第ｉの論理演算部１６＿ｉと、第ｉの部分シェア分散値計算部２２＿ｉとはそれぞれ接続されている．
【００９４】
図２及び図５において同一の構成要素には同じ符号を付し、その説明を省略する。図２及び図５を比較すると、第ｉの論理演算部１６＿ｉ、第ｉの仮冪剰余補正部２１＿ｉ、第ｉの部分シェア分散値計算部２２＿ｉが追加されている。また、第ｉの部分冪剰余合成部１４＿ｉが計算する結果の取り扱いが第１及び第２の実施形態では異なる。
【００９５】
第２の実施形態では、第ｉの部分冪剰余合成部１４＿ｉは、部分冪乗余から平文の分散された指数の合計値の冪乗の剰余に関する分散値を「仮冪乗余の分散値」として計算する。
【００９６】
第ｉの論理演算部１６＿ｉは、少なくとも平文の分散された指数の最下位ビットの分散値を秘密計算によって計算する。第ｉの論理演算部１６＿ｉの具体的な処理については後述する。
【００９７】
第ｉの仮冪剰余補正部２１＿ｉは、仮冪剰余の分散値から冪乗余の分散値を計算する。具体的には、第ｉの仮冪剰余補正部２１＿ｉは仮冪乗余の分散値に対する補正により冪乗余の分散値を計算する。
【００９８】
第ｉの部分シェア分散値計算部２２＿ｉは、ａの分散値から、法ｐ上でのａ１の分散値、ａ２の分散値およびａ３の分散値を計算する。
【００９９】
図６は、第２の実施形態に係る冪剰余秘密計算システムの構成例を示すブロック図である。図６を参照すると、第２の実施形態による冪剰余秘密計算システムは、図５で参照される第ｉ（ｉ＝１、２、３）のサーバ装置からなる。第２の実施形態による冪剰余秘密計算システムにおいて、サーバ装置１０＿１、１０＿２、１０＿３は自身と異なるサーバ装置とネットワーク経由で通信可能な方法で接続されている．
【０１００】
このような構成の冪剰余秘密計算においては、ｘ（ｘ∈｛０、…、ｐ−１｝）及びａの（２、３）ＲＳＳによる分散値、法ｐに対して、その入力と計算過程からａ（指数）の値を知られることなく冪乗余（ｘ＾ａ  ｍｏｄ  ｐ）の（２、３）ＲＳＳによる分散値が計算される。当該計算された分散値は、第１〜第３のデータ記憶部１２＿１〜１２＿３に記憶される。入力ｘは、第１〜第３のサーバ装置１０＿１〜１０＿３のいずれかの装置又は外部から入力される。指数ａは、第１〜第３のデータ記憶部１２＿１〜１２＿３に記憶されている又は外部から入力される。法ｐは、データ記憶部１２に保管されている。上記計算結果のシェアは、第１〜第３のサーバ装置１０＿１〜１０＿３とシェアを送受信することで復元してもよい。あるいは、第１〜第３のサーバ装置１０＿１〜１０＿３ではない外部にシェアを送信することで、復元してもよい。
【０１０１】
図７は、第２の実施形態の動作の一例を表すフローチャートである。図７を参照しつつ、第２の実施形態に係る冪乗余秘密計算システムの動作を説明する。
【０１０２】
データ記憶部１２＿ｉには、値ｐ、ｑおよび底ｘ∈｛０、…、ｐ−１｝、および法ｑによって分散された指数ａの（２、３）ＲＳＳによる分散値が記憶されているものとする。また、ａの（２、３）ＲＳＳはａ＝ａ１＋ａ２＋ａ３  ｍｏｄ  ｑとなるａ１、ａ２、ａ３によって構成されているものとする。ただし、ｐおよびｑは素数であり、（１’）  ３ｑ＋１  ＞  ｐ  ＞＝２ｑ＋１あるいは（２’）  ２ｑ＋１  ＞  ｐのいずれかの条件を満たしているものとする。
【０１０３】
ステップＢ１において、第１〜第３の部分冪剰余計算部１３＿１〜１３＿３はそれぞれ、データ記憶部１２＿１〜１２＿３に記憶されたｘおよびａの分散値からｘ＾ａ１  ｍｏｄ  ｐ、ｘ＾ａ２  ｍｏｄ  ｐ、ｘ＾ａ３  ｍｏｄ  ｐの（２、３）ＲＳＳによる分散値を計算する。
【０１０４】
ステップＢ２において、第１〜第３の部分冪剰余合成部１４＿１〜１４＿３は、乗算の秘密計算によってステップＢ１の部分冪剰余からｓ’＝ｘ＾ａ１＋ａ２＋ａ３  ｍｏｄ  ｐの分散値を計算する。ここで、乗算の秘密計算は算術演算部１５＿１〜１５＿３により非特許文献３の方法などを用いて実行される。算術演算部１５＿１〜１５＿３は基本演算シード記憶部１１＿１〜１１＿３に記憶されているシードを用いて、互いに通信を行う。
【０１０５】
ステップＢ２によって得られたｓ’を仮冪剰余とする。
【０１０６】
ステップＢ３において、第１〜第３の部分シェア分散値計算部２２＿１〜２２＿３はそれぞれ、データ記憶部１２＿１〜１２＿３に記憶されたａの分散値から、法ｐ上でのａ１の分散値、ａ２の分散値およびａ３の分散値を計算する。また、算術演算部１５を用いて、ａ１＋ａ２およびａ１＋ａ２＋ａ３の分散値が計算される。これらの処理は，各サーバ装置１０＿１〜１０＿３で通信を伴うことなく実行可能である。
【０１０７】
ステップＢ４において、第１〜第３の論理演算部１６＿１〜１６＿３は、ａ１、ａ２、ａ３、（ａ１＋ａ２）、（ａ１＋ａ２＋ａ３）の最下位ビットの分散値を秘密計算によって計算する。なお、それぞれの最下位ビットをＬＳＢ（ａ１）、ＬＳＢ（ａ２）、ＬＳＢ（ａ３）、ＬＳＢ（ａ１＋ａ２  ｍｏｄ  ｐ）、ＬＳＢ（ａ１＋ａ２＋ａ３  ｍｏｄ  ｐ）と表記することにする。この処理は、非特許文献２に記載のビット分解の秘密計算などによって実行可能である。
【０１０８】
ステップＢ５において、第１〜第３の論理演算部１６＿１〜１６＿３は、ステップＢ４で得られたＬＳＢ（ａ１）、ＬＳＢ（ａ２）、ＬＳＢ（ａ３）、ＬＳＢ（ａ１＋ａ２  ｍｏｄ  ｐ）、ＬＳＢ（ａ１＋ａ２＋ａ３  ｍｏｄ  ｐ）の分散値から論理式（ａ１＋ａ２）  ＞  ｐ  および  （ａ１＋ａ２＋ａ３）  ＞  ｐの真理値の分散値を秘密計算によって計算する。ただし、各論理式は条件が真のときに「１」であり、偽のときに「０」であるものとする。
【０１０９】
ｐが奇数であり、ａ１＋ａ２  ＞  ｐのときａ１＋ａ２とａ１＋ａ２  ｍｏｄ  ｐの偶奇が反転することに着目すると、この処理は（ａ１＋ａ２＞ｐ）＝ＬＳＢ（ａ１）＋ＬＳＢ（ａ２）＋ＬＳＢ（ａ１＋ａ２）  ｍｏｄ  ２であり、論理演算における加算の秘密計算によって通信を伴うことなく実行可能である。同様に、（ａ１＋ａ２＋ａ３＞ｐ）＝ＬＳＢ（ａ１＋ａ２）＋ＬＳＢ（ａ３）＋ＬＳＢ（ａ１＋ａ２＋ａ３）  ｍｏｄ  ２で計算可能である。なお、ｐおよびｑが前記の条件（１’）  ３ｑ＋１  ＞  ｐ  ＞＝２ｑ＋１を満たしている場合には、ａ１＋ａ２はｐより小さいため、（ａ１＋ａ２  ＞  ｐ）の計算を省略することができる（必ずａ１＋ａ２＞ｐ＝０となる）。
【０１１０】
ステップＢ６において、第１〜第３の仮剰余補正計算部２１＿１〜２１＿３は、ステップＢ２で求めた仮冪剰余の分散値ｓ’と、ステップＢ５で計算した（ａ１＋ａ２＞ｐ）および（ａ１＋ａ２＋ａ３＞ｐ）の分散値から、所望の冪剰余ｓ  ＝  ｘ＾ａ  ｍｏｄ  ｐの分散値を計算する。
【０１１１】
上記計算は、例えば以下の手順によって計算できる。
【０１１２】
（Ｂ６−１）  ｓ’・（ａ１＋ａ２＞ｐ）・ｂ＾｛−１｝  ＋  ｓ’・（１-（ａ１＋ａ２＞ｐ））の秘密計算を算術演算部１５＿１〜１５＿３により計算する。この計算によって得られた分散値をｔの分散値とする。
【０１１３】
（Ｂ６−２）  ｔ・（ａ１＋ａ２＋ａ３  ＞  ｐ）＋ｔ・（１-（ａ１＋ａ２＋ａ３＞ｐ））の秘密計算を算術演算部１５＿１〜１５＿３により実行する。当該ステップ（Ｂ６−２）で得られた分散値が、所望の冪剰余ｘ＾ａ  ｍｏｄ  ｐの分散値となる。
【０１１４】
以上のように、第２の実施形態では、仮冪乗余の分散値を（ａ１＋ａ２＞ｐ）や（ａ１＋ａ２＋ａ３＞ｐ）といった分散値を用いて修正（補正）することで冪乗余の分散値が計算される。その結果、第１の実施形態と同様に、（２、３）型ＲＳＳで分散された指数の値を明かすことなく、与えられた底と法に対する冪剰余の秘密計算が効率よく実行できる。
【０１１５】
［ハードウェア構成］
次に、第１、第２の実施形態に係るサーバ装置１０のハードウェア構成を説明する。図８は、サーバ装置１０のハードウェア構成の一例を示すブロック図である。
【０１１６】
サーバ装置１０は、情報処理装置（コンピュータ）により構成可能であり、図８に例示する構成を備える。例えば、サーバ装置１０は、内部バスにより相互に接続される、ＣＰＵ（Central Processing Unit）３１、メモリ３２、入出力インターフェイス３３及び通信手段であるＮＩＣ（Network Interface Card）３４等を備える。
【０１１７】
但し、図８に示す構成は、サーバ装置１０のハードウェア構成を限定する趣旨ではない。サーバ装置１０は、図示しないハードウェアを含んでもよいし、必要に応じて入出力インターフェイス３３を備えていなくともよい。また、サーバ装置１０に含まれるＣＰＵ等の数も図８の例示に限定する趣旨ではなく、例えば、複数のＣＰＵがサーバ装置１０に含まれていてもよい。
【０１１８】
メモリ３２は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、補助記憶装置（ハードディスク等）である。
【０１１９】
入出力インターフェイス３３は、図示しない表示装置や入力装置のインターフェイスとなる手段である。表示装置は、例えば、液晶ディスプレイ等である。入力装置は、例えば、キーボードやマウス等のユーザ操作を受け付ける装置である。
【０１２０】
サーバ装置１０の機能は、上述の各種処理モジュールにより実現される。当該処理モジュールは、例えば、メモリ３２に格納されたプログラムをＣＰＵ３１が実行することで実現される。また、そのプログラムは、ネットワークを介してダウンロードするか、あるいは、プログラムを記憶した記憶媒体を用いて、更新することができる。さらに、上記処理モジュールは、半導体チップにより実現されてもよい。即ち、上記処理モジュールが行う機能を何らかのハードウェア、及び／又は、ソフトウェアで実行する手段があればよい。
【０１２１】
上記の説明により、本発明の産業上の利用可能性は明らかであるが、秘密鍵を保護したままデジタル署名を計算することが可能になり、ブロックチェーン等の分散ノード上での秘密鍵保護などに好適に適用可能である。冪剰余は暗号系の処理で多用される関数であり、秘密計算で冪剰余を実行できると、分散システムにおいて暗号系処理を効率的に実現するできるためである。
【０１２２】
なお、引用した上記の非特許文献の各開示は、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択（部分的削除を含む）が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１２３】
１０＿ｉ、１０＿１〜１０＿３、１０  サーバ装置
１１＿ｉ、１１＿１〜１１＿３  基本演算シード記憶部
１２＿ｉ、１２＿１〜１２＿３  データ記憶部
１３＿ｉ、１３＿１〜１３＿３、１０１  部分冪剰余計算部
１４＿ｉ、１４＿１〜１４＿３、１０２  部分冪剰余合成部
１５＿ｉ、１５＿１〜１５＿３  算術演算部
１６＿ｉ、１６＿１〜１６＿３  論理演算部
２１＿ｉ、２１＿１〜２１＿３  仮冪剰余補正部
２２＿ｉ、２２＿１〜２２＿３  部分シェア分散値計算部
３１  ＣＰＵ（Central Processing Unit）
３２  メモリ
３３  入出力インターフェイス
３４  ＮＩＣ（Network Interface Card）
１００  情報処理装置
【図１】
2020152831.tif 000003
【図２】
2020152831.tif 000004
【図３】
2020152831.tif 000005
【図４】
2020152831.tif 000006
【図５】
2020152831.tif 000007
【図６】
2020152831.tif 000008
【図７】
2020152831.tif 000009
【図８】
2020152831.tif 000010
【手続補正書】
【提出日】令和3年7月20日(2021.7.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
平文の底と平文の法と分散された指数とから、前記底を前記分散された指数で冪乗したものの剰余の分散値の組を部分冪剰余として計算する、部分冪剰余計算部と、
前記部分冪剰余から前記底を前記分散された指数の合計値で冪乗したものの剰余の分散値を冪剰余の分散値として計算する、部分冪剰余合成部と、
を備える、情報処理装置。
【請求項２】
乗算の秘密計算を行う算術演算部をさらに備え、
前記部分冪剰余合成部は、前記算術演算部を用いて前記冪剰余の分散値を計算する、請求項１に記載の情報処理装置。
【請求項３】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部をさらに備える、請求項１又は２に記載の情報処理装置。
【請求項４】
平文とシェアを格納する、データ記憶部をさらに備える、請求項１乃至３のいずれか一項に記載の情報処理装置。
【請求項５】
前記部分冪剰余合成部は、前記部分冪剰余から前記底を前記分散された指数の合計値で冪乗したものの剰余の分散値を仮冪剰余の分散値として計算し、
前記仮冪剰余の分散値から前記冪剰余の分散値を計算する、仮冪剰余補正部をさらに備える、請求項１乃至４のいずれか一項に記載の情報処理装置。
【請求項６】
前記分散された指数の最下位ビットの分散値を秘密計算によって計算する、論理演算部をさらに備える、請求項１乃至５のいずれか一項に記載の情報処理装置。
【請求項７】
前記冪剰余の分散値は、（２、３）閾値のアクセス構造を有する複製型秘密分散を用いた秘密計算により計算される、請求項１乃至６のいずれか一項に記載の情報処理装置。
【請求項８】
平文の底と平文の法と分散された指数とから、前記底を前記分散された指数で冪乗したものの剰余の分散値の組を部分冪剰余として計算するステップと、
前記部分冪剰余から前記底を前記分散された指数の合計値で冪乗したものの剰余の分散値を冪剰余の分散値として計算するステップと、
を含む、秘密計算方法。
【請求項９】
平文の底と平文の法と分散された指数とから、前記底を前記分散された指数で冪乗したものの剰余の分散値の組を部分冪剰余として計算する処理と、
前記部分冪剰余から前記底を前記分散された指数の合計値の冪乗したものの剰余の分散値を冪剰余の分散値として計算する処理と、
をコンピュータに実行させるプログラム。
【国際調査報告】
2020152831.tif 000011
2020152831.tif 000012
2020152831.tif 000013
2020152831.tif 000014