(57)【要約】  メッセージおよびメッセージに関連づけられた識別パラメータが得られる。メッセージは複数のユニットを含む。複数の１ユニットメッセージ認証コードが生成され、各１ユニットメッセージ認証コードはメッセージの複数のユニットのうちの各ユニットに対応し、各１ユニットメッセージ認証コードは、メッセージに関連づけられた識別パラメータ、複数のユニットのうちの所与の１つ、および、メッセージ内の所与のユニットの位置に基づいて生成される。したがって、メッセージの各ユニットの検証は、例示のみの目的で、例えばガーブルドサーキットなどの安全な計算の方法内で効率的に実行できる。
2017524306.tif 000002
【特許請求の範囲】
【請求項１】
方法であって、
メッセージおよびメッセージに関連づけられた識別パラメータを得るステップであって、メッセージが複数のユニットを含む、得るステップ、および、
複数の１ユニットメッセージ認証コードを生成するステップであって、各１ユニットメッセージ認証コードがメッセージの複数のユニットのうちの各ユニットに対応し、各１ユニットメッセージ認証コードが、メッセージに関連づけられた識別パラメータ、複数のユニットのうちの所与の１つ、および、メッセージ内の所与のユニットの位置に基づいて生成される、生成するステップを含み、
ステップの１つまたは複数が処理デバイスによって実行される、
方法。
【請求項２】
メッセージがＸＯＲ暗号化キーを含む、請求項１に記載の方法。
【請求項３】
メッセージが複数のビットを含み、複数の１ビットメッセージ認証コードの各々がメッセージの複数のビットの各々にそれぞれ生成されるように、前記複数のユニットの各ユニットが単一のビットからなる、請求項１に記載の方法。
【請求項４】
複数の１ユニットメッセージ認証コードが、メッセージ認証コードキーを用いて、メッセージの複数のユニットに関してそれぞれ生成される、請求項１に記載の方法。
【請求項５】
複数の１ユニットメッセージ認証コードをメッセージの保持者に提供するステップをさらに含む、請求項４に記載の方法。
【請求項６】
メッセージ認証コードキーを検証者に提供するステップをさらに含み、検証者が、続いて複数の１ユニットメッセージ認証コードと共に受信し、当該メッセージと称されるメッセージの真正性を検証できるようにする、請求項５に記載の方法。
【請求項７】
検証者が当該メッセージと称されるメッセージの内容を知ることを認可されていないという条件で、当該メッセージと称されるメッセージおよび複数の１ユニットメッセージ認証コードが、当該メッセージと称されるメッセージの真正性の検証を行うように、安全な計算プロトコルに提供される、請求項６に記載の方法。
【請求項８】
安全な計算プロトコルが、プライベートなデータベースシステムの一部であるガーブルドサーキットに基づく安全な計算プロトコルを含む、請求項７に記載の方法。
【請求項９】
メモリおよびメモリに動作可能に結合されたプロセッサを含む、請求項１から８のいずれか一項に記載の方法のステップを実行するように構成された、装置。
【請求項１０】
方法であって、
プライベートなデータベースシステムに関連づけられた検証者において、検証されたビットが検証者に知られることを阻止しながら、ビットの組のうちの所与のビットの有効性を検証するステップを含み、
検証するステップが、プライベートなデータベースシステムの一部として検証者を実装する処理デバイスによって行われる、
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に説明された発明は、内務省／国立ビジネスセンター（ＤＯＩ／ＮＢＣ）による情報先端研究プロジェクト活動（ＩＡＲＰＡ）によって授与された契約番号Ｄ１１ＰＣ２０１９４に基づく政府の支援を受けてなされたものである。政府は本発明に若干の権利を有する。
【０００２】
本出願は概して暗号学に関し、より具体的には、暗号化操作における悪意のある変更に対する保護の技法に関する。
【背景技術】
【０００３】
この箇所は、本発明のより良い理解を容易にすることに役立ち得る態様を紹介する。したがって、この箇所の説明はこの観点から読まれるものであり、従来技術にあるもの、または従来技術にないものに関する承認として理解されるものではない。
【０００４】
ＸＯＲ暗号化は、シャノン（Ｓｈａｎｎｏｎ）暗号化としても知られているが、暗号学において広く用いられる暗号化の最も簡単な形式の１つである。それはまた、実装の効率が高い。キーｋを用いるメッセージｍを暗号化するためには、システムまたはデバイスは単にｃ＝ｍ（ｘｏｒ）ｋを計算するのみであり、ここで（ｘｏｒ）は二進排他的ＯＲ演算子を表す。例えば高度暗号化標準（ＡＥＳ）などの、他の非常に効率的な暗号化スキームが存在しながらも、ＸＯＲ暗号化はガーブルドサーキット（ＧＣ）に基づく安全な計算の応用に特に適用可能であり得る。そのような応用は、しかしながら、悪意のある変更の影響を受けやすい。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第８，４８８，７９１号明細書
【非特許文献】
【０００６】
【非特許文献１】Ａ．Ｙａｏ、「Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｓｅｃｕｒｅ  Ｃｏｍｐｕｔａｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＦＯＣＳ、１６０−１６４頁、１９８２年
【発明の概要】
【課題を解決するための手段】
【０００７】
例示的な実施形態が、悪意のある変更から、例えばＸＯＲ暗号化操作などの、しかしそれには限定されない、暗号化操作を保護する技法を提供する。
【０００８】
例えば、一実施形態において、方法は以下のステップを含む。メッセージおよびメッセージに関連づけられた識別パラメータが得られる。メッセージは複数のユニットを含む。複数の１ユニットメッセージ認証コードが生成され、各１ユニットメッセージ認証コードはメッセージの複数のユニットのうちの各ユニットに対応し、各１ユニットメッセージ認証コードは、メッセージに関連づけられた識別パラメータ、複数のユニットのうちの所与の１つ、および、メッセージ内の所与のユニットの位置に基づいて生成される。
【０００９】
一例において、メッセージがＸＯＲ暗号化キーであってもよく、識別パラメータがキーに関連づけられた一意的な識別子であってもよい。メッセージ認証コードキーが、複数の１ユニットメッセージ認証コードを生成するように用いられる。ＸＯＲ暗号化キーの例において、ユニットが、複数の１ビットメッセージ認証コードの生成をもたらすビットであってもよい。ＸＯＲ暗号化キーの各ビットの検証が、例えば、例示のみの目的で、ＧＣなどの安全な計算の方法の中で、したがって効率的に実行され得る。
【００１０】
別の実施形態において、中で符号化されている１つまたは複数のソフトウェアプログラムの実行可能なコードを有する、プロセッサ可読な記憶媒体を含む製品が提供される。少なくとも１つの処理デバイスによって実行されると、１つまたは複数のソフトウェアプログラムが、上記方法のステップを実施する。
【００１１】
さらに別の実施形態において、装置が、上記方法のステップを実行するように構成されたメモリおよびプロセッサを含む。
【００１２】
有利には、ＧＣに基づく安全な計算用途において、ＸＯＲ暗号化キーの各ビットに関する１ビットメッセージ認証コードの生成が、ＧＣへのキーの真正性を効率的に検証するように用いられることができ、したがって、ＸＯＲ暗号化キーの悪意のある変更を阻止する。さらに、例示的な実施形態は、プライベートなデータベースシステムに関連づけられた検証者において、検証されたビットが検証者に知られることを阻止しながら、ビットの組のうちの所与のビットの有効性の検証を提供する。
【００１３】
本明細書に説明された実施形態の、これらの、およびその他の特徴および利点は、添付の図面および以下の発明を実施するための形態からより明らかになるであろう。
【図面の簡単な説明】
【００１４】
【図１】一実施形態による、保護されたＸＯＲ暗号化を用いるプライベートなデータベースシステムを示す図である。
【図２】一実施形態による、ＸＯＲ暗号化を保護する方法論を示す図である。
【図３】１つまたは複数の実施形態による、保護されたＸＯＲ暗号化を用いるシステムが実施される処理プラットフォームを示す図である。
【発明を実施するための形態】
【００１５】
例示的な実施形態は、例としての計算システム、データ記憶システム、データベースシステム、通信ネットワーク、処理プラットフォーム、システム、ユーザデバイス、ネットワークノード、ネットワーク要素、クライアント、サーバ、および関連する通信プロトコルを参照して、本明細書に記載される。例えば、例示的な実施形態は、ガーブルドサーキット（ＧＣ）に基づく安全な計算または操作を利用するアプリケーションによって、および／または、アプリケーション内で、使用に特に適する。しかしながら、実施形態は、説明される特定の構成を用いることに限定されるものではなく、悪意のある変更から、例えばＸＯＲ暗号化などの、暗号化操作を保護する技法を提供することが望ましい任意の環境に、むしろより一般に適用可能なものであることが理解されるべきである。
【００１６】
ＧＣに基づく計算において、一般に、評価される関数は、１つまたは複数の論理ゲートからなるブール回路として表され、ゲートの入力および出力端子がワイヤであるとみなされる。ランダムな（ガーブルド処理された）入力値が各ゲートに関連づけられた各ワイヤに割り当てられる。そしてガーブルド処理されたテーブルが構築され、回路の各入力ワイヤの割り当てられたガーブルド処理された入力値が与えられると、対応するガーブルド処理された出力値が回路の各出力ワイヤに関して計算される。回路は、したがって関数は、各回路ゲートに関するそのようなガーブルド処理されたテーブルを構築することによって評価される。ＧＣに基づく安全な用途において、ガーブルドサーキットは暗号化された入力データに基づいて評価される。ＧＣに基づく安全な計算の使用例は、いわゆる「プライベートなデータベースシステム」の一部として実施される安全なデータベース検索が挙げられるが、これに限られない。プライベートなデータベースシステムは、入力値のプライバシーを維持しながら、入力値に基づいて関数を評価することが可能である。
【００１７】
したがって、プライベートなＤＢ検索において、ＧＣが暗号化されたデータ上で実行されるため、暗号化はＧＣの内部で除去されなければならない。この除去タスクは、ＸＯＲ暗号化を用いる際に最小限のコストを有する。しかしながら、すべての他の有名な暗号化スキーム（例えばＡＥＳ）を用いる際、除去タスクは非常に高いコストを招く可能性がある。
【００１８】
しかしながら、ＸＯＲ暗号化によるある問題は、それが非常に展性がある（変更を受けやすい）ことである。特に、メッセージを知ることなしに、暗号化キーを保持する当事者（例えば、敵対者）は、秘密キーの対応するビットを反転することのみで、メッセージのビットを反転することができる（すなわち、ビット反転とは、論理０のビット値を論理１のビット値に変更する、または逆に論理１のビット値を論理０のビット値に変更することを意味する）。敵対者によって行われる際、このビット反転は「悪意のある変更」とみなされる。
【００１９】
あるプライベートなデータベースシステムにおけるＸＯＲ暗号化の別の問題は、メッセージおよびキーが非常に大きい、例えば５０−１００ギガバイト（ＧＢ）ことがあることである。システムにはキーまたはメッセージの顕著な増加に対する余裕がほとんどない（例えば、補助的認証情報を記憶するために追加記憶装置が必要になるため）。
【００２０】
実施形態は、暗号化キーを効率的に認証することによって、上記のおよび他の問題を解決する解決方法を提供する。
【００２１】
既存の解決方法、例えばキーｋに関するメッセージ認証コード（ＭＡＣ）を構築することは、キー全体が完全に正しく、キーにおけるいかなる変化も非常に高い確率で検出されることを保障することに主に焦点を当てている。このことは少なくとも２つの欠点をもたらす。
【００２２】
１）既存の解決方法の効率は、回路の複雑性（したがって、プライベートなデータベース設定における安全な計算をもたらすことに関連する非常に高いコスト）の観点からは乏しい。
【００２３】
２）メッセージおよびキーが異常に長い場合、キーのビットごとに基づいて敵対的なキー所有者を検出する確率が小さい（例えば０．５）ことを許容する解決方法を排除するかもしれない、ということを既存の解決方法は許容しない。キー所有者がキーのあまりに多いビットを変更しようとした場合、キー所有者はかなりの確率で捕えられるだろうが、数ビットしか変更しない場合は検出されずに済むかもしれない。多くの用途において、プライベートなデータベース設定における場合と同様に、数ビットしか変更しないことは全体的な成果に影響しない。
【００２４】
いくつかの実施形態は、キーｋ全体に関して１つのＭＡＣを生成することとは対照的に、暗号キーｋの各ビットに関して別々のメッセージ認証コード（ＭＡＣ）を生成することによって、これらのおよびその他の欠点を克服する。プライベートなデータベース用途において、各メッセージは固有の識別子、すなわちｍｓｇ−ｉｄを有する。この実施形態において、そのためにＭＡＣが生成される「メッセージ」は暗号化キーそれ自身であるため、ｍｓｇ−ＩＤは暗号化キーｋに関連づけられた固有の識別子（識別パラメータ）である。したがって、個別のＭＡＣはＭＡＣキー、メッセージＩＤ、ビット位置、およびキービットを用いて生成される。このＭＡＣは、暗号化キービットが正しく用いられていることを確認可能な検証者に与えられてもよい。
【００２５】
そのような実施形態において、もたらされるＭＡＣは非常に短い（例えば１ビット）ため、ＭＡＣ証明者の記憶空間があまり大きくなく、容認できるものであることは理解されるべきである（検証者はＭＡＣキーを有し、検証のためにＭＡＣ自体を生成することができることに留意）。さらに、検証（プライベートなデータベース用途においてＧＣ内部で行われてもよい）は非常に効率的である。
【００２６】
図１は一実施形態による保護されたＸＯＲ暗号を用いるプライベートなデータベースシステムの例を示す。しかしながら、本明細書に記載の暗号操作保護技法がプライベートなデータベースシステムにおける保護されたＸＯＲ暗号を提供するために特によく適していながらも、１つまたは複数の前記技法が、代替として、他の暗号化操作ならびに／または他の用途およびシステムと共に実装されてもよいことは理解されるべきである。
【００２７】
示されるように、プライベートなデータベースシステム１００は、ネットワーク１３０を介して接続されるクライアント（Ｃ）１１０とサーバ（Ｓ）１２０とを含む。クライアント１１０とサーバ１２０とは、２当事者安全計算プロトコル１４０への入力を提供する。２当事者安全計算プロトコル１４０は、ネットワーク１３０に接続された、および／または、クライアント１１０とサーバ１２０の一方または両方に直接接続された、それ自身の個別のモジュールとして実装されてもよい。２当事者安全計算プロトコルの機能の一部あるいはすべては、代替として、クライアント１１０、サーバ１２０、またはそれらのある組み合わせにおいて実装されることもできる。よく知られている２当事者安全計算プロトコル、例としてのみだが、Ａ．Ｙａｏ、「Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｓｅｃｕｒｅ  Ｃｏｍｐｕｔａｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＦＯＣＳ、１６０−１６４頁、１９８２年で説明されたＹａｏガーブルドサーキットプロトコルがプロトコル１４０に関して用いられることができる。プロトコル１４０に関して用いられ得る２当事者安全計算プロトコルの別の例は、Ｇ．Ｂａｅｃｈｌｅｒ  ａｎｄ  Ｖ．Ｙ．Ｋｏｌｅｓｎｉｋｏｖに２０１３年７月１６日に発行された米国特許第８，４８８，７９１号明細書、題名「Ｓｅｃｕｒｉｎｇ  Ｔｗｏ−Ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ  Ａｇａｉｎｓｔ  Ｍａｌｉｃｉｏｕｓ  Ａｄｖｅｒｓａｔｉｅｓ」に説明される、１つまたは複数の、安全な２当事者の計算方法論であってもよい。
【００２８】
プロトコル１４０が米国特許第８，４８８，７９１号明細書のプロトコルであっても、任意のよく知られている既存の２当事者安全計算プロトコルであっても、プロトコル１４０は、入力をプライベートに保ちながら、計算出力を生成する。プライベートなデータベースシステム１００の例において、計算は暗号化されたデータベース検索であり、入力はキー（ｋ）１１２またはその一部、クライアント１１０からの認証子文字列（Ａｕｔｈ）１１４、および、サーバ１２０からの暗号化されたインデックス（Ｉ）１２２またはその一部である（インデックス全体を暗号化するキーは非常に大きいことがあり、アプリケーションはそれと共に機能しているビットに対応するビットのみを望むことに注意）。これらの入力は図２の文脈で以下にさらに説明される。
【００２９】
１つの当事者がより信頼度が低い（プライベートなデータベース例におけるクライアント）、および、その入力が検証されるべきである（例えば、暗号化キー、ワンタイムパッドエントリなど）、および、保護を妨げることとなる結果が最小になる、代替の実施形態が実装可能であることは理解すべきである。例えば、プライベートなデータベースの例において、ブルームフィルタが検索を実行するように用いられることが可能であり、クライアントは現実に、成功するためには列において多くの回数不正行為（すなわちフリップビット）をしなければならず、成功は起こりそうにない。
【００３０】
図２は、一実施形態による保護ＸＯＲ暗号化の方法論を示す図である。図２の方法論２００は、ＸＯＲ暗号化を実行するように用いられる暗号化キーｋの各ビットに関する個別の１ビットメッセージ認証コード（ＭＡＣ）を生成する。数ある利点の中でも、本方法論は復号キーの正確な使用を保障する。さらに、以下に例示的に述べられる当事者、すなわち「キー保持者」と、「検証者」とは、それぞれ、図１のクライアント１１０と、２当事者安全計算プロトコル１４０を実装するモジュールとであってもよい。代替として、１人または複数の他の当事者（図１に示されるまたは示されない）がキー保持者および／または検証者の機能を実行することができる。
【００３１】
ｍｓｇ−ｉｄをメッセージのある識別パラメータ（すなわち、この実施形態ではＸＯＲ暗号化キー）とする。
【００３２】
ｋは用いられるＸＯＲ暗号化キー（すなわち、ＸＯＲマスク）を表すものとする。
【００３３】
ｋにおけるビットの数をｎとする。
【００３４】
ＭＡＣを任意の１ビットメッセージ認証コード（ＭＡＣ）とする。１ビットＭＡＣが０．５の確率で偽造されると考えられるが、この偽造の確率はある用途（例えば、本明細書で例示的に説明されるプライベートなデータベース用途）において容認できる。
【００３５】
例示のみの目的で、１ビットＭＡＣは、任意のＭＡＣを計算し、暗号ハッシュ関数（例示のみの目的で、ＳＨＡ−２５６）をＭＡＣの出力に適用し、ハッシュ関数の出力の最後のビットをとることによって得られる。また、ＡＥＳに基づくＭＡＣにおいて、任意のビットの出力は、例示のみの目的で、最後のビットをとることができる。
【００３６】
したがって、キーｋが与えられ、方法論２００は以下のように実行される。
【００３７】
ステップ２０２：マスターＭＡＣキーｋｍを生成する。
【００３８】
ステップ２０４：ｋの各ビットｉ、１＜＝ｉ＜＝ｎに関して、対応するｉ番目の検証ビットを１ビットａｕｔｈｉ＝ＭＡＣ｛ｋｍ｝（ｍｓｇ−ｉｄ｜ｉ｜ｋ［ｉ］）とする。
【００３９】
ステップ２０６：キーｋの保持者に検証ビットを提供する。一実施形態において、クライアントはこれらの検証ビットを受信し、後にこれらのビットを用いて、ｋに対応するビットが真正であることを証明する証明者の役割を果たすことが可能であることに留意する。
【００４０】
ステップ２０８：ＭＡＣキーｋｍを、ｋの提示されたビットを検証したいと考える任意の当事者（すなわち検証者）に提供する。
【００４１】
ステップ２１０：キーｋを保持する当事者（すなわちキー保持者）が、ビットｋ’ｉを提示する（変更される可能性あり）際、この当事者はそれと共にビットａｕｔｈ’ｉも提示する（変更される可能性あり）。検証者はａｕｔｈ”ｉ＝ＭＡＣ｛ｋｍ｝（ｋ’ｉ）を計算し、ａｕｔｈ”ｉ＝ａｕｔｈ’ｉである場合でかつその場合のみに受認する（検証成功の表示をシステムに提供する）。このようにｋ’ｉはｋｉであると称されることに留意する。
【００４２】
ステップ２１２：検証者がｋ’ｉを知ることを可能とされておらず（例示のプライベートなデータベースシステム設定におけるものとして）、評価がＧＣ内部で行われる場合、検証者は、可能性のあるｋｉの値と対応する認証子（ａｕｔｈｉの値）の両者をＧＣに入力する。
【００４３】
ステップ２１４：そして、ＧＣの内部で、少なくとも１つの対が合致することを決定するように検証操作が行われる。検証計算は、基本的な技法としてＧＣを用いて実行される安全な計算内のサブルーチンとして実装されることができる。特に、証明者（例えばクライアント）によって提供された対＜ｋｅｙ  ｂｉｔ，ａｕｔｈ  ｂｉｔ＞が、検証者（例えば、サーバは検証操作のホストとなり、したがって検証者となることができる）によって提供された２つの可能性のある対（すなわち、＜０，ａｕｔｈ０＞、＜１，ａｕｔｈ１＞）の１つと合致した場合、安全な計算は「受認」を出力する。
【００４４】
キー保持者が正直である（すなわち敵対者ではない）場合、ｋ”ｉ＝ｋｉであることに注意する。そうでなければ、ｋ’ｉまたはａｕｔｈ’ｉのいずれかが変更された場合（すなわち敵対者によって）、出力ビットｋ”ｉは０．５の確率でｋｉに等しい。特に、キーの特定のビットを変更するいかなる試みも、０．５の確率で不正確なＭＡＣをもたらす。
【００４５】
有利なことに、例示の実施形態はプライベートなデータベースシステム内の重要な特徴を容易にする。すなわち、検証されたビットが検証者から隠されることを可能にしながら、長い文字列の任意のビットの有効性を効率的に検証することである。これは、認可されていない文字列変更が、プライベートなデータベースシステムにおいてプライバシーの保証を妨げることをもたらす可能性があるため、望ましい。１ミリ秒のオーダーである本明細書に記載の１ビットＭＡＣ手法と比較して、既存の解決方法は例えば１秒のオーダーであり、時間に関して非常にコストがかかる。
【００４６】
本明細書に記載の例示的実施形態が、メッセージの各ビットに関する個別のＭＡＣ（例えばＸＯＲ暗号化キー）を生成することを提供しながら、代替の実施形態が、メッセージの各ビットよりも小さい個別のＭＡＣを生成することを提供することを理解されたい。例えば、メッセージがＮ個のビットを含む場合、個別のＭＡＣがＮ−ｘ個のビットのそれぞれに関して生成可能であり、ここでｘは、それに関してＭＡＣが生成されないビットの数（例えば１、２、３、．．．）であり、それらの特定のビットに関してＭＡＣが生成されないことは、本明細書に記載された暗号保護技法の１つまたは複数の利益に著しい影響を与えるものではない。
【００４７】
さらに、メッセージの長さを定義する最小の測定単位としてビットが本明細書で例示的に用いられるが（すなわち、メッセージは複数のビットから構成される）、メッセージはより一般的に、複数のユニットから構成され、したがってそれぞれ複数の１ユニットＭＡＣの生成をもたらしてもよいことを理解されたい。ビット以外のユニットの一例は、それに関してそれぞれの複数のＭＡＣが生成される、複数のマルチビットユニットをメッセージが含む（すなわち、メッセージの各マルチビットユニットに関して１つの個別のＭＡＣ）、マルチビットユニットが挙げられるが、それに限定されない。
【００４８】
図３に移ると、処理プラットフォームが示され、保護されたＸＯＲ暗号を用いるシステム、例えばプライベートなデータベースシステム（例えば、図２の方法論２００を実装する図１のシステム１００）が、１つまたは複数の実施形態によって実装される。この実施形態における処理プラットフォーム３００は、ネットワーク３０４を介して互いに通信する３０２−１、３０２−２、３０２−３、．．．３０２−Ｐと表示された複数の処理デバイスを含む。プライベートなデータベースシステム１００の１つまたは複数の構成要素および／またはモジュール（例えばクライアント１１０、サーバ１２０、プロトコルモジュール１４０、および明確には示されない様々な他のモジュール）は、したがって、１つまたは複数のコンピュータまたは他の処理プラットフォーム要素でそれぞれ実行することができ、それぞれが、本明細書で「処理デバイス」としてより一般に言及されるものの例としてみなされることができる。図３に示されるように、そのようなデバイスは、少なくとも１つのプロセッサおよび関連づけられたメモリを一般に含み、本明細書に説明されたシステムおよび方法論の特徴をインスタンス化する、および／または制御する、１つまたは複数の機能的モジュールを実装する。複数の要素またはモジュールが、所与の実施形態において単一の処理デバイスによって実装されてもよい。
【００４９】
処理プラットフォーム３００における処理デバイス３０２−１は、メモリ３１２に結合されたプロセッサ３１０を含む。プロセッサ３１０はマイクロプロセッサ、マイクロコントローラ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＧＰＡ）、または他の型の処理回路、同様に、そのような回路要素の部分または組み合わせを含んでもよい。本明細書に開示されるシステムの構成要素は、メモリに記憶され、プロセッサ３１０などの処理デバイスのプロセッサによって実行される、１つまたは複数のソフトウェアプログラムの形式で少なくとも一部は実装され得る。自身の中で具現化されるそのようなプログラムコードを有するメモリ３１２（または他の記憶デバイス）は、プロセッサ可読記憶媒体として本明細書でより一般的に言及されるものの例である。そのようなプロセッサ可読記憶媒体を含む製品が実施形態として考慮される。所与のそのような製品は、例えば、記憶ディスク、記憶アレイ、またはメモリを含む集積回路などの記憶デバイスを含んでもよい。本明細書で用いられる「製品」という用語は、一時的な伝搬する信号を排除するものと理解すべきである。
【００５０】
さらに、メモリ３１２はランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）または他の型のメモリなどの、任意の組み合わせの電子メモリを含んでもよい。１つまたは複数のソフトウェアプログラムは、処理デバイス３０２−１などの処理デバイスによって実行される際に、システム１００および方法論２００の１つまたは複数の構成要素／ステップに関連づけられた機能をデバイスに実行させる。当業者は、本明細書に提供された教示を与えられたそのようなソフトウェアを実装することが容易に可能であろう。実施形態を具現化するプロセッサ可読記憶媒体の他の例は、例えば、光学または磁気ディスクが挙げられる。
【００５１】
ネットワークインターフェース回路３１４もまた処理デバイス３０２−１に含まれ、それは処理デバイスをネットワーク３０４および他のシステム構成要素とインターフェース接続するように用いられる。そのような回路は、当業者によく知られる型の従来の送受信機を含んでもよい。
【００５２】
処理プラットフォーム３００の他の処理デバイス３０２は、図の処理デバイス３０２−１に関して示されるものと同様に構成されると前提される。
【００５３】
図３に示された処理プラットフォーム３００は、バッチ処理システム、並行処理システム、物理的機械、バーチャル機械、バーチャルスイッチ、記憶ボリューム、論理ユニットなどの知られている追加の構成要素を含んでもよい。また、図３に示された特定の処理プラットフォームが例示のみの目的で示され、図１のプライベートなデータベースシステム１００が追加のまたは代替の処理プラットフォーム、同様に、任意の組み合わせの多くの異なる処理プラットフォームを含んでもよい。
【００５４】
また、クライアント、サーバ、コンピュータ、記憶デバイス、または他の構成要素の多くの他の配置が可能である。そのような構成要素は、ワイドエリアネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、衛星ネットワーク、電話またはケーブルネットワーク、ストレージネットワーク、集中ネットワーク、またはそれらのおよび他の型のネットワークの様々な部分もしくは組み合わせなど、任意の型のネットワーク（例えば図１のネットワーク１３０および／または図３のネットワーク３０４）を介してシステムの他の要素と通信することができる。
【００５５】
特定の通信プロトコルを利用するシステムおよびネットワークの文脈で、例示されたある実施形態が本明細書に説明されるが、他の型のシステムおよびネットワークもまた、他の実施形態において使用されることができる。上記のように、本明細書で使用される用語「システム」および「ネットワーク」は、それゆえ広く解釈されることが意図されている。さらに、上記実施形態は例示のみの目的であり、いかなる形でも限定と解釈されるべきではないことを強調すべきである。他の実施形態は、保護された暗号化（例えばＸＯＲ暗号）機能を実装する、異なる型のネットワーク、デバイスならびにモジュール構成、および、代替の通信プロトコル、処理ステップならびに操作を用いてもよい。ネットワークノードが通信する特定の様態は、他の実施形態では変わることがある。また、例示の実施形態を説明する文脈で行われる特定の前提は、本発明の要件と解釈されるべきではないことを理解すべきである。本発明はこれらの特定の前提が適用されない他の実施形態において実装可能である。これらの、および添付の特許請求の範囲内の多くの他の代替の実施形態は、当業者には容易に明らかとなる。
【図１】
2017524306.tif 000003
【図２】
2017524306.tif 000004
【図３】
2017524306.tif 000005
【手続補正書】
【提出日】平成29年3月16日(2017.3.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
方法であって、
メッセージおよびメッセージに関連づけられた識別パラメータを得るステップであって、メッセージが複数のユニットを含む、得るステップ、
複数の１ユニットメッセージ認証コードを生成するステップであって、各１ユニットメッセージ認証コードがメッセージの複数のユニットのうちの各ユニットに対応し、各１ユニットメッセージ認証コードが、メッセージに関連づけられた識別パラメータ、複数のユニットのうちの所与の１つ、および、メッセージ内の所与のユニットの位置に基づいて生成される、生成するステップ、および
１ユニットメッセージ認証コードの第１の１つの値と、ガーブルドサーキットに基づく安全な計算プロトコルへの入力としての対応する第１の認証子文字列との、２つ以上の可能な組み合わせを提供するステップであって、ガーブルドサーキットに基づく安全な計算プロトコルが、第１の１ユニットメッセージ認証コードの有効性の表示を出力する、提供するステップを含み、
ステップの１つまたは複数が処理デバイスによって実行され、
メッセージが暗号化キーを含む、方法。
【請求項２】
暗号化キーがＸＯＲ暗号化キーを含む、請求項１に記載の方法。
【請求項３】
メッセージが複数のビットを含み、複数の１ビットメッセージ認証コードの各々がメッセージの複数のビットの各々にそれぞれ生成されるように、前記複数のユニットの各ユニットが単一のビットからなる、請求項１に記載の方法。
【請求項４】
複数の１ユニットメッセージ認証コードが、メッセージ認証コードキーを用いて、メッセージの複数のユニットに関してそれぞれ生成される、請求項１に記載の方法。
【請求項５】
複数の１ユニットメッセージ認証コードをメッセージの保持者に提供するステップをさらに含む、請求項４に記載の方法。
【請求項６】
メッセージ認証コードキーを検証者に提供するステップをさらに含み、検証者が、続いて複数の１ユニットメッセージ認証コードと共に受信し、当該メッセージと称されるメッセージの真正性を検証できるようにする、請求項５に記載の方法。
【請求項７】
当該メッセージと称されるメッセージおよび複数の１ユニットメッセージ認証コードが、当該メッセージと称されるメッセージの内容を検証者に知らせることなく当該メッセージと称されるメッセージの真正性の検証を実行するガーブルドサーキットに基づく安全な計算プロトコルに提供される、請求項６に記載の方法。
【請求項８】
ガーブルドサーキットに基づく安全な計算プロトコルがプライベートなデータベースシステムの一部である、請求項７に記載の方法。
【請求項９】
メモリおよびメモリに動作可能に結合されたプロセッサを含む、請求項１に記載の方法のステップを実行するように構成された、装置。
【請求項１０】
方法であって、
プライベートなデータベースシステムに関連づけられた検証者において、メッセージの複数のユニットのうちのそれぞれのユニットに対応する複数の１ユニットメッセージ認証コードの所与の１つ、および対応する認証子文字列を受信するステップであって、所与の１ユニットメッセージ認証コードが、メッセージに関連づけられた識別パラメータ、複数のユニットのうちの所与の１つ、および、メッセージ内の所与のユニットの位置に基づいて生成される、受信するステップ、および、
検証者において、メッセージの内容が検証者に知られることを阻止しながら、所与の１ユニットメッセージ認証コードの有効性を検証するステップを含み、
検証するステップが、プライベートなデータベースシステムの一部として検証者を実装する処理デバイスによって行われ、所与の１ユニットメッセージ認証コードおよび対応する認証子文字列の値の２つ以上の可能な組み合わせを、ガーブルドサーキットに基づく安全な計算プロトコルに入力することと、第１の１ユニットメッセージ認証コードの有効性を示す出力を、ガーブルドサーキットに基づく安全な計算プロトコルから受信することとを含み、
メッセージが暗号化キーを含む、方法。
【国際調査報告】
2017524306.tif 000006
2017524306.tif 000007
2017524306.tif 000008