(57)【特許請求の範囲】
【請求項１】
未知のオーディオレコーディングを既知のオーディオレコーディングと安全にマッチングさせるオーディオレコーディングのマッチング方法であり、
複数の既知のオーディオレコーディングを記憶する工程であって、該既知のオーディオレコーディングのそれぞれは、該既知のオーディオレコーディングを一意に識別する情報に対するインデックスと関連付けられるものと、
未知のオーディオレコーディングを前記複数の既知のオーディオレコーディングのそれぞれと安全に相互相関させる工程であって、最良にマッチングする既知のオーディオレコーディングを確定し、前記未知のオーディオレコーディング及び前記複数の既知のオーディオレコーディングは公開鍵によって暗号化され、
前記相互相関させるために、
加法シェアｂｋを記憶する工程と、
ユーザのクライアントに、ａｋ＋ｂｋ＝ｃｋであるような加法シェアａｋ(式中、ｃｋは該相互相関)を送信する工程と、を有し、
前記相互相関に従って確定するために、前記加法シェアａｋ及び前記加法シェアｂｋを使用してミリオネア問題を解く工程であって、前記最良にマッチングする既知のオーディオレコーディングに対応する前記加法シェアの最大値を位置特定するものを有するものと、
前記最良にマッチングする既知のオーディオレコーディングの前記インデックスを安全に確定する工程と、及び
前記最良にマッチングする既知のオーディオレコーディングの前記インデックスに関連付けられる前記情報を、前記未知のレコーディングのユーザに安全に提供する工程と、
を含むオーディオレコーディングのマッチング方法。
【請求項２】
前記オーディオレコーディングはデジタルサンプルとして記憶される請求項１に記載の方法。
【請求項３】
前記暗号化は準同型である請求項１に記載の方法。
【請求項４】
前記最良にマッチングする既知のオーディオレコーディングを安全に確定するために、安全な順列作成プロトコルを利用する請求項１に記載の方法。
【請求項５】
前記安全に提供する工程は、安全な紛失転送を使用する請求項１に記載の方法。
【請求項６】
前記未知のオーディオレコーディングは音楽の代表的なサンプルである請求項１に記載の方法。
【請求項７】
前記未知のオーディオレコーディングの、時間シフトされた位置での前記複数の既知のオーディオレコーディングのそれぞれに対するベクトル積を計算する工程であって、該時間シフトされた位置のそれぞれはベクトル積スコアをもたらすものと、及び
前記既知のオーディオレコーディングのそれぞれに対する最大ベクトル積スコアを求める工程であって、最高の最大スコアが前記最良にマッチングする既知のオーディオレコーディングに対応するものと、
をさらに含む請求項１に記載の方法。
【請求項８】
前記最良にマッチングする既知のオーディオレコーディングを安全に確定する工程が、紛失多項式評価プロトコルを使用する請求項１に記載の方法。
【請求項９】
前記公開鍵を使用して前記情報を暗号化する工程と、及び
前記ユーザによって提供される前記公開鍵に対応する秘密鍵によって前記暗号化された情報を解読する工程と、
をさらに含む請求項１に記載の方法。
【請求項１０】
未知のオーディオレコーディングを既知のオーディオレコーディングと安全にマッチングさせるオーディオレコーディングのマッチングシステムであり、
複数の既知のオーディオレコーディングを記憶するメモリであって、該既知のオーディオレコーディングのそれぞれは、該複数の既知のオーディオレコーディングを一意に識別する情報に対するインデックスと関連付けられるものと、
１つのオーディオレコーディングを前記複数の既知のオーディオレコーディングのそれぞれと安全に相互相関させる手段であって、最良にマッチングする既知のオーディオレコーディングを確定し、前記未知のオーディオレコーディング及び前記複数の既知のオーディオレコーディングは公開鍵によって暗号化され、
前記相互相関させるために、
加法シェアｂｋを記憶する手段と、
ユーザのクライアントに、ａｋ＋ｂｋ＝ｃｋであるような加法シェアａｋ(式中、ｃｋは該相互相関)を送信する手段と、を有し、
前記相互相関に従って確定するために、前記加法シェアａｋ及び前記加法シェアｂｋを使用してミリオネア問題を解く手段であって、前記最良にマッチングする既知のオーディオレコーディングに対応する前記加法シェアの最大値を位置特定するものを有するものと、
前記最良にマッチングする既知のオーディオレコーディングの前記インデックスを安全に確定する手段と、
前記最良にマッチングする既知のオーディオレコーディングの前記インデックスに関連付けられる前記情報を安全に提供する手段と、
を備えるオーディオレコーディングのマッチングシステム。
【請求項１１】
未知のオーディオレコーディングを既知のオーディオレコーディングと安全にマッチングさせるオーディオレコーディングのマッチングシステムであり、
複数の既知のオーディオレコーディングを記憶するサーバであって、該既知のオーディオレコーディングのそれぞれは、該複数の既知のオーディオレコーディングを一意に識別する情報に対するインデックスと関連付けられるものと、
前記サーバにおいて、１つのオーディオレコーディングを前記複数の既知のオーディオレコーディングのそれぞれと安全に相互相関させる手段であって、最良にマッチングする既知のオーディオレコーディングを確定し、前記未知のオーディオレコーディング及び前記複数の既知のオーディオレコーディングは公開鍵によって暗号化され、
前記相互相関させるために、
加法シェアｂｋを記憶する手段と、
ユーザのクライアントに、ａｋ＋ｂｋ＝ｃｋであるような加法シェアａｋ(式中、ｃｋは該相互相関)を送信する手段と、を有し、
前記相互相関に従って確定するために、前記加法シェアａｋ及び前記加法シェアｂｋを使用してミリオネア問題を解く手段であって、前記最良にマッチングする既知のオーディオレコーディングに対応する前記加法シェアの最大値を位置特定するものを有するものと、
前記最良にマッチングする既知のオーディオレコーディングの前記インデックスを安全に確定する手段と、
前記最良にマッチングする既知のオーディオレコーディングの前記インデックスに関連付けられる前記情報を、前記未知のオーディオレコーディングのユーザに安全に提供する手段と、
を備えるオーディオレコーディングのマッチングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはオーディオレコーディングをマッチングさせる方法に関し、より詳細には、プライバシーを保護しながら音楽をマッチングさせる方法に関する。
【背景技術】
【０００２】
消費者は、音楽等のオーディオコンテンツを取得するのに次第にインターネットへと転向しつつある。消費者は、販売店からＣＤ又はテープで音楽を購入する代わりに、オンライン音楽配信者から音楽をダウンロードする。音楽は、ネットワークに接続されているサーバのデータベース内にデジタル形式で記憶されることが多い。これによって、ｉＰｏｄのようなクライアント再生装置のユーザが音楽のコピーを「ダウンロード」することが可能となる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
消費者及び音楽配信者のプライバシーが保護されるように、オーディオコンテンツを識別する情報を取得することが望まれている。
本発明は、プライバシーが保護される処理を使用してオーディオレコーディングをマッチングさせる方法及びシステムを提供することを目的とする。
【課題を解決するための手段】
【０００４】
本発明の実施の形態は、プライバシーが保護される処理を使用してオーディオレコーディングをマッチングさせる方法及びシステムを提供する。特に、本発明は、クライアント装置内に記憶されている音楽をサーバ内に記憶されている音楽のデータベースとマッチングさせる。本方法は、安全なマルチパーティ計算を使用する。
【発明の効果】
【０００５】
本発明は、音楽のようなオーディオレコーディングをマッチングさせる方法であって、タイトル及びレコーディングのアーティストのような、音楽に関する情報を学習する、方法を提供する。本方法はプライバシーを保護するものであり、暗号法の原理を使用する。
【発明を実施するための最良の形態】
【０００６】
図１は、本発明の一実施の形態によるオーディオレコーディングをマッチングさせる方法及びシステムを示している。ユーザ(アリス)は、未知のオーディオレコーディングｘ１０１、たとえば音楽を記憶しているクライアント装置１０を有する。未知のレコーディングは、サンプルｘ１，ｘ２，．．．，ｘＴを含むデジタル信号として記憶されている。しかしながら、タイトル、レコーディングのアーティスト、アルバム名、製造日、プロデューサ、ジャンル、又は他の方法でそのレコーディングを識別し得る任意の他の情報は、ユーザ又はクライアントのいずれにとっても未知である。したがって、アリスのレコーディングは「未知」である。
【０００７】
配信者(ボブ)は、既知のオーディオレコーディングｙｋ１０２の豊富なデータベースを記憶しているサーバ２０を制御する。個々のレコーディングはｙｋ１，ｙｋ２，．．．，ｙｋＴである。各オーディオレコーディングは、上述のように、レコーディングを一意に識別する、記憶されている情報１０３と関連付けられている。したがって、ボブのレコーディングは「既知」である。オーディオレコーディング及び関連付けられている情報は、ｋによってインデックスを付される。したがって、既知のレコーディング又は関連付けられた情報のいずれかを検索するには、インデックスを知っていれば十分である。
【０００８】
アリスは、自身のレコーディングの識別情報を取得するために、自身の未知のレコーディングをボブの既知のレコーディングのデータベースと比較することを望む。処理は以下のように進行することができる。
【０００９】
アリスは、自身の未知の音楽レコーディングｘ１０１の代表的なサンプル又は抜粋(snippet)をボブに送信する。ボブはｘの抜粋を自身の既知のレコーディングｙｋ１０２と相互相関させて(１１０)、相互相関ベクトルｃｋ１０４を取得する。それぞれの既知のレコーディングに対して、相互相関は、さまざまな時間シフトされた位置における抜粋ｘと既知のレコーディングとのベクトル積をとる。既知のレコーディングの最大ベクトル積がマッチングのスコアとして解釈される。このステップはそれぞれの既知のレコーディングに対して繰り返される。
【００１０】
相互相関の最良のマッチング１０５が位置特定される(１２０)。最良のマッチングは最高のベクトル積スコアを有する。最良にマッチングする既知のレコーディングのインデックスｋ１０６が確定される(１３０)。アリスはインデックスｋを使用してアリスのレコーディング１０１と最良にマッチングするボブのレコーディングの情報１０３を検索する(１４０)ことができる。したがって、アリスのレコーディングは既知となる。
【００１１】
式で表した場合(Formally)
アリスはｘをボブに送信し、ボブのデータベース内のすべてのレコーディングｙｋ＝(ｋ＝{１，２，．．．，Ｋ})に対して、ボブは
【００１２】
【数１】
0005127590.tif 000002
【００１３】
を求める。式中、ｃｋ１０４は相互相関の全体を示す。ボブはアリスにＫ個の成分から成るベクトルＣを送信し、ｋ番目の成分ｃｋはｃｋの最大値１０５に等しい。ベクトルＣ中の最大成分のインデックス１０６は、ボブの最良にマッチングするレコーディングを示す。アリスはインデックスｋを使用してボブのデータベースにアクセスし、自身のレコーディング１０１に関連付けられる、関連する情報を検索する。
【００１４】
プライバシーの制約がある場合、アリスはボブがｘを知ることを望まず、同様にボブもアリスが自身のデータベースを学習することを望まない。信用のおける第三者を使用すれば、両者が匿名のままでいることができる一方で、ボブは依然としてアリスのレコーディングを識別することができる。
【００１５】
したがって、本発明の実施の形態は、安全なマルチパーティ計算(ＳＭＣ)を使用して図１の方法を実施する。
【００１６】
安全な２パーティ計算
本発明の実施の形態による方法は、安全な２パーティ計算の具体例である。アリス及びボブがそれぞれプライベートデータａ及びｂを有し、関数ｆ(ａ，ｂ)の結果を計算することを望んでいる場合を考える。信用のおける第三者が、結果ｃ＝ｆ(ａ，ｂ)をアリス及びボブに提供することができる。ｆ(ａ，ｂ)を実施するプロトコルは、当該プロトコルが信用のおける第三者と同様に、ａ及びｂに関する情報を決して明らかにしない場合にのみ安全である。
【００１７】
図１の方法は、Yaoのミリオネア問題(millionaires' problem)プロトコル、安全ドット積プロトコル、最大値発見プロトコル及び順列作成プロトコルのような安全なプロトコルを使用する。Smaragdisによって出願された「Secure classifying of data with Gaussian distributions」と題する米国特許出願公開第２００７００５３５０７号、及び、Smaragdisによって２００７年１月１日に出願された「System and Method for Recognizing Speech Securely」と題する米国特許出願第１１／６２３，５２２号を参照されたい。これらの特許文献は両方とも参照により本明細書に援用される。
【００１８】
本方法は、両者のいずれもが全結果にアクセスすることができないように、安全に、中間結果を２パーティ間でランダムに分散させる。たとえば、両者は特定のプロトコル処理の全結果ｚを取得する代わりに、ｚ１＋ｚ２＝ｚであるようなランダムな加法シェア(additive share)を受信する。本方法は、アリス及びボブのいずれもが中間結果を利用して他方のプライベートデータを取得することができないことを確実にする。
【００１９】
準同型公開鍵暗号系
公開鍵暗号系は、それぞれ鍵生成、暗号化、解読用の３部(ＧＥ、ＥＮ、ＤＥ)から成る。ＧＥは秘密鍵ｓｋと公開鍵ｐｋとの対を生成する。ＥＮは公開鍵ｐｋを使用して平文ｍを暗号化し、ｍを暗号化したものであるＥＮ(ｍ，ｐｋ)を出力する。ＤＥは、暗号化された平文を秘密鍵ｓｋを使用して解読する。
【００２０】
暗号化されていないデータに対して実施することができる代数的演算を暗号文の操作によっても実施することができる場合、暗号系は準同型である。準同型暗号化の１つの具体例は、その特性を使用する：
【００２１】
【数２】
0005127590.tif 000003
【００２２】
これは、信用のおけない者が、暗号化データを復号するのに必要な秘密鍵を有することなく、対応する暗号化された平文又は暗号文に対する簡単な演算によって平文演算と同等の演算を実施することができることを意味する。
【００２３】
オーディオレコーディングマッチング用途に関して、ボブは、アリスが自身の秘密のレコーディングを暗号化するのに使用するものと同じ公開鍵を使用して自身のレコーディングを暗号化する。同じ公開鍵及び準同型特性が使用されるため、暗号化データに対するマッチング演算の結果は意味のある結果を生成する。
【００２４】
安全なオーディオ比較
上述のように、本方法は相互相関１１０、最大値１０５の位置特定１２０、相互相関ベクトルにおける最大値のインデックス１０６の確定、及び情報１０３の検索１４０を含む。これよりこれらのステップをより詳細に説明する。
【００２５】
オーディオ信号の相互相関
これは、アリスの音楽の抜粋ｘ１０１の、ボブのレコーディングｙｋ１０２との相互相関１１０を含む。アリス及びボブは相互相関を実施すること、すなわち、自身のそれぞれのデータベクトルを開示することなくレコーディングの類似度を測定することを望む。
【００２６】
したがって、アリスは秘密鍵と公開鍵との対(ｓｋ，ｐｋ)１１−１２を生成し、公開鍵１２をボブに送信する。
【００２７】
アリスは公開鍵ｐｋを使用して時系列オーディオデータ１０１から成る自身の抜粋の各サンプルｘｉを暗号化し、暗号化されたデータｅｔをボブに送信する。数式としては、アリスは
【００２８】
【数３】
0005127590.tif 000004
【００２９】
を送信する。
【００３０】
ボブは相互相関１１０を実施する。ｃｋｎのｎ番目の中間結果ｚの計算は以下の通りである。
【００３１】
【数４】
0005127590.tif 000005
【００３２】
準同型特性に起因して、結果ｚはｃｋｎの暗号化値を表す。
【００３３】
ボブは乱数ｂｋｎを生成し、アリスの公開鍵を使用して結果
【００３４】
【数５】
0005127590.tif 000006
【００３５】
をアリスに送信する。式中、ｂｋｎは安全ドット積の結果のボブのシェアである。アリスはｚ’を自身の秘密鍵を用いて解読し、結果の自身のシェアを取得する。
【００３６】
【数６】
0005127590.tif 000007
【００３７】
すべての中間結果を計算した後、アリス及びボブは
【００３８】
【数７】
0005127590.tif 000008
【００３９】
であるような加法ベクトルａｋ及びｂｋを有しており、式中、ｃｋは相互相関の全体である。ボブのＫ個のレコーディングのそれぞれに対して相互相関が実施される。終了時、両者は相互相関１１０の自身の部分結果のＫ個のベクトルを有する。
【００４０】
相互相関の最大値の位置特定
したがって、結果は秘密の加法シェアａｋ及びｂｋとして分散される。以下に留意されたい。
【００４１】
【数８】
0005127590.tif 000009
【００４２】
ここで、相互相関ベクトルの最大値１０５を位置特定する(１２０)必要がある。アリス及びボブは安全な最大値発見プロトコルを使用してこのような対の比較を行い、その値を最大値の加法シェアとして学習する。比較を安全に実施するために、アリス及びボブはYaoのミリオネア問題を使用する。既知のミリオネア問題は、誰が最も富んでいるかをどれだけ富んでいるかを明かすことなく解くものである。
【００４３】
アリス及びボブは、最大値に対応するシェアを位置特定した後、２つのＫベクトルＡ及びＢを構築する。アリスはａｋｉをベクトルＡのｋ番目の成分に割り当て、ボブはｂｋｉをベクトルＢのｋ番目の成分に割り当てる。ただし、ｉは最大値のインデックス１０６である。ベクトルＡ及びＢのｋ番目の成分の和はｘｋとｙｋとの間の相互相関１１０の最大値１０５に等しい。
【００４４】
最良にマッチングするレコーディングのインデックスの確定
アリスのレコーディングは、ベクトルＡ及びＢの和が最大になるところのインデックスに対応する。本方法は、準同型暗号化の特性及び安全な順列作成プロトコルを再び利用して、ベクトルＡ及びＢの順列π(Ａ＋Ｂ)の加法シェアである(オーバーバー)Ａ及び(オーバーバー)Ｂを取得する。
【００４５】
アリスは
【００４６】
(オーバーバー)Ａ＋(オーバーバー)Ｂ−Ｒ
【００４７】
をボブに送信し、式中、Ｒはアリスによって選択される乱数である。ボブは(オーバーバー)Ａ及び(＋)(オーバーバー)Ｂ−Ｒの最大成分のインデックスをアリスに返信する。これによって、アリスが順列πの逆数を使用してインデックスを確定することが可能となる。ボブはその順列を知らないため、レコーディングのインデックスを学習することができず、アリスは自身のプライバシーを保護している。アリスによって選択される乱数Ｒはボブが最大値の値を学習しないことを保証する。
【００４８】
順列作成プロトコルは準同型暗号化に基づいており、以下のように説明することができる。ベクトルＡ及びＢ並びに順列πがアリスにしか知られていないとすると、所望の結果は
【００４９】
(オーバーバー)Ａ＋(オーバーバー)Ｂ＝π(Ａ)＋π(Ｂ)
【００５０】
であるような加法シェア(オーバーバー)Ａ及び(オーバーバー)Ｂである。
【００５１】
ボブは秘密鍵と公開鍵との対(ｓｋ，ｐｋ)を生成し、公開鍵をアリスに送信する。ボブはベクトルＢの各成分を、自身の公開鍵ｐｋを使用して暗号化し、結果として生じるベクトルをアリスに送信する。
【００５２】
アリスはランダムベクトルＳを生成し、ベクトルθを求める。ここで、θｉ＝ＥＮ(Ｂｉ，ｐｋ)ＥＮ(Ｓｉ，ｐｋ)(ｉ＝１，．．．，Ｋ)である。準同型特性は、θｉがＢｉ＋Ｓｉを暗号化したものであることを意味する。
【００５３】
アリスは、θの順列を作成してπ(θ)をボブに送信する。ボブはベクトルを自身の秘密鍵ｓｋを使用して解読して、(オーバーバー)Ｂを取得する。これは、(オーバーバー)ＢがベクトルＢ＋Ｓの順列であることを意味する。Ｓはアリスだけが知っているランダムベクトルであるため、ボブはこれを元のベクトルＢと比較して順列を発見することができない。
【００５４】
アリスはＡ−Ｓを求め、この順列が作成されて、πを使用して
【００５５】
(オーバーバー)Ａ＝π(Ａ−Ｓ)
【００５６】
が取得される。
【００５７】
情報の検索
アリスはインデックス１０６を確定した後、ボブのデータベースにインデックスを付して情報を検索することができる。ボブが自身のデータベースのプライバシーを保護することを望む場合、本方法は安全な紛失(oblivious)転送を使用する。
【００５８】
σがアリスだけが知っているレコーディングのインデックス１０６を示すものとする。ボブの情報１０３のデータベースはベクトルμ＝{μ１，．．．，μＫ}として符号化される。アリスはμをボブに明らかにすることなくデータベースからμを受信する。
【００５９】
アリスは準同型の秘密／公開鍵対(ｓｋ，ｐｋ)を生成してｐｋをボブに送信する。アリスはσを暗号化してｚ＝ＥＮ(σ，ｐｋ)をボブに送信する。ボブは乱数ｒｋを選択して
【００６０】
【数９】
0005127590.tif 000010
【００６１】
を求め、ｋをアリスに送信する(ｋ＝{１，．．．，Ｋ})。これはμｋ＋ｒｋ(σ−ｋ)を暗号化したものに等しいことに留意されたい。アリスはｄσを解読してμを取得する。
【００６２】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内でさまざまな他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべてのこのような変形及び変更を包含することである。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施の形態によるオーディオレコーディングをマッチングさせる方法及びシステムの流れ図である。
【図１】
0005127590.tif 000011