(57)【要約】【課題】入力データのデータ幅にかかわらず、符号化された状態で加算処理を実現する。【解決手段】データ分割部２ａおよび２ｂは、それぞれ入力される符号化データＸ’およびＹ’を複数の分割データｘ’ｉおよびｙ’ｉに分割する。テーブル参照部２ｃは、予め定められたテーブルを参照して分割データｘ’ｉおよびｙ’ｉの組合せに対応する分割データｚ’ｉを順次出力する。データ結合部２ｄは、テーブル参照部２ｃから順次出力される複数の分割データｚ’ｉを結合し、符号化データＺ’として出力する。各テーブルには、符号化された入力データ（分割データ）の組合せと符号された出力データ（分割データ）との対応関係が予め規定されている。データ結合部２ｄは、テーブル参照部２ｃから順次出力される複数の分割データｚ’ｉを結合し、符号化データＺ’として出力する。【選択図】図２
2008292810.tif 000002
【特許請求の範囲】
【請求項１】
所定のデータ幅をもつ第１入力データを複数の第１分割データに分割する第１分割手段と、
所定のデータ幅をもつ第２入力データを複数の第２分割データに分割する第２分割手段と、
前記第１および第２分割データの取り得る値の組合せの各々に対応付けて出力値を規定した関数テーブルを格納するテーブル格納手段とを備え、
前記関数テーブルの前記出力値は、対応する前記第１および第２分割データの値から加算処理に従って予め決定されており、
前記関数テーブルを参照することにより、前記第１分割データと当該第１分割データに対応する前記第２分割データとの組合せに対応付けられた出力値を順次取得するテーブル参照手段と、
前記テーブル参照手段によって順次取得される前記出力値を結合して出力データとして出力する結合手段とを備える、加算装置。
【請求項２】
前記第１および第２入力データは、それぞれ予め定められた符号化処理によって符号化されており、
前記加算処理は、
前記第１分割データを全単射変換する第１写像変換処理と、
前記第２分割データを全単射変換する第２写像変換処理とを含み、
前記第１および第２写像変換処理は、それぞれ前記第１および第２入力データの符号化処理を相殺するような全単射変換を行なう、請求項１に記載の加算装置。
【請求項３】
前記加算処理は、内部データを全単射変換によって前記出力値に変換する第３の写像変換処理を含む、請求項２に記載の加算装置。
【請求項４】
前記加算処理は、前記第１および第２写像変換処理の後段で、かつ前記第３の写像変換処理の前段に設けられた算術加算処理を含む、請求項３に記載の加算装置。
【請求項５】
前記テーブル格納手段は、前記複数の第１分割データに対応付けて複数の関数テーブルを格納し、
前記テーブル参照手段は、前記複数の第１分割データから一つを順次選択するとともに、選択した前記第１分割データに対応する前記関数テーブルを順次参照する、請求項１〜４のいずれか１項に記載の加算装置。
【請求項６】
前記加算処理は、２のべき乗を法とする加算剰余演算である、請求項１〜５のいずれか１項に記載の加算装置。
【請求項７】
前記加算装置は、
前記加算処理に従って前記関数テーブルを生成するテーブル生成手段と、
複数の全単射変換の候補を予め格納する全単射候補格納手段とをさらに備え、
前記加算処理は、少なくとも１つの全単射変換を含み、
前記テーブル生成手段は、前記複数の全単射変換の候補から前記少なくとも１つの全単射変換をランダムに選択する選択手段を含む、請求項１〜６のいずれか１項に記載の加算装置。
【請求項８】
演算装置と記憶装置とを含むコンピュータにインストールされて加算処理を行なう加算プログラムであって、
前記加算プログラムは、
所定のデータ幅をもつ第１入力データを複数の第１分割データに分割するステップと、
所定のデータ幅をもつ第２入力データを複数の第２分割データに分割するステップと、を前記演算装置に実行させ、
前記記憶装置は、前記第１および第２分割データの取り得る値の組合せの各々に対応付けて出力値を規定した関数テーブルを格納しており、
前記関数テーブルの前記出力値は、対応する前記第１および第２分割データの値から加算処理に従って予め決定されており、
前記加算プログラムは、さらに
前記記憶装置に格納された前記関数テーブルを参照することにより、前記第１分割データと当該第１分割データに対応する前記第２分割データとの組合せに対応付けられた出力値を順次取得するステップと、
順次取得する前記出力値を結合して出力データとして出力するステップと、を演算装置に実行させる、加算プログラム。
【請求項９】
請求項８に記載の加算プログラムを格納する、コンピュータ読取可能な記録媒体。
【請求項１０】
演算装置と記憶装置とを含むコンピュータを用いて加算処理を行なう加算方法であって、
前記演算装置が、所定のデータ幅をもつ第１入力データを複数の第１分割データに分割するステップと、
前記演算装置が、所定のデータ幅をもつ第２入力データを複数の第２分割データに分割するステップとを備え、
前記記憶装置は、前記第１および第２分割データの取り得る値の組合せの各々に対応付けて出力値を規定した関数テーブルを格納しており、
前記関数テーブルの前記出力値は、対応する前記第１および第２分割データの値から加算処理に従って予め決定されており、さらに
前記演算装置が、前記記憶装置に格納された前記関数テーブルを参照することにより、前記第１分割データと当該第１分割データに対応する前記第２分割データとの組合せに対応付けられた出力値を順次取得するステップと、
前記演算装置が、順次取得する前記出力値を結合して出力データとして出力するステップと備える、加算方法。
【請求項１１】
演算装置と記憶装置とを含むコンピュータにインストールされて、請求項１〜６のいずれか１項に記載の加算装置で参照される前記関数テーブルを生成するテーブル生成プログラムであって、
前記加算処理は、少なくとも１つの全単射変換を含み、
前記記憶装置は、複数の全単射変換の候補を予め格納しており、
前記テーブル生成プログラムは、
前記記憶装置に格納された前記複数の全単射変換の候補から前記少なくとも１つの全単射変換をランダムに選択するステップと、
選択された前記全単射変換を用いて、前記加算処理に従って前記関数テーブルを生成するステップと、を前記演算装置に実行させる、テーブル生成プログラム。
【請求項１２】
請求項１１に記載のテーブル生成プログラムを格納する、コンピュータ読取可能な記録媒体。
【請求項１３】
請求項１〜６のいずれか１項に記載の加算装置で参照される前記関数テーブルを、演算装置と記憶装置とを含むコンピュータを用いて生成するテーブル生成方法であって、
前記加算処理は、少なくとも１つの全単射変換を含み、
前記記憶装置は、複数の全単射変換の候補を予め格納しており、
前記テーブル生成方法は、
前記演算装置が、前記記憶装置に格納された前記複数の全単射変換の候補から前記少なくとも１つの全単射変換をランダムに選択するステップと、
前記演算装置が、選択された前記全単射変換を用いて、前記加算処理に従って前記関数テーブルを生成するステップとを備える、テーブル生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２つの入力データに対する加算処理を行なう加算装置、加算プログラム、その加算プログラムを格納するコンピュータ読取可能な記録媒体および加算方法、ならびに当該加算装置において参照される関数テーブルを生成するテーブル生成プログラム、そのテーブル生成プログラムを格納するコンピュータ読取可能な記録媒体およびテーブル生成方法に関し、特に入出力に係る値を符号化した状態で加算処理を実行する技術に関する。
【背景技術】
【０００２】
デジタルコンテンツ配信では、コンテンツの著作権管理（ＤＲＭ：Digital Rights Management）のために、コンテンツを暗号化して配信することが一般的である。このように暗号化されたコンテンツをソフトウェアにより復号する場合には、ソフトウェア内に復号化鍵が格納され、メモリ上でコンテンツの復号が行われる。復号処理の際、メモリ上には復号化鍵や復号化途中にあるコンテンツなどが配置される。そのため、メモリ上のデータが何らかの手段で読出されると、復号化鍵が不正に取得されてしまうという問題がある。
【０００３】
そこで、このような復号化鍵の不正取得を防止する一つの方法として、メモリ上のデータへのアクセスを制限する方法がある。たとえば、特開２００６−２０９７０３号公報（特許文献１）は、プライベートページを有する内部メモリを備えるプログラム実行保護プロセッサを開示している。このプログラム実行保護プロセッサは、プライベートページへのアクセスを許可するか否かを判断するアクセス判断手段を備え、実行されるプログラムやこのプログラムが扱うデータを外部からの不正なアクセスから保護する。
【０００４】
しかしながら、特開２００６−２０９７０３号公報（特許文献１）に開示されるようなメモリ上のデータへのアクセス制限を実現するためには、当該アクセス制限機能を組み込んだハードウェア（代表的に、プロセッサなど）が必要となるため、汎用的ではなくかつソフトウェアだけでは実現できない。
【０００５】
そこで、別の方法として、メモリ上の復号化鍵や復号化途中のデータを符号化した状態で暗号化処理または復号化処理を行なう方法が提案されている。たとえば、非特許文献１には、ブロック暗号とよばれる共通鍵暗号方式において、入力データと、当該入力データに対して所定の処理を行なうことで得られる出力データとを対応付けた複数の関数テーブルを予め用意し、必要な処理に応じてそれらの関数テーブルを参照することで暗号化処理または復号化処理を行なう方法が開示されている。
【０００６】
なお、共通鍵暗号方式とは、暗号化処理を行なう際に用いる鍵と、復号化処理を行なう際に用いる鍵とが同一である暗号方式である。また、ブロック暗号とは、暗号化するデータを１２８ビットなど一定の長さのブロックに区切り、ブロック単位で暗号化または復号化を行なうものである。ブロック暗号の一般的なものとして、たとえばＡＥＳ（Advanced Encryption Standard）などがある。
【０００７】
以下、非特許文献１に開示された暗号化処理について図２１を用いて説明する。
図２１は、非特許文献１に開示された暗号化処理の概略を説明するための図である。図２１（ａ）は、通常の暗号化処理を示し、図２１（ｂ）は、各処理を符号化した状態での暗号化処理を示す。
【０００８】
図２１（ａ）には、一例として、直列に接続された４つの処理Ｆ１，Ｆ２，Ｆ３，Ｆ４で構成された暗号化処理を示す。各処理Ｆ１〜Ｆ４では、暗号化鍵から「鍵拡張アルゴリズム」に従って生成されるラウンド鍵と入力データとの間の演算処理が行われる。符号化した状態で暗号化処理を行なうために、非特許文献１に開示される方法では、各処理の前後にランダムに選択された全単射変換を挿入した演算処理に相当する関数テーブル９０１〜９０４が予め用意される。たとえば、関数テーブル９０１は、入力データと、当該入力されるデータに対して全単射変換Ｒ０，処理Ｆ１，全単射変換Ｒ１の順に処理が行なわれることで得られる出力データとを予め対応付けた対応表を含む。この関数テーブル９０１では、入力され得るデータの各々について、対応する出力データが予め規定される。したがって、関数テーブル９０１は、何らかの入力データが与えられると、予め規定された対応関係を参照して対応するデータを出力するだけでよく、処理Ｆ１に係る演算処理を実際に行なう必要がない。これにより、入出力が符号化された状態で処理を行なうことができる。すなわち、符号化された入力データは符号化前のデータに復号されることなく所定の処理が行なわれ、かつその処理の結果得られる出力データについても符号化された状態で次の処理に送られる。他の関数テーブル９０２〜９０４についても同様である。
【０００９】
このような関数テーブル９０１〜９０４の各々では、入力データと出力データとの関係は一見するとランダムな全単射変換となるため、関数テーブル９０１〜９０４の入出力データから暗号化鍵（ラウンド鍵）や暗号化途中のデータを導出することは困難である。これにより、暗号化鍵や暗号化途中のデータを秘匿する。共通鍵暗号方式の復号化処理は、暗号化処理と同様であるため、復号化処理においても上述と同様の方法で復号化鍵や復号化途中のデータを秘匿できる。
【００１０】
なお、関数テーブルの入力側にある全単射変換は、直前の関数テーブルの出力側にある全単射変換の逆変換に相当する。すなわち、全単射変換によって符号化されたデータは、次に参照されるテーブルにおいて実質的に復号化されるので、全体としての処理の連続性を保つことができる。なお、処理Ｆ４から出力される暗号文は、ランダムに選択された全単射変換Ｒ４で符号化されているが、暗号化処理（処理Ｆ１〜処理Ｆ４）に続く図示しない処理において、全単射変換Ｒ４の逆変換が行われることにより処理の連続性が保たれる。
【特許文献１】特開２００６−２０９７０３号公報
【非特許文献１】Kaisa Nyberg, Howard M. Heys, "Selected Areas in Cryptography: 9th Annual International Workshop, SAC 2002, St. John's, Newfoundland, Canada, August 15-16, 2002, Revised Papers", Lecture Notes of in Computer Science 2595, Springer, pp.250−270 (2003)
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ところで、ＢｌｏｗｆｉｓｈやＣ２、Ｍ６、ＣＡＳＴ−１２８などの多くの暗号方式では、暗号化処理および復号化処理において、加算処理、特に加算剰余演算処理を含む。この加算剰余演算処理は、２つの入力データＸおよびＹについて、Ｚ＝Ｘ＋ＹｍｏｄＮの演算式に従って出力データＺを算出する処理である。なお、式中の「ｍｏｄ」は除算による剰余（余り）を示し、「ＹｍｏｄＮ」は入力データＹを変数Ｎで除算した場合の剰余を示す。このような暗号方式について、上述したような方法でデータを秘匿するためには、このような加算処理について符号化した状態で行なう必要がある。
【００１２】
しかしながら、上述の非特許文献１では、２つの符号化された入力データに対する加算処理については開示されていない。また、２つの入力データＸおよびＹと出力データＺとを対応付ける関数テーブルを用いることも考えられるが、入力データＸおよびＹのデータ幅がそれぞれｎビットとすると、関数テーブルで規定される対応数は２ｎ個となる。通常、入力データＸおよびＹのデータ幅は３２ビットや６４ビットであるため、このような入力データに対して関数テーブルを作成すると、そのテーブルサイズが非常に大きくなってしまい、データサイズや処理速度などの観点から現実的ではない。
【００１３】
この発明は、このような問題点を解決するためになされたものであって、その目的は、入力データのデータ幅にかかわらず、符号化された状態で加算処理を実行可能な加算装置、加算プログラム、その加算プログラムを格納するコンピュータ読取可能な記録媒体および加算方法、ならびに当該加算装置において参照される関数テーブルを生成するテーブル生成プログラム、そのテーブル生成プログラムを格納するコンピュータ読取可能な記録媒体およびテーブル生成方法を提供することである。
【課題を解決するための手段】
【００１４】
本発明のある局面に従う加算装置は、所定のデータ幅をもつ第１入力データを複数の第１分割データに分割する第１分割手段と、所定のデータ幅をもつ第２入力データを複数の第２分割データに分割する第２分割手段と、第１および第２分割データの取り得る値の組合せの各々に対応付けて出力値を規定した関数テーブルを格納するテーブル格納手段とを備え、関数テーブルの出力値は、対応する第１および第２分割データの値から加算処理に従って予め決定されており、関数テーブルを参照することにより、第１分割データと当該第１分割データに対応する第２分割データとの組合せに対応付けられた出力値を順次取得するテーブル参照手段と、テーブル参照手段によって順次取得される出力値を結合して出力データとして出力する結合手段とを備える。
【００１５】
好ましくは、第１および第２入力データは、それぞれ予め定められた符号化処理によって符号化されており、加算処理は、第１分割データを全単射変換する第１写像変換処理と、第２分割データを全単射変換する第２写像変換処理とを含み、第１および第２写像変換処理は、それぞれ第１および第２入力データの符号化処理を相殺するような全単射変換を行なう。
【００１６】
より好ましくは、加算処理は、内部データを全単射変換によって出力値に変換する第３の写像変換処理を含む。
【００１７】
より好ましくは、加算処理は、第１および第２写像変換処理の後段で、かつ第３の写像変換処理の前段に設けられた算術加算処理を含む。
【００１８】
好ましくは、テーブル格納手段は、複数の第１分割データに対応付けて複数の関数テーブルを格納し、テーブル参照手段は、複数の第１分割データから一つを順次選択するとともに、選択した第１分割データに対応する関数テーブルを順次参照する。
【００１９】
好ましくは、加算処理は、２のべき乗を法とする加算剰余演算である。
好ましくは、加算装置は、加算処理に従って関数テーブルを生成するテーブル生成手段と、複数の全単射変換の候補を予め格納する全単射候補格納手段とをさらに備え、加算処理は、少なくとも１つの全単射変換を含み、テーブル生成手段は、複数の全単射変換の候補から少なくとも１つの全単射変換をランダムに選択する選択手段を含む。
【００２０】
この発明の別の局面に従えば、演算装置と記憶装置とを含むコンピュータにインストールされて加算処理を行なう加算プログラムであって、加算プログラムは、所定のデータ幅をもつ第１入力データを複数の第１分割データに分割するステップと、所定のデータ幅をもつ第２入力データを複数の第２分割データに分割するステップと、を演算装置に実行させ、記憶装置は、第１および第２分割データの取り得る値の組合せの各々に対応付けて出力値を規定した関数テーブルを格納しており、関数テーブルの出力値は、対応する第１および第２分割データの値から加算処理に従って予め決定されており、加算プログラムは、さらに記憶装置に格納された関数テーブルを参照することにより、第１分割データと当該第１分割データに対応する第２分割データとの組合せに対応付けられた出力値を順次取得するステップと、順次取得する出力値を結合して出力データとして出力するステップと、を演算装置に実行させる。
【００２１】
この発明のさらに別の局面に従えば、上記の加算プログラムを格納するコンピュータ読取可能な記録媒体である。
【００２２】
この発明のさらに別の局面に従えば、演算装置と記憶装置とを含むコンピュータを用いて加算処理を行なう加算方法であって、演算装置が、所定のデータ幅をもつ第１入力データを複数の第１分割データに分割するステップと、演算装置が、所定のデータ幅をもつ第２入力データを複数の第２分割データに分割するステップとを備え、記憶装置は、第１および第２分割データの取り得る値の組合せの各々に対応付けて出力値を規定した関数テーブルを格納しており、関数テーブルの出力値は、対応する第１および第２分割データの値から加算処理に従って予め決定されており、さらに演算装置が、記憶装置に格納された関数テーブルを参照することにより、第１分割データと当該第１分割データに対応する第２分割データとの組合せに対応付けられた出力値を順次取得するステップと、演算装置が、順次取得する出力値を結合して出力データとして出力するステップと備える。
【００２３】
この発明のさらに別の局面に従えば、演算装置と記憶装置とを含むコンピュータにインストールされて、上記の加算装置で参照される関数テーブルを生成するテーブル生成プログラムであって、加算処理は、少なくとも１つの全単射変換を含み、記憶装置は、複数の全単射変換の候補を予め格納しており、テーブル生成プログラムは、記憶装置に格納された複数の全単射変換の候補から少なくとも１つの全単射変換をランダムに選択するステップと、選択された全単射変換を用いて、加算処理に従って関数テーブルを生成するステップと、を演算装置に実行させる。
【００２４】
この発明のさらに別の局面に従えば、上記のテーブル生成プログラムを格納するコンピュータ読取可能な記録媒体である。
【００２５】
この発明のさらに別の局面に従えば、上記の加算装置で参照される関数テーブルを、演算装置と記憶装置とを含むコンピュータを用いて生成するテーブル生成方法であって、加算処理は、少なくとも１つの全単射変換を含み、記憶装置は、複数の全単射変換の候補を予め格納しており、テーブル生成方法は、演算装置が、記憶装置に格納された複数の全単射変換の候補から少なくとも１つの全単射変換をランダムに選択するステップと、演算装置が、選択された全単射変換を用いて、加算処理に従って関数テーブルを生成するステップとを備える。
【発明の効果】
【００２６】
本発明によれば、入力データのデータ幅にかかわらず、符号化された状態で加算処理を実行できる。
【発明を実施するための最良の形態】
【００２７】
この発明の実施の形態について、図面を参照しながら詳細に説明する。なお、図中の同一または相当部分については、同一符号を付してその説明は繰返さない。
【００２８】
［１．システム構成］
図１は、この発明の実施の形態に従う加算装置を実現するための代表例であるコンピュータ１００のハードウェア構成を示すブロック図である。
【００２９】
図１を参照して、コンピュータ１００は、表示装置であるモニタ１０４と、入力装置であるキーボード１１０およびマウス１１２と、ＣＰＵ（Central Processing Unit）１２０と、ＲＯＭ（Read Only Memory）およびＲＡＭ（Random Access Memory）を含むメモリ１２２と、固定ディスク１２４とを備える。本実施の形態に従う加算装置は、固定ディスク１２４などに予め格納されたプログラムがメモリ１２２中のＲＡＭに展開された上で、ＣＰＵ１２０が当該プログラムを実行することで実現される。なお、固定ディスク１２４には、後述するような、本実施の形態に従う加算処理において利用される関数テーブル（以下、単に「テーブル」とも称す）や変数なども格納される。
【００３０】
コンピュータ１００は、ＣＤ−ＲＯＭ（Compact Disk Read-Only Memory）１１８などの光ディスクからデータを読取可能な光ディスクドライブ１０８と、フレキシブルディスク（ＦＤ：Flexible Disk）１１６からデータを読取可能なＦＤドライブ１０６と、外部装置とデータ授受可能な通信インターフェース１２８とをさらに備える。固定ディスク１２４に格納されるプログラムは、ＣＤ−ＲＯＭ１１８やフレキシブルディスク１１６などの記録媒体に格納されて流通し、光ディスクドライブ１０８やＦＤドライブ１０６などによって読取られて固定ディスク１２４にインストールされる。このような形態に代えて、コンピュータ１００が通信インターフェース１２８を介してネットワーク接続されている場合には、ネットワーク上のサーバから送信されるプログラムを受信して、固定ディスク１２４にインストールするようにしてもよい。なお、ネットワーク経由でプログラムを受信する場合には、固定ディスク１２４にインストールすることなくＲＡＭ上にロードした上で当該プログラムを実行してもよい。
【００３１】
なお、プログラムを格納する記録媒体は、ＣＤ−ＲＯＭ１１８やフレキシブルディスク１１６に限られず、たとえば、ＤＶＤ−ＲＯＭ（Digital Versatile Disk）やメモリーカードであってもよく、その場合には、コンピュータ１００にそのような記録媒体を読取可能なドライブ装置が設けられる。
【００３２】
さらに、本発明に係るプログラムは、コンピュータのオペレーティングシステム（ＯＳ）の一部として提供されるプログラムモジュールのうち、必要なモジュールを所定の配列で所定のタイミングで呼出して処理を実行させるものであってもよい。その場合、プログラム自体には上記モジュールが含まれずＯＳと協働して処理が実行される。このようなモジュールを含まないプログラムも、本発明にかかるプログラムに含まれ得る。
【００３３】
また、本発明にかかるプログラムは他のプログラムの一部に組込まれて提供されるものであってもよい。その場合にも、プログラム自体には上記他のプログラムに含まれるモジュールが含まれず、他のプログラムと協働して処理が実行される。このような他のプログラムに組込まれたプログラムも、本発明にかかるプログラムに含まれ得る。
【００３４】
また、本実施の形態に従う加算装置の一部または全部をハードウェアによって実現してもよい。
【００３５】
［２．機能構成］
図２は、この発明の実施の形態に従う加算装置を実現する主要な機能構成を示すブロック図である。これらの機能は、主として、コンピュータ１００のＣＰＵ１２０および固定ディスク１２４によって実現される。
【００３６】
図２を参照して、ＣＰＵ１２０は、加算部２と、第１符号化部３と、第２符号化部４と、テーブル生成部５とを機能として含む。また、固定ディスク１２４は、全単射候補格納部２０と、テーブル格納部２２とを含む。
【００３７】
第１符号化部３は、入力データＸを符号化して符号化データＸ’を生成し、第２符号化部４は、入力データＹを符号化して符号化データＹ’を生成する。ここで、第１符号化部３は、テーブル生成部５から与えられるデータβおよび全単射変換Ｘｆ−１に基づいて符号化を行なう。同様に、第２符号化部４は、テーブル生成部５から与えられるデータγおよび全単射変換Ｙｆ−１に基づいて符号化を行なう。この符号化処理については後述する。
【００３８】
加算部２は、第１符号化部３および第２符号化部４からそれぞれ出力される符号化データＸ’およびＹ’を受付けて加算処理を行なう。本実施の形態においては、加算処理の代表例として、加算部２が入力データＸの法Ｎのもとでの入力データＹとの加算剰余演算処理（Ｘ＋ＹｍｏｄＮ）を実行する場合について例示する。加算部２は、この加算剰余演算処理によって得られる出力データＺを符号化したものに相当する符号化データＺ’を出力する。ここで、加算部２は、入力される符号化データＸ’およびＹ’についての加算剰余演算処理（Ｘ＋ＹｍｏｄＮ）を実際に行なうのではなく、テーブル生成部５によって予め生成された少なくとも１つのテーブルを参照して、符号化データＸ’およびＹ’に対応する符号化データＺ’を出力する。
【００３９】
テーブル生成部５は、加算剰余演算処理を行なうために加算部２が参照するテーブルを生成して、固定ディスク１２４のテーブル格納部２２に格納する。このテーブル生成に際して、テーブル生成部５は、符号化部３および４に与えるデータβおよびγについても決定する。さらに、テーブル生成部５は乱数発生部５ａを含み、乱数発生部５ａは、テーブルを生成する際に使用する全単射変換をランダムに選択するために使用される。
【００４０】
全単射候補格納部２０は、後述するテーブル生成部５によるテーブル生成処理において、ランダムに選択される全単射変換と対応する逆変換とのセットを複数格納している。
【００４１】
テーブル格納部２２は、テーブル生成部５が生成したテーブルを格納し、加算部２が当該格納したテーブルを参照することで加算処理を実現する。
【００４２】
なお、図２には代表的に、加算剰余演算処理（Ｘ＋ＹｍｏｄＮ）を１回だけ実行するブロック図を示すが、本発明の加算装置はこの構成に限定されるものではない。すなわち、実際の暗号化処理および復号化処理では、加算剰余演算処理を多数回実行する必要があり、このような場合には加算部を複数設けてもよく、このような場合には符号化部３，４が最初の加算部の入力側にのみ設けられてもよい。さらに、加算剰余演算処理に算術加算処理などの他の加算処理を直列的に付加してもよい。
【００４３】
以下、各部の処理について説明する。なお、以下の説明では、代表的に、入力データＸ，Ｙおよび出力データＺがいずれも３２ビットのデータ幅をもち、かつそれぞれを符号化した符号化データＸ’，Ｙ’，Ｚ’についても３２ビットのデータ幅をもつ場合について説明する。
【００４４】
［３．加算処理およびテーブル生成処理］
特に本実施の形態に従う加算部２は、符号化データＸ’およびＹ’を所定のビット単位で複数のデータに分割した上で加算剰余演算処理を実行する。このような複数のデータに分割することで、入力データのデータ幅が小さくなるのでテーブルサイズの肥大化を抑制できる。
【００４５】
より具体的には、加算部２は、データ分割部２ａ，２ｂと、テーブル参照部２ｃと、データ結合部２ｄとを含む。データ分割部２ａおよび２ｂは、それぞれ入力される符号化データＸ’およびＹ’を複数の分割データｘ’ｉおよびｙ’ｉに分割する。ここで、分割データｘ’ｉおよびｙ’ｉは、所定のビット幅をもつデータである。
【００４６】
テーブル参照部２ｃは、予め定められたテーブルを参照して分割データｘ’ｉおよびｙ’ｉの組合せに対応する分割データｚ’ｉを順次出力する。データ結合部２ｄは、テーブル参照部２ｃから順次出力される複数の分割データｚ’ｉを結合し、符号化データＺ’として出力する。
【００４７】
ここで各テーブルは、符号化された入力データ（分割データ）の組合せと符号された出力データ（分割データ）との対応関係を規定したものであり、このようなテーブルを用いることで入力データと出力データとを秘匿した状態で加算剰余演算処理を実行できる。
【００４８】
本発明に係る加算装置は、符号化データＸ’およびＹ’を任意にビット毎に分割した上で加算剰余演算処理することが可能であるが、本実施の形態では、代表的に２ビット毎に分割する場合と４ビット毎に分割する場合とを例示する。また、加算部２で実行される加算剰余演算の内容は、代表的に入力データＸを法２３２のもとでの入力データＹとの加算剰余演算（Ｘ＋Ｙｍｏｄ２３２）とする。
【００４９】
（３−１）２ビット毎に分割した場合の処理
＜３−１−１．符号化処理＞
まず、第１符号化部３および第２符号化部４による符号化処理について図３および図４を用いて説明する。加算部２と同様に、第１符号化部３および第２符号化部４についても入力データＸおよびＹを所定ビット毎に分割した上で符号化する。なお、この分割するビット単位は加算部２において入力データを分割するビット単位と一致させることが好ましく、図３および図４には入力データＸおよびＹを２ビット毎に分割する場合について例示する。
【００５０】
図３は、この発明の実施の形態に従う第１符号化部３における機能構成を示すブロック図である。図４は、この発明の実施の形態に従う第２符号化部４における機能構成を示すブロック図である。
【００５１】
図３を参照して、第１符号化部３は、データ幅が３２ビットである入力データＸを符号化して、符号化データＸ’＝（ｘ’１６‖ｘ’１５‖・・・‖ｘ’１）を出力する。ここで、「‖」はデータの連結を表し、分割データｘ’ｉ（ｉ＝１〜１６）はいずれも２ビットのデータである。
【００５２】
本実施の形態における符号化とは、一例として、入力データＸを法２３２のもとでのデータβとの加算剰余演算処理（Ｘ＋βｍｏｄ２３２）を行った後に、全単射変換Ｘｆ−１ｉ（１≦ｉ≦１６）によって変換する処理である。なお、第１符号化部３における加算剰余演算での「法」の値は、加算部２における加算剰余演算での「法」の値と一致させる必要がある。
【００５３】
より具体的には、第１符号化部３は、加算剰余演算部３２０と、データ分割部３２２と、写像変換部３０１〜３１６と、データ結合部３２４とを含む。
【００５４】
加算剰余演算部３２０は、入力データＸとデータβとを受けて、入力データＸを法２３２のもとでのデータβとの加算剰余演算処理（Ｘ＋βｍｏｄ２３２）を行なう。データ分割部３２２は、加算剰余演算部３２０から出力される入力データ（＝ｘ１６‖ｘ１５‖・・・‖ｘ１）を所定ビット毎（代表的に、２ビット毎）に分割して、分割によって得られる分割データｘ１〜ｘ１６をそれぞれ写像変換部３０１〜３１６へ出力する。写像変換部３０１〜３１６は、それぞれ全単射変換Ｘｆ−１１〜Ｘｆ−１１６に従って、それぞれ分割データｘ’１〜ｘ’１６を生成する。データ結合部３２４は、写像変換部３０１〜３１６から出力される分割データｘ’１〜ｘ’１６を結合し、符号化データＸ’として出力する。
【００５５】
図４を参照して、第２符号化部４は、第１符号化部３と同様に、データ幅が３２ビットである入力データＹを符号化して、符号化データＹ’＝（ｙ’１６‖ｙ’１５‖・・・‖ｙ’１）を出力する。ここで、分割データｙ’ｉ（ｉ＝１〜１６）はいずれも２ビットのデータである。
【００５６】
本実施の形態における符号化とは、一例として、入力データＹを法２３２のもとでのデータγとの加算剰余演算処理（Ｙ＋γｍｏｄ２３２）を行った後に、全単射変換Ｙｆ−１ｉ（１≦ｉ≦１６）によって変換する処理を意味する。
【００５７】
より具体的には、第２符号化部４は、加算剰余演算部４２０と、データ分割部４２２と、写像変換部４０１〜４１６と、データ結合部４２４とを含む。
【００５８】
加算剰余演算部４２０は、入力データＹとデータγとを受けて、入力データＹを法２３２のもとでのデータγとの加算剰余演算処理（Ｙ＋γｍｏｄ２３２）を行なう。データ分割部４２２は、加算剰余演算部４２０から出力される入力データ（＝ｙ１６‖ｙ１５‖・・・‖ｙ１）を所定ビット毎（代表的に、２ビット毎）に分割して、分割によって得られる分割データｙ１〜ｙ１６をそれぞれ写像変換部４０１〜４１６へ出力する。写像変換部４０１〜４１６は、それぞれ全単射変換Ｙｆ−１１〜Ｙｆ−１１６に従って、それぞれ分割データｙ’１〜ｙ’１６を生成する。データ結合部４２４は、写像変換部４０１〜４１６から出力される分割データｙ’１〜ｙ’１６を結合し、符号化データＹ’として出力する。
【００５９】
後述するように、図３の加算剰余演算部３２０および図４の加算剰余演算部４２０で使用するデータβおよびγは、加算部２が参照するテーブルに応じて予め設定される。また、全単射変換Ｘｆ−１１〜Ｘｆ−１１６およびＹｆ−１１〜Ｙｆ−１１６についても加算部２が参照するテーブルに応じて予め設定される。
【００６０】
本明細書における全単射変換とは、入力されるデータと出力されるデータとが一対一に対応付けられた対応関係を意味する。そして、全単射変換の逆変換とは、入力に対する出力の関係を入れ替えたもの、すなわち出力データに対する入力データの関係を意味する。
【００６１】
＜３−１−２．加算処理＞
次に、加算部２が入力データを２ビット単位に分割して処理を行なう場合について図５および図６を用いて説明する。
【００６２】
図５は、この発明の実施の形態に従う加算部２における機能構成を示すブロック図である。
【００６３】
図６は、この発明の実施の形態に従う加算部２が参照するテーブルＴ１〜Ｔ１６のデータ構造の一例を示す図である。
【００６４】
図５を参照して、加算部２は、予め定められたテーブルＴ１〜Ｔ１６を参照して、入力される２つの符号化データＸ’＝（ｘ’１６‖ｘ’１５‖・・・‖ｘ’１）およびＹ’＝ （ｙ’１６‖ｙ’１５‖・・・‖ｙ’１）を加算処理した結果得られる符号化データＺ’＝（ｚ’１６‖ｚ’１５‖・・・‖ｚ’１）を出力する。
【００６５】
より詳細には、加算部２は、テーブルＴ１を参照して、符号化データＸ’を構成する分割データｘ’１と符号化データＹ’を構成する分割データｙ’１との組合せに対応付けられた、内部データｃ’１と分割データｚ’１とを決定する。ここで、テーブルＴ１は、図６（ａ）に示すように４ビット入力／３ビット出力の対応関係を有しており、分割データｘ’１（２ビット）と分割データｙ’１（２ビット）とが入力されると、対応する内部データｃ’１（１ビット）と分割データｚ’１（２ビット）とが一意に決定される。
【００６６】
次に、加算部２は、テーブルＴ１を参照して決定した内部データｃ’１と符号化データＸ’を構成する分割データｘ’２と符号化データＹ’を構成する分割データｙ’２との組合せに対応付けられた、内部データｃ’２と分割データｚ’２とを決定する。ここで、テーブルＴ２は、図６（ｂ）に示すように５ビット入力／３ビット出力の対応関係を有しており、分割データｘ’２（２ビット）と分割データｙ’２（２ビット）と内部データｃ’１（１ビット）とが入力されると、対応する内部データｃ’２（１ビット）と分割データｚ’２（２ビット）とが一意に決定される。
【００６７】
以下同様にして、加算部２は、テーブルＴｉ−１を参照して決定した内部データｃ’ｉ−１と符号化データＸ’を構成する分割データｘ’ｉと符号化データＹ’を構成する分割データｙ’ｉとの組合せに対応付けられた、内部データｃ’ｉと分割データｚ’ｉとを順次決定する。この処理は、変数ｉが１５に到達するまで繰返される。
【００６８】
さらに、加算部２は、テーブルＴ１５を参照して決定した内部データｃ’１５と符号化データＸ’を構成する分割データｘ’１６と符号化データＹ’を構成する分割データｙ’１６との組合せに対応付けられた、分割データｚ’１６を決定する。ここで、テーブルＴ１６は、図６（ｃ）に示すように５ビット入力／２ビット出力の対応関係を有しており、分割データｘ’１６（２ビット）と分割データｙ’１６（２ビット）と内部データｃ’１５（１ビット）とが入力されると、対応する分割データｚ’１６（２ビット）が一意に決定される。
【００６９】
最終的に、加算部２は、決定した分割データｚ’１〜ｚ’１６を結合して符号化データＺ’として出力する。
【００７０】
＜３−１−３．テーブル生成処理＞
以下、各テーブル生成処理について説明する。
【００７１】
テーブルＴ１の内部処理としては、写像変換部２０１１，２０１２，２０１６，２０１７と、算術加算部２０１３，２０１４と、データ分割部２０１５とを含む。
【００７２】
写像変換部２０１１は、全単射変換Ｘｆ１に従って、２ビットの分割データｘ’１を２ビットのデータに単射変換する。同様に、写像変換部２０１２は、全単射変換Ｙｆ１に従って、２ビットの分割データｙ’１を２ビットのデータに単射変換する。ここで、全単射変換Ｘｆ１およびＹｆ１は、それぞれ全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。
【００７３】
図３に示すように、第１符号化部３は、全単射変換Ｘｆ１の逆変換である全単射変換Ｘｆ−１１に従って分割データｘ１を単射変換して分割データｘ’１に符号化する。これに対して、写像変換部２０１１は、全単射変換Ｘｆ１に従って分割データｘ’１を単射変換する。したがって、第１符号化部３における全単射変換Ｘｆ−１１による単射変換と、写像変換部２０１１における全単射変換Ｘｆ１による単射変換とは互いに相殺される。よって、写像変換部２０１１からは分割データｘ１が出力される。
【００７４】
また、第２符号化部４は、全単射変換Ｙｆ１の逆変換である全単射変換Ｙｆ−１１に従って分割データｙ１を単射変換して分割データｙ’１に符号化する。これに対して、写像変換部２０１２は、全単射変換Ｙｆ１に従って分割データｙ’１を単射変換する。したがって、第２符号化部４における全単射変換Ｙｆ−１１による単射変換と、写像変換部２０１２における全単射変換Ｙｆ１による単射変換とは互いに相殺される。よって、写像変換部２０１２からは分割データｙ１が出力される。
【００７５】
そして、算術加算部２０１３は、写像変換部２０１１から出力された分割データｘ１と、写像変換部２０１２から出力された分割データｙ１とを算術加算して、３ビットのデータを生成する。さらに、算術加算部２０１４は、算術加算部２０１３で加算処理が行なわれた後の３ビットのデータとデータα１とを算術加算する。さらに、データ分割部２０１５は、算術加算部２０１４から出力されるデータを上位２ビットと下位２ビットとに分割し、上位２ビットを内部データｃ１として出力するとともに、下位２ビットを分割データｚ１として出力する。すなわち、データ分割部２０１５は、算術加算部２０１４における加算結果を（ｃ１‖ｚ１）として扱う。
【００７６】
ここでデータα１は、４ビットのデータであり、２進数４ビットのデータ群｛００００，０１００，１０００，０００１，０１０１，１００１｝の中からランダムに選択される。データα１をこのようなデータ群から選択することにより、入力される分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１を２種類に限定できる。
【００７７】
具体的には、データα１として「００００」または「０００１」が選択されると、分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１は、「００」または「０１」のみとなり、その他の値は出現しない。また、データα１として「０１００」または「０１０１」が選択されると、分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１は、「０１」または「１０」のみとなり、その他の値は出現しない。また、データα１として「１０００」または「１００１」が選択されると、分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１は、「１０」または「１１」のみとなり、その他の値は出現しない。
【００７８】
このように、分割データｘ’１，ｙ’１に加えて、ランダムに選択されるデータα１を含む算術加算処理を行なうことにより内部データｃ１の候補数が増えるため、テーブルＴ１の入出力データである分割データｘ’１，ｚ’１を観測されたとしても、内部データｃ１を特定されにくくなる。
【００７９】
さらに、写像変換部２０１７は、全単射変換Ｚｆ１に従って、分割データｚ１を分割データｚ’１に符号化して出力する。同様に、写像変換部２０１６は、全単射変換Ｃｆ１に従って、内部データｃ１を１ビットの内部データｃ’１に符号化して出力する。上述したように、出現する内部データｃ１の値を２種類に制限するため、内部データｃ’１は１ビットで表現できる。ここで、全単射変換Ｃｆ１についても、全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。
【００８０】
次に、テーブルＴ２の内部処理としては、写像変換部２０２１，２０２２，２０２６，２０２７，２０２８と、算術加算部２０２３，２０２４，２０２９と、データ分割部２０２５とを含む。
【００８１】
写像変換部２０２１は、全単射変換Ｘｆ２に従って、２ビットの分割データｘ’２を単射変換して分割データｘ２を生成する。同様に、写像変換部２０２２は、全単射変換Ｙｆ２に従って、２ビットの分割データｙ’２を単射変換して分割データｙ２を生成する。ここで、全単射変換Ｘｆ２およびＹｆ２は、それぞれ全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。また、写像変換部２０２８は、全単射変換Ｃｆ１−１に従って、１ビットの内部データｃ’１を２ビットのデータに単射変換する。ここで、全単射変換Ｃｆ１−１は、テーブルＴ１の写像変換部２０１６においてランダムに選択された全単射変換Ｃｆ１の逆変換に相当する。そのため、写像変換部２０２８からは内部データｃ’１を復号化した内部データｃ１が出力される。
【００８２】
そして、算術加算部２０２３は、写像変換部２０２１から出力された分割データｘ２と、写像変換部２０２２から出力された分割データｙ２とを算術加算して、３ビットのデータを生成する。さらに、算術加算部２０２９は、算術加算部２０２３で加算処理が行なわれた後の３ビットのデータと写像変換部２０２８から出力された内部データｃ１とを算術加算する。
【００８３】
続いて、算術加算部２０２４は、算術加算部２０２９で加算処理が行なわれた後の３ビットのデータとデータα２とを算術加算する。さらに、データ分割部２０２５は、算術加算部２０２４から出力されるデータを上位２ビットと下位２ビットとに分割し、上位２ビットを内部データｃ２として出力するとともに、下位２ビットを分割データｚ２として出力する。すなわち、データ分割部２０２５は、算術加算部２０２４における加算結果を（ｃ２‖ｚ２）として扱う。
【００８４】
ここでデータα２は、４ビットのデータであり、テーブルＴ１において内部データｃ１として出現するデータのパターンに応じて、次のように選択される。
【００８５】
（ｉ）内部データｃ１として「００」または「０１」が出現する場合
データα２は、２進数４ビットのデータ群｛０１００，１０００｝の中からランダムに選択される。
【００８６】
（ｉｉ）内部データｃ１として「０１」または「１０」が出現する場合
データα２は、２進数４ビットのデータ群｛００１１，０１１１｝の中からランダムに選択される。
【００８７】
（ｉｉｉ）内部データｃ１として「１０」または「１１」が出現する場合
データα２は、２進数４ビットのデータ群｛００１０，０１１０｝の中からランダムに選択される。
【００８８】
さらに、写像変換部２０２６は、全単射変換Ｚｆ２に従って、分割データｚ２を分割データｚ’２に符号化して出力する。同様に、写像変換部２０２７は、全単射変換Ｃｆ２に従って、内部データｃ２を１ビットの内部データｃ’２に符号化して出力する。上述したように、出現する内部データｃ２の値を２種類に制限するため、内部データｃ’２は１ビットで表現できる。ここで、全単射変換Ｃｆ２は、全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。
【００８９】
以下、テーブルＴｉ（３≦ｉ≦１５）の内部処理は、テーブルＴ２の内部処理と同様であるため詳細な説明は繰返さない。なお、各テーブルＴｉで使用されるデータαｉは、次のように選択される。
【００９０】
（ｉ）内部データｃｉ−１として「００」または「０１」が出現する場合
データαｉは、２進数４ビットのデータ群｛０１００，１０００｝の中からランダムに選択される。
【００９１】
（ｉｉ）内部データｃｉ−１として「０１」または「１０」が出現する場合
データαｉは、２進数４ビットのデータ群｛００１１，０１１１｝の中からランダムに選択される。
【００９２】
（ｉｉｉ）内部データｃｉ−１として「１０」または「１１」が出現する場合
データαｉは、２進数４ビットのデータ群｛００１０，０１１０｝の中からランダムに選択される。
【００９３】
最後に、テーブルＴ１６の内部処理としては、写像変換部２１６１，２１６２，２１６７，２１６８と、算術加算部２１６３，２１６４，２１６９と、データ分割部２１６５とを含む。
【００９４】
写像変換部２１６１は、全単射変換Ｘｆ１６に従って、２ビットの分割データｘ’１６を単射変換して分割データｘ１６を生成する。同様に、写像変換部２１６２は、全単射変換Ｙｆ１６に従って、２ビットの分割データｙ’１６を単射変換して分割データｙ１６を生成する。ここで、全単射変換Ｘｆ１６およびＹｆ１６は、それぞれ全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。また、写像変換部２１６８は、全単射変換Ｃｆ１５−１に従って、１ビットの内部データｃ’１５を２ビットの内部データｃ１５に単射変換する。ここで、全単射変換Ｃｆ１５−１は、テーブルＴ１５においてランダムに選択された全単射変換Ｃｆ１５（図示しない）の逆変換に相当する。
【００９５】
そして、算術加算部２１６３は、写像変換部２１６１から出力された分割データｘ１６と、写像変換部２１６２から出力された分割データｙ１６とを算術加算して、３ビットのデータを生成する。さらに、算術加算部２１６９は、算術加算部２１６３で加算処理が行なわれた後の３ビットのデータと写像変換部２１６８から出力された内部データｃ１５とを算術加算する。
【００９６】
続いて、算術加算部２１６４は、算術加算部２１６９で加算処理が行なわれた後の３ビットのデータとデータα１６とを算術加算する。さらに、データ分割部２１６５は、算術加算部２１６４から出力されるデータを上位２ビットと下位２ビットとに分割し、上位２ビットを内部データｃ１６として出力するとともに、下位２ビットを分割データｚ１６として出力する。すなわち、データ分割部２１６５は、算術加算部２１６４における加算結果を（ｃ１６‖ｚ１６）として扱う。
【００９７】
ここでデータα１６は、２ビットのデータであり、２進数２ビットのデータ群｛００，０１，１０，１１｝の中からランダムに選択される。
【００９８】
さらに、写像変換部２１６７は、全単射変換Ｚｆ１６に従って、分割データｚ１６を分割データｚ’１６に符号化して出力する。
【００９９】
以上のようなテーブルＴ１〜Ｔ１６の内部処理に従って、図６（ａ）〜図６（ｃ）に示すようなデータ構造の各値が決定される。すなわち、加算部２における加算剰余演算処理の実行前に、テーブル生成部５（図２）が分割データｘ’ｉ，ｙ’ｉのすべての組合せ（分割データｘ’ｉ，ｙ’ｉがいずれも２ビットである場合には、２２×２２＝１６通り）について、対応する内部データｃｉおよび分割データｚ’ｉを算出し、テーブルＴ１〜Ｔ１６を生成する。テーブル生成部５が生成したテーブルＴ１〜Ｔ１６は、テーブル格納部２２（図２）に格納される。そして、加算部２がテーブル格納部２２に格納されたテーブルＴ１〜Ｔ１６を参照することで、加算剰余演算処理を実行する。
【０１００】
＜１−４．符号化用変数の決定処理＞
再度、図３および図４を参照して、第１符号化部３および第２符号化部４における入力データＸおよび入力データＹの符号化処理には、全単射変換Ｘｆ−１１〜Ｘｆ−１１６およびＹｆ−１１〜Ｙｆ−１１６に加えて、データβおよびγが用いられる。上述したように、全単射変換Ｘｆ−１１〜Ｘｆ−１１６およびＹｆ−１１〜Ｙｆ−１１６による符号化処理は、テーブルＴ１〜Ｔ１６の内部処理に組み込まれる全単射変換Ｘｆ１〜Ｘｆ１６およびＹｆ１〜Ｙｆ１６によって復号化（相殺）される。
【０１０１】
これに対して、データβおよびγによって符号化されたデータは、テーブルＴ１〜Ｔ１６の内部処理においてランダムに選択されるデータαｉに応じてデータβおよびγを適切に選択することで復号化（相殺）される。
【０１０２】
具体的には、データβおよびγは、データαｉと以下のような関係式が成立するように選択される。なお、式中の０ｋはビット０がｋ個並ぶことを意味する。
【０１０３】
α＝−（β＋γ）ｍｏｄ２３２
但し、α＝（α１６‖０３０）＋（α１５‖０２８）＋（０２‖α１４‖０２６）＋（０４‖α１３‖０２４）＋・・・＋（０２６‖α２‖０２）＋（０２８‖α１）ｍｏｄ２３２
この関係式によれば、データα１〜α１６に応じて、データβとデータγとの合計値が制限されるのみでありデータβおよびデータγの各々についての制約はない。そこで、テーブル生成部５（図２）は、データβおよびデータγのいずれか一方の値を０〜（２３２−１）の範囲でランダムに選択した後に、当該選択した値とデータα１〜α１６とに基づいて、他方の変数の値を決定する。
【０１０４】
すなわち、上記の手続きによって決定されたデータα，β，γは、入力データＸおよびＹとの間に以下のような関係が成立する。
【０１０５】
（Ｘ＋β）＋（Ｙ＋γ）＋αｍｏｄＮ＝Ｘ＋ＹｍｏｄＮ
（３−２）４ビット毎に分割した場合の処理
＜３−２−１．符号化処理＞
４ビット毎に分割処理する場合の第１符号化部３＃および第２符号化部４＃による符号化処理について図７および図８を用いて説明する。
【０１０６】
図７は、この発明の実施の形態に従う第１符号化部３＃における機能構成を示すブロック図である。図８は、この発明の実施の形態に従う第２符号化部４＃における機能構成を示すブロック図である。
【０１０７】
図７を参照して、第１符号化部３＃は、データ幅が３２ビットである入力データＸを符号化して、符号化データＸ’＝（ｘ’８‖ｘ’７‖・・・‖ｘ’１）を出力する。ここで、「‖」はデータの連結を表し、分割データｘ’ｉ（ｉ＝１〜８）はいずれも４ビットのデータである。
【０１０８】
より具体的には、第１符号化部３＃は、加算剰余演算部３２０と、データ分割部３４２と、写像変換部３３１〜３３８と、データ結合部３４４とを含む。
【０１０９】
加算剰余演算部３２０は、入力データＸとデータβとを受けて、入力データＸを法２３２のもとでのデータβとの加算剰余演算処理（Ｘ＋βｍｏｄ２３２）を行なう。データ分割部３４２は、加算剰余演算部３２０から出力される入力データ（＝ｘ８‖ｘ７‖・・・‖ｘ１）を４ビット毎に分割して、分割によって得られる分割データｘ１〜ｘ８をそれぞれ写像変換部３３１〜３３８へ出力する。写像変換部３３１〜３３８は、それぞれ全単射変換Ｘｆ−１１〜Ｘｆ−１８に従って、それぞれ分割データｘ’１〜ｘ’８を生成する。データ結合部３４４は、写像変換部３３１〜３３８から出力される分割データｘ’１〜ｘ’８を結合し、符号化データＸ’として出力する。
【０１１０】
図８を参照して、第２符号化部４＃は、第１符号化部３＃と同様に、データ幅が３２ビットである入力データＹを符号化して、符号化データＹ’＝（ｙ’８‖ｙ’７‖・・・‖ｙ’１）を出力する。ここで、分割データｙ’ｉ（ｉ＝１〜８）はいずれも４ビットのデータである。
【０１１１】
より具体的には、第２符号化部４＃は、加算剰余演算部４４０と、データ分割部４４２と、写像変換部４３１〜４３８と、データ結合部４４４とを含む。
【０１１２】
加算剰余演算部４４０は、入力データＹとデータγとを受けて、入力データＹを法２３２のもとでのデータγとの加算剰余演算処理（Ｙ＋γｍｏｄ２３２）を行なう。データ分割部４４２は、加算剰余演算部４２０から出力される入力データ（＝ｙ８‖ｙ７‖・・・‖ｙ１）を４ビット毎に分割して、分割によって得られる分割データｙ１〜ｙ８をそれぞれ写像変換部４３１〜４３８へ出力する。写像変換部４３１〜４３８は、それぞれ全単射変換Ｙｆ−１１〜Ｙｆ−１８に従って、それぞれ分割データｙ’１〜ｙ’８を生成する。データ結合部４４４は、写像変換部４３１〜４３８から出力される分割データｙ’１〜ｙ’８を結合し、符号化データＹ’として出力する。
【０１１３】
後述するように、図７の加算剰余演算部３２０および図８の加算剰余演算部４２０で使用するデータβおよびγは、加算部２が参照するテーブルに応じて予め設定される。また、全単射変換Ｘｆ−１１〜Ｘｆ−１８およびＹｆ−１１〜Ｙｆ−１８についても加算部２が参照するテーブルに応じて予め設定される。
【０１１４】
＜３−２−２．加算処理＞
次に、４ビット毎に分割処理する場合の加算部２＃による加算剰余演算処理について図９を用いて説明する。
【０１１５】
図９は、この発明の実施の形態に従う加算部２＃における機能構成を示すブロック図である。
【０１１６】
図９を参照して、加算部２＃は、予め定められたテーブルＴ１〜Ｔ８を参照して、入力される２つの符号化データＸ’＝（ｘ’８‖ｘ’７‖・・・‖ｘ’１）およびＹ’＝ （ｙ’８‖ｙ’７‖・・・‖ｙ’１）に応じた符号化データＺ’＝（ｚ’８‖ｚ’７‖・・・‖ｚ’１）を出力する。
【０１１７】
より詳細には、加算部２＃は、テーブルＴ１を参照して、符号化データＸ’を構成する分割データｘ’１と符号化データＹ’を構成する分割データｙ’１との組合せに対応付けられた、内部データｃ’１と分割データｚ’１とを決定する。ここで、テーブルＴ１は、８ビット入力／５ビット出力の対応関係を有しており、分割データｘ’１（４ビット）と分割データｙ’１（４ビット）とが入力されると、対応する内部データｃ’１（１ビット）と分割データｚ’１（４ビット）とが一意に決定される。
【０１１８】
次に、加算部２＃は、テーブルＴ１を参照して決定した内部データｃ’１と符号化データＸ’を構成する分割データｘ’２と符号化データＹ’を構成する分割データｙ’２との組合せに対応付けられた、内部データｃ’２と分割データｚ’２とを決定する。ここで、テーブルＴ２は、９ビット入力／５ビット出力の対応関係を有しており、分割データｘ’２（４ビット）と分割データｙ’２（４ビット）と内部データｃ’１（１ビット）とが入力されると、対応する内部データｃ’２（１ビット）と分割データｚ’２（４ビット）とが一意に決定される。
【０１１９】
以下同様にして、加算部２＃は、テーブルＴｉ−１を参照して決定した内部データｃ’ｉ−１と符号化データＸ’を構成する分割データｘ’ｉと符号化データＹ’を構成する分割データｙ’ｉとの組合せに対応付けられた、内部データｃ’ｉと分割データｚ’ｉとを順次決定する。この処理は、変数ｉが７に到達するまで繰返される。
【０１２０】
さらに、加算部２は、テーブルＴ７を参照して決定した内部データｃ’７と符号化データＸ’を構成する分割データｘ’８と符号化データＹ’を構成する分割データｙ’８との組合せに対応付けられた、分割データｚ’８を決定する。ここで、テーブルＴ８は、９ビット入力／４ビット出力の対応関係を有しており、分割データｘ’８（４ビット）と分割データｙ’８（４ビット）と内部データｃ’７（１ビット）とが入力されると、対応する分割データｚ’８（４ビット）が一意に決定される。
【０１２１】
最終的に、加算部２＃は、決定した分割データｚ’１〜ｚ’８を結合して符号化データＺ’として出力する。
【０１２２】
＜３−２−３．テーブル生成処理＞
以下、各テーブル生成処理について説明する。
【０１２３】
テーブルＴ１の内部処理としては、写像変換部２２１１，２２１２，２２１６，２２１７と、算術加算部２２１３，２２１４と、データ分割部２２１５とを含む。
【０１２４】
写像変換部２２１１は、全単射変換Ｘｆ１に従って、４ビットの分割データｘ’１を４ビットのデータに単射変換する。同様に、写像変換部２２１２は、全単射変換Ｙｆ１に従って、４ビットの分割データｙ’１を４ビットのデータに単射変換する。ここで、全単射変換Ｘｆ１およびＹｆ１は、それぞれ全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。
【０１２５】
図７に示すように、第１符号化部３＃は、全単射変換Ｘｆ１の逆変換である全単射変換Ｘｆ−１１に従って分割データｘ１を単射変換して分割データｘ’１に符号化する。これに対して、写像変換部２２１１は、全単射変換Ｘｆ１に従って分割データｘ’１を単射変換する。したがって、第１符号化部３＃における全単射変換Ｘｆ−１１による単射変換と、写像変換部２２１１における全単射変換Ｘｆ１による単射変換とは互いに相殺される。よって、写像変換部２２１１からは分割データｘ１が出力される。
【０１２６】
また、第２符号化部４＃は、全単射変換Ｙｆ１の逆変換である全単射変換Ｙｆ−１１に従って分割データｙ１を単射変換して分割データｙ’１に符号化する。これに対して、写像変換部２２１２は、全単射変換Ｙｆ１に従って分割データｙ’１を単射変換する。したがって、第２符号化部４＃における全単射変換Ｙｆ−１１による単射変換と、写像変換部２２１２における全単射変換Ｙｆ１による単射変換とは互いに相殺される。よって、写像変換部２２１２からは分割データｙ１が出力される。
【０１２７】
そして、算術加算部２２１３は、写像変換部２２１１から出力された分割データｘ１と、写像変換部２２１２から出力された分割データｙ１とを算術加算して、５ビットのデータを生成する。さらに、算術加算部２２１４は、算術加算部２２１３で加算処理が行なわれた後の５ビットのデータとデータα１とを算術加算する。さらに、データ分割部２２１５は、算術加算部２２１４から出力されるデータを上位４ビットと下位４ビットとに分割し、上位４ビットを内部データｃ１として出力するとともに、下位４ビットを分割データｚ１として出力する。すなわち、データ分割部２２１５は、算術加算部２２１４における加算結果を（ｃ１‖ｚ１）として扱う。
【０１２８】
ここで、データα１は８ビットのデータであり、その下位４ビットと上位４ビットとがそれぞれランダムに選択される。具体的には、データα１の下位４ビットは、２進数４ビットのデータ群｛００００，０００１｝の中からランダムに選択され、データα１の上位４ビットは、２進数４ビットのデータ群｛００００，０００１，・・・，１１１０｝の中からランダムに選択される。データα１をこのようなデータ群から選択することにより、入力される分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１を２種類に限定できる。
【０１２９】
一例として、データα１の上位４ビットとして「００００」が選択されると、分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１は、「００００」または「０００１」のみとなり、その他の値は出現しない。また、データα１の上位４ビットとして「１１１０」が選択されると、分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１は、「１１１０」または「１１１１」のみとなり、その他の値は出現しない。以下同様にして、データα１を上記のデータ群から選択すれば、入力される分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１を２種類に限定できる。
【０１３０】
このように、分割データｘ’１，ｙ’１に加えて、ランダムに選択されるデータα１を含む算術加算処理を行なうことにより内部データｃ１の候補数が増えるため、テーブルＴ１の入出力データである分割データｘ’１，ｚ’１を観測されたとしても、内部データｃ１を特定されにくくなる。
【０１３１】
さらに、写像変換部２２１７は、全単射変換Ｚｆ１に従って、分割データｚ１を分割データｚ’１に符号化して出力する。同様に、写像変換部２２１６は、全単射変換Ｃｆ１に従って、４ビットの内部データｃ１を内部データｃ’１に符号化して出力する。上述したように、出現する内部データｃ１の値を２種類に制限するため、内部データｃ’１は１ビットで表現できる。ここで、全単射変換Ｃｆ１は、全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。
【０１３２】
次に、テーブルＴ２の内部処理としては、写像変換部２２２１，２２２２，２２２６，２２２７，２２２８と、算術加算部２２２３，２２２４，２２２９と、データ分割部２２２５とを含む。
【０１３３】
写像変換部２２２１は、全単射変換Ｘｆ２に従って、４ビットの分割データｘ’２を単射変換して分割データｘ２を生成する。同様に、写像変換部２２２２は、全単射変換Ｙｆ２に従って、４ビットの分割データｙ’２を単射変換して分割データｙ２を生成する。ここで、全単射変換Ｘｆ２およびＹｆ２は、それぞれ全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。また、写像変換部２２２８は、全単射変換Ｃｆ１−１に従って、１ビットの内部データｃ’１を４ビットのデータに単射変換する。ここで、全単射変換Ｃｆ１−１は、テーブルＴ１の写像変換部２２１６においてランダムに選択された全単射変換Ｃｆ１の逆変換に相当する。そのため、写像変換部２２２８からは内部データｃ’１を復号化した内部データｃ１が出力される。
【０１３４】
そして、算術加算部２２２３は、写像変換部２２２１から出力された分割データｘ２と、写像変換部２２２２から出力された分割データｙ２とを算術加算して、５ビットのデータを生成する。さらに、算術加算部２２２９は、算術加算部２２２３で加算処理が行なわれた後の５ビットのデータと写像変換部２２２８から出力された内部データｃ１とを算術加算する。
【０１３５】
続いて、算術加算部２２２４は、算術加算部２２２９で加算処理が行なわれた後の６ビットのデータとデータα２とを算術加算する。さらに、データ分割部２２２５は、算術加算部２２２４から出力されるデータを上位４ビットと下位４ビットとに分割し、上位４ビットを内部データｃ２として出力するとともに、下位４ビットを分割データｚ２として出力する。すなわち、データ分割部２２２５は、算術加算部２２２４における加算結果を（ｃ２‖ｚ２）として扱う。
【０１３６】
ここでデータα２は、８ビットのデータであり、テーブルＴ１において内部データｃ１として出現するデータのパターンに応じて、その下位４ビットと上位４ビットとがそれぞれ次のように選択される。
【０１３７】
（ｉ）内部データｃ１として「００００」または「０００１」が出現する場合
データα２の上位４ビットは、２進数４ビットのデータ群｛０００１，００１０，・・・，１１１０｝の中からランダムに選択され、データα１の下位４ビットは「００００」に設定される。
【０１３８】
（ｉｉ）内部データｃ１として「ｗ」または「ｗ＋１」（但し、０００１≦ｗ≦１１１０）が出現する場合
データα２の上位４ビットは、２進数４ビットのデータ群｛００００，０００１，・・・，１１０１｝の中からランダムに選択され、データα２の下位４ビットは（１１１１−（ｗ−０００１））ｍｏｄ１６の演算値に設定される。
【０１３９】
データα２をこのように選択することにより、入力される分割データｘ’１，ｙ’１の各組合せに対応する内部データｃ１を「ｖ」と「ｖ＋１」（０００１≦ｖ≦１１１０）との２種類に限定できる。
【０１４０】
さらに、写像変換部２２２７は、全単射変換Ｚｆ２に従って、分割データｚ２を分割データｚ’２に符号化して出力する。同様に、写像変換部２２２６は、全単射変換Ｃｆ２に従って、４ビットの内部データｃ２を内部データｃ’２に符号化して出力する。上述したように、出現する内部データｃ２の値を２種類に制限するため、内部データｃ’２は１ビットで表現できる。ここで、全単射変換Ｃｆ２は、全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。
【０１４１】
以下、テーブルＴｉ（３≦ｉ≦７）の内部処理は、テーブルＴ２の内部処理と同様であるため詳細な説明は繰返さない。なお、各テーブルＴｉで使用されるデータαｉは、次のように選択される。
【０１４２】
（ｉ）内部データｃｉ−１として「００００」または「０００１」が出現する場合
データαｉの上位４ビットは、２進数４ビットのデータ群｛０００１，００１０，・・・，１１１０｝の中からランダムに選択され、データαｉの下位４ビットは「００００」に設定される。
【０１４３】
（ｉｉ）内部データｃｉ−１として「ｗ」または「ｗ＋１」（但し、０００１≦ｗ≦１１１０）が出現する場合
データαｉの上位４ビットは、２進数４ビットのデータ群｛００００，０００１，・・・，１１０１｝の中からランダムに選択され、データαｉの下位４ビットは（１１１１−（ｗ−０００１））ｍｏｄ１６の演算値に設定される。
【０１４４】
最後に、テーブルＴ８の内部処理としては、写像変換部２２８１，２２８２，２２８７，２２８８と、算術加算部２２８３，２２８４，２２８９と、データ分割部２２８５とを含む。
【０１４５】
写像変換部２２８１は、全単射変換Ｘｆ８に従って、４ビットの分割データｘ’８を単射変換して分割データｘ８を生成する。同様に、写像変換部２２８２は、全単射変換Ｙｆ８に従って、４ビットの分割データｙ’８を単射変換して分割データｙ８を生成する。ここで、全単射変換Ｘｆ８およびＹｆ８は、それぞれ全単射候補格納部２０に予め格納される複数の全単射変換からランダムに選択される。また、写像変換部２２８８は、全単射変換Ｃｆ８−１に従って、１ビットの内部データｃ’１５を４ビットのデータに単射変換する。ここで、全単射変換Ｃｆ７−１は、テーブルＴ７においてランダムに選択された全単射変換Ｃｆ７（図示しない）の逆変換に相当する。そのため、写像変換部２２８８からは内部データｃ’７を復号化した内部データｃ７が出力される。
【０１４６】
そして、算術加算部２２８３は、写像変換部２２８１から出力された分割データｘ８と、写像変換部２２８２から出力された分割データｙ８とを算術加算して、５ビットのデータを生成する。さらに、算術加算部２２８９は、算術加算部２２８３で加算処理が行なわれた後の５ビットのデータと写像変換部２２８８から出力された内部データｃ７とを算術加算する。
【０１４７】
続いて、算術加算部２２８４は、算術加算部２２８９で加算処理が行なわれた後の６ビットのデータとデータα８とを算術加算する。さらに、データ分割部２２８５は、算術加算部２２８４から出力されるデータを上位４ビットと下位４ビットとに分割し、上位４ビットを内部データｃ８として出力するとともに、下位４ビットを分割データｚ８として出力する。すなわち、データ分割部２２８５は、算術加算部２２８４における加算結果を（ｃ８‖ｚ８）として扱う。
【０１４８】
ここでデータα８は、４ビットのデータであり、２進数４ビットのデータ群｛００００，０００１，・・・，１１１１｝の中からランダムに選択される。
【０１４９】
さらに、写像変換部２２８７は、全単射変換Ｚｆ８に従って、分割データｚ８を分割データｚ’８に符号化して出力する。
【０１５０】
以上のようなテーブルＴ１〜Ｔ８の内部処理に従って、テーブルＴ１〜Ｔ８が生成される。すなわち、加算部２＃における加算剰余演算処理の実行前に、テーブル生成部５（図２）が分割データｘ’ｉ，ｙ’ｉのすべての組合せ（分割データｘ’ｉ，ｙ’ｉがいずれも４ビットである場合には、２４×２４＝２５６通り）について、対応する内部データｃｉおよび分割データｚ’ｉを算出し、テーブルＴ１〜Ｔ８を生成する。テーブル生成部５が生成したテーブルＴ１〜Ｔ８は、テーブル格納部２２（図２）に格納される。そして、加算部２＃がテーブル格納部２２に格納されたテーブルＴ１〜Ｔ８を参照することで、加算剰余演算処理を実行する。
【０１５１】
＜３−２−４．符号化用変数の決定処理＞
再度、図７および図８を参照して、第１符号化部３＃および第２符号化部４＃における入力データＸおよび入力データＹの符号化処理には、全単射変換Ｘｆ−１１〜Ｘｆ−１８およびＹｆ−１１〜Ｙｆ−１８に加えて、データβおよびγが用いられる。上述したように、全単射変換Ｘｆ−１１〜Ｘｆ−１８およびＹｆ−１１〜Ｙｆ−１８による符号化処理は、テーブルＴ１〜Ｔ８の内部処理に組み込まれる全単射変換Ｘｆ１〜Ｘｆ８およびＹｆ１〜Ｙｆ８によって復号化（相殺）される。
【０１５２】
これに対して、データβおよびγによって符号化されたデータは、テーブルＴ１〜Ｔ８の内部処理においてランダムに選択されるデータαｉに応じてデータβおよびγを適切に選択することで復号化（相殺）される。
【０１５３】
具体的には、データβおよびγは、データαｉと以下のような関係式が成立するように選択される。なお、式中の０ｋはビット０がｋ個並ぶことを意味する。
【０１５４】
α＝−（β＋γ）ｍｏｄ２３２
但し、α＝（α８‖０２８）＋（α７‖０２４）＋（０４‖α６‖０２０）＋・・・＋（０２０‖α２‖０４）＋（０２４‖α１）ｍｏｄ２３２
この関係式によれば、データα１〜α８に応じて、データβとデータγとの合計値が制限されるのみでありデータβおよびデータγの各々についての制約はない。そこで、テーブル生成部５（図２）は、データβおよびデータγのいずれか一方の値を０〜（２３２−１）の範囲でランダムに選択した後に、当該選択した値とデータα１〜α８とに基づいて、他方の変数の値を決定する。
【０１５５】
すなわち、上記の手続きによって決定されたデータα，β，γは、入力データＸおよびＹとの間に以下のような関係が成立する。
【０１５６】
（Ｘ＋β）＋（Ｙ＋γ）＋αｍｏｄＮ＝Ｘ＋ＹｍｏｄＮ
（３−３）入力データと分割ビット幅との関係
本発明に係る加算装置では、加算の法Ｎとして２のｍ乗（２ｍ：但し、ｍは２以上の整数）をとることができ、この場合には入力データＸ，Ｙを分割する際のビット幅ｎとして、ｍ/ｎが整数となる２以上の任意の値をとることができる。ビット幅ｎを大きくする程、ランダムに選択されるデータαｉの候補が増えるため、加算剰余演算時に参照されるテーブルから符号化データＸ’，Ｙ’，Ｚ’の符号化前のデータＸ，Ｙ，Ｚを求めることは困難になる。すなわち、秘匿に対する安全性は向上する。一方、ビット幅ｎを大きくすると、テーブルサイズが大きくなるため効率が悪くなる。ここで、べき乗数ｍ＝３２、すなわち法Ｎ＝２３２とし、ｎを２以上８以下の値とすると、αｉ（１≦ｉ≦ｍ/ｎ）の候補の総数は、２×（２ｎ−１）×（２ｎ−２）３２/ｎ−２×２ｎで表される。テーブルサイズは、（２２ｎ×（ｎ＋１）＋２２ｎ＋１×（ｎ＋１）×（３２/ｎ−２）＋２２ｎ＋１×ｎ）ビットとなる。
【０１５７】
（３−４）加算処理の処理手順
上述した加算処理における処理手順について図１０を用いて説明する。
【０１５８】
図１０は、この発明の実施の形態に従う加算処理を示すフローチャートである。図１０のフローチャートに示される処理は、ＣＰＵ１２０が固定ディスク１２４などに格納されるプログラムを読出して実行し、図２に示される各機能を制御することで実現される。
【０１５９】
図２および図１０を参照して、まず、加算部２として機能するＣＰＵ１２０は、符号化データＸ’およびＹ’を取得する（ステップＳ１００）。そして、加算部２として機能するＣＰＵ１２０は、符号化データＸ’およびＹ’をそれぞれ所定のビット毎に分割し、分割データｘ’ｉおよびｘ’ｉ（１≦ｉ≦ｍ/ｎ）を生成する（ステップＳ１０２）。なお、加算部２における加算の法Ｎ＝２ｍであり、ｎは分割するビット幅である。
【０１６０】
加算部２として機能するＣＰＵ１２０は、インデックスｉ＝１に設定する（ステップＳ１０４）。そして、加算部２として機能するＣＰＵ１２０は、固定ディスク１２４のテーブル格納部２２に予め格納されたテーブルＴｉを参照し、分割データｘ’ｉおよびｘ’ｉの組合せに対応する分割データｚ’ｉおよび内部データｃｉを決定する（ステップＳ１０６）。続いて、加算部２として機能するＣＰＵ１２０は、インデックスｉ＝ｍ/ｎであるか否かを判断する（ステップＳ１０８）。
【０１６１】
インデックスｉ＝ｍ/ｎでなければ（ステップＳ１０８においてＮＯ）、加算部２として機能するＣＰＵ１２０は、インデックスｉを１だけインクリメント（ステップＳ１１０）した後、ステップＳ１０６以降の処理を繰返す。
【０１６２】
これに対して、インデックスｉ＝ｍ/ｎであれば（ステップＳ１０８においてＹＥＳ）、加算部２として機能するＣＰＵ１２０は、ステップＳ１０６において決定した分割データｚ’ｉを結合（ステップＳ１１２）し、符号化データＺ’として出力する（ステップＳ１１４）。以上のような処理によって、加算処理が実行される。
【０１６３】
（３−５）テーブル生成処理の処理手順
上述したテーブル生成処理における処理手順について図１１を用いて説明する。
【０１６４】
図１１は、この発明の実施の形態に従うテーブル生成処理を示すフローチャートである。図１１のフローチャートに示される処理は、ＣＰＵ１２０が固定ディスク１２４などに格納されるプログラムを読出して実行し、図２に示される各機能を制御することで実現される。
【０１６５】
図２および図１１を参照して、まず、テーブル生成部５として機能するＣＰＵ１２０は、加算部２における加算の法Ｎ＝２ｍと入力データを分割する際のビット幅ｎとを取得する（ステップＳ２００）。そして、テーブル生成部５として機能するＣＰＵ１２０は、インデックスｉ＝１に設定する（ステップＳ２０２）。
【０１６６】
続いて、テーブル生成部５として機能するＣＰＵ１２０は、インデックスｉ＝ｍ/ｎであるか否かを判断する（ステップＳ２０４）。すなわち、テーブル生成部５として機能するＣＰＵ１２０は、現在のインデックスが最終段のテーブルを指示しているか否かを判断する。
【０１６７】
インデックスｉ＝ｍ/ｎでなければ（ステップＳ２０４においてＮＯ）、テーブル生成部５として機能するＣＰＵ１２０は、インデックスｉ＝１であるか否かを判断する（ステップＳ２０６）。すなわち、テーブル生成部５として機能するＣＰＵ１２０は、現在のインデックスが先頭のテーブルを指示しているか否かを判断する。
【０１６８】
インデックスｉ＝１であれば（ステップＳ２０６においてＹＥＳ）、テーブル生成部５として機能するＣＰＵ１２０は、固定ディスク１２４の全単射候補格納部２０に予め格納された複数の全単射変換の候補から、全単射変換Ｘｆ１，Ｙｆ１，Ｚｆ１，Ｃｆ１，Ｃｆ−１１をランダムに選択するとともに、データα１を所定のデータ群からランダムに選択する（ステップＳ２０８）。テーブル生成部５として機能するＣＰＵ１２０は、このように選択した全単射変換Ｘｆ１，Ｙｆ１，Ｚｆ１，Ｃｆ１およびデータα１に基づいて、図５または図９に示す内部処理に従ってテーブルＴ１を生成する（ステップＳ２１０）。具体的には、テーブル生成部５として機能するＣＰＵ１２０は、入力され得る分割データｘ’１，ｙ’１の各組合せに対応する分割データｚ’１および内部データｃ’１を順次算出し、分割データｘ’１，ｙ’１との組合せと分割データｚ’１および内部データｃ’１との対応関係を示すデータ構造を構成する。
【０１６９】
これに対して、インデックスｉ＝１でなければ（ステップＳ２０６においてＮＯ）、テーブル生成部５として機能するＣＰＵ１２０は、固定ディスク１２４の全単射候補格納部２０に予め格納された複数の全単射変換の候補から、全単射変換Ｘｆｉ，Ｙｆｉ，Ｚｆｉ，Ｃｆｉ，Ｃｆ−１ｉをランダムに選択するとともに、データαｉを所定のデータ群からランダムに選択する（ステップＳ２１２）。テーブル生成部５として機能するＣＰＵ１２０は、このように選択した全単射変換Ｘｆｉ，Ｙｆｉ，Ｚｆｉ，Ｃｆｉ、１つ前のインデックス値での処理において選択した全単射変換Ｃｆ−１ｉ−１、および選択したデータαｉに基づいて、図５または図９に示す内部処理に従ってテーブルＴｉを生成する（ステップＳ２１４）。このテーブルＴｉの生成処理においても、テーブル生成部５として機能するＣＰＵ１２０は、ステップＳ２１０において説明した処理と同様の処理を実行する。
【０１７０】
ステップＳ２１０またはステップＳ２１４の処理後、テーブル生成部５として機能するＣＰＵ１２０は、インデックスｉを１だけインクリメント（ステップＳ２１６）し、ステップＳ２０４以降の処理を再度実行する。
【０１７１】
一方、インデックスｉ＝ｍ/ｎであれば（ステップＳ２０４においてＹＥＳ）、テーブル生成部５として機能するＣＰＵ１２０は、インデックスｉ＝１であるか否かを判断する（ステップＳ２２６）。すなわち、テーブル生成部５として機能するＣＰＵ１２０は、現在のインデックスが先頭のテーブルを指示しているか否かを判断する。
【０１７２】
インデックスｉ＝１であれば（ステップＳ２２６においてＹＥＳ）、テーブル生成部５として機能するＣＰＵ１２０は、固定ディスク１２４の全単射候補格納部２０に予め格納された複数の全単射変換の候補から、全単射変換Ｘｆ１，Ｙｆ１，Ｚｆ１をランダムに選択するとともに、データα１を所定のデータ群からランダムに選択する（ステップＳ２２８）。なお、ステップＳ２２８の処理が実行されるのは、加算部２が１つのテーブルだけを参照して加算剰余演算処理を実現する場合であるので、全単射変換Ｃｆ１，Ｃｆ−１１を選択する必要がない。このように選択した全単射変換Ｘｆ１，Ｙｆ１，Ｚｆ１およびデータα１に基づいて、図５または図９に示す内部処理に従ってテーブルＴ１を生成する（ステップＳ２３０）。このテーブルＴ１の生成処理においても、テーブル生成部５として機能するＣＰＵ１２０は、ステップＳ２１０において説明した処理と同様の処理を実行する。
【０１７３】
これに対して、インデックスｉ＝１でなければ（ステップＳ２２６においてＮＯ）、テーブル生成部５として機能するＣＰＵ１２０は、テーブル生成部５として機能するＣＰＵ１２０は、固定ディスク１２４の全単射候補格納部２０に予め格納された複数の全単射変換の候補から、全単射変換Ｘｆｍ／ｎ，Ｙｆｍ／ｎ，Ｚｆｍ／ｎをランダムに選択するとともに、データαｍ／ｎを所定のデータ群からランダムに選択する（ステップＳ２３２）。テーブル生成部５として機能するＣＰＵ１２０は、このように選択した全単射変換Ｘｆｍ／ｎ，Ｙｆｍ／ｎ，Ｚｆｍ／ｎ、１つ前のインデックス値での処理において選択した全単射変換Ｃｆ−１ｍ／ｎ−１、および選択したデータαｍ／ｎに基づいて、図５または図９に示す内部処理に従ってテーブルＴｍ／ｎを生成する（ステップＳ２３４）。なお、ステップＳ２３４は、加算部２で使用するテーブルの最終段を生成する処理であるので、全単射変換Ｃｆｍ／ｎ，Ｃｆ−１ｍ／ｎを選択する必要がない。このテーブルＴｍ／ｎの生成処理においても、テーブル生成部５として機能するＣＰＵ１２０は、ステップＳ２１０において説明した処理と同様の処理を実行する。
【０１７４】
ステップＳ２３０またはステップＳ２３４の処理後、テーブル生成部５として機能するＣＰＵ１２０は、生成したテーブルＴ１〜Ｔｍ／ｎをテーブル格納部２２に格納する（ステップＳ２４０）。そして、テーブル生成処理は終了する。
【０１７５】
［４．暗号化処理への適用例］
以下では、本実施の形態に係る加算装置を具体的な暗号化処理に適用する例について説明する。
【０１７６】
図１２は、加算剰余演算処理を含む暗号化処理の代表例であるＢｌｏｗｆｉｓｈの概略の処理手順を示す図である。
図１２を参照して、Ｂｌｏｗｆｉｓｈは、「ラウンド」と呼ばれる処理単位を繰返すことで暗号化を行なう。ｉ番目のラウンドは、ラウンド鍵と呼ばれる秘密情報Ｐｉ（以下、ラウンド鍵Ｐｉとも記す）と入力データＬｉとの排他的論理和と、Ｆ関数と呼ばれる変換処理と、Ｆ関数の出力と入力データＲｉとの排他的論理和と、ビットの入れ替え処理とによって構成される。
【０１７７】
具体的には、ラウンド１としては、ラウンド鍵Ｐ１と入力データＬ１との間で排他的論理和をとる排他的論理和演算部７０１と、Ｆ関数の出力と入力データＲ１との間で排他的論理和をとる排他的論理和演算部８０１とを含む。排他的論理和演算部７０１から出力されるデータは、入力データＲ２としてラウンド２へ与えられ、排他的論理和演算部８０１から出力されるデータは、入力データＬ２としてラウンド２へ与えられる。以下、ラウンド２〜１５についても同様の構成となる。
【０１７８】
最終のラウンド１６においては、ラウンド１〜１５の構成に加え、排他的論理和演算部７１６の出力データとラウンド鍵Ｐ１８との間で排他的論理和をとる排他的論理和演算部７２０と、排他的論理和演算部８１６の出力データとラウンド鍵Ｐ１７との間で排他的論理和をとる排他的論理和演算部８２０とを含む。
【０１７９】
図１３は、図１２に示すＦ関数の内部処理を示す図である。
図１３を参照して、Ｆ関数は、Ｓボックスと呼ばれる非線形変換Ｓ１〜Ｓ４を含む。さらに、Ｆ関数は、非線形変換Ｓ１の出力データを法２３２のもとでの非線形変換Ｓ２の出力データとの加算剰余演算処理を実行する加算剰余演算部６５と、加算剰余演算部６５の出力データと非線形変換Ｓ３の出力データとの間で排他的論理和をとる排他的論理和演算部６６と、排他的論理和演算部６６の出力データを法２３２のもとでの非線形変換Ｓ４の出力データとの加算剰余演算処理を実行する加算剰余演算部６７とを含む、
なお、より詳細な処理の内容については、インターネット＜URL: http://www.schneier.com/paper-blowfish-oneyear.html＞などを参照されたい。
【０１８０】
本適用例においては、まず図１２に示すラウンド１〜１６の処理を図１４〜図１８に示すように等価変換した上で、暗号化処理を実行する。
【０１８１】
図１４は、図１２に示すラウンド１の処理を等価変換した処理を示す図である。
図１４を参照して、Ｆ関数６０１は、図１２に示す排他的論理和演算部７０１における処理を図１３に示すＦ関数の内部処理に移動したものである。すなわち、非線形変換Ｓ１〜Ｓ４の前段にそれぞれ排他的論理和演算部６０１１〜６０１４が設けられる。排他的論理和演算部６０１１〜６０１４は、入力されるデータを分割して得られる８ビットのデータと、以下のような関係を満たす８ビットのデータｐ１,ｊ（１≦ｊ≦４）との間で排他的論理和をとり、その結果をそれぞれ非線形変換Ｓ１〜Ｓ４へ与える。ここで、データｐ１,ｊは、図１２に示すラウンド鍵Ｐ１との間に、Ｐ１＝（ｐ１,４‖ｐ１,３‖ｐ１,２‖ｐ１,１）の関係が成立するように設定される。
【０１８２】
図１５は、図１２に示すラウンドｉ（２≦ｉ≦１４）の処理を等価変換した処理を示す図である。
【０１８３】
図１５を参照して、Ｆ関数６０２は、図１２に示す排他的論理和演算部７０２における処理を図１３に示すＦ関数の内部処理に移動したものである。すなわち、非線形変換Ｓ１〜Ｓ４の前段にそれぞれ排他的論理和演算部６０２１〜６０２４が設けられる。排他的論理和演算部６０２１〜６０２４は、入力されるデータを分割して得られる８ビットのデータと、以下のような関係を満たす８ビットのデータｐｉ,ｊ（１≦ｊ≦４）との間で排他的論理和をとり、その結果をそれぞれ非線形変換Ｓ１〜Ｓ４へ与える。ここで、データｐｉ,ｊは、図１２に示すラウンド鍵Ｐｉとの間に、Ｐｉ＝（ｐｉ,４‖ｐｉ,３‖ｐｉ,２‖ｐｉ,１）の関係が成立するように設定される。
【０１８４】
さらに、Ｆ関数６０２は、最終段にラウンド鍵Ｐｉ−１との間で排他的論理和をとる排他的論理和演算部６０２５が設けられる。これは、ラウンド（ｉ−１）のラウンド鍵Ｐｉ−１による処理をラウンド（ｉ−１）のＦ関数の内部に移動するとともに、ラウンドｉにも配置することにより、図１２に示す処理との等価性を維持する。
【０１８５】
図１６は、図１２に示すラウンド１５の処理を等価変換した処理を示す図である。
図１６を参照して、Ｆ関数６０３は、図１２に示す排他的論理和演算部７１６における処理を図１３に示すＦ関数の内部処理に移動したものである。すなわち、非線形変換Ｓ１〜Ｓ４の前段にそれぞれ排他的論理和演算部６０３１〜６０３４が設けられる。排他的論理和演算部６０３１〜６０３４は、入力されるデータを分割して得られる８ビットのデータと、以下のような関係を満たす８ビットのデータｐ１５,ｊ（１≦ｊ≦４）との間で排他的論理和をとり、その結果をそれぞれ非線形変換Ｓ１〜Ｓ４へ与える。ここで、データｐ１５,ｊは、図１２に示すラウンド鍵Ｐ１５との間に、Ｐ１５＝（ｐ１５,４‖ｐ１５,３‖ｐ１５,２‖ｐ１５,１）の関係が成立するように設定される。
【０１８６】
さらに、Ｆ関数６０３は、その最終段に設けられた排他的論理和演算部６０３５を含む。排他的論理和演算部６０３５は、加算剰余演算部６７の出力と、ラウンド１４のラウンド鍵Ｐ１４と、ラウンド１６のラウンド鍵Ｐ１６と、ラウンド１８のラウンド鍵Ｐ１８と間で排他的論理和をとる。これにより、図１２に示す処理との等価性を維持する。
【０１８７】
図１７は、図１２に示すラウンド１６の処理を等価変換した処理を示す図である。
図１７を参照して、ラウンド鍵Ｐ１６との間の排他的論理和を算出する処理はラウンド１５に配置されるので、ラウンド１６の処理であるＦ関数６０４からは削除される。また、ラウンド１５の処理であるＦ関数６０３においてラウンド鍵Ｐ１８との間で排他的論理和をとる処理が挿入されているが、ラウンド１６におけるＦ関数６０４の入力では、本来、ラウンド鍵Ｐ１８との間で排他的論理和をとる必要がない。そこで、ラウンド１５におけるラウンド鍵Ｐ１８との間で排他的論理和の影響を相殺するために、Ｆ関数６０４の先頭においてラウンド鍵Ｐ１８との排他的論理和をとる処理が挿入される。
【０１８８】
さらに、Ｆ関数６０４は、その最終段に設けられた排他的論理和演算部６０４５を含む。排他的論理和演算部６０４５は、加算剰余演算部６７の出力と、ラウンド１５のラウンド鍵Ｐ１５と、ラウンド１７のラウンド鍵Ｐ１７との間で排他的論理和をとる。これにより、図１２に示す処理との等価性を維持する。
【０１８９】
以下、図１４〜図１７に示すような等価変換後の処理をテーブルの参照によって実行する方法について説明する。すなわち、以下では、図１４〜図１７に示す処理ブロックの各々をテーブル化する方法について説明する。なお、暗号化処理の安全性を高めるために、各処理ブロック間のデータは符号化された状態で受け渡される。そのため、図１４〜図１７に示す処理ブロックが単純にテーブル化するのではなく、入出力が符号化された状態で処理を行なうことができるようにテーブル化する。
【０１９０】
まず、図１４に示すラウンド１の処理においては、処理ブロックＲＴ１１〜ＲＴ１８がテーブル化の対象である。
【０１９１】
図１８は、図１４に示す処理ブロックＲＴ１１をテーブル化する方法を説明する図である。図１８（ａ）は、処理ブロックＲＴ１１における処理の概略を示す図であり、図１８（ｂ）は、テーブル化するための内部処理を示す図である。
【０１９２】
図１８（ａ）を参照して、処理ブロックＲＴ１１は、２つの入力データ（代表的に、３２ビット）間で排他的論理和をとる。
【０１９３】
図１８（ｂ）を参照して、本適用例では、テーブルサイズの肥大化を抑制するために、入力データを所定のビット毎（代表的に、４ビット毎）に分割した上で、２つの４ビットの入力データ間の排他的論理和をとるための処理をテーブルによって構成する。すなわち、処理ブロックＲＴ１１の処理を、８ビット入力／４ビット出力の対応関係を有する排他的論理和テーブル１０１〜１０８に置換する。
【０１９４】
排他的論理和テーブル１０１〜１０８の各々は、写像変換部７５および７６を含み、写像変換部７５および７６が、それぞれランダムに選択される全単射変換に従って入力される２つのデータを符号化する。そして、排他的論理和演算部７８が写像変換部７５および７６でそれぞれ符号化された後の入力データの間で排他的論理和をとり、写像変換部７７へ出力する。写像変換部７７は、ランダムに選択される全単射変換に従って、排他的論理和演算部７８から出力されたデータを写像変換した後に出力する。排他的論理和テーブル１０１〜１０８は、このような内部処理に従って生成される。
【０１９５】
なお、本適用例において説明するすべてのテーブルでは、入力側に設けられる全単射変換（図１８の写像変換部７５や７６など）は、直前に配置（参照）されるテーブルにおける出力側に設けられる全単射変換の逆変換と一致するように選択される。なお、図１４に示す処理ブロックＲＴ１１には平文Ｒ１がそのまま入力されるため、直前に参照されるテーブルはないが、このような場合には、平文Ｒ１の前処理として処理ブロックＲＴ１１における入力側の全単射変換の逆変換に従って、符号化処理が行なわれる。
【０１９６】
図１４に示す処理ブロックＲＴ１７についても、上述した処理ブロックＲＴ１１と同様にテーブル化される。また、図１４に示す処理ブロックＲＴ１６およびＲＴ１８は、法２３２のもとでの加算剰余演算であるので、図９に示すような方法によってテーブル化される。
【０１９７】
図１９は、図１４に示す処理ブロックＲＴ１２，ＲＴ１３，ＲＴ１４，ＲＴ１５をテーブル化する方法を説明する図である。
【０１９８】
図１９を参照して、処理ブロックＲＴ１２，ＲＴ１３，ＲＴ１４，ＲＴ１５は、それぞれ８ビット入力／３２ビット出力の単一のテーブルとして構成される。また、処理ブロックＲＴ１２，ＲＴ１３，ＲＴ１５では、テーブル化に際して、それぞれ非線形変換Ｓ１，Ｓ２，Ｓ４の後段に算術加算部８１，８２，８４が挿入され、それぞれランダムに選択されたデータβＲＴ１２，γＲＴ１３，γＲＴ１５が算術加算される。ここで、データβＲＴ１２、γＲＴ１３は以下の関係を満たす値である。
【０１９９】
α＝−（βＲＴ１２＋γＲＴ１３）ｍｏｄ２３２
ここでのデータαは、上述の処理ブロックＲＴ１６を図９に示すような方法によってテーブル化する際に使用されるデータαｉ（１≦ｉ≦８）から以下の式に従って算出されるデータである。
【０２００】
α＝（α８‖０２８）＋（α７‖０２４）＋（０４‖α６‖０２０）＋・・・＋（０２０‖α２‖０４）＋（０２４‖α１）ｍｏｄ２３２
すなわち、データβＲＴ１２，γＲＴ１３は、処理ブロックＲＴ１６のテーブル化に用いられるランダムに選択されるデータαの影響を相殺するためのデータである。なお、ＲＴ１２をテーブル化するときの出力側の全単射変換は、図７に示す全単射変換Ｘｆ−１ｉ（１≦ｉ≦８）に相当し、ＲＴ１３をテーブル化するときの出力側の全単射変換は、図８の全単射変換Ｙｆ−１ｉ（１≦ｉ≦８）に相当する。
【０２０１】
同様に、データγＲＴ１５は以下の関係を満たす値である。
α＝−γＲＴ１５ｍｏｄ２３２
ここでのデータαは、上述の処理ブロックＲＴ１８を図９に示すような方法によってテーブル化する際に使用されるデータαｉ（１≦ｉ≦８）から以下の式に従って算出されるデータである。
【０２０２】
α＝（α８‖０２８）＋（α７‖０２４）＋（０４‖α６‖０２０）＋・・・＋（０２０‖α２‖０４）＋（０２４‖α１）ｍｏｄ２３２
すなわち、データγＲＴ１５は、処理ブロックＲＴ１８のテーブル化に用いられるランダムに選択されるデータαの影響を相殺するためのデータである。なお、ＲＴ１５をテーブル化するときの出力側の全単射変換は、図８に示す全単射変換Ｙｆ−１ｉ（１≦ｉ≦８）に相当する。
【０２０３】
さらに、処理ブロックＲＴ１２，ＲＴ１３，ＲＴ１４，ＲＴ１５は、それぞれ写像変換部７１〜７４を入力側に含むとともに、それぞれ写像変換部９１〜９４を出力側に含む。そして、写像変換部７１〜７４の各々は、ランダムに選択される全単射変換に従って入力されるデータを符号化し、写像変換部９１〜９４の各々は、ランダムに選択される全単射変換に従って出力されるデータを符号化する。
【０２０４】
処理ブロックＲＴ１２，ＲＴ１３，ＲＴ１４，ＲＴ１５は、このような内部処理に従ってテーブル化される。
【０２０５】
次に、図１５に示すラウンドｉ（２≦ｉ≦１４）に含まれる処理ブロックＲＴ２１〜ＲＴ２８のテーブル化について説明する。対象となる処理ブロックＲＴ２１〜ＲＴ２８のうち、処理ブロックＲＴ２１〜２７については、それぞれ上述の処理ブロックＲＴ１１〜１７のブロック化と同様の方法によりブロック化できるので、詳細な説明は繰返さない。
【０２０６】
図２０は、図１５に示す処理ブロックＲＴ２８をテーブル化する方法を説明する図である。
【０２０７】
図２０を参照して、処理ブロックＲＴ２８をテーブル化する方法は、上述した図９に示す方法に比較して、ラウンド鍵Ｐｉ−１との排他的論理和演算部７０１８〜７０８８を写像変換部２２１７〜２２８７の直前に配置する点が異なるだけである。図２０の排他的論理和演算部７０１８〜７０８８で使用されるラウンド鍵ｐ’ｉ−１,ｊ（１≦ｊ≦８）は、ラウンド鍵Ｐｉ−１を４ビット毎に分割したデータであり、以下の関係を満たす。
【０２０８】
Ｐｉ−１＝（ｐ’ｉ−１,８‖ｐ’ｉ−１,７‖ｐ’ｉ−１,６‖ｐ’ｉ−１,５‖ｐ’ｉ−１,４‖ｐ’ｉ−１,３‖ｐ’ｉ−１,２‖ｐ’ｉ−１,１）
処理ブロックＲＴ２８は、このような内部処理に従ってテーブル化される。
【０２０９】
次に、図１６に示すラウンド１５において対象となる処理ブロックＲＴ３１〜ＲＴ３７のうち、処理ブロックＲＴ３１〜３７についてはそれぞれ上述の処理ブロックＲＴ１１〜１７のブロック化と同様の方法によりブロック化でき、処理ブロックＲＴ３８については上述の処理ブロックＲＴ２８のブロック化と同様の方法によりブロック化できるので、詳細な説明は繰返さない。
【０２１０】
また、図１７に示すラウンド１６において対象となる処理ブロックＲＴ４１〜ＲＴ４７のうち、処理ブロックＲＴ４１〜４７についてはそれぞれ上述の処理ブロックＲＴ１１〜１７のブロック化と同様の方法によりブロック化でき、処理ブロックＲＴ４８については上述の処理ブロックＲＴ２８のブロック化と同様の方法によりブロック化できるので、詳細な説明は繰返さない。
【０２１１】
なお、本発明の実施の形態と本願発明との対応関係については、データ分割部２ａが「第１分割手段」に対応し、データ分割部２ｂが「第２分割手段」に対応し、テーブル格納部２２が「テーブル格納手段」に対応し、テーブル参照部２ｃが「テーブル参照手段」に対応し、データ結合部２ｄが「結合手段」に対応し、テーブル生成部５が「テーブル生成手段」に対応し、全単射候補格納部２０が「全単射候補格納手段」に対応し、乱数発生部５ａが「選択手段」に対応する。
【０２１２】
本発明に係る加算処理は、上述したＢｌｏｗｆｉｓｈ以外の暗号化処理についても適用可能であると考えられる。すなわち、本発明に係る加算処理は、ＣＡＳＴ−１２８やＣ２、Ｍ６といった加算処理を含む暗号化処理に適用可能であると考えられる。
【０２１３】
本実施の形態によれば、加算対象となる２つの入力データと加算結果として得られる出力データとはいずれも符号化された状態で入出力される。すなわち、予め符号化された２つの入力データの取り得る値の組合せと、加算処理の結果得られる出力データを符号化した値とを対応付けた関数テーブルが予め生成されるので、この関数テーブルを参照するだけで加算結果を得ることができ、入力データが与えられる毎に実際の加算処理を行なう必要がない。これにより、復号化鍵や復号化途中にあるコンテンツがメモリ上に不可避的に配置されることを回避できる。
【０２１４】
よって、暗号化処理や復号化処理における復号化鍵や復号化途中のデータに対する秘匿性を確保して、よりセキュリティ機能を高めた加算処理を実現できる。
【０２１５】
また、本実施の形態によれば、所定のデータ幅をもつ入力データを所定のビット幅ごとに分割した上で、関数テーブルを参照することで各分割データに対応するデータを取得する。すなわち、関数テーブルは、分割されたデータのデータ幅に応じたものを使用することができるので、そのテーブルサイズの肥大化を抑制できる。これにより、テーブル生成処理の簡素化および高速化、ならびに固定ディスクに示すテーブル格納部の大きさの抑制を実現できる。
【０２１６】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した説明ではなく、特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０２１７】
【図１】この発明の実施の形態に従う加算装置を実現するための代表例であるコンピュータのハードウェア構成を示すブロック図である。
【図２】この発明の実施の形態に従う加算装置を実現する主要な機能構成を示すブロック図である。
【図３】この発明の実施の形態に従う第１符号化部における機能構成を示すブロック図である。
【図４】この発明の実施の形態に従う第２符号化部における機能構成を示すブロック図である。
【図５】この発明の実施の形態に従う加算部における機能構成を示すブロック図である。
【図６】この発明の実施の形態に従う加算部が参照するテーブルのデータ構造の一例を示す図である。
【図７】この発明の実施の形態に従う第１符号化部における機能構成を示すブロック図である。
【図８】この発明の実施の形態に従う第２符号化部における機能構成を示すブロック図である。
【図９】この発明の実施の形態に従う加算部における機能構成を示すブロック図である。
【図１０】この発明の実施の形態に従う加算処理を示すフローチャートである。
【図１１】この発明の実施の形態に従うテーブル生成処理を示すフローチャートである。
【図１２】加算剰余演算処理を含む暗号化処理の代表例であるＢｌｏｗｆｉｓｈの概略の処理手順を示す図である。
【図１３】図１２に示すＦ関数の内部処理を示す図である。
【図１４】図１２に示すラウンド１の処理を等価変換した処理を示す図である。
【図１５】図１２に示すラウンドｉ（２≦ｉ≦１４）の処理を等価変換した処理を示す図である。
【図１６】図１２に示すラウンド１５の処理を等価変換した処理を示す図である。
【図１７】図１２に示すラウンド１６の処理を等価変換した処理を示す図である。
【図１８】図１４に示す処理ブロックをテーブル化する方法を説明する図である。
【図１９】図１４に示す処理ブロックをテーブル化する方法を説明する図である。
【図２０】図１５に示す処理ブロックをテーブル化する方法を説明する図である。
【図２１】非特許文献１に開示された暗号化処理の概略を説明するための図である。
【符号の説明】
【０２１８】
２  加算部、２ａ，２ｂ，３２２，３４２，４２２，４４２，２０１５，２０２５，２１６５，２２１５，２２２５，２２８５  データ分割部、２ｃ  テーブル参照部、２ｄ，３２４，３４４，４２４，４４４  データ結合部、３  第１符号化部、４  第２符号化部、５  テーブル生成部、５ａ  乱数発生部、２０  全単射候補格納部、２２  テーブル格納部、６５，６７，３２０，４２０，４４０  加算剰余演算部、６６，７８，７０１〜７１６，７２０，８０１〜８１６，８２０，６０１１〜６０１４，６０２１〜６０２５，６０２５，６０３１〜６０３５，６０４５，７０１８〜７０８８  排他的論理和演算部、７１〜７４，７５，７７，９１〜９４，３０１〜３１６，３３１〜３３８，４０１〜４１６，４３１〜４３８，２０１１，２０１２，２０１６，２０１７，２０２１，２０２２，２０２６，２０２７，２０２８，２１６１，２１６２，２１６７，２１６８，２２１１，２２１２，２２１６，２２１７，２２２１，２２２２，２２２６，２２２７，２２２８，２２８１，２２８２，２２８７，２２８８  写像変換部、８１，８２，８４，２０１３，２０１４，２０２３，２０２４，２０２９，２１６３，２１６４，２１６９，２２１３，２２１４，２２２３，２２２４，２２２９，２２８３，２２８４，２２８９  算術加算部、１００  コンピュータ、１０４  モニタ、１０６  ＦＤドライブ、１０８  光ディスクドライブ、１１０  キーボード、１１２  マウス、１１６  フレキシブルディスク、１１８  ＣＤ−ＲＯＭ、１２２  メモリ、１２４  固定ディスク、１２８  通信インターフェース、１０１-１０８  排他的論理和テーブル。
【図１】
2008292810.tif 000003
【図２】
2008292810.tif 000004
【図３】
2008292810.tif 000005
【図４】
2008292810.tif 000006
【図５】
2008292810.tif 000007
【図６】
2008292810.tif 000008
【図７】
2008292810.tif 000009
【図８】
2008292810.tif 000010
【図９】
2008292810.tif 000011
【図１０】
2008292810.tif 000012
【図１１】
2008292810.tif 000013
【図１２】
2008292810.tif 000014
【図１３】
2008292810.tif 000015
【図１４】
2008292810.tif 000016
【図１５】
2008292810.tif 000017
【図１６】
2008292810.tif 000018
【図１７】
2008292810.tif 000019
【図１８】
2008292810.tif 000020
【図１９】
2008292810.tif 000021
【図２０】
2008292810.tif 000022
【図２１】
2008292810.tif 000023