(57)【特許請求の範囲】
【請求項１】
サービス提供者装置は透かし埋め込み関数を保持し、顧客装置はコンテンツ及び透かし情報を保持し、前記サービス提供者装置は前記透かし埋め込み関数を前記顧客装置に対して秘匿し、前記顧客装置は前記コンテンツ及び透かし情報のいずれか一方あるいは両方を前記サービス提供者装置に秘匿して、前記サービス提供者装置及び前記顧客装置が対話的に透かし埋め込み関数を実行し、透かし入りコンテンツを前記顧客装置で取得する透かし埋め込み処理方法であって、
前記顧客装置はコンテンツＣ及び透かし情報Ｉを保持し、前記サービス提供者装置は透かし埋め込み関数Ａ（・，・）を保持し、Ａ（・，・）はＣ，Ｉを入力とし、ＣにＩを埋め込んだ透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を出力する関数とし、Ａ（・，・）に含まれる秘密情報の集合をＳとし、
前記サービス提供者装置は、事前処理として、
（ａ）Ａ（・，・）を計算するために必要な手続きを、Ｓに非依存のもの（該当する手続きの集合をＰ＝｛Ｐ1，Ｐ2，…｝とする）、Ｓに依存、Ｃに非依存のもの（該当する手続きの集合をＱ＝｛Ｑｌ，Ｑ2，…｝とする）、Ｓ，Ｃともに依存するもの（該当する手続きの集合をＴ＝｛Ｔｌ，Ｔ2，…｝とする）に分類する（ここで、Ｐi，Ｑi，Ｔi（ｉ＝１，２，・・・）の手続きの単位は任意とする）、
（ｂ）各Ｔiについて、Ｔiの入出力をそれぞれＩi，Ｏiとした時、Ｉi，ＯiからＳの情報を有意に得ることが困難であり、かつＯiがＳに非依存であるとみなせばＰに属するような手続きＴjが存在する時、ＴjをＴからＰに変更する、
（ｃ）各Ｔiについて、Ｔiの入出力をそれぞれＩi，Ｏiとした時、Ｉi，ＯiからＣの情報を有意に得ることが困難であり、かつＯiがＣに非依存であれるとみなせばＱ（またはＰ）に属するような手続きＴjが存在する時、ＴjをＴからＱ（またはＰ）に変更する、
の処理を実行し、
以後、前記顧客装置及び前記サービス提供者装置の間で、
前記顧客装置は、透かし情報Ｉを前記サービス提供者装置に送信することで透かし埋め込みの依頼をかけ、
前記サービス提供者装置は、手続きＰを前記顧客装置に送信し、
前記顧客装置はＰiの入力Ｉiを得たときＰiを実行し、出力Ｏiを得、ＯiがＱまたはＴの要素の入力であればサービス提供者装置にＯiを送信し、
前記サービス提供者装置はＱjの入力Ｉjを得たときＱjを実行し、出力Ｏjを得、ＯjがＰまたはＴの要素の入力、または何れの入力でもない場合（＝最終出力）であれば、前記顧客装置にＯjを送信し、
前記顧客装置及び前記サービス提供者装置はＴkの入力Ｉkを得たとき２パーティプロトコルを実行し、その出力Ｏkが、Ｐの要素の入力または何れの入力でもない場合であれば顧客装置に出力されるようにし、Ｑの要素の入力であれば前記サービス提供者装置に出力されるようにし、Ｔの要素の入力であれば双方に出力されるようにして、
最終的に、前記顧客装置が透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を得ることを特徴とする透かし埋め込み処理方法。
【請求項２】
請求項１記載の透かし埋め込み処理方法において、
２パーティプロトコルとして、サービス提供者装置及び顧客装置が保持する秘密のビット列｛ai｝i＝１，・・・，ｍ及び｛bi｝i＝１，・・・，ｎについて、サービス提供者装置はai＝ci＋di  mod２となるようなci，diをランダムに生成して｛di｝i＝１，・・・，ｍを顧客装置に送信し、同様に顧客装置はbi＝ei＋fi  mod２となるようなei，fiをランダムに生成して｛fi｝i＝１，・・・，ｎをサービス提供者装置に送信し、1-out-of-４紛失通信を用いて、｛ai｝を顧客装置が知ることなく、かつ｛bi｝をサービス提供者装置が知ることなく、｛ai｝，｛bi｝を入力とした、透かし埋め込みに関する関数を計算することを特徴とする透かし埋め込み処理方法。
【請求項３】
透かし埋め込み関数を保持するサービス提供者装置と、コンテンツ及び透かし情報を保持する顧客装置とが通信路を介して接続され、前記サービス提供者装置は前記透かし埋め込み関数を前記顧客装置に対して秘匿し、前記顧客装置は前記コンテンツ及び透かし情報のいずれか一方あるいは両方を前記サービス提供者装置に秘匿して、前記サービス提供者装置及び前記顧客装置が対話的に透かし埋め込み関数を実行し、透かし入りコンテンツを前記顧客装置で取得する透かし埋め込み処理システムであって、
前記顧客装置はコンテンツＣ及び透かし情報Ｉを保持し、前記サービス提供者装置は透かし埋め込み関数Ａ（・，・）を保持し、Ａ（・，・）はＣ，Ｉを入力とし、ＣにＩを埋め込んだ透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を出力する関数とし、Ａ（・，・）に含まれる秘密情報の集合をＳとし、
前記サービス提供者装置は、事前処理として、
（ａ）Ａ（・，・）を計算するために必要な手続きを、Ｓに非依存のもの（該当する手続きの集合をＰ＝｛Ｐ1，Ｐ2，…｝とする）、Ｓに依存、Ｃに非依存のもの（該当する手続きの集合をＱ＝｛Ｑｌ，Ｑ2，…｝とする）、Ｓ，Ｃともに依存するもの（該当する手続きの集合をＴ＝｛Ｔｌ，Ｔ2，…｝とする）に分類する（ここで、Ｐi，Ｑi，Ｔi（ｉ＝１，２，・・・）の手続きの単位は任意とする）、
（ｂ）各Ｔiについて、Ｔiの入出力をそれぞれＩi，Ｏiとした時、Ｉi，ＯiからＳの情報を有意に得ることが困難であり、かつＯiがＳに非依存であるとみなせばＰに属するような手続きＴjが存在する時、ＴjをＴからＰに変更する、
（ｃ）各Ｔiについて、Ｔiの入出力をそれぞれＩi，Ｏiとした時、Ｉi，ＯiからＣの情報を有意に得ることが困難であり、かつＯiがＣに非依存であれるとみなせばＱ（またはＰ）に属するような手続きＴjが存在する時、ＴjをＴからＱ（またはＰ）に変更する、
の処理を実行し、
以後、前記顧客装置及び前記サービス提供者装置の間で、
前記顧客装置は、透かし情報Ｉを前記サービス提供者装置に送信することで透かし埋め込みの依頼をかけ、
前記サービス提供者装置は、手続きＰを前記顧客装置に送信し、
前記顧客装置はＰiの入力Ｉiを得たときＰiを実行し、出力Ｏiを得、ＯiがＱまたはＴの要素の入力であればサービス提供者装置にＯiを送信し、
前記サービス提供者装置はＱjの入力Ｉjを得たときＱjを実行し、出力Ｏjを得、ＯjがＰまたはＴの要素の入力、または何れの入力でもない場合（＝最終出力）であれば、前記顧客装置にＯjを送信し、
前記顧客装置及び前記サービス提供者装置はＴkの入力Ｉkを得たとき２パーティプロトコルを実行し、その出力Ｏkが、Ｐの要素の入力または何れの入力でもない場合であれば顧客装置に出力されるようにし、Ｑの要素の入力であれば前記サービス提供者装置に出力されるようにし、Ｔの要素の入力であれば双方に出力されるようにして、
最終的に、前記顧客装置が透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を得ることを特徴とする透かし埋め込み処理システム。
【請求項４】
請求項３記載の透かし埋め込み処理システムにおいて、
２パーティプロトコルとして、サービス提供者装置及び顧客装置が保持する秘密のビット列｛ai｝i＝１，・・・，ｍ及び｛bi｝i＝１，・・・，ｎについて、サービス提供者装置はai＝ci＋di  mod２となるようなci，diをランダムに生成して｛di｝i＝１，・・・，ｍを顧客装置に送信し、同様に顧客装置はbi＝ei＋fi  mod２となるようなei，fiをランダムに生成して｛fi｝i＝１，・・・，ｎをサービス提供者装置に送信し、1-out-of-４紛失通信を用いて、｛ai｝を顧客装置が知ることなく、かつ｛bi｝をサービス提供者装置が知ることなく、｛ai｝，｛bi｝を入力とした、透かし埋め込みに関する関数を計算することを特徴とする透かし埋め込み処理システム。
【請求項５】
請求項３もしくは４に記載の透かし埋め込み処理システムで用いられるサービス提供者装置。
【請求項６】
請求項３もしくは４に記載の透かし埋め込み処理システムで用いられる顧客装置。
【請求項７】
請求項３もしくは４に記載の透かし埋め込み処理システムで用いられるサービス提供者装置の処理機能をコンピュータに実行させるためのプログラム。
【請求項８】
請求項３もしくは４に記載の透かし埋め込み処理システムで用いられる顧客装置の処理機能をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティの技術分野に関し、特に暗号技術を応用し、透かしアルゴリズムやコンテンツ、透かし情報などを秘匿したまま透かし埋め込みを可能とする技術に関する。
【背景技術】
【０００２】
電子透かしは、透かしアルゴリズムや透かし埋め込み時に必要な鍵情報を知られると、透かしの改ざんや消去といった攻撃を受ける危険性がある。そのため、従来は透かしアルゴリズムを独自開発した機関（センタ；サービス提供者）が透かし埋め込み／検証プログラムを保持し、透かし埋め込み／検出依頼者（クライアント；顧客）に代わって実行するものが多い。しかしながら、コンテンツなどを秘匿したまま透かし埋め込みを可能とする技術は提案されていないのが現状である。
【０００３】
従来、目的が類似する技術としては、暗号化された透かし入りコンテンツを復号することなく透かしの検出を可能とするものがある（例えば、非特許文献１）。これはセンタ依頼型（透かし埋め込みの演算ロジック等の秘密情報を保持するセンタが、クライアントに代わって透かしの埋め込みや検出を行う方式）によるパッチワークを用いた透かし方式に対して、準同型暗号と呼ばれる暗号方式を用いて透かし入りコンテンツを暗号化したまま当該コンテンツに対して演算を施し、更にゼロ知識証明技術を用いて処理正当性を証明することで、透かし入りコンテンツをセンタに対して秘匿したまま透かしの検出を可能としている。
【０００４】
【非特許文献１】古川  潤：“安全な識別データ検出方法”，暗号と情報セキュリティシンポジウム（SCIS2002）予稿集，pp．769−774，2002．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
電子透かしの用途として、例えば、企業等において電子化された社内秘情報に対して、印刷する際に印刷実行者の識別子を透かし情報としてハードコピーに埋め込むようにし、当該ハードコピーまたはそのコピーが外部に漏洩した際には、当該印刷実行者を透かし検出により特定して責任の所在を明らかにするといった用途が挙げられる。
【０００６】
このような透かし埋め込みをサービスとして提供する事を考えると、その実現には次の２つの形態が考えられる。
（ｉ）サービス提供者は顧客から現コンテンツを受け取り、透かし埋め込みを行った後、透かし入りコンテンツを顧客に返す。
（ii）サービス提供者は顧客に透かし埋め込み機能を販売し、顧客が透かし埋め込みを行えるようにする。
【０００７】
顧客にとっては、透かし埋め込みを行うコンテンツ毎に埋め込み処理を依頼することになる（ｉ）よりも（ii）が望ましいと思われるが、これらの方法に対して、それぞれ次のような問題がある。
【０００８】
（ｉ）のサービス提供者に透かし埋め込みを依頼する場合には、顧客はサービス提供者に透かし情報を埋め込みたいコンテンツを渡す事になり、サービス提供者からの情報漏洩の恐れがある。つまり、サービス提供者に透かし埋め込みを依頼する形態においては、サービス提供者に対するコンテンツ秘匿が課題となる。
【０００９】
（ii）の透かし埋め込みを顧客自身が行う場合には、顧客に悪意があれば、購入した透かし埋め込みアルゴリズム（プログラム）を解析して演算ロジックや秘密鍵等の秘密情報を不正に取得し透かしの改ざんや除去といった問題が生じる。つまり透かし埋め込み機能を顧客に渡す形態においては、その安全性保持が課題となる。
【００１０】
本発明は、暗号技術を利用して、顧客には透かし埋め込みアルゴリズムなどを知られずに、かつ、サービス提供者にはコンテンツなどを知られずに、顧客は透かし入りコンテンツを得ることができる透かし埋め込み処理方法、透かし埋め込み処理システム、サービス提供者装置および顧客装置、並びにそのためのプログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明の基本原理を説明する。顧客装置はコンテンツＣ及び透かし情報Ｉを保持し、サービス提供者装置は透かし埋め込み関数Ａ（・，・）を保持しているものとする。ここでＡ（・，・）は、Ｃ，Ｉを入力とし、ＣにＩを埋め込んだ透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を出力する関数とする。
【００１２】
サービス提供者装置と顧客装置は協力して２パーティプロトコルを実行し、顧客装置に当該実行結果Ｃ′が出力されるようにして、サービス提供者装置はＣ，Ｃ′などを知ることなく顧客装置にＣ′を提供し、顧客装置はＡ（・，・）を知ることなくＣ′を得るようにする。
【００１３】
ここで、２パーティプロトコルとして文献「Ａ．Ｃ.Ｙao，“Ｐrotocols  for  secure  computations，”Ｉn  Ｐroc．of  the  23rd  IEEEＳymp．on  Ｆoundations  of  Ｃomputer  Ｓcience（ＦＯＣＳ′82），pp．160−164，IEEEＰress，1982．」で提案されている方法（以下、Ｙao方式と呼ぶ）を用いるとする。Ｙao方式は、ある与えられた計算回路に対して、“Ｇarbled  Ｃircuit”と呼ばれる、当該回路の素子（ＡＮＤ，ＯＲ等）情報を秘匿（暗号化）したまま実行可能なものに変換することを特徴とする。従って、サービス提供者装置がＹao方式を用いてＡ（・，・）をＧarbled  Ｃircuitに変換（暗号化）してやれば、顧客装置はＡ（・，・）のロジックを知ることなく、Ａ（・，・）と等しい結果が得られる処理を実行できるようになる。即ち、Ａ（・，・）を知ることなくＣ′を求めることができる。
【００１４】
１．サービス提供者装置は、事前処理として、Ｙao方式によってＡ（・，・）をＧarbled  Ｃircuitに変換する。これをＢ（・，・）とする。ここで、Ｂ（・，・）は、Ｃ，Ｉを入力してもＣ′を得ることができないが、下記のＣ~，Ｉを入力すると、Ｃ′を出力する関数とする。すなわち、Ａ（・，・）とＢ（・，・）は以下の関係にあるとする。
【００１５】
【数１】
0004618684.tif 000002
２．顧客装置は、サービス提供者装置に透かし埋め込みの依頼をかける。
３．サービス提供者装置１００は、Ｂ（・，・）を顧客装置に送信する。
４．顧客装置とサービス提供者装置は、Ｙao方式のコア技術である“Ｏblivious  Ｔransfer”を対話的に実行し、顧客装置は、サービス提供者装置にＣを知られることなく、Ｃの符号Ｃ~を得る。
５．顧客装置は、Ｂ（・，・）にＣ~，Ｉを入力してＢ（Ｃ~，Ｉ）を実行し、その実行結果Ｃ′（＝Ａ（Ｃ，Ｉ））を得る。
【００１６】
以上により、サービス提供者装置はＣ，Ｃ′を知ることなく顧客装置にＣ′を提供し、サービス提供者装置はＡ（・，・）を知ることなくＣ′を得ることができる。
なお、Ａ（・，・）とＢ（・，・）との関係は、次のようにすることも可能である。
【００１７】
【数２】
0004618684.tif 000003
このようにして、サービス提供者装置は、Ｃ′，ＩあるいはＣとＩを知ることなく、顧客装置にＣ′を提供することができる。
【発明の効果】
【００１８】
本発明によれば、センタ依頼型の電子透かし処理システムにおいて、デジタルコンテンツをセンタに対して秘匿したまま透かしの埋め込みを行うことができる。また透かし埋め込み関数Ａ（・，・）は特定されないため、本発明は汎用性が高いと言える。従って本発明は、従来では電子透かし処理を外部機関に依頼する際に生じていたコンテンツの漏洩リスクを回避するための有効な手段に成り得る。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の二、三の実施の形態について図面を用いて詳細に説明する。
［第１の実施の形態］
透かし埋め込み関数Ａ（・，・）全体をＧarbled  Ｃircuitに変換した場合、Ｇarbled  Ｃircuitは、計算回路における素子（ＡＮＤ，ＯＲ等）の実行回数に比例した規模の手続きが必要となるため、透かし埋め込み関数に適用する場合は全体の手続きが莫大になるものと予想される。そこで、本実施の形態では、透かし埋め込み関数の一部の手続きだけを２パーティプロトコルで実行するようにして、２パーティプロトコルの実行範囲を削減可能とする方法を提供するものである。
【００２０】
図１に本実施の形態のシステム構成を示す。図１において、サービス提供装置１００と顧客装置２００は通信路３００を介して接続され、顧客装置１００はコンテンツＣ及び透かし情報Ｉを保持し、サービス提供者装置１００は透かし埋め込み関数Ａ（・，・）を保持しているととする。
【００２１】
図２は本実施の形態の処理フローを示している。ここで、Ａ（・，・）は、Ｃ，Ｉを入力とし、ＣにＩを埋め込んだ透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を出力する関数とする。また、Ａ（・，・）に含まれる秘密情報の集合をＳとする。Ｓの要素としては、透かし埋め込みに必要な秘密鍵や、保護したい演算モジュール等が挙げられる。
１．サービス提供者装置１００は、事前処理として以下の処理を行う。
（ａ）Ａ（・，・）を計算するために必要な手続きを
・Ｓに非依存のもの（該当する手続きの集合をＰ＝｛Ｐ1，Ｐ2，…｝とする）
・Ｓに依存、Ｃに非依存のもの（該当する手続きの集合をＱ＝｛Ｑｌ，Ｑ2，…｝とする）
・Ｓ，Ｃともに依存するもの（該当する手続きの集合をＴ＝｛Ｔｌ，Ｔ2，…｝とする）
に分類する。ここで、Ｐi，Ｑi，Ｔi（ｉ＝１，２，・・・）の手続きの単位は任意とする。
（ｂ）各Ｔiについて、Ｔiの入出力をそれぞれＩi，Ｏiとした時、Ｉi，ＯiからＳの情報を有意に得ることが困難であり、かつＯiがＳに非依存であるとみなせばＰに属するような手続きＴjが存在する時、ＴjをＴからＰに変更する。
（ｃ）各Ｔiについて、Ｔiの入出力をそれぞれＩi，Ｏiとした時、Ｉi，ＯiからＣの情報を有意に得ることが困難であり、かつＯiがＣに非依存であれるとみなせばＱ（またはＰ）に属するような手続きＴjが存在する時、ＴjをＴからＱ（またはＰ）に変更する
【００２２】
以上の準備の下、以下の規則に従って顧客装置２００及びサービス提供者１００が対話的に実行することで、顧客装置２００は透かし入りコンテンツＣ′＝Ａ（Ｃ，Ｉ）を得る。
２．顧客装置２００は、透かし情報Ｉをサービス提供者装置１００に送信することで透かし埋め込みの依頼をかける。
３．サービス提供者装置１００は、手続きＰを顧客装置２００に送信する。
【００２３】
４．顧客装置２００はＰiの入力Ｉiを得たときＰiを実行し、出力Ｏiを得る。ＯiがＱまたはＴの要素の入力であればサービス提供者装置１００にＯiを送信する。
５．サービス提供者装置１００はＱjの入力Ｉjを得たときＱjを実行し、出力Ｏjを得る。ＯjがＰまたはＴの要素の入力、または何れの入力でもない場合（＝最終出力）であれば、顧客装置２００にＯjを送信する。
６．顧客装置２００及びサービス提供者装置１００はＴkの入力Ｉkを得たとき２パーティプロトコルを実行し、その出力Ｏkが、Ｐの要素の入力または何れの入力でもない場合であれば顧客装置２００に出力されるようにし、Ｑの要素の入力であればサービス提供者装置１００に出力されるようにし、Ｔの要素の入力であれば双方に出力されるようにする。
【００２４】
以下に、Ｔiを２パーティプロトコルで実行する具体的手続きについて、一例としてＹao方式とＧoldreich  et  al方式を用いる例を示す。なお、Ｇoldreich  et  al方式は文献「Ｏ．Ｇoldreich，Ｓ．Ｍicali，and  Ａ．Ｗigderson，“Ｈow  to  Ｐlay  Ａny  Ｍental  Ｇame，or  ａ  Ｃompletness  Ｔheorem  for  Ｐrotocols  with  Ｈonest  Ｍajority，“Ｐroc．of  ＳＴＯＣ，pp．218-229，1987．」に記載されている。
【００２５】
［ＴiをＹao方式の２パーティフロトコルで実行する例］
サービス提供者装置１００はＴiを、顧客装置２００はＴiの入力Ｉiをそれぞれ秘密に保持し、顧客装置２００がＴiの出力Ｏiを得る例について説明する。
先ずサービス撮供者装置１００はＴiを論理回路で表現した手続きに変更する。ここで具体例として、Ｔiは図３で示すような単純な論理回路処理と等価であるとする。即ち、ｇ1（・，・），ｇ2（・，・），ｇ3（・，・）をそれぞれ２ビット入力の論理積、論理和、排他的論理和を示す論理式としたとき、Ｉi＝（b1，b2，ｂ3，ｂ4）（ｂiは１ビット値）、Ｏi＝ｇ3（ｇ1（b1，b2），ｇ2（ｂ3，ｂ4））が成り立つ。このとき、サービス提供者装置１００は以下を行う。
１．ｕ＝１，・・・，６，ｖ＝０，１について、ｋビットの乱数Ｗuvを生成する。ここで、ｋはセキュリティパラメータ（例えばｋ＝１６０が実用的な値となる）とする。
２．ｗ＝１，２，３について、｛０，１｝から｛０，１｝に写す置換関数πwを決定する。
３．以下の４データから成るテーブルＴable１を作成して適当な順序に並び替え、これをｇｌ（・，・）に割り当てる。
【００２６】
【数３】
0004618684.tif 000004
ここでＨは任意長のデータをｋ＋１ビットデータに写す一方向性ハッシュ関数、「‖」はデータの連結を表すものとする。
４．以下の４データから成るテーブルＴable２を作成して適当な順序に並び替え、これをｇ2（・，・）に割り当てる。
【００２７】
【数４】
0004618684.tif 000005
５．以下の４データから成るテーブルＴable３を作成して適当な順序に並び替え、これをｇ3（・，・）に割り当てる。
【００２８】
【数５】
0004618684.tif 000006
６．Ｔable１，２，３を顧客装置２００に送信する。
【００２９】
次にサービス提供者装置１００と顧客装置２００は１-out-of-２紛失通信（Ｏblivions  Ｔransfer）を対話的に実行し、顧客装置２００はb1，b2，ｂ3，ｂ4にそれぞれ対応する（Ｗ1b1，π1（b1）），（Ｗ2b2，π1（b2）），（Ｗ3b3，π2（b3）），（Ｗ4b4，π2（b4））を得る。
ここで１-out-of-２紛失通信の特徴として、b1，b2，ｂ3，ｂ4はサービス提供者装置１００に知られずに済み、かつ（Ｗ11-b1，π1（１−b1）），（Ｗ21-b2，π1（１−b2）），（Ｗ31-b3，π2（１−b3）），（Ｗ41-b4，π2（１−b4））は顧客装置に知られずに済む。以下で具体例として文献「Ｓ．Ｅveｎ，Ｏ．Ｇoldreich，and  Ａ．Ｌempel,“Ａ  randomized  protocol  for  conracts，”Ｃommunication  of  the  ＡＣＭ，No．28，Vol．6，pp．637-647，1985．」の１-out-of-２紛失通信を用いて（Ｗ1b1，π1（b1））を得る手続きを説明する。
１．サービス提供者装置１００は公開鍵暗号の秘密鍵、公開鍵の組（Ｓ，Ｐ）を決定し、Ｎビットの乱数ｒ0，ｒ1を生成し、（Ｐ，ｒ0，ｒ1）を顧客装置２００に送信する。ここでＮはセキュリティパラメータとする。
２．顧客装置２００はｎビットの乱数ｘを生成する。ここでｎはセキュリティパラメータとする。
３．顧客装置２００はＰを用いてｘの暗号文Ｅnc（ｘ）を計算し、ｑ＝Ｅnc（ｘ）＋ｒb1  modＮをサービス提供者装置１００に送信する。
４．サービス提供者装置１００はＳを用いてｑ−ｒ0及びｑ−ｒ1を復号し、復号結果ｙ0，ｙ1を得る。
５．サービス提供者装置１００はｃ0＝（Ｗ10，π1（0））＋ｙ0  modｎ，ｃ0＝（Ｗ11，π1（1））＋ｙ1  modｎを計算し、（ｃ0，ｃ1）を顧客装置２００に送信する。
６．顧客装置２００は（Ｗ1b1，π1（ｂ1））を得る。
【００３０】
（Ｗ1b1，π1（b1）），（Ｗ2b2，π1（b2）），（Ｗ3b3，π2（b3）），（Ｗ4b4，π2（b4））を得た顧客装置は、最終的に以下を行うことでＯiを得る事ができる。
【００３１】
【数６】
0004618684.tif 000007
【００３２】
［ＴiをＧoldreich  et  al．方式の２パーティプロトコルで実行する例］
サービス提供者装置１００、顧客装置２００はＴiの入力Ｉi，Ｉi′をそれぞれ秘密に保持し、各装置がＴiの出力Ｏiの断片ｚ1，ｚ2を得る例について説明する。ここで、断片ｚ1，ｚ2はＯi＝ｚ1＋ｚ2を満たす値とし、各装置は何れか一方の断片のみ得る事ができる。
先ずサービス提供者装置１００はＴiを否定と論理積の組み合わせによって構成れる論理回路で表現した手続きに変更する。ここで具体例として、Ｔiは図４で示すような単純な論理回路処理と等価であるとする。即ち、ｇ1（・，・），ｇ2（・，・），ｇ3（・，・）を２ビット入力の論理積、ｇ4（・）を否定（ビット反転）を示す論理式としたとき、Ｉi＝（ｂ1，ｂ3），Ｉi′＝（ｂ2，ｂ4）（ｂ1は１ビット値），Ｏi＝ｇ3（ｇ1（（ｂ1，ｂ2），ｇ4（ｇ2（（ｂ3，ｂ4））が成り立つ。
【００３３】
次に以下の手順でｇ1（ｂ1，ｂ2）＝ｂ1ｂ2の断片ｃ3，ｄ3を計算する。
１．サービス提供者装置１００は以下を行う。
（ａ）乱数ビットｄ1を生成して顧客装置２００に送信する。
（ｂ）ｃ1＝ｂ1＋ｄ1  mod２を計算する。
２．顧客装置２００は以下を行う。
（ａ）乱数ビットｃ2，ｅを生成してサービス提供者装置１００に送信する。
（ｂ）ｄ2＝ｂ2＋ｃ2  mod２を計算する。
（ｃ）ｘ0＝ｅ，ｘ1＝ｄ2＋ｅ  mod２を計算する。
３．サービス提供者装置１００は顧客装置２００と１-out-of-２紛失通信を行い、ｘc1を得て、ｃ3＝ｃ1ｃ2＋ｘc1＋ｃ1ｄ2  mod２を計算する。
４．顧客装置２００はｄ3＝ｄ1ｄ2＋ｅ  mod２を計算する。
これにより、サービス提供者装置１００、顧客装置２００はそれぞれｃ3，ｄ3を取得し、ｂ1ｂ2＝ｃ3＋ｄ3  mod２が成り立つことから、サービス提供者装置１００及び顧客装置２００はｂ1ｂ2の断片を得た事になる。
【００３４】
次に上記と同様の操作で、ｇ2（（ｂ3，ｂ4）＝ｂ3ｂ4の断片ｃ3，ｄ3を計算する。これによりサービス提供者装置１００、顧客装置２００はそれぞれｃ4，ｄ4を得る。
次にｇ4（ｇ2（ｂ3，ｂ4）の断片ｃ5，ｄ5を計算する。これは単純に何れかの装置が自身の保持する断片をビット反転すれば良い。ここではサービス提供者装置１００がビット反転するものとする。即ち、サービス提供者装置１００はｇ4（ｇ2（ｂ3，ｂ4）の断片ｃ5＝ｃ4＋１  mod２を得る。顧客装置２００は値を変更せずｇ4（ｇ2（ｂ3，ｂ4）の断片ｄ5＝ｄ4とする。
【００３５】
最後に以下の手順でＯi＝ｇ3（ｇ1（ｂ1，ｂ2），ｇ4（ｇ2（ｂ3，ｂ4）））の断片ｚ1，ｚ2を計算する。
１．顧客装置２００は乱数ビットｅを生成し、ｘ0,0＝ｅ，ｘ0,1＝ｄ3＋ｅ  mod２，ｘ1,0＝ｄ4＋ｅ  mod２，ｘ1,1＝ｄ3＋ｄ4＋ｅ  mod２とする。
２．サービス提供者装置１００は顧客装置２００と１-out-of-２紛失通信を行い、ｘc3,c4を得て、ｚ1＝ｃ3ｄ4＋ｘc3,c4  mod２を計算する。
３．顧客装置２００はｚ2＝ｄ3ｄ4＋ｅ  mod２を計算する。
するとｚ1＋ｚ2＝（ｃ3ｄ3）（ｃ4ｄ4）＝ｇ3（ｇ1（ｂ1，ｂ2），ｇ4（ｇ2（ｂ3，ｂ4）））が成り立つため、Ｏiの断片をサービス手提供者装置１００、顧客装置２００が得た事がわかる。
なお、Ｏiを断片ではなく、例えば顧客装置２００が得る場合は、単純にサービス提供者装置１００がｚｌを顧客装置２００に送信すればよい。
【００３６】
［第２の実施の形態］
次に第２の実施の形態として、２パーティプロトコルとして文献「Ｒ.Ｃramer，Ｉ.Ｄamgard，and  Ｊ.Ｂ.Ｎielsen，“Ｍultiparty  computation  from  threshold  homomorphic  encryption，”Ｂasic  Ｒesearch  in  Ｃomputer  Ｓcience（BRICS）RS−00−14，Jun．2000．」で提案されている方法（以下、ＣＤＮ方式と呼ぶ）を用いた例について説明する。
【００３７】
ここで、ＣＤＮ方式について簡単に説明する。ＣＤＮ方式は、ある加法準同型性を持つ暗号関数Ｅnc（・）に対して、ａ，ｂ∈Ｍの暗号文Ｅnc（ａ），Ｅnc（ｂ）を入力として、ａ，ｂを知らず、かつＥnc（ａ），Ｅnc（ｂ）を復号せずａ，ｂの積を暗号化したＥnc（ａｂ）を計算する技術（以降、当該技術をＭＵＬＴプロトコルと呼ぶ）である。なお、加法準同型性を持つ暗号関数とは、簡単に言えば、ａ，ｂ∈Ｍの暗号文Ｅnc（ｃ），Ｅnc（ｂ）を入力として、ある既知の演算子“★”に対して、Ｅnc（ａ＋ｂ）＝Ｅnc（ａ）★Ｅnc（ｂ）が成り立つような暗号関数である。いま、Ｍはメッセージ空間となる可換環とする。するとａ，ｂ∈｛０，１｝に対して、Ｅnc（ａ），Ｅnc（ａ＋ｂ），Ｅnc（ａｂ）を計算できることを利用して、ＡＮＤ，ＯＲ等の素子について入力を暗号化したまま実行し、実行結果の暗号文を得ることができる。即ち、様々な計算回路について、入力を暗号化したまま実行できる。
【００３８】
また、ＣＤＮ方式で与えられている暗号関数Ｅnc（・）は以下の性質を持つ。
［性質１］  ａ∈Ｍの暗号文Ｅnc（ａ）、及びｃ∈Ｍを入力として、Ｅnc（ａ-1），Ｅnc（ａ＋c），Ｅnc（ａｃ）が計算できる。
［性質２］  一定数以上のパーティが協力した時に限り（本実施例に限って言えば、顧客装置，サービス提供者装置が協力した時に限り）復号できる（Ｅnc-1（・）を計算できる）。
【００３９】
図５に本実施の形態におけるシステム構成を示す。ここで、サービス提供者装置１００と顧客装置２００が通信路３００を介して接続され、サービス提供者装置１００は透かし埋め込み関数Ａ（・，・）を保持し、顧客装置２００はコンテンツＣ及び透かし情報Ｉを保持すると共に、さらに、各装置１００，２００は、公開鍵生成に必要な関数ｆE（・）とｇE（・，・），ｆR（・）とｇR（・，・）をそれぞれ保持するものとする。
【００４０】
初めに、本実施の形態における、Ｅnc（・）を計算するために必要な公開鍵ＰＫ、及びＥnc-1（・）を計算するために必要な秘密鍵ＳＫ＝｛ＳＫR，ＳＫE｝を生成する手順について、図６を用いて説明する。
１．顧客装置２００，サービス提供者装置１００は、それぞれＳＫR∈Ｋ，ＳＫE∈Ｋをランダムに生成し、自身で保持する。ここでＫは事前に指定された鍵空間を表す。
２．顧客装置２００，サービス提供者装置１００は、それぞれｆR（ＳＫR），ｆE（ＳＫE）を計算し、相手装置に送信する。
３．顧客装置２００，サービス提供者装置１００は、公開鍵ＰＫ＝ｇR（ｆE（ＳＫE），ＳＫR）＝ｇE（ｆR（ＳＫR），ＳＫE）を計算する。
【００４１】
なお、ここでＥnc-1（・）は、ＳＫR，ＳＫEを用いた時に限り実行できる。即ち、復号結果Ｙ＝Ｅnc-1（Ｘ）に対して、Ｙ＝λR（λE（Ｘ，ＳＫE），ＳＫR）＝μE（μR（Ｘ，ＳＫR），ＳＫE）を満たすような関数λR（・，・），λE（・，・），μR（・，・），μE（・，・）が存在し、かつ（λR（・，・），μR（・，・）），（λE（・，・），μE（・，・））はそれぞれ顧客装置２００，サービス提供者装置１００が保持している。
【００４２】
次に以上の準備の下、ＣＤＮ方式を用いて、サービス提供者装置１００はＣ，Ｃ′を知ることなく顧客装置２００にＣ′を提供し、顧客装置２００はＡ（・，・）を知ることなくＣ′を得るための処理について、図７、図８を用いて説明する。なお、図８でＲは顧客装置２００、Ｅはサービス提供者装置１００を表す。
１．サービス提供者装置１００は、事前処理として以下を行う。
（ａ）Ａ（・，・）を計算するために必要な手続きを
・Ｓに非依存のもの（該当する手続きの集合をＰ＝｛Ｐ1，Ｐ2，…｝とする）
・Ｓに依存、Ｃに非依存のもの（該当する手続きの集合をＱ＝｛Ｑ1，Ｑ2，…｝とする）
・Ｓ，Ｃともに依存するもので、加法準同型性及び［性質１］により入力を暗号化したまま計算できるもの（該当する手続きの集合をＴ＝｛Ｔ1，Ｔ2，…｝とする）
・上記以外のもの（該当する手続きの集合をＵ＝｛Ｕ1，Ｕ2，…｝とする）
に分類する。
（ｂ）手続きＵi（ｉ＝１，２，…）を計算回路に表現を変換し、変換後の手続きをＵiに置き換える。
【００４３】
２．顧客装置２００は、Ｉをサービス提供者装置１００に送信することで透かし埋め込みの依頼をかける。
３．サービス提供者装置１００は、Ｐ，Ｔを顧客装置２００に送信する。
【００４４】
４．顧客装置２００，サービス提供者装置１００は以下に基づいた処理を実行する（図８）。
（４−１）  手続きＰiは、顧客装置２００が実行する。
（４−２），（４−３）  手続きＱi，Ｔiは、サービス提供者装置１００が実行する。そして、実行結果がＣ′の部分情報であれば、当該実行結果を顧客装置２００に送信する）。
（４−４）  手続きＴiの出力が暗号文（これをＥnc（ａi）（ａi∈Ｍ）とする）であり、かつａiの暗号文をＵiの入力として用いる必要がある時、２パーティプロトコルによりａiの有意な情報を漏らすことなくＥnc（ａi）をＥnc（ｂｊ）（ｊ＝０，１，２，…）に変換する（ここでｂｊ∈｛０，１｝，ａi＝Σk=0２kｂk）。
（４−５）  手続きＵiは、以下のように実行する。
（ａ）サービス提供者装置１００は、Ｓに依存する入力をビット毎にＰＫを用いて暗号化する。
（ｂ）顧客装置２００は、Ｃに依存する入力をビット毎にＰＫを用いて暗号化する。
（ｃ）顧客装置２００，サービス提供者装置１００は、加法準同型性、［性質１］を用いると共に、ＭＵＬＴプロトコルを対話的に実行し、Ｕiの出力の暗号文（これをＥnc（ｚj）（ｊ＝１，２，…）とする）を得る。
【００４５】
５．顧客装置２００，サービス提供者装置１００は、以下の手順により顧客装置２００が所持する暗号文Ｅnc（ａi）（及びＥnc（ｚi））を復号し、顧客装置２００は当該復号結果を元にＣ′を得る。
（５−１）  サービス提供者装置１００はａi′＝λE（Ｅnc（ａi），ＳＫE）を計算し、ａi′を顧客装置２００に送信する。
（５−２）  顧客装置２００は、ａi″＝λR（ａi′，ＳＫR）を計算する。
【００４６】
本実施の形態でも、先の第１の実施の形態と同様の効果が期待できる。また顧客装置２００，サービス提供者装置１００が対話的に実行する手続きが第１の実施の形態のそれと一般に異なるため、第１の実施の形態よりも処理時間が短縮される可能性がある。
【００４７】
［第３の実施の形態］
本実施の形態は、本出願人が特願２００５−１２８８４、特願２００５−１６１６１などで提案した秘密計算方法を利用するものである。これは、関数への入力値を知ることなく、当該関数の計算及び出力結果（排他的論理和）の取得を可能とするもので、以下に概要を説明する。
【００４８】
Ｇをある有限体上で定義された楕円曲線の有理点からなる群とし、ＰをＧの元とする。Ｐの位数をｐとする。そして、秘密鍵ｘ∈｛１,…,ｐ｝に対してＱ＝ｘＰとし、（Ｇ,ｐ,Ｐ,Ｑ）を公開鍵とする。
【００４９】
平文ａ∈｛０,１｝を暗号化する暗号関数Ｅを次のように定義する。
Ｅ（ａ,ｒ）＝（Ａ,Ｂ）＝（ｒＰ,（ｒ＋ａ）Ｑ）
ここでｒは１以上ｐ以下の乱数である。
【００５０】
復号処理はｘＡを計算すれば良く、これにより
【００５１】
【数７】
0004618684.tif 000008
が成り立つことから、秘密鍵ｘを用いることで容易にＥ（ａ,ｒ）を復号できる。するとａ,ｂ∈｛０,１｝の暗号文Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａ＋ｂの暗号文を求めることは容易である。すなわち、Ｅ（ａ,ｒ）＋Ｅ（ｂ,ｓ）＝（（ｒ＋ｓ）Ｐ,（ｒ＋ａ＋ｓ＋ｂ）Ｑ）が成り立つことから、この操作によりａ＋ｂの暗号文Ｅ（ａ＋ｂ,ｒ＋ｓ）＝Ｅ（ａ,ｒ）＋Ｅ（ｂ,ｓ）が得られる。
【００５２】
Ｅ（ａ,ｒ）,Ｅ（ｂ,ｓ）からａとｂの排他的論理和の暗号文は、以下のようにして求める。ここで、ｂ，ｂ∈｛０，１｝の暗号文Ｅ（ａ，ｒ）（＝（Ａ，Ｂ），Ｅ（ｂ，ｓ）（＝（Ｘ，Ｙ）は制御装置へ事前に与えられているとする。
【００５３】
先ず、暗号文変換装置が制御装置より（Ｇ,ｐ,Ｐ,Ｑ）,Ｅ（ａ,ｒ）（＝（Ａ,Ｂ））を入力として以下の処理を行う。
１．ランダムビットｅおよび１以上ｐ以下の乱数ｔを生成する。
２．以下に従って（Ａ′,Ｂ′）を求め、それを複数の復号装置に送信する。
【００５４】
【数８】
0004618684.tif 000009
【００５５】
次に、複数の復号装置が（Ａ′,Ｂ′）入力として分散復号を行い、制御装置に送信することで、制御装置は（Ａ′,Ｂ′）の復号結果ｃを得る（このときｃ＝ａ＋ｅ（排他的論理和）が成り立つ）。
【００５６】
制御装置は、当該復号結果ｃ∈｛０,１｝について以下の処理を行う。
１.１以上ｐ以下の乱数ｗを生成する。
２．以下に従って（Ｃ,Ｄ）を求め、当該暗号文を暗号文変換装置に送信する。
【００５７】
【数９】
0004618684.tif 000010
このとき（Ｃ，Ｄ）の復号結果はａ＋ｂ＋ｅ（排他的論理和）となる。
【００５８】
暗号文変換装置は（Ｇ,ｐ,Ｐ,Ｑ）,（Ｃ,Ｄ）を入力として、以下の処理を行う。
１．１以上ｐ以下の乱数ｕを生成する。
２．以下に従って（Ｃ′,Ｄ′）を求め、それを制御装置に送信する。
【００５９】
【数１０】
0004618684.tif 000011
【００６０】
（Ｃ′,Ｄ′）の復号結果ｃ′は、ｃ′＝ａ＋ｂ（排他的論理和）が成り立つことから、上記の操作により制御装置はａ＋ｂ（排他的論理和）の暗号文、すなわち（Ｃ′,Ｄ′）を得ることができる。
【００６１】
図９に本実施の形態のシステム構成を示す。サービス提供者装置１００は透かしパタン生成アルゴリズムを構成する論理関数（透かしパタン生成関数）、透かしパタン重畳アルゴリズムを構成する論理関数（透かしパタン重畳関数）、透かし鍵、サービス提供者装置１００に固有の秘密鍵１を保持し、顧客装置２００は透かし情報、顧客装置２００固有の秘密鍵２、原画像を保持している。サービス提供者装置１００と顧客装置２００は互いにデータ等の送受信を行い、最終的に顧客装置２００は透かし入り画像を取得するが、サービス提供者装置１００では透かし情報や原画像を復号することができず、一方、顧客装置２００では透かしパタン生成関数や透かしパタン重畳関数、透かし鍵を復号することができない。
【００６２】
図１０乃至図１２に本実施の形態の処理フローを示す。ここで、サービス提供者装置１００は秘密透かし発行器と復号器１を備え、顧客装置２００は透かし埋込器と復号器２を備えるとする。以下の説明では、簡単に秘密透かし発行器すなわちサービス提供者装置１００、透かし埋込器すなわち顧客装置２００とする。
【００６３】
初めに、本実施の形態で用いられる公開鍵の生成処理について説明する（図１０）。
１．サービス提供者装置１００（秘密透かし発行器）は、有限体および楕円曲線を生成するためのパラメータが与えられるなどして有限体および楕円曲線をそれぞれ一つずつ決定し、更に当該有限体上で定義された当該楕円曲線の有理点からなる群Ｇを決定する。Ｇの元を一つ選び、これをＰとし、Ｐの位数ｐを計算する。そして、（Ｇ，ｐ，Ｐ）の組を復号器１、復号器２に送信する。
【００６４】
２．復号器１、復号器２ではそれぞれ以下の処理を行う。
（２−１）  復号器１は乱数（秘密鍵）αを生成し、Ｑ1＝αＰを計算して、Ｑ1をサービス提供者装置１００に送信する。
（２−２）  復号器２は乱数（秘密鍵）βを生成し、Ｑ2＝βＰを計算して、Ｑ2をサービス提供者装置１００に送信する。
【００６５】
３．サービス提供者装置１００は、Ｑ＝Ｑ1＋Ｑ2を計算する。そして、（Ｇ，ｐ，Ｐ，Ｑ）を公開する。
【００６６】
以上の準備の下、本出願人の提案した秘密計算方法を用いて、サービス提供者装置１００は透かしパタン生成アルゴリズム及び透かしパタン重畳アルゴリズムや透かし鍵を顧客装置２００に知られずに、また、顧客装置２００は透かし情報及び原画像をサービス提供者装置１００に知られずに、顧客装置２００にて透かし入画像を得るための処理手順を説明する。なお、透かし情報をＳ、原画像をＩ、透かし鍵をＫとする。
【００６７】
処理は透かしパタン生成処理の秘密計算化及び復号、透かしパタン重畳処理の秘密計算化及び復号に大別される。
【００６８】
図１１Ａ乃至図１１Ｄは透かしパタン生成処理の秘密計算及び復号の処理フローを示している。ここで、各装置は公開情報（Ｇ，ｐ，Ｐ，Ｑ）を保持しているとする。
１．サービス提供者装置１００は、透かしパタン生成アルゴリズムを構成する論理関数（透かしパタン生成関数）ｆx,y,z,w（ｋ，ｓ）、透かしパタン重畳アルゴリズムを構成する論理関数（透かしパタン重畳関数）ｈxx,yy,zz,ww（ｆ，ｉ）、透かし鍵Ｋを事前に生成して保持する。ここで、ｆx,y,z,w（ｋ，ｓ），ｈxx,yy,zz,ww（ｆ，ｉ）は以下のように表されるとする。
【００６９】
【数１１】
0004618684.tif 000012
【００７０】
【数１２】
0004618684.tif 000013
【００７１】
２．サービス提供者装置１００は、乱数ｒ１，ｒ２，ｒ３，ｒ４，ｒ５を生成し（ただし、１≦ｒ１，ｒ２，ｒ３，ｒ４，ｒ５≦ｐ），ｘ，ｙ，ｚ，ｗ，ｋを以下のように暗号化する。
Ｅ（ｘ）＝（Ｘ１，Ｘ２）＝（ｒ１・Ｐ，（ｒ１＋ｘ）・Ｑ）
Ｅ（ｙ）＝（Ｙ１，Ｙ２）＝（ｒ２・Ｐ，（ｒ２＋ｙ）・Ｑ）
Ｅ（ｚ）＝（Ｚ１，Ｚ２）＝（ｒ３・Ｐ，（ｒ３＋ｚ）・Ｑ）
Ｅ（ｗ）＝（Ｗ１，Ｗ２）＝（ｒ４・Ｐ，（ｒ４＋ｗ）・Ｑ）
Ｅ（ｋ）＝（Ｋ１，Ｋ２）＝（ｒ５・Ｐ，（ｒ５＋ｋ）・Ｑ）
そして、サービス提供者装置１００は、これら暗号文Ｅ（ｘ），Ｅ（ｙ），Ｅ（ｚ），Ｅ（ｗ），Ｅ（ｋ）を顧客装置２００に送信する。
【００７２】
３．顧客装置２００は透かし情報Ｓを入力する。
４．顧客装置２００は乱数ｒ6生成し（ただし、１≦ｒ6≦ｐ）、透かし情報Ｓを以下に従って暗号化する。
Ｅ（ｓ）＝（Ｓ1，Ｓ2）＝（ｒ6・Ｐ，（ｒ6＋ｓ）・Ｑ）
【００７３】
５．Ｅ（ｋ）＝（Ｋ1，Ｋ2）とＥ（ｘ）＝（Ｘ1，Ｘ2）により、ｆx，y，z，w（ｋ，ｓ）中のｋとｘの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ1，Ｄ1）とする。
【００７４】
（５−１）  顧客装置２００はランダムビットｅ及び乱数ｔ，ｕを生成し（ただし、１≦ｔ，ｕ≦ｐ）、以下に従って（Ｋ1′，Ｋ2′）、（Ｘ1′，Ｘ2′）を求める。
【００７５】
【数１３】
0004618684.tif 000014
【００７６】
【数１４】
0004618684.tif 000015
そして、顧客装置２００は、Ｋ1′を復号器１、復号器２に送信する。
【００７７】
（５−２）  復号器１はα・Ｋ1′を計算して顧客装置２００に送信する。
（５−３）  復号器２はβ・Ｋ1′を計算して顧客装置２００に送信する。
【００７８】
（５−４）  顧客装置２００はγ・Ｋ′＝α・Ｋ1′＋β・Ｋ1′を計算する。ここで、γ・Ｋ′＝Ｋ2′であれば、（Ｋ1′，Ｋ2′）の復号結果ｃを“０”、γ・Ｋ′＝Ｋ2′−Ｑであれば“１”とする。
【００７９】
その後、顧客装置２００は乱数ｗを生成し（ただし、１≦ｗ≦ｐ）、以下に従って（Ｃ1，Ｄ1）を計算する。
【００８０】
【数１５】
0004618684.tif 000016
【００８１】
ここで、（Ｃ1，Ｄ1）の復号結果ｃ′は
【００８２】
【数１６】
0004618684.tif 000017
が成り立つ。したがって、顧客装置２００はｋ，ｘを知ることなく、このｋ，ｘの排他的論理和の暗号文、すなわち（Ｃ1，Ｄ1）を得ることができる。
【００８３】
６．同様に、Ｅ（ｓ）＝（Ｋ1，Ｋ2）とＥ（ｙ）＝（Ｙ1，Ｙ2）により、ｆx，y，z，w（ｋ，ｓ）中のｓとｙの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ2，Ｄ2）とする。
【００８４】
７．同様に、Ｅ（ｋ）＝（Ｋ1，Ｋ2）とＥ（ｓ）＝（Ｓ1，Ｓ2）により、ｆx，y，z，w（ｋ，ｓ）中のｋとｓの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ3，Ｄ3）とする。
８．上記ステップ７で求めた（Ｃ3，Ｄ3）とＥ（ｚ）＝（Ｚ1，Ｚ2）により、ｆx，y，z，w（ｋ，ｓ）中のｋとｓとｚの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ4，Ｄ4）とする。
【００８５】
９．顧客装置２００は、（Ｃ1，Ｄ1），（Ｃ2，Ｄ2），（Ｃ4，Ｄ4）及びＥ（ｗ）＝（Ｗ1，Ｗ2）により、
（Ｍ，Ｎ）＝（Ｃ1，Ｄ1）＋（Ｃ2，Ｄ2）＋（Ｃ4，Ｄ4）＋（Ｗ1，Ｗ2）
を計算する。
すなわち、この（Ｍ，Ｎ）が秘密透かしパタン計算結果Ｅ（ｆx，y，z，w（ｋ，ｓ））であり、顧客装置２００は、ｋ，ｘ，ｙ，ｚ，ｗを知ることになく、また、ｓをサービス提供者装置１００に知られることなく、Ｅ（ｆx，y，z，w（ｋ，ｓ））＝（Ｍ，Ｎ）を得ることができる。
【００８６】
１０．顧客装置２００は、必要なら復号器１、２と協同してＥ（ｆx，y，z，w（ｋ，ｓ））の復号を以下に従って行う。
（１０−１）  顧客装置２００は、Ｍを復号器１及び復号器２に送信する。
（１０−２）  復号器１はα・Ｍを計算して顧客装置２００に送信する。
（１０−３）  復号器２はβ・Ｍを計算して顧客装置２００に送信する。
（１０−４）  顧客装置２００は、γ・Ｍ＝α・Ｍ＋β・Ｍとし、（ｆx，y，z，w（ｋ，ｓ））＝Ｎ−γ・Ｍを計算する。
【００８７】
図１２Ａ乃至図１２Ｄは透かしパタン重畳処理の秘密計算化及び復号の処理フローを示している。ここでも、各装置は公開鍵情報（Ｇ，ｐ，Ｐ，Ｑ）を保持しているとする。
１．サービス提供者装置１００は、乱数ｒ7，ｒ8，ｒ9，ｒ10を生成し（ただし、１≦ｒ7，ｒ8，ｒ9，ｒ10≦ｐ），ｘｘ，ｙｙ，ｚｚ，ｗｗを以下に従って暗号化する。
【００８８】
Ｅ（ｘｘ）＝（ＸＸ1，ＸＸ2）＝（ｒ7・Ｐ，（ｒ7＋ｘｘ）・Ｑ）
Ｅ（ｙｙ）＝（ＹＹ1，ＹＹ2）＝（ｒ8・Ｐ，（ｒ8＋ｙｙ）・Ｑ）
Ｅ（ｚｚ）＝（ＺＺ1，ＺＺ2）＝（ｒ9・Ｐ，（ｒ9＋ｚｚ）・Ｑ）
Ｅ（ｗｗ）＝（ＷＷ1，ＷＷ2）＝（ｒ10・Ｐ，（ｒ10＋ｗｗ）・Ｑ）
サービス提供者装置１００は、Ｅ（ｘｘ），Ｅ（ｙｙ），Ｅ（ｚｚ），Ｅ（ｗｗ）を顧客装置２００に送信する。
【００８９】
２．顧客装置２００は原画像Ｉを入力する。
３．顧客装置２００は乱数ｒ11を生成し（ただし、１≦ｒ11≦ｐ）原画像Ｉを以下に従って暗号化する。
Ｅ（ｉ）＝（Ｉ1，Ｉ2）＝（ｒ11・Ｐ，（ｒ11＋ｉ）・Ｑ）
【００９０】
４．秘密透かしパタン計算結果Ｅ（ｆx，y，z，w（ｋ，ｓ））＝（Ｍ，Ｎ）とＥ（ｘｘ）＝（ＸＸ1，ＸＸ2）により、ｈxx，yy，zz，ww（ｆ，ｉ）中のｆとｘｘの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ5，Ｄ5）とする。
【００９１】
（４−１）  顧客装置２００はランダムビットｅ及び乱数ｔ，ｕを生成し（ただし、１≦ｔ，ｕ≦ｐ）、以下に従って（Ｍ′，Ｎ′）、（ＸＸ1′，ＸＸ2′）を求める。
【００９２】
【数１７】
0004618684.tif 000018
【００９３】
【数１８】
0004618684.tif 000019
顧客装置２００はＭ′を復号器１、復号器２に送信する。
（４−２）  復号器１はα・Ｍ′を計算して、その計算結果を顧客装置２００に送信する。
（４−３）  復号器２はβ・Ｍ′を計算して、その計算結果を顧客装置２００に送信する。
（４−４）  顧客装置２００はγ・Ｍ′＝α・Ｍ′＋β・Ｍ′を計算する。ここで、γ・Ｍ′＝Ｎ′であれば、（Ｍ′，Ｎ′）の復号結果ｃを“０”、γ・Ｍ′＝Ｍ′−Ｑであれば“１”とする。
その後、顧客装置２００は乱数ｗを生成し（ただし、１≦ｗ≦ｐ）、以下に従って（Ｃ5，Ｄ5）を計算する。
【００９４】
【数１９】
0004618684.tif 000020
【００９５】
５．同様に、Ｅ（ｉ）＝（Ｉ1，Ｉ2）とＥ（ｙｙ）＝（ＹＹ1，ＹＹ2）により、ｈxx，yy，zz，ww（ｆ，ｉ）中のｉとｙｙの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ6，Ｄ6）とする。
【００９６】
６．同様に、Ｅ（ｆx，y，z，w（ｋ，ｓ））＝（Ｍ，Ｎ）とＥ（ｉ）＝（Ｉ1，Ｉ2）により、ｈxx，yy，zz，ww（ｆ，ｉ）中のｆとｉの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ7，Ｄ7）とする。
７．上記ステップ６で求めた（Ｃ7，Ｄ7）とＥ（ｚｚ）＝（ＺＺ1，ＺＺ2）により、ｈxx，yy，zz，ww（ｆ，ｉ）中のｆとｉとｚｚの排他的論理和の暗号文を求める。ここでは、その暗号文を（Ｃ8，Ｄ8）とする。
８．顧客装置２００は、（Ｃ5，Ｄ5），（Ｃ6，Ｄ6），（Ｃ8，Ｄ8）及びＥ（ｗｗ）＝（ＷＷ1，ＷＷ2）により、
（Ｍ1，Ｎ1）＝（Ｃ5，Ｄ5）＋（Ｃ6，Ｄ6）＋（Ｃ8，Ｄ8）＋（ＷＷ1，ＷＷ2）
を計算する。この（Ｍ1，Ｎ1）が秘密透かしパタン重畳計算結果Ｅ（ｆxx，yy，zz，ww（ｆ，ｉ））である。
【００９７】
以上により、顧客装置２００は、ｆ，ｘｘ，ｙｙ，ｚｚ，ｗｗを知ることになく、また、Ｉをサービス提供者装置１００に知られることなく、Ｅ（ｆxx，yy，zz，ww（ｆ，ｉ））＝（Ｍ1，Ｎ1）を得ることができる。
【００９８】
９．顧客装置２００は、必要なら復号器１、２と協同してＥ（ｆxx，yy，zz，ww（ｆ，ｉ））＝（Ｍ1，Ｎ1）の復号を以下に従って行う。
（９−１）  顧客装置２００は、Ｍ1を復号器１及び復号器２に送信する。
（９−２）  復号器１はα・Ｍ1を計算して顧客装置２００に送信する。
（９−３）  復号器２はβ・Ｍ1を計算して顧客装置２００に送信する。
（９−４）  顧客装置２００は、γ・Ｍ＝α・Ｍ1＋β・Ｍ1とし、ｈxx，yy，zz，ww（ｆ，ｉ）＝Ｎ1−γ・Ｍ1を計算して、透かし入り画像を得る。
【００９９】
以上、本発明の実施の形態を説明したが、本発明はこれらに限定されるものではなく、任意の暗号技術を用いることができる。また、サービス提供者装置は３台以上として処理を分散させることも可能であり、これによりセキュリティが更に向上する。
【０１００】
なお、実施形態における各装置の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、実施形態で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【０１０１】
【図１】本発明の第１の実施の形態のシステム構成例を示す図。
【図２】第１の実施の形態の透かし埋め込みの処理フロー図。
【図３】論理回路の具体例を示す図。
【図４】論理回路の他の具体例を示す図。
【図５】本発明の第２の実施の形態のシステム構成例を示す図。
【図６】第２の実施の形態の公開鍵生成の処理フロー図。
【図７】第２の実施の形態の透かし埋め込みの処理フロー図。
【図８】図７のステップ４の詳細な処理フロー図。
【図９】本発明の第３の実施の形態のシステム構成例を示す図。
【図１０】第３の実施の形態の公開鍵生成の処理フロー図。
【図１１Ａ】第３の実施の形態の透かしパタン生成秘密計算化における最初の処理フロー図。
【図１１Ｂ】図１１Ａの続きの処理フロー図。
【図１１Ｃ】図１１Ｂの続きの処理フロー図。
【図１１Ｄ】図１１Ｃの続きの処理フロー図。
【図１２Ａ】第３の実施の形態の透かしパタン重畳秘密計算化における最初の処理フロー図。
【図１２Ｂ】図１２Ａの続きの処理フロー図。
【図１２Ｃ】図１２Ｂの続きの処理フロー図。
【図１２Ｄ】図１２Ｃの続きの処理フロー図。
【符号の説明】
【０１０２】
１００  サービス提供者装置
２００  顧客装置
３００  通信路
【図１】
0004618684.tif 000021
【図２】
0004618684.tif 000022
【図３】
0004618684.tif 000023
【図４】
0004618684.tif 000024
【図５】
0004618684.tif 000025
【図６】
0004618684.tif 000026
【図７】
0004618684.tif 000027
【図８】
0004618684.tif 000028
【図９】
0004618684.tif 000029
【図１０】
0004618684.tif 000030
【図１１Ａ】
0004618684.tif 000031
【図１１Ｂ】
0004618684.tif 000032
【図１１Ｃ】
0004618684.tif 000033
【図１１Ｄ】
0004618684.tif 000034
【図１２Ａ】
0004618684.tif 000035
【図１２Ｂ】
0004618684.tif 000036
【図１２Ｃ】
0004618684.tif 000037
【図１２Ｄ】
0004618684.tif 000038