視覚復号型秘密分散方法および視覚復号型秘密分散システム
【課題】 各参加者が持たなければならない分散OHPシートの枚数を削減する視覚復号型秘密分散方法及びシステムを提供すること。
【解決手段】 秘密画像を分散する方法として，拡大体GF(2^m)上のShamirの(k,n)閾値法を用いる。秘密画像を拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルにおいて，黒ピクセル(p=1)の時の多項式f(0 ... 0)=(1 ... 1)，白ピクセル(p=0)の時の多項式f(0 ... 0)=(0 ... 0)となるような次数がk-1次のランダムな多項式f(x)を生成する。m枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルの色 p_1,...,p_m において多項式f(0 ... 0)=(p_1 ... p_m)となるような次数がk-1次のランダムな多項式f(x)を生成する。
【解決手段】 秘密画像を分散する方法として，拡大体GF(2^m)上のShamirの(k,n)閾値法を用いる。秘密画像を拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルにおいて，黒ピクセル(p=1)の時の多項式f(0 ... 0)=(1 ... 1)，白ピクセル(p=0)の時の多項式f(0 ... 0)=(0 ... 0)となるような次数がk-1次のランダムな多項式f(x)を生成する。m枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルの色 p_1,...,p_m において多項式f(0 ... 0)=(p_1 ... p_m)となるような次数がk-1次のランダムな多項式f(x)を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、視覚復号型秘密分散方法および視覚復号型秘密分散システムに関し，特にShamirの閾値法を用いて秘密画像を2枚以上の分散OHPシートに分散する視覚復号型秘密分散方法に関する。
【背景技術】
【０００２】
視覚復号型秘密分散方法は秘密分散方法の一つであり，正確には(k,n)閾値-視覚復号型秘密分散方法である。(k,n)閾値-視覚復号型秘密分散方法は分散対象となる秘密画像をn枚の分散OHPシートに分散し，その分散したn枚の分散OHPシートから任意のk(=<n)枚の分散OHPシートを重ね合わせることによって，元の秘密画像が復元して現れるが，任意のk-1枚以下の分散OHPシートから元の秘密画像を復元することができない性質を持つ。
【０００３】
従来より知られている(k,n)閾値-視覚復号型秘密分散方法では，以下の非特許文献１に開示されているようにコピー機の白黒反転機能を利用し，元の秘密画像を完全に再構成できる完全再構成(k,n)閾値-視覚復号型秘密分散方法がある。
【０００４】
【非特許文献１】S. Cimato, A. D. Santis, A. L. Ferrara, B. Masucci, Ideal contrast visual cryptography schemes with reversing, Information Processing Letters, vol. 93, Issue 4, 2005, pp. 199-206.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記した非特許文献1では，各参加者が持たなければならない分散OHPシートの枚数が2^{k-1}枚となる。つまり，分散する参加者の数k(=<n)が多くなるほど，各参加者が持たなければならない分散OHPシートの枚数が指数関数のように多くなってしまう。
【０００６】
また，秘密画像を2枚以上所有している場合においても，2枚以上の秘密画像を分散する際，秘密画像1枚毎に分散しなければならず，効率性が悪い。
【０００７】
そこで，本発明は，各参加者が持たなければならない分散OHPシートの枚数を削減する視覚復号型秘密分散方法を提供することを目的とする。
【０００８】
また，本発明は，分散OHPシートを再構成する場合の演算量を削減する視覚復号型秘密分散方法を提供することを目的とする。
【０００９】
さらに，本発明は，2枚以上の秘密画像を同時に効率よく分散できる視覚復号型秘密分散方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本件発明は、以下の特徴を有する課題を解決するための手段を採用している。
【００１１】
本発明に係る秘密画像を分散する方法の一態様による発明は，拡大体GF(2^m)上のShamirの(k,n)閾値法を用い，分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成される。
【００１２】
前記分散生成フェーズは，
前記分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成するステップと，
前記分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算するステップと，
前記分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するステップと，
前記分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色を、v_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成するステップと，
前記分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送るステップを有している。
【００１３】
前記復元フェーズは，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集めるステップと，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元するステップを有している。
【００１４】
ここで、拡大体GF(2^m)とは，集合の要素が2のガロア体GF(2)を拡大したものであり，2^m(2のm乗)の要素を持つガロア体である。ガロア体とは，集合の要素が有限で四則演算が閉じている集合である。尚、拡大体については，電子情報通信学会編者，黒澤 馨・尾形わかは著者，「現代暗号の基礎数理」4.5節 拡大体GF(2^m)，コロナ社に記載されている。
【００１５】
一方，Shamirの(k,n)閾値法は，分散対象となる秘密情報Sを，多項式f(0)=Sとなるような次数がk-1次のランダムな多項式f(x)を用いて，多項式上の点であるn個のシェアを生成し，生成したn個のシェアからk(=<n)個のシェアを用いて代数的に解くことにより，秘密情報Sを得る方法である。
【００１６】
１枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いるとき，秘密画像Iの各ピクセルにおいて，ピクセルが黒ピクセルの時の多項式f([0 ... 0])=([1 ... 1])，ピクセルが白ピクセルの時の多項式f([0 .. 0])=([0 ... 0])となるような次数がk-1次のランダムな多項式f(x)を生成する。N枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いるとき，N枚の秘密画像の各ピクセルの色p_1,...,p_Nにおいて，多項式f([0 ... 0])=([p_1 ... p_N])となるような次数がk-1次のランダムな多項式f(x)を生成する。
【００１７】
本発明に係る秘密画像を分散するシステムの一態様による発明は，
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成する視覚復号型秘密分散方法を利用している。
【００１８】
前記分散生成フェーズにおいて，
分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成する多項式生成手段と，
分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算する多項式計算手段と，
分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するバイナリ表現ベクトル変換手段と，
分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色をv_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成する分散OHPシート生成手段と，
分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送る送信手段を有している。
【００１９】
前記復元フェーズにおいて，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集める収集手段と，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元する復元手段を有している。
【発明の効果】
【００２０】
本発明によれば，拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて秘密画像を分散することにより，各参加者が持たなければならない分散OHPシートの枚数を削減することができる。
【００２１】
また本発明によれば，Shamirの(k,n)閾値法において，多項式f([0 ... 0])=([0 ... 0])または([1 ... 1])とすることにより，分散OHPシートを再構成する際の演算量を削減することができる。
【００２２】
さらに本発明によれば，Shamirの(k,n)閾値法において，多項式f([0 ... 0])=([p_1 ... p_N])とすることにより，N枚の画像を同時に効率よく分散することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明に係る拡大体GF(2^m)上のShamirの(k,n)閾値法を用いた視覚復号型秘密分散方法の実施の形態について詳細に説明する。ただし，2^m > n とする。
【００２４】
本発明では、秘密画像を分散する方法として，拡大体GF(2^m)上のShamirの(k,n)閾値法を用いる。秘密画像を拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルにおいて，黒ピクセル(p=1)の時の多項式f(0 ... 0)=(1 ... 1)，白ピクセル(p=0)の時の多項式f(0 ... 0)=(0 ... 0)となるような次数がk-1次のランダムな多項式f(x)を生成する。m枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルの色 p_1,...,p_m において多項式f(0 ... 0)=(p_1 ... p_m)となるような次数がk-1次のランダムな多項式f(x)を生成する。
【実施例１】
【００２５】
以下、本発明に係る視覚復号型秘密分散方法の第１の実施例について説明し、特に秘密画像を復元する際の演算量を削減するという本発明の効果をどのようにして得ているのかを詳細に説明する。ここで、前記視覚復号型秘密分散方法は、準備フェーズ、分散生成フェーズ、復元フェーズの３つのフェーズから成っている。以下、各フェーズについて順に説明する。
【００２６】
１．準備フェーズ
参加者n人，閾値k，拡大体GF(2^m)とする。秘密画像Iにはl(エル)ピクセルがある。
【００２７】
２．分散生成フェーズ
分散生成フェーズで用いる分散生成機構は図１に記載されている。分散生成機構は具体的には，前記分散生成フェーズで機能する多項式生成部，多項式計算部，バイナリ表現ベクトル変換部，分散OHPシート生成部，及び送信部で構成されている。復元機構は具体的には前記復元フェーズで機能する収集部及び復元部で構成されている。前記多項式生成部は秘密画像入力部を有しており、多項式計算部は分散OHPシート数入力部を有している。なお、多項式生成部，多項式計算部，バイナリ表現ベクトル変換部，分散OHPシート生成部での各動作については、分散OHPシート生成手段としての分散生成機構の中でそれぞれ以下に述べるような動作を行う。
【００２８】
前記多項式生成部は，分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成する。前記多項式計算部は，分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算する。前記バイナリ表現ベクトル変換部は，分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換する。前記分散OHPシート生成部は，分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色をv_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成する。前記送信手段は，分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送る。
【００２９】
前記収集部は，再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集める。前記復元部は，再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元する。
【００３０】
また，分散生成対象となる秘密画像（Ｉ）のサンプルを図２に示す。
【００３１】
(2-1).分散生成機構を用いる分散生成者は，秘密画像（Ｉ）の各ピクセル（ｊ）に対して，
ピクセル（ｊ）が黒ピクセル(p_j=1)の時の多項式f_j([0 ... 0])=([1 ... 1])，
ピクセル（ｊ）が白ピクセル(p_j=0)の時の多項式f_j([0 ... 0])=([0 ... 0])となるような
ランダムな拡大体GF(2^m)上のk-1次の多項式f_j(x)を生成する。
【００３２】
多項式f_j(x)は、以下の数式（１）のように表される。
【００３３】
f_j(x) = x^{k-1} a_1 + x^{k-2} a_2 + ... + x a_{k-1} + [b_1 ... b_m]・・・・（１）
ここで、a_1, ..., a_{k-1}は拡大体GF(2^m)上のランダムな係数であり，[b_1 ... b_m]は[0 ... 0]または[1 ... 1]である。
【００３４】
(2-2).分散生成機構を用いる分散生成者は，参加者iに対してi=1からnまで，さらに各ピクセル（ｊ）に対してj=1からlまで，上記第(2-1)項で生成した多項式f_j(x)から以下の数式（２）に従って拡大体GF(2^m)上で参加者iのシェアV_{j,i}を計算する。
【００３５】
V_{j,i} = f_j(i) = [v_{j,i,1} ... v_{j,i,m}]・・・・・・・・・・・・・・・・・・・（２）
参加者iのシェアV_{j,i}は拡大体GF(2^m)の要素であるから，v_{j,i,m}は0または1であり，0を白，1を黒とし（0を黒，1を白としてもよい），v_{i_j,1}を参加者iの1枚目の分散OHPシートのピクセル（ｊ）の色，v_{i_j,m}を参加者iのm枚目の分散OHPシートのピクセル（ｊ）の色として参加者iのm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を以下の数式（３）に従って生成する。なお、以下の数式（３）はS_{i,1}，.....，S_{i,m}のように合計m個の数式が存在している。
【００３６】
S_{i,1} = (v_{1,i,1} ... v_{l,i,1})，...
...，S_{i,m} = (v_{1,i,m} ... v_{l,i,m})・・・・・・・・・・・・・・・・（３）
具体例として，参加者がn=5，閾値がk=4，拡大体GF(2^4)で行われる時，5人の参加者のシェアを生成した4枚の分散OHPシートのサンプルを図３に示す。
【００３７】
(2-3).分散生成者は，i=1からnまで，m枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者iにそれぞれ渡す。
【００３８】
３．復元フェーズ
(3-1).再構成者はn人の参加者iがそれぞれ持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}のうち，k人分の分散OHPシートを集める。
【００３９】
(3-2).再構成者は3-1で集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて，秘密画像Iを復元する。
【００４０】
ここで、Lagrangeの補間公式とは，多項式の代数的解法を簡略化することができ，複数の離散データを与えるだけで複数の離散データを通る多項式が定まる。尚、Lagrangeの補間公式については，宮地充子・菊池浩明編著者，「IT Text 情報セキュリティ」，7.1節 秘密分散法，オーム社に記載されている。
【００４１】
拡大体GF(2^m)上のLagrangeの補間公式を用いた秘密画像の復元は以下の数式（４）に従って行われる。
【００４２】
[I_1 ... I_m]= f([0 ... 0])= lambda_1([0 ... 0]) * [S_{1,1} ... S_{1,m}] + ... + lambda_k([0 ... 0]) *[S_{k,1} ...S_{k,m}]=[c_1 ...c_m]・・・・・・・・・・・・・・・・・・（４）
なお、lambda_1([0 ... 0]), ..., lambda_k([0 ... 0])は拡大体GF(2^m)上のLagrange係数であり，S_{1,1} ... S_{1,m}, ..., S_{k,1} ... S_{k,m}はk人の参加者がそれぞれm枚持つ分散OHPシートであり，c_1,...,c_m はガロア体GF(2)上で計算されるS_{1,1},...,S_{k,m} のうちのいくつかの和であり，I_1,...,I_m はそれぞれ式 c_1,...,c_m によって復元される画像である。m個の式 c_1 ,..., c_m の中で，加算される項の数が最も少ない c_t を選択する。
【００４３】
ガロア体GF(2)上の式 I_t = c_t による分散OHPシートの重ね合せと白黒反転を用いた(分散OHPシートの)演算は、A XOR B = NOT(NOT(A) OR B) OR NOT(A OR NOT(B))に従って行われる。
【００４４】
ここで、XOR(排他的論理和)はガロア体GF(2)上の加算を示し、OR(論理和)は分散OHPシートの重ね合せを示し、NOT(否定)は分散OHPシートの白黒反転を示す。
【００４５】
ガロア体GF(2)上の式 I_t = c_tに沿って分散OHPシートの白黒反転と重ね合せを用いた演算によって，秘密画像Iと同じ画像I_tを得る。
【００４６】
具体例として，5人の参加者の中から参加者1，参加者2，参加者3，参加者4の分散OHPシートを集めて拡大体GF(2^4)上のLagrangeの補間公式による分散OHPシートの重ね合せと白黒反転を用いて秘密画像を復元する方法を図4に示す。図４に示すように加算される項目が最も少ないのはｃ2とｃ３の９項であるのでｃ2またはｃ３を選択してＩ2を復元すれば分散OHPシートを再構成する際の演算量を削減することができる。なお、図４ではｃ2を選択してＩ2を復元した例が示されている。
【実施例２】
【００４７】
以下、本発明に係る視覚復号型秘密分散方法の第２の実施例について説明し、特に２枚以上の秘密画像を同時に効率よく分散できるという本発明の効果をどのようにして得ているのかを詳細に説明する。ここで、前記視覚復号型秘密分散方法は、準備フェーズ、分散生成フェーズ、復元フェーズの３つのフェーズから成っている。以下、各フェーズについて順に説明する。
【００４８】
１．準備フェーズ
参加者n人，閾値k，拡大体GF(2^m)とする。N(=<m)枚の秘密画像I_1, ..., I_Nがあり，各々の秘密画像には以下の数式（５）を満足するl(エル)ピクセルがある。なお、以下の数式（５）はI_1，.....，I_Nのように合計N個の数式が存在している。
【００４９】
I_1 = (p_{1,1} ... p_{1,l})，...
...，I_N = (p_{N,1} ... p_{N,l})・・・・・・・・・・・・・・・・・（５）
ここで、p_{N,l}は0または1であり，0は白ピクセル，1は黒ピクセルに対応させる。
【００５０】
２．分散生成フェーズ
分散生成者は上記実施例１と同様，分散生成機構を用いてN枚の秘密画像I_Nの分散生成を行う。N<mのとき，I_{N+1} = I_1, ... , I_j = I_{j-N} ,..., I_m = I_{m-N} とすることで，ちょうどm枚の秘密画像を用意する。
【００５１】
(2-1).分散生成者は，m枚の秘密画像I_1, ... I_m の各ピクセルp_{1,1}, ..., p_{m,l}に対して，ランダムな拡大体GF(2^m)上のk-1次の多項式f_1(x), ..., f_l(x)を生成する。
【００５２】
多項式f_1(x), ..., f_l(x)は、以下の数式（６）のように表される。なお、以下の数式（６）はf_1(x) ，.....，f_l(x)のように合計l個の数式が存在している。
【００５３】
f_1(x) = x^{k-1} a_{1,1} + x^{k-2} a_{1,2} + ... + x a_{1,(k-1)} + [p_{1,1} ... p_{m,1}]，...
...，f_l(x) = x^{k-1} a_{l,1} + x^{k-2} a_{l,2} + ... + x a_{l,(k-1)} + [p_{1,l} ... p_{m,l}]
・・・・・（６）
ここで、a_{1,1}, ..., a_{l,(k-1)}は拡大体GF(2^m)上のランダムな係数である。
【００５４】
(2-2).分散生成者は，2-1で生成した多項式f_1(x), ..., f_l(x)で参加者iのシェアV_{1,i}, ..., V_{l,i}をi=1からnまで以下の数式（７）を満足するようにGF(2^m)上で計算する。なお、以下の数式（７）はf_1(x)，.....，f_l(x)のように合計l個の数式が存在している。
【００５５】
V_{1,i} = f_1(i) = [u_{1,i,1} ... u_{1,i,N}]，...
...，V_{l,i} = f_l(i) = [u_{l,i,1} ... u_{l,i,N}]・・・・・・・・・・・・・・・・（７）
(2-3).分散生成者は，参加者iのシェアV_{1,i}, ..., V_{l,i}を用いて，i=1からnまで以下の数式（８）に従って参加者iのm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を生成する。なお、以下の数式（８）はS_{i,1}, ..., S_{i,m}のように合計m個の数式が存在している。
【００５６】
S_{i,1} = (u_{1,i,1} ... u_{l,i,1})，...
...，S_{i,m} = (u_{1,i,m} ... u_{l,i,m})・・・・・・・・・・・・（８）
ここで、u_{l,i,N}は0または1であり，0を白ピクセル，1を黒ピクセルに対応させている。
【００５７】
S_{i,1}を参加者iの1枚目の分散OHPシートとし、S_{i,m}を参加者iのm枚目の分散OHPシートとする。
【００５８】
(2-4).分散生成者は，m枚の分散OHPシートS_{i,1}, ..., S_{i,m}をi=1からnまでの参加者iにそれぞれ渡す。
【００５９】
３．復元フェーズ
(3-1).再構成者は参加者iが持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}をk人分集める。
【００６０】
(3-2).再構成者は3-1で集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて，m枚の秘密画像I_mを復元する。
【００６１】
拡大体GF(2^m)上のLagrangeの補間公式を用いたm枚の秘密画像I_mの復元は、以下の数式（９）に従って行う。
【００６２】
[I_1 ... I_m] = f([0 ... 0]) = lambda_1([0 ... 0]) * [S_{1,1} ... S_{1,m}] + ... + lambda_k([0 ... 0]) * [S_{k,1} ... S_{k,m}] = [c_1 ... c_m]・・・・・・・・・・・・・・・・・・・・（９）
ここで、lambda_1([0 ... 0]), ..., lambda_k([0 ... 0])は拡大体GF(2^m)上のLagrange係数であり，S_{1,1} ... S_{1,m}, ..., S_{k,1} ... S_{k,m}はk人の参加者がそれぞれm枚持つ分散OHPシートであり，c_1,...,c_m はガロア体GF(2)上で計算される S_{1,1},...,S_{k,m} のうちのいくつかの和であり，I_1,...,I_m はそれぞれ式 c_1,...,c_m によって復元される画像である。
【００６３】
それぞれの秘密画像I_j (1=< j =< N) について，I_j = I_{j+N} = ... = I_{j+tN} ならば，c_j, c_{j+N}, ..., c_{j+tN} の中で加算される項の数が最も少ない c_{j'} を選択する。
【００６４】
ガロア体GF(2)上の式 I_j=c_{j'} による分散OHPシートの重ね合せと白黒反転を用いた(分散OHPシートの)演算は上記した実施例１と同様に行われる。
【００６５】
数式 I_j = c_{j'} に沿って分散OHPシートの白黒反転と重ね合せを用いた演算によって，N枚の秘密画像I_1, ..., I_Nを得る。
【００６６】
また、発明対象としては、上記視覚復号型秘密分散方法における各ステップをコンピュータに実行させるプログラムも含み、このプログラムはプログラムそのものであってもよいし、このプログラムがコンピュータで読み取り可能な記録媒体に格納されているものであってもよい。
【００６７】
本発明では、この記録媒体として、マイクロコンピュータで処理が行なわれるために必要なメモリ、例えばＲＯＭのようなものそのものがプログラムメディアであってもよいし、また、図示していない外部記憶装置としてプログラム読み取り装置が設けられ、そこに記録媒体を挿入することで読み取り可能なプログラムメディアであってもよい。いずれの場合においても、格納されているプログラムはマイクロコンピュータがアクセスして実行させる構成であってもよいし、あるいはいずれの場合もプログラムを読み出し、読み出されたプログラムは、マイクロコンピュータのプログラム記憶エリアにロードされて、そのプログラムが実行される方式であってもよい。このロード用のプログラムは予め本体装置に格納されているものとする。
【００６８】
ここで、上記プログラムメディアは、本体と分離可能に構成される記録媒体であり、磁気テープやカセットテープ等のテープ系、ＦＤ（フレキシブルディスク）やＨＤ（ハードディスク）等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ等の光ディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＲＯＭ等による半導体メモリを含めた固定的にプログラムを担持する媒体であってもよい。
【００６９】
また、本発明においては、インターネットを含む通信ネットワークと接続可能なシステム構成であることから、通信ネットワークからプログラムをダウンロードするように流動的にプログラムを担持する媒体であってもよい。なお、このように通信ネットワークからプログラムをダウンロードする場合には、そのダウンロード用プログラムは予め装置本体に格納しておくか、あるいは別の記録媒体からインストールされるものであってもよい。
【００７０】
さらに、本発明では、プログラム自体として、マイクロコンピュータで実行される処理そのものであってもよいし、あるいはインターネットを含む通信ネットワークとアクセスすることで取り込める、あるいは取り込めたものであってもよいし、こちらから送り出すものであってもよい。
【００７１】
また、上記した各実施の形態は、本発明を好適に実施した形態の一例に過ぎず、本発明は、その主旨を逸脱しない限り、種々変形して実施することが可能なものである。
【図面の簡単な説明】
【００７２】
【図１】視覚復号型秘密分散方法の分散生成機構の構成図である。
【図２】視覚復号型秘密分散方法において分散生成対象となる秘密画像のサンプル図である。
【図３】視覚復号型秘密分散方法の分散生成フェーズにおいて，参加者がn=5，閾値がk=4，拡大体GF(2^4)で行われる時，5人の参加者のシェアを生成した4枚の分散OHPシートのサンプル図である。
【図４】視覚復号型秘密分散方法の復元フェーズにおいて， 参加者がn=5，閾値がk=4，拡大体GF(GF2^4)で行われる時，5人の参加者の中から参加者1，参加者2，参加者3，参加者4の分散OHPシートを集めて拡大体GF(2^4)上のLagrangeの補間公式による分散OHPシートの重ね合せと白黒反転を用いて秘密画像を復元する方法を示す図である。
【技術分野】
【０００１】
本発明は、視覚復号型秘密分散方法および視覚復号型秘密分散システムに関し，特にShamirの閾値法を用いて秘密画像を2枚以上の分散OHPシートに分散する視覚復号型秘密分散方法に関する。
【背景技術】
【０００２】
視覚復号型秘密分散方法は秘密分散方法の一つであり，正確には(k,n)閾値-視覚復号型秘密分散方法である。(k,n)閾値-視覚復号型秘密分散方法は分散対象となる秘密画像をn枚の分散OHPシートに分散し，その分散したn枚の分散OHPシートから任意のk(=<n)枚の分散OHPシートを重ね合わせることによって，元の秘密画像が復元して現れるが，任意のk-1枚以下の分散OHPシートから元の秘密画像を復元することができない性質を持つ。
【０００３】
従来より知られている(k,n)閾値-視覚復号型秘密分散方法では，以下の非特許文献１に開示されているようにコピー機の白黒反転機能を利用し，元の秘密画像を完全に再構成できる完全再構成(k,n)閾値-視覚復号型秘密分散方法がある。
【０００４】
【非特許文献１】S. Cimato, A. D. Santis, A. L. Ferrara, B. Masucci, Ideal contrast visual cryptography schemes with reversing, Information Processing Letters, vol. 93, Issue 4, 2005, pp. 199-206.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記した非特許文献1では，各参加者が持たなければならない分散OHPシートの枚数が2^{k-1}枚となる。つまり，分散する参加者の数k(=<n)が多くなるほど，各参加者が持たなければならない分散OHPシートの枚数が指数関数のように多くなってしまう。
【０００６】
また，秘密画像を2枚以上所有している場合においても，2枚以上の秘密画像を分散する際，秘密画像1枚毎に分散しなければならず，効率性が悪い。
【０００７】
そこで，本発明は，各参加者が持たなければならない分散OHPシートの枚数を削減する視覚復号型秘密分散方法を提供することを目的とする。
【０００８】
また，本発明は，分散OHPシートを再構成する場合の演算量を削減する視覚復号型秘密分散方法を提供することを目的とする。
【０００９】
さらに，本発明は，2枚以上の秘密画像を同時に効率よく分散できる視覚復号型秘密分散方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本件発明は、以下の特徴を有する課題を解決するための手段を採用している。
【００１１】
本発明に係る秘密画像を分散する方法の一態様による発明は，拡大体GF(2^m)上のShamirの(k,n)閾値法を用い，分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成される。
【００１２】
前記分散生成フェーズは，
前記分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成するステップと，
前記分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算するステップと，
前記分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するステップと，
前記分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色を、v_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成するステップと，
前記分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送るステップを有している。
【００１３】
前記復元フェーズは，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集めるステップと，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元するステップを有している。
【００１４】
ここで、拡大体GF(2^m)とは，集合の要素が2のガロア体GF(2)を拡大したものであり，2^m(2のm乗)の要素を持つガロア体である。ガロア体とは，集合の要素が有限で四則演算が閉じている集合である。尚、拡大体については，電子情報通信学会編者，黒澤 馨・尾形わかは著者，「現代暗号の基礎数理」4.5節 拡大体GF(2^m)，コロナ社に記載されている。
【００１５】
一方，Shamirの(k,n)閾値法は，分散対象となる秘密情報Sを，多項式f(0)=Sとなるような次数がk-1次のランダムな多項式f(x)を用いて，多項式上の点であるn個のシェアを生成し，生成したn個のシェアからk(=<n)個のシェアを用いて代数的に解くことにより，秘密情報Sを得る方法である。
【００１６】
１枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いるとき，秘密画像Iの各ピクセルにおいて，ピクセルが黒ピクセルの時の多項式f([0 ... 0])=([1 ... 1])，ピクセルが白ピクセルの時の多項式f([0 .. 0])=([0 ... 0])となるような次数がk-1次のランダムな多項式f(x)を生成する。N枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いるとき，N枚の秘密画像の各ピクセルの色p_1,...,p_Nにおいて，多項式f([0 ... 0])=([p_1 ... p_N])となるような次数がk-1次のランダムな多項式f(x)を生成する。
【００１７】
本発明に係る秘密画像を分散するシステムの一態様による発明は，
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成する視覚復号型秘密分散方法を利用している。
【００１８】
前記分散生成フェーズにおいて，
分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成する多項式生成手段と，
分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算する多項式計算手段と，
分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するバイナリ表現ベクトル変換手段と，
分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色をv_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成する分散OHPシート生成手段と，
分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送る送信手段を有している。
【００１９】
前記復元フェーズにおいて，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集める収集手段と，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元する復元手段を有している。
【発明の効果】
【００２０】
本発明によれば，拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて秘密画像を分散することにより，各参加者が持たなければならない分散OHPシートの枚数を削減することができる。
【００２１】
また本発明によれば，Shamirの(k,n)閾値法において，多項式f([0 ... 0])=([0 ... 0])または([1 ... 1])とすることにより，分散OHPシートを再構成する際の演算量を削減することができる。
【００２２】
さらに本発明によれば，Shamirの(k,n)閾値法において，多項式f([0 ... 0])=([p_1 ... p_N])とすることにより，N枚の画像を同時に効率よく分散することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明に係る拡大体GF(2^m)上のShamirの(k,n)閾値法を用いた視覚復号型秘密分散方法の実施の形態について詳細に説明する。ただし，2^m > n とする。
【００２４】
本発明では、秘密画像を分散する方法として，拡大体GF(2^m)上のShamirの(k,n)閾値法を用いる。秘密画像を拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルにおいて，黒ピクセル(p=1)の時の多項式f(0 ... 0)=(1 ... 1)，白ピクセル(p=0)の時の多項式f(0 ... 0)=(0 ... 0)となるような次数がk-1次のランダムな多項式f(x)を生成する。m枚の秘密画像に対して拡大体GF(2^m)上のShamirの(k,n)閾値法を用いて分散するために，各ピクセルの色 p_1,...,p_m において多項式f(0 ... 0)=(p_1 ... p_m)となるような次数がk-1次のランダムな多項式f(x)を生成する。
【実施例１】
【００２５】
以下、本発明に係る視覚復号型秘密分散方法の第１の実施例について説明し、特に秘密画像を復元する際の演算量を削減するという本発明の効果をどのようにして得ているのかを詳細に説明する。ここで、前記視覚復号型秘密分散方法は、準備フェーズ、分散生成フェーズ、復元フェーズの３つのフェーズから成っている。以下、各フェーズについて順に説明する。
【００２６】
１．準備フェーズ
参加者n人，閾値k，拡大体GF(2^m)とする。秘密画像Iにはl(エル)ピクセルがある。
【００２７】
２．分散生成フェーズ
分散生成フェーズで用いる分散生成機構は図１に記載されている。分散生成機構は具体的には，前記分散生成フェーズで機能する多項式生成部，多項式計算部，バイナリ表現ベクトル変換部，分散OHPシート生成部，及び送信部で構成されている。復元機構は具体的には前記復元フェーズで機能する収集部及び復元部で構成されている。前記多項式生成部は秘密画像入力部を有しており、多項式計算部は分散OHPシート数入力部を有している。なお、多項式生成部，多項式計算部，バイナリ表現ベクトル変換部，分散OHPシート生成部での各動作については、分散OHPシート生成手段としての分散生成機構の中でそれぞれ以下に述べるような動作を行う。
【００２８】
前記多項式生成部は，分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成する。前記多項式計算部は，分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算する。前記バイナリ表現ベクトル変換部は，分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換する。前記分散OHPシート生成部は，分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色をv_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成する。前記送信手段は，分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送る。
【００２９】
前記収集部は，再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集める。前記復元部は，再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元する。
【００３０】
また，分散生成対象となる秘密画像（Ｉ）のサンプルを図２に示す。
【００３１】
(2-1).分散生成機構を用いる分散生成者は，秘密画像（Ｉ）の各ピクセル（ｊ）に対して，
ピクセル（ｊ）が黒ピクセル(p_j=1)の時の多項式f_j([0 ... 0])=([1 ... 1])，
ピクセル（ｊ）が白ピクセル(p_j=0)の時の多項式f_j([0 ... 0])=([0 ... 0])となるような
ランダムな拡大体GF(2^m)上のk-1次の多項式f_j(x)を生成する。
【００３２】
多項式f_j(x)は、以下の数式（１）のように表される。
【００３３】
f_j(x) = x^{k-1} a_1 + x^{k-2} a_2 + ... + x a_{k-1} + [b_1 ... b_m]・・・・（１）
ここで、a_1, ..., a_{k-1}は拡大体GF(2^m)上のランダムな係数であり，[b_1 ... b_m]は[0 ... 0]または[1 ... 1]である。
【００３４】
(2-2).分散生成機構を用いる分散生成者は，参加者iに対してi=1からnまで，さらに各ピクセル（ｊ）に対してj=1からlまで，上記第(2-1)項で生成した多項式f_j(x)から以下の数式（２）に従って拡大体GF(2^m)上で参加者iのシェアV_{j,i}を計算する。
【００３５】
V_{j,i} = f_j(i) = [v_{j,i,1} ... v_{j,i,m}]・・・・・・・・・・・・・・・・・・・（２）
参加者iのシェアV_{j,i}は拡大体GF(2^m)の要素であるから，v_{j,i,m}は0または1であり，0を白，1を黒とし（0を黒，1を白としてもよい），v_{i_j,1}を参加者iの1枚目の分散OHPシートのピクセル（ｊ）の色，v_{i_j,m}を参加者iのm枚目の分散OHPシートのピクセル（ｊ）の色として参加者iのm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を以下の数式（３）に従って生成する。なお、以下の数式（３）はS_{i,1}，.....，S_{i,m}のように合計m個の数式が存在している。
【００３６】
S_{i,1} = (v_{1,i,1} ... v_{l,i,1})，...
...，S_{i,m} = (v_{1,i,m} ... v_{l,i,m})・・・・・・・・・・・・・・・・（３）
具体例として，参加者がn=5，閾値がk=4，拡大体GF(2^4)で行われる時，5人の参加者のシェアを生成した4枚の分散OHPシートのサンプルを図３に示す。
【００３７】
(2-3).分散生成者は，i=1からnまで，m枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者iにそれぞれ渡す。
【００３８】
３．復元フェーズ
(3-1).再構成者はn人の参加者iがそれぞれ持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}のうち，k人分の分散OHPシートを集める。
【００３９】
(3-2).再構成者は3-1で集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて，秘密画像Iを復元する。
【００４０】
ここで、Lagrangeの補間公式とは，多項式の代数的解法を簡略化することができ，複数の離散データを与えるだけで複数の離散データを通る多項式が定まる。尚、Lagrangeの補間公式については，宮地充子・菊池浩明編著者，「IT Text 情報セキュリティ」，7.1節 秘密分散法，オーム社に記載されている。
【００４１】
拡大体GF(2^m)上のLagrangeの補間公式を用いた秘密画像の復元は以下の数式（４）に従って行われる。
【００４２】
[I_1 ... I_m]= f([0 ... 0])= lambda_1([0 ... 0]) * [S_{1,1} ... S_{1,m}] + ... + lambda_k([0 ... 0]) *[S_{k,1} ...S_{k,m}]=[c_1 ...c_m]・・・・・・・・・・・・・・・・・・（４）
なお、lambda_1([0 ... 0]), ..., lambda_k([0 ... 0])は拡大体GF(2^m)上のLagrange係数であり，S_{1,1} ... S_{1,m}, ..., S_{k,1} ... S_{k,m}はk人の参加者がそれぞれm枚持つ分散OHPシートであり，c_1,...,c_m はガロア体GF(2)上で計算されるS_{1,1},...,S_{k,m} のうちのいくつかの和であり，I_1,...,I_m はそれぞれ式 c_1,...,c_m によって復元される画像である。m個の式 c_1 ,..., c_m の中で，加算される項の数が最も少ない c_t を選択する。
【００４３】
ガロア体GF(2)上の式 I_t = c_t による分散OHPシートの重ね合せと白黒反転を用いた(分散OHPシートの)演算は、A XOR B = NOT(NOT(A) OR B) OR NOT(A OR NOT(B))に従って行われる。
【００４４】
ここで、XOR(排他的論理和)はガロア体GF(2)上の加算を示し、OR(論理和)は分散OHPシートの重ね合せを示し、NOT(否定)は分散OHPシートの白黒反転を示す。
【００４５】
ガロア体GF(2)上の式 I_t = c_tに沿って分散OHPシートの白黒反転と重ね合せを用いた演算によって，秘密画像Iと同じ画像I_tを得る。
【００４６】
具体例として，5人の参加者の中から参加者1，参加者2，参加者3，参加者4の分散OHPシートを集めて拡大体GF(2^4)上のLagrangeの補間公式による分散OHPシートの重ね合せと白黒反転を用いて秘密画像を復元する方法を図4に示す。図４に示すように加算される項目が最も少ないのはｃ2とｃ３の９項であるのでｃ2またはｃ３を選択してＩ2を復元すれば分散OHPシートを再構成する際の演算量を削減することができる。なお、図４ではｃ2を選択してＩ2を復元した例が示されている。
【実施例２】
【００４７】
以下、本発明に係る視覚復号型秘密分散方法の第２の実施例について説明し、特に２枚以上の秘密画像を同時に効率よく分散できるという本発明の効果をどのようにして得ているのかを詳細に説明する。ここで、前記視覚復号型秘密分散方法は、準備フェーズ、分散生成フェーズ、復元フェーズの３つのフェーズから成っている。以下、各フェーズについて順に説明する。
【００４８】
１．準備フェーズ
参加者n人，閾値k，拡大体GF(2^m)とする。N(=<m)枚の秘密画像I_1, ..., I_Nがあり，各々の秘密画像には以下の数式（５）を満足するl(エル)ピクセルがある。なお、以下の数式（５）はI_1，.....，I_Nのように合計N個の数式が存在している。
【００４９】
I_1 = (p_{1,1} ... p_{1,l})，...
...，I_N = (p_{N,1} ... p_{N,l})・・・・・・・・・・・・・・・・・（５）
ここで、p_{N,l}は0または1であり，0は白ピクセル，1は黒ピクセルに対応させる。
【００５０】
２．分散生成フェーズ
分散生成者は上記実施例１と同様，分散生成機構を用いてN枚の秘密画像I_Nの分散生成を行う。N<mのとき，I_{N+1} = I_1, ... , I_j = I_{j-N} ,..., I_m = I_{m-N} とすることで，ちょうどm枚の秘密画像を用意する。
【００５１】
(2-1).分散生成者は，m枚の秘密画像I_1, ... I_m の各ピクセルp_{1,1}, ..., p_{m,l}に対して，ランダムな拡大体GF(2^m)上のk-1次の多項式f_1(x), ..., f_l(x)を生成する。
【００５２】
多項式f_1(x), ..., f_l(x)は、以下の数式（６）のように表される。なお、以下の数式（６）はf_1(x) ，.....，f_l(x)のように合計l個の数式が存在している。
【００５３】
f_1(x) = x^{k-1} a_{1,1} + x^{k-2} a_{1,2} + ... + x a_{1,(k-1)} + [p_{1,1} ... p_{m,1}]，...
...，f_l(x) = x^{k-1} a_{l,1} + x^{k-2} a_{l,2} + ... + x a_{l,(k-1)} + [p_{1,l} ... p_{m,l}]
・・・・・（６）
ここで、a_{1,1}, ..., a_{l,(k-1)}は拡大体GF(2^m)上のランダムな係数である。
【００５４】
(2-2).分散生成者は，2-1で生成した多項式f_1(x), ..., f_l(x)で参加者iのシェアV_{1,i}, ..., V_{l,i}をi=1からnまで以下の数式（７）を満足するようにGF(2^m)上で計算する。なお、以下の数式（７）はf_1(x)，.....，f_l(x)のように合計l個の数式が存在している。
【００５５】
V_{1,i} = f_1(i) = [u_{1,i,1} ... u_{1,i,N}]，...
...，V_{l,i} = f_l(i) = [u_{l,i,1} ... u_{l,i,N}]・・・・・・・・・・・・・・・・（７）
(2-3).分散生成者は，参加者iのシェアV_{1,i}, ..., V_{l,i}を用いて，i=1からnまで以下の数式（８）に従って参加者iのm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を生成する。なお、以下の数式（８）はS_{i,1}, ..., S_{i,m}のように合計m個の数式が存在している。
【００５６】
S_{i,1} = (u_{1,i,1} ... u_{l,i,1})，...
...，S_{i,m} = (u_{1,i,m} ... u_{l,i,m})・・・・・・・・・・・・（８）
ここで、u_{l,i,N}は0または1であり，0を白ピクセル，1を黒ピクセルに対応させている。
【００５７】
S_{i,1}を参加者iの1枚目の分散OHPシートとし、S_{i,m}を参加者iのm枚目の分散OHPシートとする。
【００５８】
(2-4).分散生成者は，m枚の分散OHPシートS_{i,1}, ..., S_{i,m}をi=1からnまでの参加者iにそれぞれ渡す。
【００５９】
３．復元フェーズ
(3-1).再構成者は参加者iが持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}をk人分集める。
【００６０】
(3-2).再構成者は3-1で集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて，m枚の秘密画像I_mを復元する。
【００６１】
拡大体GF(2^m)上のLagrangeの補間公式を用いたm枚の秘密画像I_mの復元は、以下の数式（９）に従って行う。
【００６２】
[I_1 ... I_m] = f([0 ... 0]) = lambda_1([0 ... 0]) * [S_{1,1} ... S_{1,m}] + ... + lambda_k([0 ... 0]) * [S_{k,1} ... S_{k,m}] = [c_1 ... c_m]・・・・・・・・・・・・・・・・・・・・（９）
ここで、lambda_1([0 ... 0]), ..., lambda_k([0 ... 0])は拡大体GF(2^m)上のLagrange係数であり，S_{1,1} ... S_{1,m}, ..., S_{k,1} ... S_{k,m}はk人の参加者がそれぞれm枚持つ分散OHPシートであり，c_1,...,c_m はガロア体GF(2)上で計算される S_{1,1},...,S_{k,m} のうちのいくつかの和であり，I_1,...,I_m はそれぞれ式 c_1,...,c_m によって復元される画像である。
【００６３】
それぞれの秘密画像I_j (1=< j =< N) について，I_j = I_{j+N} = ... = I_{j+tN} ならば，c_j, c_{j+N}, ..., c_{j+tN} の中で加算される項の数が最も少ない c_{j'} を選択する。
【００６４】
ガロア体GF(2)上の式 I_j=c_{j'} による分散OHPシートの重ね合せと白黒反転を用いた(分散OHPシートの)演算は上記した実施例１と同様に行われる。
【００６５】
数式 I_j = c_{j'} に沿って分散OHPシートの白黒反転と重ね合せを用いた演算によって，N枚の秘密画像I_1, ..., I_Nを得る。
【００６６】
また、発明対象としては、上記視覚復号型秘密分散方法における各ステップをコンピュータに実行させるプログラムも含み、このプログラムはプログラムそのものであってもよいし、このプログラムがコンピュータで読み取り可能な記録媒体に格納されているものであってもよい。
【００６７】
本発明では、この記録媒体として、マイクロコンピュータで処理が行なわれるために必要なメモリ、例えばＲＯＭのようなものそのものがプログラムメディアであってもよいし、また、図示していない外部記憶装置としてプログラム読み取り装置が設けられ、そこに記録媒体を挿入することで読み取り可能なプログラムメディアであってもよい。いずれの場合においても、格納されているプログラムはマイクロコンピュータがアクセスして実行させる構成であってもよいし、あるいはいずれの場合もプログラムを読み出し、読み出されたプログラムは、マイクロコンピュータのプログラム記憶エリアにロードされて、そのプログラムが実行される方式であってもよい。このロード用のプログラムは予め本体装置に格納されているものとする。
【００６８】
ここで、上記プログラムメディアは、本体と分離可能に構成される記録媒体であり、磁気テープやカセットテープ等のテープ系、ＦＤ（フレキシブルディスク）やＨＤ（ハードディスク）等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ等の光ディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＲＯＭ等による半導体メモリを含めた固定的にプログラムを担持する媒体であってもよい。
【００６９】
また、本発明においては、インターネットを含む通信ネットワークと接続可能なシステム構成であることから、通信ネットワークからプログラムをダウンロードするように流動的にプログラムを担持する媒体であってもよい。なお、このように通信ネットワークからプログラムをダウンロードする場合には、そのダウンロード用プログラムは予め装置本体に格納しておくか、あるいは別の記録媒体からインストールされるものであってもよい。
【００７０】
さらに、本発明では、プログラム自体として、マイクロコンピュータで実行される処理そのものであってもよいし、あるいはインターネットを含む通信ネットワークとアクセスすることで取り込める、あるいは取り込めたものであってもよいし、こちらから送り出すものであってもよい。
【００７１】
また、上記した各実施の形態は、本発明を好適に実施した形態の一例に過ぎず、本発明は、その主旨を逸脱しない限り、種々変形して実施することが可能なものである。
【図面の簡単な説明】
【００７２】
【図１】視覚復号型秘密分散方法の分散生成機構の構成図である。
【図２】視覚復号型秘密分散方法において分散生成対象となる秘密画像のサンプル図である。
【図３】視覚復号型秘密分散方法の分散生成フェーズにおいて，参加者がn=5，閾値がk=4，拡大体GF(2^4)で行われる時，5人の参加者のシェアを生成した4枚の分散OHPシートのサンプル図である。
【図４】視覚復号型秘密分散方法の復元フェーズにおいて， 参加者がn=5，閾値がk=4，拡大体GF(GF2^4)で行われる時，5人の参加者の中から参加者1，参加者2，参加者3，参加者4の分散OHPシートを集めて拡大体GF(2^4)上のLagrangeの補間公式による分散OHPシートの重ね合せと白黒反転を用いて秘密画像を復元する方法を示す図である。
【特許請求の範囲】
【請求項１】
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，
その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成される視覚復号型秘密分散方法において，
前記分散生成フェーズは，
前記分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成するステップと，
前記分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算するステップと，
前記分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するステップと，
前記分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色を、v_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成するステップと，
前記分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送るステップを有し，
前記復元フェーズは，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集めるステップと，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元するステップを有することを特徴とする視覚復号型秘密分散方法。
【請求項２】
前記Shamirの(k,n)閾値法は拡大体GF(2^m)上における(k,n)閾値法であり、
前記(k,n)閾値法を用いた秘密分散方法により得られる前記参加者（ｉ）のシェアV_iは前記拡大体GF(2^m)の要素であり，
前記参加者（ｉ）が持たなければならない分散OHPシートの枚数を削減するために、前記シェアV_iをV_i=([v_{i,1} ... v_{i,m}])なるm次の0または1を表示するバイナリ表現ベクトルに変換することを特徴とする請求項１に記載の視覚復号型秘密分散方法。
【請求項３】
前記復元フェーズにおいて、
前記秘密画像（Ｉ）の各ピクセル（ｊ）に対して，前記ピクセル（ｊ）が黒(p_j=1)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [1 ... 1]となり，前記ピクセル（ｊ）が白(p_j=0)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [0 ... 0]となるような拡大体(2^m)上の多項式f_j(x)を生成することによって前記秘密画像（Ｉ）のm通りの復元を行い，
前記秘密画像（Ｉ）のm通りの復元方法のうち分散OHPシートの再構成の演算量を最も削減し、最も効率よく復元できる秘密画像I_tの復元方法を選択することを
特徴とする請求項１または２に記載の視覚復号型秘密分散方法。
【請求項４】
前記分散フェーズにおいて、
N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像I_{N+1}, ..., I_mを任意の画像とした場合，m枚の画像I_1, ..., I_N, I_{N+1}, ..., I_mを用いて，その画像の各ピクセルの色p_{1,1}, ..., p_{l,m}に対して，拡大体GF(2^m)上の多項式f_1([0 ... 0]) = [p_{1,1} ... p_{m,1}], ...,f_l([0 ... 0]) = [p_{1,l} ... p_{m,l}]となるような拡大体GF(2^m)上のj=1からj=lまでの多項式f_j(x)を生成することにより，同時にN枚の秘密画像を効率よく分散することを特徴とする請求項１〜３のいずれかに記載の視覚復号型秘密分散方法。
【請求項５】
N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像をI_{N+1}=I_1, ..., I_j=I_{j-N}, ..., I_m=I_{m-N}とすることにより，分散OHPシートの再構成の演算量を削減できることを特徴とする請求項１〜４の何れか一に記載の視覚復号型秘密分散方法。
【請求項６】
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，
その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成する視覚復号型秘密分散方法を利用した視覚復号型秘密分散システムであって，
前記分散生成フェーズにおいて，
分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成する多項式生成手段と，
分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算する多項式計算手段と，
分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するバイナリ表現ベクトル変換手段と，
分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色をv_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成する分散OHPシート生成手段と，
分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送る送信手段を有し，
前記復元フェーズにおいて，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集める収集手段と，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元する復元手段を有することを特徴とする視覚復号型秘密分散システム。
【請求項７】
視覚復号型秘密分散システムにおいて，
Shamirの(k,n)閾値法は拡大体GF(2^m)上における(k,n)閾値法であり、
前記(k,n)閾値法を用いた秘密分散方法により得られる前記参加者（ｉ）のシェアV_iは前記拡大体GF(2^m)の要素であり，
前記参加者（ｉ）が持たなければならない分散OHPシートの枚数を削減するために、前記シェアV_iが、V_i=([v_{i,1} ... v_{i,m}])なるm次の0または1を表示するバイナリ表現ベクトルに変換されることを特徴とする請求項６に記載の視覚復号型秘密分散システム。
【請求項８】
前記復元フェーズにおいて、
前記秘密画像（Ｉ）の各ピクセル（ｊ）に対して，前記ピクセル（ｊ）が黒(p_j=1)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [1 ... 1]となり，前記ピクセル（ｊ）が白(p_j=0)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [0 ... 0]となるような拡大体(2^m)上の多項式f_j(x)を生成することによって前記秘密画像（Ｉ）のm通りの復元が行われ，
前記秘密画像（Ｉ）のm通りの復元方法のうち分散OHPシートの再構成の演算量を最も削減し、最も効率よく復元できる秘密画像I_tの復元方法が選択されることを特徴とする請求項６または７に記載の視覚復号型秘密分散システム。
【請求項９】
前記分散フェーズにおいて、N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像I_{N+1}, ..., I_mを任意の画像とした場合，m枚の画像I_1, ..., I_N, I_{N+1}, ..., I_mを用いて，その画像の各ピクセルの色p_{1,1}, ..., p_{l,m}に対して，拡大体GF(2^m)上の多項式f_1([0 ... 0]) = [p_{1,1} ... p_{m,1}], ...,f_l([0 ... 0]) = [p_{1,l} ... p_{m,l}]となるような拡大体GF(2^m)上のj=1からj=lまでの多項式f_j(x)を生成することにより，同時にN枚の秘密画像を効率よく分散することを特徴とする請求項６〜８のいずれかに記載の視覚復号型秘密分散システム。
【請求項１０】
N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像をI_{N+1}=I_1, ..., I_j=I_{j-N}, ..., I_m=I_{m-N}とすることにより，分散OHPシートの再構成の演算量を削減できることを特徴とする請求項６〜９のいずれかに記載の視覚復号型秘密分散システム。
【請求項１１】
コンピュータに、
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成される視覚復号型秘密分散方法を実行させるプログラムであって，
前記分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成するステップと，
前記分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算するステップと，
前記分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するステップと，
前記分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色を、v_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成するステップと，
前記分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送るステップと，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集めるステップと，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元するステップ
を実行させることを特徴とするプログラム。
【請求項１２】
請求項１１に記載のプログラムを記録したことを特徴とするコンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）。
【請求項１】
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，
その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成される視覚復号型秘密分散方法において，
前記分散生成フェーズは，
前記分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成するステップと，
前記分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算するステップと，
前記分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するステップと，
前記分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色を、v_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成するステップと，
前記分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送るステップを有し，
前記復元フェーズは，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集めるステップと，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元するステップを有することを特徴とする視覚復号型秘密分散方法。
【請求項２】
前記Shamirの(k,n)閾値法は拡大体GF(2^m)上における(k,n)閾値法であり、
前記(k,n)閾値法を用いた秘密分散方法により得られる前記参加者（ｉ）のシェアV_iは前記拡大体GF(2^m)の要素であり，
前記参加者（ｉ）が持たなければならない分散OHPシートの枚数を削減するために、前記シェアV_iをV_i=([v_{i,1} ... v_{i,m}])なるm次の0または1を表示するバイナリ表現ベクトルに変換することを特徴とする請求項１に記載の視覚復号型秘密分散方法。
【請求項３】
前記復元フェーズにおいて、
前記秘密画像（Ｉ）の各ピクセル（ｊ）に対して，前記ピクセル（ｊ）が黒(p_j=1)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [1 ... 1]となり，前記ピクセル（ｊ）が白(p_j=0)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [0 ... 0]となるような拡大体(2^m)上の多項式f_j(x)を生成することによって前記秘密画像（Ｉ）のm通りの復元を行い，
前記秘密画像（Ｉ）のm通りの復元方法のうち分散OHPシートの再構成の演算量を最も削減し、最も効率よく復元できる秘密画像I_tの復元方法を選択することを
特徴とする請求項１または２に記載の視覚復号型秘密分散方法。
【請求項４】
前記分散フェーズにおいて、
N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像I_{N+1}, ..., I_mを任意の画像とした場合，m枚の画像I_1, ..., I_N, I_{N+1}, ..., I_mを用いて，その画像の各ピクセルの色p_{1,1}, ..., p_{l,m}に対して，拡大体GF(2^m)上の多項式f_1([0 ... 0]) = [p_{1,1} ... p_{m,1}], ...,f_l([0 ... 0]) = [p_{1,l} ... p_{m,l}]となるような拡大体GF(2^m)上のj=1からj=lまでの多項式f_j(x)を生成することにより，同時にN枚の秘密画像を効率よく分散することを特徴とする請求項１〜３のいずれかに記載の視覚復号型秘密分散方法。
【請求項５】
N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像をI_{N+1}=I_1, ..., I_j=I_{j-N}, ..., I_m=I_{m-N}とすることにより，分散OHPシートの再構成の演算量を削減できることを特徴とする請求項１〜４の何れか一に記載の視覚復号型秘密分散方法。
【請求項６】
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，
その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成する視覚復号型秘密分散方法を利用した視覚復号型秘密分散システムであって，
前記分散生成フェーズにおいて，
分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成する多項式生成手段と，
分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算する多項式計算手段と，
分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するバイナリ表現ベクトル変換手段と，
分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色をv_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成する分散OHPシート生成手段と，
分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送る送信手段を有し，
前記復元フェーズにおいて，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集める収集手段と，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元する復元手段を有することを特徴とする視覚復号型秘密分散システム。
【請求項７】
視覚復号型秘密分散システムにおいて，
Shamirの(k,n)閾値法は拡大体GF(2^m)上における(k,n)閾値法であり、
前記(k,n)閾値法を用いた秘密分散方法により得られる前記参加者（ｉ）のシェアV_iは前記拡大体GF(2^m)の要素であり，
前記参加者（ｉ）が持たなければならない分散OHPシートの枚数を削減するために、前記シェアV_iが、V_i=([v_{i,1} ... v_{i,m}])なるm次の0または1を表示するバイナリ表現ベクトルに変換されることを特徴とする請求項６に記載の視覚復号型秘密分散システム。
【請求項８】
前記復元フェーズにおいて、
前記秘密画像（Ｉ）の各ピクセル（ｊ）に対して，前記ピクセル（ｊ）が黒(p_j=1)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [1 ... 1]となり，前記ピクセル（ｊ）が白(p_j=0)の時の拡大体(2^m)上の多項式f_j([0 ... 0]) = [0 ... 0]となるような拡大体(2^m)上の多項式f_j(x)を生成することによって前記秘密画像（Ｉ）のm通りの復元が行われ，
前記秘密画像（Ｉ）のm通りの復元方法のうち分散OHPシートの再構成の演算量を最も削減し、最も効率よく復元できる秘密画像I_tの復元方法が選択されることを特徴とする請求項６または７に記載の視覚復号型秘密分散システム。
【請求項９】
前記分散フェーズにおいて、N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像I_{N+1}, ..., I_mを任意の画像とした場合，m枚の画像I_1, ..., I_N, I_{N+1}, ..., I_mを用いて，その画像の各ピクセルの色p_{1,1}, ..., p_{l,m}に対して，拡大体GF(2^m)上の多項式f_1([0 ... 0]) = [p_{1,1} ... p_{m,1}], ...,f_l([0 ... 0]) = [p_{1,l} ... p_{m,l}]となるような拡大体GF(2^m)上のj=1からj=lまでの多項式f_j(x)を生成することにより，同時にN枚の秘密画像を効率よく分散することを特徴とする請求項６〜８のいずれかに記載の視覚復号型秘密分散システム。
【請求項１０】
N枚のl(エル)ピクセルの秘密画像I_1,...,I_Nを用いて，N<mであるとき，(m-N)枚の画像をI_{N+1}=I_1, ..., I_j=I_{j-N}, ..., I_m=I_{m-N}とすることにより，分散OHPシートの再構成の演算量を削減できることを特徴とする請求項６〜９のいずれかに記載の視覚復号型秘密分散システム。
【請求項１１】
コンピュータに、
分散対象となるl(エル)ピクセルの秘密画像（Ｉ）を分散生成機構によって，n個の分散OHPシート群を生成する分散生成フェーズと，その生成した任意のk個以上の分散OHPシート群（S）を再構成することによって，前記秘密画像（Ｉ）が復元して現れる復元フェーズとで構成される視覚復号型秘密分散方法を実行させるプログラムであって，
前記分散生成機構がShamirの(k,n)閾値法を用いて前記秘密画像（Ｉ）の各ピクセル（ｊ）の色p_jに対し，f_j(0)=p_jとなるような次数がk-1次以下のランダムな多項式f_j(x)を生成するステップと，
前記分散生成機構がi=1からn(>= k)まで，参加者（ｉ）のシェアV_{j,i}=f_j(i)を計算するステップと，
前記分散生成機構が参加者（ｉ）のシェアV_{j,i}をV_{j,i}=[v_{j,i,1}, ... , v_{j,i,m}]なるm次の0または1を表示するバイナリ表現ベクトルに変換するステップと，
前記分散生成機構が参加者（ｉ）のl個のバイナリ表現ベクトルV_{1,i},...,V_{l,i}からt枚目の分散OHPシートのピクセル（ｊ）の色を、v_{j,i,t}が0ならば白，1ならば黒もしくはv_{j,i,t}が0ならば黒，1ならば白として参加者（ｉ）のm枚の分散OHPシートS_{i,1}=(v_{1,i,1}... v_{l,i,1}),..., S_{i,m}=(v_{1,i,m}... v_{l,i,m})を生成するステップと，
前記分散生成機構が生成したm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を参加者（ｉ）に送るステップと，
再構成者がn人の参加者のうちk人の参加者からそれぞれの参加者（ｉ）が持つm枚の分散OHPシートS_{i,1}, ..., S_{i,m}を集めるステップと，
再構成者が集めた分散OHPシートS_{1,1}, ..., S_{1,m}, ..., S_{k,1}, ..., S_{k,m}をLagrangeの補間公式を用いて分散OHPシートの白黒反転と重ね合せで秘密画像を復元するステップ
を実行させることを特徴とするプログラム。
【請求項１２】
請求項１１に記載のプログラムを記録したことを特徴とするコンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２００７−１５０９３８（Ｐ２００７−１５０９３８Ａ）
【公開日】平成１９年６月１４日（２００７．６．１４）
【国際特許分類】
【出願番号】特願２００５−３４４９７４（Ｐ２００５−３４４９７４）
【出願日】平成１７年１１月３０日（２００５．１１．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１４年度独立行政法人情報通信研究機構「民間基盤技術研究促進制度／（次世代電子投票・アンケートシステムとその社会的利用に関する研究）」、産業活力再生特別措置法第３０条の適用を受けるもの）
【出願人】（０００２３２０９２）ＮＥＣソフト株式会社 (173)
【出願人】（５０３４７１９９４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成１９年６月１４日（２００７．６．１４）
【国際特許分類】
【出願日】平成１７年１１月３０日（２００５．１１．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１４年度独立行政法人情報通信研究機構「民間基盤技術研究促進制度／（次世代電子投票・アンケートシステムとその社会的利用に関する研究）」、産業活力再生特別措置法第３０条の適用を受けるもの）
【出願人】（０００２３２０９２）ＮＥＣソフト株式会社 (173)
【出願人】（５０３４７１９９４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]