(57)【要約】      （修正有）【課題】アクセスパターンを秘匿し、オーバーヘッドを削減する。【解決手段】安全性担保のアクセス領域と履歴データ領域と、非アクセス領域を持つ記憶装置であって、１度だけ、非アクセス領域内データをランダムに並び替える手段と、アクセス領域に移動させる手段と、１つのデータにアクセスが生じると、アクセス領域と非アクセス領域間でデータ交換を行い、アクセス領域内の他のデータにもアクセスを行い、アクセス領域と非アクセス領域間でデータ交換を行う制御手段と、アクセスすべきデータへのアクセス処理の終了時に、アクセス領域内の必要なデータを書き出す手段と、アクセス領域から非アクセス領域に移動したデータを履歴領域に保存する手段と、備え、制御手段は、アクセスを行うデータがアクセス領域に存在せず、非アクセス領域に存在し、履歴領域に保存データがある時、アクセスを行うデータと履歴領域の保存データとをアクセス領域に移動する。【選択図】図５
2014171005.tif 000002
【特許請求の範囲】
【請求項１】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置であって、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、
前記アクセス領域から前記非アクセス領域に移動したデータを履歴領域に履歴データとして保存する保存手段と、
備え、
前記制御手段は、
アクセスを行うデータが前記アクセス領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動することを特徴とする記憶装置。
【請求項２】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置であって、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、
前記アクセス領域から前記非アクセス領域に移動したデータを履歴領域に履歴データとして保存する保存手段と、
備え、
前記制御手段は、
アクセスを行うデータが前記履歴領域に保存されている場合に、前記履歴領域に保存されていないデータを選択し、前記アクセスを行うデータと前記選択したデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動することを特徴とする記憶装置。
【請求項３】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置であって、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、
前記アクセス領域から前記非アクセス領域に移動したデータを履歴領域に履歴データとして保存する保存手段と、
備え、
前記制御手段は、
アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域からランダムに選択したデータと前記アクセスするデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動することを特徴とする記憶装置。
【請求項４】
前記データの数的な処理を行う処理手段を備え、前記処理手段が、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数１により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換することを特徴とする請求項１から請求項３のいずれかに記載の記憶装置。
【数１】
2014171005.tif 000008
【請求項５】
前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する情報付加手段を備えたことを特徴とする請求項１から請求項３のいずれかに記載の記憶装置。
【請求項６】
すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する格納制御手段を備えたことを特徴とする請求項１から請求項３のいずれかに記載の記憶装置。
【請求項７】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法であって、
アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数２により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行い、アクセスを行うデータが前記アクセス領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、
該アクセス領域および履歴領域に移動したデータを前記数２により難読化する第５のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、
を備えたことを特徴とするアクセスパターンの秘匿方法。
【数２】
2014171005.tif 000009
【請求項８】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法であって、
アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数３により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記履歴領域に保存されている場合に、前記履歴領域に保存されていないデータを選択し、前記アクセスを行うデータと前記選択したデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、
該アクセス領域および履歴領域に移動したデータを前記数３により難読化する第５のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、
を備えたことを特徴とするアクセスパターンの秘匿方法。
【数３】
2014171005.tif 000010
【請求項９】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法であって、
アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数４により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域と履歴領域からランダムに選択したデータを前記アクセス領域に移動する第４のステップと、
該アクセス領域に移動したデータを前記数４により難読化する第５のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、
を備えたことを特徴とするアクセスパターンの秘匿方法。
【数４】
2014171005.tif 000011
【請求項１０】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法をコンピュータに実行させるためのプログラムであって、
アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数５により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行い、アクセスを行うデータが前記アクセス領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、
該アクセス領域および履歴領域に移動したデータを前記数５により難読化する第５のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、
をコンピュータに実行させるためのプログラム。
【数５】
2014171005.tif 000012
【請求項１１】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法をコンピュータに実行させるためのプログラムであって、
アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数６により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記履歴領域に保存されている場合に、前記履歴領域に保存されていないデータを選択し、前記アクセスを行うデータと前記選択したデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、
該アクセス領域および履歴領域に移動したデータを前記数６により難読化する第５のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、
をコンピュータに実行させるためのプログラム。
【数６】
2014171005.tif 000013
【請求項１２】
データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法をコンピュータに実行させるためのプログラムであって、
アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数７により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域と履歴領域からランダムに選択したデータを前記アクセス領域に移動する第４のステップと、
該アクセス領域に移動したデータを前記数７により難読化する第５のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、
をコンピュータに実行させるためのプログラム。
【数７】
2014171005.tif 000014
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アクセスパターンを秘匿し、オーバーヘッドを削減する記憶装置、アクセスパターンの秘匿方法およびプログラムに関する。
【背景技術】
【０００２】
近年、暗号に対するサイドチャネル攻撃と呼ばれる攻撃が大きな問題となっている。ソフトウェアに対するサイドチャネル攻撃としては、メモリアクセスを解析し秘密情報を復元する攻撃がある。こうした攻撃に対応して、メモリアクセスを攻撃者から保護するためにＯｂｌｉｖｉｏｕｓ  ＲＡＭが注目を集めている（例えば、非特許文献１および非特許文献２参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｏｄｅｄ  Ｇｏｌｄｒｅｉｃｈ  ａｎｄ  Ｒａｆａｉｌ  Ｏｓｔｒｏｖｓｋｙ，“Ｓｏｆｔｗａｒｅ  ｐｒｏｔｅｃｔｉｏｎ  ａｎｄ  ｓｉｍｕｌａｔｉｏｎ  ｏｎ  ｏｂｌｉｖｉｏｕｓ  ＲＡＭＳ，”  Ｊ．ＡＣＭ，４３（３）：４３１−４７３，１９９６．
【非特許文献２】Ｘ．Ｚｈｕａｎｇ  ｅｔ  ａｌ．“Ｈａｒｄｗａｒｅ  Ａｓｓｉｓｔｅｄ  Ｃｏｎｔｒｏｌ  Ｆｌｏｗ  Ｏｂｆｕｓｃａｔｉｏｎ  ｆｏｒ  Ｅｍｂｅｄｄｅｄ  Ｐｒｏｃｅｓｓｏｒｓ”，ＣＡＳＥ２００４，２００４．
【非特許文献３】Ｙ．Ｎａｋａｎｏ  ｅｔ  ａｌ．“Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｐａｔｔｅｒｎ  Ｐｒｏｔｅｃｔｉｏｎ  ｆｏｒ  Ｒｅｓｏｕｒｃｅ−ｃｏｎｓｔｒａｉｎｅｄ  Ｄｅｖｉｃｅｓ”，ＣＡＲＤＩＳ  ２０１２，２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところが、非特許文献１などで検討されているＯｂｌｉｖｉｏｕｓ  ＲＡＭによるメモリの保護は、オーバーヘッドが大きく、実用化が困難であるという問題がある。そこで、非特許文献２では、ハードウェアの支援によるメモリ保護手法が提案されているが、この方法では、データに対するアクセス頻度や順序などの情報を攻撃者が入手できるという問題がある。また、専用のハードウェアが必要であるという制約がある。これらに対して、非特許文献３では、現実的なオーバーヘッドで攻撃者からアクセスパターンを保護する手法が提案されているが、ソフトウェアのみで実現するためには比較的大きなオーバーヘッドが生じる、オーバーヘッドを削減するためには安全なメモリが必要であるといった課題があった。
【０００５】
そこで、本発明は、上述の課題に鑑みてなされたものであり、アクセスパターンを秘匿し、オーバーヘッドを削減する記憶装置、アクセスパターンの秘匿方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【０００７】
（１）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置であって、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、前記アクセス領域から前記非アクセス領域に移動したデータを履歴領域に履歴データとして保存する保存手段と、備え、前記制御手段は、アクセスを行うデータが前記アクセス領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記アクセス領域に移動することを特徴とする記憶装置を提案している。
【０００８】
（２）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置であって、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、前記アクセス領域から前記非アクセス領域に移動したデータを履歴領域に履歴データとして保存する保存手段と、備え、前記制御手段は、アクセスを行うデータが前記履歴領域に保存されている場合に、前記履歴領域に保存されていないデータを選択し、前記アクセスを行うデータと前記選択したデータとを前記アクセス領域に移動することを特徴とする記憶装置を提案している。
【０００９】
（３）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置であって、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、前記アクセス領域から前記非アクセス領域に移動したデータを履歴領域に履歴データとして保存する保存手段と、備え、前記制御手段は、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域からランダムに選択したデータと前記アクセスするデータとを前記アクセス領域に移動することを特徴とする記憶装置を提案している。
【００１０】
（４）本発明は、（１）から（３）の記憶装置について、前記データの数的な処理を行う処理手段を備え、前記処理手段が、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数１により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換することを特徴とする記憶装置を提案している。
【００１１】
（５）本発明は、（１）から（３）の記憶装置について、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する情報付加手段を備えたことを特徴とする記憶装置を提案している。
【００１２】
（６）本発明は、（１）から（３）の記憶装置について、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する格納制御手段を備えたことを特徴とする記憶装置を提案している。
【００１３】
（７）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法であって、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数２により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行い、アクセスを行うデータが前記アクセス領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、該アクセス領域および履歴領域に移動したデータを前記数２により難読化する第５のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、を備えたことを特徴とするアクセスパターンの秘匿方法を提案している。
【００１４】
（８）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法であって、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数３により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記履歴領域に保存されている場合に、前記履歴領域に保存されていないデータを選択し、前記アクセスを行うデータと前記選択したデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、該アクセス領域および履歴領域に移動したデータを前記数３により難読化する第５のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、を備えたことを特徴とするアクセスパターンの秘匿方法を提案している。  
【００１５】
（９）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法であって、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数４により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域と履歴領域からランダムに選択したデータを前記アクセス領域に移動する第４のステップと、該アクセス領域に移動したデータを前記数４により難読化する第５のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、を備えたことを特徴とするアクセスパターンの秘匿方法を提案している。
【００１６】
（１０）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法をコンピュータに実行させるためのプログラムであって、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数５により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行い、アクセスを行うデータが前記アクセス領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、該アクセス領域および履歴領域に移動したデータを前記数５により難読化する第５のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００１７】
（１１）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法をコンピュータに実行させるためのプログラムであって、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数６により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記履歴領域に保存されている場合に、前記履歴領域に保存されていないデータを選択し、前記アクセスを行うデータと前記選択したデータとを前記アクセス領域に移動し、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動する第４のステップと、該アクセス領域および履歴領域に移動したデータを前記数６により難読化する第５のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００１８】
（１２）本発明は、データの数的な処理により安全性が担保されたデータのアクセス領域と履歴データ領域と、非アクセス領域とに分割された記憶装置におけるアクセスパターンの秘匿方法をコンピュータに実行させるためのプログラムであって、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数７により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、前記非アクセス領域の各データが、前記アクセス領域にあるか否かを示す情報を前記非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、前記すべての領域の一つのブロックに複数のデータを格納する処理を行う第１のステップと、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第２のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第３のステップと、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域と履歴領域からランダムに選択したデータを前記アクセス領域に移動する第４のステップと、該アクセス領域に移動したデータを前記数７により難読化する第５のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第６のステップと、をコンピュータに実行させるためのプログラムを提案している。
【発明の効果】
【００１９】
本発明によれば、データの数的処理により安全性を担保するため、従来よりも小さなオーバーヘッドでアクセスパターンを秘匿することができる。また、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができるという効果がある。また、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うことから、データのアクセスパターンを秘匿することができるという効果がある。さらに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うため、さらに、データのアクセスパターンを秘匿することができるという効果がある。
【００２０】
また、数１等に示すように、乱数ｄとかけられる列は常に１になっており、これによって元のデータｖの変更が難読化後の変数全体に及ぶようになっているため、この難読化を適用することによって、乱数を変更すれば、それがすべての変数に影響を及ぼすことになり、アクセス領域全体を書き換えるよりは効率が上がるという効果がある。
【００２１】
また、保存領域の全ブロックに、例えば、１ビットの値を割り当て、ビットの１，０によって各データがアクセス領域に保持されているかどうかを判定することにより、アクセス領域のデータの管理を小さなオーバーヘッドで実現することにより、高速化を図ることができるという効果がある。
【００２２】
さらに、本発明によれば、例えば、ｓｈｏｒｔ  ｉｎｔ型の場合、１つのデータは２バイト（１６ビット）であるので、６４ビット環境では、１つのブロックに４つのｓｈｏｒｔ  ｉｎｔ型を格納することが可能となる。これによって、必要なメモリサイズの削減が可能となる。同時に、４つのｓｈｏｒｔ  ｉｎｔ型変数を１度に取得することが可能となるので、連続してアクセスするデータが同一のブロックに格納されている場合はアクセス速度の向上も実現できる。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１の実施形態に係る記憶装置の構成を示す図である。
【図２】本発明の第１の実施形態に係る処理部の機能を説明する図である。
【図３】本発明の第１の実施形態に係る情報付加部の機能を説明する図である。
【図４】本発明の第１の実施形態に係る格納制御部の機能を説明する図である。
【図５】本発明の第１の実施形態に係る記憶装置の処理を示す図である。
【図６】本発明の第２の実施形態に係る記憶装置の構成を示す図である。
【図７】本発明の第２の実施形態に係る記憶装置の処理を示す図である。
【図８】本発明の第３の実施形態に係る記憶装置の構成を示す図である。
【図９】本発明の第３の実施形態に係る記憶装置の処理を示す図である。
【図１０】本発明の実施例に係るアクセス時の記憶領域内のデータの遷移を示す図である。
【図１１】本発明の実施例に係る記憶装置の処理を示す図である。
【図１２】本発明の実施例に係る記憶装置の処理を示す図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２５】
＜第１の実施形態＞
図１から図５を用いて、本発明の実施形態について説明する。
【００２６】
＜記憶装置の構成＞
本実施形態に係る記憶装置は、図１に示すように、並べ替え部１１０と、移動部１２０と、制御部１３０と、書き出し部１４０と、保存部１５０と、処理部１６０と、情報付加部１７０と、格納制御部１８０と、記憶領域２００とから構成されている。なお、本発明の記憶装置は、例えば、ＲＡＭ等の一般的な記憶装置ばかりでなく、ＳＩＭやＩＣカード等の記憶媒体も含むものである。
【００２７】
記憶領域２００は、メモリをデータのアクセス領域と非アクセス領域と履歴領域とに分割されており、アクセス領域と履歴データ領域とは、後述する処理部１６０により、データの数的な処理により安全性が担保されている。なお、アクセス領域、非アクセス領域、履歴領域は、ＤＲＡＭ、ＳＲＡＭ等の書き換え可能なメモリで構成される。並べ替え部１１０は、初期状態において、１度だけ、非アクセス領域内のデータをランダムに並び替える。移動部１２０は、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる。
【００２８】
制御部１３０は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００２９】
例えば、アクセスを行うデータがアクセス領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合に、アクセスを行うデータと履歴領域に保存された任意のデータとをアクセス領域に移動する。
【００３０】
書き出し部１４０は、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す。保存部１５０は、アクセス領域から非アクセス領域に移動したデータを履歴領域に履歴データとして保存する。
【００３１】
処理部１６０は、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数１により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する。具体的には、図２に示すように、アクセス領域を例にとれば、アクセス領域は、６つのブロックから形成されているため、これを３つのブロックごとに、２つブロック群に分割し、この分割したブロック群に対して、数１による演算を行うことにより、３つの値をそれぞれｙ０１からｙ０５、ｙ１１からｙ１５の値に変換することによって難読化を行うことができる。
【００３２】
【数１】
2014171005.tif 000003
【００３３】
行列Ａは、乱数ｄとかけられる最右列がすべて１になっており、これによって元の変数ｖの変更が難読化後の変数全体に及ぶようになっている。つまり、難読化を適用することによって、乱数を変更すれば、それがすべての変数に影響を及ぼすことになる。したがって、アクセス領域全体を書き換えるよりは効率的であり、従来のように、ソフトウェアのみで実現する手法よりも小さいオーバーヘッドでアクセスパターンを秘匿することが可能となる。また、難読化するブロックサイズを状況に応じて変更することで、必要に応じて安全性と性能を選択できる。
【００３４】
情報付加部１７０は、非アクセス領域の各データが、アクセス領域にあるか否かを示す情報を非アクセス領域の各データに対応付けて、付加する。具体的には、例えば、図３に示すように、非アクセス領域のデータブロックに付加情報用のブロックを加え、このブロックに、アクセス領域にあるデータには、「１」、ないデータには、「０」を割り付けたビット列を付加する。
【００３５】
つまり、アクセス領域に保管されているデータを管理することは重要であり、最新のデータが一つだけ保持されていなければならない。そのため、保存領域（非アクセス領域）からアクセス領域にデータを移動する際に、選択したデータがアクセス領域に保持されていないことを確認する必要がある。シンプルな解決策としてスキャンによるものがあるが、スキャンを使用した場合、多くのオーバーヘッドが生じる。そこで、保存領域の全ブロックに、例えば、１ビットの値を割り当て、ビットの１，０によって各データがアクセス領域に保持されているかどうかを判定する。これによって、アクセス領域のデータの管理を高速に行うことが可能である。
【００３６】
格納制御部１８０は、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納する。具体的には、例えば、図４に示すように、ＣＰＵのワードサイズが３２ビットである場合に、８ビットのデータを４つ格納したり、１６ビットのデータを２つ格納したり、あるいは、１６ビットのデータ１つと８ビットのデータ２つを格納する。
【００３７】
つまり、各ブロックのサイズは一定である。そのため、大きなサイズのデータブロックに対応するために、各ブロックをＣＰＵのワードサイズに合わせて３２あるいは６４ビットで構成する必要がある。しかし、プログラムが扱う変数はこれよりも小さい場合が多く、大きなブロックを使用すると必要となるメモリが増加するという問題がある。そこで、１ブロックのサイズを３２あるいは６４ビットとし、１つのブロックに複数の小さいデータを格納する。
【００３８】
例えば、ｓｈｏｒｔ  ｉｎｔ型の場合、１つのデータは２バイト（１６ビット）であるので、６４ビット環境では、１つのブロックに４つのｓｈｏｒｔ  ｉｎｔ型を格納することが可能となる。これによって、必要なメモリサイズの削減が可能となる。同時に、４つのｓｈｏｒｔ  ｉｎｔ型変数を１度に取得することが可能となるので、連続してアクセスするデータが同一のブロックに格納されている場合はアクセス速度の向上も実現できる。
【００３９】
＜記憶装置の処理＞
図５を用いて、本実施形態に係る記憶装置の処理について説明する。
【００４０】
まず、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数２により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、非アクセス領域の各データが、アクセス領域にあるか否かを示す情報を非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納する処理を行う（ステップＳ１００）。
【００４１】
【数２】
2014171005.tif 000004
【００４２】
次に、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ２００）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ３００）。
【００４３】
さらに、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行い、アクセスを行うデータがアクセス領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合に、アクセスを行うデータと履歴領域に保存された任意のデータとをアクセス領域に移動し、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動し、アクセス領域および履歴領域に移動したデータを数２により難読化する（ステップＳ４００）。
【００４４】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ５００）。
【００４５】
以上、説明したように、本実施形態によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。
【００４６】
また、上記のような難読化を適用することによって、乱数を変更すれば、それがすべての変数に影響を及ぼすことになり、アクセス領域全体を書き換えるよりは効率が上がるという効果がある。また、付加されたデータによって各データがアクセス領域に保持されているかどうかを判定することにより、アクセス領域のデータの管理を小さなオーバーヘッドで実現することにより、高速化を図ることができるという効果がある。
【００４７】
さらに、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納することにより、必要なメモリサイズの削減が可能となる。また、連続してアクセスするデータが同一のブロックに格納されている場合はアクセス速度の向上も実現できる。
【００４８】
＜第２の実施形態＞
図６から図７を用いて、本発明の実施形態について説明する。
【００４９】
＜記憶装置の構成＞
本実施形態に係る記憶装置は、図６に示すように、並べ替え部１１０と、移動部１２０と、制御部１３１と、書き出し部１４０と、保存部１５０と、処理部１６０と、情報付加部１７０と、格納制御部１８０と、記憶領域２００とから構成されている。なお、本発明の記憶装置は、例えば、ＲＡＭ等の一般的な記憶装置ばかりでなく、ＳＩＭやＩＣカード等の記憶媒体も含むものである。なお、第１の実施形態と同一の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は省略する。
【００５０】
制御部１３１は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００５１】
＜記憶装置の処理＞
図７を用いて、本実施形態に係る記憶装置の処理について説明する。
【００５２】
まず、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数３により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、非アクセス領域の各データが、アクセス領域にあるか否かを示す情報を非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納する処理を行う（ステップＳ１１０）。
【００５３】
【数３】
2014171005.tif 000005
【００５４】
次に、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ２１０）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ３１０）。
【００５５】
さらに、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが履歴領域に保存されている場合に、履歴領域に保存されていないデータを選択し、アクセスを行うデータと選択したデータとをアクセス領域に移動し、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動し、アクセス領域および履歴領域に移動したデータを数３により難読化する（ステップＳ４１０）。
【００５６】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ５１０）。
【００５７】
以上、説明したように、本実施形態によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。
【００５８】
また、上記のような難読化を適用することによって、乱数を変更すれば、それがすべての変数に影響を及ぼすことになり、アクセス領域全体を書き換えるよりは効率が上がるという効果がある。また、付加されたデータによって各データがアクセス領域に保持されているかどうかを判定することにより、アクセス領域のデータの管理を小さなオーバーヘッドで実現することにより、高速化を図ることができるという効果がある。
【００５９】
さらに、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納することにより、必要なメモリサイズの削減が可能となる。また、連続してアクセスするデータが同一のブロックに格納されている場合はアクセス速度の向上も実現できる。
【００６０】
＜第３の実施形態＞
図８から図９を用いて、本発明の実施形態について説明する。
【００６１】
＜記憶装置の構成＞
本実施形態に係る記憶装置は、図８に示すように、並べ替え部１１０と、移動部１２０と、制御部１３２と、書き出し部１４０と、保存部１５０と、処理部１６０と、情報付加部１７０と、格納制御部１８０と、記憶領域２００とから構成されている。なお、本発明の記憶装置は、例えば、ＲＡＭ等の一般的な記憶装置ばかりでなく、ＳＩＭやＩＣカード等の記憶媒体も含むものである。なお、第１の実施形態と同一の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は省略する。
【００６２】
制御部１３２は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００６３】
＜記憶装置の処理＞
図９を用いて、本実施形態に係る記憶装置の処理について説明する。
【００６４】
まず、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数４により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、非アクセス領域の各データが、アクセス領域にあるか否かを示す情報を非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納する処理を行う（ステップＳ１２０）。
【００６５】
【数４】
2014171005.tif 000006
【００６６】
次に、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ２２０）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ３２０）。
【００６７】
さらに、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータがアクセス領域に保存されている場合に、非アクセス領域と履歴領域からランダムに選択したデータをアクセス領域に移動し、アクセス領域に移動したデータを数４により難読化する（ステップＳ４２０）。
【００６８】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ５２０）。
【００６９】
以上、説明したように、本実施形態によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。
【００７０】
また、上記のような難読化を適用することによって、乱数を変更すれば、それがすべての変数に影響を及ぼすことになり、アクセス領域全体を書き換えるよりは効率が上がるという効果がある。また、付加されたデータによって各データがアクセス領域に保持されているかどうかを判定することにより、アクセス領域のデータの管理を小さなオーバーヘッドで実現することにより、高速化を図ることができるという効果がある。
【００７１】
さらに、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納することにより、必要なメモリサイズの削減が可能となる。また、連続してアクセスするデータが同一のブロックに格納されている場合はアクセス速度の向上も実現できる。
【００７２】
＜実施例＞
図１０から図１２を用いて、本発明の実施例について説明する。
【００７３】
図１０は、１、２、・・・、９、Ａ、Ｂ、・・・、Ｆをメモリに保存されているデータとしたときに、プログラムが、５→Ｄ→８→５→Ａの順にデータにアクセスする場合のメモリの遷移を示したものである。以下、この処理を例示として、説明する。なお、図１０の例にかかわらず、非アクセス領域をさらに複数に分割してもよい。
【００７４】
まず、アクセス領域および履歴データ領域内のデータをｖ１、ｖ２、・・・、ｖｍ（ｍは、正の整数）、ｄを乱数、ｙ１、ｙ２、ｙ３、・・・、ｙｎ（ｎは、正の整数）をマスキング用変数ベクトル、Ａを階数がｍ＋１で、その最右列がすべて１であるｎ×（ｍ＋１）行列であるとしたときに、数５により、これらを難読化したデータｘ１、ｘ２、ｘ３、・・・、ｘｎに変換する処理、非アクセス領域の各データが、アクセス領域にあるか否かを示す情報を非アクセス領域の各データに対応付けて、付加する処理、すべての領域において、データの最小単位ビット数が、処理単位ビット数よりも大きい場合に、すべての領域の一つのブロックに複数のデータを格納する処理を行う（ステップＳ１１００）。
【００７５】
【数５】
2014171005.tif 000007
【００７６】
次に、初期状態において、１度だけ、非アクセス領域内のデータをランダムに並び替え（ステップＳ１２００）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ１３００）。
【００７７】
そして、まず、５にアクセスする場合には、５はアクセス領域に含まれないため、５ともう一つランダムに選択されたデータ（図１０では、２）をアクセス領域に移動し、例えば、これにより、アクセス領域から移動する４とＢとを履歴領域に保存して、５にアクセスする。このとき、アクセス領域内の他のデータ（図１０では、２、３、８）に対してもアクセスを行う（ステップＳ１４００）。
【００７８】
次に、Ｄにアクセスする場合には、Ｄはアクセス領域に含まれないため、Ｄをアクセス領域に移動し、もう一つのデータは、履歴領域から選択する（例えば、図１０では、Ｂ）。これにより、アクセス領域から移動する５と８とを履歴領域に保存して、Ｄにアクセスする。このとき、アクセス領域内の他のデータ（図１０では、３、Ｂ、２）に対してもアクセスを行う（ステップＳ１５００）。
【００７９】
さらに、８にアクセスする場合には、８は履歴領域に含まれているため、もう一つのデータは履歴領域に含まれないデータをランダムに選択し（図１０では、Ａ）、アクセス領域に移動する。これにより、アクセス領域から移動する３とＢとを履歴領域に保存して、８にアクセスする。このとき、アクセス領域内の他のデータ（図１０では、Ａ、Ｄ、２）に対してもアクセスを行う（ステップＳ１６００）。
【００８０】
さらに、５にアクセスする場合、５は履歴領域に含まれているため、もう一つのデータは履歴領域に含まれないデータをランダムに選択し（図１０では、６）、アクセス領域に移動する。これにより、アクセス領域から移動する２と８とを履歴領域に保存して、５にアクセスする。また、アクセス領域内の他のデータ（図１０では、Ａ、Ｄ、６）に対してもアクセスを行う（ステップＳ１７００）。
【００８１】
最後に、Ａにアクセスする場合、Ａはアクセス領域に含まれているため、アクセス領域に含まれないランダムに選択したデータと履歴領域に保存されているデータとを（図１０では、３、Ｆ）、アクセス領域に移動する。これにより、アクセス領域から移動する６とＤとが非アクセス領域に書き出され、Ａにアクセスする。また、アクセス領域内の他のデータ（図１０では、５、Ｆ、３）に対してもアクセスを行う（ステップＳ１８００）。
【００８２】
そして、すべての処理が完了するとアクセス領域内の必要なデータを書き出して、終了する（ステップＳ１９００）。
【００８３】
なお、記憶装置の処理をコンピュータシステムが読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを記憶装置に読み込ませ、実行することによって本発明の記憶装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００８４】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００８５】
また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００８６】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００８７】
１１０；並べ替え部
１２０；移動部
１３０；制御部
１３１；制御部
１３２；制御部
１４０；書き出し部
１５０；保存部
１６０；処理部
１７０；情報付加部
１８０；格納制御部
２００；記憶領域
【図１】
2014171005.tif 000015
【図２】
2014171005.tif 000016
【図３】
2014171005.tif 000017
【図４】
2014171005.tif 000018
【図５】
2014171005.tif 000019
【図６】
2014171005.tif 000020
【図７】
2014171005.tif 000021
【図８】
2014171005.tif 000022
【図９】
2014171005.tif 000023
【図１０】
2014171005.tif 000024
【図１１】
2014171005.tif 000025
【図１２】
2014171005.tif 000026