(57)【要約】  ２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣにてビット埋込処理を実行する情報処理装置を提供する。情報処理装置は、基本演算シード記憶部と、シェア再構成データ生成部と、シェア構成部と、を備える。基本演算シード記憶部は、シェアについての演算を行う際の乱数を生成するためのシードを格納する。シェア再構成データ生成部は、シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する。シェア構成部は、少なくともシェア再構成データを用いてビット埋込用のシェアを構成する。
2020165932.tif 000002
【特許請求の範囲】
【請求項１】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部と、
前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する、シェア再構成データ生成部と、
少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成する、シェア構成部と、
を備える、情報処理装置。
【請求項２】
前記シェア再構成データ生成部は、前記シェアの再構成に使用される乱数を生成する、請求項１に記載の情報処理装置。
【請求項３】
前記シェア再構成データ生成部は、値ｘ’に関する前記シェア再構成データを生成する際、値ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合に、ｘ１’、ｘ２’及びｘ３’のうち２つの値が等しくなるように、乱数を生成する、請求項２に記載の情報処理装置。
【請求項４】
前記シェア再構成データ生成部は、値ｘ’に関する前記シェア再構成データを生成する際、値ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合に、ｘ１’、ｘ２’及びｘ３’のうち２つがゼロとなるように乱数を生成する、請求項２に記載の情報処理装置。
【請求項５】
前記シェア再構成データ生成部は、値ｘに関する前記シェア再構成データを生成する際、値ｘ＝ｘ１＋ｘ２＋ｘ３とした場合に、ｘ１、ｘ２及びｘ３のうち２つの値が等しくなるように、乱数を生成すると共に、
値ｘ’に関する前記シェア再構成データを生成する際、ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合、ｘ１’＝ｘ’＋ｒ、ｘ２’＝０、ｘ３’＝-ｒとなるように乱数ｒを生成する、請求項２に記載の情報処理装置。
【請求項６】
前記ビット埋込用のシェアを用いて不正行為者の有無を検知する、不正検知部をさらに備える、請求項１乃至５のいずれか一項に記載の情報処理装置。
【請求項７】
前記ビット埋込用のシェアを用いて環上での排他的論理和を計算する、算術演算部をさらに備え、
前記不正検知部は、前記排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知する、請求項６に記載の情報処理装置。
【請求項８】
前記ビット埋込用のシェアを用いた不正行為者の有無を検知することと、前記排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知すること、が並列に実行される、請求項７に記載の情報処理装置。
【請求項９】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部を備える情報処理装置において、
前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成するステップと、
少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成するステップと、
を含む、秘密計算方法。
【請求項１０】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部を備える情報処理装置に搭載されたコンピュータに、
前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する処理と、
少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成する処理と、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、秘密計算方法及びプログラムに関する。特に、不正検知可能な４者秘密計算におけるビット埋込に関する情報処理装置、秘密計算方法及びプログラムに関する。
【背景技術】
【０００２】
近年、秘密計算に関する研究開発が盛んに行われている。秘密計算では、入力データを秘匿したまま所定の処理を実行し、結果を得ることができる。【０００３】
秘密計算プロトコルは大きく２つの種類に大別される。第１の方式は、特定の計算に限って実行可能な秘密計算プロトコルである。第２の方式は、任意の計算が実行可能な秘密計算プロトコルである。また、第２の方式には種々の方式が存在し、方式間で通信量（データ量）や通信ラウンド数をはじめとした様々なコストにおけるトレードオフが成立する。たとえば、通信量が少ない代わりに通信回数が多い方式や通信量は多いが通信回数が少ない方式が存在する。【０００４】
代表的な秘密計算プロトコルとして、マルチパーティ計算（ＭＰＣ；Multi Party Computation）が挙げられる。ＭＰＣとは、各参加者の入力を秘匿しながら、複数の参加者間で任意の関数を計算できる秘密計算プロトコルである。ＭＰＣにも、いくつかの方式があるが、近年注目を集める方式は、秘密分散ベースのＭＰＣである。秘密分散ベースのＭＰＣでは、入力を各参加者に分散する。ここで、分散データのことをシェアと呼称する。各参加者は各自のシェアを用いて、参加者間で協調しながら、目的の関数を計算する。このとき、計算過程の値に関してもシェアの形式を保っているために、元々の入力や計算過程の値が明らかになることはない。最終的な計算結果のシェアだけが、復元され、安全に任意の関数が計算できる。以降、ｎ≧２のときの
2020165932.tif 000003
の値のシェアを
2020165932.tif 000004
、ｎ＝１のときの
2020165932.tif 000005
の値のシェアを
2020165932.tif 000006
として表記する。【０００５】
ここで、ＭＰＣが達成する安全性は、大きく２つある。１つは秘匿性（Secrecy）である。もう１つは正当性（Correctness）である。秘匿性は、ＭＰＣを実行するにあたり、想定する攻撃者が存在したとしても、参加者に対し、入力に関する情報が漏れないことを保証する安全性となる。正当性は、秘密計算プロトコルを実行するにあたり、想定する攻撃者が存在したとしても、実行結果が正しいことを保証する安全性となる。【０００６】
ここで、上記の「想定する攻撃者」には、いくつかの指標がある。代表的な指標として、１つ目は攻撃者の振舞いが挙げられる。２つ目は参加者における攻撃者の割合である。【０００７】
攻撃者の振舞いに着目した場合、代表的な攻撃者の種類として、セミオネスト攻撃者（Semi-honest Adversary）とマリシャス攻撃者（Malicious Adversary）が挙げられる。セミオネスト攻撃者は、プロトコルに従いつつも、可能な範囲で得られる情報を増やそうと試みる攻撃者である。マリシャス攻撃者は、プロトコルから逸脱した振舞いを取ることで、自身が得られる情報を増やそうと試みる攻撃者である。ここで、プロトコルから逸脱する振舞いとは、たとえば本来送信すべきデータに対し、ビット反転を行うことによって、送信データを改ざんすることが挙げられる。【０００８】
参加者における攻撃者の割合に着目した場合、大きく２つの種類が挙げられる。１つは、過半数が不正者（Dishonest majority）の場合である。もう１つは、過半数が正直者（Honest majority）の場合である。ここで、全参加者数をｎとし、攻撃者の数をｔとする。過半数が不正者の場合とは、つまり、ｔ＜ｎが成り立つ場合を意味する。過半数が正直者の場合とは、つまり、ｔ＜ｎ／２が成り立つ場合を意味する。過半数が正直者である場合としてｔ＜ｎ／３が成り立つ場合も含まれるが、本書では特に断りが無い限り、ｔ＜ｎ／２が成り立つ場合を過半数が正直者である場合とする。【０００９】
近年、注目を集めるＭＰＣとして３者間ＭＰＣが挙げられる。非特許文献１は、過半数が正直者で、かつ、攻撃者がセミオネスト攻撃者である場合の３者間ＭＰＣを開示する。非特許文献１に開示されたＭＰＣは、
2020165932.tif 000007
上での算術演算を実現する。非特許文献１に開示されたＭＰＣは、
2020165932.tif 000008
上での乗算１回あたり、３ｎビットの通信コストを要する。つまり、参加者あたりｎビットの通信コストで乗算を実現できる。【００１０】
非特許文献２は、過半数が正直者で、かつ、攻撃者がマリシャス攻撃者である場合の３者間ＭＰＣを開示する。これは、非特許文献１の方式をベースとした方式である。非特許文献２に開示されたＭＰＣは、非特許文献１に開示されたＭＰＣとは異なり、マリシャス攻撃者の存在を許容する。非特許文献２に開示されたＭＰＣではマリシャス攻撃者による不正を、確率的に検知することが可能となる。検知確率を上げるほど、つまり、不正が成功する確率を下げようとするほど、通信コストが増加することとなる。たとえば、不正が成功する確率を２-４０とした場合、非特許文献２では、
2020165932.tif 000009
上での乗算１回あたり、２１ｎビットの通信コストを要する。つまり、参加者あたり７ｎビットの通信コストで不正検知機能付きの乗算を実現できる。【００１１】
非特許文献３では、非特許文献１におけるシェアに対するビット埋込処理の方法が提案されている。ビット埋込とは、たとえば、
2020165932.tif 000010
から
2020165932.tif 000011
のシェアを得ることが挙げられる。このような処理は、算術回路や論理回路が混在した混合回路に対し、効率よくＭＰＣを実行したい場合に重要な処理となる。特に、条件判定の結果を用いて、処理を分岐させる場合に、重要な処理となる。たとえば、非特許文献２の方式を用いて非特許文献３で提案されたビット埋込を実行した場合、マリシャス攻撃者の存在を許容できる、通信コストは４２ｎビット・２ラウンドとなる。【００１２】
多くの場合、ＭＰＣにおいて参加者が少なく、過半数が正直者の場合の方が、通信コストは低くなる。このため、前述のような３者間ＭＰＣが計算効率の良い方式であると考えられてきた。しかし、想定する攻撃者がマリシャス攻撃者の場合、計算効率は４者間ＭＰＣの方が良い場合がある。【００１３】
たとえば、非特許文献４は、ｔ＜ｎ／３、つまりｔ＝１で、かつ、攻撃者がマリシャス攻撃者である場合の４者間ＭＰＣを開示する。非特許文献４に開示されたＭＰＣは、
2020165932.tif 000012
上での乗算１回あたり、６ｎビットの通信コストを要する。つまり、参加者あたり１．５ｎビットの通信コストで乗算を実現できる。しかし、非特許文献４では方式固有のビット埋込処理が提案されていない。非特許文献３に記載のあるビット埋込は、シェアの形式が特定の形式であることを要求するため、非特許文献３に記載のビット埋込を非特許文献４の方式に適用することはできない。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】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.
【非特許文献３】大原ら.、”異なるサイズの環が混在する不正検知可能なマルチパーティ計算.”、In SCIS 2018, 2A1-4.
【非特許文献４】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.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
なお、上記先行技術文献の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者らによってなされたものである。【００１６】
ＭＰＣを行うにあたり、可能な限り通信コストが軽減された方式が望まれる。通信コストには通信量と通信ラウンド回数とがあるが、単位時間あたりの処理件数の効率を重視する場合、特に通信量が重要となる。【００１７】
たとえば、ｔ＜ｎ／３、つまりｔ＝１で、かつ、攻撃者がマリシャス攻撃者である場合での４者間ＭＰＣであれば、
2020165932.tif 000013
上での乗算１回あたり、５ｎビットの通信コストで実現できる。つまり、参加者あたり１．２５ｎビットの通信コストで乗算を実現できる。これは２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた方法である。【００１８】
各参加者をＰ_ｉ（ｉ＝１、…、４）としたとき、
2020165932.tif 000014
のシェアを
2020165932.tif 000015
として、
2020165932.tif 000016
をＰ_ｉのシェアとする。また、
2020165932.tif 000017
のシェアを
2020165932.tif 000018
として、
2020165932.tif 000019
をＰ_ｉのシェアとする。このとき、
2020165932.tif 000020
に対して、
2020165932.tif 000021
とすると、
2020165932.tif 000022
とする。また、
2020165932.tif 000023
に対して、
2020165932.tif 000024
とすると、
2020165932.tif 000025
とする。【００１９】
なお、
2020165932.tif 000026
とし、疑似ランダム関数
2020165932.tif 000027
とする。また、
2020165932.tif 000028
を文字列連結演算子とする。ここで、Ｐ_１は
2020165932.tif 000029
を、Ｐ_２は
2020165932.tif 000030
を、Ｐ_３は
2020165932.tif 000031
を、Ｐ_４は
2020165932.tif 000032
を、それぞれ有する。【００２０】
なお、
2020165932.tif 000033
に関して、参加者の内、ある一人の参加者は
2020165932.tif 000034
の出力を計算できず、他の三人の参加者は
2020165932.tif 000035
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165932.tif 000036
の扱いは特に制限されない。本書での
2020165932.tif 000037
はあくまでも一例である。【００２１】
ここで、
2020165932.tif 000038
を
2020165932.tif 000039
上のシェアに関する加法演算子、減法演算子、乗法演算子とする。なお、これらの演算子は
2020165932.tif 000040
上の要素に対する二項演算子としての加法演算子、減法演算子、乗法演算子としても以降用いることに注意されたい。
2020165932.tif 000041
上のシェアに関する加法演算子、乗法演算子について、
2020165932.tif 000042
としたとき、以下の４つの式が成り立つ。
2020165932.tif 000043
2020165932.tif 000044
2020165932.tif 000045
2020165932.tif 000046
【００２２】
また、
2020165932.tif 000047
を
2020165932.tif 000048
上のシェアに関する排他的論理和、論理積とする。なお、これらの演算子は
2020165932.tif 000049
上の要素に対する二項演算子としての排他的論理和、論理積としても以降用いることに注意されたい。
2020165932.tif 000050
上のシェアに関する排他的論理和、論理積について、
2020165932.tif 000051
としたとき、以下の４つの式が成り立つ。
2020165932.tif 000052
2020165932.tif 000053
2020165932.tif 000054
2020165932.tif 000055
【００２３】
たとえば、前述の２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣでは、
2020165932.tif 000056
2020165932.tif 000057
2020165932.tif 000058
2020165932.tif 000059
2020165932.tif 000060
となり
2020165932.tif 000061
から
2020165932.tif 000062
が計算できる。また、
2020165932.tif 000063
としたとき、
2020165932.tif 000064
に関しても、以下の手順で
2020165932.tif 000065
を用いて計算できる。【００２４】
１．各参加者（Ｐ＿１〜Ｐ３）のそれぞれは以下の計算を行う。
Ｐ_１：
2020165932.tif 000066
2020165932.tif 000067
2020165932.tif 000068
2020165932.tif 000069
【００２５】
Ｐ_２：
2020165932.tif 000070
2020165932.tif 000071
2020165932.tif 000072
2020165932.tif 000073
【００２６】
Ｐ_３：
2020165932.tif 000074
2020165932.tif 000075
2020165932.tif 000076
2020165932.tif 000077
【００２７】
２．上記計算が終了すると、各参加者は以下の通信を行う。【００２８】
・Ｐ_１は
2020165932.tif 000078
をＰ_３に送信する。
・Ｐ_２は
2020165932.tif 000079
をＰ_１に送信する。
・Ｐ_３は
2020165932.tif 000080
をＰ_２に送信する。
・Ｐ_１は
2020165932.tif 000081
をＰ_４に送信する。
・Ｐ_２は
2020165932.tif 000082
をＰ_４に送信する。【００２９】
３．各参加者は、上記通信により得た情報を用いて以下の計算により
2020165932.tif 000083
を得る。【００３０】
2020165932.tif 000084
2020165932.tif 000085
2020165932.tif 000086
2020165932.tif 000087
【００３１】
なお、Ｐ_４のシェアは以下のようにして、計算する。【００３２】
Ｐ_４：
2020165932.tif 000088
2020165932.tif 000089
【００３３】
シェアと定数倍算、および定数加算については当業者にとって自明なので説明を割愛する。また、
2020165932.tif 000090
上のシェアに関する演算についても、
2020165932.tif 000091
上のシェアに関する演算と同様に実行できるので説明を割愛する。このとき、参加者中にマリシャス攻撃者が１人存在したとしても、各自のシェアと異なる参加者から受信した値を用いて、値の改ざんがなかったか検証できる。改ざんがあった場合は、プロトコルを中断する。【００３４】
しかし、上記２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた方法を用いた４者間ＭＰＣでは、ビット埋込を行うことが難しい。シェアの形式が異なるため、非特許文献３に開示された方法を直接用いることができないためである。よって、混合回路の計算を不正検知可能なＭＰＣで効率よく行いたい場合、非特許文献４に開示された４者間ＭＰＣもしくは上記２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣで実行可能な、効率の良いビット埋込処理の提案が求められる。【００３５】
本発明は、２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣにてビット埋込処理を実行することに寄与する、情報処理装置、秘密計算方法及びプログラムを提供することを主たる目的とする。
【課題を解決するための手段】
【００３６】
本発明乃至開示の第１の視点によれば、シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部と、前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する、シェア再構成データ生成部と、少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成する、シェア構成部と、を備える、情報処理装置が提供される。【００３７】
本発明乃至開示の第２の視点によれば、シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部を備える情報処理装置において、前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成するステップと、少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成するステップと、を含む、秘密計算方法が提供される。【００３８】
本発明乃至開示の第３の視点によれば、シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部を備える情報処理装置に搭載されたコンピュータに、前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する処理と、少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成する処理と、を実行させるプログラムが提供される。
なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。記憶媒体は、半導体メモリ、ハードディスク、磁気記録媒体、光記録媒体等の非トランジェント（non-transient）なものとすることができる。本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００３９】
本発明によれば、前記２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣにて混合回路を計算する際に、効率よく計算可能なビット埋込を実行する情報処理装置、秘密計算方法及びプログラムが、提供される。
【図面の簡単な説明】
【００４０】
【図１】一実施形態の概要を説明するための図である。
【図２】第１の実施形態におけるビット埋込システムの機能構成例を示すブロック図である。
【図３】第１の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図４】第１の実施形態におけるビット埋込についてのビット埋込システムの動作例を示すフローチャートである。
【図５】第２の実施形態におけるビット埋込システムの機能構成例を示すブロック図である。
【図６】第２の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図７】第２の実施形態におけるビット埋込についてのビット埋込システムの動作例を示すフローチャートである。
【図８】第３の実施形態におけるビット埋込システムの機能構成例を示すブロック図である。
【図９】第３の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図１０】第３の実施形態におけるビット埋込についてのビット埋込システムの動作例を示すフローチャートである。
【図１１】第４の実施形態におけるビット埋込システムの機能構成例を示すブロック図である。
【図１２】第４の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図１３】第４の実施形態におけるビット埋込についてのビット埋込システムの動作例を示すフローチャートである。
【図１４】第５の実施形態におけるビット埋込の機能構成例を示すブロック図である。
【図１５】第５の実施形態によるサーバ装置の機能構成を示すブロック図である。
【図１６】第５の実施形態におけるビット埋込についてのビット埋込システムの動作例を示すフローチャートである。
【図１７】秘密計算サーバ装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００４１】
初めに、一実施形態の概要について説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、この概要の記載はなんらの限定を意図するものではない。また、各図におけるブロック間の接続線は、双方向及び単方向の双方を含む。一方向矢印については、主たる信号（データ）の流れを模式的に示すものであり、双方向性を排除するものではない。さらに、本願開示に示す回路図、ブロック図、内部構成図、接続図などにおいて、明示は省略するが、入力ポート及び出力ポートが各接続線の入力端及び出力端のそれぞれに存在する。入出力インターフェイスも同様である。
【００４２】
一実施形態に係る情報処理装置１０は、基本演算シード記憶部１１と、シェア再構成データ生成部１２と、シェア構成部１３と、を備える（図１参照）。基本演算シード記憶部１１は、シェアについての演算を行う際の乱数を生成するためのシードを格納する。シェア再構成データ生成部１２は、シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する。シェア構成部１３は、少なくともシェア再構成データを用いてビット埋込用のシェアを構成する。
【００４３】
ここで、４者ＭＰＣにおいてもビット埋込は効率よく秘密計算を実行するためには有益な処理であるが、各装置が保有するシェアの形式が不統一であるとその恩恵が得られない。そこで、上記情報処理装置１０は、各装置が保有するシェアの形式を統一しビット埋込が容易となるようにシェアを再構成する。
【００４４】
以下に具体的な実施の形態について、図面を参照してさらに詳しく説明する。なお、各実施形態において同一構成要素には同一の符号を付し、その説明を省略する。
【００４５】
［第１の実施形態］
第１の実施形態について、図面を用いてより詳細に説明する。
【００４６】
図２〜図４を参照して、第１の実施形態に係るビット埋込処理システムについて説明する。
【００４７】
図２は、第１の実施形態によるビット埋込処理システムの機能構成例を示すブロック図である。図２を参照すると、第１の実施形態によるビット埋込処理システムは、後述する図３で参照される第ｉ（ｉ＝１、２、３、４）の秘密計算サーバ装置（以下、単にサーバ装置と表記する）から成る。第１の実施形態によるビット埋込処理システムにおいて、サーバ装置１００_１、１００_２、１００_３、１００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。
【００４８】
図３は、第ｉのサーバ装置１００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。図３に示すように、第ｉのサーバ装置１００_ｉは、第ｉのシェア再構成データ生成部１０２_ｉと、第ｉのシェア構成部１０３_ｉと、第ｉの不正検知部１０４_ｉと、第ｉの算術演算部１０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部１０７_ｉと、を含む。なお、第ｉのシェア再構成データ生成部１０２_ｉと、第ｉのシェア構成部１０３_ｉと、第ｉの不正検知部１０４_ｉと、第ｉの算術演算部１０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部１０７_ｉとは、それぞれ接続されている。
【００４９】
このような構成のビット埋込処理システムにおいては、第１乃至第４のサーバ装置１００_１〜１００_４の内のいずれかの装置が入力した値
2020165932.tif 000092
、あるいは第１乃至第４のデータ記憶部１０７_１〜１０７_４に記憶されたシェア
2020165932.tif 000093
、あるいは第１乃至第４のサーバ装置１００_１〜１００_４ではない外部から入力されたシェア
2020165932.tif 000094
に対し、その入力や計算過程の値から
2020165932.tif 000095
の値を知られることなく、
2020165932.tif 000096
を計算し、第１乃至第４のデータ記憶部１０７_１〜１０７_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置１００_１〜１００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置１００_１〜１００_４ではない外部にシェアが送信され、復元されてもよい。
【００５０】
次に、第１の実施形態におけるビット埋込処理システムおよび第１乃至第４のサーバ装置１００_１〜１００_４の動作について、詳細に説明する。図４は、第１乃至第４のサーバ装置１００_１〜１００_４のビット埋込に関する動作例を示すフローチャートである。
【００５１】
第1の実施形態では、
2020165932.tif 000097
上の値ｘのシェア
2020165932.tif 000098
に対してビット埋込を行う場合について説明する。その際、各サーバ装置１００_ｉは、
2020165932.tif 000099
上の値ｘのシェア
2020165932.tif 000100
から
2020165932.tif 000101
上の値ｘ２のシェア
2020165932.tif 000102
と
2020165932.tif 000103
のシェア
2020165932.tif 000104
を計算（構成）するためのデータを生成する。各サーバ装置１００_ｉは、
2020165932.tif 000105
上の値ｘのシェア
2020165932.tif 000106
を保持する。例えば、
2020165932.tif 000107
とした際、各サーバ装置１００_ｉは、以下の値の組を保持する。
サーバ装置１００_１：
2020165932.tif 000108
サーバ装置１００_２：
2020165932.tif 000109
サーバ装置１００_３：
2020165932.tif 000110
サーバ装置１００_４：
2020165932.tif 000111
例えば、値ｘ＝１とし、
2020165932.tif 000112
、
2020165932.tif 000113
、
2020165932.tif 000114
であれば、サーバ装置１００_１は（１、０）を保持する。
このような状況下において、ビット埋込を行う場合、
2020165932.tif 000115
上の値ｘのシェア
2020165932.tif 000116
から
2020165932.tif 000117
上の値ｘ２のシェア
2020165932.tif 000118
と値
2020165932.tif 000119
のシェア
2020165932.tif 000120
を計算する。
【００５２】
（ステップＡ１）
各基本演算シード記憶部１０６_１、１０６_２、１０６_３、１０６_４は、それぞれ
2020165932.tif 000121
、
2020165932.tif 000122
、
2020165932.tif 000123
、
2020165932.tif 000124
を記憶する。
【００５３】
また、各サーバ装置１００_１〜１００_４は疑似ランダム関数
2020165932.tif 000125
を共有する。なお、
2020165932.tif 000126
とし、疑似ランダム関数
2020165932.tif 000127
とする。また、各データ記憶部１０７_１〜１０７_４に、それぞれ
2020165932.tif 000128
を記憶する。ここで、
2020165932.tif 000129
は各データ記憶部１０７_ｉに記憶された
2020165932.tif 000130
である。
【００５４】
なお、
2020165932.tif 000131
に関して、サーバ装置１００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165932.tif 000132
の出力を計算できず、他の三台の参加者は
2020165932.tif 000133
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165932.tif 000134
の扱いは特に制限されない。本書での
2020165932.tif 000135
はあくまでも一例である。
【００５５】
（ステップＡ２）
ステップＡ２において、第ｉのシェア再構成データ生成部１０２_ｉは、ビット埋込を行う際に用いられるシェアを再構成するためのデータ（シェア再構成データ）を生成する。具体的には、第ｉのシェア再構成データ生成部１０２_ｉは、
2020165932.tif 000136
上の値ｘのシェア
2020165932.tif 000137
から
2020165932.tif 000138
上の値ｘ２のシェア
2020165932.tif 000139
と
2020165932.tif 000140
のシェア
2020165932.tif 000141
を計算（構成）するためのデータを生成する。
【００５６】
具体的には、第ｉのシェア再構成データ生成部１０２_ｉは、ある値ｘ（例えば、上記値ｘ２）のシェアを再構成するためのデータを生成する際、ｘ＝ｘ１＋ｘ２＋ｘ３とした場合（ｘは３つの値の和とした場合）、ｘ１、ｘ２、ｘ３のうち２つの値が等しくなるように乱数を生成する。さらに、第ｉのシェア再構成データ生成部１０２_ｉは、ある値ｘ’（例えば、上記
2020165932.tif 000142
）のシェアを再構成するためのデータを生成する際、ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合、ｒを乱数としてｘ１’＝ｘ’＋ｒ、ｘ２’＝０、ｘ３’＝-ｒとなるように乱数ｒを生成する。
【００５７】
第１のシェア再構成データ生成部１０２_１、第２のシェア再構成データ生成部１０２_２及び第３のシェア再構成データ生成部１０２_３はそれぞれ、第１の基本演算シード記憶部１０６_１、第２の基本演算シード記憶部１０６_２、第３の基本演算シード記憶部１０６_３より、
2020165932.tif 000143
を取得する。
【００５８】
そして、第１のシェア再構成データ生成部１０２_１、第２のシェア再構成データ生成部１０２_２及び第３のシェア再構成データ生成部１０２_３は
2020165932.tif 000144
を生成（計算）する。さらに、第１のシェア再構成データ生成部１０２_１は、
2020165932.tif 000145
を第１のデータ記憶部１０７_１に記憶する。第３のシェア再構成データ生成部１０２_３は、
2020165932.tif 000146
を、第３のシェア構成部１０３_３に送信する。また、第２のシェア再構成データ生成部１０２_２は、第２のデータ記憶部１０７_２から
2020165932.tif 000147
を取り出し、
2020165932.tif 000148
を、第４のシェア構成部１０３_４に送信する。
【００５９】
第２のシェア再構成データ生成部１０２_２は、第２の基本演算シード記憶部１０６_２から
2020165932.tif 000149
を取得する。第３のシェア再構成データ生成部１０２_３は、第３の基本演算シード記憶部１０６_３から
2020165932.tif 000150
を取得する。第４のシェア再構成データ生成部１０２_４は、第４の基本演算シード記憶部１０６_４から
2020165932.tif 000151
を取得する。また、第４のシェア再構成データ生成部１０２_４は、第４のデータ記憶部１０７_４から
2020165932.tif 000152
を取得する。
【００６０】
ここで、第２のシェア再構成データ生成部１０２_２、第３のシェア再構成データ生成部１０２_３および第４のシェア再構成データ生成部１０２_４は
2020165932.tif 000153
を計算する。第２のシェア再構成データ生成部１０２_２、第３のシェア再構成データ生成部１０２_３および第４のシェア再構成データ生成部１０２_４は、それぞれ、第２のデータ記憶部１０７_２、第３のデータ記憶部１０７_３および第４のデータ記憶部１０７_４に上記
2020165932.tif 000154
を送信する。
【００６１】
さらに第４のシェア再構成データ生成部１０２_４は、
2020165932.tif 000155
を用いて、
2020165932.tif 000156
を生成し、第１のシェア構成部１０３_１および第４のシェア構成部１０３_４に送信する。同様に第３のシェア再構成データ生成部１０２_３は、
2020165932.tif 000157
を生成し、第３のシェア構成部１０３_３に
2020165932.tif 000158
、第３のデータ記憶部１０７_３に
2020165932.tif 000159
を送信する。
【００６２】
ここで、
2020165932.tif 000160
である。
2020165932.tif 000161
は、たとえば、カウンタであり、各サーバ装置１００_１〜１００_４の間で共有している。
【００６３】
（ステップＡ３）
各シェア構成部１０３_１、１０３_２、１０３_３、１０３_４は各データ記憶部１０７_１、１０７_２、１０７_３、１０７_４からそれぞれ、
2020165932.tif 000162
、
2020165932.tif 000163
、
2020165932.tif 000164
、
2020165932.tif 000165
を取り出す。さらに、各シェア構成部１０４_１、１０４_２、１０４_３、１０４_４は上記ステップＡ２で送信された値を用いて、以下の８の式によりシェアを構成する。
2020165932.tif 000166
2020165932.tif 000167
2020165932.tif 000168
2020165932.tif 000169
2020165932.tif 000170
2020165932.tif 000171
2020165932.tif 000172
2020165932.tif 000173
2020165932.tif 000174
、
2020165932.tif 000175
は各ｉ番目のデータ記憶部１０８_ｉに記憶される。
【００６４】
このように、各シェア構成部１０３_ｉは、各サーバ装置１００_ｉが保持する値
2020165932.tif 000176
と、シェア再構成データ生成部１０２_ｉが生成したデータ（例えば、乱数ｒ、ｒ’、ｚ等）を用いて
2020165932.tif 000177
上の値ｘのシェア
2020165932.tif 000178
から
2020165932.tif 000179
上の値ｘ２のシェア
2020165932.tif 000180
と
2020165932.tif 000181
のシェア
2020165932.tif 000182
を再構成する。具体的には、上記８の式のうち上から４番目までの式は、
2020165932.tif 000183
に関する再構成されたシェアを示す。また、上記８の式のうち上から５番目〜８番目までの式は、
2020165932.tif 000184
に関する再構成されたシェアを示す。
【００６５】
上記８つの式のうち上から４番目までの式を確認すると、値ｘ２＝ｘ２_１＋ｘ２_２＋ｘ２_３とした場合、
ｘ２_１＝ｒ
ｘ２_２＝ｘ２-２ｒ
ｘ２_３＝ｒ
となり、第ｉのシェア再構成データ生成部１０２_ｉによる値ｘのシェアを再構成するためのデータ生成時に作られる乱数ｒは正しく生成されていることが分かる。つまり、第ｉのシェア再構成データ生成部１０２_ｉは、ある値ｘのシェアを再構成するためのデータを生成する際、ｘ＝ｘ１＋ｘ２＋ｘ３とした場合、ｘ１、ｘ２、ｘ３のうち２つの値が等しくなるように乱数を生成する。
【００６６】
さらに、上記８つの式のうち上から５番目〜８番目までの式を確認すると、
2020165932.tif 000185
とした場合、
2020165932.tif 000186
2020165932.tif 000187
2020165932.tif 000188
となり、第ｉのシェア再構成データ生成部１０２_ｉによる値
2020165932.tif 000189
のシェアを再構成するためのデータ生成時に作られる乱数ｒは正しく生成されていることが分かる。
つまり、第ｉのシェア再構成データ生成部１０２_ｉは、ある値ｘ’のシェアを再構成するためのデータを生成する際、ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合、ｒを乱数としてｘ１’＝ｘ’＋ｒ、ｘ２’＝０、ｘ３’＝-ｒとなるように乱数ｒを生成する。
【００６７】
（ステップＡ４）
各ｉ番目の算術演算部１０５_ｉが互いに通信することで、環上での排他的論理和処理
2020165932.tif 000190
を以下のように計算する。ここで、
2020165932.tif 000191
とは、
2020165932.tif 000192
、
2020165932.tif 000193
を入力とし、
2020165932.tif 000194
を出力する処理である。例えば、以下の式がなりたつ。
2020165932.tif 000195
ここで、
2020165932.tif 000196
である。各ｉ番目の算術演算部１０５_ｉは、
2020165932.tif 000197
を各データ記憶部１０７_ｉに記憶する。このように、算術演算部１０５_ｉは、ビット埋込用のシェアを用いて環上での排他的論理和を計算する。
【００６８】
（ステップＡ５）
第１のシェア再構成データ生成部１０２_１は、
2020165932.tif 000198
を第１のデータ記憶部１０７_１から取り出す。次に、第１のシェア再構成データ生成部１０２_１は、
2020165932.tif 000199
を、第４の不正検知部１０４_４に送信する。
【００６９】
第４の不正検知部１０４_４は、第４のデータ記憶部１０７_４に記憶されている
2020165932.tif 000200
を取り出し、
2020165932.tif 000201
、かつ、
2020165932.tif 000202
が成立するか否かを検証する。
【００７０】
成立した場合、第４の不正検知部１０４_４は、successの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部１０４_４は、abortの文字列を各サーバ装置１００_１、１００_２、１００_３、１００_４にブロードキャストし、秘密計算に関するプロトコルを中断する。
【００７１】
さらに第３の不正検知部１０４_３は、
2020165932.tif 000203
を第３のデータ記憶部１０７_３から取出し、
2020165932.tif 000204
を第１の不正検知部１０４_１に送信する。
【００７２】
第１の不正検知部１０４_１は、第１のデータ記憶部１０７_１から
2020165932.tif 000205
を取出し、
2020165932.tif 000206
が成り立つか否かを検証する。
【００７３】
2020165932.tif 000207
が成り立つ場合は、第１の不正検知部１０４_１はsuccessの文字列を各サーバ装置１００_２、１００_３、１００_４にブロードキャストし、次のステップに進む。
2020165932.tif 000208
が成り立たない場合は、第１の不正検知部１０４_１はabortの文字列を各サーバ装置１００_２、１００_３、１００_４にブロードキャストし、プロトコルを中断する。
【００７４】
なお、大量のビット埋込処理を並列に行う場合、
2020165932.tif 000209
、
2020165932.tif 000210
に関しては、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【００７５】
（ステップＡ６）
各ｉ番目の不正検知部１０４_ｉは、上記ステップＡ４の
2020165932.tif 000211
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置１００_１、１００_２、１００_３、１００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置１００_１、１００_２、１００_３、１００_４は、abortの文字列を各サーバ装置にブロードキャストし、秘密計算に関するプロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＡ６は上記ステップＡ５と並列に実行することが可能である。
【００７６】
このように、不正検知部１０４_ｉは、ビット埋込用のシェアや排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知する。
【００７７】
以上、説明した第１の実施形態においては、以下に記載するような効果を奏する。
【００７８】
第１の効果は、不正検知可能な４者間秘密計算を用いて、シェアのビット埋込が実行できる。複雑な混合回路を実行する際に不正検知に関するステップを並列に行った場合、不正検知に関する通信コストを消却できるものとする。このときの通信コストは、７ｎビット・２ラウンドとなる。一方で、非特許文献２と非特許文献３を組み合わせた場合のビット埋込の通信コストは、不正が成功する確率を２−４０としたとき、４２ｎビット・２ラウンドである。これより、本願開示の方が効率の良い方式となる（通信コストが低減される）。
【００７９】
第２の効果は、不正検知可能な４者間秘密計算を用いて、シェアのビット埋込を行う際に、不正検知確率が常に「１」となることである。非特許文献２と非特許文献３を組み合わせた場合、不正検知確率はパラメタライズであるため、不正検知確率を向上させようとした際に、通信コストも大きくなる。秘密計算を適用できるアプリケーションには様々なものがあり、そのアプリケーションに応じて求められる不正検知確率は異なる。求められる要件の調査と、調査に伴う各パラメータの設定は利用者にとって負担となる。本願開示では、不正検知確率が「１」なので、要件の調査やパラメータ設定の負担が軽減される。
【００８０】
［第２の実施形態］
図５〜図７を参照して、第２の実施形態に係るビット埋込処理システムについて説明する。
【００８１】
図５は、第２の実施形態によるビット埋込処理システムの機能構成例を示すブロック図である。第２の実施形態に係るビット埋込処理システムは、上述した第１の実施形態に係るビット埋込処理システムの変形例である。以下、第２の実施形態において、第１の実施形態において既に説明した部分と同等な機能を有する部分には同一符号を付し、説明を省略する。
【００８２】
図５を参照すると、第１の実施形態によるビット埋込処理システムは、後述する図６で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第２の実施形態によるビット埋込処理システムにおいて、サーバ装置２００_１、２００_２、２００_３、２００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図６は、第ｉのサーバ装置２００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【００８３】
図６に示すように、第ｉのサーバ装置２００_ｉは、第ｉのシェア再構成データ生成部２０２_ｉと、第ｉのシェア構成部２０３_ｉと、第ｉの不正検知部２０４_ｉと、第ｉの算術演算部２０５_ｉと、第ｉの基本演算シード記憶部２０６_ｉと、第ｉのデータ記憶部２０７_ｉと、を含む。なお、第ｉのシェア再構成データ生成部２０２_ｉ第ｉのシェア構成部２０３_ｉと、第ｉの不正検知部２０４_ｉと、第ｉの算術演算部２０５_ｉと、第ｉの基本演算シード記憶部２０６_ｉと、第ｉのデータ記憶部２０７_ｉとは、それぞれ接続されている。
【００８４】
このような構成のビット埋込処理システムにおいては、第１乃至第４のサーバ装置２００_１〜２００_４の内のいずれかの装置が入力した値
2020165932.tif 000212
、あるいは第１乃至第４のデータ記憶部２０７_１〜２０７_４に記憶されたシェア
2020165932.tif 000213
、あるいは第１乃至第４のサーバ装置２００_１〜２００_４ではない外部から入力されたシェア
2020165932.tif 000214
に対し、その入力や計算過程の値から
2020165932.tif 000215
の値を知られることなく、
2020165932.tif 000216
を計算し、第１乃至第４のデータ記憶部２０７_１〜２０７_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置２００_１〜２００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置２００_１〜２００_４ではない外部にシェアが送信され、復元してもよい。
【００８５】
次に、第２の実施形態におけるビット埋込処理システムおよび第１乃至第４のサーバ装置２００_１〜２００_４の動作について、詳細に説明する。図７は、第１乃至第４のサーバ装置２００_１〜２００_４のビット埋込に関する動作例を示すフローチャートである。
【００８６】
（ステップＢ１）
各基本演算シード記憶部２０６_１〜２０６_４は、それぞれ
2020165932.tif 000217
、
2020165932.tif 000218
、
2020165932.tif 000219
、
2020165932.tif 000220
を記憶する。
【００８７】
また、各サーバ装置２００_１〜２００_４は疑似ランダム関数
2020165932.tif 000221
を共有する。なお、
2020165932.tif 000222
とし、疑似ランダム関数
2020165932.tif 000223
とする。
【００８８】
また、各データ記憶部２０７_１〜２０７_４は、それぞれ
2020165932.tif 000224
を記憶する。ここで、
2020165932.tif 000225
は各データ記憶部１０８_ｉに記憶された
2020165932.tif 000226
である。
【００８９】
なお、
2020165932.tif 000227
に関して、サーバ装置２００_ｉ（ｉ＝１、２、３、）の内、ある一台の参加者は
2020165932.tif 000228
の出力を計算できず、他の三台の参加者は
2020165932.tif 000229
の出力を計算できるという状況を作ることを意図している。また、
2020165932.tif 000230
は、サーバ装置２００_１、２００_２、２００_３の内、ある一台の参加者は
2020165932.tif 000231
の出力を計算できず、他の二台の参加者は
2020165932.tif 000232
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165932.tif 000233
の扱いは特に制限されない。本書での
2020165932.tif 000234
はあくまでも一例である。
【００９０】
（ステップＢ２）
第１のシェア再構成データ生成部２０２_１と第２のシェア再構成データ生成部２０２_２はそれぞれ、第１の基本演算シード記憶部２０７_１、第２の基本演算シード記憶部２０６_２より、
2020165932.tif 000235
を取得する。
【００９１】
次に、第１のシェア再構成データ生成部２０２_１と第２のシェア再構成データ生成部２０２_２は
2020165932.tif 000236
を生成する。そして、第１のシェア再構成データ生成部２０２_１は、
2020165932.tif 000237
を第１のデータ記憶部２０７_１に記憶する。第２のシェア再構成データ生成部２０２_２は、
2020165932.tif 000238
を、第３のシェア構成部２０３_３に送信する。また、第２のシェア再構成データ生成部２０２_２は
2020165932.tif 000239
2020165932.tif 000240
を、第４のシェア構成部２０３_４に送信する。
【００９２】
同様に、第２のシェア再構成データ生成部２０２_２と第３のシェア再構成データ生成部２０２_３は
2020165932.tif 000241
を生成する。第２のシェア再構成データ生成部２０２_２は、
2020165932.tif 000242
を第２のデータ記憶部２０７_２に記憶する。第３のシェア再構成データ生成部２０２_３は、
2020165932.tif 000243
を、第１のシェア構成部２０３_１に送信する。また、第３のシェア再構成データ生成部２０２_３は
2020165932.tif 000244
2020165932.tif 000245
を、第４のシェア構成部２０３_４に送信する。
【００９３】
さらに同様に、第３のシェア再構成データ生成部２０２_３と第１のシェア再構成データ生成部２０２_１は
2020165932.tif 000246
を生成する。第３のシェア再構成データ生成部２０２_３は、
2020165932.tif 000247
を第３のデータ記憶部２０７_３に記憶する。第１のシェア再構成データ生成部２０２_１は、
2020165932.tif 000248
を、第２のシェア構成部２０３_２に送信する。また、第１のシェア再構成データ生成部２０２_１は
2020165932.tif 000249
2020165932.tif 000250
を、第４のシェア構成部２０３_４に送信する。
【００９４】
ここで、
2020165932.tif 000251
である。
2020165932.tif 000252
は、たとえば、カウンタであり、各サーバ装置２００_１〜２００_４の間で共有している。
【００９５】
（ステップＢ３）
各シェア構成部２０４_１、２０４_２、２０４_３、２０４_４は上記ステップＢ２で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165932.tif 000253
2020165932.tif 000254
2020165932.tif 000255
2020165932.tif 000256
2020165932.tif 000257
2020165932.tif 000258
2020165932.tif 000259
2020165932.tif 000260
2020165932.tif 000261
2020165932.tif 000262
2020165932.tif 000263
2020165932.tif 000264
2020165932.tif 000265
、
2020165932.tif 000266
、
2020165932.tif 000267
は各ｉ番目のデータ記憶部２０７_ｉに記憶される。
【００９６】
（ステップＢ４）
各ｉ番目の算術演算部２０５_ｉは互いに通信することで、環上での排他的論理和処理
2020165932.tif 000268
を以下のように計算する。ここで、
2020165932.tif 000269
とは、
2020165932.tif 000270
、
2020165932.tif 000271
を入力とし、
2020165932.tif 000272
を出力する処理である。例えば、以下の式が成り立つ。
2020165932.tif 000273
2020165932.tif 000274
ここで、
2020165932.tif 000275
である。各ｉ番目の算術演算部２０５_ｉは、
2020165932.tif 000276
を各データ記憶部２０７_ｉに記憶する。
【００９７】
（ステップＢ５）
第１のシェア再構成データ生成部２０２_１は、第１のデータ記憶部２０７_１から
2020165932.tif 000277
を取り出す。次に、第１のシェア再構成データ生成部２０２_１は、
2020165932.tif 000278
を、第３の不正検知部２０４_３に送信する。また、第１のシェア再構成データ生成部２０２_１は、
2020165932.tif 000279
2020165932.tif 000280
を、第４の不正検知部２０４_４に送信する。
【００９８】
第３の不正検知部２０４_３および第４の不正検知部２０４_４は、それぞれ、第３のデータ記憶部２０８_３に記憶されている
2020165932.tif 000281
、第４のデータ記憶部２０７_４に記憶されている
2020165932.tif 000282
を取出し、値が一致するか否かを検証する。
【００９９】
一致した場合、第３の不正検知部２０４_３又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第３の不正検知部２０４_３又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、秘密計算に関するプロトコルを中断する。
【０１００】
なお、大量のビット埋込処理を並列して行う場合、上記検証は、
2020165932.tif 000283
それぞれとを連結した値に対するハッシュ値と、
2020165932.tif 000284
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するか否かを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165932.tif 000285
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165932.tif 000286
2020165932.tif 000287
に関しても同様である。
【０１０１】
同様に、第２のシェア再構成データ生成部２０２_２は、
2020165932.tif 000288
を第２のデータ記憶部２０７_２から取り出す。次に、第２のシェア再構成データ生成部２０２_２は、
2020165932.tif 000289
を、第１の不正検知部２０４_１に送信する。また、第２のシェア再構成データ生成部２０２_２は、
2020165932.tif 000290
2020165932.tif 000291
を、第４の不正検知部２０４_４に送信する。
【０１０２】
第１の不正検知部２０４_１および第４の不正検知部２０４_４は、それぞれ、第１のデータ記憶部２０７_１に記憶されている
2020165932.tif 000292
、第４のデータ記憶部２０７_４に記憶されている
2020165932.tif 000293
を取出し、値が一致するか否かを検証する。
【０１０３】
一致した場合、第１の不正検知部２０４_１又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第１の不正検知部２０４_１又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、秘密計算に関するプロトコルを中断する。
【０１０４】
なお、大量のビット埋込処理を並列して行う場合、上記検証は、
2020165932.tif 000294
それぞれとを連結した値に対するハッシュ値と、
2020165932.tif 000295
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するか否かを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165932.tif 000296
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165932.tif 000297
2020165932.tif 000298
に関しても同様である。
【０１０５】
さらに同様に、第３のシェア再構成データ生成部２０２_３は、
2020165932.tif 000299
を第３のデータ記憶部２０８_３から取り出す。次に、第３のシェア再構成データ生成部２０２_３は、
2020165932.tif 000300
を、第２の不正検知部２０４_２に送信する。また、第３のシェア再構成データ生成部２０２_３は、
2020165932.tif 000301
2020165932.tif 000302
を、第４の不正検知部２０４_４に送信する。
【０１０６】
第２の不正検知部２０４_２および第４の不正検知部２０４_４は、それぞれ、第２のデータ記憶部２０７_２に記憶されている
2020165932.tif 000303
、第４のデータ記憶部２０７_４に記憶されている
2020165932.tif 000304
を取り出し、値が一致するか否かを検証する。
【０１０７】
一致した場合、第２の不正検知部２０４_２又は第４の不正検知部２０４_４は、successの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第２の不正検知部２０４_１又は第４の不正検知部２０４_４は、abortの文字列を各サーバ装置２００_１、２００_２、２００_３、２００_４にブロードキャストし、秘密計算に関するプロトコルを中断する。
【０１０８】
なお、大量のビット埋込処理を並列して行う場合、上記検証は、
2020165932.tif 000305
それぞれとを連結した値に対するハッシュ値と、
2020165932.tif 000306
に関する値それぞれとを連結した値に対するハッシュ値とで、一致するか否かを検証することにしてもよい。この場合、処理全体の通信量に対して、それぞれ
2020165932.tif 000307
を連結した値に対するハッシュ値は無視できるものと捉えることができる。
2020165932.tif 000308
2020165932.tif 000309
に関しても同様である。
【０１０９】
（ステップＢ６）
各ｉ番目の不正検知部２０４_ｉは、上記ステップＢ４の
2020165932.tif 000310
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置２００_１、２００_２、２００_３、２００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置２００_１、２００_２、２００_３、２００_４は、abortの文字列を各サーバ装置にブロードキャストし、秘密計算に関するプロトコルを中断する。これは上記の不正検知可能な４者間秘密計算によって実現される。ステップＢ６は上記ステップＢ５と並列に実行することが可能である。
【０１１０】
以上、説明した第２の実施形態においては、第１の実施形態における効果と同じ効果を奏する。ただし、第１の実施形態における第１の効果に関して、第２の実施形態では環上での排他的論理和計算に相当する
2020165932.tif 000311
の計算回数が増加していることに注意する。第１の実施形態では、ビット埋込に関して
2020165932.tif 000312
の計算を１回で実行できる。一方で第２の実施形態では、ビット埋込に関して
2020165932.tif 000313
の計算を２回で実行できる。通信コストとしては、１６ｎビット・３ラウンドとなる。
【０１１１】
上述のように、理論的な通信コストとしては、第２の実施形態の方が第１の実施形態よりも劣っているが、通信の形態が変化していることに注意されたい。たとえば、第１の実施形態における図４のステップＡ２では、第４のサーバ装置２００_４から、第１のサーバ装置２００_１への通信が発生している。一方で、第２の実施形態では、ビット埋込の実行にあたり、第４のサーバ装置２００_４から、第１のサーバ装置２００_１への通信が発生していない。このように通信の形態が変わるため、通信環境によっては第２の実施形態の方が、効率が良い場合がある。
【０１１２】
［第３の実施形態］
図８〜図１０を参照して、第３の実施形態に係るビット埋込処理システムについて説明する。
【０１１３】
図８は、第３の実施形態によるビット埋込処理システムの機能構成例を示すブロック図である。第３の実施形態に係るビット埋込処理システムは、上述した第１の実施形態および第２の実施形態に係るビット埋込処理システムの変形例である。以下、第３の実施形態において、第１の実施形態および第２の実施形態において既に説明した部分と同等な機能を有する部分には同一符号を付し、説明を省略する。
【０１１４】
図８を参照すると、第３の実施形態によるビット埋込処理システムは、後述する図９で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第３の実施形態によるビット埋込処理システムにおいて、サーバ装置３００_１、３００_２、３００_３、３００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図９は、第ｉのサーバ装置３００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０１１５】
図９に示すように、第ｉのサーバ装置３００_ｉは、第ｉのシェア再構成データ生成部３０２_ｉと、第ｉのシェア構成部３０３_ｉと、第ｉの不正検知部３０４_ｉと、第ｉの算術演算部２０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部３０７_ｉと、を含む。なお、第ｉのシェア再構成データ生成部３０２_ｉと、第ｉのシェア構成部３０３_ｉと、第ｉの不正検知部３０４_ｉと、第ｉの算術演算部２０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部３０７_ｉとは、それぞれ接続されている。
【０１１６】
このような構成のビット埋込処理システムにおいては、第１乃至第４のサーバ装置３００_１〜３００_４の内のいずれかの装置が入力した値
2020165932.tif 000314
、あるいは第１乃至第４のデータ記憶部３０７_１〜３０７_４に記憶されたシェア
2020165932.tif 000315
、あるいは第１乃至第４のサーバ装置３００_１〜３００_４ではない外部から入力されたシェア
2020165932.tif 000316
に対し、その入力や計算過程の値から
2020165932.tif 000317
の値を知られることなく、
2020165932.tif 000318
を計算し、第１乃至第４のデータ記憶部３０７_１〜３０７_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置３００_１〜３００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置３００_１〜３００_４ではない外部にシェアが送信され、復元されてもよい。
【０１１７】
次に、第３の実施形態におけるビット埋込処理システムおよび第１乃至第４のサーバ装置３００_１〜３００_４の動作について、詳細に説明する。図１０は、第１乃至第４のサーバ装置３００_１〜３００_４のビット埋込に関する動作例を示すフローチャートである。
【０１１８】
（ステップＣ１）
各基本演算シード記憶部１０６_１、１０６_２、１０６_３、１０６_４は、それぞれ
2020165932.tif 000319
、
2020165932.tif 000320
、
2020165932.tif 000321
、
2020165932.tif 000322
を記憶する。
【０１１９】
また、各サーバ装置３００_１〜３００_４は疑似ランダム関数
2020165932.tif 000323
を共有する。なお、
2020165932.tif 000324
とし、疑似ランダム関数
2020165932.tif 000325
とする。また、各データ記憶部３０７_１〜３０７_４に、それぞれ
2020165932.tif 000326
を記憶する。ここで、
2020165932.tif 000327
は各データ記憶部３０７_ｉに記憶された
2020165932.tif 000328
である。
【０１２０】
なお、
2020165932.tif 000329
に関して、サーバ装置３００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165932.tif 000330
の出力を計算できず、他の三台の参加者は
2020165932.tif 000331
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165932.tif 000332
の扱いは特に制限されない。本書での
2020165932.tif 000333
はあくまでも一例である。
【０１２１】
（ステップＣ２）
第１のシェア再構成データ生成部３０２_１、第２のシェア再構成データ生成部３０２_２及び第３のシェア再構成データ生成部３０２_３はそれぞれ、第１の基本演算シード記憶部１０６_１、第２の基本演算シード記憶部１０６_２、第３の基本演算シード記憶部１０６_３より、
2020165932.tif 000334
を取得する。
【０１２２】
次に、第１のシェア再構成データ生成部３０２_１、第２のシェア再構成データ生成部３０２_２及び第３のシェア再構成データ生成部３０２_３は
2020165932.tif 000335
を生成する。そして、第１のシェア再構成データ生成部３０２_１は、
2020165932.tif 000336
を第１のシェア構成部３０３_１に送信する。第３のシェア再構成データ生成部３０２_２は
2020165932.tif 000337
を、第３のシェア構成部３０３_４に送信する。
【０１２３】
第２のシェア再構成データ生成部３０２_２は、第２のデータ記憶部３０７_２から
2020165932.tif 000338
を取出し、
2020165932.tif 000339
を、第４のシェア構成部３０３_４に送信する。
【０１２４】
同様に、第１のシェア再構成データ生成部３０２_１、第２のシェア再構成データ生成部３０２_２及び第３のシェア再構成データ生成部３０２_３は
2020165932.tif 000340
を生成する。第２のシェア再構成データ生成部３０２_２は、
2020165932.tif 000341
を第２のシェア構成部３０３_２に送信する。第１のシェア再構成データ生成部３０２_３は、
2020165932.tif 000342
を第１のシェア構成部３０３_１に送信する。
【０１２５】
また、第３のシェア再構成データ生成部３０２_３は、第３のデータ記憶部３０７_２から
2020165932.tif 000343
を取出し、
2020165932.tif 000344
を、第４のシェア構成部３０３_４に送信する。
【０１２６】
さらに同様に、第１のシェア再構成データ生成部３０２_１、第２のシェア再構成データ生成部３０２_２及び第３のシェア再構成データ生成部３０２_３は
2020165932.tif 000345
を生成する。第３のシェア再構成データ生成部３０２_３は、
2020165932.tif 000346
を第３のシェア構成部３０３_３に送信する。第２のシェア再構成データ生成部３０２_２は、
2020165932.tif 000347
を第２のシェア構成部３０３_２に送信する。
【０１２７】
また、第１のシェア再構成データ生成部３０２_１は、第１のデータ記憶部３０７_１から
2020165932.tif 000348
を取出し、
2020165932.tif 000349
を第４のシェア構成部３０３_４に送信する。
【０１２８】
ここで、
2020165932.tif 000350
である。
2020165932.tif 000351
は、たとえば、カウンタであり、各サーバ装置３００_１〜３００_４の間で共有している。
【０１２９】
（ステップＣ３）
各シェア構成部３０４_１、３０４_２、３０４_３、３０４_４は上記ステップＣ２で送信された値と、各ｉ番目のデータ記憶部３０８_ｉに記憶された
2020165932.tif 000352
を用いて、以下の１２の式によりシェアを構成する。
2020165932.tif 000353
2020165932.tif 000354
2020165932.tif 000355
2020165932.tif 000356
2020165932.tif 000357
2020165932.tif 000358
2020165932.tif 000359
2020165932.tif 000360
2020165932.tif 000361
2020165932.tif 000362
2020165932.tif 000363
2020165932.tif 000364
2020165932.tif 000365
、
2020165932.tif 000366
、
2020165932.tif 000367
は各ｉ番目のデータ記憶部３０７_ｉに記憶される。
【０１３０】
このように、各シェア再構成データ生成部３０２_ｉは、シェアの再構成に使用される乱数を生成する。その際、各シェア再構成データ生成部３０２_ｉは、値
2020165932.tif 000368
に関するシェア再構成データを生成する際、値
2020165932.tif 000369
とした場合に、
2020165932.tif 000370
、
2020165932.tif 000371
及び
2020165932.tif 000372
のうち２つの値が等しくなるように、乱数を生成する。上記ステップＣ３の例では、例えば、
2020165932.tif 000373
のとき、
2020165932.tif 000374
となるように乱数が生成されている。
【０１３１】
（ステップＣ４）
各ｉ番目の算術演算部２０５_ｉは相互に通信することで、環上での排他的論理和処理
2020165932.tif 000375
を以下のように計算する。ここで、
2020165932.tif 000376
とは、
2020165932.tif 000377
、
2020165932.tif 000378
を入力とし、
2020165932.tif 000379
を出力する処理である。例えば、以下の式が成り立つ。
2020165932.tif 000380
2020165932.tif 000381
ここで、
2020165932.tif 000382
である。各ｉ番目の算術演算部２０５_ｉは、
2020165932.tif 000383
を各データ記憶部３０７_ｉに記憶する。
【０１３２】
（ステップＣ５）
第１のシェア再構成データ生成部３０２_１は、第１のデータ記憶部３０７_１から
2020165932.tif 000384
を取り出す。次に、第１のシェア再構成データ生成部３０２_１は、
2020165932.tif 000385
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０７_４に記憶されている
2020165932.tif 000386
を取出し、
2020165932.tif 000387
、かつ、
2020165932.tif 000388
が成り立つかを検証する。
【０１３３】
成り立つ場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、秘密計算に関するプロトコルを中断する。
【０１３４】
同様に、第２のシェア再構成データ生成部３０２_２は、第２のデータ記憶部３０７_２から
2020165932.tif 000389
を取り出す。次に、第２のシェア再構成データ生成部３０２_２は、
2020165932.tif 000390
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０７_４に記憶されている
2020165932.tif 000391
を取出し、
2020165932.tif 000392
が成立するか否かを検証する。
【０１３５】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、秘密計算に関するプロトコルを中断する。
【０１３６】
さらに同様に、第３のシェア再構成データ生成部３０２_３は、第３のデータ記憶部３０７_３から
2020165932.tif 000393
を取り出す。次に、第３のシェア再構成データ生成部３０２_３は、
2020165932.tif 000394
を、第４の不正検知部３０４_４に送信する。第４の不正検知部３０４_４は、第４のデータ記憶部３０７_４に記憶されている
2020165932.tif 000395
を取出し、
2020165932.tif 000396
が成立するか否かを検証する。
【０１３７】
成立した場合、第４の不正検知部３０４_４は、successの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、次のステップに進む。一致しなかった場合、第４の不正検知部３０４_４は、abortの文字列を各サーバ装置３００_１、３００_２、３００_３、３００_４にブロードキャストし、プロトコルを中断する。
【０１３８】
なお、大量のビット埋込処理を並列して行う場合、
2020165932.tif 000397
については、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０１３９】
（ステップＣ６）
各ｉ番目の不正検知部３０４_ｉは、上記ステップＣ４の
2020165932.tif 000398
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置３００_１、３００_２、３００_３、３００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置３００_１、３００_２、３００_３、３００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＣ６は上記ステップＣ５と並列に実行することが可能である。つまり、ビット埋込用のシェアを用いた不正行為者の有無を検知することと、排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知することは並列に実行することができる。
【０１４０】
以上、説明した第３の実施形態においては、第１の実施形態および第２の実施形態における効果と同じ効果を奏する。ただし、第２の実施形態における第１の効果に関して、第３の実施形態の方が通信コストの点で効率が良いことに注意する。第３の実施形態では、第２の実施形態と同様、環上での排他的論理和計算に相当する
2020165932.tif 000399
の計算を２回行うことで実行できる。第３の実施形態と第２の実施形態とで異なる点は、環上での排他的論理和計算前の再分散が効率よく行われている点である。不正検知に関する処理を並列に行った場合、第３の実施形態では、ビット埋込の通信コストとして、１３ｎビット・３ラウンドを要する。これより、第３の実施形態の方が第１又は第２の実施形態よりも通信コストの点で効率が良い。
【０１４１】
［第４の実施形態］
図１１〜図１３を参照して、第４の実施形態に係るビット埋込システムについて説明する。
【０１４２】
図１１は、第４の実施形態によるビット埋込システムの機能構成例を示すブロック図である。図１１を参照すると、第４の実施形態によるビット埋込処理システムは、後述する図１２で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第４の実施形態によるビット埋込処理システムにおいて、サーバ装置４００_１、４００_２、４００_３、４００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図１２は、第ｉのサーバ装置４００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０１４３】
図１２に示すように、第ｉのサーバ装置４００_ｉは、第ｉのマスク値計算部４０１_ｉと、第ｉのシェア構成部４０３_ｉと、第ｉの不正検知部４０４_ｉと、第ｉの算術演算部４０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部４０７_ｉと、を含む。なお、第ｉのマスク値計算部４０１_ｉと、第ｉのシェア構成部４０３_ｉと、第ｉの不正検知部４０４_ｉと、第ｉの算術演算部４０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部４０７_ｉとは、それぞれ接続されている。
【０１４４】
このような構成のビット埋込処理システムにおいては、第１乃至第４のサーバ装置４００_１〜４００_４の内のいずれかの装置が入力した値
2020165932.tif 000400
、あるいは第１乃至第４のデータ記憶部４０７_１〜４０７_４に記憶されたシェア
2020165932.tif 000401
、あるいは第１乃至第４のサーバ装置４００_１〜４００_４ではない外部から入力されたシェア
2020165932.tif 000402
に対し、その入力や計算過程の値から
2020165932.tif 000403
の値を知られることなく、
2020165932.tif 000404
を計算し、第１乃至第４のデータ記憶部４０７_１〜４０７_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置４００_１〜４００_４がシェアを送受信し、復元されてもよい。あるいは、第１乃至第４のサーバ装置４００_１〜４００_４ではない外部にシェアが送信され、復元されてもよい。
【０１４５】
次に、第４の実施形態におけるビット埋込処理システムおよび第１乃至第４のサーバ装置４００_１〜４００_４の動作について、詳細に説明する。図１３は、第１乃至第４のサーバ装置４００_１〜４００_４のビット埋込に関する動作例を示すフローチャートである。
【０１４６】
（ステップＤ１）
各基本演算シード記憶部１０６_１、１０６_２、１０６_３、１０６_４は、それぞれ
2020165932.tif 000405
、
2020165932.tif 000406
、
2020165932.tif 000407
、
2020165932.tif 000408
を記憶する。
【０１４７】
また、各サーバ装置４００_１〜４００_４は疑似ランダム関数
2020165932.tif 000409
を共有する。なお、
2020165932.tif 000410
とし、疑似ランダム関数
2020165932.tif 000411
とする。また、各データ記憶部４０７_１〜４０７_４に、それぞれ
2020165932.tif 000412
を記憶する。
【０１４８】
ここで、
2020165932.tif 000413
は各データ記憶部４０７_ｉに記憶された
2020165932.tif 000414
である。なお、
2020165932.tif 000415
に関して、サーバ装置４００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165932.tif 000416
の出力を計算できず、他の三台の参加者は
2020165932.tif 000417
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165932.tif 000418
の扱いは特に制限されない。本書での
2020165932.tif 000419
はあくまでも一例である。
【０１４９】
（ステップＤ２）
第１、第２、第３のマスク値計算部４０１_１、４０１_２、４０１_３は
2020165932.tif 000420
を計算し、第１、第２、第３のデータ記憶部４０７_１、４０７_２、４０７_３に
2020165932.tif 000421
を記憶する。第２のマスク値計算部４０１_２は、データ記憶部４０７_２からシェア
2020165932.tif 000422
を取り出す。
【０１５０】
第２のマスク値計算部４０１_２は、
2020165932.tif 000423
を生成し、
2020165932.tif 000424
を第４のサーバ装置４００_４に送信する。第４のサーバ装置４００_４は、第４のデータ記憶部４０７_４に
2020165932.tif 000425
を記憶する。
【０１５１】
ここで、
2020165932.tif 000426
である。
2020165932.tif 000427
は、たとえば、カウンタであり、各サーバ装置４００_１〜４００_４の間で共有している。
【０１５２】
（ステップＤ３）
各シェア構成部４０３_１、４０３_２、４０３_３、４０３_４は各データ記憶部４０７_１、４０７_２、４０７_３、４０７_４からそれぞれ、
2020165932.tif 000428
、
2020165932.tif 000429
、
2020165932.tif 000430
、
2020165932.tif 000431
を取り出し、以下の１６の式によりシェアを構成する。
2020165932.tif 000432
2020165932.tif 000433
2020165932.tif 000434
2020165932.tif 000435
2020165932.tif 000436
2020165932.tif 000437
2020165932.tif 000438
2020165932.tif 000439
2020165932.tif 000440
2020165932.tif 000441
2020165932.tif 000442
2020165932.tif 000443
2020165932.tif 000444
2020165932.tif 000445
2020165932.tif 000446
2020165932.tif 000447
2020165932.tif 000448
、
2020165932.tif 000449
、
2020165932.tif 000450
、
2020165932.tif 000451
は各ｉ番目のデータ記憶部４０７_ｉに記憶される。なお、３-１は
2020165932.tif 000452
上での3の乗法逆元を意味する。ここで、３と２ｎは互いに素なので、任意のｎ（≧２）に対して、
2020165932.tif 000453
上で３−１は存在する。
【０１５３】
（ステップＤ４）
各ｉ番目の算術演算部４０５ｉは互いに通信することで、環上での排他的論理和処理
2020165932.tif 000454
を以下のように計算する。ここで、
2020165932.tif 000455
とは、
2020165932.tif 000456
、
2020165932.tif 000457
を入力とし、
2020165932.tif 000458
を出力する処理である。例えば、以下の式が成り立つ。
2020165932.tif 000459
2020165932.tif 000460
2020165932.tif 000461
ここで、
2020165932.tif 000462
である。各ｉ番目の算術演算部４０５_ｉは、
2020165932.tif 000463
を各データ記憶部４０７_ｉに記憶する。
【０１５４】
（ステップＤ５）
第１のサーバ装置４００_１は、上記ステップＤ３における第２のサーバ装置４００_２と同様、第１のマスク値計算部４０１_１は、
2020165932.tif 000464
を生成し、
2020165932.tif 000465
を第４のサーバ装置４００_４に送信する。第４のサーバ装置４００_４は、第４のデータ記憶部４０７_４に
2020165932.tif 000466
を記憶する。第４の不正検知部４０４_４は、第４のデータ記憶部４０７_４から
2020165932.tif 000467
を取り出し、
2020165932.tif 000468
が成り立つか否かを検証する。
【０１５５】
2020165932.tif 000469
が成り立つ場合は、第４の不正検知部４０４_４はsuccessの文字列を各サーバ装置４００_１、４００_２、４００_３にブロードキャストし、次のステップに進む。
2020165932.tif 000470
が成り立たない場合は、第４の不正検知部４０４_４はabortの文字列を各サーバ装置４００_１、４００_２、４００_３にブロードキャストし、プロトコルを中断する。
【０１５６】
なお、大量のビット埋込処理を並列に行う際に、各ステップＤ５において
2020165932.tif 000471
を連結してハッシュ値
2020165932.tif 000472
を計算し、
2020165932.tif 000473
に対しても連結した値に対するハッシュ値
2020165932.tif 000474
を計算することで、
2020165932.tif 000475
が成り立つか否かの検証を
2020165932.tif 000476
が成り立つか否かの検証と捉えてもよい。このとき、
2020165932.tif 000477
に関する通信量は処理全体の計算量に対し、無視できるものと捉えることができる。
【０１５７】
（ステップＤ６）
各ｉ番目の不正検知部４０４_ｉは、上記ステップＤ４の
2020165932.tif 000478
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置４００_１、４００_２、４００_３、４００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置４００_１、４００_２、４００_３、４００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＤ６は上記ステップＤ５と並列に実行することが可能である。
【０１５８】
以上、第４の実施形態においては、第１乃至第３の実施形態における効果と同じ効果を奏する。ただし、第１乃至第３の実施形態それぞれにおける第１の効果に関して、通信の形態が異なる点に注意する。たとえば、第４の実施形態では、図１３のステップＤ２にて第２のサーバ装置４００_２から第４のサーバ装置４００_４に対する通信と、その検証のためのステップＤ５にて第１のサーバ装置４００_１から第４のサーバ装置４００_４に対する通信が発生している。これは上記
2020165932.tif 000479
の環上で実行される２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた不正検知可能な４者間ＭＰＣによる乗算に要する通信路の一部である。つまり、第４の実施形態ではビット埋込を行うにあたり、上記ＭＰＣによる乗算に要する通信路以外は必要としない。第１乃至第３の実施形態では、上記ＭＰＣによる乗算に要する通信路以外に、追加の通信が必要である。このため、通信環境によっては、第４の実施形態の方が効率の面で良い場合がある。なお、第４の実施形態によるビット埋込のコストは、大量の処理を並列に行う場合は、１６ｎビット・３ラウンドとなる。
【０１５９】
［第５の実施形態］
図１４〜図１６を参照して、第５の実施形態に係るビット埋込処理システムについて説明する。
【０１６０】
図１４は、第５の実施形態によるビット埋込処理システムの機能構成例を示すブロック図である。第５の実施形態に係るビット埋込処理システムは、上述した第１乃至第４の実施形態に係るビット埋込処理システムの変形例である。以下、第５の実施形態において、第１乃至第４の実施形態において既に説明した部分と同等な機能を有する部分には同一符号を付し、説明を省略する。
【０１６１】
図１４を参照すると、第５の実施形態によるビット埋込処理システムは、後述する図１５で参照される第ｉ（ｉ＝１、２、３、４）のサーバ装置から成る。第５の実施形態によるビット埋込処理システムにおいて、サーバ装置５００_１、５００_２、５００_３、５００_４は、自身と異なるサーバ装置とネットワーク経由で通信可能に接続されている。図１５は、第ｉのサーバ装置５００_ｉ（ｉ＝１、２、３、４）の機能構成例を示すブロック図である。
【０１６２】
図１５に示すように、第ｉのサーバ装置５００_ｉは、第ｉのマスク値計算部４０１_ｉと、第ｉのシェア再構成データ生成部５０２_ｉと、第ｉのシェア構成部５０３_ｉと、第ｉの不正検知部５０４_ｉと、第ｉの算術演算部５０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部５０７_ｉと、を含む。なお、第ｉのマスク値計算部４０１_ｉと、第ｉのシェア再構成データ生成部５０２_ｉと、第ｉのシェア構成部５０３_ｉと、第ｉの不正検知部５０４_ｉと、第ｉの算術演算部５０５_ｉと、第ｉの基本演算シード記憶部１０６_ｉと、第ｉのデータ記憶部５０７_ｉとは、それぞれ接続されている。
【０１６３】
このような構成のビット埋込処理システムにおいては、第１乃至第４のサーバ装置５００_１〜５００_４の内のいずれかの装置が入力した値
2020165932.tif 000480
、あるいは第１乃至第４のデータ記憶部５０７_１〜５０７_４に記憶されたシェア
2020165932.tif 000481
、あるいは第１乃至第４のサーバ装置５００_１〜５００_４ではない外部から入力されたシェア
2020165932.tif 000482
に対し、その入力や計算過程の値から
2020165932.tif 000483
の値を知られることなく、
2020165932.tif 000484
を計算し、第１乃至第４のデータ記憶部５０７_１〜５０７_４に記憶する。上述の計算結果のシェアは、第１乃至第４のサーバ装置５００_１〜５００_４がシェアを送受信し、復元されてよい。あるいは、第１乃至第４のサーバ装置５００_１〜５００_４ではない外部にシェアが送信され、復元されてもよい。
【０１６４】
次に、第５の実施形態におけるビット埋込処理システムおよび第１乃至第４のサーバ装置５００_１〜５００_４の動作について、詳細に説明する。図１５は、第１乃至第４のサーバ装置５００_１〜５００_４のビット埋込に関する動作例を示すフローチャートである。
【０１６５】
（ステップＥ１）
各基本演算シード記憶部１０６_１、１０６_２、１０６_３、１０６_４は、それぞれ
2020165932.tif 000485
、
2020165932.tif 000486
、
2020165932.tif 000487
、
2020165932.tif 000488
を記憶する。
【０１６６】
また、各サーバ装置５００_１〜５００_４は疑似ランダム関数
2020165932.tif 000489
を共有する。なお、
2020165932.tif 000490
とし、疑似ランダム関数
2020165932.tif 000491
とする。また、各データ記憶部５０７_１〜５０７_４に、それぞれ
2020165932.tif 000492
を記憶する。ここで、
2020165932.tif 000493
は各データ記憶部５０７_ｉに記憶された
2020165932.tif 000494
である。
【０１６７】
なお、
2020165932.tif 000495
に関して、サーバ装置５００_ｉ（ｉ＝１、２、３、４）の内、ある一台の参加者は
2020165932.tif 000496
の出力を計算できず、他の三台の参加者は
2020165932.tif 000497
の出力を計算できるという状況を作ることを意図している。この状況を作り出せるのであれば、
2020165932.tif 000498
の扱いは特に制限されない。本書での
2020165932.tif 000499
はあくまでも一例である。
【０１６８】
（ステップＥ２）
第１、第２、第３のマスク値計算部４０１_１、４０１_２、４０１_３は
2020165932.tif 000500
を計算し、第１、第２、第３のデータ記憶部５０７_１、５０７_２、５０７_３に
2020165932.tif 000501
を記憶する。第２のマスク値計算部４０１_２は、データ記憶部５０７_２からシェア
2020165932.tif 000502
を取り出す。第２のマスク値計算部４０１_２は、
2020165932.tif 000503
を生成し、
2020165932.tif 000504
を第４のサーバ装置５００_４に送信する。第４のサーバ装置５００_４は、第４のデータ記憶部５０７_４に
2020165932.tif 000505
を記憶する。
【０１６９】
ここで、
2020165932.tif 000506
である。
2020165932.tif 000507
は、たとえば、カウンタであり、各サーバ装置５００_１〜５００_４の間で共有している。
【０１７０】
第１のシェア再構成データ生成部５０２_１、第２のシェア再構成データ生成部５０２_２及び第３のシェア再構成データ生成部５０２_３はそれぞれ、第１の基本演算シード記憶部３０７_１、第２の基本演算シード記憶部３０７_２、第３の基本演算シード記憶部３０７_３より、
2020165932.tif 000508
を取得する。そして、
2020165932.tif 000509
を生成する。
【０１７１】
第２のシェア再構成データ生成部５０２_２は、
2020165932.tif 000510
を第２のシェア構成部５０３_２に送信する。第１のシェア再構成データ生成部５０２_１は、
2020165932.tif 000511
を第１のシェア構成部５０３_１に送信する。
【０１７２】
また、第３のシェア再構成データ生成部５０２_３は、第３のデータ記憶部５０７_２から
2020165932.tif 000512
を取出し、
2020165932.tif 000513
を、第４のシェア構成部５０３_４に送信する。
【０１７３】
ここで、
2020165932.tif 000514
である。
2020165932.tif 000515
は、たとえば、カウンタであり、各サーバ装置５００_１〜５００_４の間で共有している。
【０１７４】
（ステップＥ３）
各シェア構成部５０３_１、５０３_２、５０３_３、５０３_４は各データ記憶部５０７_１、５０７_２、５０７_３、５０７_４からそれぞれ、
2020165932.tif 000516
、
2020165932.tif 000517
、
2020165932.tif 000518
、
2020165932.tif 000519
を取り出す。さらに、各シェア構成部５０３_１、５０３_２、５０３_３、５０３_４は上記ステップＥ２で送信された値を用いて、以下の１２の式によりシェアを構成する。
2020165932.tif 000520
2020165932.tif 000521
2020165932.tif 000522
2020165932.tif 000523
2020165932.tif 000524
2020165932.tif 000525
2020165932.tif 000526
2020165932.tif 000527
2020165932.tif 000528
2020165932.tif 000529
2020165932.tif 000530
2020165932.tif 000531
2020165932.tif 000532
、
2020165932.tif 000533
、
2020165932.tif 000534
は各ｉ番目のデータ記憶部５０７_ｉに記憶される。
【０１７５】
このように、各シェア再構成データ生成部５０２_ｉは、シェアの再構成に使用される乱数を生成する。その際、各シェア再構成データ生成部５０２_ｉは、値
2020165932.tif 000535
に関するシェア再構成データを生成する際、値
2020165932.tif 000536
とした場合に、
2020165932.tif 000537
、
2020165932.tif 000538
及び
2020165932.tif 000539
のうち２つがゼロとなるように乱数を生成する。上記ステップＥ３の例では、例えば、
2020165932.tif 000540
のとき、
2020165932.tif 000541
となるように乱数が生成されている。
【０１７６】
（ステップＥ４）
各ｉ番目の算術演算部５０５_ｉは互いに通信することで、環上での排他的論理和処理
2020165932.tif 000542
を以下のように計算する。ここで、
2020165932.tif 000543
とは、
2020165932.tif 000544
、
2020165932.tif 000545
を入力とし、
2020165932.tif 000546
を出力する処理である。例えば、下記の式が成り立つ。
2020165932.tif 000547
2020165932.tif 000548
ここで、
2020165932.tif 000549
である。各ｉ番目の算術演算部５０５_ｉは、
2020165932.tif 000550
を各データ記憶部５０７_ｉに記憶する。
【０１７７】
（ステップＥ５）
第１のサーバ装置５００_１は、上記ステップＥ３における第２のサーバ装置５００_２と同様、第１のマスク値計算部４０１_１は、
2020165932.tif 000551
を生成し、
2020165932.tif 000552
を第４のサーバ装置５００_４に送信する。第４のサーバ装置５００_４は、第４のデータ記憶部５０７_４に
2020165932.tif 000553
を記憶する。第４の不正検知部５０４_４は、第４のデータ記憶部５０７_４から
2020165932.tif 000554
を取り出し、
2020165932.tif 000555
が成り立つか否かを検証する。
【０１７８】
2020165932.tif 000556
が成り立つ場合は、第４の不正検知部５０４_４はsuccessの文字列を各サーバ装置５００_１、５００_２、５００_３にブロードキャストし、次のステップに進む。
2020165932.tif 000557
が成り立たない場合は、第４の不正検知部５０４_４はabortの文字列を各サーバ装置５００_１、５００_２、５００_３にブロードキャストし、プロトコルを中断する。
【０１７９】
次に、第２のシェア再構成データ生成部５０２_２は、第２のデータ記憶部５０７_２から
2020165932.tif 000558
を取り出す。次に、第２のシェア再構成データ生成部５０２_２は、
2020165932.tif 000559
を、第４の不正検知部５０４_４に送信する。第４の不正検知部５０４_４は、第４のデータ記憶部５０７_４に記憶されている
2020165932.tif 000560
を取出し、
2020165932.tif 000561
が成立するか否かを検証する。
【０１８０】
成立した場合、第４の不正検知部５０４_４は、successの文字列を各サーバ装置５００_１、５００_２、５００_３、５００_４にブロードキャストし、次のステップに進む。成立しなかった場合、第４の不正検知部５０４_４は、abortの文字列を各サーバ装置５００_１、５００_２、５００_３、５００_４にブロードキャストし、プロトコルを中断する。
【０１８１】
なお、大量のビット埋込処理を並列して実行する場合、
2020165932.tif 000562
に関しては、それぞれの値を連結したものに対するハッシュ値を送信し、ハッシュ値同士の比較によって検証してもよい。このとき、処理全体の計算量に対して、ハッシュ値の送信量は無視できるものと捉えることができる。
【０１８２】
（ステップＥ６）
各ｉ番目の不正検知部５０４_ｉは、上記ステップＥ４の
2020165932.tif 000563
における送受信データを用いて、突き合わせることで不正検知を行う。不正が検知されなかった第１乃至第４のサーバ装置５００_１、５００_２、５００_３、５００_４は、successの文字列を各サーバ装置にブロードキャストする。不正が検知された第１乃至第４のサーバ装置５００_１、５００_２、５００_３、５００_４は、abortの文字列を各サーバ装置にブロードキャストし、プロトコルを中断する。これは上述の不正検知可能な４者間秘密計算によって実現される。ステップＥ６は上記ステップＥ５と並列に実行することが可能である。
【０１８３】
以上、説明した第５の実施形態においては、第１乃至第４の実施形態における効果と同じ効果を奏する。ただし、第１乃至第４の実施形態における第１の効果に関して、第５の実施形態は、通信の形態が異なる。このため、通信環境によっては、第５の実施形態の方が効率良く実行できる場合がある。なお、不正検知に関する処理を並列に行った場合、第５の実施形態では、ビット埋込の通信コストとして、１２ｎビット・３ラウンドを要する。
【０１８４】
［ハードウェア構成］
続いて、秘密計算システムをなす秘密計算サーバのハードウェア構成について説明する。
【０１８５】
図１７は、第ｉの秘密計算サーバ装置１００_ｉのハードウェア構成の一例を示す図である。第ｉの秘密計算サーバ装置１００_ｉは、所謂、情報処理装置（コンピュータ）により実現され、図１７に例示する構成を備える。例えば、第ｉの秘密計算サーバ装置１００_ｉは、内部バスにより相互に接続される、ＣＰＵ（Central Processing Unit）２１、メモリ２２、入出力インターフェイス２３、通信手段であるＮＩＣ（Network Interface Card）２４等を備える。
【０１８６】
但し、図１７に示す構成は、第ｉの秘密計算サーバ装置１００_ｉのハードウェア構成を限定する趣旨ではない。第ｉの秘密計算サーバ装置１００_ｉは、図示しないハードウェアを含んでもよい。第ｉの秘密計算サーバ装置１００_ｉに含まれるＣＰＵ等の数も図１７の例示に限定する趣旨ではなく、例えば、複数のＣＰＵ２１が第ｉの秘密計算サーバ装置１００_ｉに含まれていてもよい。
【０１８７】
メモリ２２は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、補助記憶装置（ハードディスク等）等である。
【０１８８】
入出力インターフェイス２３は、図示しない入出力装置のインターフェイスである。入出力装置には、例えば、表示装置、操作デバイス等が含まれる。表示装置は、例えば、液晶ディスプレイ等である。操作デバイスは、例えば、キーボードやマウス等である。
【０１８９】
第ｉの秘密計算サーバ装置１００_ｉの機能は、上述の処理モジュールにより実現される。当該処理モジュールは、例えば、メモリ２２に格納されたプログラムをＣＰＵ２１が実行することで実現される。また、そのプログラムは、ネットワークを介してダウンロードするか、あるいは、プログラムを記憶した記憶媒体を用いて、更新することができる。さらに、上記処理モジュールは、半導体チップにより実現されてもよい。即ち、上記処理モジュールが行う機能は、何らかのハードウェア、或いはハードウェアを利用して実行されるソフトウェアにより実現できればよい。
【０１９０】
［変形例］
なお、第１乃至第５の実施形態にて説明した秘密計算検証システムの構成及び動作は例示であって、種々の変形が可能である。例えば、上記実施形態では、４つの秘密計算サーバ装置１００_１〜１００_４が対等である場合を説明したが、１つのサーバ装置を代表サーバとして定めてもよい。この場合、代表サーバが秘密計算に用いるデータの入出力（入力データの分散及び配布、計算結果の復号）を制御してもよい。
【０１９１】
上述の説明で用いたフローチャートでは、複数の工程（処理）が順番に記載されているが、各実施形態で実行される工程の実行順序は、その記載の順番に制限されない。各実施形態では、例えば各処理を並行して実行する等、図示される工程の順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態は、内容が相反しない範囲で組み合わせることができる。即ち、上記各実施形態の任意の組み合わせが更なる実施形態として含まれる。
【０１９２】
上述の説明で用いたフローチャートでは、複数の工程（処理）が順番に記載されているが、各実施形態で実行される工程の実行順序は、その記載の順番に制限されない。各実施形態では、例えば各処理を並行して実行する等、図示される工程の順番を内容的に支障のない範囲で変更することができる。また、上述の各実施形態は、内容が相反しない範囲で組み合わせることができる。即ち、上記各実施形態の任意の組み合わせが更なる実施形態として含まれる。
【０１９３】
上記の説明により、本発明の産業上の利用可能性は明らかであるが、本発明は、たとえば、
2020165932.tif 000564
の環上で実行される２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた不正検知可能な４者間ＭＰＣにて、生体テンプレート照合や統計演算などの混合回路の計算を効率よく実現する場合に好適である。
【０１９４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
［付記１］
上述の第１の視点に係る情報処理装置のとおりである。
［付記２］
前記シェア再構成データ生成部は、前記シェアの再構成に使用される乱数を生成する、好ましくは付記１に記載の情報処理装置。
［付記３］
前記シェア再構成データ生成部は、値ｘ’に関する前記シェア再構成データを生成する際、値ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合に、ｘ１’、ｘ２’及びｘ３’のうち２つの値が等しくなるように、乱数を生成する、好ましくは付記２に記載の情報処理装置。
［付記４］
前記シェア再構成データ生成部は、値ｘ’に関する前記シェア再構成データを生成する際、値ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合に、ｘ１’、ｘ２’及びｘ３’のうち２つがゼロとなるように乱数を生成する、好ましくは付記２に記載の情報処理装置。
［付記５］
前記シェア再構成データ生成部は、値ｘに関する前記シェア再構成データを生成する際、値ｘ＝ｘ１＋ｘ２＋ｘ３とした場合に、ｘ１、ｘ２及びｘ３のうち２つの値が等しくなるように、乱数を生成すると共に、
値ｘ’に関する前記シェア再構成データを生成する際、ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合、ｘ１’＝ｘ’＋ｒ、ｘ２’＝０、ｘ３’＝-ｒとなるように乱数ｒを生成する、好ましくは付記２に記載の情報処理装置。
［付記６］
前記ビット埋込用のシェアを用いて不正行為者の有無を検知する、不正検知部をさらに備える、好ましくは付記１乃至５のいずれか一に記載の情報処理装置。
［付記７］
前記ビット埋込用のシェアを用いて環上での排他的論理和を計算する、算術演算部をさらに備え、
前記不正検知部は、前記排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知する、好ましくは付記６に記載の情報処理装置。
［付記８］
前記ビット埋込用のシェアを用いた不正行為者の有無を検知することと、前記排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知すること、が並列に実行される、好ましくは付記７に記載の情報処理装置。
［付記９］
シェアをマスクするためのマスク値を計算すると共に、前記計算されたマスク値によりマスクされたシェアを他の装置に送信する、マスク値計算部をさらに備え、
前記シェア構成部は、前記送信されたマスク値を用いて前記ビット埋込用のシェアを構成する、好ましくは付記１乃至８のいずれか一に記載の情報処理装置。
［付記１０］
前記不正検知部は、前記マスク値を用いて不正行為者の有無を検知する、好ましくは付記６乃至８のいずれか一項を引用する好ましくは付記６に記載の情報処理装置。
［付記１１］
前記不正検知部は、前記不正行為者を検知した場合には、秘密計算に関するプロトコルを中断する、好ましくは付記６乃至１０のいずれか一に記載の情報処理装置。
［付記１２］
上述の第２の視点に係る秘密計算方法のとおりである。
［付記１３］
上述の第３の視点に係るプログラムのとおりである。
なお、付記１２の形態及び付記１３の形態は、付記１の形態と同様に、付記２の形態〜付記１１の形態に展開することが可能である。
【０１９５】
なお、引用した上記の特許文献等の各開示は、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択（部分的削除を含む）が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１９６】
１０  情報処理装置
１１、１０６_１、２０６_１、１０６_ｉ、２０６_ｉ  基本演算シード記憶部
１２、１０２_１、２０２_１、３０２_１、４０２_１、５０２_１、１０２_ｉ〜５０２_ｉ  シェア再構成データ生成部
１３、１０３_１、２０３_１、３０３_１、４０３_１、５０３_１、１０３_ｉ〜５０３_ｉ  シェア構成部
２１  ＣＰＵ（Central Processing Unit）
２２  メモリ
２３  入出力インターフェイス
２４  ＮＩＣ（Network Interface Card）
１００_１〜１００_４、２００_１〜２００_４、３００_１〜３００_４、４００_１〜４００_４、５００_１〜５００_４、１００_ｉ〜５００_ｉ  秘密計算サーバ装置
４０１_１、４０１_ｉ  マスク値計算部
１０４_１、２０４_１、３０４_１、４０４_１、５０４_１、１０４_ｉ〜５０４_ｉ  不正検知部
１０５_１、２０５_１、３０５_１、４０５_１、５０５_１、１０５_ｉ〜５０５_ｉ  算術演算部
１０７_１、２０７_１、３０７_１、４０７_１、５０７_１、１０７_ｉ〜５０７_ｉ  データ記憶部
【図１】
2020165932.tif 000565
【図２】
2020165932.tif 000566
【図３】
2020165932.tif 000567
【図４】
2020165932.tif 000568
【図５】
2020165932.tif 000569
【図６】
2020165932.tif 000570
【図７】
2020165932.tif 000571
【図８】
2020165932.tif 000572
【図９】
2020165932.tif 000573
【図１０】
2020165932.tif 000574
【図１１】
2020165932.tif 000575
【図１２】
2020165932.tif 000576
【図１３】
2020165932.tif 000577
【図１４】
2020165932.tif 000578
【図１５】
2020165932.tif 000579
【図１６】
2020165932.tif 000580
【図１７】
2020165932.tif 000581
【手続補正書】
【提出日】令和3年8月11日(2021.8.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部と、
前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する、シェア再構成データ生成部と、
少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成する、シェア構成部と、
を備える、情報処理装置。
【請求項２】
前記シェア再構成データ生成部は、前記シェアの再構成に使用される乱数を生成する、請求項１に記載の情報処理装置。
【請求項３】
前記シェア再構成データ生成部は、値ｘ’に関する前記シェア再構成データを生成する際、値ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合に、ｘ１’、ｘ２’及びｘ３’のうち２つの値が等しくなるように、乱数を生成する、請求項２に記載の情報処理装置。
【請求項４】
前記シェア再構成データ生成部は、値ｘ’に関する前記シェア再構成データを生成する際、値ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合に、ｘ１’、ｘ２’及びｘ３’のうち２つがゼロとなるように乱数を生成する、請求項２に記載の情報処理装置。
【請求項５】
前記シェア再構成データ生成部は、値ｘに関する前記シェア再構成データを生成する際、値ｘ＝ｘ１＋ｘ２＋ｘ３とした場合に、ｘ１、ｘ２及びｘ３のうち２つの値が等しくなるように、乱数を生成すると共に、
値ｘ’に関する前記シェア再構成データを生成する際、ｘ’＝ｘ１’＋ｘ２’＋ｘ３’とした場合、ｘ１’＝ｘ’＋ｒ、ｘ２’＝０、ｘ３’＝-ｒとなるように乱数ｒを生成する、請求項２に記載の情報処理装置。
【請求項６】
前記ビット埋込用のシェアを用いて不正行為者の有無を検知する、不正検知部をさらに備える、請求項１乃至５のいずれか一項に記載の情報処理装置。
【請求項７】
前記ビット埋込用のシェアを用いて環上での排他的論理和を計算する、算術演算部をさらに備え、
前記不正検知部は、前記排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知する、請求項６に記載の情報処理装置。
【請求項８】
前記ビット埋込用のシェアを用いた不正行為者の有無を検知することと、前記排他的論理和の計算時に送受信されたデータを用いて不正行為者の有無を検知すること、が並列に実行される、請求項７に記載の情報処理装置。
【請求項９】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部を備える情報処理装置において、
前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成するステップと、
少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成するステップと、
を含む、秘密計算方法。
【請求項１０】
シェアについての演算を行う際の乱数を生成するためのシードを格納する、基本演算シード記憶部を備える情報処理装置に搭載されたコンピュータに、
前記シードを用いてビット埋込を行う際に用いられるシェアを再構成するためのシェア再構成データを生成する処理と、
少なくとも前記シェア再構成データを用いてビット埋込用のシェアを構成する処理と、
を実行させるプログラム。
【請求項１１】
前記情報処理装置は、ネットワークを介して第２乃至第４の前記情報処理装置と通信接続し、前記情報処理装置と第２乃至第４の前記情報処理装置は、２−ｏｕｔ−ｏｆ−４複製型秘密分散を用いた４者間ＭＰＣのサーバを構成する請求項１乃至８のいずれか一項に記載の情報処理装置。
【国際調査報告】
2020165932.tif 000582
2020165932.tif 000583