情報ベクトル符号化装置、情報ベクトル復元装置、情報ベクトル符号化方法、情報ベクトル復元方法およびプログラム
【課題】任意の線形符号を対象とし、簡易な構成で強い秘密保護特性を有する情報ベクトル符号化装置等を提供する。
【解決手段】任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。
【解決手段】任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意の線形符号を対象とし、簡易な構成で強い秘密保護特性を有する情報ベクトル符号化装置、情報ベクトル復元装置、情報ベクトル符号化方法、情報ベクトル復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、秘密分散法を既存の誤り訂正符号を元にして構成する手法（「秘密分散符号」と呼ぶ）が注目を浴びている（例えば、非特許文献１から５を参照。）。秘密分散符号では、元となった既存の誤り訂正符号の特徴を生かすことができ、分散情報の生成・秘密情報の復元に符号化器や復号器をそのまま利用することや、誤り訂正処理によって分散情報の改ざんを検知・訂正することなどが可能となる。
【０００３】
非特許文献１に示すように、ＭｃＥｌｉｅｃｅらは、Ｓｈａｍｉｒの多項式補間によるしきい値法（非特許文献６参照）が、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号で構成可能なことを初めて指摘した。さらに、非特許文献３に示すように、Ｐｉｅｐｒｙｚｋらは、しきい値法が最大距離分離符号（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ；ＭＤＳ符号）から構成できることを指摘している。
【０００４】
ここで、ＭＤＳ符号はＳｉｎｇｌｅｔｏｎ限界を達成し、代数符号として理想的な性質を有しているが、最大符号長(分散情報の最大数)が有限体の大きさで制限されるなどの制約を有する。
【０００５】
また、しきい値型以外のアクセス構造を有する秘密分散法は、単純にＭＤＳ符号を用いて構成することはできない。そこで、非特許文献４に示すように、Ｍａｓｓｅｙ は、ＭｃＥｌｉｅｃｅらの結果を一般の線形符号での構成へ拡張した。また、非特許文献５に示すように、ｄｅｌａ Ｃｒｕｚらは、一要素の秘密情報を対象としたＭａｓｓｅｙの構成を複数要素で構成されるベクトルを対象とする構成へ拡張した。
【０００６】
一方、非特許文献６に示される旧来の多項式補間によるしきい値法において、複数の情報(ベクトル)を符号化する手法は、「ランプ型しきい値法」と呼ばれる。ランプ型しきい値法は、複数の情報をまとめて処理してしまうことで、通信帯域やストレージ利用量の削減が可能となるが、しきい値未満の個数の分散情報から情報ベクトルそのものは、復号不可能でも、ベクトルの要素の一部は一意に復号可能である可能性を持つ。また、ベクトルそのものが復号不可能な手法（要素のうち１つも確定的には復号できない手法）は、「強い秘密保護特性を有するランプ型しきい値法」と呼ばれる。非特許文献２に示すように、Ｎｉｓｈｉａｒａらは、多項式補間で実現可能な強いランプ型しきい値法の構成手法を示した。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｒ.Ｊ.ＭｃＥｌｉｅｃｅ ａｎｄ Ｄ.Ｖ.Ｓａｒｗａｔｅ、 “Ｏｎ ｓｈａｒｉｎｇ ｓｅｃｒｅｔｓ ａｎｄ Ｒｅｅｄ−Ｓｏｌｏｍｏｎ ｃｏｄｅｓ、” Ｃｏｍｍｕｎ。 ＡＣＭ 、ｖｏｌ. ２４、ｎｏ. ９、ｐｐ. ５８３−５８４、１９８１.
【非特許文献２】Ｍ. Ｎｉｓｈｉａｒａ ａｎｄ Ｋ. Ｔａｋｉｚａｗａ、“Ｓｔｒｏｎｇｌｙ ｓｅｃｕｒｅ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ ｓｃｈｅｍｅ ｗｉｔｈ ｒａｍｐ ｔｈｒｅｓｈｏｌｄ ｂａｓｅｄ ｏｎ Ｓｈａｍｉｒ‘ｓ ｐｏｌｙｎｏｍｉａｌ ｉｎｔｅｒｐｏｌａｔｉｏｎ ｓｃｈｅｍｅ、” ＩＥＩＣＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｆｕｎｄａｍｅｎｔａｌｓ、 ｖｏｌ. Ｊ９２−Ａ、ｎｏ. １２、ｐｐ. １００９−１０１３、２００９.
【非特許文献３】Ｊ. Ｐｉｅｐｒｚｙｋ ａｎｄ Ｘ.−Ｍ. Ｚｈａｎｇ、“Ｉｄｅａｌ ｔｈｒｅｓｈｏｌｄ ｓｃｈｅｍｅｓ ｆｒｏｍ ＭＤＳ ｃｏｄｅｓ、” ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＣＩＳＣ ２００２、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、ｐｐ. ２５３−２６３, Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２００２.
【非特許文献４】Ｊ. Ｌ. Ｍａｓｓｅｙ、“Ｓｏｍｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｃｏｄｉｎｇ ｔｈｅｏｒｙ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｙ、” ｉｎ Ｃｏｄｅｓ ａｎｄ Ｃｉｐｈｅｒｓ．Ｃｒｙｐｔｏｇｒａｐｈｙ ａｎｄ Ｃｏｄｉｎｇ ＩＶ、ｐｐ. ３３−４７、１９９５.
【非特許文献５】Ｒ. ｄｅｌａ Ｃｒｕｚ、Ａ. Ｍｅｙｅｒ、ａｎｄ Ｐ. Ｓｏｌｅ、 “Ａｎ ｅｘｔｅｎｓｉｏｎ ｏｆ Ｍａｓｓｅｙ ｓｃｈｅｍｅ ｆｏｒ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ、”ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＥＥＥ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ Ｗｏｒｋｓｈｏｐ（ＩＴＷ ２０１０）、ｐｐ. １−５、２０１０.
【非特許文献６】Ａ. Ｓｈａｍｉｒ、“Ｈｏｗ ｔｏ ｓｈａｒｅ ａ ｓｅｃｒｅｔ、” Ｃｏｍｍｕｎ. ＡＣＭ 、ｖｏｌ. ２２、ｎｏ. １１、ｐｐ. ６１２−６１３、１９７９.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、今までに提案された秘密分散符号は、秘密保護特性が保証されているものの特定の符号（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ（ＲＳ）符号や、ＲＳ符号を含む最大距離分離（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ；ＭＤＳ）符号を元とした特殊な構成であったり、任意の線形符号を元としているものの強い秘密保護特性が保証できない構成であるという問題がある。また、ｄｅｌａ Ｃｒｕｚらの構成では、一般の線形符号を利用して情報ベクトルを対象としているが、その手法は強い秘密保護特性を有してはいない。例えば、情報ベクトルの要素ひとつたりとも復号させたくない場合でも、その一部の要素は一意に復号可能となる場合があるという問題がある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、任意の線形符号を対象とし、簡易な構成で強い秘密保護特性を有する情報ベクトル符号化装置、情報ベクトル復元装置、情報ベクトル符号化方法、情報ベクトル復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【００１１】
（１）本発明は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、符号化器によりｎ個の符号語シンボルを出力する情報ベクトル符号化装置であって、前記符号化器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器（例えば、図２の部分行列Ａ選択器２１０に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器（例えば、図２の行基本変形器２２０に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器（例えば、図２の列交換器２３０に相当）とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する情報ベクトル符号化装置を提案している。
【００１２】
この発明によれば、符号化器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。したがって、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。
【００１３】
（２）本発明は、（１）の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、復号器により、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、前記復号器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器（例えば、図２の部分行列Ａ選択器２１０に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器（例えば、図２の行基本変形器２２０に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器（例えば、図２の列交換器２３０に相当）とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置を提案している。
【００１４】
この発明によれば、復号器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００１５】
（３）本発明は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う正則行列Ｑ乗算器（例えば、図６の正則行列Ｑ乗算器４１０に相当）と、前記正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する任意の[ｌ＋ｎ、ｋ]線形符号Ｃの符号化器（例えば、図６の符号化器４２０に相当）と、を備えたことを特徴とする情報ベクトル符号化装置を提案している。
【００１６】
この発明によれば、正則行列Ｑ乗算器は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う。任意の[ｌ＋ｎ、ｋ]線形符号Ｃの符号化器は、正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。したがって、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。
【００１７】
（４）本発明は、（３）の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する復号器（例えば、図８の復号器５１０に相当）と、該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する逆行列Ｑ−１乗算器（例えば、図８の逆行列Ｑ−１乗算器５２０に相当）と、を備えたことを特徴とする情報ベクトル復元装置を提案している。
【００１８】
この発明によれば、復号器は、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する。逆行列Ｑ−１乗算器は、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【００１９】
（５）本発明は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法であって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図３のステップＳ１０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図３のステップＳ１０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップ（例えば、図３のステップＳ１０４に相当）と、からなることを特徴とする情報ベクトル符号化方法を提案している。
【００２０】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。したがって、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。
【００２１】
（６）本発明は、（５）の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図５のステップＳ２０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図５のステップＳ２０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図５のステップＳ２０３に相当）と、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップ（例えば、図５のステップＳ２０４に相当）と、からなることを特徴とする情報ベクトル復元方法を提案している。
【００２２】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００２３】
（７）本発明は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップ（例えば、図７のステップＳ３０１に相当）と、前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップ（例えば、図７のステップＳ３０２に相当）と、からなることを特徴とする情報ベクトル符号化方法を提案している。
【００２４】
この発明によれば、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行い、線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。したがって、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。
【００２５】
（８）本発明は、（７）の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップ（例えば、図９のステップＳ４０１に相当）と、該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップ（例えば、図９のステップＳ４０２に相当）と、からなることを特徴とする情報ベクトル復元方法を提案している。
【００２６】
この発明によれば、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力し、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【００２７】
（９）本発明は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法をコンピュータに実行させるためのプログラムであって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図３のステップＳ１０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図３のステップＳ１０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップ（例えば、図３のステップＳ１０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２８】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。したがって、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。
【００２９】
（１０）本発明は、（９）のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図５のステップＳ２０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図５のステップＳ２０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図５のステップＳ２０３に相当）と、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップ（例えば、図５のステップＳ２０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３０】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００３１】
（１１）本発明は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップ（例えば、図７のステップＳ３０１に相当）と、前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップ（例えば、図７のステップＳ３０２に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３２】
この発明によれば、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行い、線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。したがって、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。
【００３３】
（１２）本発明は、（１１）のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップ（例えば、図９のステップＳ４０１に相当）と、該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップ（例えば、図９のステップＳ４０２に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３４】
この発明によれば、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力し、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【発明の効果】
【００３５】
本発明によれば、種々の線形符号を利用して強い秘密保護特性を持つ秘密分散符号が構成可能である。このため利用する符号に応じて、高速な符号化や復号が可能になったり、長い符号長の符号を利用することで、有限体の大きさに比べて非常に多くの分散情報が生成可能であったり、符号の誤り訂正能力を利用した分散情報の改ざん検知などが可能となる。
【図面の簡単な説明】
【００３６】
【図１】本発明の第１の実施形態に係る情報ベクトル符号化装置の構成を示す図である。
【図２】本発明の第１の実施形態に係る符号変換装置の構成を示す図である。
【図３】本発明の第１の実施形態に係る情報ベクトル符号化装置の処理を示す図である。
【図４】本発明の第１の実施形態に係る情報ベクトル復元装置の構成を示す図である。
【図５】本発明の第１の実施形態に係る情報ベクトル復元装置の処理を示す図である。
【図６】本発明の第２の実施形態に係る情報ベクトル符号化装置の構成を示す図である。
【図７】本発明の第２の実施形態に係る情報ベクトル符号化装置の処理を示す図である。
【図８】本発明の第２の実施形態に係る情報ベクトル復元装置の構成を示す図である。
【図９】本発明の第２の実施形態に係る情報ベクトル復元装置の処理を示す図である。
【発明を実施するための形態】
【００３７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３８】
＜第１の実施形態＞
図１から図５を用いて、本発明の第１の実施形態について説明する。
【００３９】
＜情報ベクトル符号化装置の構成＞
図１に示すように、本実施形態に係る情報ベクトル符号化装置は、符号化器１００からなり、符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。
【００４０】
＜符号変換装置の構成＞
図２に示すように、本実施形態に係る符号変換装置２００は、部分行列Ａ選択器２０１と、行基本変形器２０２と、列交換器２０３とから構成されている。
【００４１】
部分行列Ａ選択器２０１は、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する。行基本変形器２０２は、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。列交換器２０３は、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する。
【００４２】
＜情報ベクトル符号化装置の処理＞
図３を用いて、情報ベクトル符号化装置の処理について説明する。
【００４３】
まず、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し（ステップＳ１０１）、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する（ステップＳ１０２）。
【００４４】
そして、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し（ステップＳ１０３）、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する（ステップＳ１０４）。
【００４５】
＜情報ベクトル復元装置の構成＞
図４に示すように、本実施形態に係る情報ベクトル復元装置は、復号器３００からなり、符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。
【００４６】
＜情報ベクトル復元装置の処理＞
図５を用いて、情報ベクトル復元装置の処理について説明する。
【００４７】
まず、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し（ステップＳ２０１）、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する（ステップＳ２０２）。
【００４８】
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し（ステップＳ２０３）、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する（ステップＳ２０４）。
【００４９】
以上、説明したように、本実施形態によれば、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。また、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００５０】
＜第２の実施形態＞
図６から図９を用いて、本発明の第２の実施形態について説明する。
【００５１】
＜情報ベクトル符号化装置の構成＞
図６に示すように、本実施形態に係る情報ベクトル符号化装置は、正則行列Ｑ乗算器４１０と、符号化器４２０とから構成されている。
【００５２】
正則行列Ｑ乗算器４１０は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う。符号化器４２０は、正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。
【００５３】
＜情報ベクトル符号化装置の処理＞
図７を用いて、情報ベクトル符号化装置の処理について説明する。
【００５４】
まず、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う（ステップＳ３０１）。そして、線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する（ステップＳ３０２）。
【００５５】
＜情報ベクトル復元装置の構成＞
図８に示すように、本実施形態に係る情報ベクトル復元装置は、復号器５１０と、逆行列Ｑ−１乗算器５２０とから構成されている。
【００５６】
復号器５１０は、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する。逆行列Ｑ−１乗算器５２０は、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。
【００５７】
＜情報ベクトル復元装置の処理＞
図９を用いて、情報ベクトル復元装置の処理について説明する。
【００５８】
まず、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する（ステップＳ４０１）。そして、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する（ステップＳ４０２）。
【００５９】
以上、説明したように、本実施形態によれば、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。また、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【００６０】
＜実施例＞
本発明を具体的に説明するために、以下に、本発明の１実施例を示す。
【００６１】
＜記号の定義＞
まず、Ｆｑを位数ｑを有する有限体とする。このとき、ｑは、素数の累乗である。また、ベクトルｖ＝ [ｖ１、・・・、ｖｎ] ∈Ｆｎｑの非ゼロの要素のインデックスの集合ｓｕｐｐｏｒｔを数１のように定義する。
【００６２】
【数１】
【００６３】
また、ベクトルｖのハミング重みを数２と定義する。
【００６４】
【数２】
【００６５】
また、［ｎ、ｋ］線形記号Ｃは、Ｆｎｑのｋ次元線形部分空間で定義される。［ｎ、ｋ］線形記号Ｃを生成する生成行列Ｇ∈Ｆｋ×ｎｑの各行は、［ｎ、ｋ］線形記号Ｃの基底を成す。［ｎ、ｋ］線形記号Ｃの双対符号Ｃ⊥を数３と定義する。
【００６６】
【数３】
【００６７】
また、Ｃのｒ次一般化ハミング重み(Ｇｅｎｅｒａｌｉｚｅｄ Ｈａｍｍｉｎｇ Ｗｅｉｇｈｔ, ＧＨＷ）は、数４で定義される。
【００６８】
【数４】
【００６９】
ここで、ｓｕｐｐ（Ｄ）は、ｓｕｐｐ（Ｄ）＝｛ｉ：∃［ｘ１、・・・、ｘｎ］∈Ｄ、ｘｉ≠０｝で定義される。｛ｄｒ：ｒ＝１、・・・、ｋ｝を［ｎ、ｋ］線形符号ＣのＨａｍｍｉｎｇ Ｗｅｉｇｈｔ Ｈｉｅｒａｒｃｈｙ（ＨＷＨ）と呼び、ｄｅ＋１（Ｃ）＝ｎ−ｋ＋ｅ＋１を満たす最小のｅをＣのＭＤＳ−ｒａｎｋと呼ぶ。ｉ＝１、・・・、ｋについて、
μｉ（Ｃ）＝ｎ−ｋ＋ｉ−ｄｉ（Ｃ）をＣのｄｅｆｅｃｔと呼ぶ。
【００７０】
＜秘密分散符号＞
数５を秘匿する情報ベクトルとする（１≦ｌ≦ｋ）ＣをＦｑ上の[ｌ＋ｎ、ｋ]線形符号とする。また、Ｃの生成行列を数６と表す。このとき、数７は、Ｇのｉ列目（１≦ｉ≦ｌ＋ｎ）であり、数８と仮定する。
【００７１】
【数５】
【００７２】
【数６】
【００７３】
【数７】
【００７４】
【数８】
【００７５】
ベクトルｓをＧを用いて符号化する際、まず、∀ｉ＝１、・・・、ｌについて、数９を満たす数１０をランダムに選択する。ＧがＧ＝［Ｉｋ Ｘ］という形で表される組織的生成行列の場合、数１１のｋ−１次元乱数ベクトルを用いて、数１２のように構成すればよい。ここで、Ｉｋ は、ｋ×ｋ単位行列である。
【００７６】
【数９】
【００７７】
【数１０】
【００７８】
【数１１】
【００７９】
【数１２】
【００８０】
次いで、ベクトルｕから数１３に示す符号語を生成する。そして、符号語シンボルｃｌ＋１、・・・、ｃｌ＋ｎを伝送路を通して、受信者へ送信する、あるいは、ｎ人の管理者に分散情報として保管させる。以降、基本として、この構成を用いる。
【００８１】
【数１３】
【００８２】
＜アンチアクセス集合＞
まず、秘密分散の分散情報の集合について、アンチアクセス集合（Ａｎｔｉ−Ａｃｃｅｓｓ Ｓｔｒｕｃｔｕｒｅ）と強い秘密保護特性（Ｓｔｒｏｎｇｌｙ−Ｓｅｃｕｒｅ） を以下に定義する。
【００８３】
＜定義１；アンチアクセス集合＞
Ｓ１，・・・、ＳｌをＦｑ上の統計的に独立かつ一様分布に従う確率変数とする。このとき、Ｓ１，・・・、Ｓｌ のとる実現値をｓ１，・・・、ｓｌと表す。また、ｃｌ＋１、・・・、ｃｌ＋ｎをＦｑ上の確率変数とし、各々の実現値をｃｌ＋１、・・・、ｃｌ＋ｎと表す。インデックスの集合Ｘに対する確率変数の集合｛Ｃｉ：ｉ∈Ｘ｝をＣｘのように表す。
【００８４】
次に、Ｊ⊂Ａｓ．ｔ．、｜Ｊ｜＝βを定義する。[ｌ＋ｎ、ｋ] 線形符号Ｃで構成した秘密分散法においてＪが以下に定義する「強秘密保護特性」を満たすとき、Ｊを「アンチアクセス集合」と呼ぶ。
強秘密保護特性（Ｓｔｒｏｎｇｌｙ−Ｓｅｃｕｒｅ）；∀ｔ＝０、・・・、ｌ−１、∀Ｄ＝｛ｒ１、・・・、ｒβ−ｔ｝⊆Ｊ、∀ε＝｛ｉ１、・・・、ｉｔ＋１｝⊂｛１、・・・、ｌ｝において、Ｉ（Ｓε；ＣＤ）＝０が成立する。ここで、Ｉ（）は、相互情報量を示す。
【００８５】
＜定義２；ａ−強秘密保護特性を有する手法＞
[ｌ＋ｎ、ｋ] 線形符号Ｃで構成した秘密分散法において、∀Ｊ⊂Ａｓ．ｔ．、｜Ｊ｜＝ａが、アンチアクセス集合である時、その手法をａ−強秘密保護特性を有する手法と呼ぶ。ａ−強秘密保護特性を有する手法では、ａ個以下の符号語シンボルから、ベクトルｓの１つの要素たりとも確定的に復号されることがないという特性が保証される。ａ−強秘密保護特性を有するしきい値型ライクなアクセス構造を以下に定義する。
【００８６】
＜定義３；ａ−強秘密保護特性を有するしきい値型ライクなアクセス構造＞
ａ−強秘密保護特性を有するしきい値型ライクなアクセス構造は、以下の性質を満たす。
１．可用性:∀Ｉ⊆Ａｓ．ｔ．、｜Ｉ｜≧Ｔについて、ＢＩより一意にベクトルｓを復号可能である。
２．秘匿性: ∀Ｉ⊆Ａｓ．ｔ．、｜Ｉ｜≧ａは、定義１のアンチアクセス集合となる。
【００８７】
＜構成＞
任意の[ｌ＋ｎ、ｋ] 線形符号Ｃを変換し、定義３を満たす秘密分散符号を構成する。ここで、Ｃの生成行列を数１４と表す。また、Ｃの双対符号Ｃ⊥のＨＷＨを{ｄｉ(Ｃ⊥) ＝ｋ＋ｉ−μｉ(Ｃ⊥) :ｉ＝１、・・・、ｋ}、ＭＤＳ−ｒａｎｋをｅと表す。
【００８８】
【数１４】
【００８９】
以下の手法で、Ｇを変換しＧｔ、すなわちＣを変換しＣｔを得る。
１．Ｇの任意のｋ＋ｅ列を選択し、部分行列Ａを構成する。Ｇの行を入れ替えて、Ｇ´＝[Ａ Ｂ]とする。(先頭ｋ＋ｅ 列でよい)
２．[Ａ Ｉｋ]を行基本変形することで得られる行列を[ＡＲＲＥ Ｑ]とする。このとき、Ｉｋはｋ×ｋ単位行列であり、ＡＲＲＥは、Ａを行基本変形して得られる被約階段行列である。また、数１５に示す関係がある。
【００９０】
【数１５】
【００９１】
３．Ｇ′′＝ＧＧ′＝[ＡＲＲＥ ＱＢ]を得る。
４．Ｇ′′のブロック行列ＡＲＲＥの内部で列交換を行い、Ａ´ＲＲＥ＝[Ｉｋ Ｘ]を得る。このとき、数１６の関係がある。
【００９２】
【数１６】
【００９３】
５．Ｇｔ＝[Ａ´ＲＲＥ ＱＢ]＝[Ｉｋ Ｘ ＱＢ]とする。このＧｔによる符号Ｃｔで構成される秘密分散符号は、パラメータＴ＝ｋ＋ｅ、ａ＝ｄｌ(Ｃ⊥)−２において、定義３を満たす。すなわち、任意のｋ＋ｅ 個の符号語シンボル（分散情報）から、復号処理によってベクトルｓを復号可能できる。また、任意のｄｌ(Ｃ⊥)−２個未満の符号語シンボル（分散情報）からは、ベクトルｓの一要素たりとも確定的に復号されてしまうことはない。
【００９４】
なお、情報ベクトル符号化装置あるいは情報ベクトル復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを情報ベクトル符号化装置あるいは情報ベクトル復元装置に読み込ませ、実行することによって本発明の情報ベクトル符号化装置あるいは情報ベクトル復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００９５】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００９６】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００９７】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。例えば、復号アルゴリズムに関しては特に言及しなかったが、例えば、シンドローム復号や最尤復号等を用いてもよいが、これに限られるものではない。
【符号の説明】
【００９８】
１００；符号化器
２００；符号変換装置
２１０；部分行列Ａ選択器
２２０；行基本変形器
２３０；列交換器
３００；復号器
４１０；正則行列Ｑ乗算器
４２０；符号化器
５１０；復号器
５２０；正則行列Ｑ−１乗算器
【技術分野】
【０００１】
本発明は、任意の線形符号を対象とし、簡易な構成で強い秘密保護特性を有する情報ベクトル符号化装置、情報ベクトル復元装置、情報ベクトル符号化方法、情報ベクトル復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、秘密分散法を既存の誤り訂正符号を元にして構成する手法（「秘密分散符号」と呼ぶ）が注目を浴びている（例えば、非特許文献１から５を参照。）。秘密分散符号では、元となった既存の誤り訂正符号の特徴を生かすことができ、分散情報の生成・秘密情報の復元に符号化器や復号器をそのまま利用することや、誤り訂正処理によって分散情報の改ざんを検知・訂正することなどが可能となる。
【０００３】
非特許文献１に示すように、ＭｃＥｌｉｅｃｅらは、Ｓｈａｍｉｒの多項式補間によるしきい値法（非特許文献６参照）が、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号で構成可能なことを初めて指摘した。さらに、非特許文献３に示すように、Ｐｉｅｐｒｙｚｋらは、しきい値法が最大距離分離符号（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ；ＭＤＳ符号）から構成できることを指摘している。
【０００４】
ここで、ＭＤＳ符号はＳｉｎｇｌｅｔｏｎ限界を達成し、代数符号として理想的な性質を有しているが、最大符号長(分散情報の最大数)が有限体の大きさで制限されるなどの制約を有する。
【０００５】
また、しきい値型以外のアクセス構造を有する秘密分散法は、単純にＭＤＳ符号を用いて構成することはできない。そこで、非特許文献４に示すように、Ｍａｓｓｅｙ は、ＭｃＥｌｉｅｃｅらの結果を一般の線形符号での構成へ拡張した。また、非特許文献５に示すように、ｄｅｌａ Ｃｒｕｚらは、一要素の秘密情報を対象としたＭａｓｓｅｙの構成を複数要素で構成されるベクトルを対象とする構成へ拡張した。
【０００６】
一方、非特許文献６に示される旧来の多項式補間によるしきい値法において、複数の情報(ベクトル)を符号化する手法は、「ランプ型しきい値法」と呼ばれる。ランプ型しきい値法は、複数の情報をまとめて処理してしまうことで、通信帯域やストレージ利用量の削減が可能となるが、しきい値未満の個数の分散情報から情報ベクトルそのものは、復号不可能でも、ベクトルの要素の一部は一意に復号可能である可能性を持つ。また、ベクトルそのものが復号不可能な手法（要素のうち１つも確定的には復号できない手法）は、「強い秘密保護特性を有するランプ型しきい値法」と呼ばれる。非特許文献２に示すように、Ｎｉｓｈｉａｒａらは、多項式補間で実現可能な強いランプ型しきい値法の構成手法を示した。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｒ.Ｊ.ＭｃＥｌｉｅｃｅ ａｎｄ Ｄ.Ｖ.Ｓａｒｗａｔｅ、 “Ｏｎ ｓｈａｒｉｎｇ ｓｅｃｒｅｔｓ ａｎｄ Ｒｅｅｄ−Ｓｏｌｏｍｏｎ ｃｏｄｅｓ、” Ｃｏｍｍｕｎ。 ＡＣＭ 、ｖｏｌ. ２４、ｎｏ. ９、ｐｐ. ５８３−５８４、１９８１.
【非特許文献２】Ｍ. Ｎｉｓｈｉａｒａ ａｎｄ Ｋ. Ｔａｋｉｚａｗａ、“Ｓｔｒｏｎｇｌｙ ｓｅｃｕｒｅ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ ｓｃｈｅｍｅ ｗｉｔｈ ｒａｍｐ ｔｈｒｅｓｈｏｌｄ ｂａｓｅｄ ｏｎ Ｓｈａｍｉｒ‘ｓ ｐｏｌｙｎｏｍｉａｌ ｉｎｔｅｒｐｏｌａｔｉｏｎ ｓｃｈｅｍｅ、” ＩＥＩＣＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｆｕｎｄａｍｅｎｔａｌｓ、 ｖｏｌ. Ｊ９２−Ａ、ｎｏ. １２、ｐｐ. １００９−１０１３、２００９.
【非特許文献３】Ｊ. Ｐｉｅｐｒｚｙｋ ａｎｄ Ｘ.−Ｍ. Ｚｈａｎｇ、“Ｉｄｅａｌ ｔｈｒｅｓｈｏｌｄ ｓｃｈｅｍｅｓ ｆｒｏｍ ＭＤＳ ｃｏｄｅｓ、” ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＣＩＳＣ ２００２、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、ｐｐ. ２５３−２６３, Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、２００２.
【非特許文献４】Ｊ. Ｌ. Ｍａｓｓｅｙ、“Ｓｏｍｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｃｏｄｉｎｇ ｔｈｅｏｒｙ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｙ、” ｉｎ Ｃｏｄｅｓ ａｎｄ Ｃｉｐｈｅｒｓ．Ｃｒｙｐｔｏｇｒａｐｈｙ ａｎｄ Ｃｏｄｉｎｇ ＩＶ、ｐｐ. ３３−４７、１９９５.
【非特許文献５】Ｒ. ｄｅｌａ Ｃｒｕｚ、Ａ. Ｍｅｙｅｒ、ａｎｄ Ｐ. Ｓｏｌｅ、 “Ａｎ ｅｘｔｅｎｓｉｏｎ ｏｆ Ｍａｓｓｅｙ ｓｃｈｅｍｅ ｆｏｒ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ、”ｉｎ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ＩＥＥＥ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ Ｗｏｒｋｓｈｏｐ（ＩＴＷ ２０１０）、ｐｐ. １−５、２０１０.
【非特許文献６】Ａ. Ｓｈａｍｉｒ、“Ｈｏｗ ｔｏ ｓｈａｒｅ ａ ｓｅｃｒｅｔ、” Ｃｏｍｍｕｎ. ＡＣＭ 、ｖｏｌ. ２２、ｎｏ. １１、ｐｐ. ６１２−６１３、１９７９.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、今までに提案された秘密分散符号は、秘密保護特性が保証されているものの特定の符号（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ（ＲＳ）符号や、ＲＳ符号を含む最大距離分離（Ｍａｘｉｍｕｍ Ｄｉｓｔａｎｃｅ Ｓｅｐａｒａｂｌｅ；ＭＤＳ）符号を元とした特殊な構成であったり、任意の線形符号を元としているものの強い秘密保護特性が保証できない構成であるという問題がある。また、ｄｅｌａ Ｃｒｕｚらの構成では、一般の線形符号を利用して情報ベクトルを対象としているが、その手法は強い秘密保護特性を有してはいない。例えば、情報ベクトルの要素ひとつたりとも復号させたくない場合でも、その一部の要素は一意に復号可能となる場合があるという問題がある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、任意の線形符号を対象とし、簡易な構成で強い秘密保護特性を有する情報ベクトル符号化装置、情報ベクトル復元装置、情報ベクトル符号化方法、情報ベクトル復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【００１１】
（１）本発明は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、符号化器によりｎ個の符号語シンボルを出力する情報ベクトル符号化装置であって、前記符号化器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器（例えば、図２の部分行列Ａ選択器２１０に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器（例えば、図２の行基本変形器２２０に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器（例えば、図２の列交換器２３０に相当）とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する情報ベクトル符号化装置を提案している。
【００１２】
この発明によれば、符号化器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。したがって、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。
【００１３】
（２）本発明は、（１）の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、復号器により、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、前記復号器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器（例えば、図２の部分行列Ａ選択器２１０に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器（例えば、図２の行基本変形器２２０に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器（例えば、図２の列交換器２３０に相当）とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置を提案している。
【００１４】
この発明によれば、復号器が、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００１５】
（３）本発明は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う正則行列Ｑ乗算器（例えば、図６の正則行列Ｑ乗算器４１０に相当）と、前記正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する任意の[ｌ＋ｎ、ｋ]線形符号Ｃの符号化器（例えば、図６の符号化器４２０に相当）と、を備えたことを特徴とする情報ベクトル符号化装置を提案している。
【００１６】
この発明によれば、正則行列Ｑ乗算器は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う。任意の[ｌ＋ｎ、ｋ]線形符号Ｃの符号化器は、正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。したがって、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。
【００１７】
（４）本発明は、（３）の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する復号器（例えば、図８の復号器５１０に相当）と、該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する逆行列Ｑ−１乗算器（例えば、図８の逆行列Ｑ−１乗算器５２０に相当）と、を備えたことを特徴とする情報ベクトル復元装置を提案している。
【００１８】
この発明によれば、復号器は、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する。逆行列Ｑ−１乗算器は、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【００１９】
（５）本発明は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法であって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図３のステップＳ１０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図３のステップＳ１０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップ（例えば、図３のステップＳ１０４に相当）と、からなることを特徴とする情報ベクトル符号化方法を提案している。
【００２０】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。したがって、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。
【００２１】
（６）本発明は、（５）の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図５のステップＳ２０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図５のステップＳ２０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図５のステップＳ２０３に相当）と、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップ（例えば、図５のステップＳ２０４に相当）と、からなることを特徴とする情報ベクトル復元方法を提案している。
【００２２】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００２３】
（７）本発明は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップ（例えば、図７のステップＳ３０１に相当）と、前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップ（例えば、図７のステップＳ３０２に相当）と、からなることを特徴とする情報ベクトル符号化方法を提案している。
【００２４】
この発明によれば、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行い、線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。したがって、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。
【００２５】
（８）本発明は、（７）の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップ（例えば、図９のステップＳ４０１に相当）と、該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップ（例えば、図９のステップＳ４０２に相当）と、からなることを特徴とする情報ベクトル復元方法を提案している。
【００２６】
この発明によれば、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力し、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【００２７】
（９）本発明は、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法をコンピュータに実行させるためのプログラムであって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図３のステップＳ１０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図３のステップＳ１０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップ（例えば、図３のステップＳ１０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２８】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。したがって、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。
【００２９】
（１０）本発明は、（９）のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップ（例えば、図５のステップＳ２０１に相当）と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップ（例えば、図５のステップＳ２０２に相当）と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップ（例えば、図５のステップＳ２０３に相当）と、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップ（例えば、図５のステップＳ２０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３０】
この発明によれば、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。また、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００３１】
（１１）本発明は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップ（例えば、図７のステップＳ３０１に相当）と、前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップ（例えば、図７のステップＳ３０２に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３２】
この発明によれば、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行い、線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。したがって、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。
【００３３】
（１２）本発明は、（１１）のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップ（例えば、図９のステップＳ４０１に相当）と、該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップ（例えば、図９のステップＳ４０２に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００３４】
この発明によれば、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力し、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。したがって、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【発明の効果】
【００３５】
本発明によれば、種々の線形符号を利用して強い秘密保護特性を持つ秘密分散符号が構成可能である。このため利用する符号に応じて、高速な符号化や復号が可能になったり、長い符号長の符号を利用することで、有限体の大きさに比べて非常に多くの分散情報が生成可能であったり、符号の誤り訂正能力を利用した分散情報の改ざん検知などが可能となる。
【図面の簡単な説明】
【００３６】
【図１】本発明の第１の実施形態に係る情報ベクトル符号化装置の構成を示す図である。
【図２】本発明の第１の実施形態に係る符号変換装置の構成を示す図である。
【図３】本発明の第１の実施形態に係る情報ベクトル符号化装置の処理を示す図である。
【図４】本発明の第１の実施形態に係る情報ベクトル復元装置の構成を示す図である。
【図５】本発明の第１の実施形態に係る情報ベクトル復元装置の処理を示す図である。
【図６】本発明の第２の実施形態に係る情報ベクトル符号化装置の構成を示す図である。
【図７】本発明の第２の実施形態に係る情報ベクトル符号化装置の処理を示す図である。
【図８】本発明の第２の実施形態に係る情報ベクトル復元装置の構成を示す図である。
【図９】本発明の第２の実施形態に係る情報ベクトル復元装置の処理を示す図である。
【発明を実施するための形態】
【００３７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３８】
＜第１の実施形態＞
図１から図５を用いて、本発明の第１の実施形態について説明する。
【００３９】
＜情報ベクトル符号化装置の構成＞
図１に示すように、本実施形態に係る情報ベクトル符号化装置は、符号化器１００からなり、符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する。
【００４０】
＜符号変換装置の構成＞
図２に示すように、本実施形態に係る符号変換装置２００は、部分行列Ａ選択器２０１と、行基本変形器２０２と、列交換器２０３とから構成されている。
【００４１】
部分行列Ａ選択器２０１は、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する。行基本変形器２０２は、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する。列交換器２０３は、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する。
【００４２】
＜情報ベクトル符号化装置の処理＞
図３を用いて、情報ベクトル符号化装置の処理について説明する。
【００４３】
まず、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し（ステップＳ１０１）、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する（ステップＳ１０２）。
【００４４】
そして、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し（ステップＳ１０３）、変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する（ステップＳ１０４）。
【００４５】
＜情報ベクトル復元装置の構成＞
図４に示すように、本実施形態に係る情報ベクトル復元装置は、復号器３００からなり、符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。
【００４６】
＜情報ベクトル復元装置の処理＞
図５を用いて、情報ベクトル復元装置の処理について説明する。
【００４７】
まず、任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成し（ステップＳ２０１）、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する（ステップＳ２０２）。
【００４８】
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力し（ステップＳ２０３）、変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する（ステップＳ２０４）。
【００４９】
以上、説明したように、本実施形態によれば、任意のｄ１(Ｃ⊥)−２個の符号語シンボルからは情報ベクトルの要素一つたりとも確定的に復号することができないという強い秘密保護特性を有する。ここで、ｄ１(Ｃ⊥)は符号Ｃ⊥の１次一般化ハミング重みを表す。また、Ｃの生成行列Ｇをパラメタｅによって基本変形することによって、変換された行列Ｇｔを得る。Ｇｔによって生成される符号Ｃ‘を利用することで、任意のｋ＋ｅ個の符号語シンボルからは情報ベクトルが復号可能である。
【００５０】
＜第２の実施形態＞
図６から図９を用いて、本発明の第２の実施形態について説明する。
【００５１】
＜情報ベクトル符号化装置の構成＞
図６に示すように、本実施形態に係る情報ベクトル符号化装置は、正則行列Ｑ乗算器４１０と、符号化器４２０とから構成されている。
【００５２】
正則行列Ｑ乗算器４１０は、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う。符号化器４２０は、正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する。
【００５３】
＜情報ベクトル符号化装置の処理＞
図７を用いて、情報ベクトル符号化装置の処理について説明する。
【００５４】
まず、l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う（ステップＳ３０１）。そして、線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する（ステップＳ３０２）。
【００５５】
＜情報ベクトル復元装置の構成＞
図８に示すように、本実施形態に係る情報ベクトル復元装置は、復号器５１０と、逆行列Ｑ−１乗算器５２０とから構成されている。
【００５６】
復号器５１０は、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する。逆行列Ｑ−１乗算器５２０は、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する。
【００５７】
＜情報ベクトル復元装置の処理＞
図９を用いて、情報ベクトル復元装置の処理について説明する。
【００５８】
まず、ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する（ステップＳ４０１）。そして、ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する（ステップＳ４０２）。
【００５９】
以上、説明したように、本実施形態によれば、符号そのものを変換せずに、既存のＣの符号化器の前処理によって強い秘密保護特性を得ることができる。また、符号そのものを変換せずに、既存のＣの復号器の後処理によって強い秘密保護特性を得ることができる。
【００６０】
＜実施例＞
本発明を具体的に説明するために、以下に、本発明の１実施例を示す。
【００６１】
＜記号の定義＞
まず、Ｆｑを位数ｑを有する有限体とする。このとき、ｑは、素数の累乗である。また、ベクトルｖ＝ [ｖ１、・・・、ｖｎ] ∈Ｆｎｑの非ゼロの要素のインデックスの集合ｓｕｐｐｏｒｔを数１のように定義する。
【００６２】
【数１】
【００６３】
また、ベクトルｖのハミング重みを数２と定義する。
【００６４】
【数２】
【００６５】
また、［ｎ、ｋ］線形記号Ｃは、Ｆｎｑのｋ次元線形部分空間で定義される。［ｎ、ｋ］線形記号Ｃを生成する生成行列Ｇ∈Ｆｋ×ｎｑの各行は、［ｎ、ｋ］線形記号Ｃの基底を成す。［ｎ、ｋ］線形記号Ｃの双対符号Ｃ⊥を数３と定義する。
【００６６】
【数３】
【００６７】
また、Ｃのｒ次一般化ハミング重み(Ｇｅｎｅｒａｌｉｚｅｄ Ｈａｍｍｉｎｇ Ｗｅｉｇｈｔ, ＧＨＷ）は、数４で定義される。
【００６８】
【数４】
【００６９】
ここで、ｓｕｐｐ（Ｄ）は、ｓｕｐｐ（Ｄ）＝｛ｉ：∃［ｘ１、・・・、ｘｎ］∈Ｄ、ｘｉ≠０｝で定義される。｛ｄｒ：ｒ＝１、・・・、ｋ｝を［ｎ、ｋ］線形符号ＣのＨａｍｍｉｎｇ Ｗｅｉｇｈｔ Ｈｉｅｒａｒｃｈｙ（ＨＷＨ）と呼び、ｄｅ＋１（Ｃ）＝ｎ−ｋ＋ｅ＋１を満たす最小のｅをＣのＭＤＳ−ｒａｎｋと呼ぶ。ｉ＝１、・・・、ｋについて、
μｉ（Ｃ）＝ｎ−ｋ＋ｉ−ｄｉ（Ｃ）をＣのｄｅｆｅｃｔと呼ぶ。
【００７０】
＜秘密分散符号＞
数５を秘匿する情報ベクトルとする（１≦ｌ≦ｋ）ＣをＦｑ上の[ｌ＋ｎ、ｋ]線形符号とする。また、Ｃの生成行列を数６と表す。このとき、数７は、Ｇのｉ列目（１≦ｉ≦ｌ＋ｎ）であり、数８と仮定する。
【００７１】
【数５】
【００７２】
【数６】
【００７３】
【数７】
【００７４】
【数８】
【００７５】
ベクトルｓをＧを用いて符号化する際、まず、∀ｉ＝１、・・・、ｌについて、数９を満たす数１０をランダムに選択する。ＧがＧ＝［Ｉｋ Ｘ］という形で表される組織的生成行列の場合、数１１のｋ−１次元乱数ベクトルを用いて、数１２のように構成すればよい。ここで、Ｉｋ は、ｋ×ｋ単位行列である。
【００７６】
【数９】
【００７７】
【数１０】
【００７８】
【数１１】
【００７９】
【数１２】
【００８０】
次いで、ベクトルｕから数１３に示す符号語を生成する。そして、符号語シンボルｃｌ＋１、・・・、ｃｌ＋ｎを伝送路を通して、受信者へ送信する、あるいは、ｎ人の管理者に分散情報として保管させる。以降、基本として、この構成を用いる。
【００８１】
【数１３】
【００８２】
＜アンチアクセス集合＞
まず、秘密分散の分散情報の集合について、アンチアクセス集合（Ａｎｔｉ−Ａｃｃｅｓｓ Ｓｔｒｕｃｔｕｒｅ）と強い秘密保護特性（Ｓｔｒｏｎｇｌｙ−Ｓｅｃｕｒｅ） を以下に定義する。
【００８３】
＜定義１；アンチアクセス集合＞
Ｓ１，・・・、ＳｌをＦｑ上の統計的に独立かつ一様分布に従う確率変数とする。このとき、Ｓ１，・・・、Ｓｌ のとる実現値をｓ１，・・・、ｓｌと表す。また、ｃｌ＋１、・・・、ｃｌ＋ｎをＦｑ上の確率変数とし、各々の実現値をｃｌ＋１、・・・、ｃｌ＋ｎと表す。インデックスの集合Ｘに対する確率変数の集合｛Ｃｉ：ｉ∈Ｘ｝をＣｘのように表す。
【００８４】
次に、Ｊ⊂Ａｓ．ｔ．、｜Ｊ｜＝βを定義する。[ｌ＋ｎ、ｋ] 線形符号Ｃで構成した秘密分散法においてＪが以下に定義する「強秘密保護特性」を満たすとき、Ｊを「アンチアクセス集合」と呼ぶ。
強秘密保護特性（Ｓｔｒｏｎｇｌｙ−Ｓｅｃｕｒｅ）；∀ｔ＝０、・・・、ｌ−１、∀Ｄ＝｛ｒ１、・・・、ｒβ−ｔ｝⊆Ｊ、∀ε＝｛ｉ１、・・・、ｉｔ＋１｝⊂｛１、・・・、ｌ｝において、Ｉ（Ｓε；ＣＤ）＝０が成立する。ここで、Ｉ（）は、相互情報量を示す。
【００８５】
＜定義２；ａ−強秘密保護特性を有する手法＞
[ｌ＋ｎ、ｋ] 線形符号Ｃで構成した秘密分散法において、∀Ｊ⊂Ａｓ．ｔ．、｜Ｊ｜＝ａが、アンチアクセス集合である時、その手法をａ−強秘密保護特性を有する手法と呼ぶ。ａ−強秘密保護特性を有する手法では、ａ個以下の符号語シンボルから、ベクトルｓの１つの要素たりとも確定的に復号されることがないという特性が保証される。ａ−強秘密保護特性を有するしきい値型ライクなアクセス構造を以下に定義する。
【００８６】
＜定義３；ａ−強秘密保護特性を有するしきい値型ライクなアクセス構造＞
ａ−強秘密保護特性を有するしきい値型ライクなアクセス構造は、以下の性質を満たす。
１．可用性:∀Ｉ⊆Ａｓ．ｔ．、｜Ｉ｜≧Ｔについて、ＢＩより一意にベクトルｓを復号可能である。
２．秘匿性: ∀Ｉ⊆Ａｓ．ｔ．、｜Ｉ｜≧ａは、定義１のアンチアクセス集合となる。
【００８７】
＜構成＞
任意の[ｌ＋ｎ、ｋ] 線形符号Ｃを変換し、定義３を満たす秘密分散符号を構成する。ここで、Ｃの生成行列を数１４と表す。また、Ｃの双対符号Ｃ⊥のＨＷＨを{ｄｉ(Ｃ⊥) ＝ｋ＋ｉ−μｉ(Ｃ⊥) :ｉ＝１、・・・、ｋ}、ＭＤＳ−ｒａｎｋをｅと表す。
【００８８】
【数１４】
【００８９】
以下の手法で、Ｇを変換しＧｔ、すなわちＣを変換しＣｔを得る。
１．Ｇの任意のｋ＋ｅ列を選択し、部分行列Ａを構成する。Ｇの行を入れ替えて、Ｇ´＝[Ａ Ｂ]とする。(先頭ｋ＋ｅ 列でよい)
２．[Ａ Ｉｋ]を行基本変形することで得られる行列を[ＡＲＲＥ Ｑ]とする。このとき、Ｉｋはｋ×ｋ単位行列であり、ＡＲＲＥは、Ａを行基本変形して得られる被約階段行列である。また、数１５に示す関係がある。
【００９０】
【数１５】
【００９１】
３．Ｇ′′＝ＧＧ′＝[ＡＲＲＥ ＱＢ]を得る。
４．Ｇ′′のブロック行列ＡＲＲＥの内部で列交換を行い、Ａ´ＲＲＥ＝[Ｉｋ Ｘ]を得る。このとき、数１６の関係がある。
【００９２】
【数１６】
【００９３】
５．Ｇｔ＝[Ａ´ＲＲＥ ＱＢ]＝[Ｉｋ Ｘ ＱＢ]とする。このＧｔによる符号Ｃｔで構成される秘密分散符号は、パラメータＴ＝ｋ＋ｅ、ａ＝ｄｌ(Ｃ⊥)−２において、定義３を満たす。すなわち、任意のｋ＋ｅ 個の符号語シンボル（分散情報）から、復号処理によってベクトルｓを復号可能できる。また、任意のｄｌ(Ｃ⊥)−２個未満の符号語シンボル（分散情報）からは、ベクトルｓの一要素たりとも確定的に復号されてしまうことはない。
【００９４】
なお、情報ベクトル符号化装置あるいは情報ベクトル復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを情報ベクトル符号化装置あるいは情報ベクトル復元装置に読み込ませ、実行することによって本発明の情報ベクトル符号化装置あるいは情報ベクトル復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００９５】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００９６】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００９７】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。例えば、復号アルゴリズムに関しては特に言及しなかったが、例えば、シンドローム復号や最尤復号等を用いてもよいが、これに限られるものではない。
【符号の説明】
【００９８】
１００；符号化器
２００；符号変換装置
２１０；部分行列Ａ選択器
２２０；行基本変形器
２３０；列交換器
３００；復号器
４１０；正則行列Ｑ乗算器
４２０；符号化器
５１０；復号器
５２０；正則行列Ｑ−１乗算器
【特許請求の範囲】
【請求項１】
ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、符号化器によりｎ個の符号語シンボルを出力する情報ベクトル符号化装置であって、
前記符号化器が、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する情報ベクトル符号化装置。
【請求項２】
前記請求項１の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、復号器により、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、
前記復号器が、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置。
【請求項３】
l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う正則行列Ｑ乗算器と、
前記正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する任意の[ｌ＋ｎ、ｋ]線形符号Ｃの符号化器と、
を備えたことを特徴とする情報ベクトル符号化装置。
【請求項４】
前記請求項３の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、
前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する復号器と、
該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する逆行列Ｑ−１乗算器と、
を備えたことを特徴とする情報ベクトル復元装置。
【請求項５】
ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法であって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップと、
からなることを特徴とする情報ベクトル符号化方法。
【請求項６】
前記請求項５の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップと、
からなることを特徴とする情報ベクトル復元方法。
【請求項７】
l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップと、
前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップと、
からなることを特徴とする情報ベクトル符号化方法。
【請求項８】
前記請求項７の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、
前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップと、
該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップと、
からなることを特徴とする情報ベクトル復元方法。
【請求項９】
ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法をコンピュータに実行させるためのプログラムであって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１０】
前記請求項９のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１１】
l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップと、
前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１２】
前記請求項１１のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、
前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップと、
該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１】
ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、符号化器によりｎ個の符号語シンボルを出力する情報ベクトル符号化装置であって、
前記符号化器が、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する情報ベクトル符号化装置。
【請求項２】
前記請求項１の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、復号器により、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、
前記復号器が、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する部分行列選択器と、部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する行基本変形器と、被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する列交換器とからなる符号変換装置より得られる変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置。
【請求項３】
l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う正則行列Ｑ乗算器と、
前記正則行列Ｑ乗算器において線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する任意の[ｌ＋ｎ、ｋ]線形符号Ｃの符号化器と、
を備えたことを特徴とする情報ベクトル符号化装置。
【請求項４】
前記請求項３の情報ベクトル符号化装置により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元装置であって、
前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する復号器と、
該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する逆行列Ｑ−１乗算器と、
を備えたことを特徴とする情報ベクトル復元装置。
【請求項５】
ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法であって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップと、
からなることを特徴とする情報ベクトル符号化方法。
【請求項６】
前記請求項５の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップと、
からなることを特徴とする情報ベクトル復元方法。
【請求項７】
l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップと、
前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップと、
からなることを特徴とする情報ベクトル符号化方法。
【請求項８】
前記請求項７の情報ベクトル符号化方法により生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法であって、
前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップと、
該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップと、
からなることを特徴とする情報ベクトル復元方法。
【請求項９】
ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、ｎ個の符号語シンボルを出力する情報ベクトル符号化方法をコンピュータに実行させるためのプログラムであって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
前記変換符号Ｃｔの組織的生成行列Ｇｔによりｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを符号化して、ｎ個の符号語シンボルを出力する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１０】
前記請求項９のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、
任意の[ｌ＋ｎ、ｋ]線形符号Ｃの生成行列Ｇと、Ｃの双対符号Ｃ⊥のＭＤＳ−ｒａｎｋ ｅとを入力として部分行列［Ａ Ｂ］を構成する第１のステップと、
部分行列［Ａ Ｂ］を被約階段行列［ＡＲＲＥ ＱＢ］に変換する第２のステップと、
被約階段行列［ＡＲＲＥ ＱＢ］の列交換を行い、変換符号Ｃｔの組織的生成行列Ｇｔを出力する第３のステップと、
変換符号Ｃｔの組織的生成行列Ｇｔにより、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１１】
l次元情報ベクトルとｋ−ｌ次元乱数ベクトルとを入力とし、正則行列Ｑによる線形変換を行う第１のステップと、
前記線形変換したｋ次元ベクトルを入力し、ｎ個の符号語シンボルを出力する第２のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１２】
前記請求項１１のプログラムにより生成されたｎ個の符号語シンボルのうち、ｋ＋ｅ個の符号語シンボルを入力し、これをｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する情報ベクトル復元方法をコンピュータに実行させるためのプログラムであって、
前記ｋ＋ｅ個の符号語シンボルを入力し、ｋ次元ベクトルを出力する第１のステップと、
該ｋ次元ベクトルに正則行列Ｑの逆行列Ｑ−１を乗じて、ｌ次元情報ベクトルとｋ−ｌ次元乱数ベクトルに復号する第２のステップと、
をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−２４７５７５（Ｐ２０１２−２４７５７５Ａ）
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願番号】特願２０１１−１１８３５８（Ｐ２０１１−１１８３５８）
【出願日】平成２３年５月２６日（２０１１．５．２６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願日】平成２３年５月２６日（２０１１．５．２６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]