(57)【要約】      （修正有）【課題】メッセージ内のデータを、信頼できない第三者サーバーによって処理させる。【解決手段】メッセージが、一組の誤り訂正符号(ＥＣＣ)のうちの選択された１つを用いて符号語を生成することによって、信頼できない第三者によって保存及び処理される。この選択されたＥＣＣは、ブロックの重み率に依存し、各符号語は、全ての可能なＥＣＣ及び全ての可能な重み率の符号語に関する最小距離基準を満たす。この符号語の各シンボルは、チャネルのパラメーターに従って明示的に、ランダムにかつ独立に変更され、ランダム化された符号語が得られる。その後、このランダム化された符号語に対して上記信頼できない第三者によって実行された操作の符号化された結果が復号化される。【選択図】図１Ａ
2014002369.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを処理するための方法であって、
一組の誤り訂正符号(ＥＣＣ)を用い、前記メッセージの各ブロックについて選択されたＥＣＣを用いて符号語を生成するステップであって、前記選択されたＥＣＣは、前記ブロックの重み率に依存し、前記各符号語は、全ての可能なＥＣＣ及び全ての可能な重み率の前記符号語に関する最小距離基準を満たすものと、
ランダム化された符号語を得るために、前記符号語の各シンボルをチャネルのパラメーターに従って明示的に、ランダムにかつ独立に変更するステップと、
前記ランダム化された符号語に対して信頼できない第三者によって実行された操作の符号化された結果を復号化するステップと、
を含み、
前記ステップは、クライアントプロセッサによって実行される、メッセージを処理するための方法。
【請求項２】
複数のメッセージが処理され、
前記複数のメッセージに関する集約統計を求めるステップ、を更に含む請求項１に記載の方法。
【請求項３】
複数のメッセージが処理され、
前記複数のメッセージに関する監査を行うステップ、を更に含む請求項１に記載の方法。
【請求項４】
前記チャネルは仮定的雑音チャネルである、請求項１に記載の方法。
【請求項５】
前記チャネルはバイナリ対称チャネルである、請求項４に記載の方法。
【請求項６】
仮定的チャネルに従った前記符号語の前記変更は、暗号論的擬似乱数生成器によって達成される、請求項１に記載の方法。
【請求項７】
前記信頼できない第三者は、変更パラメーターを知っており、前記集約統計は正確である、請求項２に記載の方法。
【請求項８】
前記ＥＣＣ符号語は、前記ブロックの前記重み率を正確に保存する、請求項１に記載の方法。
【請求項９】
前記符号語は、前記ブロックの前記重み率を概算で保存する、請求項１に記載の方法。
【請求項１０】
前記変更パラメーターは、前記クライアントにおいて秘密に維持され、
仮定的チャネルに従った前記符号語の前記変更は、物理的複製不可能関数によって達成される、請求項１に記載の方法。
【請求項１１】
前記チャネルは、暗号論的擬似乱数生成器によって生成される、請求項１に記載の方法。
【請求項１２】
前記チャネルは、物理的複製不可能関数によって生成される、請求項４に記載の方法。
【請求項１３】
メッセージを処理するためのシステムであって、
前記メッセージの各ブロックについて、一組の誤り訂正符号(ＥＣＣ)から選択された該ＥＣＣを用いて符号語を生成するように構成されたクライアントであって、前記選択されたＥＣＣは、前記ブロックの重み率に依存し、前記各符号語は、全ての可能なＥＣＣ及び全ての可能な重み率の前記符号語に関する最小距離基準を満たし、該クライアントは、前記符号語の各シンボルをチャネルのパラメーターに従って明示的に、ランダムにかつ独立に変更して、ランダム化された符号語を得るものと、
前記ランダム化された符号語を処理して、前記クライアント用の符号化された結果を生成するように構成されたサーバーと、
を備える、メッセージを処理するためのシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には、メッセージ内のデータをアウトソーシングすることに関し、より詳細には、メッセージ内のデータを、当該データを明らかにすることなく、信頼できない第三者によって処理することに関する。
【背景技術】
【０００２】
データのアウトソーシング 
データがクライアントによってサーバーにアウトソーシングされるとき、特に、サーバーが信頼できない第三者である場合には、そのデータをセキュアな方法でサーバーから「隠す」ことが多くの場合に望ましい。この理由は、クライアント情報のプライバシーを守るとともに、サーバーが、そのデータを取得及び生成するのに用いられたプロセスについての機密情報にアクセスすることを防止するためである。これらの理由によって、データは、多くの場合、サーバーにアウトソーシングする前に、セキュアな方法で変更される。
【０００３】
そのようなアウトソーシングが必要である幾つかの理由がある。例えば、クライアントは、当該クライアントが費用効果の高い方法で効率的に保存することができる量よりもはるかに多い大量のデータを取得又は生成する。これは、クライアントが移動ハンドヘルドデバイス等の小さなフォームファクタのデバイスである場合に当てはまる。
【０００４】
加えて、データの全てを処理することは、クライアントにとって負担となるか又は不可能である可能性がある。加えて、クライアントは、多くのコンピューターアプリケーションで見られるように複雑な処理タスクを実行することができない場合がある。サーバーは、合理的なコストでクライアントに利用可能な事実上無制限のメモリ及び計算リソースを有するものと想定されている。
【０００５】
したがって、クライアントは、データ保存のためにサーバーに転送し、サーバーは、平均、分散又は他の集約統計の計算等の処理計算をデータに対して実行する。２つ目の例として、クライアントは、データを、信頼できない第三者に利用可能にして、調査、監視等の目的で集約計算を実行する必要がある。
【０００６】
プライバシーの問題のために、クライアントは、データをサーバーに生の形で提供したくない。加えて、クライアントは、例えば、データに対して監査を行うために、サーバーからデータの一部を定期的に取り出すことに関心がある場合がある。
【０００７】
したがって、上記相反する目標を達成するセキュアな方法を提供すること、すなわち、クライアントのデータを非公開に維持しながらサーバーが統計を集約することが望まれており、また、クライアントが必要な時はいつでもデータの一部を正確に取り出すことを可能にすることも望まれている。
【０００８】
クラウドコンピューティング
「クラウド」コンピューティングの出現は、個人及び企業が上記目標に取り組むためにデータの計算処理及びアーカイバル等のタスクを実行する方法に根本的な変化をもたらした。
【０００９】
特に、高価なハードウェアに投資して計算集約的なタスクを実行するか、又はメモリを継続的に購入して、急速に増大するデータのアーカイブを満たす代わりに、これらの作業をクラウドに移すことが便利になっており、場合によっては、経済的に必須になっている。
【００１０】
クラウドコンピューティングの定義、範囲及び能力は、時間とともにかなり広くなっており、変化し続けている。本明細書での焦点は、１つの側面、すなわち、データをアウトソーシングするという側面である。
【００１１】
例えば、クライアントは、絶えず増大するデータのアーカイブを保存するために、例えばサーバーにおける大きな保存設備へのアクセスを望むエンティティによって稼動される。そのようなアーカイブの例には、クライアント設備でのコンピューター及び周辺機器の全てにおけるログインの成功又は失敗の履歴が含まれる。データは、クライアントの医療設備内の患者の医療記録の履歴の場合もあるし、投票パターンの記録等の履歴の場合もある。
【００１２】
サーバーは、クラウドベースの保存サービスをクライアントに提供する。保存に加えて、クライアントは、サーバーが、データについての或る集約統計値を求める等の限られた量の処理能力を提供することも望んでいる。例えば、毎日の終わりに、サーバーは、クライアント設備での全ての周辺機器についての失敗したログインの割合をクライアントに提供する。さらに、クライアントは、監査目的のために正確な形でデータの一部を取り出すことができるべきである。
【００１３】
信頼できる第三者によれば、これを行うことは取るに足らないことである。しかしながら、目標は、プライバシー制約下で、上記タスク、すなわち保存及び処理を実行することである。これらの制約は、サーバーが、データの個々のインスタンスを知ることなく、全てのデータに関する集約統計を求めることができるべきであることを規定している。同様に、サーバーは、データが何を表しているのかを知ることなく、データを監査することができるべきである。
【００１４】
サーバーがデータを知ることを防止する１つの解決策は、ブロック暗号又はストリーム暗号による対称鍵暗号を用いることである。その解決策では、クライアントは、データを処理及び保存するためにサーバーに送信する前に、そのデータを暗号化する。しかしながら、暗号化はデータの構造を隠すので、その方法は、サーバーが、データの処理後に意味のある結果を提供することを不可能にする。
【００１５】
代替的な解決策では、クライアントは、データをサーバーに送信する前に準同型暗号を用いてデータを暗号化する。加法的準同型暗号システム又は乗法的準同型暗号システムの特性を利用すると、サーバーは、データに関する幾つかの簡単な集約関数の暗号化された値、例えば平均値を求めることができ、その統計をクライアントに送信することができる。
【００１６】
その解決策は、計算上のプライバシー、忘却計算(oblivious computation：気付かれない計算)、及び完全なデータ取り出しを促進する。しかしながら、その解決策は、深刻な欠点を有する。準同型暗号システムは、公開鍵暗号システムであり、そのため、暗号文が平文よりもはるかに大きく、その結果、サーバーにおける保存要件が非常に大きくなり、データをサーバーに通信するオーバーヘッドが法外に大きくなることに加えて、処理複雑度が増す。
【００１７】
上記問題に対するより簡単で複雑さのより少ない解決策は、データがサーバーに送信される前に、雑音をクライアントデータに加えることである。その方法は、個々のデータインスタンスを効果的に隠すが、依然として、データに関する集約統計を求めることを可能にし、従来のランダム化応答調査技法と同様である。しかしながら、クライアントが雑音列を正確に再生することができない限り、データの取り出しは簡単ではない。当然のことながら、雑音列を保存することは選択肢ではない。なぜならば、クライアントは、雑音列を保存するのに十分なメモリを有するのであれば、アウトソーシングする必要はないからである。
【００１８】
乱数生成
データを隠すための１つの情報理論的にセキュアな方法は、確率分布から取り出された乱数値を加えるものである。例えば数値データの場合、プライバシーは、一様分布からサンプリングされた数値を用いてデータをマスキングすることによって得ることができる。これらの数値は、暗号論的擬似乱数生成器(ＣＳ−ＰＲＮＧ)を用いてサンプリングすることができる。ＣＳ−ＰＲＮＧは、擬似乱数列のビットを生成するシードを用い、次に、このシードを用いて、所望の確率分布から数値を生成することができる。通常、これらの数値は整数である。
【００１９】
集約統計
データがサーバーから隠されても、多くの場合、サーバーが、データの一部についての概要情報を提供する集約統計を求めることを可能にすることが有益である。例えば、所与の日に所与のプリンターにおいて印刷される幾つかのページを求めることが望まれる場合がある。別の例として、所与の時間間隔の間、トレーダーによって実行される取引の総数を求めることが望まれる場合がある。
【００２０】
一般的な集約統計には、和、加重和、平均、加重平均、高次積率、加重高次積率等が含まれる。ランダム化応答等の技法は、個々のデータを隠すが、データに関する集約統計の推定値を求めることを可能にする。ランダム化応答は、機密性を維持しながら、応答者が機密データに応答することを可能にする方法である。
【００２１】
監査
時に、クライアントは、サーバーに保存されたデータの一部に対して監査を行うことを望む場合がある。監査は、保存されたデータの一部を回復し、その完全性又は正確性を、クライアントによって決定されたメトリックに従って検証することを指す。監査を実行するために、クライアントは、変更されたデータのうちの幾つかをサーバーにいつでも要求することができる。未変更のデータにアクセスできるようにするには、データをランダム化するのに用いられるいずれの方法も、完全に可逆的であるべきである。
【発明の概要】
【発明が解決しようとする課題】
【００２２】
この発明は、生成されたメッセージ内のデータを、信頼できない第三者サーバーによって処理するための方法およびシステムを提供する。
【課題を解決するための手段】
【００２３】
この発明の実施の形態は、生成されたメッセージ内のデータを、信頼できない第三者サーバーによって処理するための方法を提供する。このサーバーは、データに関する集約統計を求めることができ、クライアントは、アウトソーシングされたデータを正確に取り出すことができる。このプロセスにおいて、データは符号化されているので、そのデータ内の個々のエントリーは、サーバーに明らかにされない。この方法は、誤り訂正符号(ＥＣＣ)とランダム化応答との新規な組み合わせを用い、機密データに対する応答を、それらの応答の機密性を維持しながら可能にする。
【００２４】
定重み率符号のためのパラメーターが、誤りのある復号化の確率が無視できるように設計される。実施の形態は、従来のランダム化応答とともに定重み率誤り訂正符号を用いる。特に、クライアントデータの分布及びランダム化パラメーターを所与として、クライアントは、サーバーから集約統計を得ることができ、クライアントが無視できる誤り確率でサーバーからデータのインスタンスを取り出すことができるように、必要とされる誤り訂正符号の率を導出することができる。
【発明の効果】
【００２５】
この発明の実施の形態は、集約統計を求める等の処理のためにメッセージ内のデータをクライアントからサーバーにセキュアにアウトソーシングする問題に対処する新規な手法であって、サーバーが、メッセージ内のデータについての情報をほとんど又は全く知ることがないとともに、クライアントが、サーバーからのベクトルを回復する必要がある場合には、サーバーからのベクトルの質を検出することができ、これらのベクトルを高確率で正確に復号化することができるような新規な手法を提供する。
【図面の簡単な説明】
【００２６】
【図１Ａ】この発明の実施の形態による、信頼できない第三者サーバーによってクライアントメッセージ内のデータを処理するための方法及びシステムのブロック図である。
【図１Ｂ】この発明の実施の形態による、メッセージを符号化及び復号化するための方法のブロック図である。
【図２】この発明の実施の形態による、メッセージを符号化するためのシステムおよび方法を示すブロック図である。
【図３】この発明の実施の形態による、メッセージに関する統計を集約するための方法のブロック図である。
【図４】この発明の実施の形態による、クライアントデータを監査するための方法のブロック図である。
【発明を実施するための形態】
【００２７】
図１Ａに示すように、この発明の実施の形態は、クライアント１０によって生成されたメッセージ５のブロック２０１を、そのメッセージ内のデータの基礎をなす内容を明らかにすることなく、信頼できない第三者サーバー２０によって処理するための方法及びシステムを提供する。符号化されたメッセージ１５は、そのデータに関する集約統計２５をサーバーが求めることができるという特性を有する。代替的に、サーバーは、保存されたメッセージを監査することができ、監査結果３０をクライアントに提供することができる。クライアント及びサーバーはそれぞれ、当該技術分野で知られているように、１つ又は複数のプロセッサ、メモリ、及び入出力インターフェースを有する。これらのプロセッサは、本明細書において説明する方法を実施する。
【００２８】
図１Ｂは、一組の誤り訂正符号(ＥＣＣ)２０２を用いて、信頼できないサーバーによって処理される長さｌのメッセージ５のブロックを符号化及び復号化するための概略的な方法を示している。ここで、特定のブロック用のＥＣＣは、そのブロックの重み率(weight rate)７に依存し、各符号語は、全ての可能なＥＣＣ及び全ての可能な重み率の符号語に関する最小距離基準８を満たす。符号語内の各シンボルは、ランダム化された符号語２０４を得るように、通信チャネルのパラメーター９に従って、明示的に、ランダムにかつ独立に変更される(１２０)。ランダム化された符号語に対してサーバーによって実行された操作の符号化された結果１５は、クライアントによって復号化されて(１３０)、結果１１が得られる。
【００２９】
問題の定式化
図２は、この発明の実施の形態による、メッセージを符号化するためのシステム及び方法を示している。
【００３０】
メッセージ５のブロックｘｋ＝(ｘ１，ｘ１，…，ｘｋ)∈｛０，１｝２０１を考えることにする。このブロックはバイナリベクトルの形式である。クライアントは、このバイナリベクトルを、誤り訂正符号(ＥＣＣ)(ｎ，ｋ)２０２を用いて符号化し(２１０)、符号語ｙｎ２０３を生成する。この符号語は、バイナリ値又はバイナリシンボルの形式とすることができる。この符号化は、重み率保存型(weight rate preserving)誤り訂正符号を用いて実行される。
【００３１】
通信ネットワークでは、重み率保存型符号が用いられてきた。通信システムにおいて、従来技術の最小距離基準は、符号の設計において用いられる特定のＥＣＣ符号及び重み率しか満たさない。
【００３２】
これとは対照的に、この発明では、ＥＣＣは通信の用途では用いられず、代わりに、信頼できない第三者によって処理されるデータのためのセキュリティを提供するのにＥＣＣが用いられる。加えて、この発明者らは、ファミリー(一組の)誤り訂正符号を有し、各符号語は、単一のＥＣＣの符号語のみに関する最小距離基準ではなく、全ての可能なＥＣＣ及び全ての可能な重み率の符号語に関する最小距離基準を満たす。これは、この発明者らの誤り訂正符号の新規な設計及び使用である。具体的には、ランダム反転(random inversion：ランダムインバージョン)を実行する前に重み率保存型ＥＣＣを用いることによって、クライアントが結果を回復することが可能になる。
【００３３】
セキュリティ及びプライバシーの理由から、クライアントは、仮定的雑音チャネル(hypothetical noisy channel)のパラメーターに従って符号語ｙｎをランダム化し(２２０)、ランダム化された符号語ｚｎ２０４をサーバーに送信する。このランダム化は、符号語内の各シンボルを交叉確率ｐを用いてランダムに反転(フリップ)することによって行われる。この交叉確率は、仮定的雑音チャネルの設計用に得られる。チャネルは、特定のクライアント用に又は特定のクライアントによって設計されるので、サーバーを含む他のエンティティは、このパラメーターを知ることができない。
【００３４】
仮定的雑音チャネルは、様々な方法で生成することができる。このチャネルを生成する１つの方法は、暗号論的擬似乱数生成器(ＣＳ−ＰＲＮＧ)を用いて、ビット(シンボル)をフリップするか否かを判断することである。この雑音プロセスは、所望であれば、後に同じシードを用いて再生成することができる。
【００３５】
別の方法は、物理的複製不可能関数(ＰＵＦ)と呼ばれる物理的雑音プロセスを用いて、ビットをフリップするか否かを判定することである。ＰＵＦは、評価することはできるが予測することはできない物理的なチャネルの一実施の形態である。この点において、ＰＵＦは、一方向関数に類似するものである。ＰＵＦを用いると、雑音プロセスを再生成することができない。これは、この発明にとって問題ではない。なぜならば、雑音プロセスで何であろうとも、ＥＣＣによって、クライアントは、雑音のある符号語を所与として、雑音のない符号語を回復することが可能になり、したがって、メッセージを回復することが可能になるからである。
【００３６】
サーバーは、ランダム化された符号語、すなわちベクトルｚｎを保存し、例えば、メッセージに関する集約統計及びサーバーによって受信されたこれまでのメッセージの監査結果を処理した後、ｚｎについての幾つかの結果(又はベクトルｚｎ全体)をクライアントにフィードバックする(２３０)。
【００３７】
クライアントは、監査を行うことを望む場合、ベクトルｚｎをサーバーに要求し、このベクトルを復号化して(２４０)、ベクトルｋｋ２４１を求める。
【００３８】
定義１
(ｎ，ｋ)を２ｋ個の符号語のバイナリ符号Ｃとする。ｆを、ベクトル空間Ｍ＝｛０，１｝ｋからＣへの一対一の符号化関数とし、ベクトルｘｋとその対応する符号語ｙｋとの差を以下のように定義する。
【００３９】
【数１】
2014002369.tif 000003
【００４０】
ここで、ｗｔ(ｘｋ)はｘｋの重みである。符号Ｃは、Δ(Ｃ)＝ｍｉｎｆΔ(Ｃ，ｆ)である場合に重み率Δ(Ｃ)保存型と呼ばれる。特に、Δ(Ｃ)＝０である場合、符号Ｃは、重み率保存型と呼ばれる。バイナリ符号語用の重み率は、符号語内の値１を有するシンボルの数を符号語の長さ(シンボル、例えばビットを単位とする)によって除算したものとすることができる。
【００４１】
量Δ(Ｃ)は、ベクトルｘｋの重み率とその対応する符号語ｙｋの重み率との差を重み率に換算して表したものである。この量は、ベクトルの統計情報が、対応する符号語にどの程度保存されているのかの尺度である。したがって、Δ(Ｃ)＝０は、ｘｋ内のシンボルの２０％が値１を有する場合、その符号語内のバイナリシンボルの２０％も値１を有することを意味する。このｘｋ内のシンボルの２０％が値１を有するということは、例えば、特定のコンピューター端末における不成功のログインの割合に対応することができる。
【００４２】
符号Ｃが重み率保存型である場合、重み率が正確に保存されているような、すなわち、以下の式となるような符号化方法が存在する。
【００４３】
【数２】
2014002369.tif 000004
【００４４】
特に、Ｃが線形ＥＣＣ[ｎ，ｋ]である場合、以下の式となる。
【００４５】
【数３】
2014002369.tif 000005
【００４６】
ここで、Ｇは、線形符号Ｃの生成行列であり、ｍｉｎ及びｍａｘは、それぞれ最小関数及び最大関数を指す。
【００４７】
符号化及び復号化を簡単にするとともに保存を効率的にするために、重み率保存型線形ＥＣＣが、この発明の好ましい実施の形態において用いられる。しかしながら、この発明は、重み率が正確に保存されているとは限らないＥＣＣ設計も包含している。この場合、量Δ(Ｃ)は、正確に０であるとは限らない。Δ(Ｃ)に対する要件を緩和することによって、より効率的な符号設計、すなわち、より小さな値の符号語長ｎを用いることを可能にする設計を可能にすることができる。
【００４８】
セキュリティ及びプライバシーの理由から、サーバーは、終日にわたって蓄積されたバイナリイベントの数等、送信されたベクトルについての或る集約統計結果のみを求める。サーバーは、その結果をクライアントにフィードバックする(２３０)。サーバーは、ＥＣＣを反転することができない。なぜならば、この実施の形態では、サーバーは、入力されるメッセージｘｋと出力されるランダム化された符号語との間のマッピングを知らないからである。メッセージから符号語へのこのマッピングは、非線形であり、実際は、ＣＳ−ＰＲＮＧを用いてランダム化することができ、ＣＳ−ＰＲＮＧの状態情報は、クライアントにしか知られていない。
【００４９】
重み率保存型符号語が与えられると、サーバーは、その符号語に関する正確な集約統計を求めることができる。サーバーが正確な集約統計値を知ることを防止するが、サーバーが集約統計値の推定値を得ることを可能にするために、図２に示すように、クライアントは、その符号語をサーバーに送信する前に、その符号語の各シンボルを交叉確率ｐを用いてランダム化する。このランダム化技法は、ランダム化応答と呼ばれ、このランダム化応答では、機密データの機密性が維持される。
【００５０】
定義２
０≦ｐ≦１とする。ランダム化応答は、交叉確率ｐを有するバイナリ対称チャネル、すなわち、以下の式である。
【００５１】
【数４】
2014002369.tif 000006
【００５２】
式中、Ｙは入力シンボルであり、Ｚは出力シンボルである。一般に、長さｎを有するバイナリベクトルｙが交叉確率ｐを用いてランダム化される場合、ｙの重み率
【００５３】
【数５】
2014002369.tif 000007
【００５４】
は、ｐを所与として、出力バイナリベクトルｚから偏りなく推定することができる。すなわち、以下の式となる。
【００５５】
【数６】
2014002369.tif 000008
【００５６】
この推定の分散は、以下の式となる。
【００５７】
【数７】
2014002369.tif 000009
【００５８】
大きな長さｎの符号語の場合、この推定値は非常に正確である可能性がある。幾つかの実施の形態では、サーバーが正確な集約統計を知ることは望まれず、そのため、パラメーターｐは、クライアントによって管理され、サーバーには明らかにされない。この実施の形態では、サーバーは、集約統計値の変化が入力メッセージｘｋの統計的特性の変化に起因するものであるのか、又はランダム化チャネルの交叉確率パラメーターの変化によるものであるのかを判断することができない。
【００５９】
他の実施の形態において、正確な集約統計値をサーバーに明らかにすることが問題でない場合には、パラメーターｐはサーバーに明らかにされてもよい。
【００６０】
ランダム化に用いられる原理は、符号語を仮定的雑音チャネルに通すことであり、ここで、最小距離等の、メッセージを符号語に符号化するのに用いられたパラメーターは、この雑音チャネルの交叉確率ｐ等のパラメーターに基づいて選択される。
【００６１】
重み率保存型符号が符号化に用いられる場合、クライアントは、重みｗｔ(ｚ)についての報告をサーバーから受信した後に、元のメッセージ(ベクトルｘｋ)の重み率を正確に推定することができる。次に、クライアントは、このベクトルの質に基づいてベクトルを復号化するか否かを判断することができる。
【００６２】
定義３
重み率保存型の(ｎ，ｋ)の符号Ｃは、全ての符号語にわたる誤りのある復号化の平均確率がε未満となるような、すなわち以下の式となるような符号化Ｅ及び復号化Ｄが存在する場合に、交叉確率ｐに関してε許容可能(ε-admissible)と呼ばれる。
【００６３】
【数８】
2014002369.tif 000010
【００６４】
式中、Ｅ−１は、符号からベクトル空間Ｍへの符号化Ｅの逆マッピングであり、ｚは、ベクトルｘの入力符号語Ｅ(ｘ)の交叉確率ｐを用いてランダム化された出力である。
【００６５】
保存を効率的にするとともに符号化を簡単にするために、ｋ個のシンボル(ビット)のベクトル長について、バイナリ対称チャネルの交叉確率ｐ及び誤りのある復号化の許容される平均確率ε、この発明者らは、
【００６６】
【数９】
2014002369.tif 000011
【００６７】
によって定義される符号化率を対象としている。
【００６８】
定理１
所与のベクトル長ｋ、ランダム化応答の交叉確率ｐ、及び誤りのある復号化の許容される平均確率εに関して、各ｉ＝０，１，…，ｋについて以下を定義する。
【００６９】
【数１０】
2014002369.tif 000012
【００７０】
及び
【００７１】
【数１１】
2014002369.tif 000013
【００７２】
この場合、以下を有するε許容可能重み率保存型符号Ｃが存在する
【００７３】
【数１２】
2014002369.tif 000014
【００７４】
式中、
【００７５】
【数１３】
2014002369.tif 000015
【００７６】
であり、δｉは、以下の式の一意解である。
【００７７】
【数１４】
2014002369.tif 000016
【００７８】
上記の証明は、付録に与えられている。
【００７９】
定重み符号のためのより良好な復号化が、例えば、埋め込みによって定重み符号を復号化するための幾何学的手法の場合に、復号化の平均確率の点から性能を高めることができる。簡単にするために、この発明者らは一般的なＭＭＤを用いる。
【００８０】
付録
証明
ベクトル長ｋ、及びランダム化応答の交叉確率ｐを所与として、符号率１／δが達成可能であることを構成的に証明することにする。すなわち、誤りのある復号化の平均確率が、任意ではあるが固定されたε＞０未満となるような重み率保存型ブロック符号を構成することができる。
【００８１】
コードブック生成
各ｉ＝０，１，…，ｋについて、長さｋδ、重みｉδ、及び最小距離ｄｉを有する定重み符号Ｃｉを構成する。ここで、
【００８２】
【数１５】
2014002369.tif 000017
【００８３】
である。
【００８４】
この場合、コードブックは、以下のように表される。
【００８５】
【数１６】
2014002369.tif 000018
【００８６】
符号化
重みｉを有するベクトルｘについて、定重み符号Ｃｉから符号語を割り当てる。ベクトルｘの重み率
【００８７】
【数１７】
2014002369.tif 000019
【００８８】
は、各ｉ＝０，１，…，ｋについてその符号語に保存される。
【００８９】
復号化
交叉確率ｐを用いたランダム化応答からベクトルｚを受信した後、クライアントに置かれた復号器が、最小距離復号化(ＭＤＤ)を用いて、以下の式となるような符号語ｙ０∈Ｃを求めることができる。
【００９０】
【数１８】
2014002369.tif 000020
【００９１】
この場合、復号化された符号語はｙ０である。
【００９２】
符号の存在性
各ｉ＝０，１，…，ｋについて、以下の式を定義する。
【００９３】
【数１９】
2014002369.tif 000021
【００９４】
ｆｉ(ｘ)がｘの増加関数であることを示すことができる。
【００９５】
δの定義によって、δ≧δｉである。したがって、δｉの定義から、以下の式となる。
【００９６】
【数２０】
2014002369.tif 000022
【００９７】
この式は、Ｃｉ内の符号語の数である。すなわち、以下の式となる。
【００９８】
【数２１】
2014002369.tif 000023
【００９９】
定重み符号のよく知られた結果から、
【０１００】
【数２２】
2014002369.tif 000024
【０１０１】
である場合に、長さｋδ、重みｉδ、及び最小距離ｄｉを有する定重み符号が存在する。
【０１０２】
誤りのある復号化の平均確率
符号語ｙ∈Ｃｉがランダム化され、ベクトルｚが受信される。この場合、誤りのある復号化の以下の２種類のイベントが存在する。
Ｅ１：符号語ｙ’∈Ｃｉが復号されるが、ｙ’≠ｙである；及び
Ｅ２：ｊ≠ｉであるＣｊからの符号語が復号化される。
【０１０３】
以下では、Ｃの全ての符号語にわたる誤りのある復号化の平均確率がε未満であることを説明する。以下の式を有する。
【０１０４】
【数２３】
2014002369.tif 000025
【０１０５】
ｙｓ、ｙｔを、長さｎ及びｄｉｓｔ(ｙｓ，ｙｔ)＝ｄを有する２つのバイナリベクトルとする。ベクトルｙｓが交叉確率ｐを用いてランダム化され、ベクトルｚが受信される場合、以下の式となる。
【０１０６】
【数２４】
2014002369.tif 000026
【０１０７】
式中、
【０１０８】
【数２５】
2014002369.tif 000027
【０１０９】
は、１／２とｐとの間のカルバックライブラー(ＫＬ：Kullback-Leibler)ダイバージェンス(divergence：情報量)である。
【０１１０】
定重み符号Ｃｉは、
【０１１１】
【数２６】
2014002369.tif 000028
【０１１２】
の符号語を有するので、イベントＥ１の確率は以下の式となる。
【０１１３】
【数２７】
2014002369.tif 000029
【０１１４】
式中、ｄｉは、定重み符号Ｃｉの最小距離であり、
【０１１５】
【数２８】
2014002369.tif 000030
【０１１６】
である。
【０１１７】
同様に、イベントＥ２の確率は以下の式となる。
【０１１８】
【数２９】
2014002369.tif 000031
【０１１９】
したがって、以下の式となる。
【０１２０】
【数３０】
2014002369.tif 000032
【０１２１】
符号化の普遍性
証明
関数ｆｉはｄｉの減少関数である。ｄｉの定義から、ｄｉは、ｐが減少するにつれて減少する。そのため、ｆｉはｐの増加関数である。また、
【０１２２】
【数３１】
2014002369.tif 000033
【０１２３】
もｐの増加関数である。これらの知見によって、ｐ≧ｐ’である場合、δ＊(ｐ)≧δ＊(ｐ’)であることを検証することが可能である。したがって、上記証明において構成された交叉確率ｐに関するε許容可能重み率保存型符号は、任意の交叉確率ｐ’≦ｐに関してもε許容可能であると結論付けることができる。
【０１２４】
定重み符号の具体的な構成は、条件
【０１２５】
【数３２】
2014002369.tif 000034
【０１２６】
が満たされる場合に求めることができる。
【図１Ａ】
2014002369.tif 000035
【図１Ｂ】
2014002369.tif 000036
【図２】
2014002369.tif 000037
【図３】
2014002369.tif 000038
【図４】
2014002369.tif 000039
【外国語明細書】
2014002369.tif 000040
2014002369.tif 000041
2014002369.tif 000042
2014002369.tif 000043
2014002369.tif 000044
2014002369.tif 000045
2014002369.tif 000046
2014002369.tif 000047
2014002369.tif 000048
2014002369.tif 000049
2014002369.tif 000050
2014002369.tif 000051
2014002369.tif 000052
2014002369.tif 000053
2014002369.tif 000054
2014002369.tif 000055
2014002369.tif 000056
2014002369.tif 000057
2014002369.tif 000058
2014002369.tif 000059
2014002369.tif 000060
2014002369.tif 000061
2014002369.tif 000062
2014002369.tif 000063
2014002369.tif 000064
2014002369.tif 000065
2014002369.tif 000066
2014002369.tif 000067
2014002369.tif 000068
2014002369.tif 000069
2014002369.tif 000070
2014002369.tif 000071