(57)【要約】  物理的複製不可能関数（ＰＵＦ）入力およびＰＵＦ出力を有し、かつチャレンジの入力に応答して、ＰＵＦおよびチャレンジに特有の出力値を生成するように構築されたＰＵＦデバイスと、ＰＵＦ出力に接続されるプロセッサ入力を有し、かつＰＵＦ入力に接続されるプロセッサ出力を有するプロセッサであって、プロセッサ出力経由でのＰＵＦ入力へのチャレンジの発行を制御して、ＰＵＦ出力からの出力を受信し、かつ所望の暗号化出力のインスタンスに関して以下の一連のステップを複数回実行するように構成されたプロセッサと、を備える、ＰＵＦおよび閾値暗号化を含む認証システムならびにデバイス。
2018507658.tif 000002
【特許請求の範囲】
【請求項１】
認証システムで使用のための認証可能デバイスであって、
ａ）物理的複製不可能関数（「ＰＵＦ」）入力およびＰＵＦ出力を有し、かつチャレンジの入力に応答して、前記ＰＵＦおよび前記チャレンジに特有の出力値を生成するように構築されたＰＵＦデバイスと、
ｂ）前記ＰＵＦ出力に接続されるプロセッサ入力を有し、かつ前記ＰＵＦ入力に接続されるプロセッサ出力を有するプロセッサであって、前記プロセッサ出力経由での前記ＰＵＦ入力への前記チャレンジの発行を制御して、所望の暗号化出力のインスタンスに関して以下の一連のステップであって、
ｉ）前記プロセッサ出力経由で前記ＰＵＦ入力にチャレンジを発行し、前記ＰＵＦ出力から前記プロセッサ入力経由で対応する出力を受信し、
ｉｉ）ステップｉにおいて前記ＰＵＦ出力から受信された前記出力を使用して、前記認証可能デバイスの内部で、ステップｉにおいて前記ＰＵＦ出力から受信された前記出力と関連付けられた私有鍵または秘密の共有をリカバリし、かつ
ｉｉｉ）前記認証可能デバイスの内部で、ステップｉｉにおいてリカバリされた前記共有上で暗号演算を行い、
前記私有鍵または秘密が、共有に分配され、それによって、所望の暗号化出力の所与のインスタンスのために、演算が前記私有鍵または秘密を使用して行われることを共に可能にする異なる共有が、ステップｉｉにおいてリカバリされる、一連のステップを複数回実行するように構成されたプロセッサと、を備える、認証可能デバイス。
【請求項２】
前記プロセッサが、共有リフレッシュ手順を行って、前記私有鍵または秘密の共有をリフレッシュするように更に構成される、請求項１に記載の認証可能デバイス。
【請求項３】
前記プロセッサが、ステップｉｉｉにおいて行われる複数の暗号演算を組み合わせて、暗号化出力を生じるように更に構成される、請求項４に記載の認証可能デバイス。
【請求項４】
前記プロセッサが、ラグランジュ多項式補間を行うように更に構成される、請求項４に記載の認証可能デバイス。
【請求項５】
前記プロセッサが、楕円曲線暗号化を行うように更に構成される、請求項４に記載の認証可能デバイス。
【請求項６】
前記プロセッサが、分散型鍵生成を行うように更に構成される、請求項４に記載の認証可能デバイス。
【請求項７】
前記プロセッサが、２つ以上の論理コアを備え、前記プロセッサは、各論理コアが、他の論理コアでステップｉ〜ｉｉｉを同時に実行することができるように構成される、請求項１に記載の認証可能デバイス。
【請求項８】
前記プロセッサが、前記共有リフレッシュ手順を準備段階および適用段階に分割するように更に構成される、請求項４に記載の認証可能デバイス。
【請求項９】
前記プロセッサが、共有更新情報の生成を含む準備段階を行い、かつ１つ以上の共有に対する前記共有更新情報の適用を含む適用段階を行うように更に構成される、請求項１２に記載の認証可能デバイス。
【請求項１０】
前記プロセッサは、１つの共有リフレッシュ手順のみが一度に行われるように、前記準備および適用段階を行うように更に構成される、請求項１３に記載の認証可能デバイス。
【請求項１１】
前記デバイスが、再構成可能なＰＵＦを含む、請求項１４に記載の認証可能デバイス。
【請求項１２】
前記プロセッサが、ステップｉｉｉにおいて行われる複数の暗号演算を組み合わせて、暗号化出力を生じるように更に構成される、請求項１に記載の認証可能デバイス。
【請求項１３】
ステップｉｉにおいてリカバリされた前記共有が、ヘルパーによって、ステップｉにおいて前記ＰＵＦ出力から受信された前記出力と関連付けられる、請求項１に記載の認証可能デバイス。
【請求項１４】
前記ヘルパーが、前記デバイス上に記憶される、請求項１３に記載の認証可能デバイス。
【請求項１５】
前記プロセッサが、所望の暗号化出力の所与のインスタンスのために、それがステップｉを実行する前記複数回のそれぞれにおいて、異なるチャレンジを発行するように構成される、請求項１〜１４のいずれかに記載の認証可能デバイス。
【請求項１６】
前記プロセッサが、ゼロ知識証明認証プロトコルを行うように更に構成される、請求項１〜１４のいずれかに記載の認証可能デバイス。
【請求項１７】
前記デバイスが、２つ以上のＰＵＦを備える、請求項１〜１４のいずれかに記載の認証可能デバイス。
【請求項１８】
前記プロセッサが、２つ以上の論理コアを備える、請求項１〜１４のいずれかに記載の認証可能デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、ハードウェア検証、特に、ただし、非排他的に、置換による改ざんおよび破壊に対して保護するための束縛認証（ｂｉｎｄｉｎｇ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ）に関する。
【０００２】
関連出願の相互参照
本国際出願は、２０１５年５月５日に出願された米国非仮特許出願通し番号第１４／７０４，９１４号（「’９１４出願」）および２０１５年６月２２日に出願された（’９１４出願の一部継続であった）通し番号第１４／７４６，０５４号、ならびに２０１５年３月５日に出願された米国仮特許出願通し番号第６２／１２８，９２０号（「’９２０出願」）および２０１５年４月２１日に出願された通し番号第６２／１５０，５８６号（「’５８６出願」）の優先権の利益を主張する。’９２０および’５８６出願ならびに（米国特許出願公開第２０１５０３１７４８０号の訴訟の記録において公開された）２０１４年５月５日に出願された米国仮特許出願通し番号第６１／９８８，８４８号の内容もまた、参照によって本明細書に組み込まれる。
【背景技術】
【０００３】
ＰＵＦの固有特性は、暗号構築にいくつかの利点を提供する。一般に、ＰＵＦは、３つの主な利点（１）私有鍵の記憶の排除、（２）改ざん検出の提供、および（３）ハードウェアの信頼の基点の確立のうちの一部または全てを提供し得る。私有鍵の記憶は、ＰＵＦを評価して、そのＰＵＦを有するハードウェアの識別された部分に固有の値を動的に再生成することによって排除することができる。改ざん検出に関して、ＰＵＦの複製不可能特性（例えば、配線遅延、抵抗）は、ＰＵＦに対する修正が、登録後にチャレンジ（入力）からレスポンス（出力）へのＰＵＦのマッピングを不可逆的に変更するようなものであり得る（しかしながら、登録前の悪意のある修正に対するものではない。例えば、Ｂｅｃｋｅｒら、「Ｓｔｅａｌｔｈｙ  Ｄｏｐａｎｔ−Ｌｅｖｅｌ  Ｈａｒｄｗａｒｅ  Ｔｒｏｊａｎｓ」、Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ−ＣＨＥＳ  ２０１３、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第８０８６巻、第１９７〜２１４頁、Ｓｐｒｉｎｇｅｒ、２０１３）。これらのＰＵＦ特性は、ハードウェアに固有の、改ざんから保護された値を作り出すために使用され得、その値から、ハードウェアの信頼の基点を確立することができる。
【０００４】
Ｒuｈｍａｉｒ（uはウムラウト付き、以下同じ）ら（「Ｍｏｄｅｌｉｎｇ  Ａｔｔａｃｋｓ  ｏｎ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １７ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ、ＣＣＳ’１０、第２３７〜２４９頁、ＡＣＭ、２０１０）は、ＰＵＦデバイスの３つの別個のクラスを定義する。
【０００５】
●弱いＰＵＦは、典型的には、秘密鍵を導出するためにのみ使用される。チャレンジスペースは、限定され得、レスポンススペースは、決して明らかにされないことが想定される。典型的な構築は、ＳＲＡＭ（Ｈｏｌｃｏｍｂら、「Ｉｎｉｔｉａｌ  ＳＲＡＭ  Ｓｔａｔｅ  ａｓ  ａ  Ｆｉｎｇｅｒｐｒｉｎｔ  ａｎｄ  Ｓｏｕｒｃｅ  ｏｆ  Ｔｒｕｅ  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒｓ  ｆｏｒ  ＲＦＩＤ  Ｔａｇｓ」、Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ＲＦＩＤ  Ｓｅｃｕｒｉｔｙ、２００７）、バタフライ（Ｋｕｍａｒら、「Ｅｘｔｅｎｄｅｄ  ａｂｓｔｒａｃｔ：Ｔｈｅ  Ｂｕｔｔｅｒｆｌｙ  ＰＵＦ  Ｐｒｏｔｅｃｔｉｎｇ  ＩＰ  ｏｎ  Ｅｖｅｒｙ  ＦＰＧＡ」、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｈａｒｄｗａｒｅ−Ｏｒｉｅｎｔｅｄ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｔｒｕｓｔ、第６７〜７０頁、２００８）、アービタ（Ｌｅｅら、「Ａ  ｔｅｃｈｎｉｑｕｅ  ｔｏ  ｂｕｉｌｄ  ａ  ｓｅｃｒｅｔ  ｋｅｙ  ｉｎ  ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔｓ  ｆｏｒ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｐｐｌｉｃａｔｉｏｎｓ」、ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ＶＬＳＩ  Ｃｉｒｃｕｉｔｓ：Ｄｉｇｅｓｔ  ｏｆ  Ｔｅｃｈｎｉｃａｌ  Ｐａｐｅｒｓ、第１７６〜１７９頁、２００４）、リングオシレータ（Ｓｕｈら、「Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｆｏｒ  Ｄｅｖｉｃｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｓｅｃｒｅｔ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ４４ｔｈ  ａｎｎｕａｌ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、ＤＡＣ’０７、第９〜１４頁、ＡＣＭ、２００７）、およびコーティング（Ｔｕｙｌｓら、「Ｒｅａｄ−  Ｐｒｏｏｆ  Ｈａｒｄｗａｒｅ  ｆｒｏｍ  Ｐｒｏｔｅｃｔｉｖｅ  Ｃｏａｔｉｎｇｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ８ｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ、ＣＨＥＳ’０６、第３６９〜３８３頁、Ｓｐｒｉｎｇｅｒ、２００６）ＰＵＦを含む。
【０００６】
●強いＰＵＦは、（ｉ）物理的に複製することが不可能であり、（ｉｉ）（典型的には、約数週間かかる）合理的な時間内に完全な組のチャレンジレスポンス対を収集することが不可能であり、および（ｉｉｉ）ランダムチャレンジに対するレスポンスを予測することが困難であることが想定される。例えば、Ｒuｈｍａｉｒ（「Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｈｉｇｈ−Ｃａｐａｃｉｔｙ  Ｃｒｏｓｓｂａｒ  Ｍｅｍｏｒｉｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｎａｎｏｔｅｃｈｎｏｌ．、第１０巻、Ｎｏ．３：４８９−４９８、２０１１）によって説明された超高情報含量（ＳＨＩＣ）ＰＵＦが、強いＰＵＦとして考えられ得る。
【０００７】
●制御されたＰＵＦは、強いＰＵＦのための基準の全てを満たし、かつより高度な機能を計算してプロトコルを暗号で増強することが可能な補助制御ユニットを追加的に実装する。
【０００８】
ＰＵＦ出力には、同じ入力を評価するにもかかわらず、わずかに変動するという点で雑音がある。これは、一般に、生体測定における雑音を除去するように開発されたファジー抽出方法で対処される。（Ｊｕｅｌｓら、「Ａ  Ｆｕｚｚｙ  Ｃｏｍｍｉｔｍｅｎｔ  Ｓｃｈｅｍｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ６ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、ＣＣＳ’９９、第２８〜３６頁、ＡＣＭ、１９９９を参照。）ファジー抽出は、出力が固定入力に対して一定であるように、例えば補助制御ユニット内などのＰＵＦを有するデバイス内で部分的に利用されてもよい。ファジー抽出（または逆ファジー抽出）は、例えば、Ｊｕｅｌｓらによって説明されるような「セキュアスケッチ（ｓｅｃｕｒｅ  ｓｋｅｔｃｈ）」を利用して、再構築されるべきセンシティブ値
【数１】
2018507658.tif 000003
をリカバリするためのヘルパーストリンググ（ｈｅｌｐｅｒ  ｓｔｒｉｎｇ）ヘルパーｉを記憶してもよい。入力ストリングＯのためのセキュアスケッチＳＳは、例えば、
【数２】
2018507658.tif 000004
として定義され得、ここで、ＥＣＣは、ｔ誤りを訂正することができる長さｎの二元（ｎ，ｋ，２ｔ＋１）誤り訂正符号であり、
【数３】
2018507658.tif 000005
は、ｋビット値である。元の値Ｖが、次いで、誤り訂正符ＥＣＣおよびＯ’のための復号スキームＤを使用して、ヘルパーストリングヘルパーｉおよびＯの最大ハミング距離ｔ内の入力Ｏ’を仮定して、
【数４】
2018507658.tif 000006
として、再生され得る。
【０００９】
物理的複製不可能関数Ｐｄ：デバイスｄに束縛された
【数５】
2018507658.tif 000007
は、好ましくは、以下の特性を呈する。
【００１０】
１．複製不可能性：
【数６】
2018507658.tif 000008
、それらの出力分散が統計的にｔ近似（ｔ−ｃｌｏｓｅ）であるように、クローンＰＵＦ  Ｐ’を用いてＰＵＦ  Ｐを複製する確率は、かなり十分に小さな
【数７】
2018507658.tif 000009
よりも少ない。
【００１１】
２．予測不可能性：敵が、無視できるほどの確率を超えて（少なくとも、デバイスへの物理的なアクセスを用いずに）、チャレンジｃについてのデバイスのＰＵＦレスポンスｒを予測することができないこと、およびヘルパーデータが、ＰＵＦレスポンスについて敵に何も明らかにしないことが望ましい。全てのエンティティは、確率論的多項式時間（ＰＰＴ）に束縛され、すなわち、（関連したパラメータにおけるビットの数のことを言う）広域セキュリティパラメータλに関して、多項式的に多くの演算を必要とする計算のみを効率的に行うことができることを想定すると、チャレンジｃに対するＰＵＦ  Ｐの訂正レスポンスｒを推測する敵
【数８】
2018507658.tif 000010
の確率を表す、
【数９】
2018507658.tif 000011
は、好ましくは、Κ２において無視できる。これは、例えば、敵
【数１０】
2018507658.tif 000012
およびＰＵＦデバイスＰ間のゲーム、すなわち、長さΚ１のチャレンジスペース
【数１１】
2018507658.tif 000013
から長さΚ２のレスポンススペース
【数１２】
2018507658.tif 000014
までの
【数１３】
2018507658.tif 000015
マッピング入力ストリングを通して査定され得、ここで、λは、プロトコルのためのセキュリティパラメータであり、１λとして単項で仮定する。
【００１２】
【表１】
2018507658.tif 000016
【００１３】
ゲームは、以下のように進む。
【００１４】
１．敵
【数１４】
2018507658.tif 000017
は、（セキュリティパラメータλに関して）多項式的に多くのチャレンジ
【数１５】
2018507658.tif 000018
をＰＵＦデバイスＰに発行し、ここで、チャレンジセット
【数１６】
2018507658.tif 000019
は、チャレンジスペース全体
【数１７】
2018507658.tif 000020
の適切なサブセットである。
【００１５】
２．ＰＵＦデバイスＰは、レスポンス
【数１８】
2018507658.tif 000021
を
【数１９】
2018507658.tif 000022
に戻す。
【００１６】
３．敵
【数２０】
2018507658.tif 000023
は、結局、チャレンジクエリ
【数２１】
2018507658.tif 000024
の元のセットになかったチャレンジｃを出力する。敵は、コミットされたチャレンジｃについてＰＵＦデバイスＰにクエリすることを許可されない。
【００１７】
４．敵
【数２２】
2018507658.tif 000025
は、多項式的に多くのチャレンジ
【数２３】
2018507658.tif 000026
の新たなセットをＰＵＦデバイスＰにもう１度発行してもよい。敵は、コミットされたチャレンジｃについてＰＵＦデバイスＰにクエリすることを許可されない。
【００１８】
５．ＰＵＦデバイスＰは、レスポンス
【数２４】
2018507658.tif 000027
を
【数２５】
2018507658.tif 000028
に戻す。
【００１９】
６．敵
【数２６】
2018507658.tif 000029
は、結局、コミットされたチャレンジｃに対するＰのレスポンスについての推測ｒ’を出力する。
【００２０】
敵は、推測ｒ’が、
【数２７】
2018507658.tif 000030
のコミットされたチャレンジｃに対するＰの実際のレスポンス
【数２８】
2018507658.tif 000031
に等しいときにのみ、ゲームに勝つ。（留意されるように、ＰＵＦの出力は、雑音のあるものであり、かつ任意の固定入力についてわずかに変動し、そのため、同等性は、典型的には、ファジー抽出器の出力に関して取られる（例えば、Ｄｏｄｉｓら、「Ｆｕｚｚｙ  Ｅｘｔｒａｃｔｏｒｓ：Ｈｏｗ  ｔｏ  Ｇｅｎｅｒａｔｅ  Ｓｔｒｏｎｇ  Ｋｅｙｓ  ｆｒｏｍ  Ｂｉｏｍｅｔｒｉｃｓ  ａｎｄ  Ｏｔｈｅｒ  Ｎｏｉｓｙ  Ｄａｔａ」、ＳＩＡＭ  Ｊ．  Ｃｏｍｐｕｔ．、第３８巻、Ｎｏ．１：９７〜１３９、２００８））。
【００２１】
３．ロバスト性：
【数２９】
2018507658.tif 000032
、すなわち、同じ入力ｘについてｔ離れたレスポンスを生じる固定ＰＵＦＰの確率は、いくらか十分に小さい
【数３０】
2018507658.tif 000033
よりも少ない。
【００２２】
４．不可区別性：ＰＵＦデバイスの出力（典型的には、ファジー抽出器出力）は、好ましくは、ＰＰＴ敵
【数３１】
2018507658.tif 000034
のアドバンテージ
【数３２】
2018507658.tif 000035
が、最大でも無視できるほどに１／２を超えるように、同じ長さｌのランダムストリングから計算的に区別不可能である。ＰＵＦの不可区別性は、例えば、敵
【数３３】
2018507658.tif 000036
が、ＰＵＦ  Ｐのためのファジー抽出器の出力ｒおよび同じ長さｌのランダムに選ばれたストリング
【数３４】
2018507658.tif 000037
を見分けることを尋ねられるゲームを通して、査定され得る。
【００２３】
【表２】
2018507658.tif 000038
【００２４】
このゲームは、以下のように進む。
【００２５】
１．敵
【数３５】
2018507658.tif 000039
は、任意のチャレンジ
【数３６】
2018507658.tif 000040
についての登録段階を実行する。
【００２６】
２．ＰＵＦデバイスは、対応するヘルパーストリングＨｉを戻し、それは、ＰＵＦ  Ｐ（ｃ）の出力で誤り訂正されたセンシティブ値ＥＣＣ（Ｒｉ）を判読不能にする。チャレンジ−ヘルパー対（ｃｉ、Ｈｉ）のこのセットを
【数３７】
2018507658.tif 000041
として表す。
【００２７】
３．敵
【数３８】
2018507658.tif 000042
は、次に、任意の
【数３９】
2018507658.tif 000043
についてのＰＵＦレスポンスｒｉ＝Ｐ（ｃｉ）を要求する。このステップにおいて要求されるチャレンジのセットを
【数４０】
2018507658.tif 000044
で表す。
【００２８】
４．全ての要求
【数４１】
2018507658.tif 000045
について、ＰＵＦデバイスは、セット
【数４２】
2018507658.tif 000046
を戻す。
【００２９】
５．敵
【数４３】
2018507658.tif 000047
は、
【数４４】
2018507658.tif 000048
が、ｃのためにＲｉではなくて、Ｈｉを有するように、チャレンジ
【数４５】
2018507658.tif 000049
を選択する。ＰＵＦデバイスは、ランダムに一様にビット
【数４６】
2018507658.tif 000050
を選ぶ。
【００３０】
６．ｂ＝０である場合、
【数４７】
2018507658.tif 000051
は、
【数４８】
2018507658.tif 000052
を与えられる。そうではなくて、ｂ＝１である場合には、
【数４９】
2018507658.tif 000053
は、ランダムストリング
【数５０】
2018507658.tif 000054
を与えられる。
【００３１】
7．敵
【数５１】
2018507658.tif 000055
でない限り、
【数５２】
2018507658.tif 000056
についてＰＵＦデバイスにクエリすることを許可されない。
【００３２】
８．全ての要求
【数５３】
2018507658.tif 000057
について、ＰＵＦデバイスは、セット
【数５４】
2018507658.tif 000058
を戻す。
【００３３】
９．敵は、推測ビットｂ’を出力し、ｂ’＝ｂであるときに成功する。
【００３４】
ＰＵＦの関連した査定は、Ｈｏｒｉら、「Ｑｕａｎｔｉｔａｔｉｖｅ  ａｎｄ  Ｓｔａｔｉｓｔｉｃａｌ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ａｒｂｉｔｅｒ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｏｎ  ＦＰＧＡｓ」、２０１０  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  ＦＰＧＡｓ  （ＲｅＣｏｎＦｉｇ）、第２９８〜３０３頁、２０１０、Ｍａｉｔｉ、Ａ  Ｓｙｓｔｅｍａｔｉｃ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｄｅｓｉｇｎ  ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎ、論文、Ｖｉｒｇｉｎｉａ  Ｔｅｃｈ、２０１２、および他のものによって提供される。
【００３５】
物理的複製不可能関数についての文献は、ＰＵＦハードウェア設計の特性を評価する（例えば、Ｇａｓｓｅｎｄら、「Ｓｉｌｉｃｏｎ  Ｐｈｙｓｉｃａｌ  Ｒａｎｄｏｍ  Ｆｕｎｃｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  ＡＣＭ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｓｅｃｕｒｉｔｙ、ＣＣＳ’０２、第１４８〜１６０頁、ＡＣＭ、２００２、Ｋａｔｚｅｎｂｅｉｓｓｅｒら、「ＰＵＦ：Ｍｙｔｈ、Ｆａｃｔ  ｏｒ  Ｂｕｓｔｅｄ？Ａ  Ｓｅｃｕｒｉｔｙ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｐｈｙｓｉｃａｌｌｙ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  （ＰＵＦｓ）  Ｃａｓｔ  ｉｎ  Ｓｉｌｉｃｏｎ」、Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ  −  ＣＨＥＳ’１２、第２８３〜３０１頁、Ｓｐｒｉｎｇｅｒ、２０１２、Ｒａｖｉｋａｎｔｈ、Ｐｈｙｓｉｃａｌ  ｏｎｅ−ｗａｙ  ｆｕｎｃｔｉｏｎｓ、Ｐｈ．Ｄ．論文、２００１、Ｒuｈｍａｉｒら、「Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｈｉｇｈ−Ｃａｐａｃｉｔｙ  Ｃｒｏｓｓｂａｒ  Ｍｅｍｏｒｉｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ  Ｔｒａｎｓ．Ｎａｎｏｔｅｃｈｎｏｌ．、第１０巻、Ｎｏ．３：４８９〜４９８、２０１１、Ｓｕｈら、「Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｆｏｒ  Ｄｅｖｉｃｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｓｅｃｒｅｔ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ４４ｔｈ  ａｎｎｕａｌ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ、ＤＡＣ’０７、第９〜１４頁、ＡＣＭ、２００７、Ｙｕら、「Ｒｅｃｏｍｂｉｎａｔｉｏｎ  ｏｆ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ」、ＧＯＭＡＣＴｅｃｈ、２０１０）は、ＰＵＦ特性の形式理論モデルを提供し、それらの定義に関するプロトコルを設計する（Ａｒｍｋｎｅｃｈｔら、「Ａ  Ｆｏｒｍａｌｉｚａｔｉｏｎ  ｏｆ  ｔｈｅ  Ｓｅｃｕｒｉｔｙ  Ｆｅａｔｕｒｅｓ  ｏｆ  Ｐｈｙｓｉｃａｌ  Ｆｕｎｃｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０１１  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ、ＳＰ’１１、第３９７〜４１２頁、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ、２０１１、Ｂｒｚｕｓｋａら、「Ｐｈｙｓｉｃａｌｌｙ  Ｕｎ−ｃｌｏｎｅａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｉｎ  ｔｈｅ  Ｕｎｉｖｅｒｓａｌ  Ｃｏｍｐｏｓｉｔｉｏｎ  Ｆｒａｍｅｗｏｒｋ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＣＲＹＰＴＯ  ２０１１  −  ３１ｓｔ  Ａｎｎｕａl  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第６８４１巻、第５１頁、Ｓｐｒｉｎｇｅｒ、２０１１、Ｆｒｉｋｋｅｎら、「Ｒｏｂｕｓｔ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｕｓｉｎｇ  Ｐｈｙｓｉｃａｌｌｙ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ」、Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第５７３５巻、第２６２〜２７７頁、Ｓｐｒｉｎｇｅｒ、２００９、Ｈａｎｄｓｃｈｕｈら、「Ｈａｒｄｗａｒｅ  Ｉｎｔｒｉｎｓｉｃ  Ｓｅｃｕｒｉｔｙ  ｆｒｏｍ  Ｐｈｙｓｉｃａｌｌｙ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ」、Ｔｏｗａｒｄｓ  Ｈａｒｄｗａｒｅ−Ｉｎｔｒｉｎｓｉｃ  Ｓｅｃｕｒｉｔｙ、Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ、第３９〜５３頁、Ｓｐｒｉｎｇｅｒ、２０１０、Ｋｉｒｋｐａｔｒｉｃｋら、「ＰＵＦ  ＲＯＫｓ：Ａ  Ｈａｒｄｗａｒｅ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｒｅａｄ−Ｏｎｃｅ  Ｋｅｙｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ６ｔｈ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ，  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、ＡＳＩＡＣＣＳ’１１、第１５５〜１６４頁、ＡＣＭ、２０１１、Ｐａｒａｌら、「Ｒｅｌｉａｂｌｅ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  ＰＵＦ−ｂａｓｅｄ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ  ｕｓｉｎｇ  Ｐａｔｔｅｒｎ  Ｍａｔｃｈｉｎｇ」、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｈａｒｄｗａｒｅ−  Ｏｒｉｅｎｔｅｄ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｔｒｕｓｔ  （ＨＯＳＴ）、第１２８〜１３３頁、２０１１、Ｒuｈｍａｉｒら、「ＰＵＦｓ  ｉｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ：Ａｔｔａｃｋ  Ｍｏｄｅｌｓ  ａｎｄ  Ｓｅｃｕｒｉｔｙ  Ｅｖａｌｕａｔｉｏｎｓ」、２０１３  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ、第０巻：２８６〜３００、２０１３、ｖａｎ  Ｄｉｊｋら、「Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｐｒｏｔｏｃｏｌｓ：Ｓｅｃｕｒｉｔｙ  Ｐｒｏｏｆｓ  ａｎｄ  Ｉｍｐｏｓｓｉｂｉｌｉｔｙ  Ｒｅｓｕｌｔｓ」、Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ、Ｒｅｐｏｒｔ  ２０１２／２２８、２０１２、Ｗｕら、「Ｏｎ  Ｆｏｕｎｄａｔｉｏｎ  ａｎｄ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ」、２０１０、Ｙｕら、「Ｌｉｇｈｔｗｅｉｇｈｔ  ａｎｄ  Ｓｅｃｕｒｅ  ＰＵＦ  Ｋｅｙ  Ｓｔｏｒａｇｅ  ｕｓｉｎｇ  Ｌｉｍｉｔｓ  ｏｆ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １３ｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ、ＣＨＥＳ’１１、第３５８〜３７３頁、Ｓｐｒｉｎｇｅｒ、２０１１を参照）。
【００３６】
先行技術のＰＵＦに基づくプロトコルは、以下の２つの広いカテゴリに分類される。（１）プロトコル１に以下に説明されるものと同様の単純なチャレンジ−レスポンスプロビジョニングプロセス、または（２）生のＰＵＦ出力が決してデバイスから出ないような、デバイスのＰＵＦレスポンスの暗号化増強。これらのアプローチは、外部エンティティが、既存の公開鍵暗号標準においてサポートされないかまたは不必要な補助情報（例えば、チャレンジおよびそれらの関連付けられたヘルパーデータ）を取り扱うこと、および／またはハードウェアデバイスが、最初の登録プロセスの間に適用されるチャレンジが本物であることを証明することを伴うことを必要とし得、ならびに／あるいはハードウェアデバイスが、所与のチャレンジに対する本質的に同じレスポンスを常にリカバリすることを前提とする。
【００３７】
所与のチャレンジ−レスポンス対は、対が収集されたときのデバイスのハードウェア状態を反映するが、デバイスは、老化し、そのハードウェア状態は、時が経つにつれてドリフトする。ＰＵＦハードウェアが老化するので、レスポンスに存在する誤りの数は、増大し得る。Ｍａｉｔｉら（「Ｔｈｅ  Ｉｍｐａｃｔ  ｏｆ  Ａｇｉｎｇ  ｏｎ  ａｎ  ＦＰＧＡ−Ｂａｓｅｄ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  （ＦＰＬ）、第１５１〜１５６頁、２０１１）は、通常動作条件を越えてデバイスに意図的にストレスかけることによって、ＰＵＦハードウェアへの模擬老化の影響を研究する。温度および電圧の両方を変動させることによって、著者は、時が経つにつれて、偽陰性を導く内部ＰＵＦ変動におけるドリフトを示すことができた。Ｍａｉｔｉらは、誤りドリフトが、５０％の最大エントロピー率の傾向がある内部ＰＵＦ誤り率分散に厳密に影響を及ぼしたことに言及する。十分な時間が経過した後、ハードウェアデバイスは、登録されたチャレンのために適切なレスポンスをリカバリすることがもはやできなくなり得る。
【００３８】
例えば、特定のチャレンジｃｉが、登録の間にデバイスに発行され、デバイスが、デバイスのハードウェア識別情報をチャレンジｃと結び付ける公開トークン｛コミットメントｉ，ヘルパーｉ｝を戻すことを想定する。本物であることを証明されるために、デバイスは、対｛ｃｉ，ヘルパーｉ｝を使用して、そのプライベート識別情報
【数５５】
2018507658.tif 000059
をリカバリする。図１０に示されるように、時が経つにつれて、ＰＵＦハードウェアは、ハードウェア老化が、デバイスの誤り訂正限界を超えて誤りを増大した時間に（例えば、図１０の例では、簡潔さのために、時が経つにつれて、直線的に発生するドリフトを想定する、時間τ＝５において）達し得、デバイスは、その私有鍵を確実に再生成することがもはやできない。
【００３９】
Ｋｉｒｋｐａｔｒｉｃｋら（「Ｓｏｆｔｗａｒｅ  Ｔｅｃｈｎｉｑｕｅｓ  ｔｏ  Ｃｏｍｂａｔ  Ｄｒｉｆｔ  ｉｎ  ＰＵＦ−ｂａｓｅｄ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｓｙｓｔｅｍｓ」、Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｅ  Ｃｏｍｐｏｎｅｎｔ  ａｎｄ  Ｓｙｓｔｅｍ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ、２０１０）は、ハードウェア老化ドリフトを検出するための、および外部サーバ上に記憶されたデバイスのチャレンジ−コミットメント対を更新することによって応答するための方法を説明する。このアプローチは、サーバが、チャレンジ−コミットメント対の形態で補助情報を維持するが、定期的なプロトコルが、サーバおよびデバイスの間で実行されることを必要とする。
【００４０】
ＰＵＦに基づくシステムに対抗する別のチャレンジは、サイドチャネル攻撃であり、それは、補助環境変数の観測および解析を試み、センシティブＰＵＦ出力についての情報を演繹する。例えば、電磁気（ＥＭ）解析（例えば、Ｍｅｒｌｉら、「Ｓｅｍｉ−ｉｎｖａｓｉｖｅ  ＥＭ  Ａｔｔａｃｋ  ｏｎ  ＦＰＧＡ  ＲＯ  ＰＵＦｓ  ａｎｄ  Ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ  Ｓｅｃｕｒｉｔｙ、ＷＥＳＳ’１１、第２：１〜２：９頁、ＡＣＭ、２０１１、Ｍｅｒｌｉら、「Ｓｉｄｅ−Ｃｈａｎｎｅｌ  Ａｎａｌｙｓｉｓ  ｏｆ  ＰＵＦｓ  ａｎｄ  Ｆｕｚｚｙ  Ｅｘｔｒａｃｔｏｒｓ」、Ｔｒｕｓｔ  ａｎｄ  Ｔｒｕｓｔｗｏｒｔｈｙ  Ｃｏｍｐｕｔｉｎｇ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第６７４０巻、第３３〜４７頁、Ｓｐｒｉｎｇｅｒ、２０１１、Ｓｃｈｕｓｔｅｒ、Ｓｉｄｅ−Ｃｈａｎｎｅｌ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  （ＰＵＦｓ）、修士論文、Ｔｅｃｈｎｉｓｃｈｅ  Ｕｎｉｖｅｒｓｉｔａｔ  Ｍｕｎｃｈｅｎ、２０１０）は、デバイス動作の間に変化するＥＭ場を観測することによって、ＰＵＦ出力ビットを抽出する。別のサイドチャネル攻撃方法論は、（単純または差分）電力解析であり（例えば、Ｋａｒａｋｏｙｕｎｌｕら、「Ｄｉｆｆｅｒｅｎｔｉａｌ  ｔｅｍｐｌａｔｅ  ａｔｔａｃｋｓ  ｏｎ  ＰＵＦ  ｅｎａｂｌｅｄ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｄｅｖｉｃｅｓ」、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｆｏｒｅｎｓｉｃｓ  ａｎｄ  Ｓｅｃｕｒｉｔｙ  （ＷＩＦＳ）、第１〜６頁、２０１０、Ｋｏｃｈｅｒら、「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ」、Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｒｅｓｅａｒｃｈ，  Ｉｎｃ．、２０１１、Ｋｏｃｈｅｒら、「Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ’９９、第３８８〜３９７頁、Ｓｐｒｉｎｇｅｒ、１９９９、Ｒuｈｍａｉｒら、「Ｐｏｗｅｒ  ａｎｄ  Ｔｉｍｉｎｇ  Ｓｉｄｅ  Ｃｈａｎｎｅｌｓ  ｆｏｒ  ＰＵＦｓ  ａｎｄ  ｔｈｅｉｒ  Ｅｆｆｉｃｉｅｎｔ  Ｅｘｐｌｏｉｔａｔｉｏｎ」、２０１３）、この場合、電力トレースが、デバイスから収集され、かつセンシティブ情報（例えば、ＰＵＦ出力ビット）を抽出するように解析される。固定チャレンジに対する本質的に同じレスポンスをリカバリするデバイスの多くの観測を通じて、敵は、センシティブＰＵＦ出力を発見することができる。
【００４１】
サイドチャネル攻撃の有効性は、一部のシステムにおいて、ランダム性を導入することによって低減され得ることが知られる（Ｃｏｒｏｎ、「Ｒｅｓｉｓｔａｎｃｅ  Ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  Ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第１７１７巻、第２９２〜３０２頁、Ｓｐｒｉｎｇｅｒ、１９９９）が、このようにして、センシティブ値を区別することは、いくらかの脆弱性を残し得る。なぜなら、基底値は、静的なままであり、ならびに／あるいは追加的な複雑性および／または処理オーバーヘッドを導くからである。
【発明の概要】
【課題を解決するための手段】
【００４２】
本発明に係る認証システムでは、ＰＵＦのチャレンジ−レスポンス挙動が、私有鍵の共有を維持するために内在化および使用され得る。このアプローチは、ＰＵＦでイネーブルにされるハードウェアデバイスが、一度も私有鍵を生成、再構築、または記憶せずに、任意の閾値暗号演算（例えば、暗号解読、デジタル署名生成、ゼロ知識証明）を実行することができるように実装され得る。また、任意の外部エンティティが、あるデバイスのためにチャレンジを発行するおよびヘルパーデータを記憶する必要性を排除するように、および／または外部エンティティが、標準公開鍵プロトコルと区別することができないＰＵＦに基づくプロトコルをイネーブルにするように、実装されてもよい。一実施形態では、デバイスが、例えばＰＵＦなどの信頼の基点を装備してもよいし、およびデバイスによって生成、リカバリ、または処理される必要がある全てのセンシティブ値を定期的にリフレッシュするように構成されてもよい。これは、ＰＵＦの老化および／またはサイドチャネル攻撃を軽減するために利用されてもよい。閾値共有演算は、１つの共有が、常に記憶されたままであるように、スタッガード式にされてもよい。
【図面の簡単な説明】
【００４３】
【図１】図１は、単一ＰＵＦ回路および２つの閾値共有を有するデバイスの機能図である。
【図２】図２は、２重ＰＵＦ回路を有するデバイスの機能図である。
【図３】図３は、１点のみを仮定して、次数ｄ＝３の多項式Ｐ（ｘ）例を補間する試みを例解するグラフであり、それは、少なくともｄ＋１点が必要とされるので失敗する。
【図４】図４は、２点を仮定して、同じ多項式Ｐ（ｘ）を補間することに失敗した試みを例解する。
【図５】図５は、３点を仮定して、同じ多項式Ｐ（ｘ）を補間することに失敗した試みを例解する。
【図６】図６は、４点を仮定して、Ｐ（ｘ）の成功した補間を例解する。
【図７】図７は、発明のある実施形態における図２のものと同様のデバイスの登録の操作上のフローチャートである。
【図８】図８は、発明のある実施形態における図２のものと同様のデバイスにおける閾値暗号演算の操作上のフローチャートである。
【図９】図９は、スタッガード式閾値演算の操作上のフローチャートである。
【図１０】図１０は、固定チャレンジのためのＰＵＦ出力における経時的な誤りを例解するグラフである。
【図１１】図１１は、τ＝１について、更新されたチャレンジ−ヘルパー対を用いてＰＵＦ出力における経時的な誤りを例解するグラフである。
【図１２】図１２は、束縛されたＰＵＦ誤り率を確立する対のリフレッシュを伴う、ＰＵＦ出力における経時的な誤りを例解するグラフである。
【図１３】図１３は、一括ＰＵＦ処理センターを描写する図である。
【図１４】図１４は、複合要素からの共同識別情報を描写する図である。
【発明を実施するための形態】
【００４４】
本発明は、（関連付けられた専門用語および慣習を含む）楕円曲線暗号法を利用する実施形態の例を参照して説明されるが、本明細書における発明的概念および教示は、様々な他の暗号スキーム、例えば、離散対数または因数分解のような異なる問題を利用するものなど（米国特許第８，９１８，６４７号の教示に関係するものが、参照によって組み込まれる）に同等に適用され、発明は、発明と共にまたは発明に基づいて利用され得る本明細書に説明される様々な追加的な特徴によって限定されない。
【００４５】
閾値暗号法
閾値暗号法は、演算が、参加者の定足数の協力を用いてのみ可能であるように、１組の参加者の間で暗号演算を分散することを伴う。信頼されたディーラー
【数５６】
2018507658.tif 000060
は、１組の参加者
【数５７】
2018507658.tif 000061
のためにマスター非対称鍵対
【数５８】
2018507658.tif 000062
を生成する。私有鍵が、次いで、ｎ個の参加者間に分配され、各参加者は、
【数５９】
2018507658.tif 000063
の共有を受信する。これは、少なくともｔ個の参加者の定足数が、マスター私有鍵を使用して演算を行うために、それらのプライベート共有を組み合わせる必要があるように、
【数６０】
2018507658.tif 000064
の（ｔ，ｎ）共有を構成する。
【００４６】
他の秘密スキームが、本発明と共に使用され得る（例えば、Ｂｌａｋｌｅｙ、「Ｓａｆｅｇｕａｒｄｉｎｇ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｋｅｙｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １９７９  ＡＦＩＰＳ  Ｎａｔｉｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｃｏｎｆｅｒｅｎｃｅ、第３１３〜３１７頁、ＡＦＩＰＳ  Ｐｒｅｓｓ、１９７９）が、ある例が、Ｓｈａｍｉｒの多項式補間構築（「Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ」、Ｃｏｍｍｕｎ．ＡＣＭ、第２２巻、Ｎｏ．１１：６１２〜６１３、１９７９）を利用して説明され、それは、秘密を共有するために使用することができる。次数ｔ−１の多項式
【数６１】
2018507658.tif 000065
が定義され、ここで、係数ｃｉは、秘密のままである。すなわち、
【数６２】
2018507658.tif 000066
係数の知識がなくても、
【数６３】
2018507658.tif 000067
は、
【数６４】
2018507658.tif 000068
の少なくともｔ点が、ラグランジュの多項式補間アプローチを適用することによって知られるときに評価することができる。私有鍵
【数６５】
2018507658.tif 000069
は、自由係数ｃ０
【数６６】
2018507658.tif 000070
として設定され得、私有鍵の１組の共有が参加者に分散される（例えば、Ｅｒｔａｕｌ、「ＥＣＣ  Ｂａｓｅｄ  Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  Ｓｅｃｕｒｅ  Ｄａｔａ  Ｆｏｒｗａｒｄｉｎｇ  ａｎｄ  Ｓｅｃｕｒｅ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  ｉｎ  ＭＡＮＥＴ  （Ｉ）」、ＮＥＴＷＯＲＫＩＮＧ  ２００５、Ｎｅｔｗｏｒｋｉｎｇ  Ｔｅｃｈｎｏｌｏｇｉｅｓ，  Ｓｅｒｖｉｃｅｓ，  ａｎｄ  Ｐｒｏｔｏｃｏｌｓ；  Ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｎｅｔｗｏｒｋｓ；Ｍｏｂｉｌｅ  ａｎｄ  Ｗｉｒｅｌｅｓｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｙｓｔｅｍｓ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第３４６２巻、第１０２〜１１３頁、Ｓｐｒｉｎｇｅｒ、２００５を参照）。ｎ個の参加者
【数６７】
2018507658.tif 000071
間で私有鍵
【数６８】
2018507658.tif 000072
を分配するために、ディーラーは、
【数６９】
2018507658.tif 000073
であるように、ｐｉの＜公開，私有＞鍵対を＜ｒｉ・Ｇ  ｍｏｄ  ｑ，ｒｉ＞として計算する。ここで、
【数７０】
2018507658.tif 000074
は、楕円曲線Ｅのための次数ｑの基点であり、（Ｐ）ｘ（あるいは（Ｐ）ｙ）は、曲線Ｅ上の点Ｐのｘ（あるいはｙ）座標のことを言う（演算が行われる母数は、それが状況から明らかである場合に省略されてもよい）。公開鍵は、全ての参加者に利用可能にされるが、私有鍵は、各参加者に安全に（例えば、デバイスの公開鍵およびＥｌＧａｍａｌ暗号法を使用して）分散される。全ての参加者はまた、
【数７１】
2018507658.tif 000075
へのアクセスを与えられ、それは、彼らが、以下のことをチェックすることによって、彼らの秘密鍵および他の参加者の公開鍵を検証することを可能にする。
【数７２】
2018507658.tif 000076
参加者は、世界的に既知の公開鍵に関して、それらの共有の正当性を検証することができるので、これは、私有鍵
【数７３】
2018507658.tif 000077
の（ｔ，ｎ）検証可能な秘密共有（ＶＳＳ）（例えば、Ｆｅｌｄｍａｎ、「Ａ  Ｐｒａｃｔｉｃａｌ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  Ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２８ｔｈ  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、ＳＦＣＳ’８７、第４２７〜４３８頁、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ、１９８７、Ｐｅｄｅｒｓｅｎ、「Ｎｏｎ−Ｉｎｔｅｒａｃｔｉｖｅ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ−Ｔｈｅｏｒｅｔｉｃ  Ｓｅｃｕｒｅ  Ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ  ９１、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第５７６巻、第１２９〜１４０頁、Ｓｐｒｉｎｇｅｒ、１９９２）を構成する。
【００４７】
次に、任意のｔ個の共有
【数７４】
2018507658.tif 000078
へのアクセスを仮定すると、ここで、
【数７５】
2018507658.tif 000079
は、次数ｔ−１を有しかつｔ≦ｎであり、共有（ｉ，ｒｉ）は、以下のf（ｘ）を評価するためにラグランジュ多項式補間を通して組み合わせてもよい。 
【数７６】
2018507658.tif 000080
これは、ｔ個の参加者の任意の定足数
【数７７】
2018507658.tif 000081
が、それらの共有
【数７８】
2018507658.tif 000082
を組み合わせること、および多項式の自由係数
【数７９】
2018507658.tif 000083
をリカバリすることを可能にし、それは、マスター非対称私有鍵
【数８０】
2018507658.tif 000084
である。ラグランジュ形式が、補間多項式のために使用されるが、（例えば、単項式基準またはニュートン形式を使用する）他のアプローチを代用してもよい。同様に、例示的な構築は、
【数８１】
2018507658.tif 000085
を評価し、係数をリカバリするものではない。代わりに、後者は、ヴァンデルモンド行列表現を使用しておよび線形方程式系を解いて達成してもよい。
【００４８】
図３〜図６は、
【数８２】
2018507658.tif 000086
のラグランジュ多項式補間を例解する。補間多項式
【数８３】
2018507658.tif 000087
は、１組のｋ点
【数８４】
2018507658.tif 000088
から生成される。図３は、単一点のみから生成された補間多項式
【数８５】
2018507658.tif 000089
を例解する。図４は、２点から生成された補間多項式
【数８６】
2018507658.tif 000090
を例解する。図５は、３点から生成された補間多項式
【数８７】
2018507658.tif 000091
を例解する。図６は、４点から生成された補間多項式
【数８８】
2018507658.tif 000092
を例解する。多項式の次数が３のみである際、任意の４点が、元の多項式の完全な補間を結果としてもたらす。セットｋのサイズが多項式ｔ−１の次数を超える（すなわち、ｋ≧ｔである）とき、
【数８９】
2018507658.tif 000093
は、元の多項式
【数９０】
2018507658.tif 000094
を完全に補間する。このため、この例では、補間多項式は、４点から生成され、それは、多項式の次数（３）を超える。ｋ＜ｔ点の任意のセットを仮定すると、ｋ＜ｔ点のセットを満足する次数ｔ−１の無限数の多項式が存在するので、秘密Ｐ（０）について何の情報も明らかにされないことに留意する。
【００４９】
例示的な実施形態は、楕円曲線暗号法を使用してもよいが、様々な他の暗号フレームワーク（例えば、ＥｌＧａｍａｌ、ＲＳＡ、ＮＴＲＵ等）が利用され得ることが容易に明らかであろう。いくらかの閾値暗号演算が、このフレームワーク内で、種々の方法、例えば、閾値暗号法、暗号解読、および署名、知識の閾値ゼロ知識証明、閾値サインクリプション、ならびに分散型鍵生成などを使用して、実行され得る。他の楕円曲線機構、例えば、Ｍａｓｓｅｙ−Ｏｍｕｒａ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ、Ｍｅｎｅｚｅｓ−Ｖａｎｓｔｏｎｅ、Ｋｏｙａｍａ−Ｍａｕｒｅｒ−Ｏｋａｍｏｔｏ−Ｖａｎｓｔｏｎｅ、Ｅｒｔａｕｌ、Ｄｅｍｙｔｋｏなどが、同様に利用されてもよい。
【００５０】
デバイスの登録情報
【数９１】
2018507658.tif 000095
を所有しているエンティティは、それゆえ、対象デバイスのみが、例えば、以下のＥｌＧａｍａｌ暗号法などの方法を使用して、それをリカバリすることができるように、メッセージｍを暗号化することができる。
【００５１】
【表３】
2018507658.tif 000096
【００５２】
次いで、グループの全ての参加者
【数９２】
2018507658.tif 000097
が、グループ私有鍵ｒを使用して、メッセージ
【数９３】
2018507658.tif 000098
の暗号化
【数９４】
2018507658.tif 000099
の暗号解読を望み、ここで、
【数９５】
2018507658.tif 000100
である場合、（例えば、Ｅｒｔａｕｌによって）閾値ＥｌＧａｍａｌ暗号解読を以下のように使用することができる。
【００５３】
●各参加者
【数９６】
2018507658.tif 000101
は、それらの秘密鍵
【数９７】
2018507658.tif 000102
を使用して、以下のシャドウを計算する。
【数９８】
2018507658.tif 000103
【００５４】
●各参加者は、次いで、
【数９９】
2018507658.tif 000104
として定義されたそれらの部分的な暗号解読Ｓｉをブロードキャストする。
【００５５】
●各参加者は、以下の値をローカルに計算する。
【数１００】
2018507658.tif 000105
●最終的に、各参加者は、次に、
【数１０１】
2018507658.tif 000106
を計算することによって、メッセージｍをローカルにリカバリしてもよい。
【００５６】
同様に、グループ
【数１０２】
2018507658.tif 000107
は、閾値署名スキームを使用することができ、ここで、
【数１０３】
2018507658.tif 000108
であり（例えば、Ｃｈｅｎら、「Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｔｈｒｅｓｈｏｌｄ  ｇｒｏｕｐ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ」、ＩＥＥＥ  Ｒｅｇｉｏｎ  １０  Ｃｏｎｆｅｒｅｎｃｅ  ＴＥＮＣＯＮ、第Ｂ巻、第１３〜１６頁、Ｖｏｌ．２、２００４、Ｈｕａ−ｑｕｎら、「Ｖｅｒｉｆｉａｂｌｅ  （ｔ，  ｎ）  Ｔｈｒｅｓｈｏｌｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ」、Ｗｕｈａｎ  Ｕｎｉｖｅｒｓｉｔｙ  Ｊｏｕｒｎａｌ  ｏｆ  Ｎａｔｕｒａｌ  Ｓｃｉｅｎｃｅｓ、第１０巻、Ｎｏ．１：１６５〜１６８、２００５、Ｉｂｒａｈｉｍら、「Ａ  Ｒｏｂｕｓｔ  Ｔｈｒｅｓｈｏｌｄ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  ｐｒｏｖｉｄｉｎｇ  ａ  Ｎｅｗ  Ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ」、ＩＥＥＥ  ４６ｔｈ  Ｍｉｄｗｅｓｔ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ、第１巻、第２７６〜２８０頁、Ｖｏｌ．１、２００３、Ｋｉｍら、「Ｔｈｒｅｓｈｏｌｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ  ｆｏｒ  ＥｌＧａｍａｌ  Ｖａｒｉａｎｔｓ」、Ｃｏｍｐｕｔｅｒ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｉｎｔｅｒｆａｃｅｓ、第３３巻、Ｎｏ．４：４３２〜４３７、２０１１、Ｓｈａｏ、「Ｒｅｐａｉｒｉｎｇ  Ｅｆｆｉｃｉｅｎｔ  Ｔｈｒｅｓｈｏｌｄ  Ｇｒｏｕｐ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｎｅｔｗｏｒｋ  Ｓｅｃｕｒｉｔｙ、２００８）、以下のようにメッセージｍのための
【数１０４】
2018507658.tif 000109
の全てを表現する署名を生成する。
【００５７】
●各参加者
【数１０５】
2018507658.tif 000110
は、それらの秘密鍵
【数１０６】
2018507658.tif 000111
およびランダム整数
【数１０７】
2018507658.tif 000112
を使用して、メッセージｍのためのそれらの個々の署名（Ｒｉ，Ｓｉ）を計算する。
【００５８】
−最初に、Ｒｉが、
【数１０８】
2018507658.tif 000113
から計算され、全ての参加者
【数１０９】
2018507658.tif 000114
に公開される。
【００５９】
−次に、各参加者ｐｉが、以下のようにＲ、ｅ、およびＳｉを計算する。
【数１１０】
2018507658.tif 000115
【数１１１】
2018507658.tif 000116
は、暗号学的ハッシュ関数を表す。各参加者は、指定されたセクレタリ（便宜のために、信頼される必要のないもの）にＳｉをブロードキャストする。
【００６０】
●全ての（Ｒｉ，Ｓｉ）対を受信したセクレタリは、以下の計算によって署名を検証する。
【数１１２】
2018507658.tif 000117
適切に構築される場合、この式は、以下のように保たれる。
【数１１３】
2018507658.tif 000118
●これらが保たれる場合、セクレタリが、以下を計算する。
【数１１４】
2018507658.tif 000119
それは、ｍについてグループ署名（（Ｒ）ｙｍｏｄ  ｑ，Ｓ）を計算する。
●（Ｒ，Ｓ）の受領後、受信側ｐＲは、参加者
【数１１５】
2018507658.tif 000120
のグループ全体の公開鍵
【数１１６】
2018507658.tif 000121
に対するその有効性、すなわち、
【数１１７】
2018507658.tif 000122
をチェックし、それは、以下の理由のために、有効な署名を保つ。
【数１１８】
2018507658.tif 000123
【００６１】
グループの参加者
【数１１９】
2018507658.tif 000124
はまた、協力して、以下のように、知識の閾値ゼロ知識証明（例えば、Ｓａｒｄａｒら、「Ｚｅｒｏ  Ｋｎｏｗｌｅｄｇｅ  Ｐｒｏｏｆ  ｉｎ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ  Ｕｓｉｎｇ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、Ｇｌｏｂａｌ  Ｔｒｅｎｄｓ  ｉｎ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍｓ、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅの第２６９巻、第２２０〜２２６頁、Ｓｐｒｉｎｇｅｒ、２０１２）を使用して、共有された私有鍵
【数１２０】
2018507658.tif 000125
の所有を実証することができ、ここで、
【数１２１】
2018507658.tif 000126
、およびｔ≦ｎである。
【００６２】
●グループ公開鍵は
【数１２２】
2018507658.tif 000127
であり、ここで、ｒは、共有された秘密であり、Ｇは、グループ生成元である。検証器
【数１２３】
2018507658.tif 000128
は、一過性ノンスＮを選び、これを
【数１２４】
2018507658.tif 000129
の全ての参加者に分散する。
【００６３】
●各参加者
【数１２５】
2018507658.tif 000130
は、それらの秘密共有
【数１２６】
2018507658.tif 000131
およびランダムノンス整数ｙｉを使用して、共有された秘密ｒのそれらの個々の証明（Ｂｉ,Ｍｉ）を計算する。
−最初に、Ｂｉが計算され、全ての参加者
【数１２７】
2018507658.tif 000132
に公開される。
【数１２８】
2018507658.tif 000133
−各参加者は、ローカルに以下を計算する。
【数１２９】
2018507658.tif 000134
−次に、各参加者ｐｉは、以下のように、e、Ｍｉを計算する。
【数１３０】
2018507658.tif 000135
●
【数１３１】
2018507658.tif 000136
の受領後、検証器vは以下を計算する。
【数１３２】
2018507658.tif 000137
●次に、検証器は、公開鍵
【数１３３】
2018507658.tif 000138
に対する証明の有効性をチェックする。
【数１３４】
2018507658.tif 000139
【数１３５】
2018507658.tif 000140
である場合、検証器
【数１３６】
2018507658.tif 000141
は、閾値ゼロ知識証明を有効として受諾し、そうでない場合は証明を拒否する。
【００６４】
メッセージをサインクリプティングするプロセス（例えば、Ｃｈａｎｇｇｅｎら、「Ｔｈｒｅｓｈｏｌｄ  Ｓｉｇｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍ  ａｎｄ  Ｖｅｒｉｆｉａｂｌｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｗｉｒｅｌｅｓｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、Ｎｅｔｗｏｒｋｉｎｇ  ａｎｄ  Ｍｏｂｉｌｅ  Ｃｏｍｐｕｔｉｎｇ、第２巻、第１１８２〜１１８５頁、２００５、Ｚｈｅｎｇ、「Ｄｉｇｉｔａｌ  Ｓｉｇｎｃｒｙｐｔｉｏｎ  ｏｒ  Ｈｏｗ  ｔｏ  Ａｃｈｉｅｖｅ  Ｃｏｓｔ（Ｓｉｇｎａｔｕｒｅ  ＆  Ｅｎｃｒｙｐｔｉｏｎ）<<Ｃｏｓｔ  （Ｓｉｇｎａｔｕｒｅ）  ＋  Ｃｏｓｔ  （Ｅｎｃｒｙｐｔｉｏｎ）」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ’９７、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第１２９４巻、第１６５〜１７９頁、Ｓｐｒｉｎｇｅｒ、１９９７、Ｚｈｅｎｇら、「Ｈｏｗ  ｔｏ  Ｃｏｎｓｔｒｕｃｔ  Ｅｆｆｉｃｉｅｎｔ  Ｓｉｇｎｃｒｙｐｔｉｏｎ  Ｓｃｈｅｍｅｓ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ」、Ｉｎｆ．Ｐｒｏｃｅｓｓ．Ｌｅｔｔ．、第６８巻、Ｎｏ．５：２２７〜２３３、１９９８）は、それぞれ別個に計算することよりも少ない費用で、メッセージの署名および暗号化の両方を行うことを容易にする。メッセージ
【数１３７】
2018507658.tif 000142
および公開鍵
【数１３８】
2018507658.tif 000143
を用いる受信側ｐＲを仮定すると、サインクリプションは、以下のように生成することができる。
【００６５】
●各
【数１３９】
2018507658.tif 000144
は、ランダム
【数１４０】
2018507658.tif 000145
を選択し、
【数１４１】
2018507658.tif 000146
を計算し、これをセクレタリ（便宜のために、信頼される必要がないもの）および受信側ｐＲの両方に公式にブロードキャストする。各
【数１４２】
2018507658.tif 000147
はまた、
【数１４３】
2018507658.tif 000148
を計算し、それは、非公式に（例えば、ＥｌＧａｍａｌ暗号法使用して）ｐＲに送信される。
【００６６】
●セクレタリは、
【数１４４】
2018507658.tif 000149
を計算して、（ｒｉ、
【数１４５】
2018507658.tif 000150
の参加者ｐｉの共有と混同されない）ｒを各署名者
【数１４６】
2018507658.tif 000151
にブロードキャストする。
【００６７】
●各署名者
【数１４７】
2018507658.tif 000152
は、
【数１４８】
2018507658.tif 000153
を計算し、ここで、
【数１４９】
2018507658.tif 000154
は、
【数１５０】
2018507658.tif 000155
のｐｉの共有である。各署名者は、それらの部分的なサインクリプションｓｉをセクレタリに送信する。
【００６８】
●部分的なサインクリプションｓｉの受領後、セクレタリは、
【数１５１】
2018507658.tif 000156
をチェックすることによって、部分的なサインクリプションの有効性を検証するために、
【数１５２】
2018507658.tif 000157
を計算する。
【００６９】
●一旦、全ての部分的なサインクリプションｓｉを受信し、それらの有効性をチェックすると、セクレタリは、それらを組み合わせて、
【数１５３】
2018507658.tif 000158
を計算し、（ｒ，ｓ）は、受信側ｐＲに送信された最終的なサインクリプションである。
【００７０】
●次に
【数１５４】
2018507658.tif 000159
を受信した受信側参加者ｐＲは、以下を計算する。
【数１５５】
2018507658.tif 000160
●受領者ｐＲは、次いで、以下のことを検証する。
【数１５６】
2018507658.tif 000161
これらが保たれる場合、ｍについてのグループ署名は、有効である。
【００７１】
●受領者ｐＲは、次に、以下を計算することによって、メッセージｍをリカバリすることができる。
【数１５７】
2018507658.tif 000162
これにて、受領者ｐＲは、メッセージｍについてのグループの署名を検証したばかりでなく、ｍを暗号解読した。
【００７２】
分散型鍵生成
標準閾値暗号演算（例えば、上述したもの）は、伝統的に、信頼されたディーラー
【数１５８】
2018507658.tif 000163
の存在を必要とし、生成多項式
【数１５９】
2018507658.tif 000164
を定義し、秘密ｒを選択し、およびｒの共有を全ての参加者
【数１６０】
2018507658.tif 000165
に分散する。分散型鍵生成プロトコル（例えば、Ｉｂｒａｈｉｍ、Ｐｅｄｅｒｓｅｎ、「Ａ  Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍ  ｗｉｔｈｏｕｔ  ａ  Ｔｒｕｓｔｅｄ  Ｐａｒｔｙ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＥＵＲＯＣＲＹＰＴ９１、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第５４７巻、第５２２〜５２６頁、Ｓｐｒｉｎｇｅｒ、１９９１、Ｔａｎｇ、「ＥＣＤＫＧ：Ａ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ  Ｂａｓｅｄ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｓｃｒｅｔｅ  Ｌｏｇａｒｉｔｈｍ」、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ０４−８３８、Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｏｕｔｈｅｒｎ  Ｃａｌｉｆｏｒｎｉａ、２００４）は、信頼されたディーラーの必要性を取り除き、および１組の参加者
【数１６１】
2018507658.tif 000166
が、誰も共有された秘密ｒを知らない秘密の共有を生成することを可能にする。これは、以下のように本文脈において達成することができる。
【００７３】
●各参加者
【数１６２】
2018507658.tif 000167
が、次数ｔ−１のランダム多項式
【数１６３】
2018507658.tif 000168
を定義し、ここで、ｔは、閾値である。参加者ｐｉの一時的なプライベート値は、
【数１６４】
2018507658.tif 000169
の自由係数である。
【００７４】
●各参加者
【数１６５】
2018507658.tif 000170
は、
【数１６６】
2018507658.tif 000171
を参加者ｐｊ、
【数１６７】
2018507658.tif 000172
に非公式に送信する。
【００７５】
●参加者ｐｉは、
【数１６８】
2018507658.tif 000173
の係数に対するコミットメント
【数１６９】
2018507658.tif 000174
をブロードキャストする。
【００７６】
●参加者ｐｉは、全ての参加者のための公開共有
【数１７０】
2018507658.tif 000175
をブロードキャストする。
【００７７】
●各参加者
【数１７１】
2018507658.tif 000176
は、次に、それらが受信した共有を検証する必要がある。
−最初に、各参加者
【数１７２】
2018507658.tif 000177
は、以下のことを検証する。
【数１７３】
2018507658.tif 000178
【００７８】
−同様に、各参加者
【数１７４】
2018507658.tif 000179
は、それらの共有が、他の共有と一貫することを検証する。
【数１７５】
2018507658.tif 000180
【００７９】
●これらの２つの検証が成功する場合、各参加者
【数１７６】
2018507658.tif 000181
は、以下の、マスター非対称私有鍵ｒのその共有を計算する。
【数１７７】
2018507658.tif 000182
【００８０】
●同様に、グループのためのマスター非対称公開鍵は、以下のように計算される。
【数１７８】
2018507658.tif 000183
【００８１】
分散型鍵生成プロトコルは、好ましくは、Ｇｅｎｎａｒｏら（「Ｓｅｃｕｒｅ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ  ｆｏｒ  Ｄｉｓｃｒｅｔｅ−Ｌｏｇ  Ｂａｓｅｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＥＵＲＯＣＲＹＰＴ  ９９、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第１５９２巻、第２９５〜３１０頁、Ｓｐｒｉｎｇｅｒ、１９９９）によって説明される攻撃におけるような、出力分散を偏らせることを試みる敵に対して安全である。（Ｇｅｎｎａｒｏら（「Ｓｅｃｕｒｅ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｐｅｄｅｒｓｅｎ’ｓ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｋｅｙ  Ｇｅｎｅｒａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ」、Ｔｏｐｉｃｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＣＴ−ＲＳＡ  ２００３、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第２６１２巻、第３７３〜３９０頁、Ｓｐｒｉｎｇｅｒ、２００３）は、後に、多くの閾値演算が、出力分散を偏らせる敵の能力にもかかわらず、安全に行われ得ることを結論付けた）。同様に、閾値構築は、好ましくは、静的な敵のみならず適応性のある悪意のある敵の両方に対して安全である（Ａｂｅら、「Ａｄａｐｔｉｖｅｌｙ  Ｓｅｃｕｒｅ  Ｆｅｌｄｍａｎ  ＶＳＳ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｕｎｉｖｅｒｓａｌｌｙ−Ｃｏｍｐｏｓａｂｌｅ  Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ  ２００４、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第３１５２巻、第３１７〜３３４頁、Ｓｐｒｉｎｇｅｒ、２００４、Ｊａｒｅｃｋｉら、「Ａｄａｐｔｉｖｅｌｙ  Ｓｅｃｕｒｅ  Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ：Ｉｎｔｒｏｄｕｃｉｎｇ  Ｃｏｎｃｕｒｒｅｎｃｙ，  Ｒｅｍｏｖｉｎｇ  Ｅｒａｓｕｒｅｓ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＥＵＲＯＣＲＹＰＴ  ２０００、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第１８０７巻、第２２１〜２４２頁、Ｓｐｒｉｎｇｅｒ、２０００、Ｌｉｂｅｒｔら、「Ａｄａｐｔｉｖｅｌｙ  Ｓｅｃｕｒｅ  Ｆｏｒｗａｒｄ−Ｓｅｃｕｒｅ  Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  Ｔｈｒｅｓｈｏｌｄ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｌｏｇｙ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第７５３７巻、第１〜２１頁、Ｓｐｒｉｎｇｅｒ、２０１２）。
【００８２】
ＰＵＦでイネーブルにされる閾値暗号法
ＰＵＦのコア機能は、チャレンジ（入力）ドメインおよびレスポンス（出力）範囲の間の固有マッピングを抽出することである。チャレンジからレスポンスまでのマッピングは、各ＰＵＦでイネーブルにされるデバイスに対して固有であるので、プロビジョニングプロセスを通して１組のチャレンジ−レスポンス対（ＣＲＰ）を収集することは、デバイスが、将来検証されることを可能にする。プロトコル１は、多くのＰＵＦでイネーブルにされるプロトコルの基底をなすナイーブなプロビジョニングプロセスを例解する。
【００８３】
【表４】
2018507658.tif 000184
【００８４】
認証は、チャレンジのためにレスポンスがサーバに知られる該チャレンジを発行することによって、およびレスポンスが、予想されたレスポンスに対してｔ近似であることを検証することによって、進む。しかしながら、この軽量でナイーブなプロトコルは、多くの制限を有する。登録の間、多数のチャレンジ−レスポンス対は、各対が、認証のために１回だけ使用され得るように、収集される必要がある。敵がレスポンスを観測した場合、それは、デバイスとして偽り得る。同様に、敵は、機械学習を適用して、ＰＵＦマッピング［Ｒuｈｍａｉｒ  Ｉ］を十分に特徴付け得るので、チャレンジ−レスポンスデータベースは、センシティブである。これらの発行は、ＰＵＦ機能の周りに暗号化構築を適用することによって、完全に排除され得る。
【００８５】
楕円曲線暗号法を利用する実施形態の例では、以下のアルゴリズム１および２が使用され得、ＰＵＦでイネーブルにされるデバイスが、任意のセンシティブ情報を不揮発性メモリに記憶せずに、センシティブ値をローカルに記憶し、かつ取り出すことを可能にする。アルゴリズム１は、ＰＵＦを使用するセンシティブ値
【数１７９】
2018507658.tif 000185
の記憶を例解し、アルゴリズム２は、
【数１８０】
2018507658.tif 000186
の動的再生成を例解する。チャレンジｃｉおよびヘルパーデータヘルパーｉは、センシティブ値
【数１８１】
2018507658.tif 000187
について何も明らかにされないように、公開され得る。本例は、排他的論理和
【数１８２】
2018507658.tif 000188
による
【数１８３】
2018507658.tif 000189
の暗号化を使用するが、
【数１８４】
2018507658.tif 000190
がまた、任意のサイズの値の記憶および取り出しをイネーブルにするために他の暗号化アルゴリズム（例えば、ＡＥＳ）に対する鍵として使用されてもよい。
【００８６】
【表５】
2018507658.tif 000191
【００８７】
ＯおよびＯ’がｔ近似である場合は常に、誤り訂正符号ＥＣＣが、復号アルゴリズムＤに渡され得、それは、センシティブ値
【数１８５】
2018507658.tif 000192
をリカバリする。
【００８８】
アルゴリズム３を使用して、ローカルデバイスは、ＰＵＦを使用する登録プロトコルを行うことができる。これは、各ＰＵＦ回路が、ローカル公開鍵
【数１８６】
2018507658.tif 000193
を生成することを可能にし、それは、より複雑な鍵セットアップアルゴリズム（例えば、アルゴリズ４における分散型鍵生成プロトコル）をブートストラップするのに有用である。鍵セットアップアルゴリズムが、（１組の別個のデバイス間で外部ではなくて）デバイスの内部で行われるとき、このブートストラッププロセスは、必要でなくてもよい。
【００８９】
【表６】
2018507658.tif 000194
【００９０】
発明によれば、ＰＵＦに基づく暗号プリミティブは、秘密共有に適合され、ＰＵＦまたは他の信頼の基点に基づく閾値暗号を許可する。楕円曲線暗号法を利用する実施形態の例を使用すると、分散型鍵生成は、マスター私有鍵
【数１８７】
2018507658.tif 000195
のいくらかの共有（例えば、２つ：ｒ１、ｒ２）を生成するために使用され、それ自体は、決して生成または構築されない。（また、私有鍵ではなくて（例えば、Ｅｒｔａｕｌによって説明されるような）メッセージと共に直接的に機能することができる）。プロトコルは、アルゴリズム４：ＰＵＦ−ＤＫＧに要約され、ここで、例示的な実現形態は、（ｔ，ｎ）を（２，２）として選ぶ。
【００９１】
【表７】
2018507658.tif 000196
【００９２】
センシティブ値を記憶して取り出すためのアルゴリズム１および２、ならびに最初の分散型鍵生成プロトコルを行うためのアルゴリズム４を使用して、任意のＰＵＦでイネーブルにされる閾値暗号演算（例えば、暗号解読、デジタル署名、ゼロ知識証明）が、次に行われ得る。アルゴリズム５は、入力として参加者の共有ｒｉを必要とする任意の閾値暗号演算
【数１８８】
2018507658.tif 000197
をどのように評価するかを説明する。リカバリされた共有ｒｉは、ラグランジュ項
【数１８９】
2018507658.tif 000198
によって既に乗算されていることに留意する。
【００９３】
【表８】
2018507658.tif 000199
【００９４】
これは、任意の閾値暗号演算（例えば、暗号解読、デジタル署名生成、ゼロ知識証明）が、それらの私有鍵を決して生成、再構築、または記憶せずに、ＰＵＦでイネーブルにされる参加者によって行われることを可能にする。更に、外部見地（例えば、サーバ）から、ＰＵＦでイネーブルにされるデバイスは、単純に、標準公開鍵暗号化プロトコルを実装する。すなわち、サーバは、決して、チャレンジを発行しないか、またはヘルパーデータを記憶せず、デバイスとのその相互作用は、任意の標準公開鍵暗号デバイスと区別不可能である。
【００９５】
ＰＵＦのチャレンジ−レスポンス機能を内在化することによって、かつアルゴリズム１および２を利用して値（例えば、暗号化鍵）をローカルに記憶してリカバリすることによって、任意の（例えば、対称または非対称）暗号演算が、補助（例えば、チャレンジもしくはヘルパーデータ）情報を発行または記憶する必要性なしに、行われ得る。本明細書に説明される一実施形態は、分散型鍵生成および閾値暗号の両方を通じた構築を有利に強化するが、どちらも、本発明に係るデバイスのＰＵＦ機能を使用して、値のローカライズされた記憶および取り出しを通じて、任意の暗号演算をサポートする必要がない。
【００９６】
閾値暗号は、典型的には、物理的に別個のノードにわたって演算を分散することを考慮に入れるが、本発明の一実施形態では、閾値暗号は、単一デバイス内に適用されてもよい。例として、デバイスは、例えば、２つのＰＵＦ回路（例えば、リングオシレータ、アービタ、ＳＲＡＭ）を装備してもよいし、同時に（例えば、複数のＣＰＵコアを通して）少なくとも２つの命令を実行する能力を備えてもよい。かかるデバイスの一実施形態は、例えば、２１５，０００個の論理セル、１３メガバイトのブロックランダムアクセスメモリ、および７００個のデジタル信号処理（ＤＳＰ）スライスを装備した、Ｘｉｌｉｎｘ  Ａｒｔｉｘ  ７フィールドプログラマブルゲートアレイ（ＦＰＧＡ）プラットフォームを備え得る。楕円曲線暗号を利用する実施形態では、例えば、ハードウェア数学的エンジンが、基盤に搭載されたＤＳＰスライスにおいてインスタンス化され得、ＰＵＦ構築が論理セル内に位置付けられ、論理処理コアが、ＰＵＦへの入力および出力を含み、それらを制御するように構築され、デバイスの外部入力および出力が、例えば上記したものなどのアルゴリズムを行う（楕円曲線および他の数学的計算を数学的エンジンに送信する）。ＦＰＧＡは、ＦＰＧＡ構造の別個の領域内に実装される１つ以上のＰＵＦ回路を有してもよい。同時実行が、複数のソフトウェアＣＰＵ、例えば、ＭｉｃｒｏＢｌａｚｅプロセッサをインスタンス化することによって、達成されてもよい。１つのＰＵＦ回路のみを用いる本発明の実施形態は、単純に、複数のＰＵＦ回路に並列にクエリするのではなくて、各共有上で順番に演算を実行する。図２は、ローカル閾値暗号演算をイネーブルにするために２つのＰＵＦ回路を装備したデバイスを例解し、そのデバイスは、例えば、別個のコアが各ＰＵＦを含有する、ＦＰＧＡであってもよい。単一ＰＵＦの潜在的に抽出可能な出力は、次いで、ローカル（２，２）閾値システムを構築することによって不要にされ得、部分ｐｉのそれぞれが、別の参加者として機能する。例えば、各部分は、ランダムチャレンジを選択し、登録アルゴリズム（アルゴリズム３）を実行して非対称鍵対
【数１９０】
2018507658.tif 000200
を生成し、およびその公開登録情報をローカルに記憶し、次いで、分散型鍵生成プロトコル（アルゴリズム４）を一緒に実行し、および決して実際に構築されない私有鍵上で全ての暗号演算を行ってもよい。閾値暗号法が単一デバイス内に適用されるとき、全ての計算が、デバイスの内部で行われるので、登録アルゴリズム（アルゴリズム３）を実行して、非対称鍵対を生成する必要がなくてもよい。
【００９７】
アルゴリズム６は、どのように２重ＰＵＦデバイスが、分散型鍵生成を使用してデバイス内で（２，２）閾値共有を構築することによって閾値手法で暗号演算を計算することができるかを説明する。すなわち、２つの部分は、分散型鍵生成を通してどちらの部分にも既知ではない私有鍵を確立し、および対応する公開鍵
【数１９１】
2018507658.tif 000201
を公開する。デバイスを対象とした全ての演算が、次に、内部協力を通して閾値手法で行われ（各部分が、その共有ｒｉを取り出し、ローカル閾値演算を行い、その結果が組み合わされて、閾値演算
【数１９２】
2018507658.tif 000202
を完了する）、一方で、デバイスの入力／出力挙動は、外部システムに対して変化しないままである。
【００９８】
【表９】
2018507658.tif 000203
【００９９】
それゆえ、デバイスに発行されたチャレンジおよび（ある程度、チャレンジの相関関係であり得る）そのレスポンスの間のマッピングに拘束されるのではなくて、マルチＰＵＦデバイスｄｉは、単一静的外部識別情報、
【数１９３】
2018507658.tif 000204
を有することができる。各ＰＵＦコアのチャレンジ−レスポンス機能は、決して、生成または構築されない、デバイスのプライベート識別情報、
【数１９４】
2018507658.tif 000205
の各共有を維持するために使用される。これは、遠隔の敵に対してサイドチャネル攻撃をより困難にさせ、それは、次に、デバイス内で生成された複数の値を同時に観測して解明する必要がある。各部分は、その共有
【数１９５】
2018507658.tif 000206
を取り出し、ローカル閾値演算を行い、共有が、組み合わされて、演算
【数１９６】
2018507658.tif 000207
を完了する。
【０１００】
図７および図８を参照すると、楕円曲線暗号法、２つの共有への鍵の分割、および（２，２）閾値演算を利用する実施形態例のコア操作が説明される。
【０１０１】
●登録コマンド１：最初の登録プロセスの間、サーバおよびデバイスは、有限体
【数１９７】
2018507658.tif 000208
および次数ｑの基点Ｇ上で定義された楕円曲線Ｅについて合意する。ここで、ｐは、λビット長である。サーバは、登録コマンドをデバイスに発行する。
【０１０２】
●分散型鍵生成２：デバイスは、分散型鍵生成をローカルに行い、（決して、生成または構築されない）マスター私有鍵およびその公開鍵
【数１９８】
2018507658.tif 000209
の共有（ｒ０，ｒ１）を作り出す。共有を一緒に直接的に追加するのではなくて（それは、私有鍵ｒ＝ｒ０＋ｒ１を構築する）、公開鍵は、
【数１９９】
2018507658.tif 000210
を計算することによって形成される。
【０１０３】
●ヘルパーデータ生成３：デバイスは、ランダムチャレンジ
【数２００】
2018507658.tif 000211
を生成する。ここで、
【数２０１】
2018507658.tif 000212
は、連結を表し、各ｃｉブロックは、λビット長である。デバイスは、ファジー抽出を通して、各共有ｒｉをチャレンジｃｉ上のＰＵＦの出力Ｏｉに結び付け、それは、公開ヘルパーｈｉを出力する。ＰＵＦ出力Ｏｉには雑音があるので、将来、チャレンジｃｉについてクエリされるときに、新たな出力
【数２０２】
2018507658.tif 000213
が
【数２０３】
2018507658.tif 000214
を満たすという保証は存在しない。しかしながら、Ｏｉおよび
【数２０４】
2018507658.tif 000215
は、いくらかの距離計量（例えば、ハミング距離）に関してｔ近似であることが想定される。それゆえ、誤り訂正符号が、最大ｔまでの誤りが依然としてＯｉをリカバリするように、ＰＵＦ出力に適用されてもよい。誤り訂正は、各共有ｒｉ上で適用されてもよく、この値は、各ヘルパー値
【数２０５】
2018507658.tif 000216
が、共有ｒｉについての情報を明らかにしないように、チャレンジｃｉについてのＰＵＦＯｉの出力で判読不能にされる。ファジー抽出を通したリカバリの間、
【数２０６】
2018507658.tif 000217
の排他的論理和を計算することは、Ｏｉおよび
【数２０７】
2018507658.tif 000218
がｔ近似である場合は常に、ｒｉを戻す。デバイスは、チャレンジ
【数２０８】
2018507658.tif 000219
およびヘルパーデータ
【数２０９】
2018507658.tif 000220
をローカルに記憶し、それは、そのデバイスが、共有を後でリカバリすることを可能にする。チャレンジおよびヘルパーデータの両方が、公開されること、およびＰＵＦを呼び出さずに共有またはデバイスの私有鍵について何も明らかにしないことに留意する。このプロセスは、アルゴリズム１によって説明される。
【０１０４】
●戻される公開鍵４：デバイスは、その公開登録情報
【数２１０】
2018507658.tif 000221
をサーバに戻す。
【０１０５】
●登録の記憶５：サーバは、デバイスに固有の（センシティブでない）識別子（例えば、シリアル番号）と共に、デバイスの公開登録情報を記憶する。
【０１０６】
●閾値演算クエリ６：デバイスが暗号演算（例えば、暗号解読、デジタル署名生成、ゼロ知識証明認証）を行うことをサーバが望むとき、それは、以下を発行する。
−行われるべき演算のための適切なコマンド
−演算のために必要である任意の補助データＡｕｘ（例えば、暗号解読されるべき暗号文、署名されるべきメッセージ）
【０１０７】
●ＰＵＦ取り出し７：デバイスは、そのローカル記憶装置からチャレンジ
【数２１１】
2018507658.tif 000222
およびヘルパーデータ
【数２１２】
2018507658.tif 000223
を読み取る。デバイスは、次いで、各チャレンジブロックｃｉについてＰＵＦをクエリし、出力
【数２１３】
2018507658.tif 000224
をヘルパーブロックｈｉおよび誤り訂正符号と組み合わせて、各共有ブロックｒｉをリカバリする。このプロセスは、アルゴリズム２によって説明される。
【０１０８】
●閾値演算８：デバイスは、各共有ｒｉについて閾値演算
【数２１４】
2018507658.tif 000225
を行う。アルゴリズム５は、任意の閾値演算
【数２１５】
2018507658.tif 000226
のためのこのプロセスを説明する。
【０１０９】
●組み合わされる閾値演算９：デバイスは、閾値演算を組み合わせて、完全な演算
【数２１６】
2018507658.tif 000227
を形成し、結果をサーバに戻す。
【０１１０】
●演算処理１０：サーバは、最終的に、演算のために必要とされる任意の追加的な処理（例えば、ゼロ知識証明の検証）を行う。
【０１１１】
共有リフレッシュ
様々な共有リフレッシュプロトコル（例えば、Ｆｒａｎｋｅｌら、「Ｏｐｔｉｍａｌ−Ｒｅｓｉｌｉｅｎｃｅ  Ｐｒｏａｃｔｉｖｅ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、３８ｔｈ  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、第３８４〜３９３頁、１９９７、Ｈｅｒｚｂｅｒｇら、「Ｐｒｏａｃｔｉｖｅ  Ｐｕｂｌｉｃ  Ｋｅｙ  ａｎｄ  Ｓｉｇｎａｔｕｒｅ  Ｓｙｓｔｅｍｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ４ｔｈ  ＡＣＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、ＣＣＳ’９７、第１００〜１１０頁、ＡＣＭ、１９９７、Ｈｅｒｚｂｅｒｇら、「Ｐｒｏａｃｔｉｖｅ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｏｒ：Ｈｏｗ  ｔｏ  Ｃｏｐｅ  Ｗｉｔｈ  Ｐｅｒｐｅｔｕａｌ  Ｌｅａｋａｇｅ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴ０  ９５、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第９６３巻、第３３９〜３５２頁、Ｓｐｒｉｎｇｅｒ、１９９５）は、１組のプレーヤ
【数２１７】
2018507658.tif 000228
のそれぞれが、時間周期τにおいて元の秘密ｒのそれらの共有
【数２１８】
2018507658.tif 000229
を新たな共有
【数２１９】
2018507658.tif 000230
にリフレッシュすることを可能にし、そのため、新たな共有の結果として生じる組
【数２２０】
2018507658.tif 000231
が、元の秘密の共有のままとなる。このプロトコルは、マスター秘密ｒの再構築を必要とせず、そのため、移動性のある敵は、共有された秘密をリカバリするために固定時間周期τにおいてｔ個のプレーヤを危険にさらす必要がある。次数（ｔ−１）の多項式
【数２２１】
2018507658.tif 000232
は、それぞれが共有
【数２２２】
2018507658.tif 000233
を有するｎ個の参加者間で共有される秘密
【数２２３】
2018507658.tif 000234
を表現することを想定し、プレーヤｐｊのための暗号化を
【数２２４】
2018507658.tif 000235
としておよびｐｊによる暗号解読を
【数２２５】
2018507658.tif 000236
として表すと、１組のプレーヤ
【数２２６】
2018507658.tif 000237
が、以下のようなプロトコルを使用してｒのそれらの共有をリフレッシュすることができる。
【０１１２】
●各プレーヤｐｉは、δｉ（０）＝０であるように、次数（ｔ−１）の新たな多項式を定義する。
【数２２７】
2018507658.tif 000238
【０１１３】
ここで、セット
【数２２８】
2018507658.tif 000239
が、
【数２２９】
2018507658.tif 000240
からランダムに選ばれる。
【０１１４】
●各プレーヤｐｉは、以下のセットを計算し、
【数２３０】
2018507658.tif 000241
検証可能な秘密共有
【数２３１】
2018507658.tif 000242
およびそれらの署名
【数２３２】
2018507658.tif 000243
をブロードキャストする。
【０１１５】
●各プレーヤｐｉは、
【数２３３】
2018507658.tif 000244
をリカバリし、
【数２３４】
2018507658.tif 000245
を検証する。
【数２３５】
2018507658.tif 000246
【０１１６】
●最終的に、各プレーヤｐｉは、以下のように時間周期（τ）からの彼らの共有を更新する。
【数２３６】
2018507658.tif 000247
それゆえ、リフレッシュされた組の共有
【数２３７】
2018507658.tif 000248
は、マスター私有鍵
【数２３８】
2018507658.tif 000249
の共有のままとなり、更に、時間周期τからのｔ−１以下の共有の知識が、時間周期τ＋１において役に立たない。
【０１１７】
アルゴリズム７に略述されるように、参加者は、共有の組
【数２３９】
2018507658.tif 000250
がマスター私有鍵
【数２４０】
2018507658.tif 000251
の共有のままとなるように、時間周期τにおける彼らの共有
【数２４１】
2018507658.tif 000252
を次の時間周期における新たな共有
【数２４２】
2018507658.tif 000253
に更新することができる。
【０１１８】
【表１０】
2018507658.tif 000254
【０１１９】
ハードウェアデバイスは、図８における共有リフレッシュ１１においてアルゴリズム７を行い、次の時間周期τ＋１のために新たな共有
【数２４３】
2018507658.tif 000255
を生成する。ＰＵＦリフレッシュおよび記憶１２において、ハードウェアデバイスは、新たなチャレンジ
【数２４４】
2018507658.tif 000256
を生成し、それは、次の時間周期のためにチャレンジ−ヘルパー対をリフレッシュする。ハードウェアデバイスは、新たなチャレンジを使用して、更新された共有
【数２４５】
2018507658.tif 000257
を記憶する。アルゴリズム５および６は、閾値共有のみならずチャレンジ−ヘルパー対の両方をリフレッシュするように修正され、アルゴリズム８および９は、それぞれ、その修正を反映する。
【０１２０】
【表１１】
2018507658.tif 000258
【０１２１】
【表１２】
2018507658.tif 000259
【０１２２】
例えば、図１に示されるような単一ＰＵＦ実施形態を参照すると、共有更新が、任意選択的に、準備段階（アルゴリズム１０）および適用段階（アルゴリズム１１）に論理的に分配されてもよい。準備の間、各参加者は、そのランダム多項式を生成し、更新のその部分を他の参加者に分散する。全ての参加者が共有更新のそれらの部分をブロードキャストした後、準備段階が完了する。（ブロードキャストは、準備が、例えばＦＰＧＡなどのような単一デバイス内に適用される場合、省略されてもよい）。
【０１２３】
【表１３】
2018507658.tif 000260
【０１２４】
次に、各参加者は、他の参加者から受信した更新情報を検証し、アルゴリズム１１に規定されるように、更新をその共有に適用する。
【０１２５】
【表１４】
2018507658.tif 000261
【０１２６】
ある共有についての各閾値演算は、他の共有とは独立して行われ得るので、デバイスは、１回に１つの共有のみをリカバリする必要がある。このプロセスは、アルゴリズム１２に例解される。コマンド
【数２４６】
2018507658.tif 000262
およびその関連付けられた補助情報Ａｕｘを受信した後、デバイスは、最初に、アルゴリズム１０を行って、共有更新について準備する。次に、デバイスは、各共有について閾値演算を反復的に行う。共有は、不揮発性メモリからチャレンジ−ヘルパー対を読み取ることによって、およびＰＵＦを使用して対応する共有を再生成することによって、リカバリされる。共有について閾値演算を行った後、共有更新が、アルゴリズム１１を使用して適用され、それは、新たな時間周期（τ＋１）について更新された共有を生成する。各共有について閾値演算を計算した後、閾値演算が組み合わされ、結果
【数２４７】
2018507658.tif 000263
を形成し、その結果は、サーバに戻される。
【０１２７】
【表１５】
2018507658.tif 000264
【０１２８】
一実施形態では、（２，２）閾値システムが、デバイスの内部に構築される。アルゴリズム１３は、より一般的なアルゴリズム１２の単一ＰＵＦ（２，２）閾値構築の例を例解する。デバイスは、共有セット｛ｒ０，ｒ１｝を有し、かつ各共有について閾値演算を反復的に計算して、セット
【数２４８】
2018507658.tif 000265
を作り出す。一旦、閾値演算の両方が完了し、かつ共有が更新および記憶されると、２つの閾値演算が、最終出力
【数２４９】
2018507658.tif 000266
に組み合わされる。
【０１２９】
【表１６】
2018507658.tif 000267
【０１３０】
アルゴリズム１３のフロー、より一般的なアルゴリズム１２の特定の単一ＰＵＦ（２，２）閾値構築が、図９に例解される。ステップ１の前に、共有更新準備（アルゴリズム１０）が行われる。ステップ１において、第１の共有
【数２５０】
2018507658.tif 000268
が取り出され、その対応するローカル閾値演算が行われる。共有更新（アルゴリズム１１）が、次いで、
【数２５１】
2018507658.tif 000269
に適用され、次の時間周期に
【数２５２】
2018507658.tif 000270
を生じる。更新された共有が、次いで、新たなランダムチャレンジ
【数２５３】
2018507658.tif 000271
を使用して記憶され、それは、対応するヘルパーデータ
【数２５４】
2018507658.tif 000272
を生成し、それは、更新された共有が、ＰＵＦを使用してリカバリされることを可能にする。同じプロセスが、共有
【数２５５】
2018507658.tif 000273
のためにステップ２において続けられる。最終的に、組み合わされる出力
【数２５６】
2018507658.tif 000274
が、各共有について行われた２つのローカルな閾値演算を組み合わせることによって構築される。
【０１３１】
デバイスは、ある一定の識別情報
【数２５７】
2018507658.tif 000275
を有するが、
【数２５８】
2018507658.tif 000276
を必要とする全ての演算
【数２５９】
2018507658.tif 000277
が、
【数２６０】
2018507658.tif 000278
を決して再構築せずに、かつ各演算が実行された後に変化する値を伴って、行われる。各部分は、ＰＵＦ−記憶およびＰＵＦ−取り出しアルゴリズムを使用して、その共有を維持するので、（チャレンジ、ヘルパー）対は、ＰＵＦ−記憶が実行されるときに、各演算後に更新される。各共有は、新たな時間周期τ＋１のためにリフレッシュされ、および新たなランダムチャレンジ
【数２６１】
2018507658.tif 000279
を生成することによって、かつ更新されたヘルパーをヘルパー
【数２６２】
2018507658.tif 000280
に設定することによって、記憶される。共有再生成、閾値演算、および共有記憶が（同時にではなくて）連続的に起こるように閾値演算をずらすことは、２つ以上の更新された共有の同時のリカバリを排除する。１つの共有が存在する間のいかなる改ざんも、（改ざんが、誤り訂正限定を超えるＰＵＦ出力を強要することを想定すると）別の共有のリカバリを妨げることになり、その場合には、デバイスは、その私有鍵について演算を行うことができない。
【０１３２】
したがって、かかる実施形態に対してサイドチャネル攻撃を適用する敵は、リフレッシュメントの期間を超えることができない観測の期間からｔ個以上の共有を抽出する必要がある。換言すれば、時間周期τからの任意の共有は、時間周期τ＋１において役に立たないので、敵は、所与の時間周期τにおいてｔ個のデバイスを危険にさらす必要がある。それゆえ、サイドチャネル攻撃の難しさは、（各演算後でさえも）より頻繁に更新することによって増大させることができる。（リフレッシュ頻度の増大もまた、複数のＰＵＦデバイス実施形態へのサイドチャネル攻撃が内包する難しさを増し得、それにおいて、遠隔の敵が、デバイス内で同時に生成された複数のＰＵＦ値を観測して解明する必要がある）。
【０１３３】
また、固定されたチャレンジ／ヘルパーおよびレスポンスを使用するシステムの寿命は、老化に起因するハードウェアの誤り率の増加に直接的に制限されるのに対して、各時間周期における対を継続的に更新することによって、誤り率は、名目上ゼロにリセットすることができる。すなわち、各時間周期τの間に対
【数２６３】
2018507658.tif 000281
を定期的にリフレッシュすることは、ＰＵＦ出力をハードウェアの現在の状態に結び付け、前の時間周期からのハードウェアドリフトを取り除く。その点について、図１１は、アルゴリズム２：ＰＵＦ−取り出しを使用して時間τ=０から、元のチャレンジ−ヘルパー対
【数２６４】
2018507658.tif 000282
を使用して時間τ＝１においてその共有をリカバリするデバイスを例解する。デバイスは、次いで、内部で、時間周期τ＝１のために新たなチャレンジ−ヘルパー対
【数２６５】
2018507658.tif 000283
を生成する。共有は、次いで、τ=１のための新たなチャレンジ−ヘルパー対を使用して、アルゴリズム１：ＰＵＦ−記憶を実行することによって記憶される。これは、更新されたチャレンジ−ヘルパー対をハードウェアの現在の状態に結び付け、それは、時間周期
【数２６６】
2018507658.tif 000284
の間に発生されるハードウェア老化を排除する。それゆえ、時間τ＝１におけるＰＵＦ出力におけるビット誤りの予想される数は、ハードウェアが率ｐに従って老化し続けるにもかかわらず、ゼロである。
【０１３４】
図１２に見られ得るように、各ＰＵＦコアの内部チャレンジ−ヘルパー対を定期的に更新するこのプロセスを繰り返すことによって、最大ＰＵＦ出力誤りは、束縛され得、および任意に、リフレッシュ繰り返し周期を調節することによって小さくさせることができる。それゆえ、ＰＵＦマッピングにおける徐々のシフトは、取るに足らない。ハードウェアがその間の時間に致命的に老化しない限り、シフトは、記憶されたチャレンジおよびヘルパーデータに継続的に織り込まれる。
【０１３５】
動的構成員数
この構築における共有の動的性質はまた、参加者が、（ｔ，ｎ）閾値システムにおける１組の参加者に加わってもよいかまたはそれから去ってもよいように、あるグループに参加する参加者の数ｎが、動的に変動され得る実施形態を許可する。この場合では、最大ｎ−ｔまでの参加者が、単に、次の共有リフレッシュプロトコルからそれらを除外することによって、その組
【数２６７】
2018507658.tif 000285
から除かれ得る。参加者ｐｊを１組の参加者に加えるために、それぞれの現在の参加者ｐｉは、それらの共有更新多項式
【数２６８】
2018507658.tif 000286
から余分な共有ｕｉｊを生成する。
【０１３６】
（（ｔ，ｎ）閾値システムにおいて）動的構成員数およびマルチＰＵＦデバイス（複数可）を利用する一部の実施形態では、デバイス（複数可）が、ローカル自己試験を行って、それがハードウェア老化に起因して、その共有をもはやリカバリすることができない点に近づかないことを確実にするように構成されてもよい。２次閾値、
【数２６９】
2018507658.tif 000287
（誤り訂正によって訂正され得る誤りの最大数）は、
【数２７０】
2018507658.tif 000288
誤りがＰＵＦ出力において観測されるときに、遷移プロトコルが始動されるように、デバイスのために設定され得る。遷移プロトコルは、デバイスｄｉが、
【数２７１】
2018507658.tif 000289
をリカバリすることなく、その私有鍵
【数２７２】
2018507658.tif 000290
について演算を行う能力を異なるデバイス
【数２７３】
2018507658.tif 000291
に移すことができる。２重ＰＵＦデバイスの例では、デバイスｄｉが危機的なハードウェア老化を検出するとき（例えば、ＰＵＦ誤りが二次的閾値
【数２７４】
2018507658.tif 000292
を超えるとき）、それは、共有リフレッシュプロトコルを実行し、およびｎを２→４に増加させる。デバイスｄｉは、次に、１組の共有
【数２７５】
2018507658.tif 000293
を所有し、ｄｊが有効であることを検証した後に
【数２７６】
2018507658.tif 000294
をｄｊに非公式に送信する（例えば、ｄｊの登録トークンについて信頼されたソースからの署名を検証し、およびｄｊにゼロ知識証明を行わせる）。一旦、ｄｊがセット
【数２７７】
2018507658.tif 000295
を受信したら、ｄｉおよびｄｊの両方がｄｉとして機能し得、万一、ｄｉのハードウェア故障の場合には、それは、ｄｊと容易に交換され得る。
【０１３７】
内部自己試験手順は、複数のＰＵＦでイネーブルにされるデバイスがより大きなシステム（例えば、以下に記述されるように処理センター）の一部として使用される設定に容易に拡張されてもよい。１つのＰＵＦでイネーブルにされるデバイスが、その共有をリカバリすることに失敗すると、それは、新たなデバイスと交換することができる。残りのおよび正しく機能しているＰＵＦでイネーブルにされるデバイスは、共有更新アルゴリズムを実行し、同様に新たなデバイス共有を送信することによってｎを増加させる。これは、失敗しているデバイスが、広域（ｔ，ｎ）閾値システムの共有で直ちに交換およびプロビジョニングされ得るように、複数のＰＵＦでイネーブルにされるデバイスから成るシステムが、単一エンティティとして機能し続けることを可能にする。
【０１３８】
閾値対称演算
非対称演算に加えて、対称暗号演算がまた、閾値手法で行われてもよい（例えば、Ｎｉｋｏｖａら、「Ｔｈｒｅｓｈｏｌｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ  Ａｇａｉｎｓｔ  Ｓｉｄｅ−Ｃｈａｎｎｅｌ  Ａｔｔａｃｋｓ  ａｎｄ  Ｇｌｉｔｃｈｅｓ」、Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第４３０７巻、第５２９〜５４５頁、Ｓｐｒｉｎｇｅｒ  Ｂｅｒｌｉｎ  Ｈｅｉｄｅｌｂｅｒｇ、２００６、Ｍｏｒａｄｉら、「Ｐｕｓｈｉｎｇ  ｔｈｅ  Ｌｉｍｉｔｓ：Ａ  Ｖｅｒｙ  Ｃｏｍｐａｃｔ  ａｎｄ  ａ  Ｔｈｒｅｓｈｏｌｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ＡＥＳ」、Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯＣＲＹＰＴ  ２０１１、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅの第６６３２巻、第６９〜８８頁、Ｓｐｒｉｎｇｅｒ  Ｂｅｒｌｉｎ  Ｈｅｉｄｅｌｂｅｒｇ、２０１１、Ｂｉｌｇｉｎら、「Ａ  Ｍｏｒｅ  Ｅｆｆｉｃｉｅｎｔ  ＡＥＳ  Ｔｈｒｅｓｈｏｌｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」、Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ、Ｒｅｐｏｒｔ  ２０１３／６９７、２０１３）。これは、全ての暗号演算、非対称および対称性が、私有鍵ではなくて閾値共有について、行われることを可能にする。非対称私有鍵の共有について説明されたリフレッシュプロセスのように、対称鍵の共有もまた、リフレッシュされてもよい。
【０１３９】
再構成可能なＰＵＦ
一実施形態では、再構成可能なＰＵＦがまた、使用されてもよい。（例えば、Ｍａｊｚｏｏｂｉら、「Ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  Ｓｅｃｕｒｅ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ＰＵＦｓ」、ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｔｅｃｈｎｏｌｏｇｙ  Ｓｙｓｔｅｍｓ、第２巻、Ｎｏ．１：５：１〜５：３３、２００９、Ｋｕｒｓａｗｅら、「Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｐｈｙｓｉｃａｌ  Ｕｎｃｌｏｎａｂｌｅ  Ｆｕｎｃｔｉｏｎｓ  −  Ｅｎａｂｌｉｎｇ  ｔｅｃｈｎｏｌｏｇｙ  ｆｏｒ  ｔａｍｐｅｒ−ｒｅｓｉｓｔａｎｔ  ｓｔｏｒａｇｅ」、Ｈａｒｄｗａｒｅ−Ｏｒｉｅｎｔｅｄ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｔｒｕｓｔ、２００９．ＨＯＳＴ’０９．ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ、第２２〜２９頁、２００９、Ｋａｔｚｅｎｂｅｉｓｓｅｒら、「Ｒｅｃｙｃｌａｂｌｅ  ＰＵＦｓ：  ｌｏｇｉｃａｌｌｙ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ＰＵＦｓ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇ、第１巻、Ｎｏ．３：１７７〜１８６、２０１１、Ｅｉｃｈｈｏｒｎら、「Ｌｏｇｉｃａｌｌｙ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ＰＵＦｓ：Ｍｅｍｏｒｙ−ｂａｓｅｄ  Ｓｅｃｕｒｅ  Ｋｅｙ  Ｓｔｏｒａｇｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｓｉｘｔｈ  ＡＣＭ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｃａｌａｂｌｅ  Ｔｒｕｓｔｅｄ  Ｃｏｍｐｕｔｉｎｇ、ＳＴＣ’１１、第５９〜６４頁、ＡＣＭ、２０１１を参照）再構成可能なＰＵＦは、新たなＰＵＦマッピングが生成されるように、そのパラメータを変えることができる。この再構成は、可逆的または不可逆的であってもよいし、永久的であってもよい。
【０１４０】
一例として、デバイスは、不可逆再構成プロセスを有する２つの再構成可能なＰＵＦ回路（例えば、ＰＵＦ−Ａ、ＰＵＦ−Ｂ）、および利用される２−２閾値共有を備えることができる。各共有が、ＰＵＦ−Ａを使用してリカバリされ、かつリフレッシュされた後、それは、ＰＵＦ−Ｂを使用して記憶のためにチャレンジ−ヘルパー対に変えられる。一旦、リフレッシュされた共有の両方がＰＵＦ−Ｂを使用して記憶されたら、再構成プロセスは、ＰＵＦ−Ａが、次に、新たなＰＵＦマッピングを提示するように、ＰＵＦ−Ａに適用される。次に共有がリカバリされる時、同じ手順が、リカバリのためにＰＵＦ−ＢおよびコミットメントのためにＰＵＦ−Ａを使用して行われる。
【０１４１】
別の例として、デバイスは、可逆構成プロセスを有する単一の再構成可能なＰＵＦ回路、および利用される２−２閾値共有を備えてもよい。ＰＵＦ構成は、パラメータによって制御され、そのパラメータは、デバイス上にローカルに記憶されてもよい。パラメータａを使用して、１つの共有をリカバリすると、新たなランダムパラメータｂが選ばれ、ＰＵＦが再構成され、リフレッシュされた共有が、パラメータｂで構成されたＰＵＦを使用して記憶のためにチャレンジ−ヘルパー対に変えられる。ＰＵＦは、次いで、第２の共有をリカバリするためにパラメータａを使用して再構成され、その第２の共有は、その後、リフレッシュされ、およびパラメータｂで構成されたＰＵＦを使用して記憶のためにチャレンジ−ヘルパー対に変えられる。この際、元のＰＵＦパラメータａが削除され、次のラウンドは、新たなランダムパラメータｃを選択して、パラメータｂを交換する。
【０１４２】
スケーラビリティ
標準ＰＵＦプロトコルは、元来、特定のハードウェアデバイスに結び付けられ（実際、これは、それらの目標であり）、それは、システムを容易にスケールして任意の処理負荷をサポートする能力に制約を課し得る。図１３は、プライベート情報を動的に再生成するために利用されるＰＵＦを用いて、任意に大きな処理負荷をサポートすることをスケールするように設計された処理センターを例解する。分散型鍵生成を通して秘密の（ｔ，ｎ）共有を構築することによって、システムのための私有鍵は、決して構築または記憶されない。しかしながら、任意のｔ個のＰＵＦは、処理センターに代わって、暗号演算を行うように協力することができる。例えば、ｔ=７である場合、ＰＵＦの各列は、処理センターの代わりに、暗号演算を共同で行うことができ、（列Ａ〜Ｄを使用する）４つの要求が、同時に完了され得る。それゆえ、スケーラブルなハードウェアに本来備わる識別情報ソリューションが設計され得、それにおいて、ローカルハードウェアに本来備わる識別情報を有する（例えば、ＰＵＦを装備した）ハードウェア構成要素のグループが、全体としてそれらのグループのための固有のハードウェアに本来備わる識別情報を形成するように協力的に機能することができる。発明の本実施形態は、システムを構成するデバイスが、ローカルに閾値暗号を実装することを必要としない。むしろ、各デバイスは、アルゴリズム３を実行し、かつそのローカル公開鍵
【数２７８】
2018507658.tif 000296
を公開してもよい。次いで、（ｔ，ｎ）共有が、プライベート通信のために各デバイスのローカル公開鍵を使用して、システムのためにセットアップされる。
【０１４３】
図１４は、１組の構成要素識別情報から生成されるマスター識別情報を例解する。（ｎ，ｎ）閾値システムは、マスター識別情報を使用して暗号演算を行うために、全ての構成要素がそれらの共有をリカバリすることができることを必要とするように構築されてもよい。発明の別の実施形態では、（ｔ，ｎ）閾値システムは、危機的な構成要素の全ておよび非危機的な構成要素の一部が、マスター識別情報を使用して暗号演算を行うために、それらの共有をリカバリすることができることを必要とするように構築されてもよい。
【０１４４】
性能
（誤り訂正を必要としなかった）単一模擬３８４ビットリングオシレータＰＵＦ、およびＮＩＳＴ楕円曲線Ｐ−３８４上で定義される（２，２）閾値システムを有する実施形態について性能試験を行った。各共有についての演算を、複数のＰＵＦ実施形態において行われ得るように同時にではなくて、順番に行った。試験は、値の記憶および取り出し、ならびにデバイスおよびサーバ間の通信のために必要な合計時間を測定した。サーバは、８個のコア３．１ＧＨｚプロセッサおよび１６ＧＢのＲＡＭ、ならびに１１５２００ボー接続上で１００ＭＨｚにおいて実行するＸｉｌｉｎｘ  Ａｒｔｉｘ  ７ＦＰＧＡ上に実装されるデバイスサイドアルゴリズムを装備した。ここで、全ての演算は、ＮＩＳＴ  Ｐ−３８４曲線上で行った。表１は、１０００回の試行にわたるプロトコル毎の平均時間を報告する。
【０１４５】
【表１７】
2018507658.tif 000297
【図１】
2018507658.tif 000298
【図２】
2018507658.tif 000299
【図３】
2018507658.tif 000300
【図４】
2018507658.tif 000301
【図５】
2018507658.tif 000302
【図６】
2018507658.tif 000303
【図７】
2018507658.tif 000304
【図８】
2018507658.tif 000305
【図９】
2018507658.tif 000306
【図１０】
2018507658.tif 000307
【図１１】
2018507658.tif 000308
【図１２】
2018507658.tif 000309
【図１３】
2018507658.tif 000310
【図１４】
2018507658.tif 000311
【国際調査報告】
2018507658.tif 000312