(57)【要約】  効率的な伝送システムを提供する。メッセージをｔ個以下の数の符号化されたメッセージからはメッセージに関する情報が得られず、２ｔ＋１個以上の符号語からはメッセージが復号できるような３ｔ＋１個以上のメッセージの符号語とｔ個以下の誤りがあっても、前記した複数のメッセージの符号語のうちｔ個以下の誤りを検出することができる複数の不正符号化メッセージ特定用データを生成、送信する送信装置１００と、受信したメッセージの符号語とそれらに対応する不正符号化メッセージ特定用データにたいしメッセージの符号語と、不正符号化メッセージ特定用データを用いて、メッセージの符号語のそれぞれに不正がないか判定し、不正がないと判定されたメッセージの符号語のすべてが同じメッセージの符号語であるかを判定し、すべてが同じメッセージの符号語であると判定できた場合、不正がないと判定されたメッセージの符号語からメッセージを復号、出力し、それ以外の場合はメッセージの受信失敗を表す出力を行う受信装置２００を備える。（図１）
2009020143.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを入力として、ｔ個以下の数の符号語からは、メッセージに関する情報が得られず、正しい２ｔ＋１個以上の符号語からは、メッセージが復号できるようなメッセージの符号語を生成するメッセージ符号化装置と、
前記メッセージの符号語を入力とし、前記符号語からメッセージを復元する際に、ｔ個以下の不正な符号語が含まれていた場合に不正な符号語を特定するための不正符号語特定データを生成する不正符号語特定データ生成装置と、
を備え、前記メッセージの符号語と前記不正符号語特定データを出力する、ことを特徴とする符号化装置。
【請求項２】
前記不正符号語特定データ生成装置は、前記不正符号語特定データのなかに、ｔ個以下の不正な不正符号語特定データが存在する場合に、不正な不正符号語特定データを訂正可能な不正符号語特定データを生成する、ことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記不正符号語特定データ生成装置は、ランダムな情報源をリードソロモン符号化した符号語を不正符号語特定データとして生成する、ことを特徴とする請求項２に記載の符号化装置。
【請求項４】
ユニバーサルハッシュ関数族を表すデータ集合からランダムなユニバーサルハッシュ関数を表すデータを選び、前記ユニバーサルハッシュ関数を表すデータを、ｔ個以下の不正な符号語があっても、不正な符号語を訂正可能であるように符号化する関数データ符号化装置をさらに備え、
前記不正符号語特定データ生成装置は、前記メッセージの符号語を、前記ユニバーサルハッシュ関数に入力して算出した結果を、不正符号語特定データとして出力し
、
前記メッセージの符号語と、前記ユニバーサルハッシュ関数を表すデータの符号語と、前記不正符号語特定データを出力し、
前記ユニバーサルハッシュ関数族として、前記関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる、ことを特徴とする請求項１乃至３のいずれか１項に記載の符号化装置。
【請求項５】
ユニバーサルハッシュ関数を表すデータを、リードソロモン符号化した符号語をユニバーサルハッシュ関数を表すデータの符号語として生成する関数データ符号化装置を備える、ことを特徴とする請求項４に記載の符号化装置。
【請求項６】
符号語と不正符号語特定用データとを入力とし、不正符号語特定データを用いて不正な符号語を特定する不正符号語特定装置と、
前記不正符号語特定装置で不正符号語と特定されなかった符号語の集合に対してそれらが同じメッセージに復号されるかどうかの同一性を判定し、同一性があると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、同一性がないと判定されなかった場合には復号失敗を表す出力を行うメッセージ復号装置と、
を備える、ことを特徴とする復号化装置。
【請求項７】
不正な不正符号語特定データを訂正する不正符号語特定データ訂正装置を備える、ことを特徴とする請求項６記載の復号化装置。
【請求項８】
不正な不正符号語特定データを、リードソロモン誤り訂正処理によって訂正する不正符号化メッセージ特定装置を備える、ことを特徴とする請求項７に記載の復号化装置。
【請求項９】
メッセージの符号語とユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データとを入力とし、不正なユニバーサルハッシュ関数の符号語を訂正し、ユニバーサルハッシュ関数を表すデータを復号化する関数データ復号装置をさらに備え、
前記不正符号語特定装置は、不正関数出力特定データを用いて、復号化したユニバーサルハッシュ関数にメッセージの符号語を入力した出力のなかから不正な符号語を特定し、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる、ことを特徴とする請求項６乃至８のいずれか１項に記載の復号化装置。
【請求項１０】
不正なユニバーサルハッシュ関数を表すデータの符号語を、リードソロモン誤り訂正処理によって、不正なユニバーサルハッシュ関数の符号語を訂正する関数データ復号装置を備える、ことを特徴とする請求項９に記載の復号化装置。
【請求項１１】
請求項１に記載の符号化装置と、
請求項６に記載の復号化装置と、
を備えたことを特徴とする伝送システム。
【請求項１２】
請求項２に記載の符号化装置と、
請求項７に記載の復号化装置と、
を備えたことを特徴とする伝送システム。
【請求項１３】
請求項３に記載の符号化装置と、
請求項８に記載の復号化装置と、
を備えたことを特徴とする伝送システム。
【請求項１４】
請求項４に記載の符号化装置と、
請求項９に記載の復号化装置と、
を備えたことを特徴とする伝送システム。
【請求項１５】
請求項５に記載の符号化装置と、
請求項１０に記載の復号化装置と、
を備えたことを特徴とする伝送システム。
【請求項１６】
メッセージを入力として、ｔ個以下の数の符号語からは、メッセージに関する情報が得られず、正しい２ｔ＋１個以上の符号語からは、メッセージが復号できるようなメッセージの符号語を生成するメッセージ符号化処理と、
前記メッセージの符号語を入力とし、前記符号語からメッセージを復元する際に、ｔ個以下の不正な符号語が含まれていた場合に不正な符号語を特定するための不正符号語特定データを生成する不正符号語特定データ生成処理と、
前記メッセージの符号語と前記不正符号語特定データを出力する処理と、
を符号化装置を構成するコンピュータに実行させる、ことを特徴とするプログラム。
【請求項１７】
前記不正符号語特定データ生成処理は、前記不正符号語特定データのなかに、ｔ個以下の不正な不正符号語特定データが存在する場合に、不正な不正符号語特定データを訂正可能な不正符号語特定データを生成する、ことを特徴とする請求項１６記載のプログラム。
【請求項１８】
前記不正符号語特定データ生成処理は、ランダムな情報源をリードソロモン符号化した符号語を不正符号語特定データとして生成する、ことを特徴とする請求項１７に記載のプログラム。
【請求項１９】
ユニバーサルハッシュ関数族を表すデータ集合からランダムなユニバーサルハッシュ関数を表すデータを選び、該ユニバーサルハッシュ関数を表すデータを、ｔ個以下の不正な符号語があっても、不正な符号語を訂正可能であるように符号化する関数データ符号化処理と、
メッセージの符号語を、前記ユニバーサルハッシュ関数に入力して算出した結果を、不正符号語特定データとして出力する前記不正符号語特定データ生成処理と、
メッセージの符号語と、ユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データを出力する処理と、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる処理と、
を前記コンピュータに実行させる、ことを特徴とする請求項１６乃至１８のいずれか１項に記載のプログラム。
【請求項２０】
ユニバーサルハッシュ関数を表すデータをリードソロモン符号化した符号語をユニバーサルハッシュ関数を表すデータの符号語として生成する関数データ符号化処理を前記コンピュータに実行させる、ことを特徴とする請求項１９に記載のプログラム。
【請求項２１】
符号語と不正符号語特定用データとを入力とし、不正符号語特定データを用いて不正な符号語を特定する不正符号語特定処理と、
前記不正符号語特定処理で不正符号語と特定されなかった符号語の集合に対してそれらが同じメッセージに復号されるかどうかの同一性を判定し、同一性があると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、同一性がないと判定されなかった場合には復号失敗を表す出力を行うメッセージ復号処理と、
を復号化装置を構成するコンピュータに実行させる、ことを特徴とするプログラム。
【請求項２２】
不正な不正符号語特定データを訂正する不正符号語特定データ訂正処理を前記復号化装置を構成するコンピュータに実行させる、ことを特徴とする請求項１９記載のプログラム。
【請求項２３】
不正な不正符号語特定データをリードソロモン誤り訂正処理によって訂正する不正符号化メッセージ特定処理を、前記復号化装置を構成するコンピュータに実行させることを特徴とする請求項２２記載のプログラム。
【請求項２４】
メッセージの符号語とユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データとを入力とし、不正なユニバーサルハッシュ関数の符号語を訂正し、ユニバーサルハッシュ関数を表すデータを復号化する関数データ復号処理と、
不正関数出力特定データを用いて、復号化したユニバーサルハッシュ関数にメッセージの符号語を入力した出力のなかから不正な符号語を特定する前記不正符号語特定処理と、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる処理と、
を前記コンピュータに実行させる、ことを特徴とする請求項２１乃至２３のいずれか１項に記載のプログラム。
【請求項２５】
不正なユニバーサルハッシュ関数を表すデータの符号語をリードソロモン誤り訂正処理によって、不正なユニバーサルハッシュ関数の符号語を訂正する関数データ復号処理と、
を復号化装置を構成するコンピュータに実行させる、ことを特徴とする請求項２４記載のプログラム。
【請求項２６】
メッセージを入力として、ｔ個以下の数の符号語からは、メッセージに関する情報が得られず、正しい２ｔ＋１個以上の符号語からは、メッセージが復号できるようなメッセージの符号語を生成するメッセージ符号化工程と、
前記メッセージの符号語を入力とし、前記符号語からメッセージを復元する際に、ｔ個以下の不正な符号語が含まれていた場合に不正な符号語を特定するための不正符号語特定データを生成する不正符号語特定データ生成工程と、
を有し、
前記メッセージの符号語と前記不正符号語特定データを出力する、ことを特徴とする符号化方法。
【請求項２７】
前記不正符号語特定データ生成工程は、前記不正符号語特定データのなかに、ｔ個以下の不正な不正符号語特定データが存在する場合に、不正な不正符号語特定データを訂正可能な不正符号語特定データを生成する、ことを特徴とする請求項２６に記載の符号化方法。
【請求項２８】
前記不正符号語特定データ生成工程は、ランダムな情報源をリードソロモン符号化した符号語を不正符号語特定データとして生成する、ことを特徴とする請求項２７に記載の符号化方法。
【請求項２９】
ユニバーサルハッシュ関数族を表すデータ集合からランダムなユニバーサルハッシュ関数を表すデータを選び、該ユニバーサルハッシュ関数を表すデータを、ｔ個以下の不正な符号語があっても、不正な符号語を訂正可能であるように符号化する関数データ符号化工程と、
メッセージの符号語を、前記ユニバーサルハッシュ関数に入力して算出した結果を、不正符号語特定データとして出力する前記不正符号語特定データ生成工程と、
メッセージの符号語と、ユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データを出力する工程と、
を含み、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる、ことを特徴とする請求項２６乃至２８のいずれか１項に記載の符号化方法。
【請求項３０】
ユニバーサルハッシュ関数を表すデータをリードソロモン符号化した符号語をユニバーサルハッシュ関数を表すデータの符号語として生成する関数データ符号化工程を含む、ことを特徴とする請求項２９に記載の符号化方法。
【請求項３１】
符号語と不正符号語特定用データとを入力とし、不正符号語特定データを用いて不正な符号語を特定する不正符号語特定工程と、
前記不正符号語特定装置で不正符号語と特定されなかった符号語の集合に対してそれらが同じメッセージに復号されるかどうかの同一性を判定し、同一性があると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、同一性がないと判定されなかった場合には復号失敗を表す出力を行うメッセージ復号工程と、
を含む、ことを特徴とする復号化方法。
【請求項３２】
不正な不正符号語特定データを訂正する不正符号語特定データ訂正工程を含む、ことを特徴とする請求項３１に記載の復号化方法。
【請求項３３】
不正な不正符号語特定データをリードソロモン誤り訂正処理によって訂正する不正符号化メッセージ特定工程を含む、ことを特徴とする請求項３１に記載の復号化方法。
【請求項３４】
メッセージの符号語とユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データとを入力とし、不正なユニバーサルハッシュ関数の符号語を訂正し、ユニバーサルハッシュ関数を表すデータを復号化する関数データ復号工程と、
不正関数出力特定データを用いて、復号化したユニバーサルハッシュ関数にメッセージの符号語を入力した出力のなかから不正な符号語を特定する前記不正符号語特定工程と、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる工程と、
を含む、ことを特徴とする請求項３１乃至３３のいずれか１項に記載の復号化方法。
【請求項３５】
不正なユニバーサルハッシュ関数を表すデータの符号語をリードソロモン誤り訂正処理によって、不正なユニバーサルハッシュ関数の符号語を訂正する関数データ復号装置を備えることを特徴とする請求項３４に記載の復号化方法。
【請求項３６】
情報をｃ個の分散情報に符号化し、そのうち任意のａ個以上の分散情報からは秘密情報が完全に復元できるが、ａ−ｂ−１個までの分散情報からでは秘密情報に関する情報は全く得られないという（ａ，ｂ，ｃ）しきい値法を用い、
想定不正チャンネル数をｔとし、
チャンネル数ｎ＝３ｔ＋ｄ＋１（ｄ≧０）
を満たす数のチャンネルで受信装置と接続する送信装置であって、
ｄ’を、ｄ≧ｄ’≧０であるような値として、
メッセージを（２ｔ＋ｄ’＋１，ｄ’＋ｔ，ｎ）しきい値法（上記（ａ，ｂ，ｃ）しきい値法のａを２ｔ＋ｄ’＋１、ｂをｄ’＋ｔ、ｃをｎとする）を用いて、ｎ個の符号化メッセージ情報Ｖｉ（但し、ｉ＝１，・・・，ｎ）を生成する手段と、
前記ｎ個の符号化メッセージ情報Ｖｉとｔ次多項式とを用いて、ｎ個の符号化メッセージ情報Ｖｉのうちｔ個以下のものに誤りがある場合にリード・ソロモン誤り訂正処理による誤りの検出および訂正を可能とする不正チャンネル特定情報ＡｉをＶｉ（但し、ｉ＝１，・・・，ｎ）に対応付けて生成し、対応するチャンネルからＶｉとＡｉ（但し、ｉ＝１，・・・，ｎ）を送信する手段と、
を備えている、ことを特徴とする送信装置。
【請求項３７】
メッセージのデータ集合に有限体ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）を用い（但し、ｐは素数の冪乗であり、素数そのものである場合もある）、
ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）の要素であるメッセージｓをＧＦ（ｐ）によって、（ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝）と表し、
ＧＦ（ｐ）上の定数項からｄ’＋ｔ次の項までの係数が、それぞれ、ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝である２ｔ＋ｄ’次多項式を、ランダムに生成し、２ｔ＋ｄ’次多項式をｆｓ（ｘ）として、ｆｓ（１），ｆｓ（２），．．，ｆｓ（ｎ）をそれぞれ計算し、
計算結果と入力ｉとのペアＶｉ＝（ｉ，ｖｉ）  （但し、ｉ＝１，2，．．，ｎ、ｖｉ＝ｆｓ（ｉ））を、符号化メッセージ情報としてそれぞれのチャンネルに出力する、ことを特徴とする請求項３６記載の送信装置。
【請求項３８】
請求項３６又は３７記載の前記送信装置で生成された符号化メッセージ情報Ｖｉと不正チャンネル特定情報Ａｉ（但し、ｉ＝１，・・・，ｎ）をそれぞれチャンネルを介して受信し、ＶｉとＡｉ（但し、ｉ＝１，・・・，ｎ）を用いてリード・ソロモン誤り訂正処理を行って、ｎ個のＶｉそれぞれについて不正な値であるか否かを判断する手段と、
不正であると判断されなかったＶｉがすべて同じメッセージの符号語であるかを調べ、同じメッセージの符号語である場合には、前記メッセージを出力し、異なるメッセージの符号語が含まれている場合には、メッセージの受信失敗を表す記号を出力する手段と、
を備えている、ことを特徴とする受信装置。
【請求項３９】
メッセージｓ、チャンネル数ｎ、想定不正チャンネル数ｔが入力されると、ＧＦ（ｐ＾Ｎ）上の定数項からｄ’＋ｔ次の項までの係数がそれぞれ、ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝である２ｔ＋ｄ’次多項式をランダムに生成し、２ｔ＋ｄ’次多項式をｆｓ（ｘ）として、ｆｓ（１），ｆｓ（２），．．，ｆｓ（ｎ）を計算し、計算結果ｆｓ（ｉ）と入力ｉとのペアＶｉ＝（ｉ，ｖｉ）  （但し、ｉ＝１，・・・，ｎ，ｖｉ＝ｆｓ（ｉ））を符号化メッセージ情報（但し、符号化メッセージ情報ｖｉは、ＧＦ（ｐ）の要素によって（ｖ｛ｉ，０｝，・・・，ｖ｛ｉ，Ｎ−１｝）と表せる）として生成するメッセージ符号化手段と、
チャンネル数ｎおよび想定不正チャンネル数ｔ、Ｖｉ＝（ｉ，ｖ｛ｉ，０｝，・・・，ｖ｛ｉ，Ｎ−１｝）（但し、ｉ＝１，・・・，ｎ）を入力し、ＧＦ（ｐ）上でランダムにｅを選択し、ＧＦ（ｐ）上で、
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝  （但し、ｉ＝１，・・・，ｎ）
を計算し、ｑ≧ｎ＊ｐとなるｑに対し、ＧＦ（ｑ）上で、
ｘｉ＝ｐ＊（ｉ−１）＋ｙｉ  （但し、ｉ＝１，・・・，ｎ）
を計算する符号化メッセージ情報変換手段と、
ＧＦ（ｑ）上のランダムなデータｅ０，ｅ１，・・・，ｅｔを生成するリード・ソロモン情報源生成手段と、
ｘｉ（但し、ｉ＝１，・・・，ｎ）とｅ０，ｅ１，・・・，ｅｔとから、ＧＦ（ｑ）上で、
Ｃｓ（ｘｉ）＝ｅ０＋ｅ１＊ｘｉ＋ｅ２＊ｘｉ＾２＋・・・＋ｅｔ＊ｘｉ＾ｔ  （但し、ｉ＝１，・・・，ｎ）
を計算する第１のリード・ソロモン符号語生成手段と、
ＧＦ（ｐ）上のランダムなデータｒ１，・・・，ｒｔを選択する第２の情報源生成手段と、
ｅとｒ１，・・・，ｒｔとを取得し、ＧＦ（ｑ）上で、
Ｃｅ（ｘｉ）＝ｅ＋ｒ１＊ｉ＋ｒ２＊ｉ＾２＋・・・＋ｒｔ＊ｉ＾ｔ  （但し、ｉ＝１，・・・，ｎ）を計算する第２のリード・ソロモン符号語生成手段と、
を備え、
Ｃｓ（ｘｉ）と、Ｃｅ（ｉ）とからなるＡｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））  （但し、ｉ＝１，・・・，ｎ）が、符号化メッセージ情報ｖｉに対応する不正チャンネル特定情報とＡｉを生成し、それぞれチャンネルに供給する、ことを特徴とする請求項３６記載の送信装置。
【請求項４０】
請求項３９記載の前記送信装置で生成された符号化メッセージ情報Ｖｉおよびそれらに対応する不正チャンネル特定情報Ａｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））（但し、ｉ＝１，・・・，ｎ）をチャンネルを介して入力し、
符号語（Ｃｓ（ｘ１），・・・，Ｃｓ（ｘｎ））に対してリード・ソロモン誤り訂正処理を実行し、ｅ０，ｅ１，・・・，ｅｔを復元する第１のリード・ソロモン誤り訂正手段と、
符号語（Ｃｅ（１），・・・，Ｃｅ（ｎ））に対してリード・ソロモン誤り訂正処理を実行し、ｅを復元する第２のリード・ソロモン誤り訂正手段と、
ＧＦ（ｐ）上で
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝  （但し、ｉ＝１，・・・，ｎ）
を計算し、
さらにＧＦ（ｑ）上で、
ｘ｛ｉ｝＝ｐ＊（ｉ−１）＋ｙｉ  （但し、ｉ＝１，・・・，ｎ）
を計算し、
Ｃｅ（ｉ）＝ｅ０＋ｅ１＊ｘ｛ｉ｝＋ｅ２＊ｘ｛ｉ｝＾２＋・・・＋ｅｔ＊ｘ｛ｉ｝＾ｔ  
が成立しないｉの集合Ｌを不正チャンネルリストとして出力する不正チャンネル特定手段と、
を備えている、ことを特徴とする受信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本願は、先の日本特許出願２００７−２０４１３３号（２００７年８月６日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は、伝送システムと方法と伝送プログラムに関する。
【背景技術】
【０００２】
ネットワークを介してメッセージを伝送する方法は様々ある。このような方法には、ネットワークに少しの障害があっても、
（Ａ）十分な正確さでメッセージを送ることができるような機能が求められる。【０００３】
また、用途に応じて様々な機能が付加されており、特に、
（Ｂ）盗聴者に何を送っているか知られないための機能、
（ｃ）受け取ったメッセージが改ざんされていないか検証する機能は、
それぞれもっとも重要な機能の中の１つである。【０００４】
上記（Ａ）、（Ｂ）、（Ｃ）の機能を具備しているメッセージ伝送方法の１つに、送信装置と受信装置の間に、複数のチャンネルを用意し、以下に示す３つの機能を持つメッセージ伝送方法がある。なお、送信装置と受信装置の間にはｎ本のチャンネルがあるものとする。【０００５】
（１）ｔ本までのチャンネルを流れる情報を改ざんすることができ、知ることができる不正者が存在しても、受信装置は圧倒的確率で送信装置の送ったメッセージを受信できる。【０００６】
（２）ｔ本までのチャンネルを流れる情報を改ざんすることができ、知ることができる不正者が存在しても、不正者は送信装置の送ったメッセージを一切推定することができない。【０００７】
（３）ｔ本までのチャンネルを流れる情報を改ざんすることができ、知ることができる不正者が存在しても、送信装置の送ったメッセージ以外の値を受信装置が受信することはない（ｔを「想定不正チャンネル数」と呼ぶ）。【０００８】
このようなメッセージ伝送方式は、ｔとｎの値の関係によって構成できる場合と、できない場合があることが知られている。【０００９】
ｎ≧３ｔ＋１である場合については、非特許文献１に記載されている方式によって構成することができる。【００１０】
非特許文献１に記載されている方法を用いる場合、
ｎ＝３ｔ＋ｄ＋１
とし、
ｄ’を
ｄ≧ｄ’≧０
であるような値とし、メッセージが要素数ｐ＾｛ｘ｝の集合から選ばれる場合、各チャンネルを通して送信するデータは要素数ｐ＾｛ｘ−ｄ’｝の集合の要素となる。【００１１】
チャンネルを用いた場合を例に説明を行ったが、チャンネルを実現する手段は、送信装置の生成した複数のデータを分けて送信することができるものであればよい。  【００１２】
【非特許文献１】Ｄ．Ｄｏｌｅｖ，Ｃ．Ｄｗｏｒｋ，Ｏ．Ｗａａｒｔｓ，Ｍ．Ｙｕｎｇ：  Ｐｅｒｆｅｃｔｌｙ  Ｓｅｃｕｒｅ  Ｍｅｓｓａｇｅ  Ｔｒａｎｓｍｉｓｓｉｏｎ．Ｊ．ＡＣＭ  ４０（１）  １７−４７（１９９３）
【非特許文献２】Ｇ．Ｒ．Ｂｌａｋｌｅｙ，Ｃ．Ｍｅａｄｏｗｓ：Ｓｅｃｕｒｉｔｙ  ｏｆ  Ｒａｍｐ  ｓｃｈｅｍｅ．  Ｐｒｏｃ．ｏｆＣｒｙｐｔｏｌｏｇｙ，Ｖｏｌ．６，Ｎｏ．３，ｐｐ．１５７−１６７，１９９３
【非特許文献３】Ｄ  Ｒ  Ｓｔｉｎｓｏｎ：Ｏｎ  ｔｈｅ  Ｃｏｎｎｅｃｔｉｏｎｓ  Ｂｅｔｗｅｅｎ  Ｕｎｉｖｅｒｓａｌ  Ｈａｓｈｉｎｇ，  Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｄｅｓｉｇｎｓａｎｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ．  Ｃｏｎｇｒｅｓｓｕｓ  Ｎｕｍｅｒａｎｔｉｕｍ  １１４  （１９９６），  ７−２７．
【発明の開示】
【発明が解決しようとする課題】
【００１３】
非特許文献１〜３の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明によって与えられたものである。【００１４】
非特許文献１の構成法にしたがって構成したメッセージ伝送システムでは、チャンネルを通して流すデータのサイズが大きい。【００１５】
本発明の目的は、非特許文献１で提案されているメッセージ伝送システムに比べて、各チャンネルを通して流すデータのサイズの小さい伝送システムと方法並びにプログラムを提供することにある。
【課題を解決するための手段】
【００１６】
本発明の１つの側面において、符号化装置（あるいは、方法とプログラム）は、メッセージを入力として、ｔ個以下の数の符号語からは、メッセージに関する情報が得られず、正しい２ｔ＋１個以上の符号語からは、メッセージが復号できるようなメッセージの符号語を生成するメッセージ符号化装置（工程、処理）と、
符号語を入力とし、符号語からメッセージを復元する際に、ｔ個以下の不正な符号語が含まれていた場合に不正な符号語を特定するための不正符号語特定データを生成する不正符号語特定データ生成装置（工程、処理）と、を備え、前記メッセージの符号語と前記不正符号語特定データを出力する。【００１７】
本発明において、前記不正符号語特定データ生成装置（工程、処理）は、前記不正符号語特定データのなかに、ｔ個以下の不正な不正符号語特定データが存在する場合に、不正な不正符号語特定データを訂正可能な不正符号語特定データを生成する。【００１８】
本発明において、前記不正符号語特定データ生成装置（工程、処理）は、ランダムな情報源をリードソロモン符号化した符号語を不正符号語特定データとして生成する。【００１９】
本発明において、メッセージを入力として、ｔ個以下の数の符号語からはメッセージに関する情報が得られず、正しい２ｔ＋１個以上の符号語からはメッセージが復号できるようなメッセージの符号語を生成するメッセージ符号化装置（工程、処理）と、
ユニバーサルハッシュ関数族を表すデータ集合からランダムなユニバーサルハッシュ関数を表すデータを選び、該ユニバーサルハッシュ関数を表すデータを、ｔ個以下の不正な符号語があっても、不正な符号語を訂正可能であるように符号化する関数データ符号化装置と、
メッセージの符号語を、前記ユニバーサルハッシュ関数に入力して算出した結果を、不正符号語特定データとして出力する不正符号語特定データ生成装置（工程、処理）と、
を備え、
メッセージの符号語と、ユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データを出力し、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる。【００２０】
本発明において、ユニバーサルハッシュ関数を表すデータをリードソロモン符号化した符号語をユニバーサルハッシュ関数を表すデータの符号語として生成する関数データ符号化装置（工程、処理）を備える。【００２１】
本発明によれば、符号語と不正符号語特定用データとを入力とし、不正符号語特定データを用いて不正な符号語を特定する不正符号語特定装置（工程、処理）と、
前記不正符号語特定装置で不正符号語と特定されなかった符号語の集合に対してそれらが同じメッセージに復号されるかどうかの同一性を判定し、同一性があると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、同一性がないと判定されなかった場合には復号失敗を表す出力を行うメッセージ復号装置（工程、処理）と、を備える復号化装置（方法、プログラム）が提供される。【００２２】
本発明の復号化装置（方法、プログラム）において、不正な不正符号語特定データを訂正する不正符号語特定データ訂正装置（工程、処理）を備える。【００２３】
本発明の復号化装置（方法、プログラム）において、不正な不正符号語特定データを、リードソロモン誤り訂正処理によって訂正する不正符号化メッセージ特定装置（工程、処理）を備える。【００２４】
本発明によれば、メッセージの符号語とユニバーサルハッシュ関数を表すデータの符号語と、不正符号語特定データとを入力とし、不正なユニバーサルハッシュ関数の符号語を訂正し、ユニバーサルハッシュ関数を表すデータを復号化する関数データ復号装置（工程、処理）と、
不正関数出力特定データを用いて、復号化したユニバーサルハッシュ関数にメッセージの符号語を入力した出力のなかから不正な符号語を特定する不正符号語特定装置（工程、処理）と、
前記不正符号語特定装置で不正符号語と特定されなかった符号語の集合に対して、それらが同じメッセージに復号されるかどうかの同一性を判定し、同一性があると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、同一性がないと判定されなかった場合は、復号失敗を表す出力を行うメッセージ復号装置（工程、処理）と、
を備え、
前記ユニバーサルハッシュ関数族として、該関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、いずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族を用いる、復号化装置（方法、プログラム）が提供される。【００２５】
本発明の復号化装置（方法、プログラム）において、不正なユニバーサルハッシュ関数を表すデータの符号語を、リードソロモン誤り訂正処理によって、不正なユニバーサルハッシュ関数の符号語を訂正する関数データ復号装置（工程、処理）を備える。
【発明の効果】
【００２６】
本発明によれば、メッセージ伝送システムにおいて、各チャンネルを通して流すデータのサイズを従来よりも小さくすることができる。
【図面の簡単な説明】
【００２７】
【図１】本実施形態のメッセージ伝送システムの構成を示すブロック図である。
【図２】送信装置１００の構成を示すブロック図である。
【図３】受信装置２００の構成を示すブロック図である。
【図４】送信装置１００または受信装置２００を実現するためのコンピュータの構成を示すブロック図である。
【図５】送信装置１００の動作を説明するためのフローチャートである。
【図６】受信装置２００の動作を説明するためのフローチャートである。
【図７】第１の実施例における不正チャンネル特定情報生成装置１０２の構成を示すブロック図である。
【図８】第１の実施例における不正チャンネル特定装置２０２の構成を示すブロック図である。
【図９】第２の実施例における不正チャンネル特定情報生成装置１０２の構成を示すブロック図である。
【図１０】第２の実施例における不正チャンネル特定装置２０２の構成を示すブロック図である。
【符号の説明】
【００２８】
１０  処理装置
１１  ＣＰＵ
１２  主記憶装置
１３  記録媒体
１４  データ蓄積装置
１５  メモリ制御インターフェイス部
１６  Ｉ／Ｏインターフェイス部
１８  バス
２０  入力装置
３０  出力装置
１００  送信装置
１０１  メッセージ符号化装置
１０２  不正チャンネル特定情報生成装置
２００  受信装置
２０１  メッセージ復号装置
２０２  不正チャンネル特定装置
３００−１〜３００−ｎ  チャンネル
４０１  符号化メッセージ情報変換装置
４０２  ＲＳ情報源生成装置
４０３  ＲＳ符号語生成装置
５０１  ＲＳ誤り訂正装置
５０２  不正チャンネル集合出力装置
６０１  符号化メッセージ情報変換装置
６０２  第１のＲＳ情報源生成装置
６０３  第１のＲＳ符号語生成装置
６０４  第２のＲＳ情報源生成装置
６０５  第２のＲＳ符号語生成装置
７０１  第１のＲＳ誤り訂正装置
７０２  第２のＲＳ誤り訂正装置
７０３  不正チャンネル集合出力装置
Ａ１〜Ａ３，Ｂ１〜Ｂ７  ステップ
【発明を実施するための最良の形態】
【００２９】
次に、本発明を実施するための最良の形態について図面を参照して詳細に説明する。【００３０】
本発明の一実施形態において、メッセージ伝送システムの送信側は、メッセージを想定する不正チャンネル数であるｔ個以下の数の符号化されたメッセージからは、メッセージに関する情報が得られず、ｔ個以下の符号化されたメッセージなしでもメッセージが復号できるような３ｔ＋１個以上のメッセージの符号語を生成して送信し、そのうち、ｔ個以下のデータに誤りがあっても、前記した複数のメッセージの符号語のうち、ｔ個以下の誤りを検出することができる複数の不正符号化メッセージ特定用データを生成して送信する。【００３１】
メッセージ伝送システムの受信側は、前述のようにして生成されたメッセージの符号語とそれらに対応する不正符号化メッセージ特定用データとを受信し、メッセージの符号語と、不正符号化メッセージ特定用データを用いて、メッセージの符号語のそれぞれが不正なメッセージの符号語であるかを判断し、不正な符号化メッセージ情報であると判断されなかったメッセージの符号語のすべてが同じメッセージの符号語であるか否かを判断し、同じメッセージの符号語であった場合には、当該メッセージを出力し、それ以外の場合はメッセージの受信失敗を表す出力を行う。【００３２】
前述のようなメッセージの符号化方法として、（ａ，ｂ，ｃ）しきい値法と呼ばれる符号化手法を用いることができる。【００３３】
この符号化手法は、情報をｃ個の分散情報に符号化するものである。そのうち、任意のａ個以上の分散情報からは秘密情報が完全に復元できるが、ａ−ｂ−１個までの分散情報からでは秘密情報に関する情報は全く得られない、という特徴を持つ。【００３４】
したがって、仮に、ａ−ｂ−１個までの分散情報が盗難にあったとしても、秘密情報は漏れず、ｃ−ａ個までの分散情報が破壊されても、秘密情報を復元できる。【００３５】
このような符号化手法において、
符号語数をｎとして、
ａ＝ｔ＋１、
ｂ＝ｎ−３ｔ＋１、
ｃ＝ｎ、
とすると、前述の条件を満たす。【００３６】
（ａ，ｂ，ｃ）しきい値法として代表的な手法としては、非特許文献２に記載されている手法があげられる。【００３７】
より詳細には、本発明のメッセージ伝送システムは、想定不正チャンネル数をｔとすると、
チャンネル数ｎ＝３ｔ＋ｄ＋１  （但し、ｄ≧０）
を満たす数のチャンネルで互いに接続された送信装置と受信装置からなる。【００３８】
送信装置は、ｄ’を、ｄ≧ｄ’≧０であるような値として、
メッセージを、（２ｔ＋ｄ’＋１，ｄ’＋ｔ，ｎ）しきい値法を用いて符号化した値Ｖ＿ｉ  （ｉ＝１，・・・，ｎ）を生成し、
Ｖ＿ｉとランダムなｔ次多項式とを用いて、ｎ個のＶ＿ｉのうち、ｔ個以下のものに誤りがある場合に、リードソロモン誤り訂正処理による誤りの検出および訂正を可能とする不正チャンネル特定情報Ａ＿ｉ（ｉ＝１，・・・，ｎ）を、ｎ個のＶ＿ｉに対応付けて生成し、チャンネルＣ＿ｉ（ｉ＝１，・・・，ｎ）を用いて、Ｖ＿ｉ（ｉ＝１，・・・，ｎ）、Ａ＿ｉ（ｉ＝１，・・・，ｎ）を送信する。【００３９】
受信装置には、送信装置で生成されたＶ＿ｉ（ｉ＝１，・・・，ｎ）とＡ＿ｉ（ｉ＝１，・・・，ｎ）をそれぞれチャンネルＣ＿ｉ（ｉ＝１，・・・，ｎ）を介して受信し、Ｖ＿ｉ（ｉ＝１，・・・，ｎ）とＡ＿ｉ（ｉ＝１，・・・，ｎ）を用いて、リードソロモン誤り訂正処理を行って、ｎ個のＶ＿ｉそれぞれについて不正な値であるか否かを判断し、不正であると判断されなかったＶ＿ｉがすべて同じメッセージの符号語であるかを調べる。同じメッセージの符号語である場合には、そのメッセージを出力し、異なるメッセージの符号語が含まれている場合には、メッセージの受信失敗を表す記号を出力する。【００４０】
本発明によれば、このような構成を用いることによって、各チャンネルを通して流す情報量を、従来よりも小さくすることができる。【００４１】
ｎ本のチャンネルを用いた場合の説明を行ったが、チャンネルを実現する手段は、送信装置で生成した複数のデータを分けて送信することができるものであれば任意のものが用いられる。つまり、チャンネルはｎ本でなくてもよい。【００４２】
想定不正チャンネル数とは、送信装置が生成するｎ組の情報に対する改ざん、盗聴を許す最大の数を表しているものである。【００４３】
図１は、本発明の一実施形態のメッセージ伝送システムの構成を示す図である。図１を参照すると、メッセージ伝送システムは、送信装置１００、受信装置２００、および  チャンネル３００−１〜３００−ｎを有している。【００４４】
このメッセージ伝送システムの動作には、２つのフェーズがある。【００４５】
そのうちの１つは、メッセージを符号化し、符号化したメッセージをチャンネルを用いて送信するフェーズである。【００４６】
他は、１つのチャンネルから受信した符号化されたメッセージを復号化するフェーズである。【００４７】
メッセージを符号化し、符号化したメッセージをチャンネルを用いて送信するフェーズでは、主に、送信装置１００が動作し、チャンネルから受信した符号化されたメッセージを復号化するフェーズでは、主に、受信装置２００が動作する。【００４８】
メッセージを符号化し、符号化したメッセージをチャンネルを用いて送信するフェーズでは、まず、送信装置１００は、パラメータとして入力された、想定不正チャンネル数およびチャンネル数ｎに従って、メッセージを符号化することにより、複数の符号化メッセージ情報を生成し、該複数の符号化メッセージ情報（「分散メッセージ情報」ともいう）を、それぞれ、異なるチャンネル３００−１〜３００−ｎを用いて送信する。【００４９】
さらに、送信装置１００は、生成した分散秘密情報と、想定不正チャンネル数とを用いて、符号化メッセージ情報毎の不正チャンネル特定情報を生成し、各不正チャンネル特定情報に対応する符号化メッセージ情報が送信されたチャンネル３００−１〜３００−ｎを用いて送信する。【００５０】
想定不正チャンネル数は、想定される不正なチャンネルの上限数という意味であり、本実施形態のメッセージ伝送システムによれば、想定チャンネル数までの数の符号化メッセージ情報の改ざんであれば、改ざんされた符号化メッセージ情報の特定が可能である。【００５１】
不正チャンネル特定情報は、改ざんされた符号化メッセージ情報を特定するためのデータである。【００５２】
なお、ここでは、典型例として、改ざんを示しているが、意図的に改ざんされた場合に限らず、何らかの要因で情報が不正なものに変化してしまった場合も含めることができることは勿論である。【００５３】
まず、分散メッセージ情報を送信し、その後で、不正チャンネル特定情報を送信する必要はなく、すべて生成された後で、一度に送ってもよい。【００５４】
また、チャンネルから受信した符号化されたメッセージを復号化するフェーズでは、まず受信装置２００は、チャンネル３００−１〜３００−ｎから符号化メッセージ情報と不正チャンネル特定情報とを受信し、符号化メッセージ情報と不正チャンネル特定情報とを用いて、改ざんされた符号化メッセージ情報を特定する処理を実行する。【００５５】
改ざんされた符号化メッセージ情報を特定する処理では、改ざんの有無が判定され、改ざんがある場合には、改ざんされている符号化メッセージ情報が特定される。【００５６】
受信装置２００は、改ざんが検出されなかった符号化メッセージ情報のすべてが同じメッセージが符号化されたものであるかを調べ、
同じメッセージが符号化されていた場合、そのメッセージを出力し、
それ以外の場合、メッセージ受信の失敗を表す記号を出力する。【００５７】
図２は、図１の送信装置１００の構成を示す図である。図２を参照すると、送信装置１００は、メッセージ符号化装置１０１と、不正チャンネル特定情報生成装置１０２とを有する。図２において、メッセージｓは、特定のメッセージ集合の元を表している。【００５８】
送信装置１００には、メッセージｓ、想定不正チャンネル数ｔ、チャンネル数ｎが入力されている。【００５９】
メッセージ符号化装置１０１は、メッセージｓ、想定不正チャンネル数ｔ、チャンネル数ｎを入力として、ｔ個以下の数の符号語からは、メッセージに関する情報が得られず、正しい２ｔ＋１個以上の符号語からは、メッセージが復号できるようなメッセージの符号語（符号化メッセージ情報）を生成する。【００６０】
不正チャンネル特定情報生成装置１０２は、符号語を入力とし、想定不正チャンネル数ｔ、チャンネル数ｎを入力し、該符号語からメッセージを復元する際に、ｔ個以下の不正な符号語が含まれていた場合に不正な符号語を特定するための不正符号語特定データ（不正者チャンネル特定情報Ａ１〜Ａｎ）を生成する。【００６１】
そして、メッセージ符号化装置１０１は、符号化メッセージ情報ｖ１〜ｖｎを生成し、それぞれチャンネル３０１−１〜３０１−ｎを通して送信する。【００６２】
不正チャンネル特定情報生成装置１０２は、不正者チャンネル特定情報Ａ１〜Ａｎを生成し、それぞれチャンネル３０１−１〜３０１−ｎを通して送信する。【００６３】
図３は、受信装置２００の構成を示すブロック図である。図３を参照すると、受信装置２００は、メッセージ復号装置２０１と、不正チャンネル特定装置２０２とを有している。【００６４】
受信装置２００には、想定不正チャンネル数ｔ、および、チャンネル３０１−１〜３０１−ｎから入力される符号化メッセージ情報ｖ１〜ｖｎと、不正チャンネル特定情報Ａ１〜Ａｎが入力される。【００６５】
受信装置２００は、符号化メッセージ情報ｖ１〜ｖｎと、不正者特定情報Ａ１〜Ａｎとを受信し、改ざんされた符号化メッセージ情報を特定する処理を実行する。【００６６】
改ざんされていない符号化メッセージ情報がすべて同じメッセージが符号化されたものであるかを調べ、すべて同じメッセージが符号化されたものであることが確認できた場合、そのメッセージを出力し、それ以外の場合、受信失敗を表す記号を出力する。【００６７】
不正チャンネル特定装置２０２は、チャンネル３００−１〜３００−ｎから符号化メッセージ情報ｖ１〜ｖｎと不正チャンネル特定情報Ａ１〜Ａｎを受信し、改ざんされた符号化メッセージ情報を特定する処理を実行する。【００６８】
改ざんが検出されれば、不正チャンネル特定装置２０２は、不正チャンネルの識別子を要素とする集合をメッセージ復号装置２０１に入力する。【００６９】
改ざんが検出されなければ、不正チャンネル特定装置２０２は、不正チャンネルが存在しなかったことを示す空集合をメッセージ復号装置２０１に入力する。【００７０】
メッセージ復号装置２０１は、チャンネル３００−１〜３００−ｎから符号化メッセージ情報ｖ１〜ｖｎを受信し、不正チャンネル特定装置２０２からの入力のＬに含まれていない符号化メッセージ情報がすべて同じメッセージの符号語であるか調べ、すべて同じメッセージが符号化されたものであることが確認できた場合、そのメッセージを出力し、それ以外の場合、受信失敗を表す記号を出力する。【００７１】
図４は、送信装置１００または受信装置２００を実現するためのコンピュータの構成を示すブロック図である。図４を参照すると、コンピュータは、処理装置１０、入力装置２０、および出力装置３０を備えている。処理装置１０は、プログラムにしたがって所定の処理を実行する。入力装置２０は、処理装置１０に対するコマンドや情報の入力に用いられる入力装置である。出力装置３０は、処理装置１０の処理結果をモニタするための出力装置である。また処理装置１０は、ＣＰＵ１１、主記憶装置１２、記録媒体１３、データ蓄積装置１４、メモリ制御インターフェイス部１５、およびＩ／Ｏインターフェイス部１６を有し、それらがバス１８を介して相互に接続された構成である。ＣＰＵ１１はプログラムを実行するプロセッサである。主記憶装置１２は、ＣＰＵ１１の処理に必要な情報を一時的に記憶する。記録媒体１３は、ＣＰＵ１１に実行させるためのプログラムを記憶している。【００７２】
データ蓄積装置１４は、秘密情報やアクセス構造データを記憶する。メモリ制御インターフェイス部１５は、主記憶装置１２、記録媒体１３、またはデータ蓄積装置１４のデータの書き込みおよび読み出しを制御するインターフェイス装置である。Ｉ／Ｏインターフェイス部１６は、入力装置２０および出力装置３０とのデータの入出力を制御するインターフェイス装置である。このインターフェイス装置を用いて、チャンネル３００を用いてのデータの送受信を行う。また、記録媒体１３は、磁気ディスク、半導体メモリ、光ディスク、あるいはその他の記録媒体である。【００７３】
図５は、本実施形態における、送信装置１００の動作を説明するためのフローチャートである。【００７４】
図５を参照すると、まず送信装置１００にメッセージｓ、想定不正チャンネル数ｔ、チャンネル数ｎが入力される（ステップＡ１）。【００７５】
送信装置１００では、まず、メッセージ符号化装置１０１が、メッセージｓ、想定不正チャンネル数ｔ、およびチャンネル数ｎを用いて、メッセージ符号化の処理を実行してｎ個の符号化メッセージ情報ｖ１〜ｖｎを生成し、チャンネル３００−１〜３００−ｎと、不正チャンネル特定情報生成装置１０２に入力する（ステップＡ２）。【００７６】
次に、不正チャンネル特定情報生成装置１０２は、入力された想定不正者数ｔおよびチャンネル数ｎと、メッセージ符号化装置１０１で生成された符号化メッセージ情報ｖ１〜ｖｎとを用いて、符号化メッセージ情報ｖ１〜ｖｎのそれぞれに対応した不正チャンネル特定情報Ａ１〜Ａｎを生成し、チャンネル３００−１〜３００−ｎに入力する。（ステップＡ３）。【００７７】
図６は、本実施形態における受信装置２００の動作を説明するためのフローチャートである。図６を参照すると、まず、受信装置２００に想定不正チャンネル数ｔが入力される。（ステップＢ１）。【００７８】
続いて、受信装置２００はチャンネル３００−１〜３００−ｎから不正チャンネル特定情報Ａ１〜Ａｎおよび符号化メッセージ情報をｖ１〜ｖｎを読み出す（ステップＢ２）。【００７９】
そして、受信装置２００の不正チャンネル特定装置２０２が、不正チャンネル特定情報、各符号化メッセージ情報、想定不正チャンネル数ｔを用いて、不正チャンネルの識別子を元とする集合Ｌを生成する（ステップＢ３）。【００８０】
次に、メッセージ復号装置２０１が、集合Ｌに識別子が含まれていないチャンネルから入力された符号化メッセージ情報がすべて同じメッセージの符号化情報であるか否かを調べる（ステップＢ４）。【００８１】
メッセージ復号装置２０１は、すべて同じメッセージの符号化情報であることが確認できた場合、そのメッセージを出力する（ステップＢ５）。【００８２】
メッセージ復号装置２０１は、すべて同じメッセージの符号化情報であることが確認できない場合には、メッセージの受信失敗を表す記号を出力する（ステップＢ６）。以下、具体的な実施例に即して説明する。【００８３】
＜第１の実施例＞
第１の実施例のシステム構成は図１乃至図３を参照して説明した前記実施形態と同様とされる。【００８４】
チャンネル数ｎと、想定不正チャンネル数ｔに対して、
ｎ≧３＊ｔ＋１
が成立しているものとする。【００８５】
また、
ｎ＝３ｔ＋ｄ＋１
とし、
ｄ’を
ｄ≧ｄ’≧０
であるものとする。【００８６】
第１の実施例のメッセージ伝送システムは、メッセージのデータ集合に、ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）を用いる。但し、ｐは素数の冪乗であり、素数そのものである場合もある。【００８７】
ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）は、素数の冪乗ｐに対する有限体であり、有限体上の加算を＋、減算を−、乗算を＊、除算を／、冪乗算を＾で表す。【００８８】
第１の実施例におけるメッセージ符号化装置１０１（図１参照）は、非特許文献３に記載された、（２ｔ＋ｄ’＋１，ｔ＋ｄ’，ｎ）しきい値法を用いて秘密情報を分散符号化する。【００８９】
メッセージ復号装置２０１は、（２ｔ＋ｄ’＋１，ｔ＋ｄ’，ｎ）しきい値法に対応する復号方法を用いてメッセージを復元する。【００９０】
このとき、符号化されたメッセージはデータ集合ＧＦ（ｐ）の要素になる。【００９１】
次に、第１の実施例の送信装置１００と受信装置２００（図１参照）について説明する。【００９２】
第１の実施例の送信装置１００には、メッセージｓ、想定不正チャンネル数（想定不正者数）ｔ、分散情報総数（チャンネル数）ｎが入力される。【００９３】
ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）の要素であるメッセージｓは、ＧＦ（ｐ）によって、
（ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝）
のように表せる。【００９４】
送信装置１００では、メッセージ符号化装置１０１（図１参照）が、ＧＦ（ｐ）上の定数項から、ｄ’＋ｔ次の項までの係数が、それぞれ、
ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝である、２ｔ＋ｄ’次多項式を、ランダムに生成する。この２ｔ＋ｄ’次多項式を、
ｆｓ（ｘ）
と記す。【００９５】
そして、メッセージ符号化装置１０１は、
ｆｓ（１），ｆｓ（２），・・・，ｆｓ（ｎ）
を計算し、計算結果と入力ｉとのペア
Ｖｉ＝（ｉ，ｖｉ）
（ｉ＝１，２，・・・，ｎ，ｖｉ＝ｆｓ（ｉ））
を、符号化メッセージ情報として、それぞれ、チャンネル３００−ｉ（（ｉ＝１，２，・・・，ｎ）に入力する。【００９６】
図７は、第１の実施例における不正チャンネル特定情報生成装置１０２の構成を示すブロック図である。図７を参照すると、不正チャンネル特定情報生成装置１０２は、符号化メッセージ情報変換装置４０１、ＲＳ（Reed  Solomon）情報源生成装置４０２、およびＲＳ符号語生成装置４０３を有している。【００９７】
符号化メッセージ情報変換装置４０１は、メッセージ符号化装置１０１の出力である
Ｖｉ＝（ｉ，ｖｉ）
を取得し、
ｑ≧ｎ＊ｐ
となるｑに対し、有限体ＧＦ（ｑ）上で、
ｘｉ＝ｐ＊（ｉ−１）＋ｖｉ  （ｉ＝１，２，・・・，ｎ）
を計算し、ＲＳ符号語生成装置４０３に出力する。【００９８】
ＲＳ情報源生成装置４０２は、有限体ＧＦ（ｑ）上のランダムなデータｅ０，ｅ１，・・・，ｅｔを生成し、ＲＳ符号語生成装置４０３に出力する。【００９９】
ＲＳ符号語生成装置４０３は、
符号化メッセージ情報変換装置４０１から出力されたｘｉ（ｉ＝１，２，・・・，ｎ）と、
ＲＳ情報源生成装置４０２から出力されたｅ０，ｅ１，・・・，ｅｔと
を取得し、
有限体ＧＦ（ｑ）上で、
Ａｉ＝ｅ０＋ｅ１＊ｘｉ＋ｅ２＊ｘｉ＾２＋・・・＋ｅｔ＊ｘｉ＾ｔ    （ｉ＝１，２，・・・，ｎ）
を計算し、それぞれをチャンネル３００−ｉ（ｉ＝１，２，・・・，ｎ）に入力する。【０１００】
このＡ１，Ａ２，・・・，Ａｎが、第１の実施例における不正チャンネル特定情報となる。【０１０１】
第１の実施例の受信装置２００（図２参照）には、想定不正チャンネル数ｔが入力される。【０１０２】
受信装置２００には、チャンネル３００−１，３００−２，・・・，３００−ｎから、
Ｖｉ＝（ｉ，ｖｉ）とＡｉ  （ｉ＝１，２，・・・，ｎ）
が入力される。【０１０３】
ここで取得した
（Ａ１，Ａ２，・・・，Ａｎ）
は、
ＲＳ情報源生成装置４０２の出力
ｅ０，ｅ１，・・・，ｅｔ
を情報源とするリード・ソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）誤り訂正符号の符号語になっている。【０１０４】
前提より、
ｎ≧３ｔ＋１
であることから、Ａｉに含まれるｔ個の誤りを訂正し、元の情報源ｅ０，ｅ１，・・・，ｅｔを復元することが可能である。【０１０５】
受信装置２００内では、Ｖｉ＝（ｉ，ｖｉ）と、Ａｉ  （ｉ＝１，２，・・・，ｎ）が不正チャンネル特定装置２０２に入力される。【０１０６】
図８は、第１の実施例における不正チャンネル特定装置２０２の構成を示すブロック図である。図８を参照すると、不正チャンネル特定装置２０２は、ＲＳ誤り訂正装置５０１および不正チャンネル集合出力装置５０２を有している。【０１０７】
ＲＳ誤り訂正装置５０１は、データＶｉ＝（ｉ，ｖｉ）と、データＡｉ  （ｉ＝１，２，・・・，ｎ）とを用いて、リード・ソロモン誤り訂正処理を実行し、不正チャンネル特定情報生成装置１０２のＲＳ情報源生成装置４０２が生成したものと同じ
ｅ０，ｅ１，・・・，ｅｔ
を復元し、不正チャンネル集合出力装置５０２に出力する。このとき、リード・ソロモン誤り訂正処理としては、公知の方法が用いられる。公知のリード・ソロモン誤り訂正処理の一例として、バーレカンプ（Ｂｅｒｌｅｋａｍp）法がある。【０１０８】
不正チャンネル集合出力装置５０２には、Ｖｉ＝（ｉ，ｖｉ））Ａｉ（ｉ＝１，・・・，ｎ）が入力される。【０１０９】
不正チャンネル集合出力装置５０２は、取得したデータを用いて、
ｘｉ＝ｐ＊（ｉ−１）＋ｖｉ  （ｉ＝１，２，・・・，ｎ）
を計算し、
Ａｉ＝ｅ０＋ｅ１＊ｘｉ＋ｅ２＊ｘｉ＾２＋・・・＋ｅｔ＊ｘｉ＾ｔ
が成立しないｉの集合Ｌを、不正チャンネルリストとしてメッセージ復号装置２０１に送る。【０１１０】
メッセージ復号装置２０１は、不正チャンネル特定装置２０２からの集合（不正チャンネルリスト）Ｌを取得し、集合Ｌにｉが含まれていないＶｉがすべて同じメッセージの符号語であるかを調べる。【０１１１】
メッセージ復号装置２０１は、すべてが同じメッセージの符号語であることが確認できたとき、そのメッセージを出力する。それ以外の場合、メッセージ復号装置２０１は、メッセージの受信失敗を表す記号を出力する。【０１１２】
メッセージを復号する処理において、メッセージを復元する方法としては、公知の方法を用いればよい。公知の方法の一例として、連立方程式を解く方法やラグランジュ補間を用いる方法がある。【０１１３】
以上説明したように、第１の実施例によれば、送信装置１００において、メッセージ符号化装置１０１は、（２ｔ＋ｄ’＋１，ｔ＋ｄ’，ｎ）しきい値法でｎ個の符号化メッセージ情報Ｖｉ（ｉ＝１，２，・・・，ｎ）を生成する。【０１１４】
不正チャンネル特定情報生成装置１０２は、メッセージ符号化装置１０１の生成したｎ個の符号化メッセージ情報Ｖｉと、ｔ次多項式とを用いて、各符号化メッセージ情報Ｖｉに対する不正チャンネル特定情報Ａｉ（ｉ＝１，２，・・・，ｎ）を生成する。【０１１５】
その際、不正チャンネル特定情報生成装置１０２は、符号化メッセージ情報Ｖｉ（ｉ＝１，２，・・・，ｎ）のうちｔ個以下のものに誤りがある場合にリード・ソロモン誤り訂正処理による誤りの検出および訂正を可能とする不正チャンネル特定情報を生成する。【０１１６】
受信装置２００において、不正チャンネル特定装置２０２は、符号化メッセージ情報Ｖｉ（ｉ＝１，２，・・・，ｎ）およびそれらに対応する不正チャンネル特定情報を用いて、リード・ソロモン誤り訂正処理を行って、誤った分散秘密情報を示す記号の集合Ｌ（不正チャンネル特定装置２０２からの集合（不正チャンネルリスト））を出力する。【０１１７】
メッセージ復号装置２０１は、不正チャンネル特定装置２０２によるリード・ソロモン誤り訂正処理にて誤りが検出されなかった符号化メッセージ情報Ｖｉのすべてが同じメッセージが符号化された情報であることが確認できた場合、そのメッセージを出力する。それ以外の場合、メッセージの受信失敗を表す記号を出力する。第１の実施例では、メッセージを多項式の係数に埋め込んでいる。多項式の係数に埋め込んだ情報を求める方法としては、連立方程式を解く方法などがある。【０１１８】
このように、符号化メッセージ情報Ｖｉと、ランダムなｔ次多項式とを用いて、リード・ソロモン誤り訂正処理による誤りの検出および訂正を可能とする不正チャンネル特定情報を生成することで、改ざんされた符号化メッセージ情報の特定を可能とするメッセージ伝送システムの各チャンネルを通して送信するデータのサイズを、従来よりも小さくすることができる。【０１１９】
また、第１の実施例では、各符号化メッセージ情報Ｖｉ（ｉ＝１，２，・・・，ｎ）から一意に導き出される値ｘｉ（ｉ＝１，２，・・・，ｎ）を、ランダムなｔ次多項式に代入し、得られた値を各Ｖｉに対する不正チャンネル特定情報Ａｉとする。【０１２０】
その際、任意のｖｉ，ｖｊについて、
ｖｉ≠ｖｊであればｘｉ≠ｘｊ
が成立するように、符号化メッセージ情報Ｖｉとｉからｘｉを生成するとき、
ｑ≦ｎ＊ｐとなるｑに対して、
ＧＦ（ｑ）上で、
ｘｉ＝ｐ＊（ｉ−１）＋ｖｉ  （ｉ＝１，２，・・・，ｎ）を計算する。【０１２１】
符号化メッセージ情報のサイズをｐとする第１の実施例では、符号化メッセージ情報と不正チャンネル特定情報のサイズを併せた集合のサイズがｐ＊ｑとなる。【０１２２】
また、改ざんされた符号化メッセージ情報が集合Ｌの元として出力される確率、つまり改ざんを検出できる確率は、１−１／ｑとなる。【０１２３】
非特許文献１に開示された方式では、各チャンネルを通して送るデータサイズは
ｐ＾｛（ｄ’＋ｔ＋１）−ｄ’｝
、つまり、
ｐ＾｛ｔ＋１｝
である。【０１２４】
ｑはたかが、ｐのｎ倍であるので、ｔが大きいほど、本実施例の、各チャンネルを通して送るデータのサイズが低減される。【０１２５】
本実施例は、不正チャンネル特定情報の誤りを訂正する方法として、リードソロモン誤り訂正処理を用いているが、誤りが確実に訂正できる方法であれば、他の方法を用いてもよい。【０１２６】
＜第２の実施例＞
第２の実施例において、チャンネル数ｎと想定不正チャンネル数ｔに対して、
ｎ≧３＊ｔ＋１
が成立しているものとする。【０１２７】
また、
ｎ＝３ｔ＋ｄ＋１
とし、
ｄ’を、
ｄ≧ｄ’≧０
であるものとする。【０１２８】
第２の実施例のシステムは、秘密情報のデータ集合に、有限体ＧＦ（ｐ＾（Ｎ＊（ｔ＋ｄ’＋１）））を用いる。【０１２９】
ここで、ｐは、第１の実施例で用いたのと同じ素数の冪乗である。【０１３０】
また、第１の実施例と同様、有限体上の加算を＋、減算を−、乗算を＊、除算を／、冪乗算を＾で表す。【０１３１】
第２の実施例におけるメッセージ符号化装置１０１（図１参照）も、第１の実施例同様、非特許文献３に記載された（２ｔ＋ｄ’＋１，ｔ＋ｄ’，ｎ）しきい値法を用いてメッセージを符号化する。【０１３２】
メッセージ復号装置２０１（図２参照）は、その（２ｔ＋ｄ’＋１，ｔ＋ｄ’，ｎ）しきい値法に対応する復号方法を用いてメッセージを復号する。【０１３３】
次に第２の実施例の送信装置１００と受信装置２００について説明する。【０１３４】
第２の実施例の送信装置１００には、メッセージｓ、チャンネル数ｎ、および想定不正チャンネル数ｔが入力される。【０１３５】
ＧＦ（ｐ＾（Ｎ＊（ｄ’＋ｔ＋１）））の要素であるメッセージｓは、ＧＦ（ｐ＾Ｎ）の要素によって、
（ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝）
のように表せる。【０１３６】
送信装置１００は、メッセージｓ、チャンネル数ｎ、想定不正チャンネル数ｔが入力されると、メッセージ符号化装置１０１により、ＧＦ（ｐ＾Ｎ）上の定数項からｄ’＋ｔ次の項までの係数がそれぞれ、
ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝
である２ｔ＋ｄ’次多項式をランダムに生成する。【０１３７】
この２ｔ＋ｄ’次多項式をｆｓ（ｘ）と記す。【０１３８】
そして、メッセージ符号化装置１０１は、
ｆｓ（１），ｆｓ（２），・・・，ｆｓ（ｎ）
を計算し、計算結果ｆｓ（ｉ）と入力ｉとのペア
Ｖｉ＝（ｉ，ｖｉ）  （ｉ＝１，２，・・・，ｎ，ｖｉ＝ｆｓ（ｉ））
を符号化メッセージ情報として、それぞれチャンネル３００−ｉ（ｉ＝１，２，・・・，ｎ）に入力する。【０１３９】
ＧＦ（ｐ＾Ｎ）の要素である符号化メッセージ情報ｖｉは、ＧＦ（ｐ）の要素によって
（ｖ｛ｉ，０｝，・・・，ｖ｛ｉ，Ｎ−１｝）
のように表せる。【０１４０】
図９は、第２の実施例における不正チャンネル特定情報生成装置１０２の構成を示すブロック図である。図９を参照すると、不正チャンネル特定情報生成装置１０２は、符号化メッセージ情報変換装置６０１、第１のＲＳ情報源生成装置６０２、第１のＲＳ符号語生成装置６０３、第２のＲＳ情報源生成装置６０４、および第２のＲＳ符号語生成装置６０５を有している。【０１４１】
不正チャンネル特定情報生成装置１０２にチャンネル数ｎおよび想定不正チャンネル数ｔが入力されると、符号化メッセージ情報変換装置６０１は、メッセージ符号化装置１０１の出力であるＶｉ＝（ｉ，ｖ｛ｉ，０｝，・・・，ｖ｛ｉ，Ｎ−１｝）（ｉ＝１，・・・，ｎ）を取得し、ＧＦ（ｐ）上でランダムにｅを選択し、第２のＲＳ符号語生成装置６０５に出力する。【０１４２】
また、符号化メッセージ情報変換装置６０１は、ＧＦ（ｐ）上で
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝  （ｉ＝１，２，・・・，ｎ）
を計算する。【０１４３】
続いて、符号化メッセージ情報変換装置６０１は、
ｑ≧ｎ＊ｐ
となるｑに対し、
ＧＦ（ｑ）上で、
ｘｉ＝ｐ＊（ｉ−１）＋ｙｉ（ｉ＝１，２，・・・，ｎ）
を計算し、第１のＲＳ符号語生成装置６０３に出力する。【０１４４】
第１のＲＳ情報源生成装置６０２は、ＧＦ（ｑ）上のランダムなデータｅ０，ｅ１，・・・，ｅｔを第１のＲＳ符号語生成装置６０３に出力する。【０１４５】
第１のＲＳ符号語生成装置６０３は、
符号化メッセージ情報変換装置６０１から出力されたｘｉ（ｉ＝１，２，・・・，ｎ）と、
第１のＲＳ情報源生成装置６０２から出力されたｅ０，ｅ１，・・・，ｅｔと、
を取得し、ＧＦ（ｑ）上で、
Ｃｓ（ｘｉ）＝ｅ０＋ｅ１＊ｘｉ＋ｅ２＊ｘｉ＾２＋・・・＋ｅｔ＊ｘｉ＾ｔ（ｉ＝１，２，・・・，ｎ）
を計算し、出力する。【０１４６】
第２のＲＳ情報源生成装置６０４は、ＧＦ（ｐ）上のランダムなデータｒ１，・・・，ｒｔを選択し、第２のＲＳ符号語生成装置６０５に出力する。【０１４７】
第２のＲＳ符号語生成装置６０５は、
符号化メッセージ情報変換装置６０１から出力されたｅと、
第２のＲＳ情報源生成装置６０４から出力されたｒ１，・・・，ｒｔと、
を取得し、ＧＦ（ｑ）上で、
Ｃｅ（ｘｉ）＝ｅ＋ｒ１＊ｉ＋ｒ２＊ｉ＾２＋・・・＋ｒｔ＊ｉ＾ｔ  （ｉ＝１，２，・・・，ｎ）
を計算し出力する。【０１４８】
第１のＲＳ符号語生成装置６０３から出力されたＣｓ（ｘｉ）（ｉ＝１，２，・・・，ｎ）と、
第２のＲＳ符号語生成装置６０５から出力されたＣｅ（ｉ）と
からなる
Ａｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））  （ｉ＝１，２，・・・，ｎ）
が、符号化メッセージ情報ｖｉに対応する不正チャンネル特定情報となる。【０１４９】
不正チャンネル特定情報Ａ１，Ａ２，・・・，Ａｎの各々は、それぞれチャンネル３００−ｉ  （ｉ＝１，２，・・・，ｎ）に入力される。【０１５０】
第２の実施例の受信装置２００には、想定不正チャンネル数ｔが入力される。【０１５１】
受信装置２００には、チャンネル３００−１，３００−２，・・・，３００−ｎからＶｉ＝（ｉ，ｖｉ）と、Ａｉ  （ｉ＝１，２，・・・，ｎ）が入力される。【０１５２】
このＡｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））において、
（Ｃｓ（ｘ１），Ｃｓ（ｘ２），・・・，Ｃｓ（ｘｎ））
は、第１のＲＳ情報源生成装置６０２から出力されたｅ０，ｅ１，・・・，ｅｔを情報源とするリード・ソロモン誤り訂正符号の符号語になっている。【０１５３】
ｎ≧３ｔ＋１
であるので、
Ｃｓ（ｘｉ）に含まれるｔ個の誤りを訂正し、元の情報源ｅ０，ｅ１，・・・，ｅを復元することが可能である。【０１５４】
また同様に、
（Ｃｅ（１），Ｃｅ（２），・・・，Ｃｅ（ｎ））は、ｅ，ｒ１，ｒ２，・・・，ｒｔを情報源とするリード・ソロモン誤り訂正符号の符号語になっている。ここで、ｅは符号化メッセージ情報変換装置６０１の出力である。また、ｒ１，・・・，ｒｔは、第２のＲＳ符号語生成装置６０５の出力である。【０１５５】
前提より、
ｎ≧３ｔ＋１
であることから、
Ｃｅ（ｉ）に含まれるｔ個の誤りを訂正し、元の情報源ｅ，ｒ１，・・・，ｒｔを復元することが可能である。【０１５６】
受信装置２００内では、不正チャンネル集合出力装置５０２には、Ｖｉ＝（ｉ，ｖｉ）、Ａｉ（  ｉ＝１，・・・，ｎ）が不正チャンネル特定装置２０２に入力される。【０１５７】
図１０は、第２の実施例における不正チャンネル特定装置２０２の構成を示すブロック図である。図１０を参照すると、不正チャンネル特定装置２０２は第１のＲＳ誤り訂正装置７０１、第２のＲＳ誤り訂正装置７０２、および不正チャンネル集合出力装置７０３を有している。【０１５８】
第１のＲＳ誤り訂正装置７０１は、符号語（Ｃｓ（ｘ１），・・・，Ｃｓ（ｘｎ））に対してリード・ソロモン誤り訂正処理を実行し、不正チャンネル特定情報生成装置１０２の第１のＲＳ情報源生成装置６０２が出力したのと同じｅ０，ｅ１，・・・，ｅｔを復元し、不正チャンネル集合出力装置７０３に出力する。【０１５９】
第２のＲＳ誤り訂正装置７０２は、符号語（Ｃｅ（１），・・・，Ｃｅ（ｎ））に対してリード・ソロモン誤り訂正処理を実行し、不正チャンネル特定情報生成装置１０２の符号化メッセージ情報変換装置６０１が出力したのと同じｅを復元し、不正チャンネル集合出力装置７０３に出力する。【０１６０】
不正チャンネル集合出力装置７０３には、
Ｖｉ＝（ｉ，ｖｉ）、Ａｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））  （ｉ＝１，・・・，ｎ）
が入力される。【０１６１】
そして、不正チャンネル集合出力装置７０３は、
ＧＦ（ｐ）上で
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝  （ｉ＝１，２，・・・，ｎ）
を計算し、
さらにＧＦ（ｑ）上で、
ｘ｛ｉ＿ｊ｝＝ｐ＊（ｉ＿ｊ−１）＋ｙｉ  （ｉ＝１，２，・・・，ｎ）
を計算する。【０１６２】
続いて不正チャンネル集合出力装置７０３は、
Ｃｅ（ｉ）＝ｅ０＋ｅ１＊ｘ｛ｉ｝＋ｅ２＊ｘ｛ｉ｝＾２＋・・・＋ｅｔ＊ｘ｛ｉ｝＾ｔ
が成立しないｉの集合Ｌを不正者リストとして出力する。【０１６３】
この集合（不正チャンネルリスト）Ｌが、不正チャンネル特定装置２０２の出力となる。【０１６４】
メッセージ復号装置２０１は、不正チャンネル特定装置２０２によるリード・ソロモン誤り訂正処理にて誤りが検出されなかった符号化メッセージ情報Ｖｉのすべてが同じメッセージが符号化された情報であることが確認できた場合、そのメッセージを出力する。
それ以外の場合、メッセージの受信失敗を表す記号を出力する。【０１６５】
この実施例では、ｅ０，ｅ１，・・・，ｅｔは、ｅによってＧＦ（ｐ＾Ｎ）の要素であるメッセージの符号語をＧＦ（ｐ）の要素に写した値に不正な値が含まれていないかをチェックしている。つまり、ｅ０，ｅ１，・・・，ｅｔは、メッセージの符号語をｅによって表される関数に入力した出力に不正な値が含まれていないかを特定するためのデータである。【０１６６】
また、
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝  （ｉ＝１，２，・・・，ｎ）
のようなｖ｛ｉ，０｝を入力とした関数は、非特許文献３等に記載されているように、「ユニバーサルハッシュ関数」と呼ばれる関数の関数表現になっている。【０１６７】
このユニバーサルハッシュ関数族は、この関数族からランダムに選ばれたユニバーサルハッシュ関数に対する入力と出力の関係がｔ組判明していても、そのいずれかの入力の出力と同じ出力をもつ入力を選ぶことができる確率が十分に低い関数族になっている。【０１６８】
このため、不正者にｔ本までのチャンネルを流れるデータを見られてもよい。つまり、第１のＲＳ符号語生成装置６０３と第２のＲＳ符号語生成装置６０５は、これらのデータを誤り訂正可能な形式に符号化する装置であるといえる。【０１６９】
この実施例では、メッセージを多項式の係数に埋め込んでいる。多項式の係数に埋め込んだ情報を求める方法としては、連立方程式を解く方法などがある。【０１７０】
以上説明したように、第２の実施例では、
各符号化メッセージ情報Ｖｉ（ｉ＝１，２，・・・，ｎ）と、
ランダムに選択したｅと、
から一意に導き出される
ｘｉ（ｉ＝１，２，・・・，ｎ）
を求め、
ランダムなｔ次多項式Ｃｓに、ｘｉを代入して、Ｃｓ（ｘｉ）を求め、
Ｃｅ（０）＝ｅとなるランダムなｔ次多項式にｉを代入して、Ｃｅ（ｉ）を求め、
Ｃｓ（ｘｉ）とＣｅ（ｉ）からなる値を、各Ｖｉに対する、不正チャンネル特定情報Ａｉとする。【０１７１】
その際、任意のｖｉ，ｖｊについて、
ｖｉ≠ｖｊであれば、
ｘｉ≠ｘｊ
が十分に高い確率で成立するように、
まず、ランダムな値ｅを用いて、
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝  （ｉ＝１，２，・・・，ｎ）
を計算し、
ｙｉを用いて、
ｘｉ＝ｐ＊（ｉ−１）＋ｙｉ  （ｉ＝１，２，・・・，ｎ）
を計算する。【０１７２】
符号化メッセージ情報のサイズを
ｐ＾Ｎ
とする本実施例では、符号化メッセージ情報と不正チャンネル特定情報のサイズを併せた集合のサイズが、
ｐ＾｛Ｎ＋１｝＊ｑ
となる。【０１７３】
また、改ざんされた符号化メッセージ情報が集合Ｌの元として出力される確率、つまり改ざんを検出できる確率は、
１−Ｎ／ｐ−１／ｑ
となる。【０１７４】
非特許文献２に開示された方式では、各チャンネルを通して送るデータのサイズは、
ｐ＾（Ｎ＊（ｔ＋ｄ’＋１）−ｄ’）
であることから、本実施例によれば、各チャンネルを通して送るデータのサイズが大幅に低減される。【０１７５】
第１の実施例では、符号化メッセージ情報のサイズｐと、不正検出確率１−１／ｑとの間に、
ｑ≧ｎ＊ｐ
という制約があった。【０１７６】
第２の実施例では、ｐを適切に選択することにより、符号化メッセージ情報のサイズと不正検出確率との間の制約を解消することができる。【０１７７】
つまり、メッセージ情報のサイズと不正検出確率との間の制約を解消することができる。【０１７８】
なお、発明を実施する最良の形態、第１の実施例、第２の実施例の説明では、すべてチャンネルを用いた場合の説明を行ったが、チャンネルを実現する手段は、送信装置の生成した複数のデータを分けて送信することができるものであればよい。【０１７９】
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2009020143.tif 000003
【図２】
2009020143.tif 000004
【図３】
2009020143.tif 000005
【図４】
2009020143.tif 000006
【図５】
2009020143.tif 000007
【図６】
2009020143.tif 000008
【図７】
2009020143.tif 000009
【図８】
2009020143.tif 000010
【図９】
2009020143.tif 000011
【図１０】
2009020143.tif 000012
【手続補正書】
【提出日】平成21年1月29日(2009.1.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（削除）
【請求項２】
（削除）
【請求項３】
（削除）
【請求項４】
（削除）
【請求項５】
（削除）
【請求項６】
（削除）
【請求項７】
（削除）
【請求項８】
（削除）
【請求項９】
（削除）
【請求項１０】
（削除）
【請求項１１】
（削除）
【請求項１２】
（削除）
【請求項１３】
（削除）
【請求項１４】
（削除）
【請求項１５】
（削除）
【請求項１６】
（削除）
【請求項１７】
（削除）
【請求項１８】
（削除）
【請求項１９】
（削除）
【請求項２０】
（削除）
【請求項２１】
（削除）
【請求項２２】
（削除）
【請求項２３】
（削除）
【請求項２４】
（削除）
【請求項２５】
（削除）
【請求項２６】
（削除）
【請求項２７】
（削除）
【請求項２８】
（削除）
【請求項２９】
（削除）
【請求項３０】
（削除）
【請求項３１】
（削除）
【請求項３２】
（削除）
【請求項３３】
（削除）
【請求項３４】
（削除）
【請求項３５】
（削除）
【請求項３６】
情報をｃ個の分散情報に符号化し、そのうち任意のａ個以上の分散情報からは秘密情報が完全に復元できるが、ａ−ｂ−１個までの分散情報からでは秘密情報に関する情報は全く得られないという（ａ，ｂ，ｃ）しきい値法を用い、
想定不正チャンネル数をｔとし、
チャンネル数ｎ＝３ｔ＋ｄ＋１（ｄ≧０）
を満たす数のチャンネルで受信装置と接続する送信装置であって、
ｄ’を、ｄ≧ｄ’≧０であるような値として、
メッセージを（２ｔ＋ｄ’＋１，ｄ’＋ｔ，ｎ）しきい値法（上記（ａ，ｂ，ｃ）しきい値法のａを２ｔ＋ｄ’＋１、ｂをｄ’＋ｔ、ｃをｎとする）を用いて、ｎ個の符号化メッセージ情報Ｖｉ（但し、ｉ＝１，・・・，ｎ）を生成する手段と、
前記ｎ個の符号化メッセージ情報Ｖｉとｔ次多項式とを用いて、ｎ個の符号化メッセージ情報Ｖｉのうちｔ個以下のものに誤りがある場合にリード・ソロモン誤り訂正処理による誤りの検出および訂正を可能とする不正チャンネル特定情報ＡｉをＶｉ（但し、ｉ＝１，・・・，ｎ）に対応付けて生成し、対応するチャンネルからＶｉとＡｉ（但し、ｉ＝１，・・・，ｎ）を送信する手段と、
を備えている、ことを特徴とする送信装置。
【請求項３７】
メッセージのデータ集合に有限体ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）を用い（但し、ｐは素数の冪乗であり、素数そのものである場合もある）、
ＧＦ（ｐ＾｛ｄ’＋ｔ＋１｝）の要素であるメッセージｓをＧＦ（ｐ）によって、（ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝）と表し、
ＧＦ（ｐ）上の定数項からｄ’＋ｔ次の項までの係数が、それぞれ、ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝である２ｔ＋ｄ’次多項式を、ランダムに生成し、２ｔ＋ｄ’次多項式をｆｓ（ｘ）として、ｆｓ（１），ｆｓ（２），．．，ｆｓ（ｎ）をそれぞれ計算し、
計算結果と入力ｉとのペアＶｉ＝（ｉ，ｖｉ）（但し、ｉ＝１，２，．．，ｎ、ｖｉ＝ｆｓ（ｉ））を、符号化メッセージ情報としてそれぞれのチャンネルに出力する、ことを特徴とする請求項３６記載の送信装置。
【請求項３８】
請求項３６又は３７記載の前記送信装置で生成された符号化メッセージ情報Ｖｉと不正チャンネル特定情報Ａｉ（但し、ｉ＝１，・・・，ｎ）をそれぞれチャンネルを介して受信し、ＶｉとＡｉ（但し、ｉ＝１，・・・，ｎ）を用いてリード・ソロモン誤り訂正処理を行って、ｎ個のＶｉそれぞれについて不正な値であるか否かを判断する手段と、
不正であると判断されなかったＶｉがすべて同じメッセージの符号語であるかを調べ、同じメッセージの符号語である場合には、前記メッセージを出力し、異なるメッセージの符号語が含まれている場合には、メッセージの受信失敗を表す記号を出力する手段と、
を備えている、ことを特徴とする受信装置。
【請求項３９】
メッセージｓ、チャンネル数ｎ、想定不正チャンネル数ｔが入力されると、ＧＦ（ｐ＾Ｎ）上の定数項からｄ’＋ｔ次の項までの係数がそれぞれ、ｓ＿１，・・・，ｓ＿｛ｄ’＋ｔ＋１｝である２ｔ＋ｄ’次多項式をランダムに生成し、２ｔ＋ｄ’次多項式をｆｓ（ｘ）として、ｆｓ（１），ｆｓ（２），．．，ｆｓ（ｎ）を計算し、計算結果ｆｓ（ｉ）と入力ｉとのペアＶｉ＝（ｉ，ｖｉ）（但し、ｉ＝１，・・・，ｎ，ｖｉ＝ｆｓ（ｉ））を符号化メッセージ情報（但し、符号化メッセージ情報ｖｉは、ＧＦ（ｐ）の要素によって（ｖ｛ｉ，０｝，・・・，ｖ｛ｉ，Ｎ−１｝）と表せる）として生成するメッセージ符号化手段と、
チャンネル数ｎおよび想定不正チャンネル数ｔ、Ｖｉ＝（ｉ，ｖ｛ｉ，０｝，・・・，ｖ｛ｉ，Ｎ−１｝）（但し、ｉ＝１，・・・，ｎ）を入力し、ＧＦ（ｐ）上でランダムにｅを選択し、ＧＦ（ｐ）上で、
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１｝ｅ＾｛Ｎ−１｝（但し、ｉ＝１，・・・，ｎ）
を計算し、ｑ≧ｎ＊ｐとなるｑに対し、ＧＦ（ｑ）上で、
ｘｉ＝ｐ＊（ｉ−１）＋ｙｉ（但し、ｉ＝１，・・・，ｎ）
を計算する符号化メッセージ情報変換手段と、
ＧＦ（ｑ）上のランダムなデータｅ０，ｅ１，・・・，ｅｔを生成するリード・ソロモン情報源生成手段と、
ｘｉ（但し、ｉ＝１，・・・，ｎ）とｅ０，ｅ１，・・・，ｅｔとから、ＧＦ（ｑ）上で、
Ｃｓ（ｘｉ）＝ｅ０＋ｅ１＊ｘｉ＋ｅ２＊ｘｉ＾２＋・・・＋ｅｔ＊ｘｉ＾ｔ（但し、ｉ＝１，・・・，ｎ）
を計算する第１のリード・ソロモン符号語生成手段と、
ＧＦ（ｐ）上のランダムなデータｒ１，・・・，ｒｔを選択する第２の情報源生成手段と、
ｅとｒ１，・・・，ｒｔとを取得し、ＧＦ（ｑ）上で、
Ｃｅ（ｘｉ）＝ｅ＋ｒ１＊ｉ＋ｒ２＊ｉ＾２＋・・・＋ｒｔ＊ｉ＾ｔ（但し、ｉ＝１，・・・，ｎ）を計算する第２のリード・ソロモン符号語生成手段と、
を備え、
Ｃｓ（ｘｉ）と、Ｃｅ（ｉ）とからなるＡｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））（但し、ｉ＝１，・・・，ｎ）が、符号化メッセージ情報ｖｉに対応する不正チャンネル特定情報とＡｉを生成し、それぞれチャンネルに供給する、ことを特徴とする請求項３６記載の送信装置。
【請求項４０】
請求項３９記載の前記送信装置で生成された符号化メッセージ情報Ｖｉおよびそれらに対応する不正チャンネル特定情報Ａｉ＝（Ｃｓ（ｘｉ），Ｃｅ（ｉ））（但し、ｉ＝１，・・・，ｎ）をチャンネルを介して入力し、
符号語（Ｃｓ（ｘ１），・・・，Ｃｓ（ｘｎ））に対してリード・ソロモン誤り訂正処理を実行し、ｅ０，ｅ１，・・・，ｅｔを復元する第１のリード・ソロモン誤り訂正手段と、
符号語（Ｃｅ（１），・・・，Ｃｅ（ｎ））に対してリード・ソロモン誤り訂正処理を実行し、ｅを復元する第２のリード・ソロモン誤り訂正手段と、
ＧＦ（ｐ）上で
ｙｉ＝ｖ｛ｉ，０｝＋ｖ｛ｉ，１｝＊ｅ＋ｖ｛ｉ，２｝＊ｅ＾２＋・・・＋ｖ｛ｉ，Ｎ−１）ｅ＾｛Ｎ−１｝（但し、ｉ＝１，・・・，ｎ）
を計算し、
さらにＧＦ（ｑ）上で、
ｘ｛ｉ｝＝ｐ＊（ｉ−１）＋ｙｉ（但し、ｉ＝１，・・・，ｎ）
を計算し、
Ｃｅ（ｉ）＝ｅ０＋ｅ１＊ｘ｛ｉ｝＋ｅ２＊ｘ｛ｉ｝＾２＋・・・＋ｅｔ＊ｘ｛ｉ｝＾ｔ
が成立しないｉの集合Ｌを不正チャンネルリストとして出力する不正チャンネル特定手段と、
を備えている、ことを特徴とする受信装置。
【請求項４１】
想定不正チャンネル数をｔとし、ｎ個のメッセージｍの符号語と、ｎ個の不正符号語特定データを出力する符号化装置であって、
メッセージが埋め込まれた有限体上のｎ−（ｔ＋１）次多項式Ｆを生成し、前記多項式上の点をメッセージの符号語としてｎ個生成するメッセージ符号化部と、
前記メッセージの符号語を入力として有限体上のｔ次多項式Ｇを生成し、前記メッセージの符号語のそれぞれが有限体上で異なる値となるように加工処理を行い、前記加工処理後の値を前記ｔ次多項式Ｇに入力したときの出力を不正符号語特定データとして前記メッセージの符号語と対応させて生成する不正符号語特定データ生成部と、
を備え、前記メッセージの符号語と前記不正符号語特定データを出力する、ことを特徴とする符号化装置。
【請求項４２】
請求項４１に記載の符号化装置から出力される前記メッセージの符号語と前記不正符号語特定用データと、チャンネル数ｎと想定不正チャンネル数ｔとを入力としメッセージを出力する復号化装置であって、
前記不正符号語特定データに対して誤り訂正処理を行い、前記誤り訂正処理後の不正符号語特定データより、前記不正符号語特定データが生成されたｔ次多項式の復元処理を行い、
すべてのメッセージの符号語について復元されたｔ次多項式に、前記符号化装置が行った加工と同じ仕方で加工処理を行い、前記加工処理後の値を復元したｔ次多項式に入力した値が加工前のメッセージの符号語と対応する不正符号語特定データと等しいか否かの判定処理を行い、等しいと判定されたすべてのメッセージの符号語のリストを出力する不正符号化メッセージ判定部と、
前記不正符号化メッセージ判定部が出力したリストに含まれるメッセージの符号語がすべて同一のメッセージの符号語であるか否かを判定し、すべてが同一のメッセージの符号語であると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、それ以外の場合には、復号失敗を表す出力を行うメッセージ復号部と、
を備えている、ことを特徴とする復号化装置。
【請求項４３】
請求項４１に記載の符号化装置と、請求項４２に記載の復号化装置と備えた伝送システム。
【請求項４４】
想定不正チャンネル数をｔとし、ｎ個のメッセージｍの符号語と、ｎ個の不正符号語特定データを出力する符号化方法であって、
メッセージが埋め込まれた有限体上のｎ−（ｔ＋１）次多項式Ｆを生成し、前記多項式上の点をメッセージの符号語としてｎ個生成し、
前記メッセージの符号語を入力として有限体上のｔ次多項式Ｇを生成し、前記メッセージの符号語のそれぞれが有限体上で異なる値となるように加工処理を行い、前記加工処理後の値を前記ｔ次多項式Ｇに入力したときの出力を不正符号語特定データとしてメッセージの符号語と対応させて生成し、
前記メッセージの符号語と前記不正符号語特定データを出力する、ことを特徴とする符号化方法。
【請求項４５】
請求項４４に記載の符号化方法から出力される前記メッセージの符号語と前記不正符号語特定用データと、チャンネル数ｎと想定不正チャンネル数ｔとを入力としメッセージを出力する復号化方法であって、
前記不正符号語特定データに対して誤り訂正処理を行い、前記誤り訂正処理後の不正符号語特定データより、前記不正符号語特定データが生成されたｔ次多項式の復元処理を行い、
すべてのメッセージの符号語について復元されたｔ次多項式に、前記符号化装置が行った加工と同じ仕方で加工処理を行い、前記加工処理後の値を復元したｔ次多項式に入力した値が加工前のメッセージの符号語と対応する不正符号語特定データと等しいか否かの判定処理を行い、等しいと判定されたすべてのメッセージの符号語のリストを生成し、
前記リストに含まれるメッセージの符号語がすべて同一のメッセージの符号語であるか否かを判定し、
すべてが同一のメッセージの符号語であると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、
それ以外の場合には、復号失敗を表す出力を行う、
ことを特徴とする復号化方法。
【請求項４６】
請求項４４に記載の符号化方法と、請求項４５に記載の復号化方法と、を含む伝送方法。
【請求項４７】
想定不正チャンネル数をｔとし、ｎ個のメッセージｍの符号語と、ｎ個の不正符号語特定データを出力する符号化装置を構成するコンピュータに、
メッセージが埋め込まれた有限体上のｎ−（ｔ＋１）次多項式Ｆを生成し、前記多項式上の点をメッセージの符号語としてｎ個生成するメッセージ符号処理と、
メッセージの符号語を入力として有限体上のｔ次多項式Ｇを生成し、メッセージの符号語のそれぞれが有限体上で異なる値となるように加工処理を行い、前記加工処理後の値を前記ｔ次多項式Ｇに入力したときの出力を不正符号語特定データとしてメッセージの符号語と対応させて生成する不正符号語特定データ生成処理と、
前記メッセージの符号語と前記不正符号語特定データを出力する処理と、
を実行させる符号化プログラム。
【請求項４８】
請求項４７に記載の符号化装置から出力される前記メッセージの符号語と前記不正符号語特定用データと、チャンネル数ｎと想定不正チャンネル数ｔとを入力としメッセージを出力する復号化装置を構成するコンピュータに、
前記不正符号語特定データに対して誤り訂正処理を行い、前記誤り訂正処理後の不正符号語特定データより、前記不正符号語特定データが生成されたｔ次多項式の復元処理を行い、
すべてのメッセージの符号語について復元されたｔ次多項式に、前記符号化装置が行った加工と同じ仕方で加工処理を行い、前記加工処理後の値を復元したｔ次多項式に入力した値が加工前のメッセージの符号語と対応する不正符号語特定データと等しいか否かの判定処理を行い、等しいと判定されたすべてのメッセージの符号語のリストを出力する不正符号化メッセージ判定処理と、
前記不正符号化メッセージ判定処理によって出力された前記リストに含まれるメッセージの符号語がすべて同一のメッセージの符号語であるか否かを判定し、すべてが同一のメッセージの符号語であると判定された場合、不正がないと判定された符号語よりメッセージを復号して出力し、それ以外の場合には、復号失敗を表す出力を行うメッセージ復号処理と、
を実行させる復号化プログラム。
【請求項４９】
請求項４７に記載の符号化プログラムと、請求項４８に記載の復号化プログラムと、を備えた伝送プログラム。
【国際調査報告】
2009020143.tif 000013
2009020143.tif 000014