[go: up one dir, main page]

JP2018507658A - 物理的複製不可能関数および閾値暗号化を含む認証システムならびにデバイス - Google Patents

物理的複製不可能関数および閾値暗号化を含む認証システムならびにデバイス Download PDF

Info

Publication number
JP2018507658A
JP2018507658A JP2017546818A JP2017546818A JP2018507658A JP 2018507658 A JP2018507658 A JP 2018507658A JP 2017546818 A JP2017546818 A JP 2017546818A JP 2017546818 A JP2017546818 A JP 2017546818A JP 2018507658 A JP2018507658 A JP 2018507658A
Authority
JP
Japan
Prior art keywords
puf
processor
output
challenge
share
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP2017546818A
Other languages
English (en)
Inventor
ジョン・ロス・ウォールラベンスタイン
Original Assignee
アナログ ディヴァイスィズ インク
アナログ ディヴァイスィズ インク
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US14/704,914 external-priority patent/US10432409B2/en
Priority claimed from US14/746,054 external-priority patent/US9946858B2/en
Application filed by アナログ ディヴァイスィズ インク, アナログ ディヴァイスィズ インク filed Critical アナログ ディヴァイスィズ インク
Publication of JP2018507658A publication Critical patent/JP2018507658A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/30—Authentication, i.e. establishing the identity or authorisation of security principals
    • G06F21/31—User authentication
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3271—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response
    • H04L9/3278—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response using physically unclonable functions [PUF]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/30—Authentication, i.e. establishing the identity or authorisation of security principals
    • G06F21/31—User authentication
    • G06F21/34—User authentication involving the use of external additional devices, e.g. dongles or smart cards
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09C—CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
    • G09C1/00—Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2221/00—Indexing scheme relating to security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F2221/21—Indexing scheme relating to G06F21/00 and subgroups addressing additional information or applications relating to security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F2221/2129—Authenticate client device independently of the user
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/12—Details relating to cryptographic hardware or logic circuitry
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/46—Secure multiparty computation, e.g. millionaire problem

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Storage Device Security (AREA)

Abstract

物理的複製不可能関数（ＰＵＦ）入力およびＰＵＦ出力を有し、かつチャレンジの入力に応答して、ＰＵＦおよびチャレンジに特有の出力値を生成するように構築されたＰＵＦデバイスと、ＰＵＦ出力に接続されるプロセッサ入力を有し、かつＰＵＦ入力に接続されるプロセッサ出力を有するプロセッサであって、プロセッサ出力経由でのＰＵＦ入力へのチャレンジの発行を制御して、ＰＵＦ出力からの出力を受信し、かつ所望の暗号化出力のインスタンスに関して以下の一連のステップを複数回実行するように構成されたプロセッサと、を備える、ＰＵＦおよび閾値暗号化を含む認証システムならびにデバイス。

Description

本開示は、一般に、ハードウェア検証、特に、ただし、非排他的に、置換による改ざんおよび破壊に対して保護するための束縛認証（ｂｉｎｄｉｎｇ ａｕｔｈｅｎｔｉｃａｔｉｏｎ）に関する。
関連出願の相互参照
本国際出願は、２０１５年５月５日に出願された米国非仮特許出願通し番号第１４／７０４，９１４号（「’９１４出願」）および２０１５年６月２２日に出願された（’９１４出願の一部継続であった）通し番号第１４／７４６，０５４号、ならびに２０１５年３月５日に出願された米国仮特許出願通し番号第６２／１２８，９２０号（「’９２０出願」）および２０１５年４月２１日に出願された通し番号第６２／１５０，５８６号（「’５８６出願」）の優先権の利益を主張する。’９２０および’５８６出願ならびに（米国特許出願公開第２０１５０３１７４８０号の訴訟の記録において公開された）２０１４年５月５日に出願された米国仮特許出願通し番号第６１／９８８，８４８号の内容もまた、参照によって本明細書に組み込まれる。
ＰＵＦの固有特性は、暗号構築にいくつかの利点を提供する。一般に、ＰＵＦは、３つの主な利点（１）私有鍵の記憶の排除、（２）改ざん検出の提供、および（３）ハードウェアの信頼の基点の確立のうちの一部または全てを提供し得る。私有鍵の記憶は、ＰＵＦを評価して、そのＰＵＦを有するハードウェアの識別された部分に固有の値を動的に再生成することによって排除することができる。改ざん検出に関して、ＰＵＦの複製不可能特性（例えば、配線遅延、抵抗）は、ＰＵＦに対する修正が、登録後にチャレンジ（入力）からレスポンス（出力）へのＰＵＦのマッピングを不可逆的に変更するようなものであり得る（しかしながら、登録前の悪意のある修正に対するものではない。例えば、Ｂｅｃｋｅｒら、「Ｓｔｅａｌｔｈｙ Ｄｏｐａｎｔ−Ｌｅｖｅｌ Ｈａｒｄｗａｒｅ Ｔｒｏｊａｎｓ」、Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ−ＣＨＥＳ ２０１３、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第８０８６巻、第１９７〜２１４頁、Ｓｐｒｉｎｇｅｒ、２０１３）。これらのＰＵＦ特性は、ハードウェアに固有の、改ざんから保護された値を作り出すために使用され得、その値から、ハードウェアの信頼の基点を確立することができる。
Ｒuｈｍａｉｒ（uはウムラウト付き、以下同じ）ら（「Ｍｏｄｅｌｉｎｇ Ａｔｔａｃｋｓ ｏｎ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ ＡＣＭ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｓｅｃｕｒｉｔｙ、ＣＣＳ’１０、第２３７〜２４９頁、ＡＣＭ、２０１０）は、ＰＵＦデバイスの３つの別個のクラスを定義する。
●弱いＰＵＦは、典型的には、秘密鍵を導出するためにのみ使用される。チャレンジスペースは、限定され得、レスポンススペースは、決して明らかにされないことが想定される。典型的な構築は、ＳＲＡＭ（Ｈｏｌｃｏｍｂら、「Ｉｎｉｔｉａｌ ＳＲＡＭ Ｓｔａｔｅ ａｓ ａ Ｆｉｎｇｅｒｐｒｉｎｔ ａｎｄ Ｓｏｕｒｃｅ ｏｆ Ｔｒｕｅ Ｒａｎｄｏｍ Ｎｕｍｂｅｒｓ ｆｏｒ ＲＦＩＤ Ｔａｇｓ」、Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＲＦＩＤ Ｓｅｃｕｒｉｔｙ、２００７）、バタフライ（Ｋｕｍａｒら、「Ｅｘｔｅｎｄｅｄ ａｂｓｔｒａｃｔ：Ｔｈｅ Ｂｕｔｔｅｒｆｌｙ ＰＵＦ Ｐｒｏｔｅｃｔｉｎｇ ＩＰ ｏｎ Ｅｖｅｒｙ ＦＰＧＡ」、ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈａｒｄｗａｒｅ−Ｏｒｉｅｎｔｅｄ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｔｒｕｓｔ、第６７〜７０頁、２００８）、アービタ（Ｌｅｅら、「Ａ ｔｅｃｈｎｉｑｕｅ ｔｏ ｂｕｉｌｄ ａ ｓｅｃｒｅｔ ｋｅｙ ｉｎ ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔｓ ｆｏｒ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ ａｕｔｈｅｎｔｉｃａｔｉｏｎ ａｐｐｌｉｃａｔｉｏｎｓ」、ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ ＶＬＳＩ Ｃｉｒｃｕｉｔｓ：Ｄｉｇｅｓｔ ｏｆ Ｔｅｃｈｎｉｃａｌ Ｐａｐｅｒｓ、第１７６〜１７９頁、２００４）、リングオシレータ（Ｓｕｈら、「Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ ｆｏｒ Ｄｅｖｉｃｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ ａｎｄ Ｓｅｃｒｅｔ Ｋｅｙ Ｇｅｎｅｒａｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４４ｔｈ ａｎｎｕａｌ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ、ＤＡＣ’０７、第９〜１４頁、ＡＣＭ、２００７）、およびコーティング（Ｔｕｙｌｓら、「Ｒｅａｄ− Ｐｒｏｏｆ Ｈａｒｄｗａｒｅ ｆｒｏｍ Ｐｒｏｔｅｃｔｉｖｅ Ｃｏａｔｉｎｇｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８ｔｈ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ、ＣＨＥＳ’０６、第３６９〜３８３頁、Ｓｐｒｉｎｇｅｒ、２００６）ＰＵＦを含む。
●強いＰＵＦは、（ｉ）物理的に複製することが不可能であり、（ｉｉ）（典型的には、約数週間かかる）合理的な時間内に完全な組のチャレンジレスポンス対を収集することが不可能であり、および（ｉｉｉ）ランダムチャレンジに対するレスポンスを予測することが困難であることが想定される。例えば、Ｒuｈｍａｉｒ（「Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｈｉｇｈ−Ｃａｐａｃｉｔｙ Ｃｒｏｓｓｂａｒ Ｍｅｍｏｒｉｅｓ ｉｎ Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ Ｔｒａｎｓ．Ｎａｎｏｔｅｃｈｎｏｌ．、第１０巻、Ｎｏ．３：４８９−４９８、２０１１）によって説明された超高情報含量（ＳＨＩＣ）ＰＵＦが、強いＰＵＦとして考えられ得る。
●制御されたＰＵＦは、強いＰＵＦのための基準の全てを満たし、かつより高度な機能を計算してプロトコルを暗号で増強することが可能な補助制御ユニットを追加的に実装する。
ＰＵＦ出力には、同じ入力を評価するにもかかわらず、わずかに変動するという点で雑音がある。これは、一般に、生体測定における雑音を除去するように開発されたファジー抽出方法で対処される。（Ｊｕｅｌｓら、「Ａ Ｆｕｚｚｙ Ｃｏｍｍｉｔｍｅｎｔ Ｓｃｈｅｍｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６ｔｈ ＡＣＭ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｅｃｕｒｉｔｙ、ＣＣＳ’９９、第２８〜３６頁、ＡＣＭ、１９９９を参照。）ファジー抽出は、出力が固定入力に対して一定であるように、例えば補助制御ユニット内などのＰＵＦを有するデバイス内で部分的に利用されてもよい。ファジー抽出（または逆ファジー抽出）は、例えば、Ｊｕｅｌｓらによって説明されるような「セキュアスケッチ（ｓｅｃｕｒｅ ｓｋｅｔｃｈ）」を利用して、再構築されるべきセンシティブ値
をリカバリするためのヘルパーストリンググ（ｈｅｌｐｅｒ ｓｔｒｉｎｇ）ヘルパーｉを記憶してもよい。入力ストリングＯのためのセキュアスケッチＳＳは、例えば、
として定義され得、ここで、ＥＣＣは、ｔ誤りを訂正することができる長さｎの二元（ｎ，ｋ，２ｔ＋１）誤り訂正符号であり、
は、ｋビット値である。元の値Ｖが、次いで、誤り訂正符ＥＣＣおよびＯ’のための復号スキームＤを使用して、ヘルパーストリングヘルパーｉおよびＯの最大ハミング距離ｔ内の入力Ｏ’を仮定して、
として、再生され得る。
物理的複製不可能関数Ｐｄ：デバイスｄに束縛された
は、好ましくは、以下の特性を呈する。
１．複製不可能性：
、それらの出力分散が統計的にｔ近似（ｔ−ｃｌｏｓｅ）であるように、クローンＰＵＦ Ｐ’を用いてＰＵＦ Ｐを複製する確率は、かなり十分に小さな
よりも少ない。
２．予測不可能性：敵が、無視できるほどの確率を超えて（少なくとも、デバイスへの物理的なアクセスを用いずに）、チャレンジｃについてのデバイスのＰＵＦレスポンスｒを予測することができないこと、およびヘルパーデータが、ＰＵＦレスポンスについて敵に何も明らかにしないことが望ましい。全てのエンティティは、確率論的多項式時間（ＰＰＴ）に束縛され、すなわち、（関連したパラメータにおけるビットの数のことを言う）広域セキュリティパラメータλに関して、多項式的に多くの演算を必要とする計算のみを効率的に行うことができることを想定すると、チャレンジｃに対するＰＵＦ Ｐの訂正レスポンスｒを推測する敵
の確率を表す、
は、好ましくは、Κ２において無視できる。これは、例えば、敵
およびＰＵＦデバイスＰ間のゲーム、すなわち、長さΚ１のチャレンジスペース
から長さΚ２のレスポンススペース
までの
マッピング入力ストリングを通して査定され得、ここで、λは、プロトコルのためのセキュリティパラメータであり、１λとして単項で仮定する。
ゲームは、以下のように進む。
１．敵
は、（セキュリティパラメータλに関して）多項式的に多くのチャレンジ
をＰＵＦデバイスＰに発行し、ここで、チャレンジセット
は、チャレンジスペース全体
の適切なサブセットである。
２．ＰＵＦデバイスＰは、レスポンス
を
に戻す。
３．敵
は、結局、チャレンジクエリ
の元のセットになかったチャレンジｃを出力する。敵は、コミットされたチャレンジｃについてＰＵＦデバイスＰにクエリすることを許可されない。
４．敵
は、多項式的に多くのチャレンジ
の新たなセットをＰＵＦデバイスＰにもう１度発行してもよい。敵は、コミットされたチャレンジｃについてＰＵＦデバイスＰにクエリすることを許可されない。
５．ＰＵＦデバイスＰは、レスポンス
を
に戻す。
６．敵
は、結局、コミットされたチャレンジｃに対するＰのレスポンスについての推測ｒ’を出力する。
敵は、推測ｒ’が、
のコミットされたチャレンジｃに対するＰの実際のレスポンス
に等しいときにのみ、ゲームに勝つ。（留意されるように、ＰＵＦの出力は、雑音のあるものであり、かつ任意の固定入力についてわずかに変動し、そのため、同等性は、典型的には、ファジー抽出器の出力に関して取られる（例えば、Ｄｏｄｉｓら、「Ｆｕｚｚｙ Ｅｘｔｒａｃｔｏｒｓ：Ｈｏｗ ｔｏ Ｇｅｎｅｒａｔｅ Ｓｔｒｏｎｇ Ｋｅｙｓ ｆｒｏｍ Ｂｉｏｍｅｔｒｉｃｓ ａｎｄ Ｏｔｈｅｒ Ｎｏｉｓｙ Ｄａｔａ」、ＳＩＡＭ Ｊ． Ｃｏｍｐｕｔ．、第３８巻、Ｎｏ．１：９７〜１３９、２００８））。
３．ロバスト性：
、すなわち、同じ入力ｘについてｔ離れたレスポンスを生じる固定ＰＵＦＰの確率は、いくらか十分に小さい
よりも少ない。
４．不可区別性：ＰＵＦデバイスの出力（典型的には、ファジー抽出器出力）は、好ましくは、ＰＰＴ敵
のアドバンテージ
が、最大でも無視できるほどに１／２を超えるように、同じ長さｌのランダムストリングから計算的に区別不可能である。ＰＵＦの不可区別性は、例えば、敵
が、ＰＵＦ Ｐのためのファジー抽出器の出力ｒおよび同じ長さｌのランダムに選ばれたストリング
を見分けることを尋ねられるゲームを通して、査定され得る。
このゲームは、以下のように進む。
１．敵
は、任意のチャレンジ
についての登録段階を実行する。
２．ＰＵＦデバイスは、対応するヘルパーストリングＨｉを戻し、それは、ＰＵＦ Ｐ（ｃ）の出力で誤り訂正されたセンシティブ値ＥＣＣ（Ｒｉ）を判読不能にする。チャレンジ−ヘルパー対（ｃｉ、Ｈｉ）のこのセットを
として表す。
３．敵
は、次に、任意の
についてのＰＵＦレスポンスｒｉ＝Ｐ（ｃｉ）を要求する。このステップにおいて要求されるチャレンジのセットを
で表す。
４．全ての要求
について、ＰＵＦデバイスは、セット
を戻す。
５．敵
は、
が、ｃのためにＲｉではなくて、Ｈｉを有するように、チャレンジ
を選択する。ＰＵＦデバイスは、ランダムに一様にビット
を選ぶ。
６．ｂ＝０である場合、
は、
を与えられる。そうではなくて、ｂ＝１である場合には、
は、ランダムストリング
を与えられる。
7．敵
でない限り、
についてＰＵＦデバイスにクエリすることを許可されない。
８．全ての要求
について、ＰＵＦデバイスは、セット
を戻す。
９．敵は、推測ビットｂ’を出力し、ｂ’＝ｂであるときに成功する。
ＰＵＦの関連した査定は、Ｈｏｒｉら、「Ｑｕａｎｔｉｔａｔｉｖｅ ａｎｄ Ｓｔａｔｉｓｔｉｃａｌ Ｐｅｒｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ａｒｂｉｔｅｒ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ ｏｎ ＦＰＧＡｓ」、２０１０ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ ＦＰＧＡｓ （ＲｅＣｏｎＦｉｇ）、第２９８〜３０３頁、２０１０、Ｍａｉｔｉ、Ａ Ｓｙｓｔｅｍａｔｉｃ Ａｐｐｒｏａｃｈ ｔｏ Ｄｅｓｉｇｎ ａｎ Ｅｆｆｉｃｉｅｎｔ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎ、論文、Ｖｉｒｇｉｎｉａ Ｔｅｃｈ、２０１２、および他のものによって提供される。
物理的複製不可能関数についての文献は、ＰＵＦハードウェア設計の特性を評価する（例えば、Ｇａｓｓｅｎｄら、「Ｓｉｌｉｃｏｎ Ｐｈｙｓｉｃａｌ Ｒａｎｄｏｍ Ｆｕｎｃｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ＡＣＭ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｓｅｃｕｒｉｔｙ、ＣＣＳ’０２、第１４８〜１６０頁、ＡＣＭ、２００２、Ｋａｔｚｅｎｂｅｉｓｓｅｒら、「ＰＵＦ：Ｍｙｔｈ、Ｆａｃｔ ｏｒ Ｂｕｓｔｅｄ？Ａ Ｓｅｃｕｒｉｔｙ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ （ＰＵＦｓ） Ｃａｓｔ ｉｎ Ｓｉｌｉｃｏｎ」、Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ − ＣＨＥＳ’１２、第２８３〜３０１頁、Ｓｐｒｉｎｇｅｒ、２０１２、Ｒａｖｉｋａｎｔｈ、Ｐｈｙｓｉｃａｌ ｏｎｅ−ｗａｙ ｆｕｎｃｔｉｏｎｓ、Ｐｈ．Ｄ．論文、２００１、Ｒuｈｍａｉｒら、「Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｈｉｇｈ−Ｃａｐａｃｉｔｙ Ｃｒｏｓｓｂａｒ Ｍｅｍｏｒｉｅｓ ｉｎ Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ Ｔｒａｎｓ．Ｎａｎｏｔｅｃｈｎｏｌ．、第１０巻、Ｎｏ．３：４８９〜４９８、２０１１、Ｓｕｈら、「Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ ｆｏｒ Ｄｅｖｉｃｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ ａｎｄ Ｓｅｃｒｅｔ Ｋｅｙ Ｇｅｎｅｒａｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４４ｔｈ ａｎｎｕａｌ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ、ＤＡＣ’０７、第９〜１４頁、ＡＣＭ、２００７、Ｙｕら、「Ｒｅｃｏｍｂｉｎａｔｉｏｎ ｏｆ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ」、ＧＯＭＡＣＴｅｃｈ、２０１０）は、ＰＵＦ特性の形式理論モデルを提供し、それらの定義に関するプロトコルを設計する（Ａｒｍｋｎｅｃｈｔら、「Ａ Ｆｏｒｍａｌｉｚａｔｉｏｎ ｏｆ ｔｈｅ Ｓｅｃｕｒｉｔｙ Ｆｅａｔｕｒｅｓ ｏｆ Ｐｈｙｓｉｃａｌ Ｆｕｎｃｔｉｏｎｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１１ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ、ＳＰ’１１、第３９７〜４１２頁、ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ、２０１１、Ｂｒｚｕｓｋａら、「Ｐｈｙｓｉｃａｌｌｙ Ｕｎ−ｃｌｏｎｅａｂｌｅ Ｆｕｎｃｔｉｏｎｓ ｉｎ ｔｈｅ Ｕｎｉｖｅｒｓａｌ Ｃｏｍｐｏｓｉｔｉｏｎ Ｆｒａｍｅｗｏｒｋ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ − ＣＲＹＰＴＯ ２０１１ − ３１ｓｔ Ａｎｎｕａl Ｃｒｙｐｔｏｌｏｇｙ Ｃｏｎｆｅｒｅｎｃｅ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第６８４１巻、第５１頁、Ｓｐｒｉｎｇｅｒ、２０１１、Ｆｒｉｋｋｅｎら、「Ｒｏｂｕｓｔ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｕｓｉｎｇ Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ」、Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第５７３５巻、第２６２〜２７７頁、Ｓｐｒｉｎｇｅｒ、２００９、Ｈａｎｄｓｃｈｕｈら、「Ｈａｒｄｗａｒｅ Ｉｎｔｒｉｎｓｉｃ Ｓｅｃｕｒｉｔｙ ｆｒｏｍ Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ」、Ｔｏｗａｒｄｓ Ｈａｒｄｗａｒｅ−Ｉｎｔｒｉｎｓｉｃ Ｓｅｃｕｒｉｔｙ、Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｃｒｙｐｔｏｇｒａｐｈｙ、第３９〜５３頁、Ｓｐｒｉｎｇｅｒ、２０１０、Ｋｉｒｋｐａｔｒｉｃｋら、「ＰＵＦ ＲＯＫｓ：Ａ Ｈａｒｄｗａｒｅ Ａｐｐｒｏａｃｈ ｔｏ Ｒｅａｄ−Ｏｎｃｅ Ｋｅｙｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６ｔｈ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ， Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｅｃｕｒｉｔｙ、ＡＳＩＡＣＣＳ’１１、第１５５〜１６４頁、ＡＣＭ、２０１１、Ｐａｒａｌら、「Ｒｅｌｉａｂｌｅ ａｎｄ Ｅｆｆｉｃｉｅｎｔ ＰＵＦ−ｂａｓｅｄ Ｋｅｙ Ｇｅｎｅｒａｔｉｏｎ ｕｓｉｎｇ Ｐａｔｔｅｒｎ Ｍａｔｃｈｉｎｇ」、ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｈａｒｄｗａｒｅ− Ｏｒｉｅｎｔｅｄ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｔｒｕｓｔ （ＨＯＳＴ）、第１２８〜１３３頁、２０１１、Ｒuｈｍａｉｒら、「ＰＵＦｓ ｉｎ Ｓｅｃｕｒｉｔｙ Ｐｒｏｔｏｃｏｌｓ：Ａｔｔａｃｋ Ｍｏｄｅｌｓ ａｎｄ Ｓｅｃｕｒｉｔｙ Ｅｖａｌｕａｔｉｏｎｓ」、２０１３ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｐｒｉｖａｃｙ、第０巻：２８６〜３００、２０１３、ｖａｎ Ｄｉｊｋら、「Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ ｉｎ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｐｒｏｔｏｃｏｌｓ：Ｓｅｃｕｒｉｔｙ Ｐｒｏｏｆｓ ａｎｄ Ｉｍｐｏｓｓｉｂｉｌｉｔｙ Ｒｅｓｕｌｔｓ」、Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ、Ｒｅｐｏｒｔ ２０１２／２２８、２０１２、Ｗｕら、「Ｏｎ Ｆｏｕｎｄａｔｉｏｎ ａｎｄ Ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ」、２０１０、Ｙｕら、「Ｌｉｇｈｔｗｅｉｇｈｔ ａｎｄ Ｓｅｃｕｒｅ ＰＵＦ Ｋｅｙ Ｓｔｏｒａｇｅ ｕｓｉｎｇ Ｌｉｍｉｔｓ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １３ｔｈ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ、ＣＨＥＳ’１１、第３５８〜３７３頁、Ｓｐｒｉｎｇｅｒ、２０１１を参照）。
先行技術のＰＵＦに基づくプロトコルは、以下の２つの広いカテゴリに分類される。（１）プロトコル１に以下に説明されるものと同様の単純なチャレンジ−レスポンスプロビジョニングプロセス、または（２）生のＰＵＦ出力が決してデバイスから出ないような、デバイスのＰＵＦレスポンスの暗号化増強。これらのアプローチは、外部エンティティが、既存の公開鍵暗号標準においてサポートされないかまたは不必要な補助情報（例えば、チャレンジおよびそれらの関連付けられたヘルパーデータ）を取り扱うこと、および／またはハードウェアデバイスが、最初の登録プロセスの間に適用されるチャレンジが本物であることを証明することを伴うことを必要とし得、ならびに／あるいはハードウェアデバイスが、所与のチャレンジに対する本質的に同じレスポンスを常にリカバリすることを前提とする。
所与のチャレンジ−レスポンス対は、対が収集されたときのデバイスのハードウェア状態を反映するが、デバイスは、老化し、そのハードウェア状態は、時が経つにつれてドリフトする。ＰＵＦハードウェアが老化するので、レスポンスに存在する誤りの数は、増大し得る。Ｍａｉｔｉら（「Ｔｈｅ Ｉｍｐａｃｔ ｏｆ Ａｇｉｎｇ ｏｎ ａｎ ＦＰＧＡ−Ｂａｓｅｄ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ （ＦＰＬ）、第１５１〜１５６頁、２０１１）は、通常動作条件を越えてデバイスに意図的にストレスかけることによって、ＰＵＦハードウェアへの模擬老化の影響を研究する。温度および電圧の両方を変動させることによって、著者は、時が経つにつれて、偽陰性を導く内部ＰＵＦ変動におけるドリフトを示すことができた。Ｍａｉｔｉらは、誤りドリフトが、５０％の最大エントロピー率の傾向がある内部ＰＵＦ誤り率分散に厳密に影響を及ぼしたことに言及する。十分な時間が経過した後、ハードウェアデバイスは、登録されたチャレンのために適切なレスポンスをリカバリすることがもはやできなくなり得る。
例えば、特定のチャレンジｃｉが、登録の間にデバイスに発行され、デバイスが、デバイスのハードウェア識別情報をチャレンジｃと結び付ける公開トークン｛コミットメントｉ，ヘルパーｉ｝を戻すことを想定する。本物であることを証明されるために、デバイスは、対｛ｃｉ，ヘルパーｉ｝を使用して、そのプライベート識別情報
をリカバリする。図１０に示されるように、時が経つにつれて、ＰＵＦハードウェアは、ハードウェア老化が、デバイスの誤り訂正限界を超えて誤りを増大した時間に（例えば、図１０の例では、簡潔さのために、時が経つにつれて、直線的に発生するドリフトを想定する、時間τ＝５において）達し得、デバイスは、その私有鍵を確実に再生成することがもはやできない。
Ｋｉｒｋｐａｔｒｉｃｋら（「Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｉｑｕｅｓ ｔｏ Ｃｏｍｂａｔ Ｄｒｉｆｔ ｉｎ ＰＵＦ−ｂａｓｅｄ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｓｙｓｔｅｍｓ」、Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｅｃｕｒｅ Ｃｏｍｐｏｎｅｎｔ ａｎｄ Ｓｙｓｔｅｍ Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ、２０１０）は、ハードウェア老化ドリフトを検出するための、および外部サーバ上に記憶されたデバイスのチャレンジ−コミットメント対を更新することによって応答するための方法を説明する。このアプローチは、サーバが、チャレンジ−コミットメント対の形態で補助情報を維持するが、定期的なプロトコルが、サーバおよびデバイスの間で実行されることを必要とする。
ＰＵＦに基づくシステムに対抗する別のチャレンジは、サイドチャネル攻撃であり、それは、補助環境変数の観測および解析を試み、センシティブＰＵＦ出力についての情報を演繹する。例えば、電磁気（ＥＭ）解析（例えば、Ｍｅｒｌｉら、「Ｓｅｍｉ−ｉｎｖａｓｉｖｅ ＥＭ Ａｔｔａｃｋ ｏｎ ＦＰＧＡ ＲＯ ＰＵＦｓ ａｎｄ Ｃｏｕｎｔｅｒｍｅａｓｕｒｅｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ Ｓｅｃｕｒｉｔｙ、ＷＥＳＳ’１１、第２：１〜２：９頁、ＡＣＭ、２０１１、Ｍｅｒｌｉら、「Ｓｉｄｅ−Ｃｈａｎｎｅｌ Ａｎａｌｙｓｉｓ ｏｆ ＰＵＦｓ ａｎｄ Ｆｕｚｚｙ Ｅｘｔｒａｃｔｏｒｓ」、Ｔｒｕｓｔ ａｎｄ Ｔｒｕｓｔｗｏｒｔｈｙ Ｃｏｍｐｕｔｉｎｇ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第６７４０巻、第３３〜４７頁、Ｓｐｒｉｎｇｅｒ、２０１１、Ｓｃｈｕｓｔｅｒ、Ｓｉｄｅ−Ｃｈａｎｎｅｌ Ａｎａｌｙｓｉｓ ｏｆ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ （ＰＵＦｓ）、修士論文、Ｔｅｃｈｎｉｓｃｈｅ Ｕｎｉｖｅｒｓｉｔａｔ Ｍｕｎｃｈｅｎ、２０１０）は、デバイス動作の間に変化するＥＭ場を観測することによって、ＰＵＦ出力ビットを抽出する。別のサイドチャネル攻撃方法論は、（単純または差分）電力解析であり（例えば、Ｋａｒａｋｏｙｕｎｌｕら、「Ｄｉｆｆｅｒｅｎｔｉａｌ ｔｅｍｐｌａｔｅ ａｔｔａｃｋｓ ｏｎ ＰＵＦ ｅｎａｂｌｅｄ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｄｅｖｉｃｅｓ」、ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｆｏｒｅｎｓｉｃｓ ａｎｄ Ｓｅｃｕｒｉｔｙ （ＷＩＦＳ）、第１〜６頁、２０１０、Ｋｏｃｈｅｒら、「Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ」、Ｃｒｙｐｔｏｇｒａｐｈｙ Ｒｅｓｅａｒｃｈ， Ｉｎｃ．、２０１１、Ｋｏｃｈｅｒら、「Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９ｔｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｒｙｐｔｏｌｏｇｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ’９９、第３８８〜３９７頁、Ｓｐｒｉｎｇｅｒ、１９９９、Ｒuｈｍａｉｒら、「Ｐｏｗｅｒ ａｎｄ Ｔｉｍｉｎｇ Ｓｉｄｅ Ｃｈａｎｎｅｌｓ ｆｏｒ ＰＵＦｓ ａｎｄ ｔｈｅｉｒ Ｅｆｆｉｃｉｅｎｔ Ｅｘｐｌｏｉｔａｔｉｏｎ」、２０１３）、この場合、電力トレースが、デバイスから収集され、かつセンシティブ情報（例えば、ＰＵＦ出力ビット）を抽出するように解析される。固定チャレンジに対する本質的に同じレスポンスをリカバリするデバイスの多くの観測を通じて、敵は、センシティブＰＵＦ出力を発見することができる。
サイドチャネル攻撃の有効性は、一部のシステムにおいて、ランダム性を導入することによって低減され得ることが知られる（Ｃｏｒｏｎ、「Ｒｅｓｉｓｔａｎｃｅ Ａｇａｉｎｓｔ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ Ｆｏｒ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第１７１７巻、第２９２〜３０２頁、Ｓｐｒｉｎｇｅｒ、１９９９）が、このようにして、センシティブ値を区別することは、いくらかの脆弱性を残し得る。なぜなら、基底値は、静的なままであり、ならびに／あるいは追加的な複雑性および／または処理オーバーヘッドを導くからである。
本発明に係る認証システムでは、ＰＵＦのチャレンジ−レスポンス挙動が、私有鍵の共有を維持するために内在化および使用され得る。このアプローチは、ＰＵＦでイネーブルにされるハードウェアデバイスが、一度も私有鍵を生成、再構築、または記憶せずに、任意の閾値暗号演算（例えば、暗号解読、デジタル署名生成、ゼロ知識証明）を実行することができるように実装され得る。また、任意の外部エンティティが、あるデバイスのためにチャレンジを発行するおよびヘルパーデータを記憶する必要性を排除するように、および／または外部エンティティが、標準公開鍵プロトコルと区別することができないＰＵＦに基づくプロトコルをイネーブルにするように、実装されてもよい。一実施形態では、デバイスが、例えばＰＵＦなどの信頼の基点を装備してもよいし、およびデバイスによって生成、リカバリ、または処理される必要がある全てのセンシティブ値を定期的にリフレッシュするように構成されてもよい。これは、ＰＵＦの老化および／またはサイドチャネル攻撃を軽減するために利用されてもよい。閾値共有演算は、１つの共有が、常に記憶されたままであるように、スタッガード式にされてもよい。
図１は、単一ＰＵＦ回路および２つの閾値共有を有するデバイスの機能図である。 図２は、２重ＰＵＦ回路を有するデバイスの機能図である。 図３は、１点のみを仮定して、次数ｄ＝３の多項式Ｐ（ｘ）例を補間する試みを例解するグラフであり、それは、少なくともｄ＋１点が必要とされるので失敗する。 図４は、２点を仮定して、同じ多項式Ｐ（ｘ）を補間することに失敗した試みを例解する。 図５は、３点を仮定して、同じ多項式Ｐ（ｘ）を補間することに失敗した試みを例解する。 図６は、４点を仮定して、Ｐ（ｘ）の成功した補間を例解する。 図７は、発明のある実施形態における図２のものと同様のデバイスの登録の操作上のフローチャートである。 図８は、発明のある実施形態における図２のものと同様のデバイスにおける閾値暗号演算の操作上のフローチャートである。 図９は、スタッガード式閾値演算の操作上のフローチャートである。 図１０は、固定チャレンジのためのＰＵＦ出力における経時的な誤りを例解するグラフである。 図１１は、τ＝１について、更新されたチャレンジ−ヘルパー対を用いてＰＵＦ出力における経時的な誤りを例解するグラフである。 図１２は、束縛されたＰＵＦ誤り率を確立する対のリフレッシュを伴う、ＰＵＦ出力における経時的な誤りを例解するグラフである。 図１３は、一括ＰＵＦ処理センターを描写する図である。 図１４は、複合要素からの共同識別情報を描写する図である。
本発明は、（関連付けられた専門用語および慣習を含む）楕円曲線暗号法を利用する実施形態の例を参照して説明されるが、本明細書における発明的概念および教示は、様々な他の暗号スキーム、例えば、離散対数または因数分解のような異なる問題を利用するものなど（米国特許第８，９１８，６４７号の教示に関係するものが、参照によって組み込まれる）に同等に適用され、発明は、発明と共にまたは発明に基づいて利用され得る本明細書に説明される様々な追加的な特徴によって限定されない。
閾値暗号法
閾値暗号法は、演算が、参加者の定足数の協力を用いてのみ可能であるように、１組の参加者の間で暗号演算を分散することを伴う。信頼されたディーラー
は、１組の参加者
のためにマスター非対称鍵対
を生成する。私有鍵が、次いで、ｎ個の参加者間に分配され、各参加者は、
の共有を受信する。これは、少なくともｔ個の参加者の定足数が、マスター私有鍵を使用して演算を行うために、それらのプライベート共有を組み合わせる必要があるように、
の（ｔ，ｎ）共有を構成する。
他の秘密スキームが、本発明と共に使用され得る（例えば、Ｂｌａｋｌｅｙ、「Ｓａｆｅｇｕａｒｄｉｎｇ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｋｅｙｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９７９ ＡＦＩＰＳ Ｎａｔｉｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｃｏｎｆｅｒｅｎｃｅ、第３１３〜３１７頁、ＡＦＩＰＳ Ｐｒｅｓｓ、１９７９）が、ある例が、Ｓｈａｍｉｒの多項式補間構築（「Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ」、Ｃｏｍｍｕｎ．ＡＣＭ、第２２巻、Ｎｏ．１１：６１２〜６１３、１９７９）を利用して説明され、それは、秘密を共有するために使用することができる。次数ｔ−１の多項式
が定義され、ここで、係数ｃｉは、秘密のままである。すなわち、
係数の知識がなくても、
は、
の少なくともｔ点が、ラグランジュの多項式補間アプローチを適用することによって知られるときに評価することができる。私有鍵
は、自由係数ｃ０
として設定され得、私有鍵の１組の共有が参加者に分散される（例えば、Ｅｒｔａｕｌ、「ＥＣＣ Ｂａｓｅｄ Ｔｈｒｅｓｈｏｌｄ Ｃｒｙｐｔｏｇｒａｐｈｙ ｆｏｒ Ｓｅｃｕｒｅ Ｄａｔａ Ｆｏｒｗａｒｄｉｎｇ ａｎｄ Ｓｅｃｕｒｅ Ｋｅｙ Ｅｘｃｈａｎｇｅ ｉｎ ＭＡＮＥＴ （Ｉ）」、ＮＥＴＷＯＲＫＩＮＧ ２００５、Ｎｅｔｗｏｒｋｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ， Ｓｅｒｖｉｃｅｓ， ａｎｄ Ｐｒｏｔｏｃｏｌｓ； Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｎｅｔｗｏｒｋｓ；Ｍｏｂｉｌｅ ａｎｄ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｙｓｔｅｍｓ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第３４６２巻、第１０２〜１１３頁、Ｓｐｒｉｎｇｅｒ、２００５を参照）。ｎ個の参加者
間で私有鍵
を分配するために、ディーラーは、
であるように、ｐｉの＜公開，私有＞鍵対を＜ｒｉ・Ｇ ｍｏｄ ｑ，ｒｉ＞として計算する。ここで、
は、楕円曲線Ｅのための次数ｑの基点であり、（Ｐ）ｘ（あるいは（Ｐ）ｙ）は、曲線Ｅ上の点Ｐのｘ（あるいはｙ）座標のことを言う（演算が行われる母数は、それが状況から明らかである場合に省略されてもよい）。公開鍵は、全ての参加者に利用可能にされるが、私有鍵は、各参加者に安全に（例えば、デバイスの公開鍵およびＥｌＧａｍａｌ暗号法を使用して）分散される。全ての参加者はまた、
へのアクセスを与えられ、それは、彼らが、以下のことをチェックすることによって、彼らの秘密鍵および他の参加者の公開鍵を検証することを可能にする。
参加者は、世界的に既知の公開鍵に関して、それらの共有の正当性を検証することができるので、これは、私有鍵
の（ｔ，ｎ）検証可能な秘密共有（ＶＳＳ）（例えば、Ｆｅｌｄｍａｎ、「Ａ Ｐｒａｃｔｉｃａｌ Ｓｃｈｅｍｅ ｆｏｒ Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２８ｔｈ Ａｎｎｕａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、ＳＦＣＳ’８７、第４２７〜４３８頁、ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ、１９８７、Ｐｅｄｅｒｓｅｎ、「Ｎｏｎ−Ｉｎｔｅｒａｃｔｉｖｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ−Ｔｈｅｏｒｅｔｉｃ Ｓｅｃｕｒｅ Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ ９１、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第５７６巻、第１２９〜１４０頁、Ｓｐｒｉｎｇｅｒ、１９９２）を構成する。
次に、任意のｔ個の共有
へのアクセスを仮定すると、ここで、
は、次数ｔ−１を有しかつｔ≦ｎであり、共有（ｉ，ｒｉ）は、以下のf（ｘ）を評価するためにラグランジュ多項式補間を通して組み合わせてもよい。
これは、ｔ個の参加者の任意の定足数
が、それらの共有
を組み合わせること、および多項式の自由係数
をリカバリすることを可能にし、それは、マスター非対称私有鍵
である。ラグランジュ形式が、補間多項式のために使用されるが、（例えば、単項式基準またはニュートン形式を使用する）他のアプローチを代用してもよい。同様に、例示的な構築は、
を評価し、係数をリカバリするものではない。代わりに、後者は、ヴァンデルモンド行列表現を使用しておよび線形方程式系を解いて達成してもよい。
図３〜図６は、
のラグランジュ多項式補間を例解する。補間多項式
は、１組のｋ点
から生成される。図３は、単一点のみから生成された補間多項式
を例解する。図４は、２点から生成された補間多項式
を例解する。図５は、３点から生成された補間多項式
を例解する。図６は、４点から生成された補間多項式
を例解する。多項式の次数が３のみである際、任意の４点が、元の多項式の完全な補間を結果としてもたらす。セットｋのサイズが多項式ｔ−１の次数を超える（すなわち、ｋ≧ｔである）とき、
は、元の多項式
を完全に補間する。このため、この例では、補間多項式は、４点から生成され、それは、多項式の次数（３）を超える。ｋ＜ｔ点の任意のセットを仮定すると、ｋ＜ｔ点のセットを満足する次数ｔ−１の無限数の多項式が存在するので、秘密Ｐ（０）について何の情報も明らかにされないことに留意する。
例示的な実施形態は、楕円曲線暗号法を使用してもよいが、様々な他の暗号フレームワーク（例えば、ＥｌＧａｍａｌ、ＲＳＡ、ＮＴＲＵ等）が利用され得ることが容易に明らかであろう。いくらかの閾値暗号演算が、このフレームワーク内で、種々の方法、例えば、閾値暗号法、暗号解読、および署名、知識の閾値ゼロ知識証明、閾値サインクリプション、ならびに分散型鍵生成などを使用して、実行され得る。他の楕円曲線機構、例えば、Ｍａｓｓｅｙ−Ｏｍｕｒａ、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ、Ｍｅｎｅｚｅｓ−Ｖａｎｓｔｏｎｅ、Ｋｏｙａｍａ−Ｍａｕｒｅｒ−Ｏｋａｍｏｔｏ−Ｖａｎｓｔｏｎｅ、Ｅｒｔａｕｌ、Ｄｅｍｙｔｋｏなどが、同様に利用されてもよい。
デバイスの登録情報
を所有しているエンティティは、それゆえ、対象デバイスのみが、例えば、以下のＥｌＧａｍａｌ暗号法などの方法を使用して、それをリカバリすることができるように、メッセージｍを暗号化することができる。
次いで、グループの全ての参加者
が、グループ私有鍵ｒを使用して、メッセージ
の暗号化
の暗号解読を望み、ここで、
である場合、（例えば、Ｅｒｔａｕｌによって）閾値ＥｌＧａｍａｌ暗号解読を以下のように使用することができる。
●各参加者
は、それらの秘密鍵
を使用して、以下のシャドウを計算する。
●各参加者は、次いで、
として定義されたそれらの部分的な暗号解読Ｓｉをブロードキャストする。
●各参加者は、以下の値をローカルに計算する。
●最終的に、各参加者は、次に、
を計算することによって、メッセージｍをローカルにリカバリしてもよい。
同様に、グループ
は、閾値署名スキームを使用することができ、ここで、
であり（例えば、Ｃｈｅｎら、「Ａｎ ｅｆｆｉｃｉｅｎｔ ｔｈｒｅｓｈｏｌｄ ｇｒｏｕｐ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ」、ＩＥＥＥ Ｒｅｇｉｏｎ １０ Ｃｏｎｆｅｒｅｎｃｅ ＴＥＮＣＯＮ、第Ｂ巻、第１３〜１６頁、Ｖｏｌ．２、２００４、Ｈｕａ−ｑｕｎら、「Ｖｅｒｉｆｉａｂｌｅ （ｔ， ｎ） Ｔｈｒｅｓｈｏｌｄ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ ｂａｓｅｄ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ」、Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ Ｊｏｕｒｎａｌ ｏｆ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅｓ、第１０巻、Ｎｏ．１：１６５〜１６８、２００５、Ｉｂｒａｈｉｍら、「Ａ Ｒｏｂｕｓｔ Ｔｈｒｅｓｈｏｌｄ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ ｐｒｏｖｉｄｉｎｇ ａ Ｎｅｗ Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｓｃｈｅｍｅ」、ＩＥＥＥ ４６ｔｈ Ｍｉｄｗｅｓｔ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ、第１巻、第２７６〜２８０頁、Ｖｏｌ．１、２００３、Ｋｉｍら、「Ｔｈｒｅｓｈｏｌｄ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅｓ ｆｏｒ ＥｌＧａｍａｌ Ｖａｒｉａｎｔｓ」、Ｃｏｍｐｕｔｅｒ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｉｎｔｅｒｆａｃｅｓ、第３３巻、Ｎｏ．４：４３２〜４３７、２０１１、Ｓｈａｏ、「Ｒｅｐａｉｒｉｎｇ Ｅｆｆｉｃｉｅｎｔ Ｔｈｒｅｓｈｏｌｄ Ｇｒｏｕｐ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｎｅｔｗｏｒｋ Ｓｅｃｕｒｉｔｙ、２００８）、以下のようにメッセージｍのための
の全てを表現する署名を生成する。
●各参加者
は、それらの秘密鍵
およびランダム整数
を使用して、メッセージｍのためのそれらの個々の署名（Ｒｉ，Ｓｉ）を計算する。
−最初に、Ｒｉが、
から計算され、全ての参加者
に公開される。
−次に、各参加者ｐｉが、以下のようにＲ、ｅ、およびＳｉを計算する。
は、暗号学的ハッシュ関数を表す。各参加者は、指定されたセクレタリ（便宜のために、信頼される必要のないもの）にＳｉをブロードキャストする。
●全ての（Ｒｉ，Ｓｉ）対を受信したセクレタリは、以下の計算によって署名を検証する。
適切に構築される場合、この式は、以下のように保たれる。
●これらが保たれる場合、セクレタリが、以下を計算する。
それは、ｍについてグループ署名（（Ｒ）ｙｍｏｄ ｑ，Ｓ）を計算する。
●（Ｒ，Ｓ）の受領後、受信側ｐＲは、参加者
のグループ全体の公開鍵
に対するその有効性、すなわち、
をチェックし、それは、以下の理由のために、有効な署名を保つ。
グループの参加者
はまた、協力して、以下のように、知識の閾値ゼロ知識証明（例えば、Ｓａｒｄａｒら、「Ｚｅｒｏ Ｋｎｏｗｌｅｄｇｅ Ｐｒｏｏｆ ｉｎ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｓｃｈｅｍｅ Ｕｓｉｎｇ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｇｒａｐｈｙ」、Ｇｌｏｂａｌ Ｔｒｅｎｄｓ ｉｎ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍｓ、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｉｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅの第２６９巻、第２２０〜２２６頁、Ｓｐｒｉｎｇｅｒ、２０１２）を使用して、共有された私有鍵
の所有を実証することができ、ここで、
、およびｔ≦ｎである。
●グループ公開鍵は
であり、ここで、ｒは、共有された秘密であり、Ｇは、グループ生成元である。検証器
は、一過性ノンスＮを選び、これを
の全ての参加者に分散する。
●各参加者
は、それらの秘密共有
およびランダムノンス整数ｙｉを使用して、共有された秘密ｒのそれらの個々の証明（Ｂｉ,Ｍｉ）を計算する。
−最初に、Ｂｉが計算され、全ての参加者
に公開される。
−各参加者は、ローカルに以下を計算する。
−次に、各参加者ｐｉは、以下のように、e、Ｍｉを計算する。
●
の受領後、検証器vは以下を計算する。
●次に、検証器は、公開鍵
に対する証明の有効性をチェックする。
である場合、検証器
は、閾値ゼロ知識証明を有効として受諾し、そうでない場合は証明を拒否する。
メッセージをサインクリプティングするプロセス（例えば、Ｃｈａｎｇｇｅｎら、「Ｔｈｒｅｓｈｏｌｄ Ｓｉｇｎｃｒｙｐｔｉｏｎ Ｓｃｈｅｍｅ ｂａｓｅｄ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍ ａｎｄ Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ、第２巻、第１１８２〜１１８５頁、２００５、Ｚｈｅｎｇ、「Ｄｉｇｉｔａｌ Ｓｉｇｎｃｒｙｐｔｉｏｎ ｏｒ Ｈｏｗ ｔｏ Ａｃｈｉｅｖｅ Ｃｏｓｔ（Ｓｉｇｎａｔｕｒｅ ＆ Ｅｎｃｒｙｐｔｉｏｎ）<<Ｃｏｓｔ （Ｓｉｇｎａｔｕｒｅ） ＋ Ｃｏｓｔ （Ｅｎｃｒｙｐｔｉｏｎ）」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ’９７、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第１２９４巻、第１６５〜１７９頁、Ｓｐｒｉｎｇｅｒ、１９９７、Ｚｈｅｎｇら、「Ｈｏｗ ｔｏ Ｃｏｎｓｔｒｕｃｔ Ｅｆｆｉｃｉｅｎｔ Ｓｉｇｎｃｒｙｐｔｉｏｎ Ｓｃｈｅｍｅｓ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅｓ」、Ｉｎｆ．Ｐｒｏｃｅｓｓ．Ｌｅｔｔ．、第６８巻、Ｎｏ．５：２２７〜２３３、１９９８）は、それぞれ別個に計算することよりも少ない費用で、メッセージの署名および暗号化の両方を行うことを容易にする。メッセージ
および公開鍵
を用いる受信側ｐＲを仮定すると、サインクリプションは、以下のように生成することができる。
●各
は、ランダム
を選択し、
を計算し、これをセクレタリ（便宜のために、信頼される必要がないもの）および受信側ｐＲの両方に公式にブロードキャストする。各
はまた、
を計算し、それは、非公式に（例えば、ＥｌＧａｍａｌ暗号法使用して）ｐＲに送信される。
●セクレタリは、
を計算して、（ｒｉ、
の参加者ｐｉの共有と混同されない）ｒを各署名者
にブロードキャストする。
●各署名者
は、
を計算し、ここで、
は、
のｐｉの共有である。各署名者は、それらの部分的なサインクリプションｓｉをセクレタリに送信する。
●部分的なサインクリプションｓｉの受領後、セクレタリは、
をチェックすることによって、部分的なサインクリプションの有効性を検証するために、
を計算する。
●一旦、全ての部分的なサインクリプションｓｉを受信し、それらの有効性をチェックすると、セクレタリは、それらを組み合わせて、
を計算し、（ｒ，ｓ）は、受信側ｐＲに送信された最終的なサインクリプションである。
●次に
を受信した受信側参加者ｐＲは、以下を計算する。
●受領者ｐＲは、次いで、以下のことを検証する。
これらが保たれる場合、ｍについてのグループ署名は、有効である。
●受領者ｐＲは、次に、以下を計算することによって、メッセージｍをリカバリすることができる。
これにて、受領者ｐＲは、メッセージｍについてのグループの署名を検証したばかりでなく、ｍを暗号解読した。
分散型鍵生成
標準閾値暗号演算（例えば、上述したもの）は、伝統的に、信頼されたディーラー
の存在を必要とし、生成多項式
を定義し、秘密ｒを選択し、およびｒの共有を全ての参加者
に分散する。分散型鍵生成プロトコル（例えば、Ｉｂｒａｈｉｍ、Ｐｅｄｅｒｓｅｎ、「Ａ Ｔｈｒｅｓｈｏｌｄ Ｃｒｙｐｔｏｓｙｓｔｅｍ ｗｉｔｈｏｕｔ ａ Ｔｒｕｓｔｅｄ Ｐａｒｔｙ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＥＵＲＯＣＲＹＰＴ９１、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第５４７巻、第５２２〜５２６頁、Ｓｐｒｉｎｇｅｒ、１９９１、Ｔａｎｇ、「ＥＣＤＫＧ：Ａ Ｄｉｓｔｒｉｂｕｔｅｄ Ｋｅｙ Ｇｅｎｅｒａｔｉｏｎ Ｐｒｏｔｏｃｏｌ Ｂａｓｅｄ ｏｎ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍ」、Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ０４−８３８、Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｏｕｔｈｅｒｎ Ｃａｌｉｆｏｒｎｉａ、２００４）は、信頼されたディーラーの必要性を取り除き、および１組の参加者
が、誰も共有された秘密ｒを知らない秘密の共有を生成することを可能にする。これは、以下のように本文脈において達成することができる。
●各参加者
が、次数ｔ−１のランダム多項式
を定義し、ここで、ｔは、閾値である。参加者ｐｉの一時的なプライベート値は、
の自由係数である。
●各参加者
は、
を参加者ｐｊ、
に非公式に送信する。
●参加者ｐｉは、
の係数に対するコミットメント
をブロードキャストする。
●参加者ｐｉは、全ての参加者のための公開共有
をブロードキャストする。
●各参加者
は、次に、それらが受信した共有を検証する必要がある。
−最初に、各参加者
は、以下のことを検証する。
−同様に、各参加者
は、それらの共有が、他の共有と一貫することを検証する。
●これらの２つの検証が成功する場合、各参加者
は、以下の、マスター非対称私有鍵ｒのその共有を計算する。
●同様に、グループのためのマスター非対称公開鍵は、以下のように計算される。
分散型鍵生成プロトコルは、好ましくは、Ｇｅｎｎａｒｏら（「Ｓｅｃｕｒｅ Ｄｉｓｔｒｉｂｕｔｅｄ Ｋｅｙ Ｇｅｎｅｒａｔｉｏｎ ｆｏｒ Ｄｉｓｃｒｅｔｅ−Ｌｏｇ Ｂａｓｅｄ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＥＵＲＯＣＲＹＰＴ ９９、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第１５９２巻、第２９５〜３１０頁、Ｓｐｒｉｎｇｅｒ、１９９９）によって説明される攻撃におけるような、出力分散を偏らせることを試みる敵に対して安全である。（Ｇｅｎｎａｒｏら（「Ｓｅｃｕｒｅ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ Ｐｅｄｅｒｓｅｎ’ｓ Ｄｉｓｔｒｉｂｕｔｅｄ Ｋｅｙ Ｇｅｎｅｒａｔｉｏｎ Ｐｒｏｔｏｃｏｌ」、Ｔｏｐｉｃｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＣＴ−ＲＳＡ ２００３、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第２６１２巻、第３７３〜３９０頁、Ｓｐｒｉｎｇｅｒ、２００３）は、後に、多くの閾値演算が、出力分散を偏らせる敵の能力にもかかわらず、安全に行われ得ることを結論付けた）。同様に、閾値構築は、好ましくは、静的な敵のみならず適応性のある悪意のある敵の両方に対して安全である（Ａｂｅら、「Ａｄａｐｔｉｖｅｌｙ Ｓｅｃｕｒｅ Ｆｅｌｄｍａｎ ＶＳＳ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ Ｕｎｉｖｅｒｓａｌｌｙ−Ｃｏｍｐｏｓａｂｌｅ Ｔｈｒｅｓｈｏｌｄ Ｃｒｙｐｔｏｇｒａｐｈｙ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴＯ ２００４、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第３１５２巻、第３１７〜３３４頁、Ｓｐｒｉｎｇｅｒ、２００４、Ｊａｒｅｃｋｉら、「Ａｄａｐｔｉｖｅｌｙ Ｓｅｃｕｒｅ Ｔｈｒｅｓｈｏｌｄ Ｃｒｙｐｔｏｇｒａｐｈｙ：Ｉｎｔｒｏｄｕｃｉｎｇ Ｃｏｎｃｕｒｒｅｎｃｙ， Ｒｅｍｏｖｉｎｇ Ｅｒａｓｕｒｅｓ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＥＵＲＯＣＲＹＰＴ ２０００、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第１８０７巻、第２２１〜２４２頁、Ｓｐｒｉｎｇｅｒ、２０００、Ｌｉｂｅｒｔら、「Ａｄａｐｔｉｖｅｌｙ Ｓｅｃｕｒｅ Ｆｏｒｗａｒｄ−Ｓｅｃｕｒｅ Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ Ｔｈｒｅｓｈｏｌｄ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｃｒｙｐｔｏｌｏｇｙ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第７５３７巻、第１〜２１頁、Ｓｐｒｉｎｇｅｒ、２０１２）。
ＰＵＦでイネーブルにされる閾値暗号法
ＰＵＦのコア機能は、チャレンジ（入力）ドメインおよびレスポンス（出力）範囲の間の固有マッピングを抽出することである。チャレンジからレスポンスまでのマッピングは、各ＰＵＦでイネーブルにされるデバイスに対して固有であるので、プロビジョニングプロセスを通して１組のチャレンジ−レスポンス対（ＣＲＰ）を収集することは、デバイスが、将来検証されることを可能にする。プロトコル１は、多くのＰＵＦでイネーブルにされるプロトコルの基底をなすナイーブなプロビジョニングプロセスを例解する。
認証は、チャレンジのためにレスポンスがサーバに知られる該チャレンジを発行することによって、およびレスポンスが、予想されたレスポンスに対してｔ近似であることを検証することによって、進む。しかしながら、この軽量でナイーブなプロトコルは、多くの制限を有する。登録の間、多数のチャレンジ−レスポンス対は、各対が、認証のために１回だけ使用され得るように、収集される必要がある。敵がレスポンスを観測した場合、それは、デバイスとして偽り得る。同様に、敵は、機械学習を適用して、ＰＵＦマッピング［Ｒuｈｍａｉｒ Ｉ］を十分に特徴付け得るので、チャレンジ−レスポンスデータベースは、センシティブである。これらの発行は、ＰＵＦ機能の周りに暗号化構築を適用することによって、完全に排除され得る。
楕円曲線暗号法を利用する実施形態の例では、以下のアルゴリズム１および２が使用され得、ＰＵＦでイネーブルにされるデバイスが、任意のセンシティブ情報を不揮発性メモリに記憶せずに、センシティブ値をローカルに記憶し、かつ取り出すことを可能にする。アルゴリズム１は、ＰＵＦを使用するセンシティブ値
の記憶を例解し、アルゴリズム２は、
の動的再生成を例解する。チャレンジｃｉおよびヘルパーデータヘルパーｉは、センシティブ値
について何も明らかにされないように、公開され得る。本例は、排他的論理和
による
の暗号化を使用するが、
がまた、任意のサイズの値の記憶および取り出しをイネーブルにするために他の暗号化アルゴリズム（例えば、ＡＥＳ）に対する鍵として使用されてもよい。
ＯおよびＯ’がｔ近似である場合は常に、誤り訂正符号ＥＣＣが、復号アルゴリズムＤに渡され得、それは、センシティブ値
をリカバリする。
アルゴリズム３を使用して、ローカルデバイスは、ＰＵＦを使用する登録プロトコルを行うことができる。これは、各ＰＵＦ回路が、ローカル公開鍵
を生成することを可能にし、それは、より複雑な鍵セットアップアルゴリズム（例えば、アルゴリズ４における分散型鍵生成プロトコル）をブートストラップするのに有用である。鍵セットアップアルゴリズムが、（１組の別個のデバイス間で外部ではなくて）デバイスの内部で行われるとき、このブートストラッププロセスは、必要でなくてもよい。
発明によれば、ＰＵＦに基づく暗号プリミティブは、秘密共有に適合され、ＰＵＦまたは他の信頼の基点に基づく閾値暗号を許可する。楕円曲線暗号法を利用する実施形態の例を使用すると、分散型鍵生成は、マスター私有鍵
のいくらかの共有（例えば、２つ：ｒ１、ｒ２）を生成するために使用され、それ自体は、決して生成または構築されない。（また、私有鍵ではなくて（例えば、Ｅｒｔａｕｌによって説明されるような）メッセージと共に直接的に機能することができる）。プロトコルは、アルゴリズム４：ＰＵＦ−ＤＫＧに要約され、ここで、例示的な実現形態は、（ｔ，ｎ）を（２，２）として選ぶ。
センシティブ値を記憶して取り出すためのアルゴリズム１および２、ならびに最初の分散型鍵生成プロトコルを行うためのアルゴリズム４を使用して、任意のＰＵＦでイネーブルにされる閾値暗号演算（例えば、暗号解読、デジタル署名、ゼロ知識証明）が、次に行われ得る。アルゴリズム５は、入力として参加者の共有ｒｉを必要とする任意の閾値暗号演算
をどのように評価するかを説明する。リカバリされた共有ｒｉは、ラグランジュ項
によって既に乗算されていることに留意する。
これは、任意の閾値暗号演算（例えば、暗号解読、デジタル署名生成、ゼロ知識証明）が、それらの私有鍵を決して生成、再構築、または記憶せずに、ＰＵＦでイネーブルにされる参加者によって行われることを可能にする。更に、外部見地（例えば、サーバ）から、ＰＵＦでイネーブルにされるデバイスは、単純に、標準公開鍵暗号化プロトコルを実装する。すなわち、サーバは、決して、チャレンジを発行しないか、またはヘルパーデータを記憶せず、デバイスとのその相互作用は、任意の標準公開鍵暗号デバイスと区別不可能である。
ＰＵＦのチャレンジ−レスポンス機能を内在化することによって、かつアルゴリズム１および２を利用して値（例えば、暗号化鍵）をローカルに記憶してリカバリすることによって、任意の（例えば、対称または非対称）暗号演算が、補助（例えば、チャレンジもしくはヘルパーデータ）情報を発行または記憶する必要性なしに、行われ得る。本明細書に説明される一実施形態は、分散型鍵生成および閾値暗号の両方を通じた構築を有利に強化するが、どちらも、本発明に係るデバイスのＰＵＦ機能を使用して、値のローカライズされた記憶および取り出しを通じて、任意の暗号演算をサポートする必要がない。
閾値暗号は、典型的には、物理的に別個のノードにわたって演算を分散することを考慮に入れるが、本発明の一実施形態では、閾値暗号は、単一デバイス内に適用されてもよい。例として、デバイスは、例えば、２つのＰＵＦ回路（例えば、リングオシレータ、アービタ、ＳＲＡＭ）を装備してもよいし、同時に（例えば、複数のＣＰＵコアを通して）少なくとも２つの命令を実行する能力を備えてもよい。かかるデバイスの一実施形態は、例えば、２１５，０００個の論理セル、１３メガバイトのブロックランダムアクセスメモリ、および７００個のデジタル信号処理（ＤＳＰ）スライスを装備した、Ｘｉｌｉｎｘ Ａｒｔｉｘ ７フィールドプログラマブルゲートアレイ（ＦＰＧＡ）プラットフォームを備え得る。楕円曲線暗号を利用する実施形態では、例えば、ハードウェア数学的エンジンが、基盤に搭載されたＤＳＰスライスにおいてインスタンス化され得、ＰＵＦ構築が論理セル内に位置付けられ、論理処理コアが、ＰＵＦへの入力および出力を含み、それらを制御するように構築され、デバイスの外部入力および出力が、例えば上記したものなどのアルゴリズムを行う（楕円曲線および他の数学的計算を数学的エンジンに送信する）。ＦＰＧＡは、ＦＰＧＡ構造の別個の領域内に実装される１つ以上のＰＵＦ回路を有してもよい。同時実行が、複数のソフトウェアＣＰＵ、例えば、ＭｉｃｒｏＢｌａｚｅプロセッサをインスタンス化することによって、達成されてもよい。１つのＰＵＦ回路のみを用いる本発明の実施形態は、単純に、複数のＰＵＦ回路に並列にクエリするのではなくて、各共有上で順番に演算を実行する。図２は、ローカル閾値暗号演算をイネーブルにするために２つのＰＵＦ回路を装備したデバイスを例解し、そのデバイスは、例えば、別個のコアが各ＰＵＦを含有する、ＦＰＧＡであってもよい。単一ＰＵＦの潜在的に抽出可能な出力は、次いで、ローカル（２，２）閾値システムを構築することによって不要にされ得、部分ｐｉのそれぞれが、別の参加者として機能する。例えば、各部分は、ランダムチャレンジを選択し、登録アルゴリズム（アルゴリズム３）を実行して非対称鍵対
を生成し、およびその公開登録情報をローカルに記憶し、次いで、分散型鍵生成プロトコル（アルゴリズム４）を一緒に実行し、および決して実際に構築されない私有鍵上で全ての暗号演算を行ってもよい。閾値暗号法が単一デバイス内に適用されるとき、全ての計算が、デバイスの内部で行われるので、登録アルゴリズム（アルゴリズム３）を実行して、非対称鍵対を生成する必要がなくてもよい。
アルゴリズム６は、どのように２重ＰＵＦデバイスが、分散型鍵生成を使用してデバイス内で（２，２）閾値共有を構築することによって閾値手法で暗号演算を計算することができるかを説明する。すなわち、２つの部分は、分散型鍵生成を通してどちらの部分にも既知ではない私有鍵を確立し、および対応する公開鍵
を公開する。デバイスを対象とした全ての演算が、次に、内部協力を通して閾値手法で行われ（各部分が、その共有ｒｉを取り出し、ローカル閾値演算を行い、その結果が組み合わされて、閾値演算
を完了する）、一方で、デバイスの入力／出力挙動は、外部システムに対して変化しないままである。
それゆえ、デバイスに発行されたチャレンジおよび（ある程度、チャレンジの相関関係であり得る）そのレスポンスの間のマッピングに拘束されるのではなくて、マルチＰＵＦデバイスｄｉは、単一静的外部識別情報、
を有することができる。各ＰＵＦコアのチャレンジ−レスポンス機能は、決して、生成または構築されない、デバイスのプライベート識別情報、
の各共有を維持するために使用される。これは、遠隔の敵に対してサイドチャネル攻撃をより困難にさせ、それは、次に、デバイス内で生成された複数の値を同時に観測して解明する必要がある。各部分は、その共有
を取り出し、ローカル閾値演算を行い、共有が、組み合わされて、演算
を完了する。
図７および図８を参照すると、楕円曲線暗号法、２つの共有への鍵の分割、および（２，２）閾値演算を利用する実施形態例のコア操作が説明される。
●登録コマンド１：最初の登録プロセスの間、サーバおよびデバイスは、有限体
および次数ｑの基点Ｇ上で定義された楕円曲線Ｅについて合意する。ここで、ｐは、λビット長である。サーバは、登録コマンドをデバイスに発行する。
●分散型鍵生成２：デバイスは、分散型鍵生成をローカルに行い、（決して、生成または構築されない）マスター私有鍵およびその公開鍵
の共有（ｒ０，ｒ１）を作り出す。共有を一緒に直接的に追加するのではなくて（それは、私有鍵ｒ＝ｒ０＋ｒ１を構築する）、公開鍵は、
を計算することによって形成される。
●ヘルパーデータ生成３：デバイスは、ランダムチャレンジ
を生成する。ここで、
は、連結を表し、各ｃｉブロックは、λビット長である。デバイスは、ファジー抽出を通して、各共有ｒｉをチャレンジｃｉ上のＰＵＦの出力Ｏｉに結び付け、それは、公開ヘルパーｈｉを出力する。ＰＵＦ出力Ｏｉには雑音があるので、将来、チャレンジｃｉについてクエリされるときに、新たな出力
が
を満たすという保証は存在しない。しかしながら、Ｏｉおよび
は、いくらかの距離計量（例えば、ハミング距離）に関してｔ近似であることが想定される。それゆえ、誤り訂正符号が、最大ｔまでの誤りが依然としてＯｉをリカバリするように、ＰＵＦ出力に適用されてもよい。誤り訂正は、各共有ｒｉ上で適用されてもよく、この値は、各ヘルパー値
が、共有ｒｉについての情報を明らかにしないように、チャレンジｃｉについてのＰＵＦＯｉの出力で判読不能にされる。ファジー抽出を通したリカバリの間、
の排他的論理和を計算することは、Ｏｉおよび
がｔ近似である場合は常に、ｒｉを戻す。デバイスは、チャレンジ
およびヘルパーデータ
をローカルに記憶し、それは、そのデバイスが、共有を後でリカバリすることを可能にする。チャレンジおよびヘルパーデータの両方が、公開されること、およびＰＵＦを呼び出さずに共有またはデバイスの私有鍵について何も明らかにしないことに留意する。このプロセスは、アルゴリズム１によって説明される。
●戻される公開鍵４：デバイスは、その公開登録情報
をサーバに戻す。
●登録の記憶５：サーバは、デバイスに固有の（センシティブでない）識別子（例えば、シリアル番号）と共に、デバイスの公開登録情報を記憶する。
●閾値演算クエリ６：デバイスが暗号演算（例えば、暗号解読、デジタル署名生成、ゼロ知識証明認証）を行うことをサーバが望むとき、それは、以下を発行する。
−行われるべき演算のための適切なコマンド
−演算のために必要である任意の補助データＡｕｘ（例えば、暗号解読されるべき暗号文、署名されるべきメッセージ）
●ＰＵＦ取り出し７：デバイスは、そのローカル記憶装置からチャレンジ
およびヘルパーデータ
を読み取る。デバイスは、次いで、各チャレンジブロックｃｉについてＰＵＦをクエリし、出力
をヘルパーブロックｈｉおよび誤り訂正符号と組み合わせて、各共有ブロックｒｉをリカバリする。このプロセスは、アルゴリズム２によって説明される。
●閾値演算８：デバイスは、各共有ｒｉについて閾値演算
を行う。アルゴリズム５は、任意の閾値演算
のためのこのプロセスを説明する。
●組み合わされる閾値演算９：デバイスは、閾値演算を組み合わせて、完全な演算
を形成し、結果をサーバに戻す。
●演算処理１０：サーバは、最終的に、演算のために必要とされる任意の追加的な処理（例えば、ゼロ知識証明の検証）を行う。
共有リフレッシュ
様々な共有リフレッシュプロトコル（例えば、Ｆｒａｎｋｅｌら、「Ｏｐｔｉｍａｌ−Ｒｅｓｉｌｉｅｎｃｅ Ｐｒｏａｃｔｉｖｅ Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、３８ｔｈ Ａｎｎｕａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ、第３８４〜３９３頁、１９９７、Ｈｅｒｚｂｅｒｇら、「Ｐｒｏａｃｔｉｖｅ Ｐｕｂｌｉｃ Ｋｅｙ ａｎｄ Ｓｉｇｎａｔｕｒｅ Ｓｙｓｔｅｍｓ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４ｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｅｃｕｒｉｔｙ、ＣＣＳ’９７、第１００〜１１０頁、ＡＣＭ、１９９７、Ｈｅｒｚｂｅｒｇら、「Ｐｒｏａｃｔｉｖｅ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｏｒ：Ｈｏｗ ｔｏ Ｃｏｐｅ Ｗｉｔｈ Ｐｅｒｐｅｔｕａｌ Ｌｅａｋａｇｅ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ、ＣＲＹＰＴ０ ９５、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第９６３巻、第３３９〜３５２頁、Ｓｐｒｉｎｇｅｒ、１９９５）は、１組のプレーヤ
のそれぞれが、時間周期τにおいて元の秘密ｒのそれらの共有
を新たな共有
にリフレッシュすることを可能にし、そのため、新たな共有の結果として生じる組
が、元の秘密の共有のままとなる。このプロトコルは、マスター秘密ｒの再構築を必要とせず、そのため、移動性のある敵は、共有された秘密をリカバリするために固定時間周期τにおいてｔ個のプレーヤを危険にさらす必要がある。次数（ｔ−１）の多項式
は、それぞれが共有
を有するｎ個の参加者間で共有される秘密
を表現することを想定し、プレーヤｐｊのための暗号化を
としておよびｐｊによる暗号解読を
として表すと、１組のプレーヤ
が、以下のようなプロトコルを使用してｒのそれらの共有をリフレッシュすることができる。
●各プレーヤｐｉは、δｉ（０）＝０であるように、次数（ｔ−１）の新たな多項式を定義する。
ここで、セット
が、
からランダムに選ばれる。
●各プレーヤｐｉは、以下のセットを計算し、
検証可能な秘密共有
およびそれらの署名
をブロードキャストする。
●各プレーヤｐｉは、
をリカバリし、
を検証する。
●最終的に、各プレーヤｐｉは、以下のように時間周期（τ）からの彼らの共有を更新する。
それゆえ、リフレッシュされた組の共有
は、マスター私有鍵
の共有のままとなり、更に、時間周期τからのｔ−１以下の共有の知識が、時間周期τ＋１において役に立たない。
アルゴリズム７に略述されるように、参加者は、共有の組
がマスター私有鍵
の共有のままとなるように、時間周期τにおける彼らの共有
を次の時間周期における新たな共有
に更新することができる。
ハードウェアデバイスは、図８における共有リフレッシュ１１においてアルゴリズム７を行い、次の時間周期τ＋１のために新たな共有
を生成する。ＰＵＦリフレッシュおよび記憶１２において、ハードウェアデバイスは、新たなチャレンジ
を生成し、それは、次の時間周期のためにチャレンジ−ヘルパー対をリフレッシュする。ハードウェアデバイスは、新たなチャレンジを使用して、更新された共有
を記憶する。アルゴリズム５および６は、閾値共有のみならずチャレンジ−ヘルパー対の両方をリフレッシュするように修正され、アルゴリズム８および９は、それぞれ、その修正を反映する。
例えば、図１に示されるような単一ＰＵＦ実施形態を参照すると、共有更新が、任意選択的に、準備段階（アルゴリズム１０）および適用段階（アルゴリズム１１）に論理的に分配されてもよい。準備の間、各参加者は、そのランダム多項式を生成し、更新のその部分を他の参加者に分散する。全ての参加者が共有更新のそれらの部分をブロードキャストした後、準備段階が完了する。（ブロードキャストは、準備が、例えばＦＰＧＡなどのような単一デバイス内に適用される場合、省略されてもよい）。
次に、各参加者は、他の参加者から受信した更新情報を検証し、アルゴリズム１１に規定されるように、更新をその共有に適用する。
ある共有についての各閾値演算は、他の共有とは独立して行われ得るので、デバイスは、１回に１つの共有のみをリカバリする必要がある。このプロセスは、アルゴリズム１２に例解される。コマンド
およびその関連付けられた補助情報Ａｕｘを受信した後、デバイスは、最初に、アルゴリズム１０を行って、共有更新について準備する。次に、デバイスは、各共有について閾値演算を反復的に行う。共有は、不揮発性メモリからチャレンジ−ヘルパー対を読み取ることによって、およびＰＵＦを使用して対応する共有を再生成することによって、リカバリされる。共有について閾値演算を行った後、共有更新が、アルゴリズム１１を使用して適用され、それは、新たな時間周期（τ＋１）について更新された共有を生成する。各共有について閾値演算を計算した後、閾値演算が組み合わされ、結果
を形成し、その結果は、サーバに戻される。
一実施形態では、（２，２）閾値システムが、デバイスの内部に構築される。アルゴリズム１３は、より一般的なアルゴリズム１２の単一ＰＵＦ（２，２）閾値構築の例を例解する。デバイスは、共有セット｛ｒ０，ｒ１｝を有し、かつ各共有について閾値演算を反復的に計算して、セット
を作り出す。一旦、閾値演算の両方が完了し、かつ共有が更新および記憶されると、２つの閾値演算が、最終出力
に組み合わされる。
アルゴリズム１３のフロー、より一般的なアルゴリズム１２の特定の単一ＰＵＦ（２，２）閾値構築が、図９に例解される。ステップ１の前に、共有更新準備（アルゴリズム１０）が行われる。ステップ１において、第１の共有
が取り出され、その対応するローカル閾値演算が行われる。共有更新（アルゴリズム１１）が、次いで、
に適用され、次の時間周期に
を生じる。更新された共有が、次いで、新たなランダムチャレンジ
を使用して記憶され、それは、対応するヘルパーデータ
を生成し、それは、更新された共有が、ＰＵＦを使用してリカバリされることを可能にする。同じプロセスが、共有
のためにステップ２において続けられる。最終的に、組み合わされる出力
が、各共有について行われた２つのローカルな閾値演算を組み合わせることによって構築される。
デバイスは、ある一定の識別情報
を有するが、
を必要とする全ての演算
が、
を決して再構築せずに、かつ各演算が実行された後に変化する値を伴って、行われる。各部分は、ＰＵＦ−記憶およびＰＵＦ−取り出しアルゴリズムを使用して、その共有を維持するので、（チャレンジ、ヘルパー）対は、ＰＵＦ−記憶が実行されるときに、各演算後に更新される。各共有は、新たな時間周期τ＋１のためにリフレッシュされ、および新たなランダムチャレンジ
を生成することによって、かつ更新されたヘルパーをヘルパー
に設定することによって、記憶される。共有再生成、閾値演算、および共有記憶が（同時にではなくて）連続的に起こるように閾値演算をずらすことは、２つ以上の更新された共有の同時のリカバリを排除する。１つの共有が存在する間のいかなる改ざんも、（改ざんが、誤り訂正限定を超えるＰＵＦ出力を強要することを想定すると）別の共有のリカバリを妨げることになり、その場合には、デバイスは、その私有鍵について演算を行うことができない。
したがって、かかる実施形態に対してサイドチャネル攻撃を適用する敵は、リフレッシュメントの期間を超えることができない観測の期間からｔ個以上の共有を抽出する必要がある。換言すれば、時間周期τからの任意の共有は、時間周期τ＋１において役に立たないので、敵は、所与の時間周期τにおいてｔ個のデバイスを危険にさらす必要がある。それゆえ、サイドチャネル攻撃の難しさは、（各演算後でさえも）より頻繁に更新することによって増大させることができる。（リフレッシュ頻度の増大もまた、複数のＰＵＦデバイス実施形態へのサイドチャネル攻撃が内包する難しさを増し得、それにおいて、遠隔の敵が、デバイス内で同時に生成された複数のＰＵＦ値を観測して解明する必要がある）。
また、固定されたチャレンジ／ヘルパーおよびレスポンスを使用するシステムの寿命は、老化に起因するハードウェアの誤り率の増加に直接的に制限されるのに対して、各時間周期における対を継続的に更新することによって、誤り率は、名目上ゼロにリセットすることができる。すなわち、各時間周期τの間に対
を定期的にリフレッシュすることは、ＰＵＦ出力をハードウェアの現在の状態に結び付け、前の時間周期からのハードウェアドリフトを取り除く。その点について、図１１は、アルゴリズム２：ＰＵＦ−取り出しを使用して時間τ=０から、元のチャレンジ−ヘルパー対
を使用して時間τ＝１においてその共有をリカバリするデバイスを例解する。デバイスは、次いで、内部で、時間周期τ＝１のために新たなチャレンジ−ヘルパー対
を生成する。共有は、次いで、τ=１のための新たなチャレンジ−ヘルパー対を使用して、アルゴリズム１：ＰＵＦ−記憶を実行することによって記憶される。これは、更新されたチャレンジ−ヘルパー対をハードウェアの現在の状態に結び付け、それは、時間周期
の間に発生されるハードウェア老化を排除する。それゆえ、時間τ＝１におけるＰＵＦ出力におけるビット誤りの予想される数は、ハードウェアが率ｐに従って老化し続けるにもかかわらず、ゼロである。
図１２に見られ得るように、各ＰＵＦコアの内部チャレンジ−ヘルパー対を定期的に更新するこのプロセスを繰り返すことによって、最大ＰＵＦ出力誤りは、束縛され得、および任意に、リフレッシュ繰り返し周期を調節することによって小さくさせることができる。それゆえ、ＰＵＦマッピングにおける徐々のシフトは、取るに足らない。ハードウェアがその間の時間に致命的に老化しない限り、シフトは、記憶されたチャレンジおよびヘルパーデータに継続的に織り込まれる。
動的構成員数
この構築における共有の動的性質はまた、参加者が、（ｔ，ｎ）閾値システムにおける１組の参加者に加わってもよいかまたはそれから去ってもよいように、あるグループに参加する参加者の数ｎが、動的に変動され得る実施形態を許可する。この場合では、最大ｎ−ｔまでの参加者が、単に、次の共有リフレッシュプロトコルからそれらを除外することによって、その組
から除かれ得る。参加者ｐｊを１組の参加者に加えるために、それぞれの現在の参加者ｐｉは、それらの共有更新多項式
から余分な共有ｕｉｊを生成する。
（（ｔ，ｎ）閾値システムにおいて）動的構成員数およびマルチＰＵＦデバイス（複数可）を利用する一部の実施形態では、デバイス（複数可）が、ローカル自己試験を行って、それがハードウェア老化に起因して、その共有をもはやリカバリすることができない点に近づかないことを確実にするように構成されてもよい。２次閾値、
（誤り訂正によって訂正され得る誤りの最大数）は、
誤りがＰＵＦ出力において観測されるときに、遷移プロトコルが始動されるように、デバイスのために設定され得る。遷移プロトコルは、デバイスｄｉが、
をリカバリすることなく、その私有鍵
について演算を行う能力を異なるデバイス
に移すことができる。２重ＰＵＦデバイスの例では、デバイスｄｉが危機的なハードウェア老化を検出するとき（例えば、ＰＵＦ誤りが二次的閾値
を超えるとき）、それは、共有リフレッシュプロトコルを実行し、およびｎを２→４に増加させる。デバイスｄｉは、次に、１組の共有
を所有し、ｄｊが有効であることを検証した後に
をｄｊに非公式に送信する（例えば、ｄｊの登録トークンについて信頼されたソースからの署名を検証し、およびｄｊにゼロ知識証明を行わせる）。一旦、ｄｊがセット
を受信したら、ｄｉおよびｄｊの両方がｄｉとして機能し得、万一、ｄｉのハードウェア故障の場合には、それは、ｄｊと容易に交換され得る。
内部自己試験手順は、複数のＰＵＦでイネーブルにされるデバイスがより大きなシステム（例えば、以下に記述されるように処理センター）の一部として使用される設定に容易に拡張されてもよい。１つのＰＵＦでイネーブルにされるデバイスが、その共有をリカバリすることに失敗すると、それは、新たなデバイスと交換することができる。残りのおよび正しく機能しているＰＵＦでイネーブルにされるデバイスは、共有更新アルゴリズムを実行し、同様に新たなデバイス共有を送信することによってｎを増加させる。これは、失敗しているデバイスが、広域（ｔ，ｎ）閾値システムの共有で直ちに交換およびプロビジョニングされ得るように、複数のＰＵＦでイネーブルにされるデバイスから成るシステムが、単一エンティティとして機能し続けることを可能にする。
閾値対称演算
非対称演算に加えて、対称暗号演算がまた、閾値手法で行われてもよい（例えば、Ｎｉｋｏｖａら、「Ｔｈｒｅｓｈｏｌｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ Ａｇａｉｎｓｔ Ｓｉｄｅ−Ｃｈａｎｎｅｌ Ａｔｔａｃｋｓ ａｎｄ Ｇｌｉｔｃｈｅｓ」、Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｅｃｕｒｉｔｙ、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第４３０７巻、第５２９〜５４５頁、Ｓｐｒｉｎｇｅｒ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ、２００６、Ｍｏｒａｄｉら、「Ｐｕｓｈｉｎｇ ｔｈｅ Ｌｉｍｉｔｓ：Ａ Ｖｅｒｙ Ｃｏｍｐａｃｔ ａｎｄ ａ Ｔｈｒｅｓｈｏｌｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＡＥＳ」、Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯＣＲＹＰＴ ２０１１、Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅの第６６３２巻、第６９〜８８頁、Ｓｐｒｉｎｇｅｒ Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ、２０１１、Ｂｉｌｇｉｎら、「Ａ Ｍｏｒｅ Ｅｆｆｉｃｉｅｎｔ ＡＥＳ Ｔｈｒｅｓｈｏｌｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」、Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ、Ｒｅｐｏｒｔ ２０１３／６９７、２０１３）。これは、全ての暗号演算、非対称および対称性が、私有鍵ではなくて閾値共有について、行われることを可能にする。非対称私有鍵の共有について説明されたリフレッシュプロセスのように、対称鍵の共有もまた、リフレッシュされてもよい。
再構成可能なＰＵＦ
一実施形態では、再構成可能なＰＵＦがまた、使用されてもよい。（例えば、Ｍａｊｚｏｏｂｉら、「Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ Ｓｅｃｕｒｅ Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ ＰＵＦｓ」、ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ Ｔｅｃｈｎｏｌｏｇｙ Ｓｙｓｔｅｍｓ、第２巻、Ｎｏ．１：５：１〜５：３３、２００９、Ｋｕｒｓａｗｅら、「Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ − Ｅｎａｂｌｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｆｏｒ ｔａｍｐｅｒ−ｒｅｓｉｓｔａｎｔ ｓｔｏｒａｇｅ」、Ｈａｒｄｗａｒｅ−Ｏｒｉｅｎｔｅｄ Ｓｅｃｕｒｉｔｙ ａｎｄ Ｔｒｕｓｔ、２００９．ＨＯＳＴ’０９．ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ、第２２〜２９頁、２００９、Ｋａｔｚｅｎｂｅｉｓｓｅｒら、「Ｒｅｃｙｃｌａｂｌｅ ＰＵＦｓ： ｌｏｇｉｃａｌｌｙ ｒｅｃｏｎｆｉｇｕｒａｂｌｅ ＰＵＦｓ」、Ｊｏｕｒｎａｌ ｏｆ Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ、第１巻、Ｎｏ．３：１７７〜１８６、２０１１、Ｅｉｃｈｈｏｒｎら、「Ｌｏｇｉｃａｌｌｙ Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ ＰＵＦｓ：Ｍｅｍｏｒｙ−ｂａｓｅｄ Ｓｅｃｕｒｅ Ｋｅｙ Ｓｔｏｒａｇｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｉｘｔｈ ＡＣＭ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｃａｌａｂｌｅ Ｔｒｕｓｔｅｄ Ｃｏｍｐｕｔｉｎｇ、ＳＴＣ’１１、第５９〜６４頁、ＡＣＭ、２０１１を参照）再構成可能なＰＵＦは、新たなＰＵＦマッピングが生成されるように、そのパラメータを変えることができる。この再構成は、可逆的または不可逆的であってもよいし、永久的であってもよい。
一例として、デバイスは、不可逆再構成プロセスを有する２つの再構成可能なＰＵＦ回路（例えば、ＰＵＦ−Ａ、ＰＵＦ−Ｂ）、および利用される２−２閾値共有を備えることができる。各共有が、ＰＵＦ−Ａを使用してリカバリされ、かつリフレッシュされた後、それは、ＰＵＦ−Ｂを使用して記憶のためにチャレンジ−ヘルパー対に変えられる。一旦、リフレッシュされた共有の両方がＰＵＦ−Ｂを使用して記憶されたら、再構成プロセスは、ＰＵＦ−Ａが、次に、新たなＰＵＦマッピングを提示するように、ＰＵＦ−Ａに適用される。次に共有がリカバリされる時、同じ手順が、リカバリのためにＰＵＦ−ＢおよびコミットメントのためにＰＵＦ−Ａを使用して行われる。
別の例として、デバイスは、可逆構成プロセスを有する単一の再構成可能なＰＵＦ回路、および利用される２−２閾値共有を備えてもよい。ＰＵＦ構成は、パラメータによって制御され、そのパラメータは、デバイス上にローカルに記憶されてもよい。パラメータａを使用して、１つの共有をリカバリすると、新たなランダムパラメータｂが選ばれ、ＰＵＦが再構成され、リフレッシュされた共有が、パラメータｂで構成されたＰＵＦを使用して記憶のためにチャレンジ−ヘルパー対に変えられる。ＰＵＦは、次いで、第２の共有をリカバリするためにパラメータａを使用して再構成され、その第２の共有は、その後、リフレッシュされ、およびパラメータｂで構成されたＰＵＦを使用して記憶のためにチャレンジ−ヘルパー対に変えられる。この際、元のＰＵＦパラメータａが削除され、次のラウンドは、新たなランダムパラメータｃを選択して、パラメータｂを交換する。
スケーラビリティ
標準ＰＵＦプロトコルは、元来、特定のハードウェアデバイスに結び付けられ（実際、これは、それらの目標であり）、それは、システムを容易にスケールして任意の処理負荷をサポートする能力に制約を課し得る。図１３は、プライベート情報を動的に再生成するために利用されるＰＵＦを用いて、任意に大きな処理負荷をサポートすることをスケールするように設計された処理センターを例解する。分散型鍵生成を通して秘密の（ｔ，ｎ）共有を構築することによって、システムのための私有鍵は、決して構築または記憶されない。しかしながら、任意のｔ個のＰＵＦは、処理センターに代わって、暗号演算を行うように協力することができる。例えば、ｔ=７である場合、ＰＵＦの各列は、処理センターの代わりに、暗号演算を共同で行うことができ、（列Ａ〜Ｄを使用する）４つの要求が、同時に完了され得る。それゆえ、スケーラブルなハードウェアに本来備わる識別情報ソリューションが設計され得、それにおいて、ローカルハードウェアに本来備わる識別情報を有する（例えば、ＰＵＦを装備した）ハードウェア構成要素のグループが、全体としてそれらのグループのための固有のハードウェアに本来備わる識別情報を形成するように協力的に機能することができる。発明の本実施形態は、システムを構成するデバイスが、ローカルに閾値暗号を実装することを必要としない。むしろ、各デバイスは、アルゴリズム３を実行し、かつそのローカル公開鍵
を公開してもよい。次いで、（ｔ，ｎ）共有が、プライベート通信のために各デバイスのローカル公開鍵を使用して、システムのためにセットアップされる。
図１４は、１組の構成要素識別情報から生成されるマスター識別情報を例解する。（ｎ，ｎ）閾値システムは、マスター識別情報を使用して暗号演算を行うために、全ての構成要素がそれらの共有をリカバリすることができることを必要とするように構築されてもよい。発明の別の実施形態では、（ｔ，ｎ）閾値システムは、危機的な構成要素の全ておよび非危機的な構成要素の一部が、マスター識別情報を使用して暗号演算を行うために、それらの共有をリカバリすることができることを必要とするように構築されてもよい。
性能
（誤り訂正を必要としなかった）単一模擬３８４ビットリングオシレータＰＵＦ、およびＮＩＳＴ楕円曲線Ｐ−３８４上で定義される（２，２）閾値システムを有する実施形態について性能試験を行った。各共有についての演算を、複数のＰＵＦ実施形態において行われ得るように同時にではなくて、順番に行った。試験は、値の記憶および取り出し、ならびにデバイスおよびサーバ間の通信のために必要な合計時間を測定した。サーバは、８個のコア３．１ＧＨｚプロセッサおよび１６ＧＢのＲＡＭ、ならびに１１５２００ボー接続上で１００ＭＨｚにおいて実行するＸｉｌｉｎｘ Ａｒｔｉｘ ７ＦＰＧＡ上に実装されるデバイスサイドアルゴリズムを装備した。ここで、全ての演算は、ＮＩＳＴ Ｐ−３８４曲線上で行った。表１は、１０００回の試行にわたるプロトコル毎の平均時間を報告する。

Claims (18)

  1. 認証システムで使用のための認証可能デバイスであって、
    ａ）物理的複製不可能関数（「ＰＵＦ」）入力およびＰＵＦ出力を有し、かつチャレンジの入力に応答して、前記ＰＵＦおよび前記チャレンジに特有の出力値を生成するように構築されたＰＵＦデバイスと、
    ｂ）前記ＰＵＦ出力に接続されるプロセッサ入力を有し、かつ前記ＰＵＦ入力に接続されるプロセッサ出力を有するプロセッサであって、前記プロセッサ出力経由での前記ＰＵＦ入力への前記チャレンジの発行を制御して、所望の暗号化出力のインスタンスに関して以下の一連のステップであって、
    ｉ）前記プロセッサ出力経由で前記ＰＵＦ入力にチャレンジを発行し、前記ＰＵＦ出力から前記プロセッサ入力経由で対応する出力を受信し、
    ｉｉ）ステップｉにおいて前記ＰＵＦ出力から受信された前記出力を使用して、前記認証可能デバイスの内部で、ステップｉにおいて前記ＰＵＦ出力から受信された前記出力と関連付けられた私有鍵または秘密の共有をリカバリし、かつ
    ｉｉｉ）前記認証可能デバイスの内部で、ステップｉｉにおいてリカバリされた前記共有上で暗号演算を行い、
    前記私有鍵または秘密が、共有に分配され、それによって、所望の暗号化出力の所与のインスタンスのために、演算が前記私有鍵または秘密を使用して行われることを共に可能にする異なる共有が、ステップｉｉにおいてリカバリされる、一連のステップを複数回実行するように構成されたプロセッサと、を備える、認証可能デバイス。
  2. 前記プロセッサが、共有リフレッシュ手順を行って、前記私有鍵または秘密の共有をリフレッシュするように更に構成される、請求項１に記載の認証可能デバイス。
  3. 前記プロセッサが、ステップｉｉｉにおいて行われる複数の暗号演算を組み合わせて、暗号化出力を生じるように更に構成される、請求項４に記載の認証可能デバイス。
  4. 前記プロセッサが、ラグランジュ多項式補間を行うように更に構成される、請求項４に記載の認証可能デバイス。
  5. 前記プロセッサが、楕円曲線暗号化を行うように更に構成される、請求項４に記載の認証可能デバイス。
  6. 前記プロセッサが、分散型鍵生成を行うように更に構成される、請求項４に記載の認証可能デバイス。
  7. 前記プロセッサが、２つ以上の論理コアを備え、前記プロセッサは、各論理コアが、他の論理コアでステップｉ〜ｉｉｉを同時に実行することができるように構成される、請求項１に記載の認証可能デバイス。
  8. 前記プロセッサが、前記共有リフレッシュ手順を準備段階および適用段階に分割するように更に構成される、請求項４に記載の認証可能デバイス。
  9. 前記プロセッサが、共有更新情報の生成を含む準備段階を行い、かつ１つ以上の共有に対する前記共有更新情報の適用を含む適用段階を行うように更に構成される、請求項１２に記載の認証可能デバイス。
  10. 前記プロセッサは、１つの共有リフレッシュ手順のみが一度に行われるように、前記準備および適用段階を行うように更に構成される、請求項１３に記載の認証可能デバイス。
  11. 前記デバイスが、再構成可能なＰＵＦを含む、請求項１４に記載の認証可能デバイス。
  12. 前記プロセッサが、ステップｉｉｉにおいて行われる複数の暗号演算を組み合わせて、暗号化出力を生じるように更に構成される、請求項１に記載の認証可能デバイス。
  13. ステップｉｉにおいてリカバリされた前記共有が、ヘルパーによって、ステップｉにおいて前記ＰＵＦ出力から受信された前記出力と関連付けられる、請求項１に記載の認証可能デバイス。
  14. 前記ヘルパーが、前記デバイス上に記憶される、請求項１３に記載の認証可能デバイス。
  15. 前記プロセッサが、所望の暗号化出力の所与のインスタンスのために、それがステップｉを実行する前記複数回のそれぞれにおいて、異なるチャレンジを発行するように構成される、請求項１〜１４のいずれかに記載の認証可能デバイス。
  16. 前記プロセッサが、ゼロ知識証明認証プロトコルを行うように更に構成される、請求項１〜１４のいずれかに記載の認証可能デバイス。
  17. 前記デバイスが、２つ以上のＰＵＦを備える、請求項１〜１４のいずれかに記載の認証可能デバイス。
  18. 前記プロセッサが、２つ以上の論理コアを備える、請求項１〜１４のいずれかに記載の認証可能デバイス。
JP2017546818A 2015-03-05 2016-03-07 物理的複製不可能関数および閾値暗号化を含む認証システムならびにデバイス Pending JP2018507658A (ja)

Applications Claiming Priority (9)

Application Number Priority Date Filing Date Title
US201562128920P 2015-03-05 2015-03-05
US62/128,920 2015-03-05
US201562150586P 2015-04-21 2015-04-21
US62/150,586 2015-04-21
US14/704,914 2015-05-05
US14/704,914 US10432409B2 (en) 2014-05-05 2015-05-05 Authentication system and device including physical unclonable function and threshold cryptography
US14/746,054 US9946858B2 (en) 2014-05-05 2015-06-22 Authentication system and device including physical unclonable function and threshold cryptography
US14/746,054 2015-06-22
PCT/US2016/021275 WO2016141386A1 (en) 2015-03-05 2016-03-07 Authentication system and device including physical unclonable function and threshold cryptography

Publications (1)

Publication Number Publication Date
JP2018507658A true JP2018507658A (ja) 2018-03-15

Family

ID=60514882

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2017546818A Pending JP2018507658A (ja) 2015-03-05 2016-03-07 物理的複製不可能関数および閾値暗号化を含む認証システムならびにデバイス

Country Status (3)

Country Link
EP (1) EP3265943B1 (ja)
JP (1) JP2018507658A (ja)
CN (1) CN107615285B (ja)

Families Citing this family (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110401615B (zh) * 2018-04-24 2021-11-26 广东工业大学 一种身份认证方法、装置、设备、系统及可读存储介质
CN108681441B (zh) * 2018-04-25 2021-06-01 东南大学 一种基于br-puf的随机数生成器
CN110049002B (zh) * 2019-03-01 2021-07-27 中国电子科技集团公司第三十研究所 一种基于PUF的IPSec认证方法
KR102835077B1 (ko) * 2019-11-01 2025-07-16 삼성전자주식회사 물리적 복제 방지 기능 셀들을 포함하는 보안 장치, 보안 장치의 동작 방법 및 물리적 복제 방지 기능 셀 장치의 동작 방법
CN111125782B (zh) * 2019-12-24 2022-12-09 兴唐通信科技有限公司 一种不可克隆芯片id的验证方法及系统
US11501023B2 (en) * 2020-04-30 2022-11-15 International Business Machines Corporation Secure chip identification using resistive processing unit as a physically unclonable function
CN112800438B (zh) * 2020-05-22 2024-01-16 陕西师范大学 在标准模型下计算安全的抗内存泄漏的多级秘密共享方法
CN111740965B (zh) * 2020-06-09 2022-08-19 河海大学常州校区 一种基于物理不可克隆方程的物联网设备认证方法
CN113206741B (zh) * 2021-03-25 2022-03-25 武汉飞思灵微电子技术有限公司 一种基于强puf的抗机器学习安全认证方法及装置
CN113114475B (zh) * 2021-04-23 2022-07-05 湖北工业大学 基于比特自检puf身份认证系统及协议
US12126740B2 (en) * 2021-06-25 2024-10-22 Arizona Board Of Regents On Behalf Of Northern Arizona University Systems and methods using search engines to generate cryptographic keys from erratic physical unclonable functions
EP4423964B1 (en) 2021-10-26 2025-10-01 Assa Abloy Ab Authenticating an electronic device
US20240388421A1 (en) * 2021-10-26 2024-11-21 Assa Abloy Ab Hardware integrity control of an electronic device
CN114969851B (zh) * 2022-05-31 2024-02-23 浪潮电子信息产业股份有限公司 一种基于fpga的数据处理方法、装置、设备及介质
CN115378616B (zh) * 2022-10-21 2023-01-10 三未信安科技股份有限公司 一种基于Ed25519的门限签名方法
CN115580488B (zh) * 2022-11-23 2023-03-03 西华大学 基于区块链和物理不可克隆函数的车载网消息认证方法

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060023887A1 (en) * 2004-04-02 2006-02-02 Agrawal Dharma P Threshold and identity-based key management and authentication for wireless ad hoc networks
US20100176920A1 (en) * 2007-06-14 2010-07-15 Intrinsic Id Bv Method and device for providing digital security
JP2012503814A (ja) * 2008-09-26 2012-02-09 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ デバイス及びユーザの認証
JP2012509039A (ja) * 2008-11-17 2012-04-12 イントリンシツク・イー・デー・ベー・ベー 分散ｐｕｆ
WO2014184899A1 (ja) * 2013-05-15 2014-11-20 三菱電機株式会社 機器真贋判定システムおよび機器真贋判定方法
US8918647B1 (en) * 2013-11-10 2014-12-23 Sypris Electronics, Llc Authentication system

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7840803B2 (en) * 2002-04-16 2010-11-23 Massachusetts Institute Of Technology Authentication of integrated circuits
JP5423088B2 (ja) * 2009-03-25 2014-02-19 ソニー株式会社 集積回路、暗号通信装置、暗号通信システム、情報処理方法、及び暗号通信方法
CN106227693B (zh) * 2010-10-15 2019-06-04 相干逻辑公司 多处理器系统中的通信禁用
US9083323B2 (en) * 2013-02-11 2015-07-14 Qualcomm Incorporated Integrated circuit identification and dependability verification using ring oscillator based physical unclonable function and age detection circuitry
CN103391199B (zh) * 2013-07-25 2017-02-08 南京邮电大学 一种基于puf的rfid认证方法和系统

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060023887A1 (en) * 2004-04-02 2006-02-02 Agrawal Dharma P Threshold and identity-based key management and authentication for wireless ad hoc networks
US20100176920A1 (en) * 2007-06-14 2010-07-15 Intrinsic Id Bv Method and device for providing digital security
JP2012503814A (ja) * 2008-09-26 2012-02-09 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ デバイス及びユーザの認証
JP2012509039A (ja) * 2008-11-17 2012-04-12 イントリンシツク・イー・デー・ベー・ベー 分散ｐｕｆ
WO2014184899A1 (ja) * 2013-05-15 2014-11-20 三菱電機株式会社 機器真贋判定システムおよび機器真贋判定方法
US8918647B1 (en) * 2013-11-10 2014-12-23 Sypris Electronics, Llc Authentication system

Also Published As

Publication number Publication date
EP3265943A4 (en) 2018-10-31
EP3265943A1 (en) 2018-01-10
CN107615285A (zh) 2018-01-19
EP3265943B1 (en) 2021-04-28
CN107615285B (zh) 2020-08-11

Similar Documents

Publication Publication Date Title
US10931467B2 (en) Authentication system and device including physical unclonable function and threshold cryptography
US9946858B2 (en) Authentication system and device including physical unclonable function and threshold cryptography
US9806718B2 (en) Authenticatable device with reconfigurable physical unclonable functions
EP3265943B1 (en) Authentication system and device including physical unclonable function and threshold cryptography
Das et al. Spurt: Scalable distributed randomness beacon with transparent setup
US9998445B2 (en) Authentication system
EP3146670B1 (en) Network authentication system with dynamic key generation
Groth et al. Cryptography in the multi-string model
US10958452B2 (en) System and device including reconfigurable physical unclonable functions and threshold cryptography
Bernstein et al. Post-quantum cryptography---dealing with the fallout of physics success
Sen Homomorphic encryption-theory and application
Hong et al. Constant-round privacy preserving multiset union
Das et al. Modular lattice signatures, revisited
Karl et al. Cryptonite: A framework for flexible time-series secure aggregation with online fault tolerance
Loftus et al. On cca-secure fully homomorphic encryption
Rahma et al. Public key cipher with signature based on diffie-hellman and the magic square problem
Tentu et al. Efficient verifiable multi-secret sharing based on YCH scheme
Lee Securely Computing Threshold Variants of Signature Schemes (and More!)
Wikström On the security of mix-nets and related problems
Dai et al. Memory leakage-resilient secret sharing schemes
Zhou et al. A simple provably secure AKE from the LWE problem
Peng Failure of a mix network
Dent et al. Signcryption schemes based on the RSA problem
Hamilton First Time Authentication for Airborne Networks (FAAN)
Peng Modification and Optimisation of an ElGamal-Based PVSS Scheme

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20180705

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20190228

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20190401

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20190701

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20190704

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20200106