(57)【要約】  秘密計算装置は、一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る。ただし、表Ｍ（ｉ０，…，ｉＳ−１）にカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）がＭｂ，２，１，…，Ｍｂ，３，２の何れかである行列Ｍｂ，γ，μである。秘密計算装置は、秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝および秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によって、秘匿情報｛Ｍｂ，γ，μ｝を得、処理Ｐｊ，１、処理Ｐｊ，２、処理Ｐｊ，３、および処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る。
2019039381.tif 000002
【特許請求の範囲】
【請求項１】
Ｂが１以上の整数であり、Ｒが３以上の整数であり、Ｓが２以上の整数であり、Ｕ＝Ｓ２であり、Ｆが有限体であり、ｂ＝０，…，Ｂ−１であり、ｒ＝１，…，Ｒであり、ｊ＝２，…，Ｒであり、
１ラウンド目のラウンド処理が処理Ｐ１，４を含み、前記処理Ｐ１，４が１ラウンド目のラウンド鍵ｋ１∈ＦＵの要素からなるＳ×Ｓ行列の１つの列のＳ個の要素にＳ個のカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１をそれぞれ加算して行列Ｍｂ，１，４を得る処理を含み、
ｊラウンド目のラウンド処理が処理Ｐｊ，１と処理Ｐｊ，２と処理Ｐｊ，３と処理Ｐｊ，４とを含み、前記処理Ｐｊ，１が前記行列Ｍｂ，ｊ−１，４の各要素を置換して行列Ｍｂ，ｊ，１を得る処理を含み、前記処理Ｐｊ，２が前記行列Ｍｂ，ｊ，１の各要素を行ごとに巡回シフトして行列Ｍｂ，ｊ，２を得る処理を含み、前記処理Ｐｊ，３が前記行列Ｍｂ，ｊ，２の各列のＳ個の要素の線形和を当該列のＳ個の要素とした行列Ｍｂ，ｊ，３を得る処理を含み、前記処理Ｐｊ，４が前記行列Ｍｂ，ｊ，３の各要素にｊラウンド目のラウンド鍵ｋｊの各要素を加算して行列Ｍｂ，ｊ，４を得る処理を含み、
何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る前段処理を行う表生成部と、
前記表Ｍ（ｉ０，…，ｉＳ−１）に前記カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）がＭｂ，２，１，…，Ｍｂ，３，２の何れかである行列Ｍｂ，γ，μであり、前記カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１の秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝および前記秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によってｂ＝０，…，Ｂ−１についての前記行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得る表計算部と、
何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および前記秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算により、ｊ＝２，…，Ｒについての前記処理Ｐｊ，１、前記処理Ｐｊ，２、前記処理Ｐｊ，３、および前記処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行うラウンド処理部と、
を有する秘密計算装置。
【請求項２】
請求項１の秘密計算装置であって、
前記表生成部は、前記前段処理での改ざんを検知するための第１チェックサムを第１方式に則って生成し、
前記ラウンド処理部は、前記後段処理での改ざんを検知するための第２チェックサムを第２方式に則って生成し、
前記第１方式は、改ざん検知対象である秘匿情報の復元値のデータ量に、安全性の高さが依存しない方式であり、
前記第２方式は、改ざん検知対象である秘匿情報の復元値のデータ量がα１であるときの安全性が、改ざん検知対象である秘匿情報の復元値のデータ量がα２であるときの安全性よりも高い方式であり、α１がα２よりも大きい、秘密計算装置。
【請求項３】
請求項２の秘密計算装置であって、
Ｔ，Λ，Ｗ，Ｙ，Ｑ，Θが１以上の整数であり、ｔ＝０，…，Ｔ−１であり、λ＝０，…，Λ−１であり、ｗ＝０，…，Ｗ−１であり、ｙ＝０，…，Ｙ−１であり、ｑ＝０，…，Ｑ−１であり、θ＝０，…，Θ−１であり、前記前段処理はＴ種類の秘密分散方式ｍｅｔｈ０，…，ｍｅｔｈＴ−１に則った秘匿情報を用いた秘密計算を含み、
（１）前記第１チェックサムを前記第１方式に則って生成する処理は、
（１−１）乱数ｒｔを秘密分散した秘匿情報｛ｒｔ｝を得る処理と、
（１−２）前記秘密分散方式ｍｅｔｈｔに則った秘匿情報｛ａλ｝を用いた秘密計算を行う際に、前記秘匿情報｛ａλ｝と前記秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ａλｒｔ｝を得、前記秘匿情報｛ａλ｝と前記秘匿情報｛ａλｒｔ｝との組であるランダム化分散値＜ａλ＞＝＜｛ａλ｝，｛ａλｒｔ｝＞を得、前記ランダム化分散値＜ａλ＞の追加によってＣ１，ｔを更新し、
前記秘密分散方式ｍｅｔｈｔに則った秘密計算結果である秘匿情報｛ｈｗ｝が得られた際に、前記秘匿情報｛ｈｗ｝と前記秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｈｗｒｔ｝を得、前記秘匿情報｛ｈｗ｝と前記秘匿情報｛ｈｗｒｔ｝との組であるランダム化分散値＜ｈｗ＞＝＜｛ｈｗ｝，｛ｈｗｒｔ｝＞を得、前記ランダム化分散値＜ｈｗ＞の追加によってＣ１，ｔを更新することで、
Ｃ１，ｔを含む前記第１チェックサムを更新する処理と、を含み、
（２）前記第２チェックサムを前記第２方式に則って生成する処理は、
（２−１）行列Ｍ０，γ，μ，…，ＭＢ−１，γ，μの要素からなる非ランダム化列Ａ∈ＦＵＢの秘匿情報｛Ａ｝とＹ個のダミーブロックＤ０，…，ＤＹ−１∈ＦＵの秘匿情報｛Ｄ０｝，…，｛ＤＹ−１｝とを結合した秘匿情報｛Ａ｜Ｄ｝＝｛Ａ｜Ｄ０｜…｜ＤＹ−１｝を得る処理と、
（２−２）前記秘匿情報｛Ａ｜Ｄ｝を用い、Ａ｜Ｄをランダム置換して得られるランダム化列Πｑ＝πｑ（Ａ｜Ｄ）∈ＦＵ（Ｂ＋Ｙ）の秘匿情報｛Πｑ｝＝｛πｑ（Ａ｜Ｄ）｝を秘密計算によって得る処理と、
（２−３）前記秘匿情報｛Ａ｝を用い、前記非ランダム化列Ａを構成する前記行列Ｍｂ，γ，μのＵ個の要素に対応する秘匿情報｛Ｍｂ，γ，μ｝ごとにサブ処理Ｓｕｂ０，…，ＳｕｂΘ−１の秘密計算を実行して、前記非ランダム化列Ａを構成する前記行列Ｍｂ，γ，μの要素に前記残存処理を適用して得られる前記行列Ｍｂ，Γ，ＭＵの前記秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得、前記秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得るまでの過程で得られるサブ処理Ｓｕｂθの秘密計算結果でＣ２，Ａを更新し、
前記秘匿情報｛Πｑ｝を用い、前記ランダム化列Πｑを構成するＵ個の要素に対応する秘匿情報ごとに前記サブ処理Ｓｕｂ０，…，ＳｕｂΘ−１の秘密計算を実行することで得られる各サブ処理Ｓｕｂθの秘密計算結果でＣ２，Π＿ｑを更新し、
少なくとも一部の前記ダミーブロックＤｙに対して前記サブ処理Ｓｕｂ０，…，ＳｕｂΘ−１を実行することで得られる各サブ処理Ｓｕｂθの演算結果の秘匿情報でＣ２，Ｄを更新することで、
Ｃ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄを含む前記第２チェックサムを更新する処理と、を含む秘密計算装置。
【請求項４】
請求項３の秘密計算装置であって、
前記ラウンド処理部は、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および前記ダミーブロックＤ０，…，ＤＹ−１の何れかである要処理ダミーブロックＤＰの秘匿情報｛ＤＰ｝を用い、前記要処理ダミーブロックＤＰに前記残存処理を行って得られる処理結果の秘匿情報を得るダミー後段処理をさらに行い、前記ダミー後段処理での改ざんを検知するための第３チェックサムを第３方式に則って生成し、
前記第３方式は、改ざん検知対象である秘匿情報の復元値のデータ量に、安全性の高さが依存しない方式である、秘密計算装置。
【請求項５】
請求項４の秘密計算装置であって、
（３）前記第３チェックサムを前記第３方式に則って生成する処理は、
前記秘密分散方式ｍｅｔｈｔに則った秘匿情報｛ｄλ｝を用いた秘密計算を行う際に、前記秘匿情報｛ｄλ｝と前記秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｄλｒｔ｝を得、前記秘匿情報｛ｄλ｝と前記秘匿情報｛ｄλｒｔ｝との組であるランダム化分散値＜ｄλ＞＝＜｛ｄλ｝，｛ｄλｒｔ｝＞を得、前記ランダム化分散値＜ｄλ＞の追加によってＣ３，ｔを更新し、
前記秘密分散方式ｍｅｔｈｔに則った秘密計算結果である秘匿情報｛ｈ’ｗ｝が得られた際に、前記秘匿情報｛ｈ’ｗ｝と前記秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｈ’ｗｒｔ｝を得、前記秘匿情報｛ｈ’ｗ｝と前記秘匿情報｛ｈ’ｗｒｔ｝との組であるランダム化分散値＜ｈ’ｗ＞＝＜｛ｈ’ｗ｝，｛ｈ’ｗｒｔ｝＞を得、前記ランダム化分散値＜ｈ’ｗ＞の追加によってＣ３，ｔを更新することで、
Ｃ３，ｔを含む前記第３チェックサムを更新する処理を含む、秘密計算装置。
【請求項６】
請求項３から５の何れかの秘密計算装置であって、
ｐがＢより大きな素数であり、Ｙ＝ｐ−Ｂである、秘密計算装置。
【請求項７】
請求項３から６の何れかの秘密計算装置であって、
前記ランダム置換はランダム巡回シフトである、秘密計算装置。
【請求項８】
請求項１から７の何れかの秘密計算装置であって、
前記行列Ｍｂ，γ，μはＭｂ，３，１またはＭｂ，３，２である、秘密計算装置。
【請求項９】
Ｂが１以上の整数であり、Ｒが３以上の整数であり、Ｓが２以上の整数であり、Ｕ＝Ｓ２であり、Ｆが体であり、ｂ＝０，…，Ｂ−１であり、ｒ＝１，…，Ｒであり、ｊ＝２，…，Ｒであり、
１ラウンド目のラウンド処理が処理Ｐ１，４を含み、前記処理Ｐ１，４が１ラウンド目のラウンド鍵ｋ１∈ＦＵの要素からなるＳ×Ｓ行列の１つの列のＳ個の要素にＳ個のカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１をそれぞれ加算して行列Ｍｂ，１，４を得る処理を含み、
ｊラウンド目のラウンド処理が処理Ｐｊ，１と処理Ｐｊ，２と処理Ｐｊ，３と処理Ｐｊ，４とを含み、前記処理Ｐｊ，１が前記行列Ｍｂ，ｊ−１，４の各要素を置換して行列Ｍｂ，ｊ，１を得る処理を含み、前記処理Ｐｊ，２が前記行列Ｍｂ，ｊ，１の各要素を行ごとに巡回シフトして行列Ｍｂ，ｊ，２を得る処理を含み、前記処理Ｐｊ，３が前記行列Ｍｂ，ｊ，２の各列のＳ個の要素の線形和を当該列のＳ個の要素とした行列Ｍｂ，ｊ，３を得る処理を含み、前記処理Ｐｊ，４が前記行列Ｍｂ，ｊ，３の各要素にｊラウンド目のラウンド鍵ｋｊの各要素を加算して行列Ｍｂ，ｊ，４を得る処理を含み、
表生成部が、何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る前段処理を行う表生成ステップと、
前記表Ｍ（ｉ０，…，ｉＳ−１）に前記カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）がＭｂ，２，１，…，Ｍｂ，３，２の何れかである行列Ｍｂ，γ，μであり、表計算部が、前記カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１の秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝および前記秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によってｂ＝０，…，Ｂ−１についての前記行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得る表計算ステップと、
ラウンド処理部が、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および前記秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算により、ｊ＝２，…，Ｒについての前記処理Ｐｊ，１、前記処理Ｐｊ，２、前記処理Ｐｊ，３、および前記処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行うラウンド処理ステップと、
を有する秘密計算方法。
【請求項１０】
請求項１から８の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。
【請求項１１】
請求項１から８の何れかの秘密計算装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はブロック暗号の秘密計算技術に関する。
【背景技術】
【０００２】
共通鍵暗号方式の一つにＡＥＳ（Advanced Encryption Standard）がある（例えば、非特許文献１等参照）。ＡＥＳでは、要素の置換と行の巡回シフトと列の線形和とラウンド鍵の加算とを繰り返すラウンド処理によって暗号化を行う。また、平文を所定長のブロックごとに暗号化する暗号利用モードの一つにＣＴＲモードがある。ＡＥＳがＣＴＲモードで実装された場合、各ブロックでラウンド処理が行われ、それによって得られた各ブロックの鍵の暗号文が各ブロックの平文に加算される。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Daniel J. Bernstein, Peter Schwabe, “New AES software speed records,” INDOCRYPT 2008, Progress in Cryptology - INDOCRYPT 2008 pp. 322 - 336.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、要素の置換と行の巡回シフトと列の線形和とラウンド鍵の加算とを繰り返すラウンド処理を秘密計算によって効率的に実行することである。
【課題を解決するための手段】
【０００５】
Ｂが１以上の整数であり、Ｒが３以上の整数であり、Ｓが２以上の整数であり、Ｕ＝Ｓ２であり、Ｆが有限体である。ｂ＝０，…，Ｂ−１であり、ｒ＝１，…，Ｒであり、ｊ＝２，…，Ｒであり、１ラウンド目のラウンド処理が処理Ｐ１，４を含み、処理Ｐ１，４が１ラウンド目のラウンド鍵ｋ１∈ＦＵの要素からなるＳ×Ｓ行列の１つの列のＳ個の要素にＳ個のカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１をそれぞれ加算して行列Ｍｂ，１，４を得る処理を含む。ｊラウンド目のラウンド処理が処理Ｐｊ，１と処理Ｐｊ，２と処理Ｐｊ，３と処理Ｐｊ，４とを含み、処理Ｐｊ，１が行列Ｍｂ，ｊ−１，４の各要素を置換して行列Ｍｂ，ｊ，１を得る処理を含み、処理Ｐｊ，２が行列Ｍｂ，ｊ，１の各要素を行ごとに巡回シフトして行列Ｍｂ，ｊ，２を得る処理を含み、処理Ｐｊ，３が行列Ｍｂ，ｊ，２の各列のＳ個の要素の線形和を当該列のＳ個の要素とした行列Ｍｂ，ｊ，３を得る処理を含み、処理Ｐｊ，４が行列Ｍｂ，ｊ，３の各要素にｊラウンド目のラウンド鍵ｋｊの各要素を加算して行列Ｍｂ，ｊ，４を得る処理を含む。【０００６】
秘密計算装置は、何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る前段処理を行う。ただし、表Ｍ（ｉ０，…，ｉＳ−１）にカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）がＭｂ，２，１，…，Ｍｂ，３，２の何れかである行列Ｍｂ，γ，μである。秘密計算装置は、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１の秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝および秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によってｂ＝０，…，Ｂ−１についての行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算により、ｊ＝２，…，Ｒについての処理Ｐｊ，１、処理Ｐｊ，２、処理Ｐｊ，３、および処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行う。
【発明の効果】
【０００７】
本発明では、要素の置換と行の巡回シフトと列の線形和とラウンド鍵の加算とを繰り返すラウンド処理を秘密計算によって効率的に実行できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の秘密計算システムを例示したブロック図である。
【図２】図２は実施形態の秘密計算装置の機能構成を例示したブロック図である。
【図３】図３Ａは実施形態の表生成部の機能構成を例示したブロック図である。図３Ｂは実施形態のラウンド処理部の機能構成を例示したブロック図である。
【図４】図４は実施形態の処理全体を説明するための概念図である。
【図５】図５は通常のブロック暗号化を説明するための概念図である。
【図６】図６は実施形態の暗号化処理を説明するためのフロー図である。
【図７】図７は実施形態の表生成処理の詳細を説明するためのフロー図である。
【図８】図８は実施形態のラウンド処理の詳細を説明するためのフロー図である。
【図９】図９は実施形態のラウンド処理の詳細を説明するためのフロー図である。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施形態を説明する。
［第１実施形態］
まず、第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の秘密計算システム１はＮ個の秘密計算装置１０−０〜１０−（Ｎ−１）を有する。Ｎは１以上の整数である。例えば、秘密分散によって得られたシェアを用いて秘密計算を行う場合にはＮ≧２であり、準同型暗号文を用いて秘密計算を行う場合にはＮ≧１である。Ｎ≧２の場合、秘密計算装置１０−０〜１０−（Ｎ−１）はネットワークを通じて通信可能に構成される。
【００１０】
図２に例示するように、本形態の秘密計算装置１０−ｎ（ただし、ｎ＝０，…，Ｎ−１）は、初期記憶部１００１−ｎ、表記憶部１００２−ｎ、カウンタ更新部１００３−ｎ、表生成部１０１０−ｎ、表計算部１０２０−ｎ、ラウンド処理部１０３０−ｎ、加算部１０４１−ｎ、および制御部１０５１−ｎを有する。秘密計算装置１０−ｎは制御部１０５１−ｎの制御の下で各処理を実行する。各処理で得られたデータは図示していないメモリに記憶される。メモリに格納されたデータは必要に応じて読み出され、各処理に利用される。
【００１１】
図３Ａに例示するように、表生成部１０１０−ｎは、秘密計算部１０１１−ｎおよび制御部１０１２−ｎを有する。図３Ｂに例示するように、ラウンド処理部１０３０−ｎは、秘密計算部１０３１−ｎおよび制御部１０３２−ｎを有する。
【００１２】
＜処理の概要＞
図４および図５に例示するように、本形態の秘密計算装置１０−ｎは、１，…，Ｒ＋１ラウンド目のラウンド鍵ｋ１，…，ｋＲ＋１∈ＦＵの秘匿情報｛ｋ１｝，…，｛ｋＲ＋１｝∈｛ＦＵ｝、および各ブロックｂ＝０，…，Ｂ−１のカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１∈Ｆの秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝∈｛Ｆ｝を用い、秘密計算により、各ブロックｂ＝０，…，Ｂ−１でブロック暗号化を行う。次に秘密計算装置１０−ｎは、各ブロックｂ＝０，…，Ｂ−１のブロック暗号化で得られた秘匿情報と、暗号化対象の平文ＰをＢ個のブロックに分割して得られた平文ブロックＰ０，…，ＰＢ−１∈ＦＵの秘匿情報｛Ｐ０｝，…，｛ＰＢ−１｝∈｛ＦＵ｝とを秘密計算によって加算（例えば、排他的論理和）する。ただし、Ｂは１以上の整数であり、Ｒは３以上の整数であり、Ｓは２以上の整数であり、Ｕ＝Ｓ２であり、Ｆは有限体である。有限体Ｆの例は基礎体に基づく拡大体である。基礎体の例は素数を法とした剰余からなる集合であり、当該基礎体での演算結果は当該素数を法とした剰余として得られる。例えば、Ｆは位数２の基礎体を８次拡大した拡大体ＧＦ（２８）である。例えば、基礎体の元が２バイトのデータである場合、拡大体ＧＦ（２８）の元は１バイト（＝８ビット）のデータとなる。この場合、拡大体ＧＦ（２８）によって２５６通りの値を表現できる。Ｆαはα個の有限体Ｆの元を要素とする集合を意味する。また、α∈βはαがβに属することを意味する。｛β｝はα∈βの秘匿情報｛α｝が属する集合を意味する。
【００１３】
≪ブロック暗号化≫
本形態のブロック暗号化では、表を用い、通常のブロック暗号化処理を効率化する。図５に例示するように、通常のブロック暗号化処理は、１〜Ｒ＋１ラウンドのラウンド処理を含む。例えば、ＡＥＳをＣＴＲモードで実装したブロック暗号化処理は、鍵長が１２８ビットの場合には１〜１１ラウンドの処理を、鍵長が１９２ビットの場合には１〜１３ラウンドの処理を、鍵長が２５６ビットの場合には１〜１５ラウンドの処理をそれぞれ含む。
【００１４】
１ラウンド目のラウンド処理は加算処理Ｐ１，４（処理Ｐ１，４）を含む。加算処理Ｐ１，４は１ラウンド目のラウンド鍵ｋ１∈ＦＵの要素からなるＳ×Ｓ行列の１つの列のＳ個の要素にＳ個のカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１をそれぞれ加算して行列Ｍｂ，１，４を得る処理を含む。ＡＥＳの場合、加算処理Ｐ１，４は１ラウンド目のＡｄｄＲｏｕｎｄＫｅｙに相当する。
【００１５】
ｊラウンド目（ただし、ｊ＝２，…，Ｒ）のラウンド処理は、要素の置換を行う置換処理Ｐｊ，１（処理Ｐｊ，１）と、行の巡回シフトを行うシフト処理Ｐｊ，２（処理Ｐｊ，２）と、列の線形和を行う混合処理Ｐｊ，３（処理Ｐｊ，３）と、ラウンド鍵の加算を行う加算処理Ｐｊ，４（処理Ｐｊ，４）とを含む。ＡＥＳの場合、置換処理Ｐｊ，１はＳｕｂＢｙｔｅｓに相当し、シフト処理Ｐｊ，２はＳｈｉｆｔＲｏｗｓに相当し、混合処理Ｐｊ，３はＭｉｘＣｏｕｍｎｓに相当し、加算処理Ｐｊ，４はＡｄｄＲｏｕｎｄＫｅｙに相当する。置換処理Ｐｊ，１は、行列Ｍｂ，ｊ−１，４の各要素を置換して行列Ｍｂ，ｊ，１を得る処理を含む。例えば、置換処理Ｐｊ，１は行列Ｍｂ，ｊ−１，４の各要素を予め定められた手順（例えば、Ｓ−ｂｏｘ）に則って置換して行列Ｍｂ，ｊ，１を得る処理である。ＡＥＳの場合、行列Ｍｂ，ｊ−１，４の各要素に対し、既約多項式ｘ８＋ｘ４＋ｘ３＋ｘ＋１による拡大体ＧＦ（２８）上の乗法逆元演算を行い、さらにアフィン変換を行った結果によって各要素を置換して行列Ｍｂ，ｊ，１を得る（参考文献１：情報セキュリティ対策基盤整備事業「電子政府推奨暗号の実装」，独立行政法人情報処理推進機構）。シフト処理Ｐｊ，２は、行列Ｍｂ，ｊ，１の各要素を行ごとに巡回シフトして行列Ｍｂ，ｊ，２を得る処理を含む。例えば、シフト処理Ｐｊ，２は、行列Ｍｂ，ｊ，１のι＋１（ただし、ι＝０，…，Ｐ−１）行目の行を所定の方向（例えば、左方向）にι要素分だけ巡回シフトする処理である。混合処理Ｐｊ，３は、行列Ｍｂ，ｊ，２の各列のＳ個の要素の線形和を当該列のＳ個の要素とした行列Ｍｂ，ｊ，３を得る処理を含む。これらの線形和の各項の係数は行ごとに相違する。加算処理Ｐｊ，４は、行列Ｍｂ，ｊ，３の各要素にｊラウンド目のラウンド鍵ｋｊの各要素を加算して行列Ｍｂ，ｊ，４を得る処理を含む。
【００１６】
Ｒ＋１ラウンド目のラウンド処理は、要素の置換を行う置換処理ＰＲ＋１，１と、行の巡回シフトを行うシフト処理ＰＲ＋１，２と、ラウンド鍵の加算を行う加算処理ＰＲ＋１，４とを含む。
【００１７】
≪本形態のブロック暗号化≫
本形態のブロック暗号化の特徴を説明する。前述のように、１ラウンド目の加算処理Ｐ１，４では、ラウンド鍵ｋ１の要素からなるＳ×Ｓ行列の１つの列のＳ個の要素にＳ個のカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１をそれぞれ加算して行列Ｍｂ，１，４を得る。Ｓ＝４、Ｕ＝１６、ラウンド鍵ｋ１＝（ｋ１，０，…，ｋ１，１５）の場合、行列Ｍｂ，１，４は例えば以下のようになる。
【数１】
2019039381.tif 000003
ただし、ｎ０，…，ｎ１１∈Ｆは任意値である。ｎ０＝…＝ｎ１１＝０であってもよい。ＡＥＳではｎ０，…，ｎ１１はｎｏｎｃｅに相当する。
【００１８】
２ラウンド目の置換処理Ｐ２，１は、行列Ｍｂ，１，４の各要素を予め定められた手順に則って置換して行列Ｍｂ，ｊ，１を得る。この処理は行列Ｍｂ，１，４の要素ごとに行われる。そのため、各要素の置換処理を関数ｆｓ：Ｆ→Ｆで表現できる。Ｓ＝４、Ｕ＝１６、ラウンド鍵ｋ１＝（ｋ１，０，…，ｋ１，１５）の場合、行列Ｍｂ，２，１は以下のようになる。
【数２】
2019039381.tif 000004
【００１９】
ラウンド鍵ｋ１および任意値ｎ０，…，ｎ１２は全ブロックｂ＝０，…，Ｂ−１で共通であり、定数とみなせる。ブロックｂ＝０，…，Ｂ−１ごとに異なるのはカウンタ値ｉｂ，０，…，ｉｂ，３である。カウンタ値ｉｂ，０，…，ｉｂ，３をカウンタ値の変数ｉ０，…，ｉ３とすると、式（２）は以下のように変形できる。
【数３】
2019039381.tif 000005
ここで、ｆ１，０，…，ｆ１，１１は全ブロックｂ＝０，…，Ｂ−１に共通であるため定数とみなせ、ｆ１，１２（ｉ３），…，ｆ１，１５（ｉ０）は変数ｉ＝ｉ０，…，ｉ３に対する一変数関数値である。つまり、各ブロックｂ＝０，…，Ｂ−１の行列Ｍｂ，２，１は、変数ｉ＝ｉ０，…，ｉ３に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉ３）として一般化できる。このことはＳ＝４の場合のみならず、その他のＳの場合も同様である。すなわち、各ブロックｂ＝０，…，Ｂ−１の行列Ｍｂ，２，１は、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として一般化できる。
【００２０】
２ラウンド目のシフト処理Ｐ２，２は、行列Ｍｂ，２，１の各要素を行ごとに巡回シフトして行列Ｍｂ，２，２を得る処理である。式（３）の行列Ｍｂ，２，１のι＋１行目の行を左方向にι要素分だけ巡回シフトすると以下の行列Ｍｂ，２，２が得られる。
【００２１】
【数４】
2019039381.tif 000006
このように、各ブロックｂ＝０，…，Ｂ−１の行列Ｍｂ，２，２も、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として一般化できる。
【００２２】
２ラウンド目の混合処理Ｐ２，３は、行列Ｍｂ，２，２の各列のＳ個の要素の線形和を当該列のＳ個の要素とした行列Ｍｂ，２，３を得る処理である。式（４）の行列Ｍｂ，２，２に対して混合処理Ｐ２，３を行うと例えば以下のようになる。
【数５】
2019039381.tif 000007
ただし、
【数６】
2019039381.tif 000008
である。ｘ０，…，ｘ１１は全ブロックｂ＝０，…，Ｂ−１で共通であるため定数とみなせ、ｘ１２，…，ｘ１５は変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値である。そのため、式（５）は以下のように変形できる。
【数７】
2019039381.tif 000009
ただし、ｆ２，ｓ（ｉ）（ただし、ｓ＝０，…，Ｓ−１、ｉ＝ｉ０，…，ｉＳ−１）は一変数関数値である。つまり、行列Ｍｂ，２，３も、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として一般化できる。
【００２３】
その後の２ラウンド目の加算処理Ｐ２，４および３ラウンド目の置換処理Ｐ３，１は要素ごとの処理であるため、加算処理Ｐ２，４によって得られる行列Ｍｂ，２，４および置換処理Ｐ３，１によって得られる行列Ｍｂ，３，１も変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として一般化できる。さらに、３ラウンド目のシフト処理Ｐ３，２は要素を巡回シフトするだけであるため、それによって得られる行列Ｍｂ，３，２も変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として一般化できる。例えば、行列Ｍｂ，３，２は以下のようになる。
【数８】
2019039381.tif 000010
すなわち、行列Ｍｂ，２，１，…，Ｍｂ，３，２は変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として一般化できる。ここで、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）に、各ブロックｂのカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入すると、各ブロックｂでの行列Ｍ（ｉｂ，０，…，ｉｂ，Ｓ−１）が得られる。表Ｍ（ｉ０，…，ｉＳ−１）の要素は一変数関数値または定数とみなせる。そのため、表Ｍ（ｉ０，…，ｉＳ−１）の各要素は有限体Ｆの元のデータ量以下で表現でき、表Ｍ（ｉ０，…，ｉＳ−１）全体はそのＵ倍のデータ量以下で表現できる。例えば、Ｓ＝４であり、有限体ＦがＧＦ（２８）であってその元のとり得る値の数が２５６通りである場合、表Ｍ（ｉ０，…，ｉＳ−１）の各要素のとり得る値の数は２５６通り以下となり、表全体では１バイト×２５６通り×１６個＝４０９６バイト以下のデータ量となる。一方、３ラウンド目の混合処理Ｐ３，３以降では、得られる行列を変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表として表現できず（多変数関数値を要素に持つ表となってしまい）、表のサイズが大きくなってしまう。
【００２４】
以上の特徴を利用し、秘密計算装置１０−ｎは、まず、何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る。ただし、表Ｍ（ｉ０，…，ｉＳ−１）にカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）が行列Ｍｂ，γ，μである。行列Ｍｂ，γ，μはＭｂ，２，１，…，Ｍｂ，３，２の何れかである（γ＝２，３、μ＝１，…，４）。次に、秘密計算装置１０−ｎは、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１の秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝および秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によってｂ＝０，…，Ｂ−１についての行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得る。これにより、少ない演算量で行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得ることができる。特に、秘密計算で置換処理を行う場合には、秘密計算装置１０−０〜１０−（Ｎ−１）間で通信を行う必要がある。秘匿情報｛Ｍ（ｉ０，…，ｉＳ−）｝を用いればこの通信を削減できる。特にＭｂ，γ，μがＭｂ，３，１またはＭｂ，３，２である場合、２回の置換処理Ｐ２，１，Ｐ２，２に必要な通信を削減できる。鍵長を１２８ビットとすると、この削減は２０％の通信量の削減となり、２５％の高速化を実現できる。
【００２５】
その後、秘密計算装置１０−ｎは、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算により、残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行う。後段処理は、ｊ＝２，…，Ｒについての置換処理Ｐｊ，１、シフト処理Ｐｊ，２、混合処理Ｐｊ，３、および加算処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む。例えば、Γ＝Ｒ＋１，ＭＵ＝４である場合、秘密計算装置１０−ｎは、後段処理によって秘匿情報｛Ｍｂ，Ｒ＋１，４｝を得て出力する。
【００２６】
＜処理の詳細＞
図６から図１１を用い、処理の詳細を説明する。
≪前提≫
前提として、初期記憶部１００１−ｎにラウンド鍵ｋ１，…，ｋＲ＋１の秘匿情報｛ｋ１｝，…，｛ｋＲ＋１｝、カウンタ値ｉ０，０，…，ｉ０，Ｓ−１の秘匿情報｛ｉ０，０｝，…，｛ｉ０，Ｓ−１｝、平文ブロックＰ０，…，ＰＢ−１の秘匿情報｛Ｐ０｝，…，｛ＰＢ−１｝が格納されているものとする。秘匿情報は、秘密分散方式に則ったシェア（秘密分散値）であってもよいし、準同型暗号方式に則った暗号文（RSA暗号方式やElGamal暗号方式などの暗号文）であってもよい。なお、秘密分散方式に則った秘匿情報を用いた秘密計算の方法は、例えば、千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能３パーティ秘匿関数計算の再考”，ＣＳＳ２０１０，２０１０年（参考文献２）、「Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10」（参考文献３）等に記載されている。
【００２７】
≪ステップＳ１０１０−ｎ≫
表生成部１０１０−ｎは、何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る前段処理を行う。ただし、表Ｍ（ｉ０，…，ｉＳ−１）にカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）が何れかの行列Ｍｂ，γ，μ＝Ｍｂ，２，１，…，Ｍｂ，３，２となる。すなわち、表生成部１０１０−ｎの秘密計算部１０１１−ｎが、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を変数ｉ０，…，ｉＳ−１とし、制御部１０１２−ｎの制御の下、必要となるラウンド鍵ｋ１，…，ｋＲの秘匿情報を用い、加算処理Ｐ１，４から何れかの処理Ｐγ，μ（ただし、Ｐγ，μはＰ２，１，…，Ｐ３，２の何れか）までを秘密計算によって実行して（ステップＳ１０１１−ｎ）、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る。例えば、Ｍｂ，γ，μ＝Ｍｂ，２，１の場合、表生成部１０１０−ｎの秘密計算部１０１１−ｎは、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を変数ｉ０，…，ｉＳ−１とし、秘匿情報｛ｋ１｝，｛ｋ２｝を用い、１ラウンド目の加算処理Ｐ１，４と２ラウンド目の置換処理Ｐ２，１とを秘密計算によって実行し、置換処理Ｐ２，１によって得られる行列の秘匿情報を秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝として得て出力する（例えば、式（３）の秘匿情報）。例えば、Ｍｂ，γ，μ＝Ｍｂ，３，１の場合、表生成部１０１０−ｎの秘密計算部１０１１−ｎは、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を変数ｉ０，…，ｉＳ−１とし、秘匿情報｛ｋ１｝，｛ｋ２｝，｛ｋ３｝を用い、１ラウンド目の加算処理Ｐ１，４、２ラウンド目の置換処理Ｐ２，１、シフト処理Ｐ２，２、混合処理Ｐ２，３、加算処理Ｐ２，４、３ラウンド目の置換処理Ｐ３，１を秘密計算によって実行し、置換処理Ｐ３，１によって得られる行列の秘匿情報を秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝として得て出力する。例えば、Ｍｂ，γ，μ＝Ｍｂ，３，２の場合、表生成部１０１０−ｎの秘密計算部１０１１−ｎは、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を変数ｉ０，…，ｉＳ−１とし、秘匿情報｛ｋ１｝，｛ｋ２｝，｛ｋ３｝を用い、１ラウンド目の加算処理Ｐ１，４、２ラウンド目の置換処理Ｐ２，１、シフト処理Ｐ２，２、混合処理Ｐ２，３、加算処理Ｐ２，４、３ラウンド目の置換処理Ｐ３，１、シフト処理Ｐ３，２を秘密計算によって実行し、シフト処理Ｐ３，２によって得られる行列の秘匿情報を秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝として得て出力する（例えば、式（８）の秘匿情報）。秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝は表記憶部１００２−ｎに格納される。
【００２８】
≪ステップＳ１０２０−ｎ≫
カウンタ更新部１００３−ｎは、初期記憶部１００１−ｎに格納されたカウンタ値ｉ０，０，…，ｉ０，Ｓ−１の秘匿情報｛ｉ０，０｝，…，｛ｉ０，Ｓ−１｝を用い、秘密計算によって、ブロックｂ’＝２，…，Ｂ−１のカウンタ値ｉｂ’，０，…，ｉｂ’，Ｓ−１の秘匿情報｛ｉｂ’，０｝，…，｛ｉｂ’，Ｓ−１｝を得て出力する。カウンタ値ｉｂ’，０，…，ｉｂ’，Ｓ−１は、カウンタ値ｉ０，０，…，ｉ０，Ｓ−１に予め定められた規則を適用することで得られる値である。例えば、カウンタ値ｉｂ’−１，０，…，ｉｂ’−１，Ｓ−１によって表現される値ｉｂ’−１，０…ｉｂ’−１，Ｓ−１を所定値（例えば、１）だけ増加させた値ｉｂ’−１，０…ｉｂ’−１，Ｓ−１＋１を表現する値をカウンタ値ｉｂ’，０，…，ｉｂ’，Ｓ−１とする。表計算部１０２０−ｎは、初期記憶部１００１−ｎから読み出したか、または、カウンタ更新部１００３−ｎから出力された秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝、および表記憶部１００２−ｎから読み出した秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によって、ｂ＝０，…，Ｂ−１について、行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝＝｛Ｍ（ｉｂ，０，…，ｉｂ，Ｓ−１）｝を得て出力する。
【００２９】
≪ステップＳ１０３０−ｎ≫
ラウンド処理部１０３０−ｎは、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算（ステップＳ１０３１ｂ−ｎ）により、残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行う。残存処理は、ｊ＝２，…，Ｒについての置換処理Ｐｊ，１、シフト処理Ｐｊ，２、混合処理Ｐｊ，３、および加算処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む処理である。処理Ｐγ，μは、表計算部１０２０−ｎで得られた秘匿情報｛Ｍｂ，γ，μ｝＝｛Ｍ（ｉｂ，０，…，ｉｂ，Ｓ−１）｝に対応する。例えば、Ｍｂ，γ，μ＝Ｍｂ，３，２かつΓ＝Ｒ＋１，ＭＵ＝４の場合、ラウンド処理部１０３０−ｎは、秘匿情報｛ｋ３｝，…｛ｋＲ＋１｝および秘匿情報｛Ｍｂ，３，２｝を用い、秘密計算により、３ラウンド目の混合処理Ｐ３，３からＲラウンド目の加算処理ＰＲ，４までを実行し、さらにＲ＋１ラウンド目の置換処理ＰＲ＋１，１、シフト処理ＰＲ＋１，２、加算処理ＰＲ＋１，４を実行して得られる行列Ｍｂ，Ｒ＋１，４の秘匿情報｛Ｍｂ，Ｒ＋１，４｝を得て出力する。
【００３０】
≪ステップＳ１０４１−ｎ≫
加算部１０４１−ｎは、各ブロックｂ＝０，…，Ｂ−１について、秘匿情報｛Ｍｂ，Ｒ＋１，４｝および秘匿情報｛Ｐｂ｝を入力とし、秘密計算によってＣｂ＝Ｍｂ，Ｒ＋１，４＋Ｐｂ∈ＦＵの秘匿情報｛Ｃｂ｝を得て出力する。
【００３１】
＜本形態の特徴＞
以上のように、本形態では表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を生成し、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用いて秘密計算によって各ブロックｂ＝０，…，Ｂ−１の秘匿情報｛Ｍｂ，γ，μ｝を得る。表Ｍ（ｉ０，…，ｉＳ−１）のサイズはＦのＵ倍のデータ量以下で表現でき、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用いて各ブロックｂ＝０，…，Ｂ−１の処理を行うことで演算量を削減できる。さらに、Ｍｂ，γ，μがＭｂ，３，１またはＭｂ，３，２である場合には、２回の置換処理Ｐ２，１，Ｐ２，２の秘密計算に必要な通信を削減できる。このように、本形態では、要素の置換と行の巡回シフトと列の線形和とラウンド鍵の加算とを繰り返すラウンド処理を秘密計算によって効率的に実行できる。
【００３２】
［第２実施形態］
第２実施形態は第１実施形態の変形例であり、改ざん検知を行うためのチェックサムを生成し、改ざん検知を行う。ただし、前述のように、表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得るまでの前段処理で処理されるデータ量は小さい。一方、前段処理の後に行われる後段処理で処理されるデータ量は格段に大きくなる。本形態では、これらの違いに応じ、異なる方式でチェックサムを生成する。これにより、安全に効率的な暗号化を行うことができる。以下では第１実施形態との相違点を中心に説明し、既に説明した事項については、同じ参照番号を用いて説明を簡略化する。
【００３３】
＜構成＞
図１に例示するように、本形態の秘密計算システム２はＮ個の秘密計算装置２０−０〜２０−（Ｎ−１）を有する。Ｎは１以上の整数である。Ｎ≧２の場合、秘密計算装置２０−０〜２０−（Ｎ−１）はネットワークを通じて通信可能に構成される。
【００３４】
図２に例示するように、本形態の秘密計算装置２０−ｎ（ただし、ｎ＝０，…，Ｎ−１）は、初期記憶部１００１−ｎ、表記憶部１００２−ｎ、カウンタ更新部１００３−ｎ、表生成部２０１０−ｎ、表計算部１０２０−ｎ、ラウンド処理部２０３０−ｎ、加算部１０４１−ｎ、同期部２０４２−ｎ、正当性検証部２０４３−ｎ，２０４４−ｎ、および制御部１０５１−ｎを有する。秘密計算装置２０−ｎは制御部１０５１−ｎの制御の下で各処理を実行する。各処理で得られたデータは図示していないメモリに記憶される。メモリに格納されたデータは必要に応じて読み出され、各処理に利用される。
【００３５】
図３Ａに例示するように、表生成部２０１０−ｎは、秘密計算部１０１１−ｎ、制御部１０１２−ｎ、乱数生成部２０１５−ｎ、およびチェックサム更新部２０１６−ｎを有する。図３Ｂに例示するように、ラウンド処理部２０３０−ｎは、秘密計算部１０３１−ｎ、制御部１０３２−ｎ、ダミーブロック生成部２０３５ａ−ｎ、秘匿化部２０３５ｂ−ｎ、結合部２０３５ｃ−ｎ、ランダム置換部２０３６−ｎ、およびチェックサム更新部２０３７，２０３８を有する。
【００３６】
＜処理の概要＞
本形態では、処理データ量が小さい前段処理と処理データ量が格段に大きくなる後段処理とで互いに異なる方式によってチェックサムを生成する。すなわち、表生成部２０１０が、前段処理での改ざんを検知するための第１チェックサムを第１方式に則って生成し、ラウンド処理部２０３０が、後段処理での改ざんを検知するための第２チェックサムを第２方式に則って生成する。ここで、第１方式は、改ざん検知対象である秘匿情報の復元値のデータ量に、安全性の高さが依存しない方式である。第１方式の例としては、「Dai Ikarashi, Ryo Kikuchi, Koki Hamada, and Koji Chida, “Actively Private and Correct MPC Scheme in t < n/2 from Passively Secure Schemes with Small Overhead,” Cryptology ePrint Archive, Report 2014/304, 2014.（参考文献４）」および国際公開第WO/2016/104476号（参考文献５）に記載された方式を例示できる。一方、第２方式は、改ざん検知対象である秘匿情報の復元値のデータ量に、安全性の高さが依存する方式である。すなわち、第２方式は、改ざん検知対象である秘匿情報の復元値のデータ量がα１であるときの安全性が、改ざん検知対象である秘匿情報の復元値のデータ量がα２であるときの安全性よりも高い方式である。ただし、α１がα２よりも大きい。例えば、第２方式は、改ざん検知対象である秘匿情報の復元値のデータ量が多いほど安全性が高い方式である。第２方式の例としては、「五十嵐大，菊池亮，濱田浩気，千田浩司，“少パーティ数の秘密分散ベース秘密計算における効率的なmaliciousモデル上SIMD計算の構成法，”コンピュータセキュリティシンポジウム2013論文集 2013(4), 793-800, 2013-10-14（参考文献６）」および国際公開第WO/2015/053184号（参考文献７）に記載された方式を例示できる。ただし、参考文献６，７には明記されていないが、さらなる高速化のためにはランダム置換としてランダム巡回シフト（ランダムローテーション）が用いられることが望ましい。同様に、参考文献６，７には明記されていないが、さらなる高速化のためには、生成されるダミーブロックの個数Ｙとブロック数Ｂとの合計がブロック数Ｂよりも大きな素数ｐであることが望ましい。すなわち、Ｙ＝ｐ−Ｂであることが望ましい。より好ましくは、ｐがブロック数Ｂよりも大きな最小の素数であることが望ましい。また、参考文献６，７の方式は、ダミーブロックが秘匿化されずに計算可能であることを前提としている。しかし、本形態ではダミーブロックも秘匿情報として処理される。そのため、本形態ではダミーブロックの何れかを要処理ダミーブロックとし、要処理ダミーブロックに対するチェックサムを第３方式によって生成する。これによってより高い安全性を担保する。なお、第３方式は、改ざん検知対象である秘匿情報の復元値のデータ量に、安全性の高さが依存しない方式である。例えば、第３方式は第１方式と同じ方式である。
【００３７】
＜処理の詳細＞
図６から図１１を用い、処理の詳細を説明する。
≪前提≫
第１実施形態と同じである。
【００３８】
≪ステップＳ２０１０−ｎ≫
第１実施形態と同様、表生成部２０１０−ｎは、何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る前段処理を行う。さらに本形態では、表生成部２０１０−ｎが当該前段処理での改ざんを検知するための第１チェックサムを第１方式に則って生成する。以下に、第１方式として参考文献４，５の方式を採用した例を示す。
【００３９】
ステップＳ２０１０−ｎの詳細：
図７を用いてステップＳ２０１０−ｎの詳細を例示する。この例の秘匿情報は秘密分散方式に則ったシェアである。前段処理はＴ種類の秘密分散方式ｍｅｔｈ０，…，ｍｅｔｈＴ−１に則った秘匿情報を用いた秘密計算を含む。当該秘密計算は前述のステップＳ１０１０−ｎの過程で実行される各秘密計算である。
【００４０】
表生成部２０１０−ｎの乱数生成部２０１５−ｎ（図２Ａ）は、ｔ＝０，…，Ｔ−１について乱数ｒｔ∈Ｆを秘密分散した秘匿情報｛ｒｔ｝を得て出力する。ただし、Ｔは１以上の整数であり、ｔ＝０，…，Ｔ−１である。秘匿情報｛ｒｔ｝の生成方法の具体例は参考文献５に開示されている。例えば、まず、秘密計算装置２０−ｎの乱数生成部２０１５−ｎそれぞれが乱数ｒ’ｎ∈Ｆを生成する。次に、各乱数生成部２０１５−ｎは、上記の参考文献２に記載された秘匿方法により乱数ｒ’ｎのシェア｛ｒ’ｎ｝を生成して他の乱数生成部２０１５−ｎ’（ただし、ｎ’＝０，…，Ｎ−１）に送る。そして、乱数生成部２０１５−ｎはそれぞれ｛ｒｔ｝＝Σｎ＜Ｎ｛ｒ’ｎ｝を計算し、乱数ｒｔの秘匿情報｛ｒｔ｝を得る。これにより、いずれの秘密計算装置２０−１〜２０−（Ｎ−１）も乱数ｒｔを知ることなく、乱数生成部２０１５−ｎが乱数ｒｔの秘匿情報｛ｒｔ｝を得ることができる（ステップＳ２０１５−ｎ）。
【００４１】
次に、チェックサム更新部２０１６−ｎは、第１チェックサムに含まれるＣ１，ｔをヌル（空集合）に初期化する。第１チェックサムはＣ１，ｔのみから構成されてもよいし、Ｃ１，ｔとその他の情報とから構成されてもよい（ステップＳ２０１６−ｎ）。
【００４２】
前述の前段処理で秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得るためにΨ個の秘密計算Ｃｏｍ０，…，ＣｏｍΨ−１が行われるとする。ただし、Ψは１以上の整数である。秘密分散方式ｍｅｔｈｔに則った秘匿情報｛ａλ｝∈｛Ｆ｝を用いる秘密計算Ｃｏｍψ（ただし、ψ＝０，…，Ψ−１）が行われる際、チェックサム更新部２０１６−ｎは、秘匿情報｛ａλ｝と秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ａλｒｔ｝を生成する。ただし、Λは１以上の整数であり、λ＝０，…，Λ−１である。さらにチェックサム更新部２０１６−ｎは、秘匿情報｛ａλ｝と秘匿情報｛ａλｒｔ｝との組であるランダム化分散値＜ａλ＞＝＜｛ａλ｝，｛ａλｒｔ｝＞を得、ランダム化分散値＜ａλ＞の追加によってＣ１，ｔを更新する。秘密計算Ｃｏｍψに複数の秘匿情報が用いられる場合、チェックサム更新部２０１６−ｎは、それぞれの秘匿情報についてランダム化分散値を生成し、それらの追加によってＣ１，ｔを更新する（ステップＳ２０１６ａ−ｎ）。
【００４３】
秘密計算部１０１１−ｎは秘密計算Ｃｏｍψを実行する（ステップＳ１０１１−ｎ）。
【００４４】
秘密計算Ｃｏｍψの実行により、秘密分散方式ｍｅｔｈｔに則った秘密計算結果である秘匿情報｛ｈｗ｝が得られる。この際、チェックサム更新部２０１６−ｎは、秘匿情報｛ｈｗ｝と秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｈｗｒｔ｝を得る。ただし、Ｗは１以上の整数であり、ｗ＝０，…，Ｗ−１である。さらに、チェックサム更新部２０１６−ｎは、秘匿情報｛ｈｗ｝と秘匿情報｛ｈｗｒｔ｝との組であるランダム化分散値＜ｈｗ＞＝＜｛ｈｗ｝，｛ｈｗｒｔ｝＞を得、ランダム化分散値＜ｈｗ＞の追加によってＣ１，ｔを更新する。秘密計算結果が複数の秘匿情報を含む場合、チェックサム更新部２０１６−ｎは、それぞれの秘匿情報についてランダム化分散値を生成し、それらの追加によってＣ１，ｔを更新する（ステップＳ２０１６ｂ−ｎ）。
【００４５】
ステップＳ２０１６ａ−ｎ〜Ｓ２０１６ｂ−ｎの処理は、Ψ個の秘密計算Ｃｏｍ０，…，ＣｏｍΨ−１が実行され、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝が得られるまで繰り返される。秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝が得られると、チェックサム更新部２０１６−ｎは、Ｃ１，ｔ＝＜φ０＞，…，＜φΔ−１＞を含む第１チェックサムを出力する。ただし、δ＝０，…，Δ−１であり、＜φδ＞はランダム化分散値である。
【００４６】
≪ステップＳ１０２０−ｎ≫
秘密計算装置１０−ｎに代えて秘密計算装置２０−ｎが実行する以外、第１実施形態と同じである。
【００４７】
≪ステップＳ２０３０−ｎ≫
第１実施形態と同様、ラウンド処理部２０３０−ｎは、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算により、残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行う。さらに本形態では、ラウンド処理部２０３０−ｎが当該後段処理での改ざんを検知するための第２チェックサムを第２方式に則って生成する。以下に、第２方式として参考文献６，７の方式の変更方式を採用した例を示す。
【００４８】
ステップＳ２０３０−ｎの具体例：
図８および図９を用いてステップＳ２０３０−ｎの具体例を説明する。この例の秘匿情報は秘密分散方式に則ったシェアである。
まず、ダミーブロック生成部２０３５ａ−ｎは、Ｙ個のダミーブロックＤ０，…，ＤＹ−１∈ＦＵの秘匿情報｛Ｄ０｝，…，｛ＤＹ−１｝を生成して出力する。ただし、Ｙは１以上の整数であり、ｙ＝０，…，Ｙ−１である。前述のように、好ましくはＹ＝ｐ−Ｂである。ただし、ｐはＢより大きな素数である。ダミーブロックＤ０，…，ＤＹ−１のうち何れかが要処理ダミーブロックＤＰとされる。要処理ダミーブロックＤＰは１個であってもよいし、２個以上であってもよい。要処理ダミーブロックＤＰ以外のダミーブロックＤｙ’は公開値である。ダミーブロック生成部２０３５ａ−ｎは、公開値であるダミーブロックＤｙ’を、正当性を持つ方法で秘匿して秘匿情報｛Ｄｙ’｝を得る。要処理ダミーブロックＤＰは公開値であってもよいし、公開値でなくてもよい。前者の場合、ダミーブロック生成部２０３５ａ−ｎが、公開値であるダミーブロックＤＰを秘匿して秘匿情報｛ＤＰ｝を得る。後者の場合、ダミーブロック生成部２０３５ａ−ｎは、例えば、前述の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝と任意のカウンタ値ｉｄｐ，０，…，ｉｄｐ，Ｓ−１の秘匿情報｛ｉｄｐ，０｝，…，｛ｉｄｐ，Ｓ−１｝とを用い、秘密計算によって秘匿情報｛Ｍ（ｉｄｐ，０，…，ｉｄｐ，Ｓ−１）｝を得、秘匿情報｛ＤＰ｝＝｛Ｍ（ｉｄｐ，０，…，ｉｄｐ，Ｓ−１）｝を得る（ステップＳ２０３５−ｎ）。
【００４９】
次に、ラウンド処理部２０３０−ｎは、必要な何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および要処理ダミーブロックＤＰの秘匿情報｛ＤＰ｝を用い、行列ＭＤＰ，Γ，ＭＵの秘匿情報｛ＭＤＰ，Γ，ＭＵ｝を得るダミー後段処理を行う。ただし、行列ＭＤＰ，Γ，ＭＵは要処理ダミーブロックＤＰに前述の残存処理を行って得られる処理結果である。ここではΓ＝Ｒ＋１かつＭＵ＝４の例を説明する。この際、ダミー後段処理での改ざんを検知するための第３チェックサムを第３方式に則って生成する。第３方式は、安全性がダミー後段処理の対象となる秘匿情報の復元値のデータ量に依存しない方式である。第３方式は、第１方式と同一であってもなくてもよい。ここでは第３方式と第１方式とが互いに同一である例を示す。
【００５０】
まず、チェックサム更新部２０３８−ｎは、第３チェックサムに含まれるＣ３，ｔをヌル（空集合）に初期化する。第３チェックサムはＣ３，ｔのみから構成されてもよいし、Ｃ３，ｔとその他の情報とから構成されてもよい（ステップＳ２０３８−ｎ）。
【００５１】
前述の残存処理でΨ’個の秘密計算Ｃｏｍ３０，…，Ｃｏｍ３Ψ’−１が行われるとする。ただし、Ψ’は１以上の整数である。秘密分散方式ｍｅｔｈｔに則った秘匿情報｛ｄλ｝∈｛Ｆ｝を用いる秘密計算Ｃｏｍ３ψ’（ただし、ψ’＝０，…，Ψ’−１）が行われる際、チェックサム更新部２０３８−ｎは、秘匿情報｛ｄλ｝と秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｄλｒｔ｝を生成する。ただし、Λは１以上の整数であり、λ＝０，…，Λ−１である。さらにチェックサム更新部２０３８−ｎは、秘匿情報｛ｄλ｝と秘匿情報｛ｄλｒｔ｝との組であるランダム化分散値＜ｄλ＞＝＜｛ｄλ｝，｛ｄλｒｔ｝＞を得、ランダム化分散値＜ｄλ＞の追加によってＣ３，ｔを更新する（ステップＳ２０３８ａ−ｎ）。
【００５２】
秘密計算部１０３１−ｎは秘密計算Ｃｏｍ３ψ’を実行する（ステップＳ２０３１ａ−ｎ）。
【００５３】
秘密計算Ｃｏｍ３ψ’の実行により、秘密分散方式ｍｅｔｈｔに則った秘密計算結果である秘匿情報｛ｈ’ｗ｝が得られる。この際、チェックサム更新部２０３８−ｎは、秘匿情報｛ｈ’ｗ｝と秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｈ’ｗｒｔ｝を得る。ただし、Ｗは１以上の整数であり、ｗ＝０，…，Ｗ−１である。さらに、チェックサム更新部２０３８−ｎは、秘匿情報｛ｈ’ｗ｝と秘匿情報｛ｈ’ｗｒｔ｝との組であるランダム化分散値＜ｈ’ｗ＞＝＜｛ｈ’ｗ｝，｛ｈ’ｗｒｔ｝＞を得、ランダム化分散値＜ｈ’ｗ＞の追加によってＣ３，ｔを更新する。秘密計算結果が複数の秘匿情報を含む場合、チェックサム更新部２０３８−ｎは、それぞれの秘匿情報についてランダム化分散値を生成し、それらの追加によってＣ３，ｔを更新する（ステップＳ２０３８ｂ−ｎ）。
【００５４】
ステップＳ２０３８ａ−ｎ〜Ｓ２０３８ｂ−ｎの処理は、Ψ’個の秘密計算Ｃｏｍ３０，…，Ｃｏｍ３Ψ’−１が実行され、秘匿情報｛ＭＤＰ，Γ，ＭＵ｝が得られるまで繰り返される。Γ＝Ｒ＋１かつＭＵ＝４の場合、Ｒ＋１ラウンドが終了するまで、ステップＳ２０３８ａ−ｎ〜Ｓ２０３８ｂ−ｎの処理が繰り返される。秘匿情報｛ＭＤＰ，Γ，ＭＵ｝が得られると、チェックサム更新部２０３８−ｎは、Ｃ３，ｔ＝＜φ３０＞，…，＜φ３Δ’−１＞を含む第３チェックサムを出力する。ただし、δ’＝０，…，Δ’−１であり、＜φ３δ’＞はランダム化分散値である。
【００５５】
次に、チェックサム更新部２０３７−ｎが、第２チェックサムに含まれるＣ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄをヌル（空集合）に初期化する。第２チェックサムはＣ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄのみから構成されてもよいし、Ｃ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄとその他の情報とから構成されてもよい（ステップＳ２０３７−ｎ）。
【００５６】
ランダム置換部２０３６−ｎが、ランダム置換の内容を表すランダム置換情報πｑの秘匿情報｛πｑ｝を生成する。ただし、Ｑは１以上の整数であり、ｑ＝０，…，Ｑ−１である。好ましくは、ランダム置換情報πｑはランダム巡回シフトを表す情報である（ステップＳ２０３６−ｎ）。
【００５７】
結合部２０３５ｃ−ｎには、ステップＳ１０２０−ｎで得られたｂ＝０，…，Ｂ−１についての秘匿情報｛Ｍｂ，γ，μ｝、および、ステップＳ２０３５−ｎで得られた秘匿情報｛Ｄ０｝，…，｛ＤＹ−１｝が入力される。結合部２０３５ｃ−ｎは、これらを用い、秘密計算により、行列Ｍ０，γ，μ，…，ＭＢ−１，γ，μの要素からなる非ランダム化列Ａ∈ＦＵＢの秘匿情報｛Ａ｝とＹ個のダミーブロックＤ０，…，ＤＹ−１∈ＦＵの秘匿情報｛Ｄ０｝，…，｛ＤＹ−１｝とを結合した秘匿情報｛Ａ｜Ｄ｝＝｛Ａ｜Ｄ０｜…｜ＤＹ−１｝を得る。ただし、α｜βはαとβとの結合（連結）を表す（ステップＳ２０３５ｃ−ｎ）。
【００５８】
ランダム置換部２０３６−ｎは、秘匿情報｛πｑ｝および秘匿情報｛Ａ｜Ｄ｝を用い、Ａ｜Ｄをランダム置換して得られるランダム化列Πｑ＝πｑ（Ａ｜Ｄ）∈ＦＵ（Ｂ＋Ｙ）の秘匿情報｛Πｑ｝＝｛πｑ（Ａ｜Ｄ）｝を秘密計算によって得て出力する。この処理は各ｑ＝０，…，Ｑ−１について実行される（ステップＳ２０３６ｂ−ｎ）。
【００５９】
前述の残存処理でΘ個のサブ処理Ｓｕｂ０，…，ＳｕｂΘ−１の秘密計算が行われるとする。ただし、Θが１以上の整数であり、θ＝０，…，Θ−１である。秘密計算部１０３１−ｎは、秘匿情報｛Ａ｝を用い、非ランダム化列Ａを構成する行列Ｍｂ，γ，μのＵ個の要素に対応する秘匿情報｛Ｍｂ，γ，μ｝ごとに各サブ処理ＳｕｂΘの秘密計算を実行する。すなわち、秘密計算部１０３１−ｎは、各秘匿情報｛Ｍｂ，γ，μ｝に対して各サブ処理ＳｕｂΘの秘密計算を実行する。これにより、秘密計算部１０３１−ｎは、非ランダム化列Ａを構成する各行列Ｍｂ，γ，μに残存処理を適用して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る。また秘密計算部１０３１−ｎは、ｑ＝０，…，Ｑ−１について、秘匿情報｛Πｑ｝を用い、ランダム化列Πｑ∈ＦＵ（Ｂ＋Ｙ）を構成するＵ個の要素Πｑ，ｂ”，γ，μ∈ＦＵに対応する秘匿情報｛Πｑ，ｂ”，γ，μ｝∈｛ＦＵ｝ごとに、各サブ処理ＳｕｂΘの秘密計算を実行する。すなわち、秘密計算部１０３１−ｎは、各秘匿情報｛Πｑ，ｂ”，γ，μ｝に対して各サブ処理ＳｕｂΘの秘密計算を実行する。ただし、ｂ”＝０，…，Ｂ−１，…，Ｂ＋Ｙ−１であり、Πｑ＝Πｑ，０，γ，μ｜…｜Πｑ，Ｂ＋Ｙ−１，γ，μである。これにより、秘密計算部１０３１−ｎは、各サブ処理Ｓｕｂθの秘密計算結果である秘密情報｛Πｑ，ｂ”，Γ，ＭＵ｝∈｛ＦＵ｝を得る。さらに秘密計算部１０３１−ｎは、少なくとも一部のダミーブロックＤｙ（例えば、要処理ダミーブロックＤＰを除くダミーブロックＤｙ）に対して各サブ処理ＳｕｂΘを実行することで、各サブ処理Ｓｕｂθの演算結果Ｄｙ，Γ，ＭＵ∈ＦＵを得る（ステップＳ２０３１ｂ−ｎ）。
【００６０】
秘匿化部２０３５ｂ−ｎは、演算結果Ｄｙ，Γ，ＭＵを正当性を持つ方法で秘匿し、秘匿情報｛Ｄｙ，Γ，ＭＵ｝を得て出力する（ステップＳ２０３５ｂ−ｎ）。
【００６１】
チェックサム更新部２０３７−ｎは、秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得るまでの過程で得られる各サブ処理Ｓｕｂθの秘密計算結果である秘匿情報｛Ｍｂ，θ，Γ，ＭＵ｝∈｛ＦＵ｝でＣ２，Ａを更新する。例えば、Ｃ２，Ａ＝（Ｃ０，２，Ａ，…，ＣＢ−１，２，Ａ）の場合、チェックサム更新部２０３７−ｎは（Ｃ０，２，Ａ｜｛Ｍ０，θ，Γ，ＭＵ｝，…，ＣＢ−１，２，Ａ｜｛ＭＢ−１，θ，Γ，ＭＵ｝）を新たなＣ２，Ａとする（ステップＳ２０３７ｂ−ｎ）。
【００６２】
また、チェックサム更新部２０３７−ｎは、ｑ＝０，…，Ｑ−１について、各サブ処理Ｓｕｂθの秘密計算結果である秘密情報｛Πｑ，ｂ”，θ，Γ，ＭＵ｝∈｛ＦＵ｝でＣ２，Π＿ｑを更新する。例えば、Ｃ２，Π＿ｑ＝（Ｃ０，２，Π＿ｑ，…，ＣＢ＋Ｙ−１，２，Π＿ｑ）の場合、チェックサム更新部２０３７−ｎは（Ｃ０，２，Π＿ｑ｜｛Πｑ，０，θ，Γ，ＭＵ｝，…，ＣＢ＋Ｙ−１，２，Π＿ｑ｜｛Πｑ，Ｂ＋Ｙ−１，θ，Γ，ＭＵ｝）を新たなＣ２，Π＿ｑとする（ステップＳ２０３７ｃ−ｎ）。
【００６３】
さらに、チェックサム更新部２０３７−ｎは、各サブ処理Ｓｕｂθの演算結果の秘匿情報｛Ｄｙ，θ，Γ，ＭＵ｝∈｛ＦＵ｝でＣ２，Ｄを更新する。例えば、Ｃ２，Ｄ＝（Ｃ０，２，Ｄ，…，ＣＹ−１，２，Ｄ）の場合、チェックサム更新部２０３７−ｎは（Ｃ０，２，Ｄ｜｛Ｄ０，θ，Γ，ＭＵ｝，…，ＣＹ−１，２，Ｄ｜｛ＤＹ−１，θ，Γ，ＭＵ｝）を新たなＣ２，Ｄとする（ステップＳ２０３７ｄ−ｎ）。
【００６４】
ステップＳ２０３１ｂ−ｎ〜Ｓ２０３７ｄ−ｎの処理は、Θ個のサブ処理Ｓｕｂ０，…，ＳｕｂΘ−１のすべてについて実行される。その後、チェックサム更新部２０３７−ｎは、Ｃ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄを含む第２チェックサムを出力する。
【００６５】
≪ステップＳ１０４１−ｎ≫
秘密計算装置１０−ｎに代えて秘密計算装置２０−ｎが実行する以外、第１実施形態と同じである。
【００６６】
≪ステップＳ２０４２−ｎ≫
同期部２０４２−ｎは、すべての秘密計算装置２０−１〜２０−（Ｎ−１）でのすべての秘密計算が終了するまで待機する同期処理を実行する。Ｎ＝１の場合には同期処理は実行されない。
【００６７】
≪ステップＳ２０４３−ｎ≫
正当性検証部２０４３−ｎには、Ｃ１，ｔ＝＜φ０＞，…，＜φΔ−１＞を含む第１チェックサムおよびＣ３，ｔ＝＜φ３０＞，…，＜φ３Δ’−１＞を含む第３チェックサムが入力される。正当性検証部２０４３−ｎは、参考文献４，５に記載されているように、Ｃ１，ｔおよびＣ３，ｔの正当性を検証する。
【００６８】
Ｃ１，ｔの正当性を検証する場合、正当性検証部２０４３−ｎは、＜φ０＞＝＜｛φ０｝，｛φ０ｒｔ｝＞，…，＜φΔ―１＞＝＜｛φΔ―１｝，｛φΔ―１ｒｔ｝＞の｛φ０｝，…，｛φΔ―１｝および｛ｒｔ｝を用い、秘密計算によって、φ０，…，φΔ―１の総和にｒｔを乗じて得られる結果の秘匿情報｛ｒｔ（φ０＋…＋φΔ―１）｝を求める。さらに正当性検証部２０４３−ｎは、｛φ０ｒｔ｝，…，｛φΔ―１ｒｔ｝を用い、秘密計算によって、φ０ｒｔ，…，φΔ―１ｒｔの総和の秘匿情報｛φ０ｒｔ＋…＋φΔ―１ｒｔ｝を求める。正当性検証部２０４３−ｎは、秘匿情報｛ｒｔ（φ０＋…＋φΔ―１）｝および｛φ０ｒｔ＋…＋φΔ―１ｒｔ｝を用いて、秘密計算によって、ＤＣ１，ｔ＝ｒｔ（φ０＋…＋φΔ―１）−（φ０ｒｔ＋…＋φΔ―１ｒｔ）の秘匿情報｛ＤＣ１，ｔ｝を得てＤＣ１，ｔを復元する。正当性検証部２０４３−ｎは、すべてのｔ＝０，…，Ｔ−１についてＤＣ１，ｔ＝０であれば前段処理に改ざんが無かったと判定し、そうでなければ前段処理に改ざんがあったと判定する。
【００６９】
Ｃ３，ｔの正当性を検証する場合、正当性検証部２０４３−ｎは、＜φ３０＞＝＜｛φ３０｝，｛φ３０ｒｔ｝＞，…，＜φ３Δ’―１＞＝＜｛φ３Δ’―１｝，｛φ３Δ’―１ｒｔ｝＞の｛φ３０｝，…，｛φ３Δ’―１｝および｛ｒｔ｝を用い、秘密計算によって、φ３０，…，φ３Δ’―１の総和にｒｔを乗じて得られる結果の秘匿情報｛ｒｔ（φ３０＋…＋φ３Δ―１）｝を求める。さらに正当性検証部２０４３−ｎは、｛φ３０ｒｔ｝，…，｛φ３Δ’―１ｒｔ｝を用い、秘密計算によって、φ３０ｒｔ，…，φ３Δ’―１ｒｔの総和の秘匿情報｛φ３０ｒｔ＋…＋φ３Δ’―１ｒｔ｝を求める。正当性検証部２０４３−ｎは、秘匿情報｛ｒｔ（φ３０＋…＋φ３Δ’―１）｝および｛φ３０ｒｔ＋…＋φ３Δ’―１ｒｔ｝を用いて、秘密計算によって、ＤＣ３，ｔ＝ｒｔ（φ３０＋…＋φ３Δ’―１）−（φ３０ｒｔ＋…＋φ３Δ’―１ｒｔ）の秘匿情報｛ＤＣ３，ｔ｝を得てＤＣ３，ｔを復元する。正当性検証部２０４３−ｎは、すべてのｔ＝０，…，Ｔ−１についてＤＣ３，ｔ＝０であれば後段処理に改ざんが無かったと判定し、そうでなければ後段処理に改ざんがあったと判定する。
【００７０】
≪ステップＳ２０４４−ｎ≫
正当性検証部２０４４−ｎには、Ｃ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄを含む第２チェックサムおよび秘匿情報｛πｑ｝が入力される。正当性検証部２０４４−ｎは、参考文献５，６に記載されているように、Ｃ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄの正当性を検証する。すなわち、正当性検証部２０４４−ｎは、秘匿情報｛πｑ｝を公開してランダム置換情報πｑを得、πｑ，Ｃ２，Ａ，Ｃ２，Π＿ｑ，Ｃ２，Ｄを用い、秘密計算によって、Ｃ２，Π＿ｑの復元値から、πｑに従ってＣ２，Ａ｜Ｃ２，Ｄをランダム置換した列の復元値を減じた列の秘匿情報｛ζｑ｝＝｛ζ０，ｑ｝，…，｛ζＢ＋Ｙ−１，ｑ｝を得る。正当性検証部２０４４−ｎは、秘匿情報｛ζｑ｝＝｛ζ０，ｑ｝，…，｛ζＢ＋Ｙ−１，ｑ｝の各要素｛ζｂ”，ｑ｝（ただし、ｂ”＝０，…，Ｂ＋Ｙ−１）を｛ＦＵ｝の元ごとに分割し、｛ζ’ｂ”，ｑ，０｝，…，｛ζ’ｂ”，ｑ，Ｍ”−１｝∈｛ＦＵ｝の列を得る。ただし、Ｍ”は正の整数である。｛ＦＵ｝に満たない要素には｛０｝がパディングされる。正当性検証部２０４４−ｎは、秘密計算によって、乱数ｒａｎの秘匿情報｛ｒａｎ｝と｛ζ’ｂ”，ｑ，０｝，…，｛ζ’ｂ”，ｑ，Ｍ”−１｝との積和演算を行い、その結果｛ζ｝を公開してζを得る。正当性検証部２０４４−ｎは、ζが０であれば後段処理に改ざんが無かったと判定し、そうでなければ後段処理に改ざんがあったと判定する。
【００７１】
＜本形態の特徴＞
第１実施形態と同様、本形態でも要素の置換と行の巡回シフトと列の線形和とラウンド鍵の加算とを繰り返すラウンド処理を秘密計算によって効率的に実行できる。特に本形態では、前段処理での改ざんを検知するための第１チェックサムを第１方式に則って生成し、後段処理での改ざんを検知するための第２チェックサムを第２方式に則って生成した。前段処理に比べて後段処理では処理データ量が格段に多い。第２方式は処理データ量が多いほど安全性が高い方式であり、後段処理での改ざんを検知に適している。一方、前段処理では処理データ量が少ないため、第２方式を用いても効率が悪い。本形態では、前段処理と後段処理とでチェックサムの生成方式を変更することで、安全性の高い通信を効率よく実現できる。なお、前段処理で改ざんが検知された場合にはすべての処理が破棄される。一方、後段処理で改ざんが検知された場合にはすべての処理が破棄されてもよいし、後段処理のみが破棄されてもよい。
【００７２】
［第２実施形態の変形例］
第２実施形態では、Ψ個の秘密計算Ｃｏｍ０，…，ＣｏｍΨ−１のすべてについてランダム化分散値が生成され、Ｃ１，ｔが更新される例を説明した（図７）。しかしながら、Ψ個の秘密計算Ｃｏｍ０，…，ＣｏｍΨ−１の一部のみについてランダム化分散値が生成され、Ｃ１，ｔが更新されてもよい。例えば、Ψ個の秘密計算Ｃｏｍ０，…，ＣｏｍΨ−１のうち、通信を必要とする最後の秘密計算までについてランダム化分散値が生成され、Ｃ１，ｔが更新されてもよい。例えば、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝が秘匿情報｛Ｍｂ，３，１｝または｛Ｍｂ，３，２｝である場合に、置換処理Ｐ３，１の通信を必要とする秘密計算（例えば、ＳｕｂＢｙｔｅｓの乗法逆元演算の秘密計算）までについてランダム化分散値が生成され、Ｃ１，ｔが更新されてもよい。
【００７３】
また、ステップＳ１０２０−ｎで行われる各秘密計算の前後においてランダム化分散値が生成され、Ｃ１，ｔが更新されてもよい。すなわち、ステップＳ１０２０−ｎにおいて、秘密分散方式ｍｅｔｈｔに則った秘匿情報｛ａλ｝を用いた秘密計算を行う際に、秘匿情報｛ａλ｝と秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ａλｒｔ｝を得、秘匿情報｛ａλ｝と秘匿情報｛ａλｒｔ｝との組であるランダム化分散値＜ａλ＞＝＜｛ａλ｝，｛ａλｒｔ｝＞を得、ランダム化分散値＜ａλ＞の追加によってＣ１，ｔを更新してもよい。さらに、ステップＳ１０２０−ｎにおいて、秘密分散方式ｍｅｔｈｔに則った秘密計算結果である秘匿情報｛ｈｗ｝が得られた際に、秘匿情報｛ｈｗ｝と秘匿情報｛ｒｔ｝とを用いた秘密計算によって秘匿情報｛ｈｗｒｔ｝を得、秘匿情報｛ｈｗ｝と秘匿情報｛ｈｗｒｔ｝との組であるランダム化分散値＜ｈｗ＞＝＜｛ｈｗ｝，｛ｈｗｒｔ｝＞を得、ランダム化分散値＜ｈｗ＞の追加によってＣ１，ｔを更新することで、Ｃ１，ｔを含む第１チェックサムを更新してもよい。
【００７４】
また、ステップＳ１０４１−ｎでの改ざんを検知するためのチェックサムが生成され、検証されてもよい。このチェックサムは、第２方式に則って生成されることが望ましい。
【００７５】
［その他の変形例等］
なお、本発明は上述の実施形態に限定されるものではない。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７６】
上記の各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００７７】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００７８】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００８０】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００８１】
１，２  秘密計算システム
１０−ｎ，２０−ｎ  秘密計算装置
【図１】
2019039381.tif 000011
【図２】
2019039381.tif 000012
【図３】
2019039381.tif 000013
【図４】
2019039381.tif 000014
【図５】
2019039381.tif 000015
【図６】
2019039381.tif 000016
【図７】
2019039381.tif 000017
【図８】
2019039381.tif 000018
【図９】
2019039381.tif 000019
【手続補正書】
【提出日】令和2年2月18日(2020.2.18)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
ｊラウンド目（ただし、ｊ＝２，…，Ｒ）のラウンド処理は、要素の置換を行う置換処理Ｐｊ，１（処理Ｐｊ，１）と、行の巡回シフトを行うシフト処理Ｐｊ，２（処理Ｐｊ，２）と、列の線形和を行う混合処理Ｐｊ，３（処理Ｐｊ，３）と、ラウンド鍵の加算を行う加算処理Ｐｊ，４（処理Ｐｊ，４）とを含む。ＡＥＳの場合、置換処理Ｐｊ，１はＳｕｂＢｙｔｅｓに相当し、シフト処理Ｐｊ，２はＳｈｉｆｔＲｏｗｓに相当し、混合処理Ｐｊ，３はＭｉｘＣｏlｕｍｎｓに相当し、加算処理Ｐｊ，４はＡｄｄＲｏｕｎｄＫｅｙに相当する。置換処理Ｐｊ，１は、行列Ｍｂ，ｊ−１，４の各要素を置換して行列Ｍｂ，ｊ，１を得る処理を含む。例えば、置換処理Ｐｊ，１は行列Ｍｂ，ｊ−１，４の各要素を予め定められた手順（例えば、Ｓ−ｂｏｘ）に則って置換して行列Ｍｂ，ｊ，１を得る処理である。ＡＥＳの場合、行列Ｍｂ，ｊ−１，４の各要素に対し、既約多項式ｘ８＋ｘ４＋ｘ３＋ｘ＋１による拡大体ＧＦ（２８）上の乗法逆元演算を行い、さらにアフィン変換を行った結果によって各要素を置換して行列Ｍｂ，ｊ，１を得る（参考文献１：情報セキュリティ対策基盤整備事業「電子政府推奨暗号の実装」，独立行政法人情報処理推進機構）。シフト処理Ｐｊ，２は、行列Ｍｂ，ｊ，１の各要素を行ごとに巡回シフトして行列Ｍｂ，ｊ，２を得る処理を含む。例えば、シフト処理Ｐｊ，２は、行列Ｍｂ，ｊ，１のι＋１（ただし、ι＝０，…，Ｐ−１）行目の行を所定の方向（例えば、左方向）にι要素分だけ巡回シフトする処理である。混合処理Ｐｊ，３は、行列Ｍｂ，ｊ，２の各列のＳ個の要素の線形和を当該列のＳ個の要素とした行列Ｍｂ，ｊ，３を得る処理を含む。これらの線形和の各項の係数は行ごとに相違する。加算処理Ｐｊ，４は、行列Ｍｂ，ｊ，３の各要素にｊラウンド目のラウンド鍵ｋｊの各要素を加算して行列Ｍｂ，ｊ，４を得る処理を含む。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
以上の特徴を利用し、秘密計算装置１０−ｎは、まず、何れかのラウンド鍵ｋ１，…，ｋ３の秘匿情報を用い、秘密計算により、変数ｉ＝ｉ０，…，ｉＳ−１に対する一変数関数値を要素に持つ表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を得る。ただし、表Ｍ（ｉ０，…，ｉＳ−１）にカウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１を代入したＭ（ｉｂ，０，…，ｉｂ，Ｓ−１）が行列Ｍｂ，γ，μである。行列Ｍｂ，γ，μはＭｂ，２，１，…，Ｍｂ，３，２の何れかである（γ＝２，３、μ＝１，…，４）。次に、秘密計算装置１０−ｎは、カウンタ値ｉｂ，０，…，ｉｂ，Ｓ−１の秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝および秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によってｂ＝０，…，Ｂ−１についての行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得る。これにより、少ない演算量で行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝を得ることができる。特に、秘密計算で置換処理を行う場合には、秘密計算装置１０−０〜１０−（Ｎ−１）間で通信を行う必要がある。秘匿情報｛Ｍ（ｉ０，…，ｉＳ−1）｝を用いればこの通信を削減できる。特にＭｂ，γ，μがＭｂ，３，１またはＭｂ，３，２である場合、２回の処理Ｐ２，１，Ｐ２，２に必要な通信を削減できる。鍵長を１２８ビットとすると、この削減は２０％の通信量の削減となり、２５％の高速化を実現できる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
≪ステップＳ１０２０−ｎ≫
カウンタ更新部１００３−ｎは、初期記憶部１００１−ｎに格納されたカウンタ値ｉ０，０，…，ｉ０，Ｓ−１の秘匿情報｛ｉ０，０｝，…，｛ｉ０，Ｓ−１｝を用い、秘密計算によって、ブロックｂ’＝２，…，Ｂ−１のカウンタ値ｉｂ’，０，…，ｉｂ’，Ｓ−１の秘匿情報｛ｉｂ’，０｝，…，｛ｉｂ’，Ｓ−１｝を得て出力する。カウンタ値ｉｂ’，０，…，ｉｂ’，Ｓ−１は、カウンタ値ｉ０，０，…，ｉ０，Ｓ−１に予め定められた規則を適用することで得られる値である。例えば、カウンタ値ｉｂ’−１，０，…，ｉｂ’−１，Ｓ−１によって表現される値ｉｂ’−１，０…ｉｂ’−１，Ｓ−１を所定値（例えば、１）だけ増加させた値ｉｂ’−１，０， …， ｉｂ’−１，Ｓ−１＋１を表現する値をカウンタ値ｉｂ’，０，…，ｉｂ’，Ｓ−１とする。表計算部１０２０−ｎは、初期記憶部１００１−ｎから読み出したか、または、カウンタ更新部１００３−ｎから出力された秘匿情報｛ｉｂ，０｝，…，｛ｉｂ，Ｓ−１｝、および表記憶部１００２−ｎから読み出した秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用い、秘密計算によって、ｂ＝０，…，Ｂ−１について、行列Ｍｂ，γ，μの秘匿情報｛Ｍｂ，γ，μ｝＝｛Ｍ（ｉｂ，０，…，ｉｂ，Ｓ−１）｝を得て出力する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
≪ステップＳ１０３０−ｎ≫
ラウンド処理部１０３０−ｎは、何れかのラウンド鍵ｋ２，…，ｋＲ＋１の秘匿情報および秘匿情報｛Ｍｂ，γ，μ｝を用い、秘密計算（ステップＳ１０３１ｂ−ｎ）により、残存処理を実行して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る後段処理を行う。残存処理は、ｊ＝２，…，Ｒについての置換処理Ｐｊ，１、シフト処理Ｐｊ，２、混合処理Ｐｊ，３、および加算処理Ｐｊ，４のうち、処理Ｐγ，μよりも後に行われる各処理を含む処理である。処理Ｐγ，μは、表計算部１０２０−ｎで得られた秘匿情報｛Ｍｂ，γ，μ｝＝｛Ｍ（ｉｂ，０，…，ｉｂ，Ｓ−１）｝に対応する。例えば、Ｍｂ，γ，μ＝Ｍｂ，３，２かつΓ＝Ｒ＋１，ＭＵ＝４の場合、ラウンド処理部１０３０−ｎは、秘匿情報｛ｋ３｝，…，｛ｋＲ＋１｝および秘匿情報｛Ｍｂ，３，２｝を用い、秘密計算により、３ラウンド目の混合処理Ｐ３，３からＲラウンド目の加算処理ＰＲ，４までを実行し、さらにＲ＋１ラウンド目の置換処理ＰＲ＋１，１、シフト処理ＰＲ＋１，２、加算処理ＰＲ＋１，４を実行して得られる行列Ｍｂ，Ｒ＋１，４の秘匿情報｛Ｍｂ，Ｒ＋１，４｝を得て出力する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
＜本形態の特徴＞
以上のように、本形態では表Ｍ（ｉ０，…，ｉＳ−１）の秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を生成し、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用いて秘密計算によって各ブロックｂ＝０，…，Ｂ−１の秘匿情報｛Ｍｂ，γ，μ｝を得る。表Ｍ（ｉ０，…，ｉＳ−１）のサイズはＦのＵ倍のデータ量以下で表現でき、秘匿情報｛Ｍ（ｉ０，…，ｉＳ−１）｝を用いて各ブロックｂ＝０，…，Ｂ−１の処理を行うことで演算量を削減できる。さらに、Ｍｂ，γ，μがＭｂ，３，１またはＭｂ，３，２である場合には、２回の処理Ｐ２，１，Ｐ２，２の秘密計算に必要な通信を削減できる。このように、本形態では、要素の置換と行の巡回シフトと列の線形和とラウンド鍵の加算とを繰り返すラウンド処理を秘密計算によって効率的に実行できる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
図３Ａに例示するように、表生成部２０１０−ｎは、秘密計算部１０１１−ｎ、制御部１０１２−ｎ、乱数生成部２０１５−ｎ、およびチェックサム更新部２０１６−ｎを有する。図３Ｂに例示するように、ラウンド処理部２０３０−ｎは、秘密計算部１０３１−ｎ、制御部１０３２−ｎ、ダミーブロック生成部２０３５ａ−ｎ、秘匿化部２０３５ｂ−ｎ、結合部２０３５ｃ−ｎ、ランダム置換部２０３６−ｎ、およびチェックサム更新部２０３７−ｎ，２０３８−ｎを有する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４０
【補正方法】変更
【補正の内容】
【００４０】
表生成部２０１０−ｎの乱数生成部２０１５−ｎ（図３Ａ）は、ｔ＝０，…，Ｔ−１について乱数ｒｔ∈Ｆを秘密分散した秘匿情報｛ｒｔ｝を得て出力する。ただし、Ｔは１以上の整数であり、ｔ＝０，…，Ｔ−１である。秘匿情報｛ｒｔ｝の生成方法の具体例は参考文献５に開示されている。例えば、まず、秘密計算装置２０−ｎの乱数生成部２０１５−ｎそれぞれが乱数ｒ’ｎ∈Ｆを生成する。次に、各乱数生成部２０１５−ｎは、上記の参考文献２に記載された秘匿方法により乱数ｒ’ｎのシェア｛ｒ’ｎ｝を生成して他の乱数生成部２０１５−ｎ’（ただし、ｎ’＝０，…，Ｎ−１）に送る。そして、乱数生成部２０１５−ｎはそれぞれ｛ｒｔ｝＝Σｎ＜Ｎ｛ｒ’ｎ｝を計算し、乱数ｒｔの秘匿情報｛ｒｔ｝を得る。これにより、いずれの秘密計算装置２０−１〜２０−（Ｎ−１）も乱数ｒｔを知ることなく、乱数生成部２０１５−ｎが乱数ｒｔの秘匿情報｛ｒｔ｝を得ることができる（ステップＳ２０１５−ｎ）。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
ランダム置換部２０３６−ｎが、ランダム置換の内容を表すランダム置換情報πｑの秘匿情報｛πｑ｝を生成する。ただし、Ｑは１以上の整数であり、ｑ＝０，…，Ｑ−１である。好ましくは、ランダム置換情報πｑはランダム巡回シフトを表す情報である（ステップＳ２０３６ａ−ｎ）。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
前述の残存処理でΘ個のサブ処理Ｓｕｂ０，…，ＳｕｂΘ−１の秘密計算が行われるとする。ただし、Θが１以上の整数であり、θ＝０，…，Θ−１である。秘密計算部１０３１−ｎは、秘匿情報｛Ａ｝を用い、非ランダム化列Ａを構成する行列Ｍｂ，γ，μのＵ個の要素に対応する秘匿情報｛Ｍｂ，γ，μ｝ごとに各サブ処理Ｓｕｂθの秘密計算を実行する。すなわち、秘密計算部１０３１−ｎは、各秘匿情報｛Ｍｂ，γ，μ｝に対して各サブ処理Ｓｕｂθの秘密計算を実行する。これにより、秘密計算部１０３１−ｎは、非ランダム化列Ａを構成する各行列Ｍｂ，γ，μに残存処理を適用して得られる行列Ｍｂ，Γ，ＭＵの秘匿情報｛Ｍｂ，Γ，ＭＵ｝を得る。また秘密計算部１０３１−ｎは、ｑ＝０，…，Ｑ−１について、秘匿情報｛Πｑ｝を用い、ランダム化列Πｑ∈ＦＵ（Ｂ＋Ｙ）を構成するＵ個の要素Πｑ，ｂ”，γ，μ∈ＦＵに対応する秘匿情報｛Πｑ，ｂ”，γ，μ｝∈｛ＦＵ｝ごとに、各サブ処理Ｓｕｂθの秘密計算を実行する。すなわち、秘密計算部１０３１−ｎは、各秘匿情報｛Πｑ，ｂ”，γ，μ｝に対して各サブ処理Ｓｕｂθの秘密計算を実行する。ただし、ｂ”＝０，…，Ｂ−１，…，Ｂ＋Ｙ−１であり、Πｑ＝Πｑ，０，γ，μ｜…｜Πｑ，Ｂ＋Ｙ−１，γ，μである。これにより、秘密計算部１０３１−ｎは、各サブ処理Ｓｕｂθの秘密計算結果である秘匿情報｛Πｑ，ｂ”，Γ，ＭＵ｝∈｛ＦＵ｝を得る。さらに秘密計算部１０３１−ｎは、少なくとも一部のダミーブロックＤｙ（例えば、要処理ダミーブロックＤＰを除くダミーブロックＤｙ）に対して各サブ処理Ｓｕｂθを実行することで、各サブ処理Ｓｕｂθの演算結果Ｄｙ，Γ，ＭＵ∈ＦＵを得る（ステップＳ２０３１ｂ−ｎ）。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
また、チェックサム更新部２０３７−ｎは、ｑ＝０，…，Ｑ−１について、各サブ処理Ｓｕｂθの秘密計算結果である秘匿情報｛Πｑ，ｂ”，θ，Γ，ＭＵ｝∈｛ＦＵ｝でＣ２，Π＿ｑを更新する。例えば、Ｃ２，Π＿ｑ＝（Ｃ０，２，Π＿ｑ，…，ＣＢ＋Ｙ−１，２，Π＿ｑ）の場合、チェックサム更新部２０３７−ｎは（Ｃ０，２，Π＿ｑ｜｛Πｑ，０，θ，Γ，ＭＵ｝，…，ＣＢ＋Ｙ−１，２，Π＿ｑ｜｛Πｑ，Ｂ＋Ｙ−１，θ，Γ，ＭＵ｝）を新たなＣ２，Π＿ｑとする（ステップＳ２０３７ｃ−ｎ）。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
Ｃ３，ｔの正当性を検証する場合、正当性検証部２０４３−ｎは、＜φ３０＞＝＜｛φ３０｝，｛φ３０ｒｔ｝＞，…，＜φ３Δ’―１＞＝＜｛φ３Δ’―１｝，｛φ３Δ’―１ｒｔ｝＞の｛φ３０｝，…，｛φ３Δ’―１｝および｛ｒｔ｝を用い、秘密計算によって、φ３０，…，φ３Δ’―１の総和にｒｔを乗じて得られる結果の秘匿情報｛ｒｔ（φ３０＋…＋φ３Δ’―１）｝を求める。さらに正当性検証部２０４３−ｎは、｛φ３０ｒｔ｝，…，｛φ３Δ’―１ｒｔ｝を用い、秘密計算によって、φ３０ｒｔ，…，φ３Δ’―１ｒｔの総和の秘匿情報｛φ３０ｒｔ＋…＋φ３Δ’―１ｒｔ｝を求める。正当性検証部２０４３−ｎは、秘匿情報｛ｒｔ（φ３０＋…＋φ３Δ’―１）｝および｛φ３０ｒｔ＋…＋φ３Δ’―１ｒｔ｝を用いて、秘密計算によって、ＤＣ３，ｔ＝ｒｔ（φ３０＋…＋φ３Δ’―１）−（φ３０ｒｔ＋…＋φ３Δ’―１ｒｔ）の秘匿情報｛ＤＣ３，ｔ｝を得てＤＣ３，ｔを復元する。正当性検証部２０４３−ｎは、すべてのｔ＝０，…，Ｔ−１についてＤＣ３，ｔ＝０であれば後段処理に改ざんが無かったと判定し、そうでなければ後段処理に改ざんがあったと判定する。
【手続補正１２】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2019039381.tif 000020
【手続補正１３】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2019039381.tif 000021
【手続補正１４】
【補正対象書類名】図面
【補正対象項目名】図８
【補正方法】変更
【補正の内容】
【図８】
2019039381.tif 000022
【手続補正１５】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2019039381.tif 000023
【国際調査報告】
2019039381.tif 000024
2019039381.tif 000025
2019039381.tif 000026
2019039381.tif 000027