(57)【要約】  ２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣにて効率の良い型変換処理を実行する情報処理装置を提供する。情報処理装置は、基本演算シード記憶部と、再分散値計算部と、シェア構成部と、を備える。基本演算シード記憶部は、シェアについての演算を行う際の乱数を生成するためのシードを格納する。再分散値計算部は、シードを用いて乱数を生成し、生成された乱数によりシェアの再分散値を計算すると共に、生成された乱数に関するデータを他の装置に送信する。シェア構成部は、他の装置から受信した生成された乱数に関するデータ及びシェアの再分散値を用いて型変換用のシェアを構成する。
2020165931.tif 000002
【特許請求の範囲】
【請求項１】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部と、
前記シードを用いて乱数を生成し、前記生成された乱数によりシェアの再分散値を計算すると共に、前記生成された乱数に関するデータを他の装置に送信する、再分散値計算部と、
他の装置から受信した前記生成された乱数に関するデータ及び前記シェアの再分散値を用いて型変換用のシェアを構成する、シェア構成部と、
を備える、情報処理装置。
【請求項２】
前記生成された乱数に関するデータを用いて不正行為者の有無を検知する、不正検知部をさらに備える、請求項１に記載の情報処理装置。
【請求項３】
前記型変換されたシェアについての論理演算を行う論理演算部をさらに備え、
前記論理演算部は、他の装置と互いに通信を行い前記型変換されたシェアの加算処理を実行し、
前記不正検知部は、前記型変換されたシェアの加算処理のために送受信されたデータを用いて不正行為者の有無を検知する、請求項２に記載の情報処理装置。
【請求項４】
前記論理演算部は、他の装置と互いに通信を行い前記型変換されたシェアのキャリー計算処理を実行し、
前記不正検知部は、前記型変換されたシェアのキャリー計算処理のために送受信されたデータを用いて不正行為者の有無を検知する、請求項３に記載の情報処理装置。
【請求項５】
前記キャリー計算処理は、第１要素及び前記第１要素に続く第２要素に分離可能であり、
前記論理演算部は、
前記第１要素を他の装置と非通信により計算すると共に、前記シェアの再分散値の計算に必要な通信と前記第２要素のキャリー計算処理に必要な通信を並列に行う、請求項４に記載の情報処理装置。
【請求項６】
シェアをマスクするためのマスク値を計算すると共に、前記計算されたマスク値によりマスクされたシェアを他の装置に送信する、マスク値計算部をさらに備え、
前記シェア構成部は、前記送信されたマスク値を用いて前記型変換用のシェアを構成する、請求項１乃至５のいずれか一項に記載の情報処理装置。
【請求項７】
前記再分散値計算部は、値ｘの再分散値を計算する際、値ｘをｘ１、ｘ２、ｘ３の排他的論理和とする場合に前記ｘ１乃至ｘ３のうち２つの値を等しくするように乱数を生成する、請求項１乃至６のいずれか一項に記載の情報処理装置。
【請求項８】
前記再分散値計算部は、値ｘ’の再分散値を計算する際、値ｘ’をｘ１’、ｘ２’、ｘ３’の排他的論理和とする場合、ｘ１’を乱数ｒに等しく、ｘ２’をゼロ、ｘ３’を乱数ｒと値ｘの排他的論理和とする、請求項７に記載の情報処理装置。
【請求項９】
シードを用いて乱数を生成するステップと、
前記生成された乱数によりシェアの再分散値を計算すると共に、前記生成された乱数に関するデータを他の装置に送信するステップと、
他の装置から受信した前記生成された乱数に関するデータ及び前記シェアの再分散値を用いて型変換用のシェアを構成するステップと、
を含む秘密計算方法。
【請求項１０】
シードを用いて乱数を生成する処理と、
前記生成された乱数によりシェアの再分散値を計算すると共に、前記生成された乱数に関するデータを他の装置に送信する処理と、
他の装置から受信した前記生成された乱数に関するデータ及び前記シェアの再分散値を用いて型変換用のシェアを構成する処理と、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、秘密計算方法及びプログラムに関する。特に、不正検知可能な４者秘密計算におけるシェアの型変換に関する情報処理装置、秘密計算方法及びプログラムに関する。
【背景技術】
【０００２】
近年、秘密計算に関する研究開発が盛んに行われている。秘密計算では、入力データを秘匿したまま所定の処理を実行し、結果を得ることができる。【０００３】
秘密計算プロトコルは大きく２つの種類に大別される。第１の方式は、特定の計算に限って実行可能な秘密計算プロトコルである。第２の方式は、任意の計算が実行可能な秘密計算プロトコルである。また、第２の方式には種々の方式が存在し、方式間で通信量（データ量）や通信ラウンド数をはじめとした様々なコストにおけるトレードオフが成立する。たとえば、通信量が少ない代わりに通信回数が多い方式や通信量は多いが通信回数が少ない方式が存在する。【０００４】
代表的な秘密計算プロトコルとして、マルチパーティ計算（ＭＰＣ；Multi Party Computation）が挙げられる。ＭＰＣとは、各参加者の入力を秘匿しながら、複数の参加者間で任意の関数を計算できる秘密計算プロトコルである。ＭＰＣにも、いくつかの方式があるが、近年注目を集める方式は、秘密分散ベースのＭＰＣである。秘密分散ベースのＭＰＣでは、入力を各参加者に分散する。ここで、分散データのことをシェアと呼称する。各参加者は各自のシェアを用いて、参加者間で協調しながら、目的の関数を計算する。このとき、計算過程の値に関してもシェアの形式を保っているために、元々の入力や計算過程の値が明らかになることはない。最終的な計算結果のシェアだけが復元され、安全に任意の関数が計算できる。以降、ｎ≧２のときの 
2020165931.tif 000003
の値のシェアを
2020165931.tif 000004
、ｎ＝１
のときの
2020165931.tif 000005
の値のシェアを
2020165931.tif 000006
として表記する。【０００５】
ここで、ＭＰＣが達成する安全性は、大きく２つある。１つは秘匿性（Secrecy）である。もう１つは正当性（Correctness）である。秘匿性は、ＭＰＣを実行するにあたり、想定する攻撃者が存在したとしても、参加者に対し、入力に関する情報が漏れないことを保証する安全性となる。正当性は、秘密計算プロトコルを実行するにあたり、想定する攻撃者が存在したとしても、実行結果が正しいことを保証する安全性となる。【０００６】
ここで、上記の「想定する攻撃者」には、いくつかの指標がある。代表的な指標として、１つ目は攻撃者の振舞いが挙げられる。２つ目は参加者における攻撃者の割合である。【０００７】
攻撃者の振舞いに着目した場合、代表的な攻撃者の種類として、セミオネスト攻撃者（Semi-honest Adversary）とマリシャス攻撃者（Malicious Adversary）が挙げられる。セミオネスト攻撃者は、プロトコルに従いつつも、可能な範囲で得られる情報を増やそうと試みる攻撃者である。マリシャス攻撃者は、プロトコルから逸脱した振舞いを取ることで、自身が得られる情報を増やそうと試みる攻撃者である。ここで、プロトコルから逸脱する振舞いとは、たとえば、本来送信すべきデータに対し、ビット反転を行うことによって、送信データを改ざんすることが挙げられる。【０００８】
参加者における攻撃者の割合に着目した場合、大きく２つの種類が挙げられる。１つは、過半数が不正者（Dishonest majority）の場合である。もう１つは、過半数が正直者（Honest majority）の場合である。ここで、全参加者数をｎとし、攻撃者の数をｔとする。過半数が不正者の場合とは、つまり、ｔ＜ｎが成り立つ場合を意味する。過半数が正直者の場合とは、つまり、ｔ＜ｎ／２が成り立つ場合を意味する。過半数が正直者である場合としてｔ＜ｎ／３が成り立つ場合も含まれるが、本書では特に断りが無い限り、ｔ＜ｎ／２が成り立つ場合を過半数が正直者である場合とする。【０００９】
近年、注目を集めるＭＰＣとして３者間ＭＰＣが挙げられる。非特許文献１は、過半数が正直者で、かつ、攻撃者がセミオネスト攻撃者である場合の３者間ＭＰＣを開示する。非特許文献１に開示されたＭＰＣは、
2020165931.tif 000007
上での算術演算を実現する。非特許文献１に開示せれたＭＰＣは、
2020165931.tif 000008
上での乗算１回あたり、３ｎビットの通信コストを要する。つまり、参加者あたりｎビットの通信コストで乗算を実現できる。【００１０】
非特許文献２は、過半数が正直者で、かつ、攻撃者がマリシャス攻撃者である場合の３者間ＭＰＣを開示する。これは、非特許文献１の方式をベースとした方式である。非特許文献２に開示されたＭＰＣは、非特許文献１に開示されたＭＰＣとは異なり、マリシャス攻撃者の存在を許容する。非特許文献２に開示されたＭＰＣではマリシャス攻撃者による不正を、確率的に検知することが可能となる。検知確率を上げるほど、つまり、不正が成功する確率を下げようとするほど、通信コストが増加することとなる。たとえば、不正が成功する確率を２-４０とした場合、非特許文献２では、
2020165931.tif 000009
上での乗算１回あたり、２１ｎビットの通信コストを要する。つまり、参加者あたり７ｎビットの通信コストで不正検知機能付きの乗算を実現できる。【００１１】
非特許文献３では、非特許文献１におけるシェアの型変換の方法が提案されている。シェアの型変換とは、たとえば、
2020165931.tif 000010
から
2020165931.tif 000011
のシェア列を得ることが挙げられる。この型変換をビット分解と呼称する。また、異なる型変換の例として、
2020165931.tif 000012
から、
2020165931.tif 000013
を得ることが挙げられる。この型変換を環合成と呼称する。【００１２】
非特許文献３には、たとえば、ビット分解に６ｎ−６ビットの通信コストを要することが開示されている。このような処理は、算術回路や論理回路が混在した混合回路に対し、効率よくＭＰＣを実行したい場合に重要な処理となる。たとえば、非特許文献２の方式を用いて非特許文献３で提案されたビット分解を実行した場合、マリシャス攻撃者の存在を許容できるが、通信コストは４２ｎ―４２ビットとなる。【００１３】
多くの場合、ＭＰＣにおいて参加者が少なく、過半数が正直者の場合の方が、通信コストは低くなる。このため、前述のような３者間ＭＰＣが計算効率の良い方式であると考えられてきた。しかし、想定する攻撃者がマリシャス攻撃者の場合、計算効率は４者間ＭＰＣの方が良い場合がある。【００１４】
たとえば、非特許文献４は、ｔ＜ｎ／３、つまりｔ＝１で、かつ、攻撃者がマリシャス攻撃者である場合の４者間ＭＰＣを開示する。非特許文献４に開示されたＭＰＣは、
2020165931.tif 000014
上での乗算１回あたり、６ｎビットの通信コストを要する。つまり、参加者あたり１．５ｎビットの通信コストで乗算を実現できる。しかし、非特許文献４では方式固有の型変換が提案されていない。このため、たとえば、非特許文献５に開示されたようなビット分解を用いる必要がある。【００１５】
非特許文献５で提案された方式は、環上でビット分解を行う方式のため、
2020165931.tif 000015
から
2020165931.tif 000016
のシェア列を計算するものとなる。このため、非特許文献５によるビット分解の結果を
2020165931.tif 000017
上での計算に用いることはできず、混合回路を計算する際には効率が悪い。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】T. Araki et al.、"High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority."、2016、In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS '16). ACM, New York, NY, USA, 805-817.
【非特許文献２】T. Araki et al.、"Optimized Honest-Majority MPC for Malicious Adversaries − Breaking the 1 Billion-Gate Per Second Barrier"、2017、IEEE Symposium on Security and Privacy (SP), San Jose, California, USA, 2017, pp. 843-862.
【非特許文献３】T. Araki et al.、"Generalizing the SPDZ Compiler For Other Protocols."、2018、In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS '18). ACM, New York, NY, USA, 880-895.
【非特許文献４】S. Dov Gordon et al.、"Secure Computation with Low Communication from Cross-checking."、Cryptology ePrint Archive, Report 2018/216, 2018, https://eprint.iacr.org/2018/216.
【非特許文献５】I. Damgard et al.、"Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation"、In Theory of Cryptography Conference (pp. 285-304). Springer, Berlin, Heidelberg, 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
なお、上記先行技術文献の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者らによってなされたものである。【００１８】
ＭＰＣを行うにあたり、可能な限り通信コストが軽減された方式が望まれる。通信コストには通信量と通信ラウンド回数とがあるが、単位時間あたりの処理件数の効率を重視する場合、特に通信量が重要となる。【００１９】
たとえば、ｔ＜ｎ／３、つまりｔ＝１で、かつ、攻撃者がマリシャス攻撃者である場合での４者間ＭＰＣであれば、
2020165931.tif 000018
上での乗算１回あたり、５ｎビットの通信コストで実現できる。つまり、参加者あたり１．２５ｎビットの通信コストで乗算を実現できる。これは２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた方法である。【００２０】
各参加者をＰ_ｉ（ｉ＝１、…、４）としたとき、
2020165931.tif 000019
のシェアを
2020165931.tif 000020
として、
2020165931.tif 000021
をＰ_ｉのシェアとする。また、
2020165931.tif 000022
のシェアを
2020165931.tif 000023
として、
2020165931.tif 000024
をＰ_ｉのシェアとする。このとき、
2020165931.tif 000025
に対して、
2020165931.tif 000026
とすると、
2020165931.tif 000027
とする。また、
2020165931.tif 000028
に対して、
2020165931.tif 000029
とすると、
2020165931.tif 000030
とする。【００２１】
なお、
2020165931.tif 000031
とし、疑似ランダム関数
2020165931.tif 000032
とする。また、
2020165931.tif 000033
を文字列連結演算子とする。ここで、Ｐ_１は
2020165931.tif 000034
を、Ｐ_２は
2020165931.tif 000035
を、Ｐ_３は
2020165931.tif 000036
を、Ｐ_４は
2020165931.tif 000037
を、それぞれ有する。【００２２】
なお、
2020165931.tif 000038
に関して、参加者の内、ある一人の参加者は
2020165931.tif 000039
の出力を計算できず、他の三人の参加者は
2020165931.tif 000040
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000041
の扱いは特に制限されない。本書での
2020165931.tif 000042
はあくまでも一例である。【００２３】
ここで、
2020165931.tif 000043
を
2020165931.tif 000044
上のシェアに関する加法演算子、減法演算子、乗法演算子とする。なお、これらの演算子は
2020165931.tif 000045
上の要素に対する二項演算子としての加法演算子、減法演算子、乗法演算子としても以降用いることに注意されたい。
2020165931.tif 000046
上のシェアに関する加法演算子、乗法演算子について、
2020165931.tif 000047
としたとき、以下の４つの式が成り立つ。
2020165931.tif 000048
2020165931.tif 000049
2020165931.tif 000050
2020165931.tif 000051
【００２４】
また、
2020165931.tif 000052
を
2020165931.tif 000053
上のシェアに関する排他的論理和、論理積とする。なお、これらの演算子は
2020165931.tif 000054
上の要素に対する二項演算子としての排他的論理和、論理積としても以降用いることに注意されたい。
2020165931.tif 000055
上のシェアに関する排他的論理和、論理積について、
2020165931.tif 000056
としたとき、以下の４つの式が成り立つ。
2020165931.tif 000057
2020165931.tif 000058
2020165931.tif 000059
2020165931.tif 000060
【００２５】
たとえば、前述の２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣでは、
2020165931.tif 000061
2020165931.tif 000062
2020165931.tif 000063
2020165931.tif 000064
2020165931.tif 000065
となり
2020165931.tif 000066
から
2020165931.tif 000067
が計算できる。また、
2020165931.tif 000068
としたとき、
2020165931.tif 000069
に関しても、以下の手順で
2020165931.tif 000070
を用いて計算できる。【００２６】
１．各参加者（Ｐ_１〜Ｐ_３）のそれぞれは以下の計算を行う。【００２７】
Ｐ_１：
2020165931.tif 000071
2020165931.tif 000072
2020165931.tif 000073
2020165931.tif 000074
【００２８】
Ｐ_２：
2020165931.tif 000075
2020165931.tif 000076
2020165931.tif 000077
2020165931.tif 000078
【００２９】
Ｐ_３：
2020165931.tif 000079
2020165931.tif 000080
2020165931.tif 000081
2020165931.tif 000082
【００３０】
２．上記計算が終了すると、各参加者は以下の通信を行う。【００３１】
・Ｐ_１は
2020165931.tif 000083
をＰ_３に送信する。
・Ｐ_２は
2020165931.tif 000084
をＰ_１に送信する。
・Ｐ_３は
2020165931.tif 000085
をＰ_２に送信する。
・Ｐ_１は
2020165931.tif 000086
をＰ_４に送信する。
・Ｐ_２は
2020165931.tif 000087
をＰ_４に送信する。【００３２】
３．各参加者は、上記通信により得た情報を用いて以下の計算により
2020165931.tif 000088
を得る。【００３３】
2020165931.tif 000089
2020165931.tif 000090
2020165931.tif 000091
2020165931.tif 000092
【００３４】
なお、Ｐ_４のシェアは以下のようにして、計算する。【００３５】
Ｐ_４：
2020165931.tif 000093
2020165931.tif 000094
【００３６】
シェアと定数倍算、および定数加算については当業者にとって自明なので説明を割愛する。また、
2020165931.tif 000095
上のシェアに関する演算についても、
2020165931.tif 000096
上のシェアに関する演算と同様に実行できるので説明を割愛する。このとき、参加者中にマリシャス攻撃者が１人存在したとしても、各自のシェアと異なる参加者から受信した値を用いて、値の改ざんがなかったか検証できる。改ざんがあった場合は、プロトコルを中断する。【００３７】
しかし、上記２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた方法を用いた４者間ＭＰＣでは、型変換処理を行うことが難しい。シェアの形式が異なるため、非特許文献３に開示された方法を直接用いることができないためである。また、非特許文献５に開示されたようなgeneralな型変換方式は位数のビット長が２以上の環上で行われ、混合回路中の論理回路部分の計算効率が悪い。よって、混合回路の計算を不正検知可能なＭＰＣで効率よく行いたい場合、非特許文献４に開示された４者間ＭＰＣもしくは上記２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣで実行可能な、効率の良い型変換処理が求められる。【００３８】
本発明は、２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣにて効率の良い型変換処理を実行することに寄与する、情報処理装置、秘密計算方法及びプログラムを提供することを主たる目的とする。
【課題を解決するための手段】
【００３９】
本発明乃至開示の第１の視点によれば、シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部と、前記シードを用いて乱数を生成し、前記生成された乱数によりシェアの再分散値を計算すると共に、前記生成された乱数に関するデータを他の装置に送信する、再分散値計算部と、他の装置から受信した前記生成された乱数に関するデータ及び前記シェアの再分散値を用いて型変換用のシェアを構成する、シェア構成部と、を備える、情報処理装置が提供される。【００４０】
本発明乃至開示の第２の視点によれば、シードを用いて乱数を生成するステップと、前記生成された乱数によりシェアの再分散値を計算すると共に、前記生成された乱数に関するデータを他の装置に送信するステップと、他の装置から受信した前記生成された乱数に関するデータ及び前記シェアの再分散値を用いて型変換用のシェアを構成するステップと、を含む秘密計算方法が提供される。【００４１】
本発明乃至開示の第３の視点によれば、シードを用いて乱数を生成する処理と、前記生成された乱数によりシェアの再分散値を計算すると共に、前記生成された乱数に関するデータを他の装置に送信する処理と、他の装置から受信した前記生成された乱数に関するデータ及び前記シェアの再分散値を用いて型変換用のシェアを構成する処理と、をコンピュータに実行させるプログラムが提供される。
なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。記憶媒体は、半導体メモリ、ハードディスク、磁気記録媒体、光記録媒体等の非トランジェント（non-transient）なものとすることができる。本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００４２】
本発明乃至開示の各視点によれば、２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣにて混合回路を計算する際、論理回路の計算部分も含め効率よく計算可能な型変換を実行することに寄与する情報処理装置、秘密計算方法及びプログラムが提供される。
【図面の簡単な説明】
【００４３】
【図１】一実施形態の概要を説明するための図である。
【図２】第１の実施形態における型変換システムの機能構成例を示すブロック図である。
【図３】第１の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図４】第１の実施形態におけるビット分解についての型変換システムの動作例を示すフローチャートである。
【図５】第１の実施形態における環合成についての型変換システムの動作例を示すフローチャートである。
【図６】第２の実施形態における型変換システムの機能構成例を示すブロック図である。
【図７】第２の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図８】第２の実施形態における環合成についての型変換システムの動作例を示すフローチャートである。
【図９】第３の実施形態における型変換システムの機能構成例を示すブロック図である。
【図１０】第３の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図１１】第３の実施形態におけるビット分解についての型変換システムの動作例を示すフローチャートである。
【図１２】第３の実施形態における環合成についての型変換システムの動作例を示すフローチャートである。
【図１３】第４の実施形態における型変換システムの機能構成例を示すブロック図である。
【図１４】第４の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図１５】第４の実施形態における環合成についての型変換システムの動作例を示すフローチャートである。
【図１６】第５の実施形態における型変換システムの機能構成例を示すブロック図である。
【図１７】第５の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図１８】第５の実施形態におけるビット分解についての型変換システムの動作例を示すフローチャートである。
【図１９】第６の実施形態における型変換システムの機能構成例を示すブロック図である。
【図２０】第６の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図２１】第６の実施形態におけるビット分解についての型変換システムの動作例を示すフローチャートである。
【図２２】第７の実施形態における型変換システムの機能構成例を示すブロック図である。
【図２３】第７の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図２４】第７の実施形態におけるビット分解についての型変換システムの動作例を示すフローチャートである。
【図２５】秘密計算サーバ装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００４４】
初めに、一実施形態の概要について説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、この概要の記載はなんらの限定を意図するものではない。また、各図におけるブロック間の接続線は、双方向及び単方向の双方を含む。一方向矢印については、主たる信号（データ）の流れを模式的に示すものであり、双方向性を排除するものではない。さらに、本願開示に示す回路図、ブロック図、内部構成図、接続図などにおいて、明示は省略するが、入力ポート及び出力ポートが各接続線の入力端及び出力端のそれぞれに存在する。入出力インターフェイスも同様である。
【００４５】
一実施形態に係る情報処理装置１０は、基本演算シード記憶部１１と、再分散値計算部１２と、シェア構成部１３と、を備える（図１参照）。基本演算シード記憶部１１は、シェアについての演算を行う際の乱数を生成するためのシードを格納する。再分散値計算部１２は、シードを用いて乱数を生成し、生成された乱数によりシェアの再分散値を計算すると共に、生成された乱数に関するデータを他の装置に送信する。シェア構成部１３は、他の装置から受信した生成された乱数に関するデータ及びシェアの再分散値を用いて型変換用のシェアを構成する。
【００４６】
ここで、４者ＭＰＣにおいてもビット分解や環合成は効率よく秘密計算を実行するためには有益な型変換であるが、各装置が保有するシェアの形式が不統一であるとビット分解等の恩恵が得られない。そこで、上記情報処理装置１０は、各装置が保有するシェアの形式を統一しビット分解等の型変換が容易となるようにシェアを再構成する。
【００４７】
以下に具体的な実施の形態について、図面を参照してさらに詳しく説明する。なお、各実施形態において同一構成要素には同一の符号を付し、その説明を省略する。
【００４８】
［第１の実施形態］
第１の実施形態について、図面を用いてより詳細に説明する。
【００４９】
図２〜図５を参照して、第１の実施形態に係る型変換処理システムについて説明する。
【００５０】
図２は、第１の実施形態による型変換処理システムの機能構成例を示すブロック図である。図２を参照すると、第１の実施形態による型変換処理システムは、後述する図３で参照される第ｉ（ｉ＝１、２、３、４）の秘密計算サーバ装置（以下、単にサーバ装置と表記する）から成る。第１の実施形態による型変換処理システムにおいて、サーバ装置１００_１、１００_２、１００_３、１００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。
【００５１】
図３は、第ｉのサーバ装置１００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。図３に示すように、第ｉのサーバ装置１００_ｉは、第ｉの再分散値計算部１０２_ｉと、第ｉのシェア構成部１０３_ｉと、第ｉの不正検知部１０４_ｉと、第ｉの算術演算部１０５_ｉと、第ｉの論理演算部１０６_ｉと、第ｉの基本演算シード記憶部１０７_ｉと、第ｉのデータ記憶部１０８_ｉと、を含む。なお、第ｉの再分散値計算部１０２_ｉと、第ｉのシェア構成部１０３_ｉと、第ｉの不正検知部１０４_ｉと、第ｉの算術演算部１０５_ｉと、第ｉの論理演算部１０６_ｉと、第ｉの基本演算シード記憶部１０７_ｉと、第ｉのデータ記憶部１０８_ｉとは、それぞれ接続されている。
【００５２】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置１００_１〜１００_４の内のいずれかの装置が入力した値
2020165931.tif 000097
、あるいは第１乃至第４のデータ記憶部１０８_１〜１０８_４に記憶されたシェア
2020165931.tif 000098
、あるいは第１乃至第４のサーバ装置１００_１〜１００_４ではない外部から入力されたシェア
2020165931.tif 000099
に対し、その入力や計算過程の値から
2020165931.tif 000100
の値を知られることなく、
2020165931.tif 000101
を計算し、第１乃至第４のデータ記憶部１０８_１〜１０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置１００_１〜１００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置１００_１〜１００_４ではない外部にシェアが送信され、復元されてもよい。
【００５３】
また、このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置１００_１〜１００_４の内のいずれかの装置が入力した値
2020165931.tif 000102
、あるいは第１乃至第４のデータ記憶部１０９_１〜１０９_４に記憶されたシェア
2020165931.tif 000103
、あるいは第１乃至第４のサーバ装置１００_１〜１００_４ではない外部から入力されたシェア
2020165931.tif 000104
に対し、その入力や計算過程の値から
2020165931.tif 000105
の値を知られることなく、
2020165931.tif 000106
を計算し、第１乃至第４のデータ記憶部１０８_１〜１０８_４に記憶する。
【００５４】
上記計算結果のシェアは、第１乃至第４のサーバ装置１００_１〜１００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置１００_１〜１００_４ではない外部にシェアが送信され、復元されてもよい。
【００５５】
次に、第１の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置１００_１〜１００_４の動作について、詳細に説明する。図４は、第１乃至第４のサーバ装置１００_１〜１００_４のビット分解に関する動作例を示すフローチャートである。図５は、第１乃至第４のサーバ装置１００_１〜１００_４の環合成に関する動作例を示すフローチャートである。
【００５６】
まず、図４に示すビット分解に関するフローチャートを説明する。
【００５７】
（ステップＡ１）
各基本演算シード記憶部１０７_１、１０７_２、１０７_３、１０７_４は、それぞれ
2020165931.tif 000107
、
2020165931.tif 000108
、
2020165931.tif 000109
、
2020165931.tif 000110
を記憶する。
【００５８】
また、各サーバ装置１００_１〜１００_４は疑似ランダム関数
2020165931.tif 000111
を共有する。なお、
2020165931.tif 000112
とし、疑似ランダム関数
2020165931.tif 000113
とする。また、各データ記憶部１０８_１〜１０８_４に、それぞれ
2020165931.tif 000114
、
2020165931.tif 000115
、
2020165931.tif 000116
、
2020165931.tif 000117
を記憶する。
【００５９】
なお、
2020165931.tif 000118
に関して、サーバ装置１００_ｉ（ｉ＝１〜４）の内、ある一台の参加者は
2020165931.tif 000119
の出力を計算できず、他の三台の参加者は
2020165931.tif 000120
の出力を計算できるという状況を作ることを意図している。また、
2020165931.tif 000121
は、サーバ装置１００_１、１００_２、１００_３の内、ある一台の参加者は
2020165931.tif 000122
の出力を計算できず、他の二台の参加者は
2020165931.tif 000123
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000124
の扱いは特に制限されない。ただし、本書での
2020165931.tif 000125
はあくまでも一例である。
【００６０】
（ステップＡ２）
第１の再分散値計算部１０２_１と第２の再分散値計算部１０２_２はそれぞれ、第１の基本演算シード記憶部１０７_１、第２の基本演算シード記憶部１０７_２より、
2020165931.tif 000126
を取得する。次に、第１の再分散値計算部１０２_１と第２の再分散値計算部１０２_２は
2020165931.tif 000127
を生成する。
【００６１】
そして、第１の再分散値計算部１０２_１は、
2020165931.tif 000128
を第１のデータ記憶部１０８_１に記憶する。第２の再分散値計算部１０２_２は、
2020165931.tif 000129
を、第３のシェア構成部１０３_３に送信する。また、第２の再分散値計算部１０２_２は
2020165931.tif 000130
2020165931.tif 000131
を、第４のシェア構成部１０３_４に送信する。
【００６２】
同様に、第２の再分散値計算部１０２_２と第３の再分散値計算部１０２_３は、
2020165931.tif 000132
2020165931.tif 000133
を生成する。第２の再分散値計算部１０２_２は、
2020165931.tif 000134
を第２のデータ記憶部１０８_２に記憶する。第３の再分散値計算部１０２_３は、
2020165931.tif 000135
を、第１のシェア構成部１０３_１に送信する。また、第３の再分散値計算部１０２_３は
2020165931.tif 000136
2020165931.tif 000137
を、第４のシェア構成部１０３_４に送信する。
【００６３】
さらに同様に、第３の再分散値計算部１０２_３と第１の再分散値計算部１０２_１は
2020165931.tif 000138
を生成する。第３の再分散値計算部１０２_３は、
2020165931.tif 000139
を第３のデータ記憶部１０８_３に記憶する。第１の再分散値計算部１０２_１は、
2020165931.tif 000140
を、第２のシェア構成部１０３_２に送信する。また、第１の再分散値計算部１０２_１は
2020165931.tif 000141
2020165931.tif 000142
を、第４のシェア構成部１０３_４に送信する。
【００６４】
このように、第ｉの再分散値計算部１０２_ｉは、基本演算シード記憶部１０７_ｉに格納されたシードを用いて乱数（例えば、
2020165931.tif 000143
）を生成する。さらに、再分散値計算部１０２_ｉは、シェア（例えば、
2020165931.tif 000144
）の再分散値（例えば、
2020165931.tif 000145
）を計算する。その後、再分散値計算部１０２_ｉは、生成された乱数に関するデータ（例えば、
2020165931.tif 000146
）を他のサーバ装置の再分散値計算部１０２_ｉに送信する。なお、生成された乱数に関するデータには、乱数自身も含まれる。
【００６５】
ここで、
2020165931.tif 000147
である。
2020165931.tif 000148
は、たとえば、カウンタであり、各サーバ装置１００_１〜１００_４の間で共有している。
【００６６】
（ステップＡ３）
各シェア構成部１０３_１、１０３_２、１０３_３、１０３_４は上記ステップＡ２で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000149
2020165931.tif 000150
2020165931.tif 000151
2020165931.tif 000152
2020165931.tif 000153
2020165931.tif 000154
2020165931.tif 000155
2020165931.tif 000156
2020165931.tif 000157
2020165931.tif 000158
2020165931.tif 000159
2020165931.tif 000160
【００６７】
ここで、
2020165931.tif 000161
に対し、
2020165931.tif 000162
は
2020165931.tif 000163
のｊ番目のビット（ｊ＝０、．．．、ｎ−１）を意味する。
2020165931.tif 000164
、
2020165931.tif 000165
、
2020165931.tif 000166
は各ｉ番目のデータ記憶部１０８_ｉに記憶される。
【００６８】
このように、第ｉのシェア構成部１０３_ｉは、他のサーバ装置から受信した乱数に関するデータ、シェアの再分散値を用いて型変換用（ステップＡ３ではビット分解用）のシェアを構成する（再構成）する。つまり、値ｘは、シェアｘ１、ｘ２、ｘ３として分散される。さらに、当該シェアは、再分散され再分散値ｘ１’、ｘ２’、ｘ３’が計算される。この再分散値と再分散値の計算に用いられた乱数ｒに基づき、当初のシェアｘ１、ｘ２、ｘ３はビット分解用のシェアに再構成される。その際、本願開示では、上記１２の式に示されるように、第４のサーバ装置１００_４におけるシェアの形式が他のサーバ装置１００_１〜１００_３と異なるにも関わらず、各サーバ装置のシェアの形式を保つように値ｘが再分散され、シェアが再構成される。上述のように、４者ＭＰＣでは、値
2020165931.tif 000167
に対して、
2020165931.tif 000168
とすると、
2020165931.tif 000169
となり、サーバ装置１００_１〜１００_３のシェアの形式は二つの値の組み合わせからなり、サーバ装置１００_４のシェアの形式は２つの排他的論理和による計算結果の組み合わせとなる。本願開示では、これらのシェアの形式を変換前の形式とし、上記１２の式で表せるシェアの形式が変換後の形式となる。本願開示では、変換前後の形式を比較すると、変換前後で形式は保持されたままシェアが再構成（ビット分解用のシェアに再構成）されていることが理解される。
【００６９】
（ステップＡ４）
各ｉ番目の論理演算部１０６_ｉ同士で通信することで、ｎビット加算器処理
2020165931.tif 000170
を以下のように計算する。ここで、
2020165931.tif 000171
とは、たとえば、
2020165931.tif 000172
、
2020165931.tif 000173
を入力とし、
2020165931.tif 000174
を出力する処理のことである。
【００７０】
2020165931.tif 000175
2020165931.tif 000176
ここで、
2020165931.tif 000177
なので、
2020165931.tif 000178
が計算できた。
なお、
2020165931.tif 000179
は、
2020165931.tif 000180
、…、
2020165931.tif 000181
のシェア列を意味する。各ｉ番目の論理演算部１０６_ｉは、
2020165931.tif 000182
を各データ記憶部１０８_ｉに記憶する。
【００７１】
このように、第ｉの論理演算部１０６_ｉは、上記型変換されたシェア（ビット分解用のシェア）についての論理演算を行う。より具体的には、第ｉの論理演算部１０６_ｉは、型変換されたシェアの加算処理を他のサーバ装置と相互に通信することで実行する。
【００７２】
ここで、上記ステップＡ３、Ａ４について具体例を用いてより具体的に説明する。
【００７３】
ここでは、
2020165931.tif 000183
上のシェア
2020165931.tif 000184
にビット分解を行う場合を説明する。このとき、
2020165931.tif 000185
とすると、各サーバ装置は以下のような形式でシェア
2020165931.tif 000186
を保有する。
サーバ装置１００_１：
2020165931.tif 000187
サーバ装置１００_２：
2020165931.tif 000188
サーバ装置１００_３：
2020165931.tif 000189
サーバ装置１００_４：
2020165931.tif 000190
【００７４】
上記ステップＡ３、Ａ４では、初めに
2020165931.tif 000191
、
2020165931.tif 000192
、
2020165931.tif 000193
の各桁のビットのシェアを得て（ステップＡ３）、次に、ステップＡ３にて得られたビットのシェアを用いて加算器の計算を行うことで値ｘの各桁のビットのシェアを得ている（ステップＡ４）。これは、ステップＡ３は、加算した結果が値ｘとなる各桁のビットのシェアを生成（値ｘからの再分散）を目的を有し、その後に続くステップＡ４における加算器計算に伴う負荷が軽減されるように再分散のシェアの個数自体を少なくするという意義を持つ。
【００７５】
本願開示では、上記再構成されたシェアを得るため、各サーバ装置１００_ｉは、
2020165931.tif 000194
を使用する。その際、各サーバ装置１００_ｉは、自身が保持する
2020165931.tif 000195
だけでは上記再構成されたシェアを生成することが出来ない場合がある。そこで、各サーバ装置１００_ｉは、他のサーバ装置から当該他のサーバ装置が保持する
2020165931.tif 000196
の一部を取得する必要があるが、秘密漏洩を防止する観点から当該値を他のサーバ装置から得ることはできない。そこで、各サーバ装置１００_ｉは、乱数でマスクした値（シェアの再分散値）を送受信し、上記再構成されたシェアの再構成に利用する。本願開示では、シェアの再構成に続く加算器の計算負荷が低減されるように、上記乱数（マスク用の乱数）とシェアの再構成が行われる。
【００７６】
例えば、上記１２の式に記載された
2020165931.tif 000197
は、
2020165931.tif 000198
により再分散され、再構成された
2020165931.tif 000199
、
2020165931.tif 000200
、
2020165931.tif 000201
のうち
2020165931.tif 000202
がサーバ装置１００_１が保有する値（保有する値の組）となる。その際、
2020165931.tif 000203
がマスク用のビットの乱数となり、
2020165931.tif 000204
は、
2020165931.tif 000205
を
2020165931.tif 000206
、
2020165931.tif 000207
でマスクすることで生成された再分散値となる。
【００７７】
ここで、上述のステップＡ３の目的や意義を考えると、サーバ装置１００_３やサーバ装置１００_４は、値
2020165931.tif 000208
を直接保持していないので、これらのサーバ装置が
2020165931.tif 000209
を生成することは困難である。そこで、サーバ装置１００_３やサーバ装置１００_４は、上記値を有するサーバ装置１００_１やサーバ装置１００_２から受信するか、計算可能な乱数により
2020165931.tif 000210
を構成する必要がある。しかし、サーバ装置１００_１やサーバ装置１００_２が保有する値自体を送信すると秘密漏洩の危険が増すのでマスク用の乱数が用いられている。そこで、各再分散値計算部１０２_ｉは、マスク用の乱数を計算すると共に、例えば、サーバ装置１００_２がサーバ装置１００_４に
2020165931.tif 000211
を送信している（ステップＡ２）。その後、ステップＡ３において、
2020165931.tif 000212
を含むシェアの再構成が行われている。
【００７８】
なお、上述のようにシェアの再構成にあたり、その形式を満たす必要がある。例えば、
2020165931.tif 000213
とすると、上記の１２の式では、
2020165931.tif 000214
、
2020165931.tif 000215
、
2020165931.tif 000216
と置き換えることできる。従って、サーバ装置１００_１は、
2020165931.tif 000217
を設定（シェアの再構成）する必要がある。即ち、シェアの形式が満たされるように、
2020165931.tif 000218
や
2020165931.tif 000219
が選択されている。また、本実施形態では、ステップＡ４における加算器計算に伴う負荷を軽減するために再分散のシェアの個数自体を少なくする目的でステップＡ３が実行されている。即ち、加算器の計算コストがビット分解全体の通信コストの大半を占めるため、当該通信コストの重い加算器計算の計算コストを低減するように再分散が行われている。しかし、再分散の目的は上記に限定されず、他の実施形態にて説明するように、「シェアの個数は増加するが、通信の形態に適合させ環合成における通信コストの効率化」や「再分散のシェアの個数は同じであるが、ステップＡ３における再分散のコスト低減」を目的とした再分散もあり得る。
【００７９】
（ステップＡ５）
第１の再分散値計算部１０２_１は、第１のデータ記憶部１０８_１から
2020165931.tif 000220
を取り出す。次に、第１の再分散値計算部１０２_１は、
2020165931.tif 000221
を、第３の不正検知部１０４_３に送信する。また、第１の再分散値計算部１０２_１は、
2020165931.tif 000222
2020165931.tif 000223
を、第４の不正検知部１０４_４に送信する。第３の不正検知部１０４_３および第４の不正検知部１０４_４は、それぞれ、第３のデータ記憶部１０８_３に記憶されている
2020165931.tif 000224
、第４のデータ記憶部１０８_４に記憶されている
2020165931.tif 000225
を取出し、値が一致するかを検証する。
【００８０】
一致した場合、第３の不正検知部１０４_３又は第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第３の不正検知部１０４_３又は第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【００８１】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000226
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000227
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000228
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000229
2020165931.tif 000230
に関しても同様である。
【００８２】
また同様に、第２の再分散値計算部１０２_２は、
2020165931.tif 000231
を第２のデータ記憶部１０８_２から取り出す。次に、第２の再分散値計算部１０２_２は、
2020165931.tif 000232
を、第１の不正検知部１０４_１に送信する。また、第２の再分散値計算部１０２_２は、
2020165931.tif 000233
2020165931.tif 000234
を、第４の不正検知部１０４_４に送信する。第１の不正検知部１０４_１および第４の不正検知部１０４_４は、それぞれ、第１のデータ記憶部１０８_１に記憶されている
2020165931.tif 000235
、第４のデータ記憶部１０８_４に記憶されている
2020165931.tif 000236
を取出し、値が一致するかを検証する。
【００８３】
一致した場合、第１の不正検知部１０４_１又は第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第１の不正検知部１０４_１又は第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【００８４】
大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000237
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000238
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000239
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000240
2020165931.tif 000241
に関しても同様である。
【００８５】
さらに同様に、第３の再分散値計算部１０２_３は、
2020165931.tif 000242
を第３のデータ記憶部１０８_３から取り出す。次に、第３の再分散値計算部１０２_３は、
2020165931.tif 000243
を、第２の不正検知部１０４_２に送信する。また、第３の再分散値計算部１０２_３は、
2020165931.tif 000244
2020165931.tif 000245
を、第４の不正検知部１０４_４に送信する。第２の不正検知部１０４_２および第４の不正検知部１０４_４は、それぞれ、第２のデータ記憶部１０８_２に記憶されている
2020165931.tif 000246
、第４のデータ記憶部１０８_４に記憶されている
2020165931.tif 000247
を取出し、値が一致するかを検証する。
【００８６】
一致した場合、第２の不正検知部１０４_２又は第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第２の不正検知部１０４_１乃至第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【００８７】
大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000248
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000249
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000250
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000251
2020165931.tif 000252
に関しても同様である。
【００８８】
このように、第ｉの不正検知部１０４_ｉは、他のサーバ装置から受信した乱数に関するデータに基づきプロトコルの不正を検知する。具体的には、第ｉの不正検知部１０４_ｉは、他のサーバ装置から受信した乱数に関するデータと自装置に格納されている乱数に関するデータが一致するか否かに応じて不正の有無（不正行為者の有無）を検知する。
【００８９】
（ステップＡ６）
各ｉ番目の不正検知部１０４_ｉは、上記ステップＡ４の
2020165931.tif 000253
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置１００_１、１００_２、１００_３、１００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置１００_１、１００_２、１００_３、１００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＡ６は上記ステップＡ５と並列に実行することが可能である。
【００９０】
このように、第ｉの不正検知部１０４_ｉは、型変換されたシェアの加算処理のために送受信されたデータを用いて不正行為者の有無を検知する。
【００９１】
次に、図５に示す環合成に関するフローチャートを説明する。
【００９２】
（ステップＢ１）
各基本演算シード記憶部１０７_１、１０７_２、１０７_３、１０７_４は、それぞれ、
2020165931.tif 000254
、
2020165931.tif 000255
、
2020165931.tif 000256
、
2020165931.tif 000257
を記憶する。
また、各サーバ装置１００_１〜１００_４は疑似ランダム関数
2020165931.tif 000258
を共有する。なお、
2020165931.tif 000259
とし、疑似ランダム関数
2020165931.tif 000260
とする。
【００９３】
また、各データ記憶部１０８_１〜１０８_４に、
2020165931.tif 000261
、
2020165931.tif 000262
、
2020165931.tif 000263
、
2020165931.tif 000264
を記憶する。さらに、各データ記憶部１０８_１〜１０８_４に、ループカウンタ
2020165931.tif 000265
を記憶する。なお、
2020165931.tif 000266
とし、
2020165931.tif 000267
、
2020165931.tif 000268
、
2020165931.tif 000269
、
2020165931.tif 000270
とする。
【００９４】
なお、
2020165931.tif 000271
に関して、サーバ装置１００_ｉ（ｉ＝１〜４）の内、ある一台の参加者は
2020165931.tif 000272
の出力を計算できず、他の三台の参加者は
2020165931.tif 000273
の出力を計算できるという状況を作ることを意図している。また、
2020165931.tif 000274
は、サーバ装置１００_１、１００_２、１００_３の内、ある一台の参加者は
2020165931.tif 000275
の出力を計算できず、他の二台の参加者は
2020165931.tif 000276
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000277
の扱いは特に制限されない。本書での
2020165931.tif 000278
はあくまでも一例である。
【００９５】
（ステップＢ２）
各サーバ装置１００_ｉは、各データ記憶部１０８_ｉより、ループカウンタｊをとりだす。各サーバ装置１００_ｉは、ｊ＜ｎであればステップＢ３〜Ｂ７を実行する。ｊ＝ｎであれば、ステップＢ８を実行する。
【００９６】
また、各論理演算部１０６_１〜１０６_４は、各データ記憶部１０８_１〜１０８_４から
2020165931.tif 000279
を取り出す。ここで、
2020165931.tif 000280
はｊ番目のビットに対するキャリーである。そして、各論理演算部１０６_１〜１０６_４は、
2020165931.tif 000281
を計算し、
2020165931.tif 000282
を各データ記憶部１０８_１〜１０８_４に記憶する。
【００９７】
なお、第ｉのデータ記憶部１０８_ｉが記憶する
2020165931.tif 000283
を
2020165931.tif 000284
と表記する。また、
2020165931.tif 000285
とする。
【００９８】
（ステップＢ３）
第１の再分散値計算部１０２_１と第２の再分散値計算部１０２_２はそれぞれ、第１の基本演算シード記憶部１０７_１、第２の基本演算シード記憶部１０７_２より、
2020165931.tif 000286
を取得する。次に、第１の再分散値計算部１０２_１と第２の再分散値計算部１０２_２は
2020165931.tif 000287
を生成する。
【００９９】
そして、第１の再分散値計算部１０２_１は、
2020165931.tif 000288
を第１のデータ記憶部１０８_１に記憶する。第２の再分散値計算部１０２_２は、
2020165931.tif 000289
を、第３のシェア構成部１０３_３に送信する。また、第２の再分散値計算部１０２_２は
2020165931.tif 000290
2020165931.tif 000291
を、第４のシェア構成部１０３_４に送信する。
【０１００】
同様に、第２の再分散値計算部１０２_２と第３の再分散値計算部１０２_３は
2020165931.tif 000292
を生成する。第２の再分散値計算部１０２_２は、
2020165931.tif 000293
を第２のデータ記憶部１０８_２に記憶する。第３の再分散値計算部１０２_３は、
2020165931.tif 000294
を、第１のシェア構成部１０３_１に送信する。また、第３の再分散値計算部１０２_３は
2020165931.tif 000295
2020165931.tif 000296
を、第４のシェア構成部１０３_４に送信する。
【０１０１】
さらに同様に、第３の再分散値計算部１０２_３と第１の再分散値計算部１０２_１は
2020165931.tif 000297
を生成する。第３の再分散値計算部１０２_３は、
2020165931.tif 000298
を第３のデータ記憶部１０８_３に記憶する。第１の再分散値計算部１０２_１は、
2020165931.tif 000299
を、第２のシェア構成部１０３_２に送信する。また、第１の再分散値計算部１０２_１は
2020165931.tif 000300
2020165931.tif 000301
を、第４のシェア構成部１０３_４に送信する。
【０１０２】
ここで、
2020165931.tif 000302
である。
2020165931.tif 000303
は、たとえば、カウンタであり、各サーバ装置１００_１〜１００_４の間で共有している。
【０１０３】
（ステップＢ４）
各シェア構成部１０３_１、１０３_２、１０３_３、１０３_４は上記ステップＢ３で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000304
2020165931.tif 000305
2020165931.tif 000306
2020165931.tif 000307
2020165931.tif 000308
2020165931.tif 000309
2020165931.tif 000310
2020165931.tif 000311
2020165931.tif 000312
2020165931.tif 000313
2020165931.tif 000314
2020165931.tif 000315
2020165931.tif 000316
、
2020165931.tif 000317
、
2020165931.tif 000318
は各ｉ番目のデータ記憶部２０８_ｉに記憶される。
【０１０４】
（ステップＢ５）
各ｉ番目の論理演算部１０６_ｉ同士で通信することで、キャリー計算処理
2020165931.tif 000319
を以下のように計算する。ここで、
2020165931.tif 000320
とは、全加算器における入力
2020165931.tif 000321
と下位からの桁上げ入力
2020165931.tif 000322
の５つを入力とし、下記の式のように桁上げ出力
2020165931.tif 000323
を出力する処理である。
2020165931.tif 000324
【０１０５】
各ｉ番目の論理演算部１０６_ｉは、
2020165931.tif 000325
を各データ記憶部１０８_ｉに記憶する。各サーバ装置１００_ｉは、各データ記憶部２０８_ｉより、ループカウンタｊを取り出し、ｊ＝ｊ＋１として各データ記憶部１０８_ｉに記憶する。なお、ｊ＝ｎ−１のとき、ステップＢ５は実行しなくても良い。
【０１０６】
このように、第ｉの論理演算部１０６_ｉは、他のサーバ装置と互いに通信を行い型変換されたシェアのキャリー計算処理を実行する。
【０１０７】
（ステップＢ６）
第１の再分散値計算部１０２_１は、第１のデータ記憶部１０８_１から
2020165931.tif 000326
を取り出す。次に、第１の再分散値計算部１０２_１は、
2020165931.tif 000327
を、第３の不正検知部１０４_３に送信する。また、第１の再分散値計算部１０２_１は、
2020165931.tif 000328
2020165931.tif 000329
を、第４の不正検知部１０４_４に送信する。第３の不正検知部１０４_３および第４の不正検知部１０４_４は、それぞれ、第３のデータ記憶部１０８_３に記憶されている
2020165931.tif 000330
、第４のデータ記憶部１０８_４に記憶されている
2020165931.tif 000331
を取出し、値が一致するかを検証する。
【０１０８】
一致した場合、第３の不正検知部１０４_３又は第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第３の不正検知部１０４_３又は第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【０１０９】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000332
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000333
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000334
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000335
2020165931.tif 000336
に関しても同様である。
【０１１０】
同様に、第２の再分散値計算部１０２_２は、
2020165931.tif 000337
を第２のデータ記憶部１０８_２から取り出す。次に、第２の再分散値計算部１０２_２は、
2020165931.tif 000338
を、第１の不正検知部１０４_１に送信する。また、第２の再分散値計算部１０２_２は、
2020165931.tif 000339
2020165931.tif 000340
を、第４の不正検知部１０４_４に送信する。第１の不正検知部１０４_１および第４の不正検知部１０４_４は、それぞれ、第１のデータ記憶部１０８_１に記憶されている
2020165931.tif 000341
、第４のデータ記憶部１０８_４に記憶されている
2020165931.tif 000342
を取出し、値が一致するかを検証する。
【０１１１】
一致した場合、第１の不正検知部１０４_１又は第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第１の不正検知部１０４_１又は第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【０１１２】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000343
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000344
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000345
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000346
2020165931.tif 000347
に関しても同様である。
【０１１３】
さらに同様に、第３の再分散値計算部１０２_３は、
2020165931.tif 000348
を第３のデータ記憶部１０８_３から取り出す。次に、第３の再分散値計算部１０２_３は、
2020165931.tif 000349
を、第２の不正検知部１０４_２に送信する。また、第３の再分散値計算部１０２_３は、
2020165931.tif 000350
2020165931.tif 000351
を、第４の不正検知部１０４_４に送信する。第２の不正検知部１０４_２および第４の不正検知部１０４_４は、それぞれ、第２のデータ記憶部１０８_２に記憶されている
2020165931.tif 000352
、第４のデータ記憶部１０８_４に記憶されている
2020165931.tif 000353
を取出し、値が一致するかを検証する。
【０１１４】
一致した場合、第２の不正検知部１０４_２又は第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第２の不正検知部１０４_１又は第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【０１１５】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000354
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000355
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000356
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000357
2020165931.tif 000358
に関しても同様である。
【０１１６】
（ステップＢ７）
各ｉ番目の不正検知部１０５_ｉは、上記ステップＢ５の
2020165931.tif 000359
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置１００_１、１００_２、１００_３、１００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置１００_１、１００_２、１００_３、１００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＢ７は上記ステップＢ６と並列に実行することが可能である。また、ステップＢ６、Ｂ７はループごとではなく、ｊ＝ｎ−１のときに、ｎ回のループ分を並列に実行することが可能である。
【０１１７】
このように、第ｉの不正検知部１０５_ｉは、型変換されたシェアのキャリー計算処理のために送受信されたデータを用いて不正行為者の有無を検知する。
【０１１８】
（ステップＢ８）
各ｉ番目の算術演算部１０５_ｉは、各データ記憶部１０８_ｉから
2020165931.tif 000360
を取り出す。その後、以下の式による計算を行う。
2020165931.tif 000361
各ｉ番目の算術演算部１０５_ｉは、各データ記憶部１０８_ｉに
2020165931.tif 000362
を記憶する。
【０１１９】
以上、説明した第１の実施形態においては、以下に記載するような効果を奏する。
【０１２０】
第１の効果は、不正検知可能な４者間秘密計算を用いて、シェアの型変換が実行できる。複雑な混合回路を実行する際に不正検知に関するステップを並列に行った場合、不正検知に関する通信コストを消却できるものとする。たとえば、加算器の計算にリップルキャリー型のｎビット加算器を用いた場合、このときのビット分解の通信コストは、（１６ｎ−１０）ビット・ｎ＋１ラウンドとなる。環合成の通信コストは、（１６ｎ−１６）ビット・２ｎ−２ラウンドとなる。一方で、非特許文献２と非特許文献３を組み合わせた場合の型変換の通信コストは、不正が成功する確率を２−４０としたとき、（４２ｎ−４２）ビット・ｎ−１ラウンドである。これより、本願開示の方が効率の良い方式となる。なお、本特許の実施はリップルキャリー型のｎビット加算器に限定されない。キャリールックアヘッド型やパラレルプリフィックス型などのｎビット加算器を用いても良い。
【０１２１】
第２の効果は、不正検知可能な４者間秘密計算を用いて、シェアの型変換を行う際に、不正検知確率が常に「１」となることである。非特許文献２と非特許文献３を組み合わせた場合、不正検知確率はパラメタライズであるため、不正検知確率を向上させようとした際に、通信コストも大きくなる。秘密計算を適用できるアプリケーションには様々なものがあり、そのアプリケーションに応じて求められる不正検知確率は異なる。求められる要件の調査と、調査に伴う各パラメータの設定は利用者にとって負担となる。本願開示では、不正検知確率が「１」なので、要件の調査やパラメータ設定の負担が軽減される。
【０１２２】
［第２の実施形態］
図６〜図８を参照して、第２の実施形態に係る型変換処理システムについて説明する。
【０１２３】
図６は、第２の実施形態による型変換処理システムの機能構成例を示すブロック図である。図６を参照すると、第２の実施形態による型変換処理システムは、後述する図７で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第２の実施形態による型変換処理システムにおいて、サーバ装置２００_１、２００_２、２００_３、２００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図７は、第ｉのサーバ装置２００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０１２４】
図７に示すように、第ｉのサーバ装置２００_ｉは、第ｉの再分散値計算部２０２_ｉと、第ｉのシェア構成部２０３_ｉと、第ｉの不正検知部２０４_ｉと、第ｉの算術演算部２０５_ｉと、第ｉの論理演算部２０６_ｉと、第ｉの基本演算シード記憶部２０７_ｉと、第ｉのデータ記憶部２０８_ｉと、を含む。なお、第ｉの再分散値計算部２０２_ｉと、第ｉのシェア構成部２０３_ｉと、第ｉの不正検知部２０４_ｉと、第ｉの算術演算部２０５_ｉと、第ｉの論理演算部２０６_ｉと、第ｉの基本演算シード記憶部２０７_ｉと、第ｉのデータ記憶部２０８_ｉとは、それぞれ接続されている。
【０１２５】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置２００_１〜２００_４の内のいずれかの装置が入力した値
2020165931.tif 000363
、あるいは第１乃至第４のデータ記憶部２０８_１〜２０８_４に記憶されたシェア
2020165931.tif 000364
、あるいは第１乃至第４のサーバ装置２００_１〜２００_４ではない外部から入力されたシェア
2020165931.tif 000365
に対し、その入力や計算過程の値から
2020165931.tif 000366
の値を知られることなく、
2020165931.tif 000367
を計算し、第１乃至第４のデータ記憶部２０８_１〜２０８_４に記憶する。上記計算結果のシェアは、第１乃至第４のサーバ装置２００_１〜２００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置２００_１〜２００_４ではない外部にシェアが送信され、シェアが復元されてもよい。
【０１２６】
また、このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置２００_１〜２００_４の内のいずれかの装置が入力した値
2020165931.tif 000368
、あるいは第１乃至第４のデータ記憶部２０８_１〜２０８_４に記憶されたシェア
2020165931.tif 000369
、あるいは第１乃至第４のサーバ装置２００_１〜２００_４ではない外部から入力されたシェア
2020165931.tif 000370
に対し、その入力や計算過程の値から
2020165931.tif 000371
の値を知られることなく、
2020165931.tif 000372
を計算し、第１乃至第４のデータ記憶部２０８_１〜２０８_４に記憶する。上記計算結果のシェアは、第１乃至第４のサーバ装置２００_１〜２００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置２００_１〜２００_４ではない外部にシェアが送信され、シェアが復元されてもよい。
【０１２７】
次に、第２の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置２００_１〜２００_４の動作について、詳細に説明する。図７は、第１乃至第４のサーバ装置２００_１〜２００_４の環合成に関する動作例を示すフローチャートである。ビット分解については、第１の実施例と同様に実施可能であるため説明を割愛する。
【０１２８】
図７に示す環合成に関するフローチャートを説明する。
【０１２９】
（ステップＢ´１）
各基本演算シード記憶部２０７_１、２０７_２、２０７_３、２０７_４は、それぞれ、
2020165931.tif 000373
、
2020165931.tif 000374
、
2020165931.tif 000375
、
2020165931.tif 000376
を記憶する。
【０１３０】
また、各サーバ装置２００_１〜２００_４は疑似ランダム関数
2020165931.tif 000377
を共有する。なお、
2020165931.tif 000378
とし、疑似ランダム関数
2020165931.tif 000379
とする。
【０１３１】
また、各データ記憶部２０８_１〜２０８_４に、
2020165931.tif 000380
、
2020165931.tif 000381
、
2020165931.tif 000382
、
2020165931.tif 000383
を記憶する。さらに、各データ記憶部２０８_１〜２０８_４に、ループカウンタｊ（＝１）を記憶する。なお、
2020165931.tif 000384
とし、
2020165931.tif 000385
、
2020165931.tif 000386
、
2020165931.tif 000387
、
2020165931.tif 000388
とする。
【０１３２】
なお、
2020165931.tif 000389
に関して、サーバ装置２００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165931.tif 000390
の出力を計算できず、他の三台の参加者は
2020165931.tif 000391
の出力を計算できるという状況を作ることを意図している。また、
2020165931.tif 000392
は、サーバ装置２００_１、２００_２、２００_３の内、ある一台の参加者は
2020165931.tif 000393
の出力を計算できず、他の二台の参加者は
2020165931.tif 000394
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000395
の扱いは特に制限されない。本書での
2020165931.tif 000396
はあくまでも一例である。
【０１３３】
（ステップＢ´２）
各サーバ装置２００_ｉは、以下の式に示されるように
2020165931.tif 000397
の値を定める。
2020165931.tif 000398
2020165931.tif 000399
【０１３４】
各データ記憶部２０８_１〜２０８_４は、それぞれ
2020165931.tif 000400
、
2020165931.tif 000401
、
2020165931.tif 000402
、
2020165931.tif 000403
、
2020165931.tif 000404
を記憶する。
【０１３５】
第１の再分散値計算部２０２_１と第２の再分散値計算部２０２_２はそれぞれ、第１の基本演算シード記憶部２０７_１、第２の基本演算シード記憶部２０７_２より、
2020165931.tif 000405
を取得する。次に、第１の再分散値計算部２０２_１と第２の再分散値計算部２０２_２は、
2020165931.tif 000406
を生成する。
【０１３６】
そして、第１の再分散値計算部２０２_１は、
2020165931.tif 000407
を第１のデータ記憶部２０８_１に記憶する。第２の再分散値計算部２０２_２は、
2020165931.tif 000408
を、第３のシェア構成部２０３_３に送信する。また、第２の再分散値計算部２０２_２は
2020165931.tif 000409
2020165931.tif 000410
を、第４のシェア構成部２０３_４に送信する。
【０１３７】
同様に、第２の再分散値計算部２０２_２と第３の再分散値計算部２０２_３は、
2020165931.tif 000411
を生成する。第２の再分散値計算部２０２_２は、
2020165931.tif 000412
を第２のデータ記憶部２０８_２に記憶する。第３の再分散値計算部２０２_３は、
2020165931.tif 000413
を、第１のシェア構成部２０３_１に送信する。また、第３の再分散値計算部２０２_３は
2020165931.tif 000414
2020165931.tif 000415
を、第４のシェア構成部２０３_４に送信する。
【０１３８】
さらに同様に、第３の再分散値計算部２０２_３と第１の再分散値計算部２０２_１は
2020165931.tif 000416
を生成する。第３の再分散値計算部３０２_３は、
2020165931.tif 000417
を第３のデータ記憶部２０８_３に記憶する。第１の再分散値計算部２０２_１は、
2020165931.tif 000418
を、第２のシェア構成部２０３_２に送信する。また、第１の再分散値計算部２０２_１は
2020165931.tif 000419
2020165931.tif 000420
を、第４のシェア構成部２０３_４に送信する。
【０１３９】
ここで、
2020165931.tif 000421
である。
2020165931.tif 000422
は、たとえば、カウンタであり、各サーバ装置２００_１〜２００_４の間で共有している。
【０１４０】
（ステップＢ´３）
各シェア構成部２０３_１、２０３_２、２０３_３、２０３_４は上記ステップＢ´２で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000423
2020165931.tif 000424
2020165931.tif 000425
2020165931.tif 000426
2020165931.tif 000427
2020165931.tif 000428
2020165931.tif 000429
2020165931.tif 000430
2020165931.tif 000431
2020165931.tif 000432
2020165931.tif 000433
2020165931.tif 000434
2020165931.tif 000435
、
2020165931.tif 000436
、
2020165931.tif 000437
は各ｉ番目のデータ記憶部２０８_ｉに記憶される。
【０１４１】
（ステップＢ´４）
第１の再分散値計算部２０２_１は、第１のデータ記憶部２０８_１から
2020165931.tif 000438
を取り出す。次に、第１の再分散値計算部２０２_１は、
2020165931.tif 000439
を、第３の不正検知部２０４_３に送信する。また、第１の再分散値計算部２０２_１は、
2020165931.tif 000440
2020165931.tif 000441
を、第４の不正検知部２０４_４に送信する。第３の不正検知部２０４_３および第４の不正検知部２０４_４は、それぞれ、第３のデータ記憶部２０８_３に記憶されている
2020165931.tif 000442
、第４のデータ記憶部２０８_４に記憶されている
2020165931.tif 000443
を取出し、値が一致するかを検証する。
【０１４２】
一致した場合、第３の不正検知部２０４_３又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第３の不正検知部２０４_３又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、プロトコルを中断する。
【０１４３】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000444
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000445
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000446
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000447
2020165931.tif 000448
に関しても同様である。
【０１４４】
同様に、第２の再分散値計算部１０２_２は、
2020165931.tif 000449
を第２のデータ記憶部２０８_２から取り出す。次に、第２の再分散値計算部２０２_２は、
2020165931.tif 000450
を、第１の不正検知部２０４_１に送信する。また、第２の再分散値計算部２０２_２は、
2020165931.tif 000451
2020165931.tif 000452
を、第４の不正検知部２０４_４に送信する。第１の不正検知部２０４_１および第４の不正検知部２０４_４は、それぞれ、第１のデータ記憶部２０８_１に記憶されている
2020165931.tif 000453
、第４のデータ記憶部２０８_４に記憶されている
2020165931.tif 000454
を取出し、値が一致するかを検証する。
【０１４５】
一致した場合、第１の不正検知部２０４_１又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第１の不正検知部２０４_１又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、プロトコルを中断する。
【０１４６】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000455
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000456
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000457
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000458
2020165931.tif 000459
に関しても同様である。
【０１４７】
さらに同様に、第３の再分散値計算部２０２_３は、
2020165931.tif 000460
を第３のデータ記憶部２０８_３から取り出す。次に、第３の再分散値計算部２０２_３は、
2020165931.tif 000461
を、第２の不正検知部２０４_２に送信する。また、第３の再分散値計算部２０２_３は、
2020165931.tif 000462
2020165931.tif 000463
を、第４の不正検知部２０４_４に送信する。第２の不正検知部２０４_２および第４の不正検知部２０４_４は、それぞれ、第２のデータ記憶部２０８_２に記憶されている
2020165931.tif 000464
、第４のデータ記憶部２０８_４に記憶されている
2020165931.tif 000465
を取出し、値が一致するかを検証する。
【０１４８】
一致した場合、第２の不正検知部２０４_２又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第２の不正検知部２０４_２又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、プロトコルを中断する。
【０１４９】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000466
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000467
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000468
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000469
2020165931.tif 000470
に関しても同様である。
【０１５０】
（ステップＢ´５）
各サーバ装置２００_ｉは、各データ記憶部２０８_より、ループカウンタｊをとりだす。各サーバ装置２００_ｉは、ｊ＜ｎであればステップＢ´６〜Ｂ´１０を実行する。ｊ＝ｎであれば、ステップＢ´１１を実行する。
【０１５１】
（ステップＢ´６）
ここで、キャリー計算処理
2020165931.tif 000471
を、
2020165931.tif 000472
と
2020165931.tif 000473
という２つの処理に分割して考える。なお、
2020165931.tif 000474
とは、全加算器における入力
2020165931.tif 000475
と下位からの桁上げ入力
2020165931.tif 000476
の５つを入力とし、桁上げ出力
2020165931.tif 000477
を出力する処理である。
【０１５２】
2020165931.tif 000478
とは、
2020165931.tif 000479
、
2020165931.tif 000480
、
2020165931.tif 000481
、
2020165931.tif 000482
、
2020165931.tif 000483
を入力に取り、
2020165931.tif 000484
を出力するといった、論理演算部２０６_ｉ（ｉ＝１、２、３）が計算する通信不要の処理を指す。
【０１５３】
また、
2020165931.tif 000485
とは、
2020165931.tif 000486
、
2020165931.tif 000487
、
2020165931.tif 000488
、
2020165931.tif 000489
および
2020165931.tif 000490
を入力に取り、
2020165931.tif 000491
を出力するといった、論理演算部２０６_ｉ（ｉ＝１、２、３、４）が通信を伴って計算する処理を指す。
【０１５４】
ステップＢ´６で、論理演算部２０６_ｉ（ｉ＝１、２、３）は
2020165931.tif 000492
、
2020165931.tif 000493
、
2020165931.tif 000494
、
2020165931.tif 000495
、
2020165931.tif 000496
を入力に取り、
2020165931.tif 000497
を計算することで、
2020165931.tif 000498
を得る。
【０１５５】
さらに論理演算部２０６_ｉ（ｉ＝１、２、３）は、
2020165931.tif 000499
を用いて、
2020165931.tif 000500
を計算する。論理演算部２０６_ｉ（ｉ＝１、２、３）は、データ記憶部２０８_ｉ（ｉ＝１、２、３）に
2020165931.tif 000501
を記憶する。
【０１５６】
（ステップＢ´７）
第１の再分散値計算部２０２_１と第２の再分散値計算部２０２_２はそれぞれ、第１の基本演算シード記憶部２０７_１、第２の基本演算シード記憶部２０７_２より、
2020165931.tif 000502
を取得する。次に、第１の再分散値計算部２０２_１と第２の再分散値計算部２０２_２は、
2020165931.tif 000503
を生成する。
【０１５７】
そして、第１の再分散値計算部２０２_１は、
2020165931.tif 000504
を第１のデータ記憶部２０８_１に記憶する。第２の再分散値計算部２０２_２は、
2020165931.tif 000505
を、第３のシェア構成部２０３_３に送信する。また、第２の再分散値計算部２０２_２は
2020165931.tif 000506
2020165931.tif 000507
を、第４のシェア構成部２０３_４に送信する。
【０１５８】
同様に、第２の再分散値計算部２０２_２と第３の再分散値計算部２０２_３は、
2020165931.tif 000508
を生成する。第２の再分散値計算部２０２_２は、
2020165931.tif 000509
を第２のデータ記憶部２０８_２に記憶する。第３の再分散値計算部２０２_３は、
2020165931.tif 000510
を、第１のシェア構成部２０３_１に送信する。また、第３の再分散値計算部２０２_３は
2020165931.tif 000511
2020165931.tif 000512
を、第４のシェア構成部２０３_４に送信する。
【０１５９】
さらに同様に、第３の再分散値計算部２０２_３と第１の再分散値計算部２０２_１は
2020165931.tif 000513
を生成する。第３の再分散値計算部２０２_３は、
2020165931.tif 000514
を第３のデータ記憶部２０８_３に記憶する。第１の再分散値計算部２０２_１は、
2020165931.tif 000515
を、第２のシェア構成部２０３_２に送信する。また、第１の再分散値計算部２０２_１は
2020165931.tif 000516
2020165931.tif 000517
を、第４のシェア構成部２０３_４に送信する。
【０１６０】
ここで、
2020165931.tif 000518
である。
2020165931.tif 000519
は、たとえば、カウンタであり、各サーバ装置２００_１〜２００_４の間で共有している。
【０１６１】
また、論理演算部２０６_ｉ（ｉ＝１、２、３、４）は、
2020165931.tif 000520
、
2020165931.tif 000521
、
2020165931.tif 000522
、
2020165931.tif 000523
および
2020165931.tif 000524
を入力に取り、
2020165931.tif 000525
を通信を伴って計算することで、
2020165931.tif 000526
を得る。論理演算部２０６_ｉ（ｉ＝１、２、３、４）は、データ記憶部２０８_ｉ（ｉ＝１、２、３、４）に
2020165931.tif 000527
を記憶する。
【０１６２】
このように、キャリー計算処理は、第１要素
2020165931.tif 000528
及び当該第１要素に続く第２要素
2020165931.tif 000529
に分離可能である。第ｉの論理演算部２０６_ｉは、第１要素を他のサーバ装置と非通信により計算すると共に、シェアの再分散値の計算に必要な通信と第２要素のキャリー計算処理に必要な通信を並列に行う（ステップＢ’７）。
【０１６３】
（ステップＢ´８）
論理演算部２０６_ｉ（ｉ＝１、２、３、４）は、
2020165931.tif 000530
を用いて、
2020165931.tif 000531
を計算する。
ここで、上記ステップＢ´７で得た値と、
2020165931.tif 000532
を用いて、各シェア構成部２０３_１、２０３_２、２０３_３、２０３_４は、以下の１２の式によりシェアを構成する。
2020165931.tif 000533
2020165931.tif 000534
2020165931.tif 000535
2020165931.tif 000536
2020165931.tif 000537
2020165931.tif 000538
2020165931.tif 000539
2020165931.tif 000540
2020165931.tif 000541
2020165931.tif 000542
2020165931.tif 000543
2020165931.tif 000544
2020165931.tif 000545
、
2020165931.tif 000546
、
2020165931.tif 000547
が各ｉ番目のデータ記憶部２０８_ｉに記憶される。また、データ記憶部２０８_ｉはループカウンタｊを取り出し、ｊ＝ｊ＋１として値を更新する。
【０１６４】
（ステップＢ´９）
第１の再分散値計算部２０２_１は、第１のデータ記憶部２０８_１から
2020165931.tif 000548
を取り出す。次に、第１の再分散値計算部２０２_１は、
2020165931.tif 000549
を、第３の不正検知部２０４_３に送信する。また、第１の再分散値計算部２０２_１は、
2020165931.tif 000550
2020165931.tif 000551
を、第４の不正検知部２０４_４に送信する。第３の不正検知部２０４_３および第４の不正検知部２０４_４は、それぞれ、第３のデータ記憶部２０８_３に記憶されている
2020165931.tif 000552
、第４のデータ記憶部２０８_４に記憶されている
2020165931.tif 000553
を取出し、値が一致するかを検証する。
【０１６５】
一致した場合、第３の不正検知部２０４_３又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第３の不正検知部２０４_３又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、プロトコルを中断する。
【０１６６】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000554
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000555
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000556
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000557
2020165931.tif 000558
に関しても同様である。
【０１６７】
同様に、第２の再分散値計算部２０２_２は、
2020165931.tif 000559
を第２のデータ記憶部２０８_２から取り出す。次に、第２の再分散値計算部２０２_２は、
2020165931.tif 000560
を、第１の不正検知部２０４_１に送信する。また、第２の再分散値計算部２０２_２は、
2020165931.tif 000561
2020165931.tif 000562
を、第４の不正検知部２０４_４に送信する。第１の不正検知部２０４_１および第４の不正検知部２０４_４は、それぞれ、第１のデータ記憶部２０８_１に記憶されている
2020165931.tif 000563
、第４のデータ記憶部２０８_４に記憶されている
2020165931.tif 000564
を取出し、値が一致するかを検証する。
【０１６８】
一致した場合、第１の不正検知部２０４_１又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第１の不正検知部２０４_１又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、プロトコルを中断する。
【０１６９】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000565
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000566
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000567
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000568
2020165931.tif 000569
に関しても同様である。
【０１７０】
さらに同様に、第３の再分散値計算部２０２_３は、
2020165931.tif 000570
を第３のデータ記憶部２０８_３から取り出す。次に、第３の再分散値計算部２０２_３は、
2020165931.tif 000571
を、第２の不正検知部２０４_２に送信する。また、第３の再分散値計算部２０２_３は、
2020165931.tif 000572
2020165931.tif 000573
を、第４の不正検知部２０４_４に送信する。第２の不正検知部２０４_２および第４の不正検知部２０４_４は、それぞれ、第２のデータ記憶部２０８_２に記憶されている
2020165931.tif 000574
、第４のデータ記憶部２０８_４に記憶されている
2020165931.tif 000575
を取出し、値が一致するかを検証する。
【０１７１】
一致した場合、第２の不正検知部２０４_２又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第２の不正検知部２０４_２又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、プロトコルを中断する。
【０１７２】
なお、大量の型変換処理を並列して行う場合、上記検証は、
2020165931.tif 000576
それぞれとを連結した値に対するハッシュ値と、
2020165931.tif 000577
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するかを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165931.tif 000578
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165931.tif 000579
2020165931.tif 000580
に関しても同様である。
【０１７３】
なお、ステップＢ´９は、ループごとではなく、ｊ＝ｎ−１のときに全ループ分を並列に実行しても良い。また、ステップＢ´９は、上記ステップＢ´４と並列に実行することも可能である。
【０１７４】
（ステップＢ´１０）
各ｉ番目の不正検知部２０４_ｉは、上記ステップＢ´７の
2020165931.tif 000581
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置２００_１、２００_２、２００_３、２００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置２００_１、２００_２、２００_３、２００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＢ´１０は上記ステップＢ´４、Ｂ´９と並列に実行することが可能である。また、ステップＢ´１０はループごとではなく、ｊ＝ｎ−１のときに、全ループ分を並列に実行することが可能である。
【０１７５】
（ステップＢ´１１）
各ｉ番目の算術演算部２０５_ｉは、各データ記憶部２０８_ｉから
2020165931.tif 000582
を取り出す。その後、以下の式に示す計算が実行される。
2020165931.tif 000583
各ｉ番目の算術演算部２０５_ｉは、各データ記憶部２０８_ｉに
2020165931.tif 000584
を記憶する。
【０１７６】
以上、説明した第２の実施形態においては、第１の実施形態における効果と同じ効果を奏する。ただし、第１の実施形態における第１の効果に関して、第２の実施形態の方が環合成における通信コストの点で効率が良い。第２の実施形態では、キャリー計算処理
2020165931.tif 000585
を分割して考え、シェアの再分散とキャリー計算における通信を伴う処理を並列して行うことで、通信ラウンドの削減を実現している。このため、第２の実施形態における環合成の通信コストは、（１６ｎ−１６）ビット・ｎ−１ラウンドとなる。
【０１７７】
［第３の実施形態］
図９〜図１２を参照して、第３の実施形態に係る型変換処理システムについて説明する。
【０１７８】
図９は、第３の実施形態による型変換処理システムの機能構成例を示すブロック図である。第３の実施形態に係る型変換処理システムは、上述した第１の実施形態および第２の実施形態に係る型変換処理システムの変形例である。
【０１７９】
図９を参照すると、第３の実施形態による型変換処理システムは、後述する図１０で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第３の実施形態による型変換処理システムにおいて、サーバ装置３００_１、３００_２、３００_３、３００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図１０は、第ｉのサーバ装置３００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０１８０】
図１０に示すように、第ｉのサーバ装置３００_ｉは、第ｉの再分散値計算部３０２_ｉと、第ｉのシェア構成部３０３_ｉと、第ｉの不正検知部３０４_ｉと、第ｉの算術演算部３０５_ｉと、第ｉの論理演算部３０６_ｉと、第ｉの基本演算シード記憶部３０７_ｉと、第ｉのデータ記憶部３０８_ｉと、を含む。なお、第ｉの再分散値計算部３０２_ｉと、第ｉのシェア構成部３０３_ｉと、第ｉの不正検知部３０４_ｉと、第ｉの算術演算部３０５_ｉと、第ｉの論理演算部３０６_ｉと、第ｉの基本演算シード記憶部３０７_ｉと、第ｉのデータ記憶部３０８_ｉとは、それぞれ接続されている。
【０１８１】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置３００_１〜３００_４の内のいずれかの装置が入力した値
2020165931.tif 000586
、あるいは第１乃至第４のデータ記憶部３０８_１〜３０８_４に記憶されたシェア
2020165931.tif 000587
、あるいは第１乃至第４のサーバ装置３００_１〜３００_４ではない外部から入力されたシェア
2020165931.tif 000588
に対し、その入力や計算過程の値から
2020165931.tif 000589
の値を知られることなく、
2020165931.tif 000590
を計算し、第１乃至第４のデータ記憶部３０８_１〜３０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置３００_１〜３００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置３００_１〜３００_４ではない外部にシェアが送信され、復元されてもよい。
【０１８２】
また、このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置３００_１〜３００_４の内のいずれかの装置が入力した値
2020165931.tif 000591
、あるいは第１乃至第４のデータ記憶部３０８_１〜３０８_４に記憶されたシェア
2020165931.tif 000592
、あるいは第１乃至第４のサーバ装置３００_１〜３００_４ではない外部から入力されたシェア
2020165931.tif 000593
に対し、その入力や計算過程の値から
2020165931.tif 000594
の値を知られることなく、
2020165931.tif 000595
を計算し、第１乃至第４のデータ記憶部３０８_１〜３０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置３００_１〜３００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置３００_１〜３００_４ではない外部にシェアが送信され、復元されてもよい。
【０１８３】
次に、第３の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置３００_１〜３００_４の動作について、詳細に説明する。図１１は、第１乃至第４のサーバ装置３００_１〜３００_４のビット分解に関する動作例を示すフローチャートである。図１２は、第１乃至第４のサーバ装置３００_１〜３００_４の環合成に関する動作例を示すフローチャートである。
【０１８４】
まず、図１１に示すビット分解に関するフローチャートを説明する。
【０１８５】
（ステップＣ１）
各基本演算シード記憶部３０７_１、３０７_２、３０７_３、３０７_４は、それぞれ
2020165931.tif 000596
、
2020165931.tif 000597
、
2020165931.tif 000598
、
2020165931.tif 000599
を記憶する。
【０１８６】
また、各サーバ装置３００_１〜３００_４は疑似ランダム関数
2020165931.tif 000600
を共有する。なお、
2020165931.tif 000601
とし、疑似ランダム関数
2020165931.tif 000602
とする。また、各データ記憶部３０８_１〜３０８_４に、それぞれ
2020165931.tif 000603
、
2020165931.tif 000604
、
2020165931.tif 000605
、
2020165931.tif 000606
を記憶する。
【０１８７】
なお、
2020165931.tif 000607
に関して、サーバ装置３００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165931.tif 000608
の出力を計算できず、他の三台の参加者は
2020165931.tif 000609
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000610
の扱いは特に制限されない。本書での
2020165931.tif 000611
はあくまでも一例である。
【０１８８】
（ステップＣ２）
第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２はそれぞれ、第１の基本演算シード記憶部３０７_１、第２の基本演算シード記憶部３０７_２より、
2020165931.tif 000612
を取得する。次に、第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２と第１の再分散値計算部３０２_１と第３の再分散値計算部３０２_３は
2020165931.tif 000613
を生成する。
【０１８９】
そして、第１の再分散値計算部３０２_１は、
2020165931.tif 000614
を第１のデータ記憶部３０８_１に記憶する。第３の再分散値計算部３０２_３は、
2020165931.tif 000615
を、第３のシェア構成部３０３_３に送信する。また、第２の再分散値計算部３０２_２は
2020165931.tif 000616
を、第４のシェア構成部３０３_４に送信する。
【０１９０】
同様に、第１の再分散値計算部３０２_１、第２の再分散値計算部３０２_２と第３の再分散値計算部３０２_３は、
2020165931.tif 000617
を生成する。第２の再分散値計算部３０２_２は、
2020165931.tif 000618
を第２のデータ記憶部３０８_２に記憶する。第１の再分散値計算部３０２_１は、
2020165931.tif 000619
を、第１のシェア構成部３０３_１に送信する。また、第３の再分散値計算部３０２_３は
2020165931.tif 000620
を、第４のシェア構成部３０３_４に送信する。
【０１９１】
さらに同様に、第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２と第３の再分散値計算部３０２_３は、
2020165931.tif 000621
を生成する。第３の再分散値計算部３０２_３は、
2020165931.tif 000622
を第３のデータ記憶部３０８_３に記憶する。第２の再分散値計算部３０２_２は、
2020165931.tif 000623
を、第２のシェア構成部３０３_２に送信する。また、第１の再分散値計算部３０２_１は
2020165931.tif 000624
を、第４のシェア構成部３０３_４に送信する。
【０１９２】
ここで、
2020165931.tif 000625
である。
2020165931.tif 000626
は、たとえば、カウンタであり、各サーバ装置３００_１〜３００_４の間で共有している。
【０１９３】
（ステップＣ３）
各シェア構成部３０３_１、３０３_２、３０３_３、３０３_４は上記ステップＣ２で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000627
2020165931.tif 000628
2020165931.tif 000629
2020165931.tif 000630
2020165931.tif 000631
2020165931.tif 000632
2020165931.tif 000633
2020165931.tif 000634
2020165931.tif 000635
2020165931.tif 000636
2020165931.tif 000637
2020165931.tif 000638
ここで、
2020165931.tif 000639
に対し、
2020165931.tif 000640
は
2020165931.tif 000641
の
2020165931.tif 000642
番目のビット
2020165931.tif 000643
を意味する。
2020165931.tif 000644
、
2020165931.tif 000645
、
2020165931.tif 000646
が各ｉ番目のデータ記憶部３０８_ｉに記憶される。
【０１９４】
上記ステップＣ３における１２の式において、
2020165931.tif 000647
は、
2020165931.tif 000648
としたとき、
2020165931.tif 000649
、
2020165931.tif 000650
、
2020165931.tif 000651
と置き換えることできる。このように、
2020165931.tif 000652
となるので、各再分散値計算部３０２_ｉは、値ｘの再分散値を計算する際、値ｘをｘ１、ｘ２、ｘ３の排他的論理和とする場合にｘ１乃至ｘ３のうち２つの値を等しくするように乱数を生成している。
【０１９５】
（ステップＣ４）
各ｉ番目の論理演算部３０６_ｉで通信することで、ｎビット加算器処理
2020165931.tif 000653
を以下のように計算する。ここで、
2020165931.tif 000654
とは、たとえば、
2020165931.tif 000655
、
2020165931.tif 000656
を入力とし、
2020165931.tif 000657
を出力する処理のことである。
2020165931.tif 000658
2020165931.tif 000659
ここで、
2020165931.tif 000660
なので、
2020165931.tif 000661
が計算できた。なお、
2020165931.tif 000662
は、
2020165931.tif 000663
、…、
2020165931.tif 000664
のシェア列を意味する。各ｉ番目の論理演算部３０６_ｉは、
2020165931.tif 000665
を各データ記憶部３０８_ｉに記憶する。
【０１９６】
（ステップＣ５）
第１の再分散値計算部３０２_１は、第１のデータ記憶部３０８_１から
2020165931.tif 000666
を取り出す。次に、第１の再分散値計算部３０２_１は、
2020165931.tif 000667
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０８_４に記憶されている
2020165931.tif 000668
を取出し、
2020165931.tif 000669
が成立するかを検証する。
【０１９７】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０１９８】
同様に、第２の再分散値計算部３０２_２は、
2020165931.tif 000670
を第２のデータ記憶部３０８_２から取り出す。次に、第２の再分散値計算部３０２_２は、
2020165931.tif 000671
を、第４の不正検知部３０４_４に送信する。第４の不正検知部２０４_４は、第４のデータ記憶部３０８_４に記憶されている
2020165931.tif 000672
を取出し、
2020165931.tif 000673
が成立するかを検証する。
【０１９９】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０２００】
さらに同様に、第３の再分散値計算部３０２_３は、
2020165931.tif 000674
を第３のデータ記憶部３０８_３から取り出す。次に、第３の再分散値計算部３０２_３は、
2020165931.tif 000675
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０８_４に記憶されている
2020165931.tif 000676
を取出し、
2020165931.tif 000677
が成立するかを検証する。
【０２０１】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０２０２】
なお、大量の型変換処理を並列して行う場合、
2020165931.tif 000678
については、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０２０３】
（ステップＣ６）
各ｉ番目の不正検知部３０４_ｉは、上記ステップＣ４の
2020165931.tif 000679
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置３００_１、３００_２、３００_３、３００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置３００_１、３００_２、３００_３、３００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＣ６は上記ステップＣ５と並列に実行することが可能である。
【０２０４】
次に、図１２に示す環合成に関するフローチャートを説明する。
【０２０５】
（ステップＤ１）
各基本演算シード記憶部３０７_１、３０７_２、３０７_３、３０７_４は、それぞれ
2020165931.tif 000680
、
2020165931.tif 000681
、
2020165931.tif 000682
、
2020165931.tif 000683
を記憶する。
【０２０６】
また、各サーバ装置３００_１〜３００_４は疑似ランダム関数
2020165931.tif 000684
を共有する。なお、
2020165931.tif 000685
とし、疑似ランダム関数
2020165931.tif 000686
とする。また、各データ記憶部３０８_１〜３０８_４に、
2020165931.tif 000687
、
2020165931.tif 000688
、
2020165931.tif 000689
、
2020165931.tif 000690
を記憶する。さらに、各データ記憶部３０８_１〜３０８_４に、ループカウンタｊ（＝０）を記憶する。なお、
2020165931.tif 000691
とし、
2020165931.tif 000692
、
2020165931.tif 000693
、
2020165931.tif 000694
、
2020165931.tif 000695
とする。
【０２０７】
また、
2020165931.tif 000696
に関して、サーバ装置３００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165931.tif 000697
の出力を計算できず、他の三台の参加者は
2020165931.tif 000698
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000699
の扱いは特に制限されない。本書での
2020165931.tif 000700
はあくまでも一例である。
【０２０８】
（ステップＤ２）
各サーバ装置３００_ｉは、各データ記憶部３０８_ｉより、ループカウンタｊをとりだす。各サーバ装置３００_ｉは、ｊ＜ｎであればステップＤ３〜Ｄ７を実行する。ｊ＝ｎであれば、各サーバ装置３００_ｉはステップＤ８を実行する。
【０２０９】
また、各算術演算部３０５_１〜３０５_４は、各データ記憶部３０８_１〜３０８_４から
2020165931.tif 000701
を取り出す。そして、各算術演算部３０５_１〜３０５_４は、
2020165931.tif 000702
を計算し、
2020165931.tif 000703
を各データ記憶部３０８_１〜３０８_４に記憶する。なお、第ｉのデータ記憶部３０８_ｉが記憶する
2020165931.tif 000704
を
2020165931.tif 000705
と表記する。また、
2020165931.tif 000706
とする。
【０２１０】
（ステップＤ３）
第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２と第３の再分散値計算部３０２_３はそれぞれ、第１の基本演算シード記憶部３０７_１、第２の基本演算シード記憶部３０７_２、第３の基本演算シード記憶部３０７_３より、
2020165931.tif 000707
を取得する。次に、第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２と第３の再分散値計算部３０２_３は、
2020165931.tif 000708
を生成する。そして、第１の再分散値計算部３０２_１は、
2020165931.tif 000709
を第１のシェア構成部３０３_１に送信する。第３の再分散値計算部３０２_３は
2020165931.tif 000710
を、第３のシェア構成部３０３_３に送信する。第２の再分散値計算部３０２_２は、第２のデータ記憶部３０８_２から
2020165931.tif 000711
を取出し、
2020165931.tif 000712
を、第４のシェア構成部３０３_４に送信する。
【０２１１】
同様に、第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２と第３の再分散値計算部３０２_３は
2020165931.tif 000713
を生成する。第２の再分散値計算部３０２_２は、
2020165931.tif 000714
を、第２のシェア構成部３０３_２に送信する。第１の再分散値計算部３０２_１は、
2020165931.tif 000715
を、第１のシェア構成部３０３_１に送信する。また、第３の再分散値計算部３０２_３は、第３のデータ記憶部３０８_２から
2020165931.tif 000716
を取出し、
2020165931.tif 000717
を、第４のシェア構成部３０３_４に送信する。
【０２１２】
さらに同様に、第１の再分散値計算部３０２_１と第２の再分散値計算部３０２_２と第３の再分散値計算部３０２_３は、
2020165931.tif 000718
を生成する。第３の再分散値計算部３０２_３は、
2020165931.tif 000719
を第３のシェア構成部３０３_３に送信する。第２の再分散値計算部３０２_２は、
2020165931.tif 000720
を、第２のシェア構成部３０３_２に送信する。また、第１の再分散値計算部３０２_１は、第１のデータ記憶部３０８_１から
2020165931.tif 000721
を取出し、
2020165931.tif 000722
を、第４のシェア構成部３０３_４に送信する。
【０２１３】
ここで、
2020165931.tif 000723
である。
2020165931.tif 000724
は、たとえば、カウンタであり、各サーバ装置３００_１〜３００_４の間で共有している。
【０２１４】
（ステップＤ４）
各シェア構成部３０３_１、３０３_２、３０３_３、３０３_４は上記ステップＤ３で送信された値と、各ｉ番目のデータ記憶部３０８_ｉに記憶された
2020165931.tif 000725
を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000726
2020165931.tif 000727
2020165931.tif 000728
2020165931.tif 000729
2020165931.tif 000730
2020165931.tif 000731
2020165931.tif 000732
2020165931.tif 000733
2020165931.tif 000734
2020165931.tif 000735
2020165931.tif 000736
2020165931.tif 000737
2020165931.tif 000738
、
2020165931.tif 000739
、
2020165931.tif 000740
が各ｉ番目のデータ記憶部３０８_ｉに記憶される。
【０２１５】
（ステップＤ５）
上記ステップＢ５と同じ処理が行われる。
【０２１６】
（ステップＤ６）
第１の再分散値計算部３０２_１は、第１のデータ記憶部３０８_１から
2020165931.tif 000741
を取り出す。次に、第１の再分散値計算部３０２_１は、
2020165931.tif 000742
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０８_４に記憶されている
2020165931.tif 000743
を取出し、
2020165931.tif 000744
が成り立つかを検証する。
【０２１７】
成り立つ場合、第４の不正検知部２０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０２１８】
同様に、第２の再分散値計算部３０２_２は、第２のデータ記憶部３０８_２から
2020165931.tif 000745
を取り出す。次に、第２の再分散値計算部３０２_２は、
2020165931.tif 000746
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０８_４に記憶されている
2020165931.tif 000747
を取出し
2020165931.tif 000748
が成立するかを検証する。
【０２１９】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０２２０】
さらに同様に、第３の再分散値計算部３０２_３は、第３のデータ記憶部３０８_３から
2020165931.tif 000749
を取り出す。次に、第３の再分散値計算部３０２_３は、
2020165931.tif 000750
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０８_４に記憶されている
2020165931.tif 000751
を取出し、
2020165931.tif 000752
が成立するかを検証する。
【０２２１】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０２２２】
なお、大量の型変換処理を並列して行う場合、
2020165931.tif 000753
については、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０２２３】
（ステップＤ７）
各ｉ番目の不正検知部３０４_ｉは、上記ステップＤ５の
2020165931.tif 000754
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置３００_１、３００_２、３００_３、３００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置３００_１、３００_２、３００_３、３００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＤ７は上記ステップＤ６と並列に実行することが可能である。また、ステップＤ６、Ｄ７はループごとではなく、ｊ＝ｎ−１のときに、ｎ回のループ分を並列に実行することが可能である。
【０２２４】
（ステップＤ８）
上記ステップＢ８と同じ処理が行われる。
【０２２５】
以上、説明した第３の実施形態においては、第１の実施形態および第２の実施形態における効果と同じ効果を奏する。ただし、第１の実施形態における第１の効果および第２の実施形態における第１の効果に関して、第３の実施形態の方が通信コストの点で効率が良い。第３の実施形態では、第１乃至第２の実施形態と同様、ビット分解に関して
2020165931.tif 000755
の計算を２回、環合成に関して
2020165931.tif 000756
の計算によって実行できる。第３の実施形態と第１乃至第２の実施形態とで異なる点は、加算器計算前の再分散が効率よく行われている点である。リップルキャリー型のｎビット加算器を用いて不正検知に関する処理を並列に行った場合、第３の実施形態では、ビット分解の通信コストとして、１３ｎ−１０ビット・ｎ＋１ラウンドを要する。環合成の通信コストとして、１３ｎ−１３ビット・２ｎ−２ラウンドを要する。これにより、第３の実施形態の方が第１及び第２の実施形態よりも通信コストの点で効率が良い。なお、本願開示の実施はリップルキャリー型のｎビット加算器に限定されない。キャリールックアヘッド型やパラレルプリフィックス型などのｎビット加算器を用いても良い。
【０２２６】
［第４の実施形態］
図１３〜図１５を参照して、第４の実施形態に係る型変換処理システムについて説明する。
【０２２７】
図１３は、第４の実施形態による型変換処理システムの機能構成例を示すブロック図である。第４の実施形態に係る型変換処理システムは、上述した第１乃至第３の実施形態に係る型変換処理システムの変形例である。
【０２２８】
図１３を参照すると、第４の実施形態による型変換処理システムは、後述する図１４で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第４の実施形態による型変換処理システムにおいて、サーバ装置４００_１、４００_２、４００_３、４００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図１４は、第ｉのサーバ装置４００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０２２９】
図１４に示すように、第ｉのサーバ装置４００_ｉは、第ｉの再分散値計算部４０２_ｉと、第ｉのシェア構成部４０３_ｉと、第ｉの不正検知部４０４_ｉと、第ｉの算術演算部４０５_ｉと、第ｉの論理演算部４０６_ｉと、第ｉの基本演算シード記憶部４０７_ｉと、第ｉのデータ記憶部４０８_ｉと、を含む。なお、第ｉの再分散値計算部４０２_ｉと、第ｉのシェア構成部４０３_ｉと、第ｉの不正検知部４０４_ｉと、第ｉの算術演算部４０５_ｉと、第ｉの論理演算部４０６_ｉと、第ｉの基本演算シード記憶部４０７_ｉと、第ｉのデータ記憶部４０８_ｉとは、それぞれ接続されている。
【０２３０】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置４００_１〜４００_４の内のいずれかの装置が入力した値
2020165931.tif 000757
、あるいは第１乃至第４のデータ記憶部４０８_１〜４０８_４に記憶されたシェア
2020165931.tif 000758
、あるいは第１乃至第４のサーバ装置４００_１〜４００_４ではない外部から入力されたシェア
2020165931.tif 000759
に対し、その入力や計算過程の値から
2020165931.tif 000760
の値を知られることなく、
2020165931.tif 000761
を計算し、第１乃至第４のデータ記憶部４０８_１〜４０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置４００_１〜４００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置４００_１〜４００_４ではない外部にシェアが送信され、シェアが復元されてもよい。
【０２３１】
また、このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置４００_１〜４００_４の内のいずれかの装置が入力した値
2020165931.tif 000762
、あるいは第１乃至第４のデータ記憶部４０８_１〜４０８_４に記憶されたシェア
2020165931.tif 000763
、あるいは第１乃至第４のサーバ装置４００_１〜４００_４ではない外部から入力されたシェア
2020165931.tif 000764
に対し、その入力や計算過程の値から
2020165931.tif 000765
の値を知られることなく、
2020165931.tif 000766
を計算し、第１乃至第４のデータ記憶部４０８_１〜４０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置４００_１〜４００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置４００_１〜４００_４ではない外部にシェアが送信され、シェアが復元されてもよい。
【０２３２】
次に、第４の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置４００_１〜４００_４の動作について、詳細に説明する。図１５は、第１乃至第４のサーバ装置４００_１〜４００_４の環合成に関する動作例を示すフローチャートである。ビット分解については、第３の実施例と同様に実施可能なため、詳細な説明を割愛する。
【０２３３】
図１５に示す環合成に関するフローチャートを説明する。
【０２３４】
（ステップＤ´１）
各基本演算シード記憶部４０７_１、４０７_２、４０７_３、４０７_４は、それぞれ
2020165931.tif 000767
、
2020165931.tif 000768
、
2020165931.tif 000769
、
2020165931.tif 000770
を記憶する。
【０２３５】
また、各サーバ装置４００_１〜４００_４は疑似ランダム関数
2020165931.tif 000771
を共有する。なお、
2020165931.tif 000772
とし、疑似ランダム関数
2020165931.tif 000773
とする。また、各データ記憶部４０８_１〜４０８_４に、
2020165931.tif 000774
、
2020165931.tif 000775
、
2020165931.tif 000776
、
2020165931.tif 000777
を記憶する。さらに、各データ記憶部４０８_１〜４０８_４に、ループカウンタｊ（＝１）を記憶する。なお、
2020165931.tif 000778
とし、
2020165931.tif 000779
、
2020165931.tif 000780
、
2020165931.tif 000781
、
2020165931.tif 000782
とする。
【０２３６】
また、
2020165931.tif 000783
に関して、サーバ装置４００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165931.tif 000784
の出力を計算できず、他の三台の参加者は
2020165931.tif 000785
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000786
の扱いは特に制限されない。本書での
2020165931.tif 000787
はあくまでも一例である。
【０２３７】
（ステップＤ´２）
各サーバ装置４００_ｉは、以下に示す式のように
2020165931.tif 000788
の値を定める。
2020165931.tif 000789
2020165931.tif 000790
【０２３８】
各データ記憶部４０８_１〜４０８_４は、それぞれ
2020165931.tif 000791
、
2020165931.tif 000792
、
2020165931.tif 000793
、
2020165931.tif 000794
、
2020165931.tif 000795
を記憶する。
【０２３９】
第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３はそれぞれ、第１の基本演算シード記憶部４０７_１、第２の基本演算シード記憶部４０７_２、第３の基本演算シード記憶部４０７_３より、
2020165931.tif 000796
を取得する。次に、第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３は
2020165931.tif 000797
を生成する。
【０２４０】
そして、第１の再分散値計算部４０２_１は、
2020165931.tif 000798
を第１のシェア構成部４０３_１に送信する。第３の再分散値計算部４０２_３は
2020165931.tif 000799
を、第３のシェア構成部４０３_３に送信する。第２の再分散値計算部４０２_２は、第２のデータ記憶部４０８_２から
2020165931.tif 000800
を取出し、
2020165931.tif 000801
を、第４のシェア構成部４０３_４に送信する。
【０２４１】
同様に、第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３は
2020165931.tif 000802
を生成する。第２の再分散値計算部４０２_２は、
2020165931.tif 000803
を、第２のシェア構成部４０３_２に送信する。第１の再分散値計算部４０２_３は、
2020165931.tif 000804
を、第１のシェア構成部４０３_１に送信する。また、第３の再分散値計算部４０２_３は、第３のデータ記憶部４０８_３から
2020165931.tif 000805
を取出し、
2020165931.tif 000806
を、第４のシェア構成部４０３_４に送信する。
【０２４２】
さらに同様に、第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３は
2020165931.tif 000807
を生成する。第３の再分散値計算部４０２_３は、
2020165931.tif 000808
を第３のシェア構成部４０３_３に送信する。第２の再分散値計算部４０２_２は、
2020165931.tif 000809
を、第２のシェア構成部４０３_２に送信する。また、第１の再分散値計算部４０２_１は、第１のデータ記憶部４０８_１から
2020165931.tif 000810
を取出し、
2020165931.tif 000811
を、第４のシェア構成部４０３_４に送信する。
【０２４３】
ここで、
2020165931.tif 000812
である。
2020165931.tif 000813
は、たとえば、カウンタであり、各サーバ装置４００_１〜４００_４の間で共有している。
【０２４４】
（ステップＤ´３）
各シェア構成部４０３_１、４０３_２、４０３_３、４０３_４は上記ステップＤ´２で送信された値と、各ｉ番目のデータ記憶部４０８_ｉに記憶された
2020165931.tif 000814
を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000815
2020165931.tif 000816
2020165931.tif 000817
2020165931.tif 000818
2020165931.tif 000819
2020165931.tif 000820
2020165931.tif 000821
2020165931.tif 000822
2020165931.tif 000823
2020165931.tif 000824
2020165931.tif 000825
2020165931.tif 000826
2020165931.tif 000827
、
2020165931.tif 000828
、
2020165931.tif 000829
が各ｉ番目のデータ記憶部４０８_ｉに記憶される。
【０２４５】
（ステップＤ´４）
第１の再分散値計算部４０２_１は、第１のデータ記憶部４０８_１から
2020165931.tif 000830
を取り出す。次に、第１の再分散値計算部４０２_１は、
2020165931.tif 000831
を、第４の不正検知部４０４_４に送信する。第４の不正検知部４０４_４は、第４のデータ記憶部４０８_４に記憶されている
2020165931.tif 000832
を取出し、
2020165931.tif 000833
が成り立つかを検証する。
【０２４６】
成り立つ場合、第４の不正検知部４０４_４は、successの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部４０４_４は、abortの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、プロトコルを中断する。
【０２４７】
同様に、第２の再分散値計算部４０２_２は、第２のデータ記憶部４０８_２から
2020165931.tif 000834
を取り出す。次に、第２の再分散値計算部４０２_２は、
2020165931.tif 000835
を、第４の不正検知部４０４_４に送信する。第４の不正検知部４０４_４は、第４のデータ記憶部４０８_４に記憶されている
2020165931.tif 000836
を取出し
2020165931.tif 000837
が成立するかを検証する。
【０２４８】
成立した場合、第４の不正検知部４０４_４は、successの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部４０４_４は、abortの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、プロトコルを中断する。
【０２４９】
さらに同様に、第３の再分散値計算部４０２_３は、第３のデータ記憶部４０８_３から
2020165931.tif 000838
を取り出す。次に、第３の再分散値計算部４０２_３は、
2020165931.tif 000839
を、第４の不正検知部４０４_４に送信する。第４の不正検知部４０４_４は、第４のデータ記憶部４０８_４に記憶されている
2020165931.tif 000840
を取出し、
2020165931.tif 000841
が成立するかを検証する。
【０２５０】
成立した場合、第４の不正検知部４０４_４は、successの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第４の不正検知部４０４_４は、abortの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、プロトコルを中断する。
【０２５１】
なお、大量の型変換処理を並列して行う場合、
2020165931.tif 000842
については、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０２５２】
（ステップＤ´５）
各サーバ装置４００_ｉは、各データ記憶部４０８_ｉより、ループカウンタｊをとりだす。各サーバ装置４００_ｉは、ｊ＜ｎであればステップＤ´６〜Ｄ´１０を実行する。各サーバ装置４００_ｉは、ｊ＝ｎであれば、ステップＤ´１１を実行する。
【０２５３】
（ステップＤ´６）
上記ステップＢ´６と同じ処理なので説明を割愛する。
【０２５４】
（ステップＤ´７）
第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３はそれぞれ、第１の基本演算シード記憶部４０７_１、第２の基本演算シード記憶部４０７_２、第３の基本演算シード記憶部４０７_３より、
2020165931.tif 000843
を取得する。次に、第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３は
2020165931.tif 000844
を生成する。
【０２５５】
そして、第１の再分散値計算部４０２_１は、
2020165931.tif 000845
を第１のシェア構成部４０３_１に送信する。第３の再分散値計算部４０２_２は
2020165931.tif 000846
を、第３のシェア構成部４０３_４に送信する。第２の再分散値計算部４０２_２は、第２のデータ記憶部４０８_２から
2020165931.tif 000847
を取出し、
2020165931.tif 000848
を、第４のシェア構成部４０３_４に送信する。
【０２５６】
同様に、第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３は
2020165931.tif 000849
を生成する。第２の再分散値計算部４０２_２は、
2020165931.tif 000850
を、第２のシェア構成部４０３_２に送信する。第１の再分散値計算部４０２_３は、
2020165931.tif 000851
を、第１のシェア構成部４０３_１に送信する。また、第３の再分散値計算部４０２_３は、第３のデータ記憶部４０８_３から
2020165931.tif 000852
を取出し、
2020165931.tif 000853
を、第４のシェア構成部４０３_４に送信する。
【０２５７】
さらに同様に、第１の再分散値計算部４０２_１と第２の再分散値計算部４０２_２と第３の再分散値計算部４０２_３は
2020165931.tif 000854
2020165931.tif 000855
を生成する。第３の再分散値計算部４０２_３は、
2020165931.tif 000856
を第３のシェア構成部４０３_３に送信する。第２の再分散値計算部４０２_２は、
2020165931.tif 000857
を、第２のシェア構成部４０３_２に送信する。また、第１の再分散値計算部４０２_１は、第１のデータ記憶部４０８_１から
2020165931.tif 000858
を取出し、
2020165931.tif 000859
を、第４のシェア構成部４０３_４に送信する。
【０２５８】
ここで、
2020165931.tif 000860
である。
2020165931.tif 000861
は、たとえば、カウンタであり、各サーバ装置４００_１〜４００_４の間で共有している。
【０２５９】
また、論理演算部４０６_ｉ（ｉ＝１、２、３、４）は、
2020165931.tif 000862
、
2020165931.tif 000863
、
2020165931.tif 000864
、
2020165931.tif 000865
および
2020165931.tif 000866
を入力に取り、
2020165931.tif 000867
を通信を伴って計算することで、
2020165931.tif 000868
を得る。論理演算部４０６_ｉ（ｉ＝１、２、３、４）は、データ記憶部４０８_ｉ（ｉ＝１、２、３、４）に
2020165931.tif 000869
を記憶する。
【０２６０】
（ステップＤ´８）
各シェア構成部４０３_１、４０３_２、４０３_３、４０３_４は上記ステップＤ´７で送信された値と、各ｉ番目のデータ記憶部４０８_ｉに記憶された
2020165931.tif 000870
を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 000871
2020165931.tif 000872
2020165931.tif 000873
2020165931.tif 000874
2020165931.tif 000875
2020165931.tif 000876
2020165931.tif 000877
2020165931.tif 000878
2020165931.tif 000879
2020165931.tif 000880
2020165931.tif 000881
2020165931.tif 000882
2020165931.tif 000883
、
2020165931.tif 000884
、
2020165931.tif 000885
が各ｉ番目のデータ記憶部４０８_ｉに記憶される。また、データ記憶部４０８_ｉはループカウンタ
2020165931.tif 000886
を取り出し、ｊ＝ｊ＋１として値を更新する。
【０２６１】
（ステップＤ´９）
第１の再分散値計算部４０２_１は、第１のデータ記憶部４０８_１から
2020165931.tif 000887
を取り出す。次に、第１の再分散値計算部３０２_１は、
2020165931.tif 000888
を、第４の不正検知部４０４_４に送信する。第４の不正検知部４０４_４は、第４のデータ記憶部４０８_４に記憶されている
2020165931.tif 000889
を取出し、
2020165931.tif 000890
が成り立つかを検証する。
【０２６２】
成り立つ場合、第４の不正検知部４０４_４は、successの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部４０４_４は、abortの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、プロトコルを中断する。
【０２６３】
同様に、第２の再分散値計算部４０２_２は、第２のデータ記憶部４０８_２から
2020165931.tif 000891
を取り出す。次に、第２の再分散値計算部４０２_２は、
2020165931.tif 000892
を、第４の不正検知部４０４_４に送信する。第４の不正検知部４０４_４は、第４のデータ記憶部４０８_４に記憶されている
2020165931.tif 000893
を取出し
2020165931.tif 000894
が成立するかを検証する。
【０２６４】
成立した場合、第４の不正検知部４０４_４は、successの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部４０４_４は、abortの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、プロトコルを中断する。
【０２６５】
さらに同様に、第３の再分散値計算部４０２_３は、第３のデータ記憶部４０８_３から
2020165931.tif 000895
を取り出す。次に、第３の再分散値計算部４０２_３は、
2020165931.tif 000896
を、第４の不正検知部４０４_４に送信する。第４の不正検知部４０４_４は、第４のデータ記憶部４０８_４に記憶されている
2020165931.tif 000897
を取出し、
2020165931.tif 000898
が成立するかを検証する。
【０２６６】
成立した場合、第４の不正検知部４０４_４は、successの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第４の不正検知部４０４_４は、abortの文字列を各サーバ装置４００_１、４００_２、４００_３、４００_４にブロードキャストし、プロトコルを中断する。
【０２６７】
なお、大量の型変換処理を並列して行う場合、
2020165931.tif 000899
については、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。なお、ステップＤ´９は、ループごとではなく、ｊ＝ｎ−１のときに全ループ分を並列に実行しても良い。また、ステップＤ´９は、上記ステップＤ´４と並列に実行することも可能である。
【０２６８】
（ステップＤ´１０）
各ｉ番目の不正検知部４０４_ｉは、上記ステップＤ´７の
2020165931.tif 000900
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置４００_１、４００_２、４００_３、４００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置４００_１、４００_２、４００_３、４００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＤ´１０は上記ステップＤ´４、Ｄ´９と並列に実行することが可能である。また、ステップＤ´１０はループごとではなく、ｊ＝ｎ−１のときに、全ループ分を並列に実行することが可能である。
【０２６９】
（ステップＤ´１１）
上記ステップＢ´１１と同じ処理なので説明を割愛する。
【０２７０】
以上、説明した第４の実施形態においては、第１乃至第３の実施形態における効果と同じ効果を奏する。ただし、第３の実施形態における第１の効果に関して、第４の実施形態の方が環合成における通信コストの点で効率が良い。キャリー計算処理
2020165931.tif 000901
を分割して考え、シェアの再分散とキャリー計算における通信を伴う処理を並列して行うことで、通信ラウンドの削減を実現している。このため、第４の実施形態における環合成の通信コストは、（１３ｎ−１３）ビット・ｎ−１ラウンドとなる。
【０２７１】
［第５の実施形態］
図１６〜図１８を参照して、第５の実施形態に係る型変換処理システムについて説明する。第５の実施形態に係る型変換処理システムは、上述した第１乃至第４の実施形態に係る型変換処理システムの変形例である。
【０２７２】
図１６は、第５の実施形態による型変換処理システムの機能構成例を示すブロック図である。図１６を参照すると、第５の実施形態による型変換処理システムは、後述する図１７で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第５の実施形態による型変換処理システムにおいて、サーバ装置５００_１、５００_２、５００_３、５００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図１７は、第ｉのサーバ装置５００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０２７３】
図１７に示すように、第ｉのサーバ装置５００_ｉは、第ｉのマスク値計算部５０１_ｉと、第ｉの再分散値計算部５０２_ｉと、第ｉのシェア構成部５０３_ｉと、第ｉの不正検知部５０４_ｉと、第ｉの算術演算部５０５_ｉと、第ｉの論理演算部５０６_ｉと、第ｉの基本演算シード記憶部５０７_ｉと、第ｉのデータ記憶部５０８_ｉと、を含む。なお、第ｉのマスク値計算部５０１_ｉと、第ｉの再分散値計算部５０２_ｉと、第ｉのシェア構成部５０３_ｉと、第ｉの不正検知部５０４_ｉと、第ｉの算術演算部５０５_ｉと、第ｉの論理演算部５０６_ｉと、第ｉの基本演算シード記憶部５０７_ｉと、第ｉのデータ記憶部５０８_ｉとは、それぞれ接続されている。
【０２７４】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置５００_１〜５００_４の内のいずれかの装置が入力した値
2020165931.tif 000902
、あるいは第１乃至第４のデータ記憶部５０８_１〜５０８_４に記憶されたシェア
2020165931.tif 000903
、あるいは第１乃至第４のサーバ装置５００_１〜５００_４ではない外部から入力されたシェア
2020165931.tif 000904
に対し、その入力や計算過程の値から
2020165931.tif 000905
の値を知られることなく、
2020165931.tif 000906
を計算し、第１乃至第４のデータ記憶部５０８_１〜５０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置５００_１〜５００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置５００_１〜５００_４ではない外部にシェアが送信され、復元されてもよい。
【０２７５】
次に、第５の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置５００_１〜５００_４の動作について、詳細に説明する。図１７は、第１乃至第４のサーバ装置５００_１〜５００_４のビット分解に関する動作例を示すフローチャートである。環合成については、たとえば、第３又は第４の実施形態における環合成と同様とすることができるので、説明を割愛する。
【０２７６】
以下、図１７に示すビット分解に関するフローチャートを説明する。
【０２７７】
（ステップＥ１）
各基本演算シード記憶部５０７_１、５０７_２、５０７_３、５０７_４は、それぞれ
2020165931.tif 000907
、
2020165931.tif 000908
、
2020165931.tif 000909
、
2020165931.tif 000910
を記憶する。
【０２７８】
また、各サーバ装置５００_１〜５００_４は疑似ランダム関数
2020165931.tif 000911
を共有する。なお、
2020165931.tif 000912
とし、疑似ランダム関数
2020165931.tif 000913
とする。また、各データ記憶部５０８_１〜５０８_４に、それぞれ
2020165931.tif 000914
、
2020165931.tif 000915
、
2020165931.tif 000916
、
2020165931.tif 000917
を記憶する。ここで、
2020165931.tif 000918
を文字列連結演算子とする。なお、
2020165931.tif 000919
に関して、サーバ装置５００_ｉ（ｉ＝１、２、３、４）の内、ある一台のサーバ装置は
2020165931.tif 000920
の出力を計算できず、他の三台のサーバ装置は
2020165931.tif 000921
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 000922
の扱いは特に制限されない。本書での
2020165931.tif 000923
はあくまでも一例である。
【０２７９】
（ステップＥ２）
第１、第２、第３のマスク値計算部５０１_１、５０１_２、５０１_３は
2020165931.tif 000924
を計算し、第１、第２、第３のデータ記憶部５０９_１、５０９_２、５０９_３に
2020165931.tif 000925
を記憶する。第２のマスク値計算部５０１_２は、データ記憶部５０８_２からシェア
2020165931.tif 000926
を取り出す。第２のマスク値計算部５０１_２は、
2020165931.tif 000927
を生成し、
2020165931.tif 000928
を第４のサーバ装置５００_４に送信する。第４のサーバ装置５００_４は、第４のデータ記憶部５０８_４に
2020165931.tif 000929
を記憶する。
【０２８０】
ここで、
2020165931.tif 000930
である。
2020165931.tif 000931
は、たとえば、カウンタであり、各サーバ装置５００_１〜５００_４の間で共有している。
【０２８１】
このように、第ｉのマスク値計算部５０１_ｉは、シェア（例えば、上記の例ではｘ２）をマスクするためのマスク値（例えば、上記の例ではｒ）を計算する。当該計算されたマスク値によりマスクされたシェア（上記の例では、ｙ＝ｘ２＋ｒ）が他のサーバ装置に送信される。
【０２８２】
（ステップＥ３）
各シェア構成部５０３_１、５０３_２、５０３_３、５０３_４は各データ記憶部５０８_１、５０８_２、５０８_３、５０８_４からそれぞれ、
2020165931.tif 000932
、
2020165931.tif 000933
、
2020165931.tif 000934
、
2020165931.tif 000935
を取り出し、以下の１６の式によりシェアを構成する。
2020165931.tif 000936
2020165931.tif 000937
2020165931.tif 000938
2020165931.tif 000939
2020165931.tif 000940
2020165931.tif 000941
2020165931.tif 000942
2020165931.tif 000943
2020165931.tif 000944
2020165931.tif 000945
2020165931.tif 000946
2020165931.tif 000947
2020165931.tif 000948
2020165931.tif 000949
2020165931.tif 000950
2020165931.tif 000951
ここで、
2020165931.tif 000952
に対し、
2020165931.tif 000953
は
2020165931.tif 000954
のｊ番目のビット（ｊ＝０、．．．、ｎ−１）を意味する。
2020165931.tif 000955
、
2020165931.tif 000956
、
2020165931.tif 000957
、
2020165931.tif 000958
は各ｉ番目のデータ記憶部５０８_ｉに記憶される。このように、第ｉのシェア構成部５０３_ｉは、送信されたマスク値を用いて型変換用のシェアを構成する。
【０２８３】
（ステップＥ４）
各ｉ番目の論理演算部５０６_ｉで通信することで、ｎビット加算器処理
2020165931.tif 000959
を以下のように計算する。ここで、
2020165931.tif 000960
とは、たとえば、
2020165931.tif 000961
、
2020165931.tif 000962
を入力とし、
2020165931.tif 000963
を出力する処理のことである。
【０２８４】
2020165931.tif 000964
2020165931.tif 000965
2020165931.tif 000966
ここで、
2020165931.tif 000967
なので、
2020165931.tif 000968
が計算できた。なお、
2020165931.tif 000969
は、
2020165931.tif 000970
、…、
2020165931.tif 000971
のシェア列を意味する。各ｉ番目の論理演算部５０６_ｉは、
2020165931.tif 000972
を各データ記憶部５０８_ｉに記憶する。
【０２８５】
（ステップＥ５）
第１のサーバ装置５００_１は、上記ステップＥ２における第２のサーバ装置５００_２と同様、第１のマスク値計算部５０１_１は、
2020165931.tif 000973
を生成し、
2020165931.tif 000974
を第４のサーバ装置５００_４に送信する。第４のサーバ装置５００_４は、第４のデータ記憶部５０８_４に
2020165931.tif 000975
を記憶する。第４の不正検知部５０４_４は、第４のデータ記憶部５０８_４から
2020165931.tif 000976
を取り出し、
2020165931.tif 000977
が成り立つか、検証する。
【０２８６】
2020165931.tif 000978
が成り立つ場合は、第４の不正検知部５０４_４はsuccessの文字列を各サーバ装置５００_１、５００_２、５００_３にブロードキャストし、次のステップに進む。
2020165931.tif 000979
が成り立たない場合は、第４の不正検知部５０４_４はabortの文字列を各サーバ装置５００_１、５００_２、５００_３にブロードキャストし、プロトコルを中断する。
【０２８７】
なお、大量の型変換処理を並列に行う際に、各ステップＥ５における
2020165931.tif 000980
を連結してハッシュ値
2020165931.tif 000981
を計算し、
2020165931.tif 000982
に対しても連結した値に対するハッシュ値
2020165931.tif 000983
を計算することで、
2020165931.tif 000984
が成り立つか否かの検証を
2020165931.tif 000985
が成り立つか否かの検証と捉えてもよい。このとき、
2020165931.tif 000986
に関する通信量は処理全体の計算量に対し、無視できるものと捉えることができる。
【０２８８】
（ステップＥ６）
各ｉ番目の不正検知部５０４_ｉは、上記ステップＥ４の
2020165931.tif 000987
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置５００_１、５００_２、５００_３、５００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置５００_１、５００_２、５００_３、５００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＥ６は上記ステップＥ５と並列に実行することが可能である。
【０２８９】
以上、説明した第５の実施形態においては、第１乃至第４の実施形態における効果と同じ効果を奏する。なお、ビット分解について、理論的な通信コストとしては第５の実施形態の方が、他の実施形態よりも劣っているが、通信の形態が変化していることに留意されたい。たとえば、第３の実施形態では、ステップＣ２にて、第１のサーバ装置３００_１、第２のサーバ装置３００_２、第３のサーバ装置３００_３から第４のサーバ装置３００_４への通信が生じている。一方、第５の実施形態におけるステップＥ２では、第２のサーバ装置５００_２から、第４のサーバ装置５００_４への通信の発生だけで済む。このように通信の形態が変わるため、通信環境によっては第５の実施形態の方が、効率が良い場合があり得る。
【０２９０】
［第６の実施形態］
図１９〜図２１を参照して、第６の実施形態に係る型変換処理システムについて説明する。図１９は、第６の実施形態による型変換処理システムの機能構成例を示すブロック図である。第６の実施形態に係る型変換処理システムは、上述した第１乃至第５の実施形態に係る型変換処理システムの変形例である。
【０２９１】
図１９を参照すると、第６の実施形態による型変換処理システムは、後述する図２０で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第６の実施形態による型変換処理システムにおいて、サーバ装置６００_１、６００_２、６００_３、６００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図２０は、第ｉのサーバ装置６００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０２９２】
図２０に示すように、第ｉのサーバ装置６００_ｉは、第ｉのマスク値計算部６０１_ｉと、第ｉの再分散値計算部６０２_ｉと、第ｉのシェア構成部６０３_ｉと、第ｉの不正検知部６０４_ｉと、第ｉの算術演算部６０５_ｉと、第ｉの論理演算部６０６_ｉと、第ｉの基本演算シード記憶部６０７_ｉと、第ｉのデータ記憶部６０８_ｉと、を含む。なお、第ｉのマスク値計算部６０１_ｉと、第ｉの再分散値計算部６０２_ｉと、第ｉのシェア構成部６０３_ｉと、第ｉの不正検知部６０４_ｉと、第ｉの算術演算部６０５_ｉと、第ｉの論理演算部６０６_ｉと、第ｉの基本演算シード記憶部６０７_ｉと、第ｉのデータ記憶部６０８_ｉとは、それぞれ接続されている。
【０２９３】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置６００_１〜６００_４の内のいずれかの装置が入力した値
2020165931.tif 000988
、あるいは第１乃至第４のデータ記憶部６０８_１〜６０８_４に記憶されたシェア
2020165931.tif 000989
、あるいは第１乃至第４のサーバ装置６００_１〜６００_４ではない外部から入力されたシェア
2020165931.tif 000990
に対し、その入力や計算過程の値から
2020165931.tif 000991
の値を知られることなく、
2020165931.tif 000992
を計算し、第１乃至第４のデータ記憶部６０８_１〜６０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置６００_１〜６００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置６００_１〜６００_４ではない外部にシェアが送信され、復元されてもよい。
【０２９４】
また、このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置６００_１〜６００_４の内のいずれかの装置が入力した値
2020165931.tif 000993
、あるいは第１乃至第４のデータ記憶部６０８_１〜６０８_４に記憶されたシェア
2020165931.tif 000994
、あるいは第１乃至第４のサーバ装置６００_１〜６００_４ではない外部から入力されたシェア
2020165931.tif 000995
に対し、その入力や計算過程の値から
2020165931.tif 000996
の値を知られることなく、
2020165931.tif 000997
を計算し、第１乃至第４のデータ記憶部６０８_１〜６０８_４に記憶する。上記計算結果のシェアは、第１乃至第４のサーバ装置６００_１〜６００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置６００_１〜６００_４ではない外部にシェアが送信され、復元されてもよい。
【０２９５】
次に、第６の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置６００_１〜６００_４の動作について、詳細に説明する。図２０は、第１乃至第４のサーバ装置６００_１〜６００_４のビット分解に関する動作例を示すフローチャートである。環合成については、たとえば、第３又は第４の実施形態における環合成と同様とすることができるので、説明を割愛する。
【０２９６】
以下に図２０に示すビット分解に関するフローチャートを説明する。
【０２９７】
（ステップＦ１）
各基本演算シード記憶部６０７_１、６０７_２、６０７_３、６０７_４は、それぞれ
2020165931.tif 000998
、
2020165931.tif 000999
、
2020165931.tif 001000
、
2020165931.tif 001001
を記憶する。
【０２９８】
また、各サーバ装置６００_１〜６００_４は疑似ランダム関数
2020165931.tif 001002
を共有する。なお、
2020165931.tif 001003
とし、疑似ランダム関数
2020165931.tif 001004
とする。また、各データ記憶部６０８_１〜６０８_４に、それぞれ
2020165931.tif 001005
、
2020165931.tif 001006
、
2020165931.tif 001007
、
2020165931.tif 001008
を記憶する。なお、
2020165931.tif 001009
に関して、サーバ装置６００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165931.tif 001010
の出力を計算できず、他の三台の参加者は
2020165931.tif 001011
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 001012
の扱いは特に制限されない。本書での
2020165931.tif 001013
はあくまでも一例である。
【０２９９】
（ステップＦ２）
第１、第２、第３のマスク値計算部６０１_１、６０１_２、６０１_３は
2020165931.tif 001014
を計算し、第１、第２、第３のデータ記憶部６０８_１、６０８_２、６０８_３に
2020165931.tif 001015
を記憶する。第２のマスク値計算部６０１_２は、データ記憶部６０８_２からシェア
2020165931.tif 001016
を取り出す。第２のマスク値計算部６０１_２は、
2020165931.tif 001017
を生成し、
2020165931.tif 001018
を第４のサーバ装置６００_４に送信する。第４のサーバ装置６００_４は、第４のデータ記憶部６０８_４に
2020165931.tif 001019
を記憶する。
【０３００】
次に、第１の再分散値計算部６０２_１と第２の再分散値計算部６０２_２と第３の再分散値計算部６０２_３はそれぞれ、第１の基本演算シード記憶部６０７_１、第２の基本演算シード記憶部６０７_２、第３の基本演算シード記憶部６０７_３より、
2020165931.tif 001020
を取得する。そして、第１の再分散値計算部６０２_１と第２の再分散値計算部６０２_２と第３の再分散値計算部６０２_３は
2020165931.tif 001021
を生成する。さらに、第３の再分散値計算部６０２_３は、
2020165931.tif 001022
を第３のデータ記憶部６０８_３に記憶する。第１の再分散値計算部６０２_１は、
2020165931.tif 001023
を、第１のシェア構成部６０３_１に送信する。また、第２の再分散値計算部６０２_２は、第２のデータ記憶部６０８_２から
2020165931.tif 001024
を取り出し、
2020165931.tif 001025
を、第４のシェア構成部６０３_４に送信する。
【０３０１】
ここで、
2020165931.tif 001026
である。
2020165931.tif 001027
は、たとえば、カウンタであり、各サーバ装置６００_１〜６００_４の間で共有している。
【０３０２】
（ステップＦ３）
各シェア構成部６０３_１、６０３_２、６０３_３、６０３_４は、各データ記憶部６０８_１、６０８_２、６０８_３、６０８_４からそれぞれ、
2020165931.tif 001028
、
2020165931.tif 001029
、
2020165931.tif 001030
、
2020165931.tif 001031
を取り出す。さらに上記ステップＦ２で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165931.tif 001032
2020165931.tif 001033
2020165931.tif 001034
2020165931.tif 001035
2020165931.tif 001036
2020165931.tif 001037
2020165931.tif 001038
2020165931.tif 001039
2020165931.tif 001040
2020165931.tif 001041
2020165931.tif 001042
2020165931.tif 001043
ここで、
2020165931.tif 001044
に対し、
2020165931.tif 001045
は
2020165931.tif 001046
のｊ番目のビット（ｊ＝０、．．．、ｎ-１）を意味する。
2020165931.tif 001047
、
2020165931.tif 001048
、
2020165931.tif 001049
が各ｉ番目のデータ記憶部６０８_ｉに記憶される。
【０３０３】
（ステップＦ４）
各ｉ番目の論理演算部６０６_ｉで通信することで、ｎビット加算器処理
2020165931.tif 001050
を以下のように計算する。ここで、
2020165931.tif 001051
とは、たとえば、
2020165931.tif 001052
、
2020165931.tif 001053
を入力とし、
2020165931.tif 001054
を出力する処理のことである。
2020165931.tif 001055
2020165931.tif 001056
ここで、
2020165931.tif 001057
なので、
2020165931.tif 001058
が計算できた。なお、
2020165931.tif 001059
は、
2020165931.tif 001060
、…、
2020165931.tif 001061
のシェア列を意味する。各ｉ番目の論理演算部６０６_ｉは、
2020165931.tif 001062
を各データ記憶部６０８_ｉに記憶する。
【０３０４】
（ステップＦ５）
第１のサーバ装置６００_１は、上記ステップＦ２における第２のサーバ装置６００_２と同様、第１のマスク値計算部６０１_１は、
2020165931.tif 001063
を生成し、
2020165931.tif 001064
を第４のサーバ装置６００_４に送信する。第４のサーバ装置６００_４は、第４のデータ記憶部６０８_４に
2020165931.tif 001065
を記憶する。第４の不正検知部６０４_４は、第４のデータ記憶部６０８_４から
2020165931.tif 001066
を取り出し、
2020165931.tif 001067
が成り立つか、検証する。
【０３０５】
2020165931.tif 001068
が成り立つ場合は、第４の不正検知部６０４_４はsuccessの文字列を各サーバ装置６００_１、６００_２、６００_３にブロードキャストし、次のステップに進む。
2020165931.tif 001069
が成り立たない場合は、第４の不正検知部６０４_４はabortの文字列を各サーバ装置６００_１、６００_２、６００_３にブロードキャストし、プロトコルを中断する。
【０３０６】
第２の再分散値計算部６０２_２は、
2020165931.tif 001070
を第２のデータ記憶部６０８_２から取り出す。次に、第２の再分散値計算部６０２_２は、
2020165931.tif 001071
を、第４の不正検知部６０４_４に送信する。第４の不正検知部６０４_４は、第４のデータ記憶部６０８_４に記憶されている
2020165931.tif 001072
を取出し、
2020165931.tif 001073
が成立するかを検証する。
【０３０７】
成立した場合、第４の不正検知部６０４_４は、successの文字列を各サーバ装置６００_１、６００_２、６００_３、６００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部６０４_４は、abortの文字列を各サーバ装置６００_１、６００_２、６００_３、６００_４にブロードキャストし、プロトコルを中断する。
【０３０８】
なお、大量の型変換処理を並列して実行する場合、
2020165931.tif 001074
、
2020165931.tif 001075
に関しては、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０３０９】
（ステップＦ６）
各ｉ番目の不正検知部６０４_ｉは、上記ステップＦ４の
2020165931.tif 001076
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置６００_１、６００_２、６００_３、６００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置６００_１、６００_２、６００_３、６００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＦ６は上記ステップＦ５と並列に実行することが可能である。
【０３１０】
以上、説明した第６の実施形態においては、第１乃至第５の実施形態における効果と同じ効果を奏する。また、ビット分解の理論的な通信コストについて、第６の実施形態の方が第１乃至第５の実施形態よりも、効率が良い。第６の実施形態では、第１至第４の実施形態と同様、ビット分解に関して
2020165931.tif 001077
の計算を２回行うことで実現できる。
【０３１１】
第６の実施形態と第１乃至第４の実施形態とで異なる点は、加算器計算前の再分散が効率よく行われている点である。リップルキャリー型のｎビット加算器を用いて不正検知に関する処理を並列に行った場合、第６の実施形態では、ビット分解の通信コストとして、１２ｎ−１０ビット・ｎ＋１ラウンドを要する。これより、第６の実施形態におけるビット分解の方が、第１乃至第５の実施形態におけるビット分解よりも通信コストの点で効率が良い。なお、本願開示の実施はリップルキャリー型のｎビット加算器に限定されない。キャリールックアヘッド型やパラレルプリフィックス型などのｎビット加算器を用いても良い。
【０３１２】
［第７の実施形態］
図２２〜図２４を参照して、第７の実施形態に係る型変換処理システムについて説明する。図２２は、第７の実施形態による型変換処理システムの機能構成例を示すブロック図である。第７の実施形態に係る型変換処理システムは、上述した第１乃至第６の実施形態に係る型変換処理システムの変形例である。
【０３１３】
図２２を参照すると、第７の実施形態による型変換処理システムは、後述する図２３で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第７の実施形態による型変換処理システムにおいて、サーバ装置７００_１、７００_２、７００_３、７００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図２３は、第ｉのサーバ装置７００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０３１４】
図２３に示すように、第ｉのサーバ装置７００_ｉは、第ｉのマスク値計算部７０１_ｉと、第ｉの再分散値計算部７０２_ｉと、第ｉのシェア構成部７０３_ｉと、第ｉの不正検知部７０４_ｉと、第ｉの算術演算部７０５_ｉと、第ｉの論理演算部７０６_ｉと、第ｉの基本演算シード記憶部７０７_ｉと、第ｉのデータ記憶部７０８_ｉと、を含む。なお、第ｉのマスク値計算部７０１_ｉと、第ｉの再分散値計算部７０２_ｉと、第ｉのシェア構成部７０３_ｉと、第ｉの不正検知部７０４_ｉと、第ｉの算術演算部７０５_ｉと、第ｉの論理演算部７０６_ｉと、第ｉの基本演算シード記憶部７０７_ｉと、第ｉのデータ記憶部７０８_ｉとは、それぞれ接続されている。
【０３１５】
このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置７００_１〜７００_４の内のいずれかの装置が入力した値
2020165931.tif 001078
、あるいは第１乃至第４のデータ記憶部７０８_１〜７０８_４に記憶されたシェア
2020165931.tif 001079
、あるいは第１乃至第４のサーバ装置７００_１〜７００_４ではない外部から入力されたシェア
2020165931.tif 001080
に対し、その入力や計算過程の値から
2020165931.tif 001081
の値を知られることなく、
2020165931.tif 001082
を計算し、第１乃至第４のデータ記憶部７０８_１〜７０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置７００_１〜７００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置７００_１〜７００_４ではない外部にシェアが送信され、復元されてもよい。
【０３１６】
また、このような構成の型変換処理システムにおいては、第１乃至第４のサーバ装置７００_１〜７００_４の内のいずれかの装置が入力した値
2020165931.tif 001083
、あるいは第１乃至第４のデータ記憶部７０８_１〜７０８_４に記憶されたシェア
2020165931.tif 001084
、あるいは第１乃至第４のサーバ装置７００_１〜７００_４ではない外部から入力されたシェア
2020165931.tif 001085
に対し、その入力や計算過程の値から
2020165931.tif 001086
の値を知られることなく、
2020165931.tif 001087
を計算し、第１乃至第４のデータ記憶部７０８_１〜７０８_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置７００_１〜７００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置７００_１〜７００_４ではない外部にシェアが送信され、復元されてもよい。
【０３１７】
次に、第７の実施形態における型変換処理システムおよび第１乃至第４のサーバ装置７００_１〜７００_４の動作について、詳細に説明する。図２４は、第１乃至第４のサーバ装置７００_１〜７００_４のビット分解に関する動作例を示すフローチャートである。環合成については、たとえば、第３又は第４の実施形態における環合成と同様とすることができるので、説明を割愛する。
【０３１８】
以下、図２４に示すビット分解に関するフローチャートを説明する。
【０３１９】
（ステップＧ１）
各基本演算シード記憶部７０７_１、７０７_２、７０７_３、７０７_４は、それぞれ
2020165931.tif 001088
、
2020165931.tif 001089
、
2020165931.tif 001090
、
2020165931.tif 001091
を記憶する。
【０３２０】
また、各サーバ装置７００_１〜７００_４は疑似ランダム関数
2020165931.tif 001092
を共有する。なお、
2020165931.tif 001093
とし、疑似ランダム関数
2020165931.tif 001094
とする。また、各データ記憶部７０８_１〜７０８_４に、それぞれ
2020165931.tif 001095
、
2020165931.tif 001096
、
2020165931.tif 001097
、
2020165931.tif 001098
を記憶する。なお、
2020165931.tif 001099
に関して、サーバ装置７００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165931.tif 001100
の出力を計算できず、他の三台の参加者は
2020165931.tif 001101
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165931.tif 001102
の扱いは特に制限されない。本書での
2020165931.tif 001103
はあくまでも一例である。
【０３２１】
（ステップＧ２）
第１、第２、第３のマスク値計算部７０１_１、７０１_２、７０１_３は
2020165931.tif 001104
を計算し、第１、第２、第３のデータ記憶部７０８_１、７０８_２、７０８_３に
2020165931.tif 001105
を記憶する。第２のマスク値計算部７０１_２は、データ記憶部７０８_２からシェア
2020165931.tif 001106
を取り出す。第２のマスク値計算部７０１_２は、
2020165931.tif 001107
を生成し、
2020165931.tif 001108
を第４のサーバ装置７００_４に送信する。第４のサーバ装置７００_４は、第４のデータ記憶部７０８_４に
2020165931.tif 001109
を記憶する。
【０３２２】
次に、第１の再分散値計算部７０２_１と第２の再分散値計算部７０２_２と第３の再分散値計算部７０２_３はそれぞれ、第１の基本演算シード記憶部７０７_１、第２の基本演算シード記憶部７０７_２、第３の基本演算シード記憶部７０７_３より、
2020165931.tif 001110
を取得する。そして、第１の再分散値計算部７０２_１と第２の再分散値計算部７０２_２と第３の再分散値計算部７０２_３は
2020165931.tif 001111
を生成する。さらに、第１の再分散値計算部７０２_１は、
2020165931.tif 001112
を第１のデータ記憶部７０８_１に記憶する。第３の再分散値計算部７０２_３は、
2020165931.tif 001113
を、第３のシェア構成部７０３_３に送信する。また、第２の再分散値計算部７０２_２は、第２のデータ記憶部７０８_２から
2020165931.tif 001114
を取り出し、
2020165931.tif 001115
を、第４のシェア構成部７０３_４に送信する。
【０３２３】
ここで、
2020165931.tif 001116
である。
2020165931.tif 001117
は、たとえば、カウンタであり、各サーバ装置７００_１〜７００_４の間で共有している。
【０３２４】
（ステップＧ３）
第２の再分散値計算部７０２_２は、第２の基本演算シード記憶部７０７_２から
2020165931.tif 001118
を取得する。第３の再分散値計算部７０２_３は、第３の基本演算シード記憶部７０７_３から
2020165931.tif 001119
を取得する。第４の再分散値計算部７０２_４は、第４の基本演算シード記憶部７０７_４から
2020165931.tif 001120
を取得する。また、第４の再分散値計算部７０２_４は、第４のデータ記憶部７０８_４から
2020165931.tif 001121
を取得する。
【０３２５】
ここで、第２の再分散値計算部７０２_２および第３の再分散値計算部７０２_３および第４の再分散値計算部７０２_４は
2020165931.tif 001122
を計算する。第２の再分散値計算部７０２_２および第３の再分散値計算部７０２_３および第４の再分散値計算部７０２_４は、それぞれ、第２のデータ記憶部７０８_２および第３のデータ記憶部７０８_３および第４のデータ記憶部７０８_４に送信する。
【０３２６】
さらに第４の再分散値計算部７０２_４は、
2020165931.tif 001123
を用いて、
2020165931.tif 001124
を生成し、第１のシェア構成部７０３_１および第４のシェア構成部７０３_４に送信する。同様に第３の再分散値計算部７０２_４は、
2020165931.tif 001125
を生成し、第３のシェア構成部７０３_３および第３のデータ記憶部７０８_３に送信する。
【０３２７】
ここで、
2020165931.tif 001126
である。
2020165931.tif 001127
は、たとえば、カウンタであり、各サーバ装置７００_１〜７００_４の間で共有している。
【０３２８】
（ステップＧ４）
各シェア構成部７０３_１、７０３_２、７０３_３、７０３_４は、各データ記憶部７０８_１、７０８_２、７０８_３、７０８_４からそれぞれ、
2020165931.tif 001128
、
2020165931.tif 001129
、
2020165931.tif 001130
、
2020165931.tif 001131
を取り出す。さらに上記ステップＧ２、Ｇ３で送信された値を用いて、以下の８の式によりシェアを構成する。
2020165931.tif 001132
2020165931.tif 001133
2020165931.tif 001134
2020165931.tif 001135
2020165931.tif 001136
2020165931.tif 001137
2020165931.tif 001138
2020165931.tif 001139
ここで、
2020165931.tif 001140
に対し、
2020165931.tif 001141
は
2020165931.tif 001142
のｊ番目のビット（ｊ＝０、．．．、ｎ−１）を意味する。
2020165931.tif 001143
、
2020165931.tif 001144
は各ｉ番目のデータ記憶部７０８_ｉに記憶される。
【０３２９】
上記ステップＧ４における８の式において、
2020165931.tif 001145
としたとき、
2020165931.tif 001146
、
2020165931.tif 001147
、
2020165931.tif 001148
と置き換えることできる。このように、
2020165931.tif 001149
となるので、各再分散値計算部７０２_ｉは、値ｘ’の再分散値を計算する際、値ｘ’をｘ１’、ｘ２’、ｘ３’の排他的論理和すると場合、ｘ１’を乱数ｒに等しく、ｘ２’をゼロ、ｘ３’を乱数ｒと値ｘの排他的論理和となるように乱数を生成している。
つまり、各再分散値計算部７０２_ｉは、再分散する際に一部がゼロとなるように乱数を生成する。
【０３３０】
（ステップＧ５）
各ｉ番目の論理演算部７０６_ｉで通信することで、加算器処理
2020165931.tif 001150
を以下のように計算する。ここで、
2020165931.tif 001151
とは、たとえば、
2020165931.tif 001152
、
2020165931.tif 001153
を入力とし、
2020165931.tif 001154
を出力する処理のことである。
2020165931.tif 001155
ここで、
2020165931.tif 001156
なので、
2020165931.tif 001157
が計算できた。なお、
2020165931.tif 001158
は、
2020165931.tif 001159
、…、
2020165931.tif 001160
のシェア列を意味する。各ｉ番目の論理演算部７０６_ｉは、
2020165931.tif 001161
を各データ記憶部７０８_ｉに記憶する。
【０３３１】
（ステップＧ６）
第１のサーバ装置７００_１は、上記ステップＧ２における第２のサーバ装置７００_２と同様、第１のマスク値計算部７０１_１は、
2020165931.tif 001162
を生成し、
2020165931.tif 001163
を第４のサーバ装置７００_４に送信する。第４のサーバ装置７００_４は、第４のデータ記憶部７０８_４に
2020165931.tif 001164
を記憶する。第４の不正検知部７０４_４は、第４のデータ記憶部７０８_４から
2020165931.tif 001165
を取り出し、
2020165931.tif 001166
が成り立つか、検証する。
【０３３２】
2020165931.tif 001167
が成り立つ場合は、第４の不正検知部７０４_４はsuccessの文字列を各サーバ装置７００_１、７００_２、７００_３にブロードキャストし、次のステップに進む。
2020165931.tif 001168
が成り立たない場合は、第４の不正検知部７０４_４はabortの文字列を各サーバ装置７００_１、７００_２、７００_３にブロードキャストし、プロトコルを中断する。
【０３３３】
第１の再分散値計算部７０２_１は、
2020165931.tif 001169
を第１のデータ記憶部７０８_１から取り出す。次に、第１の再分散値計算部７０２_１は、
2020165931.tif 001170
を、第４の不正検知部７０４_４に送信する。第４の不正検知部７０４_４は、第４のデータ記憶部７０８_４に記憶されている
2020165931.tif 001171
2020165931.tif 001172
を取出し、
2020165931.tif 001173
が成立するかを検証する。
【０３３４】
成立した場合、第４の不正検知部７０４_４は、successの文字列を各サーバ装置７００_１、７００_２、７００_３、７００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部７０４_４は、abortの文字列を各サーバ装置７００_１、７００_２、７００_３、７００_４にブロードキャストし、プロトコルを中断する。
【０３３５】
なお、大量の型変換処理を並列に行う場合、
2020165931.tif 001174
、
2020165931.tif 001175
に関しては、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０３３６】
（ステップＧ７）
第３の不正検知部７０４_３は、
2020165931.tif 001176
を第３のデータ記憶部７０８_３から取出し、
2020165931.tif 001177
を第１の不正検知部７０４_１に送信する。第１の不正検知部７０４_１は、第１のデータ記憶部７０８_１から
2020165931.tif 001178
を取出し、
2020165931.tif 001179
が成り立つか、検証する。
2020165931.tif 001180
が成り立つ場合は、第１の不正検知部７０４_１はsuccessの文字列を各サーバ装置７００_２、７００_３、７００_４にブロードキャストし、次のステップに進む。
2020165931.tif 001181
が成り立たない場合は、第１の不正検知部７０４_１はabortの文字列を各サーバ装置７００_２、７００_３、７００_４にブロードキャストし、プロトコルを中断する。
【０３３７】
なお、大量の型変換処理を並列に行う場合、
2020165931.tif 001182
に関しては、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０３３８】
（ステップＧ８）
各ｉ番目の不正検知部７０４_ｉは、上記ステップＧ５の
2020165931.tif 001183
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置７００_１、７００_２、７００_３、７００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置７００_１、７００_２、７００_３、７００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＧ８は上記ステップＧ６、Ｇ７と並列に実行することが可能である。
【０３３９】
以上、説明した本発明の第７の実施形態においては、第１乃至第６の実施形態における効果と同じ効果を奏する。また、ビット分解の理論的な通信コストについて、第７の実施形態の方が他の実施形態よりも、効率が良い。第７の実施形態では、ビット分解に関して
2020165931.tif 001184
の計算を１回行うことで実現できる。リップルキャリー型のｎビット加算器を用いて不正検知に関する処理を並列に行った場合、第５の実施形態では、ビット分解の通信コストとして、８ｎ−５ビット・ｎ＋１ラウンドを要する。これより、第７の実施形態の方が他の実施形態よりもビット分解の通信コストの点で効率が良い。なお、本願開示の実施はリップルキャリー型のｎビット加算器に限定されない。キャリールックアヘッド型やパラレルプリフィックス型などのｎビット加算器を用いても良い。
【０３４０】
［ハードウェア構成］
続いて、秘密計算システムをなす秘密計算サーバのハードウェア構成について説明する。
【０３４１】
図２５は、第ｉの秘密計算サーバ装置１００_ｉのハードウェア構成の一例を示す図である。第ｉの秘密計算サーバ装置１００_ｉは、所謂、情報処理装置（コンピュータ）により実現され、図２５に例示する構成を備える。例えば、第ｉの秘密計算サーバ装置１００_ｉは、内部バスにより相互に接続される、ＣＰＵ（Central Processing Unit）２１、メモリ２２、入出力インターフェイス２３、通信手段であるＮＩＣ（Network Interface Card）２４等を備える。
【０３４２】
但し、図２５に示す構成は、第ｉの秘密計算サーバ装置１００_ｉのハードウェア構成を限定する趣旨ではない。第ｉの秘密計算サーバ装置１００_ｉは、図示しないハードウェアを含んでもよい。第ｉの秘密計算サーバ装置１００_ｉに含まれるＣＰＵ等の数も図２５の例示に限定する趣旨ではなく、例えば、複数のＣＰＵ２１が第ｉの秘密計算サーバ装置１００_ｉに含まれていてもよい。
【０３４３】
メモリ２２は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、補助記憶装置（ハードディスク等）等である。
【０３４４】
入出力インターフェイス２３は、図示しない入出力装置のインターフェイスである。入出力装置には、例えば、表示装置、操作デバイス等が含まれる。表示装置は、例えば、液晶ディスプレイ等である。操作デバイスは、例えば、キーボードやマウス等である。
【０３４５】
第ｉの秘密計算サーバ装置１００_ｉの機能は、上述の処理モジュールにより実現される。当該処理モジュールは、例えば、メモリ２２に格納されたプログラムをＣＰＵ２１が実行することで実現される。また、そのプログラムは、ネットワークを介してダウンロードするか、あるいは、プログラムを記憶した記憶媒体を用いて、更新することができる。さらに、上記処理モジュールは、半導体チップにより実現されてもよい。即ち、上記処理モジュールが行う機能は、何らかのハードウェア、或いはハードウェアを利用して実行されるソフトウェアにより実現できればよい。
【０３４６】
［変形例］
なお、第１乃至第７の実施形態にて説明した秘密計算検証システムの構成及び動作は例示であって、種々の変形が可能である。例えば、上記実施形態では、４つの秘密計算サーバ装置１００_１〜１００_４が対等である場合を説明したが、１つのサーバ装置を代表サーバとして定めてもよい。この場合、代表サーバが秘密計算に用いるデータの入出力（入力データの分散及び配布、計算結果の復号）を制御してもよい。
【０３４７】
上述の説明で用いたフローチャートでは、複数の工程（処理）が順番に記載されているが、各実施形態で実行される工程の実行順序は、その記載の順番に制限されない。各実施形態では、例えば各処理を並行して実行する等、図示される工程の順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態は、内容が相反しない範囲で組み合わせることができる。即ち、上記各実施形態の任意の組み合わせが更なる実施形態として含まれる。
【０３４８】
上述の説明で用いたフローチャートでは、複数の工程（処理）が順番に記載されているが、各実施形態で実行される工程の実行順序は、その記載の順番に制限されない。各実施形態では、例えば各処理を並行して実行する等、図示される工程の順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態は、内容が相反しない範囲で組み合わせることができる。即ち、上記各実施形態の任意の組み合わせが更なる実施形態として含まれる。
【０３４９】
上記の説明により、本発明の産業上の利用可能性は明らかであるが、本発明は、たとえば、
2020165931.tif 001185
の環上で実行される２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた不正検知可能な４者間ＭＰＣにて、生体テンプレート照合や統計演算などの混合回路の計算を効率よく実現する場合に好適である。また、本発明では加算器を計算する際に用いる回路を変更することで、通信量と通信回数についてトレードオフが成立するような異なる型変換を実現できる。これにより、通信環境に応じて、効率よく型変換を行える。よって、型変換をサブルーチンとして用いる混合回路を上記４者間ＭＰＣにて実行する際に、通信環境に応じて、効率よく実行できる。
【０３５０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
［付記１］
上述の第１の視点に係る情報処理装置のとおりである。
［付記２］
前記生成された乱数に関するデータを用いて不正行為者の有無を検知する、不正検知部をさらに備える、好ましくは付記１に記載の情報処理装置。
［付記３］
前記型変換されたシェアについての論理演算を行う論理演算部をさらに備え、
前記論理演算部は、他の装置と互いに通信を行い前記型変換されたシェアの加算処理を実行し、
前記不正検知部は、前記型変換されたシェアの加算処理のために送受信されたデータを用いて不正行為者の有無を検知する、好ましくは付記２に記載の情報処理装置。
［付記４］
前記論理演算部は、他の装置と互いに通信を行い前記型変換されたシェアのキャリー計算処理を実行し、
前記不正検知部は、前記型変換されたシェアのキャリー計算処理のために送受信されたデータを用いて不正行為者の有無を検知する、好ましくは付記３に記載の情報処理装置。
［付記５］
前記キャリー計算処理は、第１要素及び前記第１要素に続く第２要素に分離可能であり、
前記論理演算部は、
前記第１要素を他の装置と非通信により計算すると共に、前記シェアの再分散値の計算に必要な通信と前記第２要素のキャリー計算処理に必要な通信を並列に行う、好ましくは付記４に記載の情報処理装置。
［付記６］
シェアをマスクするためのマスク値を計算すると共に、前記計算されたマスク値によりマスクされたシェアを他の装置に送信する、マスク値計算部をさらに備え、
前記シェア構成部は、前記送信されたマスク値を用いて前記型変換用のシェアを構成する、好ましくは付記１乃至５のいずれか一に記載の情報処理装置。
［付記７］
前記再分散値計算部は、値ｘの再分散値を計算する際、値ｘをｘ１、ｘ２、ｘ３の排他的論理和とする場合に前記ｘ１乃至ｘ３のうち２つの値を等しくするように乱数を生成する、好ましくは付記１乃至６のいずれか一に記載の情報処理装置。
［付記８］
前記再分散値計算部は、値ｘ’の再分散値を計算する際、値ｘ’をｘ１’、ｘ２’、ｘ３’の排他的論理和とする場合、ｘ１’を乱数ｒに等しく、ｘ２’をゼロ、ｘ３’を乱数ｒと値ｘの排他的論理和とする、好ましくは付記７に記載の情報処理装置。
［付記９］
前記再分散値計算部は、疑似ランダム関数に前記シードと他の装置と共有されるカウンタ値を入力し、前記シードを用いた乱数を生成する、好ましくは付記１乃至８のいずれか一に記載の情報処理装置。
［付記１０］
前記型変換用のシェアは、ビット分解用のシェア又は環合成用のシェアである、好ましくは付記１乃至９のいずれか一に記載の情報処理装置。
［付記１１］
上述の第２の視点に係る秘密計算方法のとおりである。
［付記１２］
上述の第３の視点に係るプログラムのとおりである。
なお、付記１１の形態及び付記１２の形態は、付記１の形態と同様に、付記２の形態〜付記１０の形態に展開することが可能である。
【０３５１】
なお、引用した上記の特許文献等の各開示は、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択（部分的削除を含む）が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０３５２】
１０  情報処理装置
１１、１０７_１、２０７_１、３０７_１、４０７_１、５０７_１、６０７_１、７０７_１、１０７_ｉ〜７０７_ｉ  基本演算シード記憶部
１２、１０２_１、２０２_１、３０２_１、４０２_１、５０２_１、６０２_１、７０２_１、１０２_ｉ〜７０２_ｉ  再分散値計算部
１３、１０３_１、２０３_１、３０３_１、４０３_１、５０３_１、６０３_１、７０３_１、１０３_ｉ〜７０３_ｉ  シェア構成部
２１  ＣＰＵ（Central Processing Unit）
２２  メモリ
２３  入出力インターフェイス
２４  ＮＩＣ（Network Interface Card）
１００_１〜１００_４、２００_１〜２００_４、３００_１〜３００_４、４００_１〜４００_４、５００_１〜５００_４、６００_１〜６００_４、７００_１〜７００_４、１００_ｉ〜７００_ｉ  秘密計算サーバ装置
５０１_１、６０１_１、７０１_１、５０１_ｉ〜５０１_ｉ  マスク値計算部
１０４_１、２０４_１、３０４_１、４０４_１、５０４_１、６０４_１、７０４_１、１０４_ｉ〜７０４_ｉ  不正検知部
１０５_１、２０５_１、３０５_１、４０５_１、５０５_１、６０５_１、７０５_１、１０５_ｉ〜７０５_ｉ  算術演算部
１０６_１、２０６_１、３０６_１、４０６_１、５０６_１、６０６_１、７０６_１、１０６_ｉ〜７０６_ｉ  論理演算部
１０８_１、２０８_１、３０８_１、４０８_１、５０８_１、６０８_１、７０８_１、１０８_ｉ〜７０８_ｉ  データ記憶部
【図１】
2020165931.tif 001186
【図２】
2020165931.tif 001187
【図３】
2020165931.tif 001188
【図４】
2020165931.tif 001189
【図５】
2020165931.tif 001190
【図６】
2020165931.tif 001191
【図７】
2020165931.tif 001192
【図８】
2020165931.tif 001193
【図９】
2020165931.tif 001194
【図１０】
2020165931.tif 001195
【図１１】
2020165931.tif 001196
【図１２】
2020165931.tif 001197
【図１３】
2020165931.tif 001198
【図１４】
2020165931.tif 001199
【図１５】
2020165931.tif 001200
【図１６】
2020165931.tif 001201
【図１７】
2020165931.tif 001202
【図１８】
2020165931.tif 001203
【図１９】
2020165931.tif 001204
【図２０】
2020165931.tif 001205
【図２１】
2020165931.tif 001206
【図２２】
2020165931.tif 001207
【図２３】
2020165931.tif 001208
【図２４】
2020165931.tif 001209
【図２５】
2020165931.tif 001210
【国際調査報告】
2020165931.tif 001211
2020165931.tif 001212
2020165931.tif 001213
2020165931.tif 001214