(57)【要約】【課題】ｉのビット表現の最下位から並んでいる０の個数ｊを計算する処理を省略することにより、マスクを効率的に計算することができるマスク生成技術を提供する。【解決手段】秘密情報Ｌとｘ２＾ｐとの積Ｌ［ｐ］を求める積算出部と、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］を求める連続０ビット算出部と、積Ｌ［ｐ］と個数Ｎ［ｑ］とが格納される記憶部と、ｉが２ｋの倍数ではないときには、該ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋに基づき、その剰余ｉ  ｍｏｄ  ２ｋのビット表現の最下位から並んでいる０の個数Ｎ［ｉ  ｍｏｄ  ２ｋ］を記憶部から取り出し、さらに、この個数Ｎ［ｉ  ｍｏｄ  ２ｋ］に応じた積Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を記憶部から取り出す積取得部と、ｉ−１におけるマスクＧ（ｉ−１）Ｌと積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求める排他的論理和算出部とを含む。【選択図】図５
2014081569.tif 000002
【特許請求の範囲】
【請求項１】
グレイ符号を利用して暗号利用モードで用いるマスクを生成するマスク生成装置であって、
ｆ（ｘ）をＧＦ（２）上のｎ次既約多項式とし、ガロア体ＧＦ（２ｎ）の元は
【数５】
2014081569.tif 000007
を使い、ｎ−１次以下の多項式で表現され、その多項式の係数をｎビットのビット列として表すものとし、ｆｌｏｏｒ（Ａ）をＡ以下の最大の整数を返す関数とし、ｍを生成するマスクの個数とし、ｐ＝０，１，…，ｆｌｏｏｒ（ｌｏｇ２（ｍ））における秘密情報Ｌとｘ２＾ｐとの積Ｌ［ｐ］を求める積算出部と、
ｋを正整数とし、ｑ＝１，２，…，２ｋ−１における、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］を求める連続０ビット算出部と、
（ｆｌｏｏｒ（ｌｏｇ２（ｍ））＋１）個の前記積Ｌ［ｐ］と２ｋ−１個の前記０の個数Ｎ［ｑ］とが格納される記憶部と、
ｉが２ｋの倍数であるときには、該ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｎｔｚ（ｉ）に応じた前記積Ｌ［ｎｔｚ（ｉ）］を前記記憶部から取り出し、ｉが２ｋの倍数ではないときには、該ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋに基づき、その剰余ｉ  ｍｏｄ  ２ｋのビット表現の最下位から並んでいる０の個数Ｎ［ｉ  ｍｏｄ  ２ｋ］を前記記憶部から取り出し、さらに、この個数Ｎ［ｉ  ｍｏｄ  ２ｋ］に応じた前記積Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を前記記憶部から取り出す積取得部と、
ｉ−１におけるマスクＧ（ｉ−１）Ｌと前記積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求め、ｉにおけるマスクＧ（ｉ）Ｌとする排他的論理和算出部と、を含む、
マスク生成装置。
【請求項２】
請求項１記載のマスク生成装置であって、
前記積取得部は、複数の積Ｌ［ｐ］をオーバーラップさせて取得し、２ｋ個の積Ｌ［ｐ］を前記記憶部から取り出す処理を繰り返し、繰り返し処理の中で１個のマスクを生成する毎に生成したマスクの個数ｉがｍ以下か否かを判定し、ｉ≦２ｋのときの判定結果に基づき、ｉ＞２ｋにおける判定結果を推定し、ｉを２ｋで割ったときの剰余ｑに基づき、その剰余ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］をＮ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］の順で前記記憶部から取り出し、さらに、この個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］に応じた積Ｌ［ｐ］を前記記憶部からＬ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］の順で取り出し、その次に、ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｐに応じた積Ｌ［ｎｔｚ（ｉ）］を前記記憶部から取り出す、
マスク生成装置。
【請求項３】
請求項１記載のマスク生成装置であって、
前記積取得部は、２ｋ個の積Ｌ［ｐ］を前記記憶部から取り出す処理を繰り返し、繰り返し処理の中で２ｋ個のマスクを生成する毎に生成したマスクの個数ｉがｍ以下の２ｋの最大の倍数ｍ’以下か否かを判定し、生成したマスクの個数が前記ｍ’以下の場合、ｉを２ｋで割ったときの剰余ｑに基づき、その剰余ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］をＮ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］の順で前記記憶部から取り出し、さらに、この個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］に応じた積Ｌ［ｐ］を前記記憶部からＬ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］の順で取り出し、その次に、ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｐに応じた積Ｌ［ｎｔｚ（ｉ）］を前記記憶部から取り出す、
マスク生成装置。
【請求項４】
請求項１から請求項３の何れかに記載のマスク生成装置で生成されたマスクを用いる情報処理装置であって、
鍵Ｋをから拡大鍵ｋ’を生成する拡大鍵生成部と、
鍵Ｋと排他的論理和ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌとを用いて、暗号化または復号する暗号化／復号部と、をさらに含み、
前記排他的論理和算出部は、前記拡大鍵ｋ’とｉ−１におけるマスクＧ（ｉ−１）Ｌとの排他的論理和と、前記積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求め、求めた排他的論理和をｉにおけるマスクＧ（ｉ）Ｌと前記拡大鍵ｋ’との排他的論理和ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌとする、
情報処理装置。
【請求項５】
グレイ符号を利用して暗号利用モードで用いるマスクを生成するマスク生成方法であって、
ｆ（ｘ）をＧＦ（２）上のｎ次既約多項式とし、ガロア体ＧＦ（２ｎ）の元は
【数６】
2014081569.tif 000008
を使い、ｎ−１次以下の多項式で表現され、その多項式の係数をｎビットのビット列として表すものとし、ｆｌｏｏｒ（Ａ）をＡ以下の最大の整数を返す関数とし、ｍを生成するマスクの個数とし、ｐ＝０，１，…，ｆｌｏｏｒ（ｌｏｇ２（ｍ））における秘密情報Ｌとｘ２＾ｐとの積Ｌ［ｐ］を求める積算出ステップと、
ｋを正整数とし、ｑ＝１，２，…，２ｋ−１における、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］を求める連続０ビット算出ステップと、
（ｆｌｏｏｒ（ｌｏｇ２（ｍ））＋１）個の前記積Ｌ［ｐ］と２ｋ−１個の前記０の個数Ｎ［ｑ］とを記憶部に格納する記憶ステップと、
ｉが２ｋの倍数であるときには、該ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｎｔｚ（ｉ）に応じた前記積Ｌ［ｎｔｚ（ｉ）］を前記記憶部から取り出し、ｉが２ｋの倍数ではないときには、該ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋに基づき、その剰余ｉ  ｍｏｄ  ２ｋのビット表現の最下位から並んでいる０の個数Ｎ［ｉ  ｍｏｄ  ２ｋ］を前記記憶部から取り出し、さらに、この個数Ｎ［ｉ  ｍｏｄ  ２ｋ］に応じた前記積Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を前記記憶部から取り出す積取得ステップと、
ｉ−１におけるマスクＧ（ｉ−１）Ｌと前記積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求め、ｉにおけるマスクＧ（ｉ）Ｌとする排他的論理和算出ステップと、を含む、
マスク生成方法。
【請求項６】
請求項５記載のマスク生成方法であって、
前記積取得ステップにおいて、複数の積Ｌ［ｐ］をオーバーラップさせて取得し、２ｋ個の積Ｌ［ｐ］を前記記憶部から取り出す処理を繰り返し、繰り返し処理の中で１個のマスクを生成する毎に生成したマスクの個数ｉがｍ以下か否かを判定し、ｉ≦２ｋのときの判定結果に基づき、ｉ＞２ｋにおける判定結果を推定し、ｉを２ｋで割ったときの剰余ｑに基づき、その剰余ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］をＮ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］の順で前記記憶部から取り出し、さらに、この個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］に応じた積Ｌ［ｐ］を前記記憶部からＬ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］の順で取り出し、その次に、ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｐに応じた積Ｌ［ｎｔｚ（ｉ）］を前記記憶部から取り出す、
マスク生成方法。
【請求項７】
請求項５記載のマスク生成方法であって、
前記積取得ステップにおいて、２ｋ個の積Ｌ［ｐ］を前記記憶部から取り出す処理を繰り返し、繰り返し処理の中で２ｋ個のマスクを生成する毎に生成したマスクの個数ｉがｍ以下の２ｋの最大の倍数ｍ’以下か否かを判定し、生成したマスクの個数が前記ｍ’以下の場合、ｉを２ｋで割ったときの剰余ｑに基づき、その剰余ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］をＮ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］の順で前記記憶部から取り出し、さらに、この個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］に応じた積Ｌ［ｐ］を前記記憶部からＬ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］の順で取り出し、その次に、ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｐに応じた積Ｌ［ｎｔｚ（ｉ）］を前記記憶部から取り出す、
マスク生成方法。
【請求項８】
請求項１から請求項３の何れかに記載のマスク生成装置、または、請求項４記載の情報処理装置として、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グレイ符号を利用して暗号利用モードで用いるマスクを生成するマスク生成技術、及びそのマスク生成装置で生成されたマスクを用いる情報処理技術に関する。
【背景技術】
【０００２】
データの秘匿または改竄検知のためには暗号技術が有効である。暗号技術には、ＲＳＡ暗号等を含む非対称鍵技術、及び、共通鍵暗号を利用したＡＥＳ（Advanced Encryption Standard）暗号等を含む対称鍵技術が存在する。非対称鍵技術は、対称鍵技術と比べ、鍵の取扱が容易である。しかし、速度の面では、対称鍵技術が、圧倒的に有利である。そのため、実際、大量のデータの秘匿や改竄検知には、ＡＥＳ暗号等を利用した暗号利用モードが多く利用されており、ＳＳＬ（Secure Sockets Layer）等で実用化されている。
【０００３】
もともとブロック暗号では１ブロック（ＡＥＳ暗号では１２８ビット）の暗号化しかできなかった。暗号利用モードは、ブロック暗号を単純な演算で組み合わせて、多ブロックの暗号化処理や改竄検知（メッセージ認証）等の機能を追加する方法である。
【０００４】
従来より、暗号利用モードとして、守秘機能を実現するＣＦＢ（Cipher Feed Back）モードや、メッセージ認証を実現するＣＢＣ−ＭＡＣ（Cipher Block Chaining - Message Authentication Code）等が知られていた。しかし、これらの暗号利用モードは、高い安全性を示せないという問題があった。
【０００５】
その後、認証暗号モードＯＣＢ（Offset CodeBook）、ＭＡＣモードＰＭＡＣ（Parallelizable Message Authentication Code）、ディスク暗号ＸＴＳといった暗号利用モードが提案され、高い安全性が示されるようになった。
【０００６】
高い安全性が示される暗号利用モードのいくつかでは、ガロア体ＧＦ（２ｎ）の演算が、使われている。ｆ（ｘ）をＧＦ（２）上のｎ次既約多項式とし、ガロア体ＧＦ（２ｎ）の元は、
【０００７】
【数１】
2014081569.tif 000003
【０００８】
を使い、ｎ−１次以下の多項式で表現され、その多項式の係数をｎビットのビット列として表す。ここで、ｘ倍する演算を「２倍算」と呼び、上記暗号利用モードを含む多くの暗号利用モードで利用されている。また、秘密情報Ｌを用い、ｍ個のマスクｘｉ・Ｌを利用した暗号利用モードが、多数発表されている。ただし、ｉ＝１，２，…，ｍであり、Ａ・Ｂは、有限体上の元Ａと元Ｂとの積を表し、以後、「・」を省略することもある。また、グレイ符号を利用した暗号利用モードも提案されている（非特許文献１及び２参照）。ここで、ｉ番目のグレイ符号をＧ（ｉ）とすると、Ｇ（ｉ）＝ｉ  ｘｏｒ  （ｉ＞＞１）と表せる。ただし、Ａ  ｘｏｒ  Ｂはビット列Ａとビット列Ｂのビット毎の排他的論理和を表し、Ａ＞＞Ｂはビット列Ａを右にＢビットシフトすることを意味する。グレイ符号を利用した暗号利用モードにおけるｉ番目のマスクをＧ（ｉ）Ｌとする。また、ｗ２（Ａ）をビット列Ａのハミング重み（２進数表現で１の数の合計）を返す関数とすると、グレイ符号には、
ｗ２（Ｇ（ｉ）  ｘｏｒ  Ｇ（ｉ−１））＝１
という性質があることから、ｉ−１番目のマスクＧ（ｉ−１）Ｌからｉ番目のマスクＧ（ｉ）Ｌを以下のように生成することができる。
Ｇ（ｉ）Ｌ←Ｇ（ｉ−１）Ｌ  ｘｏｒ  ｘ２＾ｊＬ        （１）
ただし、上付き添え字におけるＡ＾ＢはＡのＢ乗（つまり、ＡＢ）を表し、ｊ＝１，…，ｎ−１であり、ｊはｉのビット表現の最下位から並んでいる０の個数と一致する。ここで、ｘ２＾ｊＬは、０の個数ｊに応じて変化する。そのため、予めｊ＝１，…，ｎ−１におけるｘ２＾ｊＬを計算し、０の個数ｊ毎にテーブルに記憶しておけば、ｉのビット表現の最下位から並んでいる０の個数ｊに基づき、ｉに対応するｘ２＾ｊＬをテーブルから検索し、ｉ−１番目に求めたマスクＧ（ｉ−１）Ｌとｘ２＾ｊＬとの排他的論理和を求めるだけで、ｉ番目のマスクＧ（ｉ）Ｌを求めることができる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ted Krovetz and Phillip Rogaway, "The Software Performance of Authenticated-Encryption Modes", FSE 2011, Springer, 2011, vol. 6733, pp. 306-327
【非特許文献２】Phillip Rogaway, "Authenticated-Encryption with Associated-Data", ACM Conference on Computer and Communications Security 2002 (CCS'02), ACM Press, September 2002, pp. 98-107
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来技術では、ｘ２＾ｊＬを検索するために、マスク毎にｉのビット表現の最下位から並んでいる０の個数ｊを計算する必要がある。ｉのビット表現の最下位から並んでいる０の個数を計算する処理、及び、処理の結果得られる０の個数をｎｔｚ（ｉ）と記載する。多数のマスクＧ（ｉ）Ｌを生成する場合、この処理ｎｔｚ（ｉ）の処理量も大きなものとなる。
【００１１】
本発明は、処理ｎｔｚ（ｉ）のいくつかを省略することにより、マスクＧ（ｉ）Ｌを効率的に計算することができるマスク生成技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明の第一の態様によれば、マスク生成装置は、グレイ符号を利用して暗号利用モードで用いるマスクを生成する。マスク生成装置は、ｆ（ｘ）をＧＦ（２）上のｎ次既約多項式とし、ガロア体ＧＦ（２ｎ）の元は
【００１３】
【数２】
2014081569.tif 000004
【００１４】
を使い、ｎ−１次以下の多項式で表現され、その多項式の係数をｎビットのビット列として表すものとし、ｆｌｏｏｒ（Ａ）をＡ以下の最大の整数を返す関数とし、ｍを生成するマスクの個数とし、ｐ＝０，１，…，ｆｌｏｏｒ（ｌｏｇ２（ｍ））における秘密情報Ｌとｘ２＾ｐとの積Ｌ［ｐ］を求める積算出部と、ｋを正整数とし、ｑ＝１，２，…，２ｋ−１における、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］を求める連続０ビット算出部と、（ｆｌｏｏｒ（ｌｏｇ２（ｍ））＋１）個の積Ｌ［ｐ］と２ｋ−１個の０の個数Ｎ［ｑ］とが格納される記憶部と、ｉが２ｋの倍数であるときには、該ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｎｔｚ（ｉ）に応じた積Ｌ［ｎｔｚ（ｉ）］を記憶部から取り出し、ｉが２ｋの倍数ではないときには、該ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋに基づき、その剰余ｉ  ｍｏｄ  ２ｋのビット表現の最下位から並んでいる０の個数Ｎ［ｉ  ｍｏｄ  ２ｋ］を記憶部から取り出し、さらに、この個数Ｎ［ｉ  ｍｏｄ  ２ｋ］に応じた積Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を記憶部から取り出す積取得部と、ｉ−１におけるマスクＧ（ｉ−１）Ｌと積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求め、ｉにおけるマスクＧ（ｉ）Ｌとする排他的論理和算出部と、を含む。
【００１５】
上記の課題を解決するために、本発明の第二の態様によれば、マスク生成方法は、グレイ符号を利用して暗号利用モードで用いるマスクを生成する。マスク生成方法は、ｆ（ｘ）をＧＦ（２）上のｎ次既約多項式とし、ガロア体ＧＦ（２ｎ）の元は
【００１６】
【数３】
2014081569.tif 000005
【００１７】
を使い、ｎ−１次以下の多項式で表現され、その多項式の係数をｎビットのビット列として表すものとし、ｆｌｏｏｒ（Ａ）をＡ以下の最大の整数を返す関数とし、ｍを生成するマスクの個数とし、ｐ＝０，１，…，ｆｌｏｏｒ（ｌｏｇ２（ｍ））における秘密情報Ｌとｘ２＾ｐとの積Ｌ［ｐ］を求める積算出ステップと、ｋを正整数とし、ｑ＝１，２，…，２ｋ−１における、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］を求める連続０ビット算出ステップと、（ｆｌｏｏｒ（ｌｏｇ２（ｍ））＋１）個の積Ｌ［ｐ］と２ｋ−１個の０の個数Ｎ［ｑ］とを記憶部に格納する記憶ステップと、ｉが２ｋの倍数であるときには、該ｉのビット表現の最下位から並んでいる０の個数ｎｔｚ（ｉ）を求め、この０の個数ｎｔｚ（ｉ）に応じた積Ｌ［ｎｔｚ（ｉ）］を記憶部から取り出し、ｉが２ｋの倍数ではないときには、該ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋに基づき、その剰余ｉ  ｍｏｄ  ２ｋのビット表現の最下位から並んでいる０の個数Ｎ［ｉ  ｍｏｄ  ２ｋ］を記憶部から取り出し、さらに、この個数Ｎ［ｉ  ｍｏｄ  ２ｋ］に応じた積Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を記憶部から取り出す積取得ステップと、ｉ−１におけるマスクＧ（ｉ−１）Ｌと積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求め、ｉにおけるマスクＧ（ｉ）Ｌとする排他的論理和算出ステップと、を含む。
【発明の効果】
【００１８】
本発明は、ｉ≠ｃ２ｋ（ただし、ｃは０以上の任意の整数であり、ｋは所定の正整数）のときに処理ｎｔｚ（ｉ）を省略することにより、マスクＧ（ｉ）Ｌを効率的に計算することができるという効果を奏する。
【図面の簡単な説明】
【００１９】
【図１】ｋ＝２におけるｉと０の個数ｊとの関係を示す図。
【図２】ｋ＝３におけるｉと０の個数ｊとの関係を示す図。
【図３】ｋ＝４におけるｉと０の個数ｊとの関係を示す図。
【図４】ｋ＝５におけるｉと０の個数ｊとの関係を示す図。
【図５】第一実施形態に係るマスク生成装置１００の機能ブロック図。
【図６】第一実施形態に係るマスク生成装置１００の処理フローを示す図。
【図７】記憶部に格納される積Ｌ［ｐ］のデータの例を示す図。
【図８】記憶部に格納される０の個数Ｎ［ｑ］のデータの例を示す図。
【図９】ｋ＝１における、第二実施形態に係るマスク生成装置の積取得部及び排他的論理和算出部の処理フローを示す図。
【図１０】ｋ＝２における、第二実施形態に係るマスク生成装置の積取得部及び排他的論理和算出部の処理フローを示す図。
【図１１】ｋ＝３における、第二実施形態に係るマスク生成装置の積取得部及び排他的論理和算出部の処理フローを示す図。
【図１２】ｋ＝１における、第二実施形態の変形例に係るマスク生成装置の積取得部及び排他的論理和算出部の処理フローを示す図。
【図１３】ｋ＝２における、第二実施形態の変形例に係るマスク生成装置の積取得部及び排他的論理和算出部の処理フローを示す図。
【図１４】ｋ＝３における、第二実施形態の変形例に係るマスク生成装置の積取得部及び排他的論理和算出部の処理フローを示す図。
【図１５】第三実施形態に係る暗号システムの機能ブロック図。
【図１６】第三実施形態に係る情報処理装置（暗号化装置）の機能ブロック図。
【図１７】第三実施形態に係る情報処理装置（暗号化装置）の処理フローを示す図。
【図１８】第三実施形態に係る情報処理装置（復号装置）の機能ブロック図。
【図１９】第三実施形態に係る情報処理装置（復号装置）の処理フローを示す図。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。また、ベクトルや行列の各要素単位で行われる処理は、特に断りが無い限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００２１】
＜第一実施形態＞
＜第一実施形態のポイント＞
正整数ｋを１つ固定する。図１〜図４は、それぞれｋ＝２〜５におけるｉと０の個数ｊとの関係を示す。各図から明らかなように、任意の０以上の整数ｃに対し、０の個数ｊ（＝ｎｔｚ（ｉ）、ｉ＝ｃ２ｋ，ｃ２ｋ＋１，…，（ｃ＋１）２ｋ−１）はｉ＝ｃ２ｋの場合を除いて同じパターンとなる。各図において、同じパターンの部分を破線で囲んでいる。本実施形態では、ｉ＝１，２，…，２ｋ−１について、予めｉのビット表現の最下位から並んでいる０の個数ｊを計算する処理ｎｔｚ（ｉ）を行い、各ｉに対する０の個数ｊを記憶部に記憶しておく。さらに、ｉ≠ｃ２ｋの場合のｉ（＝１，２，…，ｍ）に対応する０の個数ｊを記憶部から取り出す構成とする。０の個数ｊは、ｃが異なっても同じパターンなので、使い回すことができる。よって、ｉ＝ｃ２ｋの場合にのみ０の個数ｊを計算する処理ｎｔｚ（ｉ）を行うことで、処理ｎｔｚ（ｉ）の回数を１／２ｋとすることができる。
【００２２】
＜第一実施形態に係るマスク生成装置１００＞
図５はマスク生成装置１００の機能ブロック図を、図６はその処理フローを示す。なお、図６中、ループ端の上端には変数＝初期値、終値、増分値を、下端には変数を記載している。
【００２３】
マスク生成装置１００は、積算出部１１１、連続０ビット算出部１１３、記憶部１１５、積取得部１１７及び排他的論理和算出部１１９を含む。
【００２４】
マスク生成装置１００は、秘密情報Ｌ、正整数ｋ及び利用者が所望するマスクの個数ｍを入力とし、グレイ符号を利用して暗号利用モードで用いるマスクＧ（ｉ）Ｌをｍ個生成し、出力する。
【００２５】
なお、ｆ（ｘ）をＧＦ（２）上のｎ次既約多項式とし、ガロア体ＧＦ（２ｎ）の元は
【００２６】
【数４】
2014081569.tif 000006
【００２７】
を使い、ｎ−１次以下の多項式で表現され、その多項式の係数をｎビットのビット列として表すものとする。以下、各部の詳細を説明する。
【００２８】
＜積算出部１１１＞
積算出部１１１は、利用者が所望するマスクの個数ｍ及び秘密情報Ｌを受け取り、ｐ＝０，１，…，ｆｌｏｏｒ（ｌｏｇ２（ｍ））における秘密情報Ｌとｘ２＾ｐとの積Ｌ［ｐ］を求め（ｓ１１１）、記憶部１１５に格納する。ただし、ｆｌｏｏｒ（Ａ）をＡ以下の最大の整数を返す関数とする。図７は、記憶部１１５に格納される積Ｌ［ｐ］のデータの例を示す。テーブル１１１Ａ〜テーブル１１１Ｅはそれぞれｍ＝１６、３２、６４、１２８、２５６におけるデータの例を示す。なお、実際には、記憶部１１５にはｘ２＾ｐＬとして具体的な値が格納される。
【００２９】
＜連続０ビット算出部１１３＞
連続０ビット算出部１１３は、正整数ｋを受け取り、処理ｎｔｚ（ｑ）により、ｑ＝１，２，…，２ｋ−１における、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］（＝ｎｔｚ（ｑ））を求め（ｓ１１３）、記憶部１１５に格納する。図８は、記憶部１１５に格納される０の個数Ｎ［ｑ］のデータの例を示す。テーブル１１３Ａ〜テーブル１１３Ｄはそれぞれｋ＝２〜５におけるデータの例を示す。
【００３０】
＜記憶部１１５＞
記憶部１１５には、（ｆｌｏｏｒ（ｌｏｇ２（ｍ））＋１）個の積Ｌ［ｐ］と２ｋ−１個の０の個数Ｎ［ｑ］とが格納される（図７及び図８参照）。
【００３１】
＜積取得部１１７＞
積取得部１１７は、ｉが２ｋの倍数であるか否かを判定する（ｓ１１７ａ）。
【００３２】
さらに、積取得部１１７は、ｉが２ｋの倍数であるときには、処理ｎｔｚ（ｉ）により、ｉのビット表現の最下位から並んでいる０の個数ｐ（＝ｎｔｚ（ｉ））を計算し、この０の個数ｐに応じた積Ｌ［ｐ］（＝Ｌ［ｎｔｚ（ｉ）］）を記憶部１１５から取り出し（ｓ１１７ｂ）、排他的論理和算出部１１９に出力する。
【００３３】
積取得部１１７は、ｉが２ｋの倍数ではないときには、ｉを２ｋで割ったときの剰余ｑ（＝ｉ  ｍｏｄ  ２ｋ）に基づき、その剰余ｑ（＝ｉ  ｍｏｄ  ２ｋ）のビット表現の最下位から並んでいる０の個数ｐ（＝Ｎ［ｑ］＝Ｎ［ｉ  ｍｏｄ  ２ｋ］）を記憶部１１５から取り出し、さらに、この０の個数ｐ（＝Ｎ［ｑ］＝Ｎ［ｉ  ｍｏｄ  ２ｋ］）に応じた積Ｌ［ｐ］（＝Ｌ［Ｎ［ｑ］］＝Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］）を記憶部１１５から取り出し（ｓ１１７ｃ）、排他的論理和算出部１１９に出力する。
【００３４】
つまり、積取得部１１７は、ｉが２ｋの倍数ではないときには、ｉのビット表現の最下位から並んでいる０の個数を計算するのではなく、ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋに基づき、記憶部１１５から０の個数Ｎ［ｉ  ｍｏｄ  ２ｋ］を取り出す。なお、剰余ｉ  ｍｏｄ  ２ｋを求める処理は、ビット列ｉからｋビット以下のビット列を取り出すことで求めることができ、処理ｎｔｚ（ｉ）よりも処理量が小さい。例えば、ビット列ｉに対し、ｋビットより大きい（左側）部分に０を、ｋビット以下（右側）に１を設定したビット列でマスクすることで、ビット列ｉからｋビット以下のビット列を取り出す。取り出したビット列が０の場合にはｓ１１７ｂの処理を、０以外の場合にはｓ１１７ｃの処理を行う。
【００３５】
このような構成により、ｉ≠ｃ２ｋのときに処理ｎｔｚ（ｉ）を省略することができる。
【００３６】
＜排他的論理和算出部１１９＞
排他的論理和算出部１１９は、積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を受け取り、ｉ−１におけるマスクＧ（ｉ−１）Ｌと積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］との排他的論理和を求め（ｓ１１９）、求めた排他的論理和をｉ番目のマスクＧ（ｉ）Ｌとして出力するとともに、ｉ＋１番目のマスクＧ（ｉ＋１）Ｌを求めるために記憶しておく。
【００３７】
＜効果＞
本実施形態では、２ｋ−１個の、ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］からなるテーブルを用いることにより、ｉ≠ｃ２ｋのときに計算コストの高い処理ｎｔｚ（ｉ）を省略することができ、マスクＧ（ｉ）Ｌを効率的に計算することができる。また、グレイ符号を利用してマスクＧ（ｉ）Ｌを生成するＯＣＢ等の暗号利用モードに実装することで、効率的に暗号化または復号する情報処理装置を実現できる。
【００３８】
なお、ｋを大きく設定することで、積取得部１１７において処理ｎｔｚ（ｉ）を省略できる回数を増やすことができるが、連続０ビット算出部１１３における処理量が大きくなる。また、ｋを大きく設定すると、Ｎ［ｑ］が多くなるとともに（メモリを多く使う、図８参照）、検索時の処理量が増加する。よって、利用者が所望するマスクの個数ｍに応じて、マスク生成装置１００の処理量全体が最も小さくなるように１≦ｋ＜ｌｏｇ２ｍの範囲で正整数ｋを設定すればよい。
【００３９】
＜第二実施形態＞
＜第二実施形態のポイント＞
第二実施形態では、積取得部２１７において、ｉが２ｋの倍数であるか否かを判定する処理（ｓ１１７ａ）、及び、ｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋを求める処理を省略することができる。
【００４０】
また、第二実施形態の積取得部２１７は、複数の積をオーバーラップさせて取得し、ｉ≦２ｋにおける処理に基づきｉ＞２ｋにおける分岐予測を行う。このような構成により、さらに処理を効率化することができる。例えば、積取得部２１７は分岐予測機能付きのＣＰＵ（Central Processing Unit）により実現される。
【００４１】
以下、第一実施形態と異なる部分についてのみ説明する。
【００４２】
＜第二実施形態に係るマスク生成装置２００＞
マスク生成装置２００は、積取得部１１７に代えて、積取得部２１７を備える（図５参照）。
【００４３】
積取得部２１７及び排他的論理和算出部１１９は、２ｋ個のマスクを生成する処理を繰り返す（言い換えると、一回の繰り返し処理（ループ処理）の中で２ｋ個のマスクを生成する）。繰り返し処理の中で、１個のマスクを生成する毎に生成したマスクの個数がｍ以下か否かを判定する。このとき、ｉ≦２ｋのときの判定結果（例えば条件式、判定式（ｉ≦ｍ）を満たす）に基づき、ｉ＞２ｋにおける判定結果（例えば条件式、判定式（ｉ≦ｍ）を満たす）を推定する。なお、繰り返し処理では、まず、ｉが２ｋの倍数ではないときに行う処理として以下の処理を行う。ｉを２ｋで割ったときの剰余ｑに基づき、その剰余ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］をＮ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］の順で記憶部１１５から取り出し、さらに、この個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］に応じた積Ｌ［ｐ］を記憶部１１５からＬ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］の順で取り出す。
【００４４】
次に、ｉが２ｋの倍数であるときに行う処理として以下の処理を行う。処理ｎｔｚ（ｉ）により、ｉのビット表現の最下位から並んでいる０の個数ｐ（＝ｎｔｚ（ｉ））を計算し、この０の個数ｐに応じた積Ｌ［ｐ］（＝Ｌ［ｎｔｚ（ｉ）］）を記憶部１１５から取り出す。
【００４５】
なお、ｉ＞２ｋにおける繰り返し処理では、ｉが２ｋの倍数ではない場合に、積取得部２１７において、個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］及び積Ｌ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］を記憶部１１５から取り出す処理を省略し、ｉ≦２ｋにおいて記憶部１１５から取り出した積Ｌ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］を再利用してもよい。
【００４６】
図９〜１１は、それぞれｋ＝１〜３における、積取得部２１７及び排他的論理和算出部１１９の処理フローを示す。なお、図９〜１１中、ループ端の上端には継続条件式を記載している。具体的に図９を用いてｋ＝１の場合について説明する。
【００４７】
＜ｋ＝１の場合＞
まず、積取得部２１７は、初期設定を行う（ｓ２１７ａ）。
【００４８】
次に、積取得部２１７は、ｉ≦ｍにおいて以下の処理を繰り返す。
【００４９】
積取得部２１７は、ｉを２ｋで割ったときの剰余ｑ＝１のビット表現の最下位から並んでいる０の個数Ｎ［１］＝０を記憶部１１５から取り出し、Ｎ［１］＝０に応じた積Ｌ［０］を記憶部１１５から取り出し（ｓ２１７ｂ）、排他的論理和算出部１１９に出力する。なお、ｋ＝１の場合には、ｓ２１７ｂで求めるｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋは１に決まっているため、その処理を省略することができる。
【００５０】
次に、積取得部２１７は、ｉをインクリメントし（ｓ２１７ｃ）、インクリメント後のｉがｍより大きい場合（ｓ２１７ｄにおいてｎｏの場合）、ループから脱出する。
【００５１】
インクリメント後のｉがｍ以下の場合（ｓ２１７ｄにおいてｙｅｓの場合）、積取得部２１７は、処理ｎｔｚ（ｉ）により、ｉのビット表現の最下位から並んでいる０の個数ｐ（＝ｎｔｚ（ｉ））を計算し、この０の個数ｐに応じた積Ｌ［ｐ］（＝Ｌ［ｎｔｚ（ｉ）］）を記憶部１１５から取り出し（ｓ２１７ｅ）、排他的論理和算出部１１９に出力する。さらに、ｉをインクリメントし（ｓ２１７ｆ）、継続条件式（ｉ≦ｍ）が真の場合には、上記処理ｓ２１７ｂ〜ｓ２１７ｆを繰り返す。
【００５２】
このような構成により、ｓ１１７ａ及びｓ１１７ｃの一部を省略することができる。
【００５３】
また、積取得部２１７は、複数の積をオーバーラップさせて取得し、ｉ≦２ｋにおける処理に基づきｉ＞２ｋにおける分岐予測を行うため、ｉ＞２ｋにおいて以下のような処理が可能となる。
【００５４】
ｉ≦２ｋにおける処理に基づき、ｉ＞２ｋにおいて、ループの継続条件式やｓ２１７ｄにおける判定式において、判定結果を推測し、次の命令をフェッチし投機的に実行する。より詳しくいうと、ｋ＝１の場合、ｉ＝１、ｉ＝２のときの判定結果（例えば条件式、判定式（ｉ≦ｍ）を満たす）に基づき、ｉ≧３における判定結果（例えば条件式、判定式（ｉ≦ｍ）を満たす）を推定し、判定結果が出る前に、次の処理（ｓ２１７ｂ、ｓ１１９及びｓ２１７ｃやｓ２１７ｅ、ｓ１１９及びｓ２１７ｆ）を始める。最後の一回（つまり、ｉ＞ｍとなったとき）以外は条件が成立するので、最後の一回以外は、分岐予測ミスとはならない。そのため、処理全体に対するペナルティの割合は非常に小さなものであり、マスク生成処理全体の効率化を実現することができる。
【００５５】
ｋ＝２の場合（図１０参照）、ｋ＝３の場合（図１１参照）、ｋ≧４の場合も同様である。
【００５６】
＜効果＞
このような構成とすることで、第一実施形態と同様の効果が得られるとともに、より効率的にマスクＧ（ｉ）Ｌを生成することができる。
【００５７】
＜変形例＞
第二実施形態と異なる部分についてのみ説明する。
【００５８】
＜変形例のポイント＞
１個のマスクを生成する毎ではなく、２ｋ個のマスクを生成する毎に、生成したマスクの個数がｍ’以下か否かを判定し、ｍ’以下のときに２ｋ個のマスクを生成する処理を繰り返す。ただし、ｍ’＝２ｋ・ｆｌｏｏｒ（ｍ／２ｋ）であり、ｍ’はｍ以下の２ｋの最大の倍数を表す。このような構成により、ｉ≦ｍ’において、判定回数を減らすことができ、処理を軽減できる。
【００５９】
＜変形例に係るマスク生成装置６００＞
マスク生成装置６００は、積取得部２１７に代えて、積取得部６１７を備える（図５参照）。
【００６０】
積取得部６１７及び排他的論理和算出部１１９は、２ｋ個のマスクを生成する処理を繰り返す（言い換えると、一回の繰り返し処理（ループ処理）の中で２ｋ個のマスクを生成する）。繰り返し処理毎（２ｋ個のマスクを生成する毎）に生成したマスクの個数がｍ’以下か否かを判定し、ｍ’より大きくなるまで処理を繰り返す。
【００６１】
なお、繰り返し処理では、まず、ｉが２ｋの倍数ではないときに行う処理として以下の処理を行う。積取得部６１７は、ｉを２ｋで割ったときの剰余ｑに基づき、その剰余ｑのビット表現の最下位から並んでいる０の個数Ｎ［ｑ］をＮ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］の順で記憶部１１５から取り出し、さらに、この個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］に応じた積Ｌ［ｐ］を記憶部１１５からＬ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］の順で取り出す。
【００６２】
次に、ｉが２ｋの倍数であるときに行う処理として以下の処理を行う。積取得部６１７は、処理ｎｔｚ（ｉ）により、ｉのビット表現の最下位から並んでいる０の個数ｐ（＝ｎｔｚ（ｉ））を計算し、この０の個数ｐに応じた積Ｌ［ｐ］（＝Ｌ［ｎｔｚ（ｉ）］）を記憶部１１５から取り出す。
【００６３】
なお、ｉ＞２ｋ（より詳しく言うと２ｋ＜ｉ≦ｍ’）における繰り返し処理では、ｉが２ｋの倍数ではない場合に、積取得部６１７において、個数Ｎ［１］、Ｎ［２］、…、Ｎ［２ｋ−１］及び積Ｌ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］を記憶部１１５から取り出す処理を省略し、ｉ≦２ｋにおいて記憶部１１５から取り出した積Ｌ［Ｎ［１］］、Ｌ［Ｎ［２］］、…、Ｌ［Ｎ［２ｋ−１］］を再利用してもよい。
【００６４】
生成したマスクの個数がｍ’より大きい場合、生成したマスクの個数がｍ以下か否かを判定し、ｍより大きくなるまで以下の処理を繰り返す。
【００６５】
積取得部６１７は、ｉを２ｋで割ったときの剰余ｑ（＝ｉ  ｍｏｄ  ２ｋ）に基づき、その剰余ｑ（＝ｉ  ｍｏｄ  ２ｋ）のビット表現の最下位から並んでいる０の個数ｐ（＝Ｎ［ｑ］＝Ｎ［ｉ  ｍｏｄ  ２ｋ］）を記憶部１１５から取り出し、さらに、この０の個数ｐ（＝Ｎ［ｑ］＝Ｎ［ｉ  ｍｏｄ  ２ｋ］）に応じた積Ｌ［ｐ］（＝Ｌ［Ｎ［ｑ］］＝Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］）を記憶部１１５から取り出し、排他的論理和算出部１１９に出力する。
【００６６】
このような構成により、第二実施形態と同様の効果を得ることができる。ｍ’はｍ以下の２ｋの最大の倍数なので、前半の繰り返し処理では、１個のマスクを生成する毎に生成したマスクの個数がｍ以下か否かを判定する処理を省略することができ、繰り返し処理毎（２ｋ個のマスクを生成する毎）に生成したマスクの個数がｍ’以下か否かを判定すればよい。また、ｍが２ｋの倍数の場合、ｍ＝ｍ’となり、後半の繰り返し処理を一回も行わない構成となるので、ｉが２ｋの倍数であるか否かを判定する処理を省略することができる。
【００６７】
図１２〜１４は、それぞれｋ＝１〜３における、積取得部６１７及び排他的論理和算出部１１９の処理フローを示す。なお、図１２〜１４中、ループ端の上端には継続条件式を記載している。具体的に図１２を用いてｋ＝１の場合について説明する。
【００６８】
＜ｋ＝１の場合＞
まず、積取得部６１７は、初期設定を行う（ｓ６１７ａ）。
【００６９】
次に、積取得部６１７は、ｉ≦ｍ’において以下の処理を繰り返す。
【００７０】
積取得部６１７は、ｉを２ｋで割ったときの剰余ｑ＝１のビット表現の最下位から並んでいる０の個数Ｎ［１］＝０を記憶部１１５から取り出し、Ｎ［１］＝０に応じた積Ｌ［０］を記憶部１１５から取り出し（ｓ６１７ｂ）、排他的論理和算出部１１９に出力する。なお、ｋ＝１の場合には、ｓ６１７ｂで求めるｉを２ｋで割ったときの剰余ｉ  ｍｏｄ  ２ｋは１に決まっているため、その処理を省略することができる。
【００７１】
次に、積取得部６１７は、ｉをインクリメントする（ｓ６１７ｃ）。
【００７２】
積取得部６１７は、処理ｎｔｚ（ｉ）により、ｉのビット表現の最下位から並んでいる０の個数ｐ（＝ｎｔｚ（ｉ））を計算し、この０の個数ｐに応じた積Ｌ［ｐ］（＝Ｌ［ｎｔｚ（ｉ）］）を記憶部１１５から取り出し（ｓ６１７ｄ）、排他的論理和算出部１１９に出力する。さらに、ｉをインクリメントし（ｓ６１７ｅ）、継続条件式（ｉ≦ｍ’）が真の場合には、上記処理ｓ６１７ｂ〜ｓ６１７ｅを繰り返す。
【００７３】
継続条件式（ｉ≦ｍ’）を満たさない場合、ｉ≦ｍにおいて以下の処理を繰り返す。
【００７４】
積取得部６１７は、ｉを２ｋで割ったときの剰余ｑ（＝ｉ  ｍｏｄ  ２ｋ）に基づき、その剰余ｑ（＝ｉ  ｍｏｄ  ２ｋ）のビット表現の最下位から並んでいる０の個数ｐ（＝Ｎ［ｑ］＝Ｎ［ｉ  ｍｏｄ  ２ｋ］）を記憶部１１５から取り出し、さらに、この０の個数ｐ（＝Ｎ［ｑ］＝Ｎ［ｉ  ｍｏｄ  ２ｋ］）に応じた積Ｌ［ｐ］（＝Ｌ［Ｎ［ｑ］］＝Ｌ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］）を記憶部１１５から取り出し（ｓ６１７ｆ）、排他的論理和算出部１１９に出力する。さらに、ｉをインクリメントし（ｓ６１７ｇ）、継続条件式（ｉ≦ｍ）が真の場合には、上記処理ｓ６１７ｆ〜ｓ６１７ｇを繰り返す。
【００７５】
このような構成により、判定処理を省略することができる。
【００７６】
また、積取得部６１７は、第二実施形態と同じように、複数の処理をオーバーラップさせて行ってもよい。この場合、ループの継続条件式において、判定結果を推測し、次の命令をフェッチし投機的に実行し、マスク生成処理全体の効率化を実現することができる。
【００７７】
例えば、前半の繰り返し処理では、ｉ≦２ｋにおける処理に基づき、２ｋ＜ｉ（より詳しく言うと、２ｋ＜ｉ≦ｍ’）において、ループの継続条件式の判定結果を推測し、次の命令をフェッチし投機的に実行する。より詳しくいうと、ｋ＝１の場合、ｉ＝１のときの判定結果（例えば条件式（ｉ≦ｍ’）を満たす）に基づき、ｉ≧３における判定結果（例えば条件式（ｉ≦ｍ）を満たす）を推定し、判定結果が出る前に、次の処理（ｓ６１７ｂ、ｓ１１９及びｓ６１７ｃやｓ６１７ｄ、ｓ１１９及びｓ６１７ｅ）を始める。
【００７８】
また、後半の繰り返し処理では、ｉ＝ｍ’＋１における処理に基づき、ｍ’＋１＜ｉにおいて、ループの継続条件式の判定結果を推測し、次の命令をフェッチし投機的に実行する。より詳しくいうと、ｉ＝ｍ’＋１のときの判定結果（例えば条件式（ｉ≦ｍ）を満たす）に基づき、ｉ＞ｍ’＋１における判定結果（例えば条件式（ｉ≦ｍ）を満たす）を推定し、判定結果が出る前に、次の処理（ｓ６１７ｆやｓ６１７ｇ）を始める。
【００７９】
各繰り返し処理において、最後の一回（つまり、ｉ＞ｍ’またはｉ＞ｍとなったとき）以外は条件が成立するので、最後の一回以外は、分岐予測ミスとはならない。そのため、処理全体に対するペナルティの割合は非常に小さなものであり、マスク生成処理全体の効率化を実現することができる。
【００８０】
ｋ＝２の場合（図１３参照）、ｋ＝３の場合（図１４参照）、ｋ≧４の場合も同様である。
【００８１】
＜第三実施形態＞
＜第三実施形態のポイント＞
ＡＥＳ暗号もしくはＣａｍｅｌｌｉａ（参考文献１参照）のようなｗｈｉｔｅｎｉｎｇと呼ばれる処理（拡大鍵との排他的論理和）がある暗号で、ＰＭＡＣやＯＣＢのようなグレイ符号を使ったマスクを利用している暗号利用モードがある場合、第一実施形態及び第二実施形態に係る発明と組み合わせることで、実装を高速化できる。
（参考文献１）Kazumaro AOKI, Tetsuya ICHIKAWA, Masayuki KANDA, Mitsuru MATSUI, Shiho MORIAI, Junko NAKAJIMA, Toshio TOKITA, "The 128-Bit Block Cipher Camellia", IEICE TRANSACTIONS on Fundamentals of Electronics, 2002, Communications and Computer Sciences  Vol.E85-A, No.1, pp.11-24
【００８２】
まず、ＡＥＳ暗号では、Ｐを平文、Ｋを鍵、Ｃを暗号文として、暗号化処理を
Ｃ＝ＡＥＳ＿Ｋ（Ｐ）
と表現するが、ｗｈｉｔｅｎｉｎｇが行われる場合、
Ｃ＝ａｅｓ＿Ｋ（Ｐ  ｘｏｒ  ｋ’）＝ＡＥＳ＿Ｋ（Ｐ）
と表現することができる。ここで、ｋ’はＫから計算されるビット列（以下「拡大鍵」ともいう）を表す。
【００８３】
ＯＣＢやＰＭＡＣでは、
AES_K(P xor G(1)L),AES_K(P xor G(2)L),...,AES_K(P xor G(i)L),...
といった値が計算される。ここで、ｉ−１番目のマスクＧ（ｉ−１）Ｌからｉ番目のマスクＧ（ｉ）Ｌを求める計算は、マスクＧ（ｉ−１）Ｌと、ｉとＬによる値Ｌ［ｎｔｚ（ｉ）］＝ｘｎｔｚ（ｉ）Ｌとの排他的論理和を求めるだけなので、
Ｇ（ｉ）Ｌ
をどんどん更新していくのではなく、
ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌ
を更新していけば、
aes_K(P xor (k' xor G(1)L)),aes_K(P xor (k' xor G(2)L)),...
,aes_K(P xor (k' xor G(i)L)),...
の計算でよくなり、１ブロックの暗号処理毎に排他的論理和一回を省略できる。
【００８４】
つまり、Ｇ（ｉ）Ｌを次式により更新すると、ｗｈｉｔｅｎｉｎｇにおいてＧ（ｉ）Ｌとｋ’との排他的論理和を求める必要がある。
【００８５】
Ｇ（ｉ）Ｌ←Ｇ（ｉ−１）Ｌ  ｘｏｒ  Ｌ［ｎｔｚ（ｉ）］
一方、ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌを次式により更新すると、ｗｈｉｔｅｎｉｎｇにおいて、そのままｋ’  ｘｏｒ  Ｇ（ｉ）Ｌを用いることができ、排他的論理和の処理回数を一回省略することができる。
【００８６】
ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌ←ｋ’  ｘｏｒ  Ｇ（ｉ−１）Ｌ  ｘｏｒ  Ｌ［ｎｔｚ（ｉ）］
【００８７】
＜第三実施形態に係る暗号システム５００＞
図１５は、暗号システム５００の機能ブロック図を示す。暗号システム５００は、情報処理装置３００と情報処理装置４００と通信回線５０１とを含む。情報処理装置３００は、平文Ｐを暗号化して、暗号文Ｃを生成し、通信回線５０１を介して情報処理装置４００に送信する。情報処理装置４００は、暗号文Ｃを受信し、復号する。つまり、情報処理装置３００は暗号化装置として機能し、情報処理装置４００は復号装置として機能する。以下、各装置の処理内容を説明する。
【００８８】
＜情報処理装置３００＞
図１６は情報処理装置３００の機能ブロック図を、図１７はその処理フローを示す。なお、図１７中、ループ端の上端には変数＝初期値、終値、増分値を、下端には変数を記載している。
【００８９】
情報処理装置３００は、積算出部１１１、連続０ビット算出部１１３、記憶部１１５、積取得部１１７、排他的論理和算出部３１９、拡大鍵生成部３２１及び暗号化部３２３を含む。
【００９０】
情報処理装置３００は、秘密情報Ｌ、正整数ｋ、利用者が所望するマスクの個数ｍ、鍵Ｋ、ｍ個の平文Ｐ［ｉ］を入力とし、グレイ符号を利用して暗号利用モードで用いるマスクＧ（ｉ）Ｌをｍ個生成し、そのマスクＧ（ｉ）Ｌを利用して、ｍ個の暗号文Ｃ［ｉ］を生成し、出力する。
【００９１】
積算出部１１１、連続０ビット算出部１１３、記憶部１１５、積取得部１１７の処理内容については第一実施形態と同様であり、説明を省略する。
【００９２】
＜拡大鍵生成部３２１＞
拡大鍵生成部３２１は、鍵Ｋを受け取り、拡大鍵ｋ’を生成し（ｓ３２１）、排他的論理和算出部３１９に出力する。
【００９３】
＜排他的論理和算出部３１９＞
排他的論理和算出部３１９は、まず、拡大鍵ｋ’を受け取る。さらに、積Ｌ［ｎｔｚ（ｉ）］またはＬ［Ｎ［ｉ  ｍｏｄ  ２ｋ］］を受け取る。ｋ’  ｘｏｒ  Ｇ（ｉ−１）Ｌ（ｉ−１におけるマスクＧ（ｉ−１）Ｌと拡大鍵ｋ’との排他的論理和）と積Ｌ［ｐ］（ただし、ｐ＝ｎｔｚ（ｉ）またはｐ＝ｉ  ｍｏｄ  ２ｋ）との排他的論理和（ｋ’  ｘｏｒ  Ｇ（ｉ−１）Ｌ  ｘｏｒ  Ｌ［ｐ］）を求め（ｓ３１９）、これをｉにおけるマスクＧ（ｉ）Ｌと拡大鍵ｋ’との排他的論理和ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌとして、暗号化部３２３に出力するとともに、ｉ＋１におけるマスクＧ（ｉ＋１）Ｌと拡大鍵ｋ’との排他的論理和（ｋ’  ｘｏｒ  Ｇ（ｉ＋１）Ｌ）を求めるために記憶しておく。
【００９４】
＜暗号化部３２３＞
暗号化部３２３は、ｍ個の平文Ｐ［ｉ］と鍵Ｋと排他的論理和ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌとを受け取る。暗号化部３２３は、鍵Ｋと排他的論理和（ｋ’  ｘｏｒ  Ｌ［ｐ］）とを用いて、平文Ｐ［ｉ］を以下のように暗号化する。
Ｃ［ｉ］＝ａｅｓ＿Ｋ（Ｐ［ｉ］  ｘｏｒ  ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌ）
ｍ個の暗号文Ｃ［ｉ］を情報処理装置４００に出力する。
【００９５】
＜情報処理装置４００＞
図１８は情報処理装置４００の機能ブロック図を、図１９はその処理フローを示す。なお、図１９中、ループ端の上端には変数＝初期値、終値、増分値を、下端には変数を記載している。
【００９６】
情報処理装置４００は、積算出部１１１、連続０ビット算出部１１３、記憶部１１５、積取得部１１７、排他的論理和算出部３１９、拡大鍵生成部３２１及び復号部４２３を含む。
【００９７】
情報処理装置４００は、秘密情報Ｌ、正整数ｋ、利用者が所望するマスクの個数ｍ、鍵Ｋ、ｍ個の暗号文Ｃ［ｉ］を入力とし、グレイ符号を利用して暗号利用モードで用いるマスクＧ（ｉ）Ｌをｍ個生成し、そのマスクＧ（ｉ）Ｌを利用して、ｍ個の暗号文Ｃ［ｉ］を復号し、ｍ個の平文Ｐ［ｉ］を出力する。
【００９８】
積算出部１１１、連続０ビット算出部１１３、記憶部１１５、積取得部１１７の処理内容については第一実施形態と同様であり、排他的論理和算出部３１９及び拡大鍵生成部３２１の処理内容については情報処理装置３００と同様であり、説明を省略する。
【００９９】
＜復号部４２３＞
復号部４２３は、ｍ個の暗号文Ｃ［ｉ］と鍵Ｋと排他的論理和ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌとを受け取る。復号部４２３は、鍵Ｋと排他的論理和（ｋ’  ｘｏｒ  Ｌ［ｐ］）とを用いて、ｍ個の暗号文Ｃ［ｉ］を以下のように復号する。
Ｐ［ｉ］＝ａｅｓ−１＿Ｋ（Ｃ［ｉ］  ｘｏｒ  ｋ’  ｘｏｒ  Ｇ（ｉ）Ｌ）
ｍ個の平文Ｐ［ｉ］を出力する。
【０１００】
＜効果＞
このような構成により、情報処理装置３００及び４００は、１ブロックの暗号化または復号処理毎に排他的論理和一回を省略できる。
【０１０１】
＜変形例＞
第二実施形態に本実施形態を適用してもよい。
【０１０２】
また、ｍは平文Ｐや暗号文Ｃの大きさ（データ量）に応じて、自動的に生成される値であってもよい。第一実施形態や第二実施形態においても同様に、暗号化または復号対象となる平文や暗号文を与えられ、その大きさに応じて自動的にｍを生成する構成としてもよい。
【０１０３】
情報処理装置３００及び４００を、一つのコンピュータにより機能させてもよい。その場合、積算出部１１１、連続０ビット算出部１１３、記憶部１１５、積取得部１１７、排他的論理和算出部３１９及び拡大鍵生成部３２１を共通して用いることができる。
【０１０４】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１０５】
＜プログラム及び記録媒体＞
上述したマスク生成装置及び情報処理装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置（各種実施形態で図に示した機能構成をもつ装置）として機能させるためのプログラム、またはその処理手順（各実施形態で示したもの）の各過程をコンピュータに実行させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。
【図１】
2014081569.tif 000009
【図２】
2014081569.tif 000010
【図３】
2014081569.tif 000011
【図４】
2014081569.tif 000012
【図５】
2014081569.tif 000013
【図６】
2014081569.tif 000014
【図７】
2014081569.tif 000015
【図８】
2014081569.tif 000016
【図９】
2014081569.tif 000017
【図１０】
2014081569.tif 000018
【図１１】
2014081569.tif 000019
【図１２】
2014081569.tif 000020
【図１３】
2014081569.tif 000021
【図１４】
2014081569.tif 000022
【図１５】
2014081569.tif 000023
【図１６】
2014081569.tif 000024
【図１７】
2014081569.tif 000025
【図１８】
2014081569.tif 000026
【図１９】
2014081569.tif 000027