(57)【要約】【課題】  任意の論理ゲートを、ゲートの種類と入出力の両方を秘匿したまま実現可能とする。【解決手段】  二つの数値ｘ，ｙの演算ｘ＊ｙとして、ｙ＝０の場合はｘ＊ｙ＝ｘ、ｙ＝１の場合はｘ＊ｙ＝１−ｘと定義し、  論理ゲートを    ｆａ，ｂ，ｃ，ｄ（ｘ，ｙ）＝ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ）の２次形式の関数で表現する（ａ，ｂ，ｃ，ｄはパラメータ）。  ａ，ｂ，ｃ，ｄ，ｘ，ｙの暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）を入力として、Ｅ（ｂ），Ｅ（ｘ）からＥ（ｂ＊ｘ）を計算し、Ｅ（ｃ），Ｅ（ｙ）からＥ（ｃ＊ｙ）を計算し、Ｅ（ｘ），Ｅ（ｙ）からＥ（ｘ＊ｙ）を計算し、Ｅ（ｄ），Ｅ（ｘ＊ｙ）からＥ（ｄ＊（ｘ＊ｙ））を計算し、Ｅ（ａ）、及び、Ｅ（ｂ＊ｘ），Ｅ（ｃ＊ｙ），Ｅ（ｄ＊（ｘ＊ｙ））を足し合わせて、Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ（ｘ＊ｙ））を得る。【選択図】図２
2006301310.tif 000002
【特許請求の範囲】
【請求項１】
二つの数値ｘ，ｙの演算ｘ＊ｙとして、ｙ＝０の場合はｘ＊ｙ＝ｘ、ｙ＝１の場合はｘ＊ｙ＝１−ｘと定義し、
論理ゲートを
ｆａ，ｂ，ｃ，ｄ（ｘ，ｙ）＝ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ）
の２次形式の関数で表現し（ａ，ｂ，ｃ，ｄはパラメータ）、
秘匿論理計算装置により、入出力値および演算内容を秘匿にして前記関数を計算することにより、任意の論理ゲートを実現する秘匿論理計算方法であって、
ａ，ｂ，ｃ，ｄ，ｘ，ｙの暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）を入力として、
Ｅ（ｂ），Ｅ（ｘ）からＥ（ｂ＊ｘ）を計算し、Ｅ（ｃ），Ｅ（ｙ）からＥ（ｃ＊ｙ）を計算し、Ｅ（ｘ），Ｅ（ｙ）からＥ（ｘ＊ｙ）を計算し、Ｅ（ｄ），Ｅ（ｘ＊ｙ）からＥ（ｄ＊（ｘ＊ｙ））を計算し、
Ｅ（ａ）、及び、前記Ｅ（ｂ＊ｘ），Ｅ（ｃ＊ｙ），Ｅ（ｄ＊（ｘ＊ｙ））を足し合わせて、
Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ（ｘ＊ｙ））
を得ることを特徴とする秘匿論理計算方法。
【請求項２】
請求項１記載の秘匿論理計算方法において、パラメータ（ａ，ｂ，ｃ，ｄ）は、予め所定の値に調整されることを特徴とする秘匿論理計算方法。
【請求項３】
請求項２記載の秘匿論理計算方法において、パラメータ（ａ，ｂ，ｃ，ｄ）＝（−５×４-1，４-1，４-1，３×４-1）として、ＡＮＤゲートを実現することを特徴とする秘匿論理計算方法。
【請求項４】
請求項２記載の秘匿論理計算方法において、パラメータ（ａ，ｂ，ｃ，ｄ）＝（−３×４-1，４-1，４-1，４-1）として、ＯＲゲートを実現することを特徴とする秘匿論理計算方法。
【請求項５】
請求項２記載の秘匿論理計算方法において、パラメータ（ａ，ｂ，ｃ，ｄ）＝（−１，２-1，２-1，０）として、ＸＯＲゲートを実現することを特徴とする秘匿論理計算方法。
【請求項６】
二つの数値ｘ，ｙの演算として、ｙ＝０の場合はｘ＊ｙ＝ｘ、ｙ＝１の場合はｘ＊ｙ＝１−ｘと定義し、
論理ゲートを
ｆａ，ｂ，ｃ，ｄ（ｘ，ｙ）＝ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ）
の２次形式の関数で表現し（ａ，ｂ，ｃ，ｄはパラメータ）、
入出力値および演算内容を秘匿にして前記関数を計算することにより、任意の論理ゲートを実現する秘匿論理計算装置であって、
ａ，ｂ，ｃ，ｄ，ｘ，ｙの暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）を入力する入力手段と、
Ｅ（ｂ），Ｅ（ｘ）からＥ（ｂ＊ｘ）を計算する第１の秘匿計算手段と、
Ｅ（ｃ），Ｅ（ｙ）からＥ（ｃ＊ｙ）を計算する第２の秘匿計算手段と、
Ｅ（ｘ），Ｅ（ｙ）からＥ（ｘ＊ｙ）を計算する第３の秘匿計算手段と、
Ｅ（ｄ），前記第３の秘匿計算手段で得られたＥ（ｘ＊ｙ）からＥ（ｄ＊（ｘ＊ｙ））を計算する第４の秘匿計算手段と、
Ｅ（ａ）、前記第１、第２及び第４の秘匿計算手段の計算結果のＥ（ｂ＊ｘ），Ｅ（ｃ＊ｙ），Ｅ（ｄ：（ｘ，ｙ））を足し合わせて、Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ（ｘ＊ｙ））を得る加算手段と、
を有することを特徴とする秘匿論理計算装置。
【請求項７】
請求項６記載の秘匿論理計算装置において、前記第１、第２、第３及び第４の秘匿計算手段は同一の秘匿計算手段で構成されることを特徴とする秘匿論理計算装置。
【請求項８】
請求項１乃至５のいずれか１項に記載の秘匿論理計算方法をコンピュータに実行させるためのプログラム。
【請求項９】
請求項１乃至５のいずれか１項に記載の秘匿論理計算方法をコンピュータに実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティの技術分野に関し、特に暗号情報を応用し、関数を解析不能な形で提供し、関数への入力値を知ることなく、当該関数の計算および出力結果の取得を可能とする技術に関する。
【背景技術】
【０００２】
従来、関数への入力値を知ることなく、当該関数の計算および出力結果の取得を可能とする技術としては、例えば、非特許文献1や非特許文献２などに記載の技術がある。これらの技術を用いれば、ある（複数の）数値に対して、ある暗号アルゴリズムを用いて変換することで当該数値を秘匿し、当該変換された数値を入力として、ある複数の装置が計算に協力することで、入力の（元の）数値を漏らすことなく関数の出力結果を得ることができる。更に出力結果の正当性、すなわち各装置が正しい処理を行ったかどうかを検証することができる。非特許文献２の技術を用いれば計算時間を削減した秘密計算を実現することもできる。
【０００３】
【非特許文献１】Ｂ．Ｓchoenmakers  and  Ｐ．Ｔuyls,“Ｐractical  Ｔwo-Ｐarty  Ｃomputation  based  on  the  Ｃonditional  Gates,”ASIACRYPT2004，Dec．2004．
【非特許文献２】千田、山本、鈴木、内山、「ＥlＧamal暗号を用いたマルチパーティ−による秘匿回路計算」，SCIS2005,2005年１月２５〜２８日
【発明の開示】
【発明が解決しようとする課題】
【０００４】
０または１からなる入力の数値が暗号化された状態のまま、当該数値の加算および排他的論理和の結果（の暗号化）を求めることができれば、当該数値の論理（ＯＲ）および論理積（ＡＮＤ）の結果（の暗号文）を求めることができる。すなわち、理論的には、入力の数値が暗号化された状態のまま多くの関数を計算できることになる。これを秘匿論理計算と呼ぶことにする。
【０００５】
既存の秘匿論理計算方式においては、入出力が暗号化されるのみで、演算の内容そのものは公開の下で実施されることが想定される。一方、演算の内容を非公開のまま演算を実施することは、デジタル権利管理モジュールや暗号モジュールなどの実装においては重要な課題である。
【０００６】
本発明は、関数を解析不能な形で提供し、関数への入力値を知ることなく、演算内容を秘匿したまま演算を実施して出力結果の取得を可能とすることで、任意の論理ゲートを実現する秘匿論理計算方法およびシステム、並びにプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
二つの数値ｘ，ｙの演算ｘ＊ｙとして、ｙ＝０の場合はｘ＊ｙ＝ｘ、ｙ＝１の場合はｘ＊ｙ＝１−ｘと定義する。そして、論理ゲートを、
ｆａ，ｂ，ｃ，ｄ（ｘ，ｙ）＝ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ）
の２次形式の関数で表現する（ａ，ｂ，ｃ，ｄはパラメータ）。
この２次形式によって表現された関数について、非特許文献２に記載されているような秘匿回路計算方式を複数回組み合わせ、入出力値および演算内容を秘匿したまま演算を行う。関数はａ，ｂ，ｃ，ｄを適切に調整することで任意の論理ゲートが実現できるので、ゲートの種類と入出力の両方を秘匿したまま任意の論理ゲートを実現できる。
【発明の効果】
【０００８】
本発明により、関数への入力値を知ることなく、演算内容を秘匿したまま演算を実施して出力結果を取得でき、ゲートの種類と入出力の両方を秘匿したまま任意の論理ゲートを実現できる。
【発明を実施するための最良の形態】
【０００９】
以下、本発明の実施の形態について詳細に説明する。  
Ｅを積と和の演算について準同型性を持つ公開鍵暗号の暗号化関数とする。すなわち、平文ｘ，ｙについて
Ｅ（ｘ）＋Ｅ（ｙ）＝Ｅ（ｘ＋ｙ）
Ｅ（ｘ）Ｅ（ｙ）＝Ｅ（ｘｙ）
が成り立つ。ここでは、Ｅを加法的準同型性を持つ公開鍵暗号の暗号化関数とする。
【００１０】
いま、Ｅについて、暗号文Ｅ（ｘ），Ｅ（ｙ）から、何らかの２次式Ｅ（ｘ＊ｙ）を計算する手段が与えられているとする。「＊」としては、排他的論理和演算を次のように拡張した演算を行うものと定義する。  
ｙ＝０の場合  ：  ｘ＊ｙ＝ｘ
ｙ＝１の場合  ：  ｘ＊ｙ＝１−ｘ
【００１１】
ここで、次のように、パラメータａ，ｂ，ｃ，ｄを持つ２次形式の関数を考える。
ｆａ，ｂ，ｃ，ｄ（ｘ，ｙ）＝ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ）      （１）
この２次形式によって表現された関数は、ａ，ｂ，ｃ，ｄの値を適切に調整することで任意の論理ゲート機能を実現できる。
【００１２】
本発明では、上記２次形式によって表現される関数について、加法的準同型性を持つ公開鍵暗号の暗号化関数Ｅを適用して、入出力と演算内容を秘匿したまま演算を行うことで、出力結果を取得する。これにより、任意の論理ゲートを、当該ゲートの種類と入出力の両方を秘匿したまま計算することが可能となる。
【００１３】
図１は本発明による秘匿論理計算装置の概念図である。ここで、Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）は、それぞれａ，ｂ，ｃ，ｄ，ｘ，ｙの暗号文である。秘匿論理計算装置１０は、暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）を入力として、Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ））を計算し、その計算結果を秘匿のまま出力する。当該Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ））の計算は、例えば、非特許文献２に記載されている秘匿回路計算方式を用い、これを複数回繰り返し適用して行う。ただし、かならず非特許文献２に記載の方式である必要はない。
【００１４】
該秘匿論理計算装置１０によれば、演算内容を秘匿したまま２次形式関数の演算を実施することができ、しかも、ａ，ｂ，ｃ，ｄの値を適切に調整することで、任意の論理ゲートが実現でき、同時にゲートの種類を秘匿できる。
【００１５】
図２は秘匿論理計算装置１０の一実施例としての処理フローを示したものである。ここで、暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）は、あらかじめ暗号文生成装置等により生成されているとする。秘匿論理計算装置１０は、該暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）を入力し（ステップ１１）、非特許文献２に記載の秘匿回路計算方式、その他の任意の秘密計算方式を適用して、まず、Ｅ（ｂ）とＥ（ｘ）からＥ（ｂ＊ｘ）を計算し（ステップ１２）、また、Ｅ（ｃ）とＥ（ｙ）からＥ（ｃ＊ｙ）を計算する（ステップ１３）。次に、Ｅ（ｘ）とＥ（ｙ）からＥ（ｘ＊ｙ）を計算し、Ｅ（ｄ）と該Ｅ（ｘ＊ｙ）とからＥ（ｄ＊（ｘ＊ｙ））を計算する（ステップ１４）。計算の途中結果は記憶装置等に保持しておく。最後に、Ｅ（ａ），Ｅ（ｂ＊ｘ），Ｅ（ｃ＊ｙ），Ｅ（ｄ＊（ｘ＊ｙ））の全てを足し合わせ（ステップ１５）、計算結果Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ））を出力する（ステップ１６）。なお、ステップ１２，１３，１４は順不同である。また、ステップ１４では、Ｅ（ｄ）とＥ（ｘ）からＥ（ｄ＊ｘ）を計算し、、該Ｅ（ｄ＊ｘ）とＥ（ｙ）からＥ（ｄ＊ｘ＊ｙ）を計算しても、結果は同じである。
【００１６】
図３は秘匿論理計算装置１０の他の実施例としての機能ブロック図を示したものである。ここで、２１〜２４は、一般にＥ（Ａ），Ｅ（Ｘ）を入力としてＥ（Ａ＊Ｘ）を計算する秘匿計算手段で、基本的にＥ（Ａ＊Ｘ）を計算できればどのような構成のものでもよい。２５は単純な加算手段である。
【００１７】
図２の場合と同様に、暗号文Ｅ（ａ），Ｅ（ｂ），Ｅ（ｃ），Ｅ（ｄ），Ｅ（ｘ），Ｅ（ｙ）は、あらかじめ暗号文生成装置等により生成されているとする。秘匿計算手段２１はＥ（ｂ）とＥ（ｘ）を入力してＥ（ｂ＊ｘ）を出力する。同様に、秘匿計算手段２２はＥ（ｃ）とＥ（ｙ）を入力してＥ（ｃ＊ｙ）を出力する。秘匿計算手段２３はＥ（ｘ）とＥ（ｙ）を入力してＥ（ｘ＊ｙ）を出力し、秘匿計算手段２４は、Ｅ（ｄ）と秘匿計算手段２３の出力Ｅ（ｘ＊ｙ）を入力してＥ（ｄ＊（ｘ＊ｙ））を出力する。加算手段２５は、秘匿計算手段２１の出力Ｅ（ｂ＊ｘ）、秘匿計算手段２２の出力Ｅ（ｃ＊ｙ）、秘匿計算手段２４の出力Ｅ（ｄ＊（ｘ＊ｙ））、及びＥ（ａ）を入力して、これらをすべて足し合わせ、Ｅ（ａ＋ｂ＊ｘ＋ｃ＊ｙ＋ｄ＊（ｘ＊ｙ））を出力する。
【００１８】
なお、図３において、秘匿計算手段２１〜２４は基本的に同じ構成でよい。したがって、制御手段等の制御下で、一つの秘匿計算手段にて秘匿計算手段２１〜２４の演算を繰り返し実行するようにして、その演算結果をメモリ等に保持し、加算手段２５に与えることで、上記と同様の動作が可能である。また、秘匿計算手段２３，２４は、Ｅ（ｄ）とＥ（ｘ）を入力してＥ（ｄ＊ｘ）を計算する秘匿計算手段、及び、このＥ（ｄ＊ｘ）とＥ（ｙ）を入力してＥ（ｄ＊ｘ＊ｙ）を計算する秘匿計算手段に置き換えても、計算結果は同じである。
【００１９】
次に、二、三の具体例を示す。ここでは、一例としてＡＮＤ，ＯＲ，ＸＯＲ（排他ＯＲ）の論理ゲートを実現するとする。図４（ａ）〜（ｃ）に、ＡＮＤ，ＯＲ，ＸＯＲの各論理ゲートとパラメータａ，ｂ，ｃ，ｄの値との対応関係を示す。以下に、パラメータａ，ｂ，ｃ，ｄの値を図４（ａ）〜（ｃ）とすることにより、それぞれＡＮＤ，ＯＲ，ＸＯＲの論理ゲートが実現することを証明する。
【００２０】
［ＡＮＤゲート］
（１）式は、図４（ａ）のパラメータ値（ａ，ｂ，ｃ，ｄ）＝（−５×４-1，４-1，４-1，３×４-1）を代入すると、式（２）のように表わされる。  
ｆAND(ｘ，ｙ)＝−５×４-1＋４-1＊ｘ＋４-1＊ｙ＋３×４-1＊(ｘ＊ｙ)  （２）
（ｉ）ｘ＝０，ｙ＝０の場合
先の「＊」の演算の定義により、右辺第２項は４-1＊ｘ＝４-1＊０＝４-1、同様に右辺第３項も、４-1＊ｙ＝４-1＊０＝４-1である。右辺第４項は、ｘ＊ｙ＝０＊０＝０で、３×４-1＊（ｘ＊ｙ）＝３×４-1＊０＝３×４-1である。この右辺第４項は、３×４-1＊ｘ＝３×４-1＊０＝３×４-1、３×４-1＊ｙ＝３×４-1＊０＝３×４-1と計算しても、結果は同じである。したがって、
ｆAND（０，０）＝−５×４-1＋４-1＋４-1＋３×４-1＝０
（ii）ｘ＝１，ｙ＝０の場合
右辺第２項は４-1＊ｘ＝４-1＊１＝１−４-1＝３×４-1である。右辺第３項は、４-1＊ｙ＝４-1＊０＝４-1である。右辺第４項は、ｘ＊ｙ＝１＊０＝１で、ｄ＊（ｘ＊ｙ）＝３×４-1＊１＝１−３×４-1＝４-1である。この右辺第４項は、３×４-1＊ｘ＝３×４-1＊１＝１−３×４-1＝４-1、４-1＊ｙ＝４-1＊０＝４-1でも、結果は同じである。したがって、
ｆAND（１，０）＝−５×４-1＋３×４-1＋４-1＋４-1＝０
（iii）ｘ＝０，ｙ＝１の場合
右辺第２項は４-1＊ｘ＝４-1＊０＝４-1である。右辺第３項は４-1＊ｙ＝４-1＊１＝１−４-1＝３×４-1である。右辺第４項は、ｘ＊ｙ＝０＊１＝１−０＝１で、ｄ＊（ｘ＊ｙ）＝３×４-1＊１＝１−３×４-1＝４-1である。この右辺第４項は、３×４-1＊ｘ＝３×４-1＊０＝３×４-1、３×４-1＊ｙ＝３×４-1＊１＝１−３×４-1＝４-1でも、結果は同じである。したがって、
ｆAND（０，１）＝−５×４-1＋４-1＋３×４-1＋４-1＝０
（iv）ｘ＝１，ｙ＝１の場合
右辺第２項は４-1＊ｘ＝４-1＊１＝１−４-1＝３×４-1、同様に右辺第３項も、４-1＊ｙ＝４-1＊１＝３×４-1である。右辺第４項は、ｘ＊ｙ＝１＊１＝１−１＝０で、ｄ＊（ｘ＊ｙ）＝３×４-1＊０＝３×４-1である。この右辺第４項は、３×４-1＊ｘ＝３×４-1＊１＝１−３×４-1＝４-1、４-1＊ｙ＝４-1＊１＝１−４-1＝３×４-1でも、結果は同じである。したがって、
ｆAND（１，１）＝−５×４-1＋３×４-1＋３×４-1＋３×４-1＝１
【００２１】
［ＯＲゲート］
（１）式は、図４（ｂ）のパラメータ値（ａ，ｂ，ｃ，ｄ）＝（−３×４-1，４-1，４-1，４-1）を代入すると、次式（３）のように表わされる。
ｆOR（ｘ，ｙ）＝−３×４-1＋４-1＊ｘ＋４-1＊ｙ＋４-1＊（ｘ＊ｙ）  （３）
（ｉ）ｘ＝０，ｙ＝０の場合
右辺第２項は４-1＊ｘ＝４-1＊０＝４-1、同様に右辺第３項も、４-1＊ｙ＝４-1＊０＝４-1である。右辺第４項は、ｘ＊ｙ＝０＊０＝０で、ｄ＊（ｘ＊ｙ）＝４-1＊０＝４-1である。この右辺第４項は、４-1＊ｘ＝４-1＊０＝４-1、４-1＊ｙ＝４-1＊０＝４-1でも、結果は同じである。したがって、
ｆOR（０，０）＝−３×４-1＋４-1＋４-1＋４-1＝０
（ii）ｘ＝１，ｙ＝０の場合
右辺第２項は４-1＊ｘ＝４-1＊１＝１−４-1＝３×４-1である。右辺第３項は、４-1＊ｙ＝４-1＊０＝４-1である。右辺第４項は、ｘ＊ｙ＝１＊０＝１で、ｄ＊（ｘ＊ｙ）＝４-1＊１＝１−４-1＝３×４-1である。この右辺第４項は、４-1＊ｘ＝４-1＊１＝３×４-1、３×４-1＊ｙ＝３×４-1＊０＝３×４-1でも、結果は同じである。したがって、
ｆOR（１，０）＝−３×４-1＋３×４-1＋４-1＋３×４-1＝１
（iii）ｘ＝０，ｙ＝１の場合
右辺第２項は４-1＊ｘ＝４-1＊０＝４-1である。右辺第３項は４-1＊ｙ＝４-1＊１＝３×４-1である。右辺第４項は、ｘ＊ｙ＝０＊１＝１−０＝１、ｄ＊（ｘ＊ｙ）＝４-1＊１＝１−４-1＝３×４-1である。この右辺第４項は、４-1＊ｘ＝４-1＊０＝４-1、４-1＊ｙ＝４-1＊１＝１−４-1＝３×４-1でも、結果は同じである。したがって、
ｆOR（０，１）＝−３×４-1＋４-1＋３×４-1＋３×４-1＝１
（iv）ｘ＝１，ｙ＝１の場合
右辺第２項は４-1＊ｘ＝４-1＊１＝１−４-1＝３×４-1である。同様に右辺第３項も、４-1＊ｙ＝４-1＊１＝３×４-1である。右辺第４項は、ｘ＊ｙ＝１＊１＝０で、ｄ＊（ｘ＊ｙ）＝４-1＊０＝４-1である。この右辺第４項は、４-1＊ｘ＝４-1＊１＝３×４-1、３×４-1＊ｙ＝３×４-1＊１＝１−３×４-1＝４-1でも、結果は同じである。したがって、
ｆOR（１，１）＝−３×４-1＋３×４-1＋３×４-1＋４-1＝１
【００２２】
［ＸＯＲゲート］
（１）式は、図４（ｃ）のパラメータ値（ａ，ｂ，ｃ，ｄ）＝（−１，２-1，２-1，０）を代入すると、次式（４）のように表わされる。
ｆXOR（ｘ，ｙ）＝−１＋２-1＊ｘ＋２-1＊ｙ＋０＊ｘ＊ｙ      （４）
（ｉ）ｘ＝０，ｙ＝０の場合
右辺第２項は２-1＊ｘ＝２-1＊０＝２-1、同様に右辺第３項も、２-1＊ｙ＝２-1＊０＝２-1である。右辺第４項は、ｘ＊ｙ＝０＊０＝０で、ｄ＊（ｘ＊ｙ）＝０＊０＝０である。この右辺第４項は、０＊ｘ＝０＊０＝０、０＊ｙ＝０＊０＝０でも、結果は同じである。したがって、
ｆXOR（０，０）＝−１＋２-1＋２-1＋０＝０
（ii）ｘ＝１，ｙ＝０の場合
右辺第２項は２-1＊ｘ＝２-1＊１＝１−２-1＝２-1である。右辺第３項は、２-1＊ｙ＝２-1＊０＝２-1である。右辺第４項は、ｘ＊ｙ＝１＊０＝１で、ｄ＊（ｘ＊ｙ）＝０＊１＝１−０＝１である。この右辺第４項は、０＊ｘ＝０＊１＝１−０＝１、１＊ｙ＝１＊０＝１でも、結果は同じである。したがって、
ｆXOR（１，０）＝−１＋２-1＋２-1＋１＝１
（iii）ｘ＝０，ｙ＝１の場合
右辺第２項は２-1＊ｘ＝２-1＊０＝２-1である。右辺第３項は２-1＊ｙ＝２-1＊１＝２-1である。右辺第４項は、ｘ＊ｙ＝０＊１＝１−０＝１で、ｄ＊（ｘ＊ｙ）＝０＊１＝１−０＝１である。この右辺第４項は、０＊ｘ＝０＊０＝０、０＊ｙ＝０＊１＝１−０＝１でも、結果は同じである。したがって、
ｆXOR（０，ｙ）＝−１＋２-1＋２-1＋１＝１
（iv）ｘ＝１，ｙ＝１の場合
右辺第２項は２-1＊ｘ＝２-1＊１＝２-1である。同様に右辺第３項も、２-1＊ｙ＝２-1＊１＝２-1である。右辺第４項は、ｘ＊ｙ＝１＊１＝１−１＝０で、ｄ＊（ｘ＊ｙ）＝０＊０＝０である。この右辺第４項は、０＊ｘ＝０＊１＝１−０＝１、１＊ｙ＝１＊１＝１−１＝０でも、結果は同じである。したがって、
ｆXOR（１，１）＝−１＋２-1＋２-1＋０＝０
【００２３】
以上、一例として、ＡＮＤ，ＯＲ，ＸＯＲの論理ゲートの場合を示したが、同様にして、（１）式におけるａ，ｂ，ｃ，ｄの値を調整すれば、任意の論理ゲートを実現できる。そして、本発明によれば、入出力を暗号化したまま、同時に論理ゲートの種類、内容を秘匿して、計算を実行することができる。
【００２４】
なお、図３などで示した装置における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２などで示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００２５】
【図１】本発明による秘匿論理計算装置の概念図。
【図２】本発明の一実施例の処理フロー図。
【図３】本発明のほかの実施例の機能ブロック図。
【図４】論理ゲートとパラメータ値の対応関係の一例を示す図。
【符号の説明】
【００２６】
１０  秘匿論理計算装置
２１〜２４  秘匿計算手段
２５  加算手段
【図１】
2006301310.tif 000003
【図２】
2006301310.tif 000004
【図３】
2006301310.tif 000005
【図４】
2006301310.tif 000006