(57)【要約】【課題】秘密ナンスを利用できるAPEを実現することができる暗号化データ生成装置等を提供する。【解決手段】追加データAをrビットの秘匿対象のデータを含む値Arと(|A|-r)ビット分の秘匿対象ではない値A'とに分割し、追加データAを用いて得られる暗号化ステートのレート部分を復元情報RIとし、暗号化ステートとメッセージMとを用いて、暗号化データCとタグTを生成し、暗号化データCとタグTと値A'と復元情報RIを出力する。【選択図】図４
2019015919.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、
追加データAをrビットの秘匿対象のデータを含む値Arと(|A|-r)ビット分の秘匿対象ではない値A'とに分割する分割部と、
n=1,2,…,|A|/rとし、前記追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和部と、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1のレート部分SR,n-1を前記排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIとして出力する第一置換部と、
暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定部と、
メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1xor Mmを求める第二排他的論理和部と、
前記暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を前記排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、前記暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換部と、
暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを出力する出力部を含む、
暗号化データ生成装置。
【請求項２】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
暗号化データCとタグTと追加データAに含まれる(|A|-r)ビット分の秘匿対象ではない値A'と暗号化データCを生成する際に得られる復元情報RIとを受け取る入力部と、
m=1,2,…,|M|/rとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)に含まれる暗号化データC|M|/rとcビットのタグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和部と、
暗号化する際に用いた置換fの逆関数をf-1とし、前記復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを前記排他的論理和SC,|A|/r+|M|/r xor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換部と、
m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和部と、
m=1,2,…,|M|/r-1において、前記復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換部と、
復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIとの排他的論理和SR,|A|/r xor RIを復号データM1,Dとして出力する第五排他的論理和部と、
復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去部と、
前記復号ステートS|A|/rのレート部分SR,|A|/rを前記復元情報RIに置換え、前記復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換部と、
前記値A'を|A'|/r個に分割して得られる各値をA'nとし、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nと、前記値A'nとの排他的論理和SR,n xor A'nを求める第六排他的論理和部と、
n=1,2,…,|A|/r-1において、前記復号ステートSnのレート部分SR,nを排他的論理和SR,n xor A'nに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換部と、
復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Arとして出力する認証部とを含む、
復号データ生成装置。
【請求項３】
暗号化データ生成装置と復号データ生成装置とを含む追加データ付き認証暗号システムであって、
前記暗号化データ生成装置は、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、
追加データAをrビットの秘匿対象のデータを含む値Arと(|A|-r)ビット分の秘匿対象ではない値A'とに分割する分割部と、
n=1,2,…,|A|/rとし、前記追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和部と、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1のレート部分SR,n-1を前記排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIとして出力する第一置換部と、
暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定部と、
メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1xor Mmを求める第二排他的論理和部と、
前記暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を前記排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、前記暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換部と、
暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを出力する出力部を含み、
前記復号データ生成装置は、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを受け取る入力部と、
前記暗号化データC=(C1,C2,…,C|M|/r)に含まれる前記暗号化データC|M|/rとcビットの前記タグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和部と、
暗号化する際に用いた前記置換fの逆関数をf-1とし、前記復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを前記排他的論理和SC,|A|/r+|M|/rxor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換部と、
m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和部と、
m=1,2,…,|M|/r-1において、前記復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換部と、
復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIとの排他的論理和SR,|A|/r xor RIを復号データM1,Dとして出力する第五排他的論理和部と、
復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去部と、
前記復号ステートS|A|/rのレート部分SR,|A|/rを前記復元情報RIに置換え、前記復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換部と、
前記値A'を|A'|/r個に分割して得られる各値をA'nとし、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nと、前記値A'nとの排他的論理和SR,n xor A'nを求める第六排他的論理和部と、
n=1,2,…,|A|/r-1において、前記復号ステートSnのレート部分SR,nを排他的論理和SR,n xor A'nに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換部と、
復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Arとして出力する認証部とを含む、
追加データ付き認証暗号システム。
【請求項４】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、
暗号化データ生成装置が、
追加データAをrビットの秘匿対象のデータを含む値Arと(|A|-r)ビット分の秘匿対象ではない値A'とに分割する分割ステップと、
n=1,2,…,|A|/rとし、前記追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和ステップと、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1のレート部分SR,n-1を前記排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIとして出力する第一置換ステップと、
暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定ステップと、
メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1xor Mmを求める第二排他的論理和ステップと、
前記暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を前記排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、前記暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換ステップと、
暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成ステップと、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを出力する出力ステップを含む、
暗号化データ生成方法。
【請求項５】
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、メッセージMのビット長を|M|とし、追加データAのビット長を|A|とし、
復号データ生成装置が、
暗号化データCとタグTと追加データAに含まれる(|A|-r)ビット分の秘匿対象ではない値A'と暗号化データCを生成する際に得られる復元情報RIとを受け取る入力ステップと、
m=1,2,…,|M|/rとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)に含まれる暗号化データC|M|/rとcビットのタグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和ステップと、
暗号化する際に用いた置換fの逆関数をf-1とし、前記復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを前記排他的論理和SC,|A|/r+|M|/r xor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換ステップと、
m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和ステップと、
m=1,2,…,|M|/r-1において、前記復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換ステップと、
復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIとの排他的論理和SR,|A|/r xor RIを復号データM1,Dとして出力する第五排他的論理和ステップと、
復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去ステップと、
前記復号ステートS|A|/rのレート部分SR,|A|/rを前記復元情報RIに置換え、前記復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換ステップと、
前記値A'を|A'|/r個に分割して得られる各値をA'nとし、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nと、前記値A'nとの排他的論理和SR,n xor A'nを求める第六排他的論理和ステップと、
n=1,2,…,|A|/r-1において、前記復号ステートSnのレート部分SR,nを排他的論理和SR,n xor A'nに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換ステップと、
復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Arとして出力する認証ステップとを含む、
復号データ生成方法。
【請求項６】
暗号化データ生成装置と復号データ生成装置とを用いた追加データ付き認証暗号方法であって、
前記暗号化データ生成装置が、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、
追加データAをrビットの秘匿対象のデータを含む値Arと(|A|-r)ビット分の秘匿対象ではない値A'とに分割する分割ステップと、
n=1,2,…,|A|/rとし、前記追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和ステップと、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1のレート部分SR,n-1を前記排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIとして出力する第一置換ステップと、
暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定ステップと、
メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1xor Mmを求める第二排他的論理和ステップと、
前記暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を前記排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、前記暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換ステップと、
暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成ステップと、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを出力する出力ステップを実行し、
前記復号データ生成装置が、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを受け取る入力ステップと、
前記暗号化データC=(C1,C2,…,C|M|/r)に含まれる前記暗号化データC|M|/rとcビットの前記タグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和ステップと、
暗号化する際に用いた前記置換fの逆関数をf-1とし、前記復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを前記排他的論理和SC,|A|/r+|M|/rxor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換ステップと、
m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和ステップと、
m=1,2,…,|M|/r-1において、前記復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換ステップと、
復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIとの排他的論理和SR,|A|/r xor RIを復号データM1,Dとして出力する第五排他的論理和ステップと、
復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去ステップと、
前記復号ステートS|A|/rのレート部分SR,|A|/rを前記復元情報RIに置換え、前記復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換ステップと、
前記値A'を|A'|/r個に分割して得られる各値をA'nとし、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nと、前記値A'nとの排他的論理和SR,n xor A'nを求める第六排他的論理和ステップと、
n=1,2,…,|A|/r-1において、前記復号ステートSnのレート部分SR,nを排他的論理和SR,n xor A'nに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換ステップと、
復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Arとして出力する認証ステップとを実行する、
追加データ付き認証暗号方法。
【請求項７】
暗号化データ生成装置と復号データ生成装置とを含む追加データ付き認証暗号システムであって、
前記暗号化データ生成装置は、
秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、
追加データAをP×rビットの秘匿対象のデータを含む値Ar=(Ar1,Ar2,…,ArP)と(|A|-P×r)ビット分の秘匿対象ではない値A'=(A'1,A'2,…,A'|A|/r-P)とに分割する分割部と、
n=1,2,…,|A|/rとし、前記追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求め、前記値Anが秘匿対象のデータAr2,Ar3,…,ArPの場合、ステートSn-1のレート部分SR,n-1を復元情報RI1,RI2,…,RIP-1として出力する第一排他的論理和部と、
bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、前記暗号化ステートSn-1のレート部分SR,n-1を前記排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIPとして出力する第一置換部と、
暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定部と、
メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、前記メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1xor Mmを求める第二排他的論理和部と、
前記暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を前記排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、前記暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換部と、
暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、
前記暗号化データCと前記タグTと前記値A'と復元情報RI=(RI1,RI2,…,RIP)とを出力する出力部を含み、
前記復号データ生成装置は、
前記暗号化データCと前記タグTと前記値A'と前記復元情報RIとを受け取る入力部と、
前記暗号化データC=(C1,C2,…,C|M|/r)に含まれる前記暗号化データC|M|/rとcビットの前記タグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの前記秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和部と、
暗号化する際に用いた前記置換fの逆関数をf-1とし、前記復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを前記排他的論理和SC,|A|/r+|M|/rxor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換部と、
m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和部と、
m=1,2,…,|M|/r-1において、前記復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を前記逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換部と、
復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIPとの排他的論理和SR,|A|/r xor RIPを復号データM1,Dとして出力する第五排他的論理和部と、
復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去部と、
前記復号ステートS|A|/rのレート部分SR,|A|/rを前記復元情報RIPに置換え、前記復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換部と、
前記値A'を|A'|/r個に分割して得られる各値をA'qとし、q=1,2,…,|A|/r-P及びp=1,2,…,P-1において、(i)値A'qを入力としたとき、復号ステートSnのレート部分SR,nと、前記値A'qとの排他的論理和SR,n xor A'qを求め、(ii)復元情報RIpを入力としたとき、復号ステートSnのレート部分SR,nのrビットに対し、復元情報RIpとの排他的論理和SR,n xor RIpを求め、排他的論理和SR,nxor RIpを秘匿対象のデータAp+1として出力する第六排他的論理和部と、
n=1,2,…,|A|/r-1において、前記復号ステートSnのレート部分SR,nを(i)排他的論理和SR,n xor A'q、または、(ii)復元情報RIpに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換部と、
復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Ar1として出力する認証部とを含む、
追加データ付き認証暗号システム。
【請求項８】
請求項１の暗号化データ生成装置、または、請求項２の復号データ生成装置として、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージの秘匿と改ざん検知を同時に行う追加データ付き認証暗号技術に関する。
【背景技術】
【０００２】
追加データ付き認証暗号とは、メッセージMの秘匿、および、メッセージMと追加データAの認証（改ざん検知）を同時に行う共通鍵暗号プリミティブである。従来の追加データ付き認証暗号としては、例えば、非特許文献１および非特許文献２に記載されたAPE（Authenticated Permutation-Based Encryption）が挙げられる。追加データ付き認証暗号は、暗号化関数および復号関数の二つの関数から構成される。追加データ付き認証暗号では、受信者と送信者との間であらかじめ秘密の鍵Kを共有しておく。
【０００３】
送信者は、メッセージMと追加データAに加えて、暗号化関数を呼び出すたびに変化するナンスと呼ばれる値Nを選択する。暗号化関数は、メッセージM、追加データA、およびナンスNに対応する暗号化データCおよびタグTを生成し、(C, T, A, N)の組を受信者に送る。
【０００４】
受信者は(C, T, A, N)の組を受け取るが、この時点ではこれらの値が悪意ある第三者によって改ざんされていないという保証はない。受信者は受け取った(C, T, A, N)の組と自分が保有する鍵Kとを用いて検証を同時に行う復号関数を計算する。
【０００５】
検証を同時に行う復号関数にはいくつかの種類がある。多くの追加データ付き認証暗号では、受信者が再計算したタグT'が送信者から受け取ったタグTと一致するかどうかで検証を行う。APEでは、受信者が再計算した中間ステートの値がある値に一致するかどうかで検証を行う。いずれにせよ値が一致しなかった場合は復号に失敗した（データが改ざんされた）という結果を出力する。
【０００６】
APEは追加データ付き認証暗号の暗号化関数と復号関数の構成法である。保証したい安全性レベル（ビット数）に比べて比較的大きなサイズの置換（bijective map）を用いて暗号化関数と復号関数を構成するという特徴を持つ。APEの復号関数は、上記のとおり、従来の復号関数とは異なる特殊な方法で検証を行う。
【０００７】
図１を参照しながら、APEの暗号化関数の具体的な計算手順を説明する。APEの暗号化関数は、ステートと呼ばれるbビットのデータを、bビットの置換f:{0, 1}b→{0, 1}b、入力データ(N, A, M)、および鍵Kを用いて繰り返し更新しながら、暗号化データCおよびタグTを計算する。置換fの詳細は非特許文献２に記載されている。なお、ナンスNの入力は必須ではなく、ナンスNがある場合も、ナンスNは追加データAの一部となる。したがって、入力データは追加データA、メッセージM、および鍵Kを考慮すれば十分である。また、追加データAはメッセージMよりも先に処理される。そのような追加データAはヘッダと呼ばれる。追加データAとメッセージMの長さはいずれもrビットの倍長に限られる。
【０００８】
bビットのステートは、レートと呼ばれるrビットと、キャパシティと呼ばれるc（=b-r）ビットに分割される。暗号化関数を計算する場合、bビットのステートの値を、レート部分のrビットは0（すなわち、すべてのビットが0のビット列）に、キャパシティ部分のcビットは鍵Kの値に初期化する。
【０００９】
手順１．追加データAをrビットのブロックに分割する。bビットのステートのうちレート部分のrビットに対し、追加データAの第一ブロックとの排他的論理和を計算し、bビットのステートに対し、置換fを計算する。この置換fの出力を新たなステートの値とする。この操作を追加データAの最終ブロックが排他的論理和されるまで繰り返す。
【００１０】
手順２．bビットのステートのうちキャパシティ部分のcビットに対し、整数値1（すなわち、最下位ビットのみが1のビット列）との排他的論理和を計算する。
【００１１】
手順３．メッセージMをrビットのブロックに分割する。bビットのステートのうちレート部分のrビットに対し、メッセージMの第一ブロックとの排他的論理和を計算し、bビットのステートに対し、置換fを計算する。この置換fの出力を新たなステートの値とし、レート部分のrビットを暗号化データCの第一ブロックとして出力する。この操作をメッセージMの最終ブロックが排他的論理和されるまで繰り返す。
【００１２】
手順４．bビットのステートのうちキャパシティ部分のcビットに対し、cビットの鍵Kとの排他的論理和を計算し、計算結果をcビットのタグTとして出力する。
【００１３】
図２を参照しながら、APEの復号関数の具体的な計算手順を説明する。APEの復号関数は、APEの暗号化関数の計算をほぼ逆順に行う。復号関数は、通常(C, T, A, N)の組を入力にとるが、APEではナンスNは追加データAの一部とみなすことができるため、(C, T, A)の組を入力にとるとみなす。
【００１４】
復号関数を計算する場合、bビットのステートの値を、rビットの暗号化データCの最終ブロック（図２の例ではC2）とcビットのタグTとを連結した値に初期化する。
【００１５】
手順１．bビットのステートのうちキャパシティ部分のcビットに対し、cビットの鍵Kとの排他的論理和を計算し、計算結果によりキャパシティ部分のcビットを更新する。
【００１６】
手順２．bビットのステートに対し、置換fの逆関数f-1:{0, 1}b→{0, 1}bを計算する。この逆関数f-1の出力を新たなステートの値とする。レート部分のrビットに対し、暗号化データCの最終ブロックの一つ前のブロック（図２の例ではC1）との排他的論理和を計算し、計算結果をメッセージMの最終ブロック（図２の例ではM2）として出力する。また、レート部分のrビットを、暗号化データCの最終ブロックの一つ前のブロック（図２の例ではC1）により更新し、更新されたステートを新たなステートの値とする。この操作を暗号化データCの第一ブロック（図２の例ではC0）が処理されるまで繰り返す。これにより、メッセージMの最終ブロック（図２の例ではM2）から第二ブロック（図２の例ではM1）までが復元される。最後に更新されたステートのうち、レート部分のrビットの値をSr、キャパシティ部分のcビットの値をScとする。
【００１７】
手順３．メッセージMの第一ブロック（図２の例ではM0）の復元方法は、それ以外のブロックとは異なる。まず、暗号化関数の手順１から手順２までと同じ計算を行う。更新されたステートのうち、レート部分のrビットの値をS'r、キャパシティ部分のcビットの値をS'cとする。rビットの値Srとrビットの値S'rとの排他的論理和を計算し、計算結果をメッセージMの第一ブロック（図２の例ではM0）として出力する。
【００１８】
手順４．cビットの値Scとcビットの値S'cとを比較し、値が一致すれば復号されたメッセージM(図２の例ではM=M0||M1||M2)を出力する。なお、復号されたメッセージMを復号データともいう。一致しなかった場合は、メッセージMは出力せず、復号に失敗した旨を表すエラーコードのみを出力する。
【００１９】
また、秘密ナンスを実現する追加データ付き認証暗号としてProtected IV (PIV)方式が存在する(非特許文献３参照)。秘密ナンスとは、ナンスの一種であり、値が暗号化されてから通信路を流れる値のことを言う。これまでに通信したパケット数等をナンスとして用いる場合、ナンスにプライバシー情報を含むため、ナンスを暗号化してから送ることが望ましい。
【００２０】
通常のナンスを利用する追加データ付き認証暗号では、送信者は入力データ(N,A,M)と鍵Kを用いて(C,T)を計算し、(C,T,A,N)を受信者に送る。つまり、Nは暗号化されない。PIV方式では、(N,A,M)と鍵Kを用いて(C,T)を計算する他、Nを暗号化して復元情報RIに変換し、(C,T,A,RI)を受信者に送る。受信者は復号の途中でRIからNを復元する。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】Elena Andreeva, Begul Bilgin, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha and Kan Yasuda, "APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography," FSE 2014, (eds.) Carlos Cid and Christian Rechberger, LNCS, Vol. 8540, pages 168-186, Springer, 2015.
【非特許文献２】Elena Andreeva, Begul Bilgin, Andrey Bogdanov, Atul Luykx, Florian Mendel, Bart Mennink, Nicky Mouha, Qingju Wang and Kan Yasuda, "PRIMATEs v1 | Submission to the CAESAR Competition," Submitted to CAESAR, 2014.
【非特許文献３】Thomas Shrimpton and R. Seth Terashima, \AModular Framework for Building Variable-Input-Length Tweakable Ciphers," ASIACRYPT 2013 , (eds.) Kazue Sako and Palash Sarkar, LNCS, Vol. 8269, pages 405-423, Springer, 2013.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、従来技術のAPEでは、ナンスを利用する場合はA の一部とみなされ、暗号化されずに受信者に送られる。
【００２３】
本発明は、秘密ナンスを利用できるAPEを実現することができる暗号化データ生成装置、復号データ生成装置、追加データ付き認証暗号システム、その方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２４】
上記の課題を解決するために、本発明の一態様によれば、追加データ付き認証暗号システムは、暗号化データ生成装置と復号データ生成装置とを含む。暗号化データ生成装置は、秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、追加データAをrビットの秘匿対象のデータを含む値Arと(|A|-r)ビット分の秘匿対象ではない値A'とに分割する分割部と、n=1,2,…,|A|/rとし、追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める第一排他的論理和部と、bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIとして出力する第一置換部と、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定部と、メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1xor Mmを求める第二排他的論理和部と、暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換部と、暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、暗号化データCとタグTと値A'と復元情報RIとを出力する出力部を含む。復号データ生成装置は、暗号化データCとタグTと値A'と復元情報RIとを受け取る入力部と、暗号化データC=(C1,C2,…,C|M|/r)に含まれる暗号化データC|M|/rとcビットのタグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和部と、暗号化する際に用いた置換fの逆関数をf-1とし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを排他的論理和SC,|A|/r+|M|/rxor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換部と、m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和部と、m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換部と、復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIとの排他的論理和SR,|A|/r xor RIを復号データM1,Dとして出力する第五排他的論理和部と、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去部と、復号ステートS|A|/rのレート部分SR,|A|/rを復元情報RIに置換え、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換部と、値A'を|A'|/r個に分割して得られる各値をA'nとし、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nと、値A'nとの排他的論理和SR,n xor A'nを求める第六排他的論理和部と、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nを排他的論理和SR,n xor A'nに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換部と、復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Arとして出力する認証部とを含む。
【００２５】
上記の課題を解決するために、本発明の他の態様によれば、追加データ付き認証暗号システムは、暗号化データ生成装置と復号データ生成装置とを含む。暗号化データ生成装置は、秘密鍵Kのビット長をcビットとし、rビットのレート部分とcビットのキャパシティ部分とを含むbビットの情報をステートとし、追加データAのビット長を|A|とし、追加データAをP×rビットの秘匿対象のデータを含む値Ar=(Ar1,Ar2,…,ArP)と(|A|-P×r)ビット分の秘匿対象ではない値A'=(A'1,A'2,…,A'|A|/r-P)とに分割する分割部と、n=1,2,…,|A|/rとし、追加データAを|A|/r個に分割して得られる各値をAnとし、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0とし、bビットの暗号化ステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求め、値Anが秘匿対象のデータAr2,Ar3,…,ArPの場合、ステートSn-1のレート部分SR,n-1を復元情報RI1,RI2,…,RIP-1として出力する第一排他的論理和部と、bビットのビット列dをbビットのビット列eに置換する関数を置換fとし、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求め、暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIPとして出力する第一置換部と、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界設定部と、メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、メッセージMを|M|/r個に分割して得られる各値をMmとし、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1 xor Mmを求める第二排他的論理和部と、暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を排他的論理和SR,|A|/r+m-1 xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する第二置換部と、暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和をタグTとして出力するタグ生成部と、暗号化データCとタグTと値A'と復元情報RI=(RI1,RI2,…,RIP)とを出力する出力部を含む。復号データ生成装置は、暗号化データCとタグTと値A'と復元情報RIとを受け取る入力部と、暗号化データC=(C1,C2,…,C|M|/r)に含まれる暗号化データC|M|/rとcビットのタグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rとcビットの秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める第三排他的論理和部と、暗号化する際に用いた置換fの逆関数をf-1とし、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを排他的論理和SC,|A|/r+|M|/rxor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める第三置換部と、m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを復号データMm+1として出力する第四排他的論理和部と、m=1,2,…,|M|/r-1において、復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める第四置換部と、復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIPとの排他的論理和SR,|A|/r xor RIPを復号データM1,Dとして出力する第五排他的論理和部と、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる境界除去部と、復号ステートS|A|/rのレート部分SR,|A|/rを復元情報RIPに置換え、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める第五置換部と、値A'を|A'|/r個に分割して得られる各値をA'qとし、q=1,2,…,|A|/r-P及びp=1,2,…,P-1において、(i)値A'qを入力としたとき、復号ステートSnのレート部分SR,nと、値A'qとの排他的論理和SR,n xor A'qを求め、(ii)復元情報RIpを入力としたとき、復号ステートSnのレート部分SR,nのrビットに対し、復元情報RIpとの排他的論理和SR,n xor RIpを求め、排他的論理和SR,nxor RIpを秘匿対象のデータAp+1として出力する第六排他的論理和部と、n=1,2,…,|A|/r-1において、復号ステートSnのレート部分SR,nを(i)排他的論理和SR,n xor A'q、または、(ii)復元情報RIpに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める第六置換部と、復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行い、一致する場合には、予め定めたビット列と復号ステートS0のレート部分SR,0との排他的論理和を値Ar1として出力する認証部とを含む。
【発明の効果】
【００２６】
本発明によれば、秘密ナンスを利用できるAPEを実現することができるという効果を奏する。
【図面の簡単な説明】
【００２７】
【図１】従来の暗号化関数を説明するための図。
【図２】従来の復号関数を説明するための図。
【図３】追加データ付き認証暗号システムの機能構成を例示する図。
【図４】暗号化装置の機能構成を例示する図。
【図５】追加データ計算部の機能構成を例示する図。
【図６】メッセージ計算部の機能構成を例示する図。
【図７】復号装置の機能構成を例示する図。
【図８】暗号化データ逆計算部の機能構成を例示する図。
【図９】追加データ計算部の機能構成を例示する図。
【図１０】暗号化方法の処理手続きを例示する図。
【図１１】第一実施形態の暗号化関数の一例を説明するための図。
【図１２】復号方法の処理手続きを例示する図。
【図１３】第一実施形態の復号関数の一例を説明するための図。
【図１４】第二実施形態の暗号化関数の一例を説明するための図。
【図１５】第二実施形態の暗号化関数の一例を説明するための図。
【図１６】第二実施形態の復号関数の一例を説明するための図。
【図１７】第二実施形態の復号関数の一例を説明するための図。
【発明を実施するための形態】
【００２８】
以下、本発明の実施形態について、説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００２９】
＜第一実施形態＞
この発明の実施形態は、ナンスNの代わりに内部ステートのrビットの値を復元情報RIとして送る。即ち、APEの暗号化処理において、送信者は暗号化データC、タグT、ナンスNを含む追加データA を送るのではなく、暗号化データC、タグT、ナンスNを含まない部分の追加データA、復元情報RIを受信者に送る。受信者は復号の途中で復元情報RIからナンスNを復元する。
【００３０】
実施形態の追加データ付き認証暗号システムは、図３に示すように、追加データ付き認証暗号の暗号化関数を実行する暗号化装置１と、追加データ付き認証暗号の復号関数を実行する復号装置２とを含む。この実施形態では、暗号化装置１および復号装置２はそれぞれ通信網３へ接続される。通信網３は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網３を介してオンラインで通信可能である必要はない。例えば、暗号化装置１が出力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から復号装置２へオフラインで入力するように構成してもよい。
【００３１】
追加データ付き認証暗号システムに含まれる暗号化装置１は、図４に示すように、記憶部１０、入力部１１、初期化部１２、追加データ計算部１４、境界設定部１５、メッセージ計算部１６、タグ生成部１７、および出力部１８を含む。暗号化装置１に含まれる追加データ計算部１４は、図５に示すように、分割部１４１、排他的論理和部１４２、および置換部１４３を含む。暗号化装置１に含まれるメッセージ計算部１６は、図６に示すように、分割部１６１、排他的論理和部１６２、置換部１６３を含む。
【００３２】
追加データ付き認証暗号システムに含まれる復号装置２は、図７に示すように、例えば、記憶部２０、入力部２１、第一初期化部２２、タグ復号部２３、暗号化データ逆計算部２４、境界除去部２５、追加データ逆計算部２６、認証部２９、および出力部３０を含む。復号装置２に含まれる暗号化データ逆計算部２４は、図８に示すように、逆置換部２４１、および排他的論理和部２４２を含む。復号装置２に含まれる追加データ逆計算部２６は、図９に示すように、分割部２６１、排他的論理和部２６３、および逆置換部２６４を含む。
【００３３】
暗号化装置１が図１０に示す各ステップの処理を行い、復号装置２が図１２に示す各ステップの処理を行うことにより実施形態の追加データ付き認証暗号方法が実現される。なお、追加データ付き認証暗号方法のうち暗号化装置１が実行する部分を暗号化方法とも呼び、復号装置２が実行する部分を復号方法とも呼ぶ。
【００３４】
暗号化装置１および復号装置２は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。暗号化装置１および復号装置２は、例えば、中央演算処理装置の制御のもとで各処理を実行する。暗号化装置１および復号装置２に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。暗号化装置１および復号装置２の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。暗号化装置１および復号装置２が備える各記憶部は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００３５】
＜暗号化装置１＞
図１０、図１１を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、暗号化装置１が実行する暗号化方法について説明する。
【００３６】
＜記憶部１０＞
暗号化装置１の記憶部１０には、rビットのレート部分とcビットのキャパシティ部分とからなるbビットのステート（以下、復号装置２の記憶部２０に記憶されるステートと区別するために、暗号化ステートとも呼ぶ）と、復号装置２との間であらかじめ共有した共通鍵K(以下、秘密鍵Kともいう)とが記憶されている。例えば、ステートは512ビットとし、レート部分は256ビット、キャパシティ部分は256ビットに構成する（すなわち、b=512, r=256, c=256）。レート部分とキャパシティ部分の長さの比は、処理速度と安全性のトレードオフの関係となっている。レート部分の長さが大きくなると、処理速度は向上するが安全性は低下する。逆に、キャパシティ部分の長さが大きくなると、安全性が向上するが処理速度が低下する。したがって、b, r, cの各値は、所望の処理速度と安全性のバランスを鑑みて適宜設計すればよい。
【００３７】
＜入力部１１＞
ステップＳ１１において、暗号化装置１の入力部１１へ、追加データAとメッセージMとの組(A, M)が入力される。追加データAとメッセージMとはいずれもr ビットの倍長のデータとする。なお、追加データAとメッセージMとをr ビットの倍長のデータに限定するものではなく、r ビットの倍長ではない場合には、例えば、10*パディングを施して、r ビットの倍長のデータに変更して本実施形態を適用してもよい。入力部１１は、メッセージMをメッセージ計算部１６へ、追加データAを追加データ計算部１４へ入力する。
【００３８】
＜初期化部１２＞
ステップＳ１２において、暗号化装置１の初期化部１２は、予め定めたビット列と秘密鍵Kとを連結した値を暗号化ステートの初期値S0として設定する。例えば、初期化部１２は、記憶部１０に記憶されている暗号化ステートのうち、レート部分の値を0（すなわち、すべてのビットが0のビット列）に、キャパシティ部分の値を秘密鍵Kの値に設定して初期化する。
【００３９】
＜追加データ計算部１４＞
ステップＳ１４において、暗号化装置１の追加データ計算部１４は、入力部１１から追加データAを受け取り、その追加データAを用いて記憶部１０に記憶された暗号化ステートの値を更新する。
【００４０】
この場合、追加データ計算部１４は以下のように構成する。
【００４１】
（分割部１４１）
追加データ計算部１４の分割部１４１は、追加データAをrビットのブロックに分割する。なお、追加データAのビット長を|A|とし、n=1,2,…,|A|/rとし、追加データAを|A|/r個に分割して得られる各値をAnとする。第一ブロックA1のrビットをArと表し、残りの部分をA'と表す。即ちA→Ar||A'である。本実施形態では、Arに秘匿対象のデータ(例えば秘密ナンス)を格納するものとする。
【００４２】
（排他的論理和部１４２）
追加データ計算部１４の排他的論理和部１４２は、bビットのステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める。
【００４３】
（置換部１４３）
追加データ計算部１４の置換部１４３は、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める。なお、置換f:{0, 1}b→{0, 1}bは、bビットのビット列dをbビットのビット列eに置換する関数であり、入力された値を復元する逆関数f-1:{0, 1}b→{0, 1}b(bビットのビット列eをbビットのビット列dに置換する関数)を定義できる関数である。置換fとしては、例えば、非特許文献２に記載されている技術を用いることができる。n=1から順にn=|A|/rまで排他的論理和部１４２及び置換部１４３の処理を繰り返す。
【００４４】
そして、置換部１４３は、n=|A|/rのときに得られる暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIとして出力する。
【００４５】
＜境界設定部１５＞
ステップＳ１５において、暗号化装置１の境界設定部１５は、追加データ計算部１４から暗号化ステートS|A|/rを受け取り、暗号化ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させ、暗号化ステートS|A'|/rを更新する。例えば、境界設定部１５は、暗号化ステートのキャパシティ部分と整数値1（すなわち、最下位ビットのみが1のビット列）との排他的論理和を計算し、その計算結果により暗号化ステートのキャパシティ部分を更新する。言い換えると、境界設定部１５は、暗号化ステートの最下位ビットのみを反転させる。この操作は、受信者が暗号化データCと追加データAとの境界を判別できるようにするために行われるものである。
【００４６】
＜メッセージ計算部１６＞
ステップＳ１６において、暗号化装置１のメッセージ計算部１６は、入力部１１からメッセージMを受け取り、そのメッセージMを用いて記憶部１０に記憶された暗号化ステートの値を更新する。
【００４７】
（分割部１６１）
メッセージ計算部１６の分割部１６１は、メッセージMをrビットのブロックに分割する。メッセージMのビット長を|M|とし、m=1,2,…,|M|/rとし、メッセージMを|M|/r個に分割して得られる各値をMmとする。
【００４８】
（排他的論理和部１６２）
メッセージ計算部１６の排他的論理和部１６２は、bビットの暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1のrビットに対し、メッセージMmとの排他的論理和SR,|A|/r+m-1 xor Mmを求める。
【００４９】
（置換部１６３）
メッセージ計算部１６の置換部１６３は、暗号化ステートS|A|/r+m-1のレート部分SR,|A|/r+m-1を排他的論理和SR,|A|/r+m-1xor Mmに置換えたビット列を置換fを用いて置換し、暗号化ステートS|A|/r+mを求め、暗号化ステートS|A|/r+mのレート部分のrビットを暗号化データCmとし、|M|/r個の暗号化データCmを含む暗号化データC=(C1,C2,…,C|M|/r)を出力する。
【００５０】
＜タグ生成部１７＞
ステップＳ１７において、暗号化装置１のタグ生成部１７は、暗号化ステートS|A|/r+|M|/rをメッセージ計算部１６から受け取り、秘密鍵Kを記憶部１０から取り出し、暗号化ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rと秘密鍵Kとの排他的論理和を計算し、その計算結果をタグTとして出力する。
【００５１】
＜出力部１８＞
ステップＳ１８において、暗号化装置１の出力部１８は、暗号化データCをメッセージ計算部１６から、タグTをタグ生成部１７から、値A'を分割部１６１から、復元情報RIを置換部１４３から受け取り、暗号化データCとタグTと値A'と復元情報RIとの組(C, T, A', RI)を復号装置２へ送信する。
【００５２】
＜復号装置２＞
図１２から図１３を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、復号装置２が実行する復号方法について説明する。
【００５３】
＜記憶部２０＞
復号装置２の記憶部２０には、rビットのレート部分とcビットのキャパシティ部分とからなるbビットのステート（以下、暗号化装置１の記憶部１０に記憶される暗号化ステートと区別するために、復号ステートと呼ぶ）と、暗号化装置１との間であらかじめ共有した秘密鍵Kとが記憶されている。b, r, cの各値は、暗号化装置１の記憶部１０に記憶されたステートと同じものとする。
【００５４】
＜入力部２１＞
ステップＳ２１において、復号装置２の入力部２１へ、暗号化装置１から受信した暗号化データCとタグTと値A'と復元情報RIとの組(C, T, A', RI)が入力される。本実施形態では、値A'は追加データAに含まれる下位(|A|-r)ビット分のデータである。入力部２１は、暗号化データCの最終ブロックとタグTとを第一初期化部２２へ、値A'を追加データ逆計算部２６へ、復元情報RIと暗号化データCの最終ブロック以外の各ブロックを暗号化データ逆計算部２４へそれぞれ入力する。
【００５５】
＜第一初期化部２２＞
ステップＳ２２において、復号装置２の第一初期化部２２は、入力部２１から暗号化データCの最終ブロックとタグTとを受け取り、記憶部２０に記憶されている復号ステートのうち、レート部分の値を暗号化データCの最終ブロックの値に、キャパシティ部分の値をタグTの値に設定して初期化する。言い換えると、第一初期化部２２は、暗号化データC=(C1,C2,…,C|M|/r)に含まれる暗号化データC|M|/rとcビットのタグTとを連結した値を復号ステートSの初期値S|A|/r+|M|/rとして設定する。なお、以降の処理において、S|A|/r+|M|/r,S|A|/r+|M|/r-1,…,S|A|/rの順で復号ステートSを更新していく。
【００５６】
＜タグ復号部２３＞
ステップＳ２３において、復号装置２のタグ復号部２３は、第一初期化部２２から復号ステートS|A|/r+|M|/rを受け取り、そのキャパシティ部分SC,|A|/r+|M|/rとcビットの秘密鍵Kとの排他的論理和SC,|A|/r+|M|/rxor Kを求める。
【００５７】
＜暗号化データ逆計算部２４＞
ステップＳ２４において、復号装置２の暗号化データ逆計算部２４は、入力部２１から暗号化データCの最終ブロック以外の各ブロックを受け取り、その暗号化データCの各ブロックCmを用いて記憶部２０に記憶された復号ステートS|A|/r+mの値を更新する。m=|M|/r,|M|/r-1,…,1である。
【００５８】
（逆置換部２４１）
暗号化データ逆計算部２４の逆置換部２４１は、bビットの復号ステート全体に対し、置換fの逆関数f-1を計算し、その計算結果を新たな復号ステートの値とする。例えば、m=|M|/r(暗号化データCの最終ブロック)において、逆置換部２４１は、復号ステートS|A|/r+|M|/rのキャパシティ部分SC,|A|/r+|M|/rを排他的論理和SC,|A|/r+|M|/rxor Kに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+|M|/r-1を求める。また、m=(|M|/r)-1,(|M|/r)-2,…,1において、逆置換部２４１は、復号ステートS|A|/r+mのレート部分SR,|A|/r+mを暗号化データCmに置換えたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r+m-1を求める。なお、逆関数f-1:{0, 1}b→{0, 1}bは、上述の通り、置換fの逆関数f-1であり、bビットのビット列eをbビットのビット列dに置換する関数である。
【００５９】
（排他的論理和部２４２）
m=|M|/r-1,(|M|/r)-2,…,2,1において、暗号化データ逆計算部２４の排他的論理和部２４２は、復号ステートS|A|/r+mのレート部分SR,|A|/r+mと、暗号化データCmとの排他的論理和SR,|A|/r+m xor Cmを計算し、計算結果を復号データMm+1,Dとして出力部３０から出力する。なお、|M|/r個の復号データMm,Dを結合したものを最終的に出力する復号データMD=(M1,D||M2,D||…||M|M|/r,D)とする。ただし、復号データM1,D(第一ブロックの暗号化データを復号したもの)は、復号ステートS|A|/rのレート部分SR,|A|/rと、復元情報RIとの排他的論理和SR,|A|/r xor RIを計算し、計算結果を復号データM1,Dとして出力部３０から出力する。改ざん等なされていなければM=MDとなる。
【００６０】
＜境界除去部２５＞
ステップＳ２５において、復号装置２の境界除去部２５は、暗号化データ逆計算部２４から復号ステートS|A|/rを受け取り、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させる。例えば、復号ステートのキャパシティ部分と整数値1との排他的論理和を計算し、その計算結果により復号ステートのキャパシティ部分を更新する。すなわち、境界除去部２５は、復号ステートの最下位ビットのみを反転させる。
【００６１】
＜追加データ逆計算部２６＞
ステップＳ２６において、復号装置２の追加データ逆計算部２６は、入力部２１から値A'を受け取り、その値A'を用いて記憶部２０に記憶された復号ステートの値を更新する。この場合、追加データ逆計算部２６は以下のように構成する。
【００６２】
（分割部２６１）
追加データ逆計算部２６の分割部２６１は、値A'をrビットのブロックに分割する。なお、値A'のビット長を|A'|とし、n=1,2,…,|A'|/rとし、値A'を|A'|/r個に分割して得られる各値をA'nとする。なお、|A'|=|A|-rであり、n=1,2,…,|A|/r-1である。
【００６３】
（逆置換部２６４）
n=|A|/rの場合、追加データ逆計算部２６の逆置換部２６４は、復号ステートS|A|/rのレート部分SR,|A|/rを復元情報RIに置換え、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める。
【００６４】
n=|A|/r-1,|A|/r-2,…,1の場合(|A'|=|A|-rなので、n=|A'|/r,|A'|/r-1,…,1の場合)、追加データ逆計算部２６の逆置換部２６４は、復号ステートSnのレート部分SR,nを排他的論理和SR,n xor A'nに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める。
【００６５】
（排他的論理和部２６３）
追加データ逆計算部２６の排他的論理和部２６３は、bビットの復号ステートSnのレート部分SR,nのrビットに対し、値A'nとの排他的論理和SR,n xor A'nを求める。
【００６６】
追加データ逆計算部２６は、n=|A|/r-1から順にn=1まで逆置換部２６４及び排他的論理和部２６３の処理を繰り返す。
【００６７】
＜認証部２９＞
ステップＳ２９において、復号装置２の認証部２９は、追加データ逆計算部２６から復号ステートS0を受け取り、記憶部２０から秘密鍵Kを取り出し、復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行う。２つの値が等しい場合は、ステップＳ３０１へ処理を進め、予め定めたビット列(初期化部１２の初期値に対応する値であり、この例ではすべてのビットが0のビット列)と復号ステートS0のレート部分SR,0との排他的論理和を値Arとして出力部３０から出力する。二つの値が等しくない場合は、ステップＳ３０２へ処理を進め、復号に失敗した旨を表すエラーコードを出力部３０から出力する。
【００６８】
＜効果＞
以上の構成により、秘密ナンスを利用できるAPEを実現することができる。また、従来のAPEでは、暗号化処理は一種類の置換fしか使わない反面、復号処理の際に置換fと逆関数f-1の2種類の置換を実装する必要がある。従って復号装置での実装コストが大きいという問題がある。本実施形態の復号装置は逆関数f-1の一種類の実装だけで良く、実装効率が改善される。また、暗号化装置側は置換fだけを実装すればよく、暗号化装置の実装コストの増大を避けることができる。
【００６９】
なお、本実施形態に係る暗号化装置のことを暗号化データを生成するという意味で暗号化データ生成装置ともいい、本実施形態に係る復号装置のことを復号データを生成するという意味で復号データ生成装置ともいう。なお、暗号化データ及び復号データは電子計算機による処理の用に供する情報であり、(i)暗号化データ生成装置を用いた暗号化データ生成方法に係る発明及び(ii)復号データ生成装置を用いた復号データ生成方法に係る発明が、特許法第二条第三項第三号の「物を生産する方法の発明」に該当することは言うまでもない。
【００７０】
＜第二実施形態＞
第一実施形態と異なる部分を中心に説明する。
【００７１】
第一実施形態では、秘匿対象のデータ(例えば秘密ナンス)のデータ量をrビット(ステートのレート部分のデータ量と同じ)としたが、本実施形態では、秘匿対象のデータのデータ量をP×rとする。Pは1以上の整数の何れかとする。ただし、秘匿対象のデータをrビットの倍長のデータに限定するものではなく、r ビットの倍長ではない場合には、例えば、10*パディングを施して、r ビットの倍長のデータに変更して本実施形態を適用してもよい。
【００７２】
＜暗号化装置１＞
図１０、図１４、図１５を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、暗号化装置１が実行する暗号化方法について説明する。
【００７３】
＜追加データ計算部１４＞
ステップＳ１４において、暗号化装置１の追加データ計算部１４は、入力部１１から追加データAを受け取り、その追加データAを用いて記憶部１０に記憶された暗号化ステートの値を更新する。
【００７４】
この場合、追加データ計算部１４は以下のように構成する。
【００７５】
（分割部１４１）
追加データ計算部１４の分割部１４１は、追加データAをrビットのブロックに分割する。なお、追加データAのビット長を|A|とし、n=1,2,…,|A|/rとし、追加データAを|A|/r個に分割して得られる各値をAnとする。追加データAに含まれる(P×rビット分の)秘匿対象のデータをAr=(Ar1,Ar2,…,ArP)と表し、((|A|-(P×r))ビット分の)残りの部分をA'=(A'1,A'2,…,A'|A|/r-P)と表す。なお、p=1,2,…,Pとし、秘匿対象のデータをArpとし、q=1,2,…,|A|/r-Pとし、残りの部分をA'qとする。秘匿対象のデータに含まれるデータAr1は、追加データAの先頭に配置する必要がある。秘匿対象のデータAr2,…,ArP及び部分A'1,A'2,…,A'|A|/r-Pは、追加データAの中にどのように配置してもよい。例えば、追加データAの先頭に秘匿対象のデータAr1,Ar2,…,ArPを配置する場合にはA→Ar||A'であり、追加データAの先頭に秘匿対象のデータの先頭のデータAr1を配置し、残りの秘匿対象のデータAr2,…,ArPを追加データAの最後に配置する場合にはA→Ar1||A'||Ar2||…||ArPである。分割した部分A'qと部分A'q+1との間に秘匿対象のデータArpを配置してもよいが、実用的な例としては上述の二つの配置例が考えられる。なお、追加データAにおける秘匿対象のデータAr2,…,ArP及び部分A'1,A'2,…,A'|A|/r-Pの配置は、受信者と送信者との間であらかじめ共有しておく。
【００７６】
（排他的論理和部１４２）
追加データ計算部１４の排他的論理和部１４２は、bビットのステートSn-1のレート部分SR,n-1のrビットに対し、値Anとの排他的論理和SR,n-1 xor Anを求める。
【００７７】
さらに、本実施形態では、排他的論理和部１４２は、値Anが秘匿対象のデータAr2,…,ArPの場合、ステートSn-1のレート部分SR,n-1を復元情報RI1,RI2,…,RIP-1として出力する。
【００７８】
図１４は追加データAの先頭に秘匿対象のデータAr1,Ar2,…,ArPを配置した場合の処理例を示し、図１５は追加データAの先頭に秘匿対象のデータの先頭のデータAr1を配置し、残りの秘匿対象のデータAr2,…,ArPを追加データAの最後に配置した場合の例を示す。
【００７９】
（置換部１４３）
追加データ計算部１４の置換部１４３は、暗号化ステートSn-1のレート部分SR,n-1を排他的論理和SR,n-1 xor Anに置換えたビット列を置換fを用いて置換し、暗号化ステートSnを求める。
【００８０】
そして、置換部１４３は、n=|A|/rのときに得られる暗号化ステートS|A|/rのレート部分SR,|A|/rを復元情報RIPとして出力する。
【００８１】
境界設定部１５、メッセージ計算部１６、タグ生成部１７における処理は第一実施形態と同様である。
【００８２】
＜出力部１８＞
ステップＳ１８において、暗号化装置１の出力部１８は、暗号化データCをメッセージ計算部１６から、タグTをタグ生成部１７から、値A'を分割部１６１から、復元情報RI1,RI2,…,RIP-1を排他的論理和部１６２から、復元情報RIPを置換部１４３から受け取り、暗号化データCとタグTと値A'と復元情報RI=(RI1,RI2,…,RIP)との組(C, T, A', RI)を復号装置２へ送信する。
【００８３】
＜復号装置２＞
図１２、図１６、図１７を参照して、実施形態の追加データ付き認証暗号システムが実行する追加データ付き認証暗号方法のうち、復号装置２が実行する復号方法について説明する。
【００８４】
＜入力部２１＞
ステップＳ２１において、復号装置２の入力部２１へ、暗号化装置１から受信した暗号化データCとタグTと値A'と復元情報RIとの組(C, T, A', RI)が入力される。本実施形態では、値A'は追加データAに含まれる(|A|-(P×r))ビット分のデータである。入力部２１は、暗号化データCの最終ブロックとタグTとを第一初期化部２２へ、値A'と復元情報RI1,RI2,…,RIP-1を追加データ逆計算部２６へ、復元情報RIPと暗号化データCの最終ブロック以外の各ブロックを暗号化データ逆計算部２４へそれぞれ入力する。
【００８５】
第一初期化部２２、タグ復号部２３、暗号化データ逆計算部２４、境界除去部２５における処理は第一実施形態と同様である。但し、復元情報RIに代えて、復元情報RIPを用いる。
【００８６】
＜追加データ逆計算部２６＞
ステップＳ２６において、復号装置２の追加データ逆計算部２６は、入力部２１から値A'と復元情報RI1,RI2,…,RIP-1を受け取り、これらの値を用いて記憶部２０に記憶された復号ステートの値を更新する。この場合、追加データ逆計算部２６は以下のように構成する。
【００８７】
（分割部２６１）
追加データ逆計算部２６の分割部２６１は、値A'をrビットのブロックに分割する。なお、値A'のビット長を|A'|とし、q=1,2,…,|A'|/rとし、値A'を|A'|/r個に分割して得られる各値をA'qとする。なお、ここでは、|A'|=|A|-(r×P)であり、q=1,2,…,|A|/r-Pである。
【００８８】
（逆置換部２６４）
n=|A|/rの場合、追加データ逆計算部２６の逆置換部２６４は、復号ステートS|A|/rのレート部分SR,|A|/rを復元情報RIPに置換え、復号ステートS|A|/rのキャパシティ部分SC,|A|/rの所定のビットを反転させたビット列を逆関数f-1を用いて置換し、復号ステートS|A|/r-1を求める。
【００８９】
n=|A|/r-1,|A|/r-2,…,1の場合、追加データ逆計算部２６の逆置換部２６４は、復号ステートSnのレート部分SR,nを、後述する排他的論理和部２６３の出力値である(i)排他的論理和SR,n xor A'q、または、(ii)復元情報RIpに置換えたビット列を逆関数f-1を用いて置換し、復号ステートSn-1を求める。
【００９０】
（排他的論理和部２６３）
追加データ逆計算部２６の排他的論理和部２６３は、(i)値A'qまたは(ii)復元情報RIpを入力とする。
【００９１】
(i)排他的論理和部２６３は、値A'qを入力としたとき、bビットの復号ステートSnのレート部分SR,nのrビットに対し、値A'qとの排他的論理和SR,n xor A'qを求め、逆置換部２６４に出力する。
【００９２】
(ii)排他的論理和部２６３は、復元情報RIpを入力としたとき、bビットの復号ステートSnのレート部分SR,nのrビットに対し、復元情報RIpとの排他的論理和SR,n xor RIpを求め、排他的論理和SR,nxor RIpを秘匿対象のデータAp+1として出力する。さらに、排他的論理和部２６３は、復号ステートSnのレート部分SR,nを復元情報RIpに置換えたビット列を逆置換部２６４に出力する。
【００９３】
追加データ逆計算部２６は、p=1,2,…，P-1、q=|A|/r-P,|A|/r-P-1,…,1において、逆置換部２６４及び排他的論理和部２６３の処理を繰り返す。
【００９４】
図１６は追加データAの先頭に秘匿対象のデータAr1,Ar2,…,ArPを配置した場合の処理例を示し、図１７は追加データAの先頭に秘匿対象のデータの先頭のデータAr1を配置し、残りの秘匿対象のデータAr2,…,ArPを追加データAの最後に配置した場合の例を示す。追加データAにおける秘匿対象のデータAr2,…,ArP及び部分A'1,A'2,…,A'|A|/r-Pの配置は、受信者と送信者との間であらかじめ共有しているため、排他的論理和部２６３及び逆置換部２６４は、入力される順番に従って、(i)値A'qまたは(ii)復元情報RIpが入力されるのか、復号ステートSnのレート部分SR,nを、(i)排他的論理和SR,n xor A'q、または、(ii)復元情報RIpに置換えたビット列が入力されるのかを判断することができる。
【００９５】
＜認証部２９＞
ステップＳ２９において、復号装置２の認証部２９は、追加データ逆計算部２６から復号ステートS0を受け取り、記憶部２０から秘密鍵Kを取り出し、復号ステートS0のキャパシティ部分SC,0と秘密鍵Kとが一致するか否かによりメッセージ認証を行う。２つの値が等しい場合は、ステップＳ３０１へ処理を進め、予め定めたビット列(初期化部１２の初期値に対応する値であり、この例ではすべてのビットが0のビット列)と復号ステートS0のレート部分SR,0との排他的論理和を値Ar1として出力部３０から出力する。二つの値が等しくない場合は、ステップＳ３０２へ処理を進め、復号に失敗した旨を表すエラーコードを出力部３０から出力する。
【００９６】
＜効果＞
このような構成により、第一実施形態と同様の効果を得ることができる。さらに、秘匿対象のデータの大きさを柔軟に設定することができる。なお、P=1のとき、第一実施形態と同様の構成となるため、第一実施形態は第二実施形態の一例とも言える。
【００９７】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００９８】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００９９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１００】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１０１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０２】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019015919.tif 000003
【図２】
2019015919.tif 000004
【図３】
2019015919.tif 000005
【図４】
2019015919.tif 000006
【図５】
2019015919.tif 000007
【図６】
2019015919.tif 000008
【図７】
2019015919.tif 000009
【図８】
2019015919.tif 000010
【図９】
2019015919.tif 000011
【図１０】
2019015919.tif 000012
【図１１】
2019015919.tif 000013
【図１２】
2019015919.tif 000014
【図１３】
2019015919.tif 000015
【図１４】
2019015919.tif 000016
【図１５】
2019015919.tif 000017
【図１６】
2019015919.tif 000018
【図１７】
2019015919.tif 000019