(57)【要約】  暗号鍵を決定するように配置構成されている電子暗号デバイス（１００）である。暗号デバイスは、物理的複製不可能関数（ＰＵＦ）（１１０）、バイアス除去ユニット（１２０）、および鍵再構築ユニット（１５０）を有する。ＰＵＦは、登録フェーズでは第１のノイズのあるビット列（１１２）を、再構築フェーズでは第２のノイズのあるビット列（１１４）を生成するように配置構成される。バイアス除去ユニット（１２０）は、登録フェーズにおいて第１のノイズのあるビット列からバイアス除去データ（１４２）を決定するように配置構成される。バイアス除去データは、第１のノイズのあるビット列内のビットを保持または破棄としてマークする。鍵再構築ユニット（１５０）は、バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定するように配置構成され、暗号鍵はバイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している。
2018504827.tif 000002
【特許請求の範囲】
【請求項１】
暗号鍵を決定するように配置構成されている電子暗号デバイス（１００）であって、暗号デバイスは登録フェーズおよびその後の再構築フェーズのために配置構成され、暗号デバイスは
−  登録フェーズでは第１のノイズのあるビット列（１１２）を、再構築フェーズでは第２のノイズのあるビット列（１１４）を生成するように配置構成されている物理的複製不可能関数（ＰＵＦ）（１１０）と、
−  第１のノイズのあるビット列内のバイアスを低減するように配置構成されているバイアス除去ユニット（１２０）であって、バイアス除去ユニットは登録フェーズにおいて第１のノイズのあるビット列からバイアス除去データ（１４２）を決定するように配置構成され、バイアス除去データは第１のノイズのあるビット列内のビットを保持または破棄としてマークする、バイアス除去ユニット（１２０）と、
−  バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定するように配置構成されている鍵再構築ユニット（１５０）であって、暗号鍵はバイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している、鍵再構築ユニット（１５０）とを備える、電子暗号デバイス（１００）。
【請求項２】
第１および第２のノイズのあるビット列が、それぞれ、第１および第２の一連のビットペアに区分され、
−  バイアス除去ユニットが第１の一連のビットペア内の不等ビットペアを識別するように配置構成され、不等ビットペアが２つの不等ビットを含み、等ビットペアが２つの等ビットを含み、バイアス除去データが第１のノイズのあるビット列内の不等ビットペアを保持としてマークする、請求項１に記載の電子暗号デバイス（１００）。
【請求項３】
バイアス除去ユニットが一連のビットペア内の第１および第２の等ビットペアを識別するように配置構成され、第１の等ビットペアが第２の等ビットペアの逆であり、バイアス除去データが少なくとも第１の等ビットペアを保持としてマークする、請求項２に記載の電子暗号デバイス（１００）。
【請求項４】
バイアス除去ユニットが一連のビットペア内の等ビットペアの第１および第２のセットを識別するように配置構成され、第１および第２のセットが同じサイズを有し、第１のセット内のすべての等ビットペアが同じであり、第２のセット内のすべての等ビットペアが同じであり、第１のセットのビットペアが第２のセット内のビットペアの逆であり、バイアス除去データが第１のセットの少なくとも等ビットペアを保持としてマークする、請求項２に記載の電子暗号デバイス（１００）。
【請求項５】
保持としてバイアス除去情報によってマークされている第１のビット列内のビットが、第１のノイズのあるビット列よりも低いバイアスを有する、請求項１から４のいずれか一項に記載の電子暗号デバイス（１００）。
【請求項６】
−  第１の誤り訂正符号から１つまたは複数の第１の符号語を取得し、登録フェーズにおいて１つまたは複数の符号語から保持としてバイアス除去データによってマークされている第１のノイズのあるビット列内のビットに対するノイズ低減データ（１４４）を決定するように配置構成されているノイズ低減ユニット（１３０）と、
−  再構築フェーズにおいてバイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットにノイズ低減データを適用し、１つまたは複数の第１の符号語およびノイズを決定するように配置構成されている正規化器（１５２）と、
−  前記１つまたは複数のノイズのある第１の符号語を訂正するように配置構成されている誤り訂正器（１５４）とを備える、請求項１から５のいずれか一項に記載の電子暗号デバイス（１００）。
【請求項７】
ノイズ低減データがバイアス除去情報によって保持としてマークされている第１のビット列内のビットと１つまたは複数の符号語との間の差を含み、ノイズ低減データが、バイアス除去情報によって破棄としてマークされている第１のビット列内のビットと１つまたは複数の符号語内のビットとの間の差を含まない、請求項６に記載の電子暗号デバイス（１００）。
【請求項８】
１つまたは複数の符号語内のビットが、第１のノイズのあるビット列内のビットに対応し、ノイズ低減データがバイアス除去情報によって保持としてマークされている第１のビット列内のビットと第１のノイズのあるビット列内の保持ビットに対応する１つまたは複数の符号語内のビットとの間の差を含む、請求項６または７に記載の電子暗号デバイス（１００）。
【請求項９】
第１のノイズのあるビット列内の保持ビットに対応する１つまたは複数の符号語内のビットが、それぞれ１つまたは複数の符号語および第１のノイズのあるビット列内の同じインデックスを有する、請求項８に記載の電子暗号デバイス（１００）。
【請求項１０】
バイアス除去ユニットが、第１のノイズのあるビット列内のすべての不等ビットペアを保持としてマークし、バイアス除去データにおいてすべての等ビットペアを破棄としてマークするように配置構成される、請求項８または請求項１から９の他のいずれか一項に記載の電子暗号デバイス（１００）。
【請求項１１】
一連のビットペア内の第２の等ビットペアが、第１および第２のビットペアが１つまたは複数の符号語のうちの同じ符号語との差において使用される場合にバイアス除去データによって保持として、および他の場合には破棄としてマークされる請求項３および６に記載の電子暗号デバイス（１００）。
【請求項１２】
バイアス除去ユニットが、第１および第２の等ビットペアが１つまたは複数の符号語の同じ符号語との差で使用されるように第１の一連のビットペアの第１の転置を決定するように配置構成され、鍵再構築ユニットが第１の転置を第２の一連のビットペアに適用するように配置構成される請求項３および６に記載の電子暗号デバイス（１００）。
【請求項１３】
ノイズ低減ユニットが、第２の誤り訂正符号から１つまたは複数の第２の符号語を符号化することによって第１の誤り訂正符号から１つまたは複数の第１の符号語を選択するように配置構成される請求項６から１２のいずれか一項に記載の電子暗号デバイス（１００）。
【請求項１４】
−  １つまたは複数のノイズのある第１の符号語の訂正の信頼度を示す信頼度情報を決定するように構成されている信頼度情報抽出器と、
−  信頼度情報を使用して１つまたは複数の第２の符号語を復号するように構成されている軟判定復号器とを備える請求項１３に記載の電子暗号デバイス（１００）。
【請求項１５】
バイアス除去ユニット（１２０）が、
−  第１のノイズのあるビット列内のビットを保持または破棄としてマークする前に第２の転置により第１のノイズのあるビット列を転置し、第１のノイズのあるビット列の第１および第２の部分内のビットを一緒にグループ化するように配置構成され、第１のノイズのあるビット列の第１および第２の部分がそれぞれ第１および第２のバイアスレベルを有し、
鍵再構築ユニット（１５０）が、
−  バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットを決定する前に第２の転置により第２のノイズのあるビット列を転置し、第２のノイズのあるビット列の第１および第２の部分内のビットを一緒にグループ化するように配置構成される、請求項６から１４のいずれか一項に記載の電子暗号デバイス（１００）。
【請求項１６】
第１の誤り訂正符号が、反復符号である、請求項６から１５のいずれか一項に記載の電子暗号デバイス（１００）。
【請求項１７】
−  物理的複製不可能関数のノイズレベルを検証するために再構築フェーズにおいて統計的検定を実行するように配置構成されている統計ユニット（１６０）と、
−  バイアス除去データおよび第２のノイズのあるビット列を使用して第１のノイズのあるビット列内では等しいが第２のノイズのあるビット列内では等しくなく、および／または第１のノイズのあるビット列内では等しくないが第２のノイズのあるビット列内で等しいビットペアの数をカウントし、カウントが閾値を超える場合に物理的複製不可能関数のノイズレベルが十分であると検証するように配置構成されている統計的検定とを含む、請求項２または１０に記載の電子暗号デバイス（１０２）。
【請求項１８】
−  統計的検定が正しく機能していることを示している場合のみ物理的複製不可能関数によって生成されるノイズのあるビット列にエントロピー濃縮関数を適用することによってランダムシードを生成するように配置構成されているランダムシード生成ユニット（１６５）を備え、
−  ランダムシード生成ユニット（１６５）が、エントロピー濃縮関数を第２のノイズのあるビット列に適用するように配置構成されるか、
または
−  物理的複製不可能関数（ＰＵＦ）（１１０）が、再構築フェーズではさらなるノイズのあるビット列（１１６）を生成するように配置構成され、第２のノイズのあるビット列（１１４）がさらなるノイズのあるビット列と異なり、
−  ランダムシード生成ユニット（１６５）が、エントロピー濃縮関数をさらなるノイズのあるビット列に適用するように配置構成される、請求項１７に記載の電子暗号デバイス（１０２）。
【請求項１９】
暗号鍵を決定するように構成されている電子暗号方法であって、暗号方法は、登録フェーズおよびその後の再構築フェーズを含み、
−  登録フェーズは
−  物理的複製不可能関数（ＰＵＦ）（１１０）を使用して第１のノイズのあるビット列を生成するステップと、
−  第１のノイズのあるビット列内のバイアスを低減するために第１のノイズのあるビット列からバイアス除去データを決定するステップであって、バイアス除去データは第１のノイズのあるビット列内のビットを保持または破棄としてマークする、決定するステップとを含み、
−  再構築フェーズは
−  物理的複製不可能関数（ＰＵＦ）（１１０）を使用して第２のノイズのあるビット列を生成するステップと、
−  バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定するステップであって、暗号鍵はバイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している、決定するステップとを含む、電子暗号方法。
【請求項２０】
−  プログラム可能な装置内にロード可能なデータを備える非一時的な有形のコンピュータ可読ストレージ媒体であって、データはプログラム可能な装置によって実行可能な命令を表し、前記命令は：
−  物理的複製不可能関数（ＰＵＦ）（１１０）から第１のノイズのあるビット列を取得するように配置構成されている１つまたは複数の取得命令と、
−  第１のノイズのあるビット列内のバイアスを低減するために第１のノイズのあるビット列からバイアス除去データを決定するように配置構成され、バイアス除去データは第１のノイズのあるビット列内のビットを保持または破棄としてマークする、１つまたは複数の決定命令と、
−  物理的複製不可能関数（ＰＵＦ）（１１０）から第２のノイズのあるビット列を取得するように配置構成されている１つまたは複数の取得命令と、
−  バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定し、暗号鍵はバイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している、１つまたは複数の決定命令とを含む、非一時的な有形のコンピュータ可読ストレージ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子暗号デバイス、電子暗号方法、および非一時的な有形のコンピュータ可読記憶媒体に関するものである。
【背景技術】
【０００２】
物理的複製不可能関数（ｐｈｙｓｉｃａｌ  ｕｎｃｌｏｎａｂｌｅ  ｆｕｎｃｔｉｏｎ）は、製造上のバラツキを利用してデジタル識別子を導出する。したがって、デジタル識別子は、物理的媒体に結び付けられている。物理的複製不可能関数は、ランダムなプロセス変動に依存するので、ＰＵＦを作成することは簡単であるが、特定の所定の識別子を生じさせるＰＵＦを作成することは、全く不可能でないとしても、非常に難しい。製造上のバラツキは、メモリ要素の異なる物理的特性を生じさせる。たとえば、物理的特性は、以下を含み得る：ドーピング濃度、酸化層の厚さ、チャネル長さ、構造の幅（たとえば、金属層の）、寄生量（たとえば、抵抗、静電容量）。デジタル回路設計が複数回製造されるときに、これらの物理的特性は、わずかに変化し、それとともに、ＩＣ素子、たとえば、メモリ素子の挙動をいくつかの状況において異なる挙動に変える。たとえば、起動時挙動は、物理的特性の製造上のバラツキによって決定される。
【０００３】
ＰＵＦがデバイス固有の、予測不可能な応答を発生するという事実は、それらを暗号鍵を発生するのに非常に適した候補にする。従来の不揮発性鍵ストレージとは対照的に、ＰＵＦベースの鍵は、デジタル形式で格納されず、ＰＵＦの物理的構造の小さいランダムな差異から生じる。さらに、鍵それ自体の生成は、低品質であり得る、外部から与えられるランダム性に依存しないが、デバイスそれ自体の高エントロピーの固有のランダム性を使用する。これらの要素の組合せは、暗号鍵ストレージのための非常に安全なリューションを実現し得る。
【０００４】
ＰＵＦを使用することで、安全なメモリに鍵を記憶する必要性が回避され得る。ＰＵＦは、さらに、リバースエンジニアリングを通じて暗号鍵を取得しようとする悪意ある試みに対する自然な防御を実現するが、それは、そうした悪意ある試みがなされたときにＰＵＦに負わせる可能性のある損傷がデジタル識別子を変更する可能性が高いからである。好ましくは、デジタル識別子は、物理的複製不可能関数が埋め込まれている電子デバイスに対して一意である。
【０００５】
たとえば、いくつかのメモリ素子の起動時挙動は、ＰＵＦに似た挙動を示すことが観察されている。そのようなメモリに電源投入されると、これは、メモリを構成するコンポーネント、たとえば、ゲートもしくはトランジスタの少なくとも部分的にランダムな物理的特性、たとえば、互いに関する物理的配置構成に依存する、コンテンツを含む、すなわち、一連のデータ値を備える傾向を有する。メモリに複数回電源投入された場合、これは、大きな割合まで、同じコンテンツを格納する。
【０００６】
ＰＵＦは、予測不可能な、デバイス固有の応答をもたらし、それでも、その物理的起源により、これらは測定ノイズ、および環境の影響を受け得る。その一方で、暗号鍵は、完全に信頼でき、完全なエントロピーを有する必要がある。このギャップを埋めるために、ＰＵＦ応答に対するある程度の量の後処理が必要である。ノイズに対処する一方法は、いわゆるファジー抽出器の使用である。ファジー抽出器は、「ノイズのある」ランダム値を信頼できる鍵に変換することができる。これらの変動を訂正するためにこのプロセスにおいて誤り訂正手続きが使用され、ＰＵＦが使用されるたび毎に、同一のデジタル識別子が導出されていることを確実にできる。誤り訂正手続きは、いわゆるヘルパーデータを使用する。ヘルパーデータは、ノイズ低減データとも呼ばれる。
【０００７】
ファジー抽出器は、２つの段階を備え得る。初期登録段階では、暗号鍵が、ＰＵＦ応答から導出される。登録プロセスでは、ＰＵＦ応答に対するヘルパーデータまたはノイズ低減データが生成される。その後現場において、再構築段階で、ＰＵＦ応答を再評価し、登録段階からのノイズ低減データを使用して同じ鍵を再構築する。ノイズ低減データは、したがって、登録段階と再構築段階との間に、格納される必要がある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】国際公開第２００９／０２４９１３号
【特許文献２】米国特許出願公開第２００３／０２０４７４３号明細書
【特許文献３】欧州特許第２１９１４１０号明細書
【特許文献４】国際公開第２０１１／０１８４１４号
【特許文献５】国際公開第２０１２／０６９５４５号
【非特許文献】
【０００９】
【非特許文献１】ＩＥＥＥ  Ｓｔｄ  １３６３−２０００、ＮＩＳＴ−ＳＰ８００−１０８、および５６−Ｃ
【非特許文献２】ＡＮＳＩ  Ｘ９．４２
【非特許文献３】ＮＩＳＴ、ＳＰ８００−９０Ａ、Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｉｏｎ  Ｕｓｉｎｇ  Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｒａｎｄｏｍ  Ｂｉｔ  Ｇｅｎｅｒａｔｏｒｓ
【発明の概要】
【課題を解決するための手段】
【００１０】
この点においてファジー抽出器の望ましい特性は、ノイズ低減データが導出される鍵に関する情報を含まないことである。言い替えれば、ノイズ低減データは、機密情報を含まず、生成された鍵を攻撃するために使用され得ない。その結果、ノイズ低減データの格納および伝達は公開される形で行うことができ、鍵の直接的格納が必要になるような敵対者からの保護を必要としない。
【００１１】
ファジー抽出器の動作は、誤り訂正符号の使用に基づき得る。典型的には、誤り訂正符号は、ブロック符号であり、および線形である、たとえば、線形誤り訂正ブロック符号である。登録時に、ファジー抽出器は、たとえば、ＰＵＦ応答ビット上で多数のパリティ関係を計算し、ノイズ低減データ内のこれらの関係を公開することによって、ＰＵＦ応答に対するノイズ低減データを計算する。ノイズ低減データは、たとえば、１つまたは複数の符号語とＰＵＦ応答との間の差を計算することによって、計算され得る。
【００１２】
この公開により、ＰＵＦ応答の予測不可能性（そのエントロピーによって測定される）は、著しく低減され得る。
【００１３】
発明者らは、ＰＵＦが高いバイアスを有している場合に、ノイズ低減データを通じての鍵に関する情報漏洩が非ゼロであることを発見した。実際、ＰＵＦが非常に高いバイアスを有している場合、ノイズ低減データは、攻撃者による鍵の完全な再構築を許すのに十分な鍵に関する情報をすら明らかにし得る。
【００１４】
たとえば乱数発生のような異なる分野から取り入れられた従来のバイアス除去（ｄｅｂｉａｓｉｎｇ）方法は、ＰＵＦおよび鍵発生に適用され得ない。ＰＵＦ応答は、少なくとも２回取得される。毎回同じ暗号鍵が生成されるべきである。しかしながら、ＰＵＦ出力は、多くの場合、完全には決定論的でない。ノイズが比較的少量であっても、そのようなバイアス除去手続きが、バイアス除去された出力として使用する異なるビットを選択するようにさせてしまう。そのようなシステムは、鍵生成に全く使用可能でない。たとえば、乱数ビット発生器によって生成されるすべての不等ビットペア（ｕｎｅｑｕａｌ  ｂｉｔ  ｐａｉｒ）について１つのバイアスしていない（アンバイアス）出力ビットを生成する古典的なフォンノイマンバイアス除去（ｖｏｎ  Ｎｅｕｍａｎｎ  ｄｅｂｉａｓｉｎｇ）は、ＰＵＦに直接適用され得ない。登録時および再構築時にＰＵＦに古典的なフォンノイマンバイアス除去を適用すると、異なるビットが選択され、再現性のある鍵をそこから形成することが可能でなくなる。
【００１５】
登録フェーズおよびその後の使用フェーズのために配置構成されている電子暗号デバイスは、請求項において定義されているように実現される。一実施形態において、電子暗号デバイスは、暗号鍵を決定するように配置構成されている。暗号デバイスは、登録フェーズおよびその後の再構築フェーズのために配置構成される。暗号デバイスは、物理的複製不可能関数、バイアス除去ユニット、および鍵再構築ユニットを備える。
【００１６】
物理的複製不可能関数は、登録フェーズでは第１のノイズのあるビット列を、再構築フェーズでは第２のノイズのあるビット列を生成するように配置構成される。
【００１７】
バイアス除去ユニットは第１のノイズのあるビット列内のバイアスを低減するためのものであり、バイアス除去ユニットは登録フェーズにおいて第１のノイズのあるビット列からバイアス除去データを決定するように配置構成され、バイアス除去データは第１のノイズのあるビット列内のビットを保持または破棄としてマークする。
【００１８】
鍵再構築ユニットはバイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定するように配置構成され、暗号鍵はバイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している。
【００１９】
登録フェーズでは、たとえば、バイアス除去ユニット１２０は、ＰＵＦ応答からどのビットを保持または破棄するかを決める選択を行う。この情報は、バイアス除去データ内に記録される。ＰＵＦが２回目に問い合わせされたときに、バイアス除去データを使用して同じビットが選択される。したがって、第２のＰＵＦ応答中にノイズが存在している場合でも、第１のＰＵＦ応答時に選択されたのと同じビットが選択される。ノイズは、第２の応答から選択されたビット中にまだ存在している可能性があることに留意されたい。
【００２０】
本出願では、バイアスは、１または０ビットのうちの一方が１または０ビットのうちの他方よりも可能性が高い状況を指す。たとえば、ＰＵＦのバイアスは、１ビットを生成する確率と０ビットを生成する確率との間の絶対差として定義され得る。バイアスは、１ビットを生成する確率と０ビットを生成する確率の最大値としても定義され得る。バイアスは、複数のデバイスを比較することによって特定のビット位置について決定され得る。典型的には、バイアスは、ビット位置のより大きい部分について一様である。いくつかのＰＵＦについて、特に、メモリベースのＰＵＦについて、メモリ上にバイアスの何らかのバラツキがあり得る。たとえば、バイアスは、メモリ上で変動し得るが、より大きいゾーンについては一定であり、たとえば、メモリの第１の半分および第２の半分は各々一定のバイアスを有するが、互いに異なり得る。バイアスは、また、局所的に変動することもあり得、たとえば、いくつかのメモリは、偶数ビット位置と奇数ビット位置とでバイアスに差があることを示す。
【００２１】
低いバイアスを有するＰＵＦは、少なくとも平均的には、１ビットの割合と０ビットの割合との間の絶対差が小さい、ビット列を生成する。この割合は、それぞれ１または０ビットの個数をビット列の長さで除算したものとしてみなされ得る。
【００２２】
暗号鍵は、暗号鍵を使用する情報の暗号化または復号、暗号鍵を使用する情報の電子署名を含む、多数の暗号プロトコルにおいて使用され得る。ＰＵＦから導出される暗号鍵は、対称鍵または非対称鍵であってよい。請求項において説明されているデバイスおよび方法の実施形態は、広範な実用的なアプリケーションにおいて適用され得る。そのようなアプリケーションは以下を含む：銀行カード、ｓｉｍカード、ペイ・パー・ビュー用のスマートカード、ＩＤカードなど。
【００２３】
本発明による方法は、コンピュータ実装方法としてコンピュータ上に、または専用ハードウェアで、またはその両方の組合せで、実装され得る。本発明による方法に対する実行可能コードは、コンピュータプログラム製品上に格納され得る。コンピュータプログラム製品の例は、メモリデバイス、光ストレージデバイス、集積回路、サーバ、オンラインソフトウェアなどを含む。好ましくは、コンピュータプログラム製品は、前記プログラム製品がコンピュータ上で実行されたときに本発明による方法を実行するためのコンピュータ可読媒体上に格納されている非一時的プログラムコード手段を含む。
【００２４】
好ましい一実施形態において、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行されたときに本発明による方法のすべてのステップを実行するように構成されているコンピュータプログラムコード手段を含む。好ましくは、コンピュータプログラムは、コンピュータ可読媒体上に具現化される。
【００２５】
本発明の別の態様は、コンピュータプログラムをダウンロードに利用可能にする方法を提供する。この態様は、コンピュータプログラムが、たとえば、ＡｐｐｌｅのＡｐｐ  Ｓｔｏｒｅ、ＧｏｏｇｌｅのＰｌａｙ  Ｓｔｏｒｅ、またはＭｉｃｒｏｓｏｆｔのＷｉｎｄｏｗｓ  Ｓｔｏｒｅにアップロードされるときに、およびコンピュータプログラムが、そのようなストアからのダウンロードに利用可能であるときに使用される。
【００２６】
本発明のさらなる詳細、態様、および実施形態は、図面を参照しつつ、例のみを用いて説明される。図中の要素は簡単に、またわかりやすいように図示されており、必ずしも縮尺通りに描かれていない。図中、すでに説明されている要素に対応する要素は、同じ参照番号を有する。以下に図の説明を示す。
【図面の簡単な説明】
【００２７】
【図１ａ】わずかなバイアスを通じてのエントロピー損失を示す略図である。
【図１ｂ】大きなバイアスを通じてのエントロピー損失を示す略図である。
【図２】電子暗号デバイスの一実施形態の一例を示す略図である。
【図３】電子暗号デバイスの一実施形態の一例を示す略図である。
【図４ａ】電子暗号デバイスの一実施形態の一例における登録フェーズを示す略図である。
【図４ｂ】電子暗号デバイスの一実施形態の一例における再構築フェーズを示す略図である。
【図５ａ】電子暗号デバイスの一実施形態の一例における登録フェーズを示す略図である。
【図５ｂ】電子暗号デバイスの一実施形態の一例における再構築フェーズを示す略図である。
【図６ａ】電子暗号デバイスの一実施形態の一例における登録フェーズを示す略図である。
【図６ｂ】電子暗号デバイスの一実施形態の一例における再構築フェーズを示す略図である。
【図６ｃ】第２の誤り訂正符号の一実施形態を示す略図である。
【図６ｄ】軟判定復号の実施形態を示す略図である。
【図７】暗号鍵を決定するように構成されている電子暗号方法の一実施形態を示す略図である。
【図８ａ】一実施形態によるコンピュータプログラムを含む書き込み可能部分を有するコンピュータ可読媒体を示す図である。
【図８ｂ】一実施形態によるプロセッサシステムを示す概略配置図である。
【図９ａ】電子暗号デバイスの一実施形態の一例を示す略図である。
【図９ｂ】電子暗号デバイスの一実施形態の一例における統計的検定を示す略図である。
【図１０】統計的検定の一実施形態をフローチャートで示す略図である。
【図１１】統計的検定の一例に対する失敗率グラフである。
【発明を実施するための形態】
【００２８】
本発明は実施形態を多くの異なる形態で受け入れる余地があるものの、本開示が本発明の原理の例示として考えられるべきであり、図示され説明されている特定の実施形態に本発明を限定するよう意図されてはいないという理解の下に、１つまたは複数の特定の実施形態が図面に示され、本明細書において詳細に説明される。
【００２９】
次に、理解しやすくするために、実施形態の要素は、動作に関して説明される。しかしながら、それぞれの要素は、それらによって実行される通りに説明されている機能を実行するように配置構成されていることは明らかになるだろう。
【００３０】
図１ａおよび１ｂは、バイアスを通じてのエントロピー損失の概略を示している。図１ａおよび１ｂには、登録時の「エントロピーの流れ」の概念が図示されている。なお、図１ａおよび１ｂのボックスの相対的サイズは、ＰＵＦ応答、ノイズ低減データ、および鍵の相対的サイズを必ずしも示さない。
【００３１】
ＰＵＦ１０は、特定の量のエントロピーを持つ応答１１を生成する。登録手続きは、ＰＵＦ応答に含まれるエントロピーの比較的大きな部分を公開するノイズ低減データ１２を生成する。ノイズ低減データ公開の後の残りのエントロピーは、暗号的に安全な秘密鍵を生成するために使用される。完全にランダムな鍵を取得するために、鍵の長さ（ビット単位）は、ノイズ低減データ公開により低減されたＰＵＦ応答エントロピーよりも決して大きくなり得ない。
【００３２】
実際、ファジー抽出器は、特定のノイズレベルおよび特定の量のエントロピーを持つ応答を発生する特定のタイプのＰＵＦを扱うように設計され得る。基本の誤り訂正符号のパラメータは、最大予想数のビット誤りを取り扱うことができるように選択される。これらのパラメータから、１回の応答に対する結果として生じるノイズ低減データ公開が計算され、したがって、残りの鍵エントロピーも計算され得る。最後に、ＰＵＦのサイズ（応答内のビットの個数）は、完全エントロピー鍵を抽出するために鍵エントロピーの十分な総量が残されるまで増やされる。
【００３３】
ＰＵＦ応答エントロピーは、ＰＵＦ応答におけるバイアスの存在によって、すなわち、２値応答０が１よりもシステマティックに多く見られる（またはその逆の）場合に、低減される。バイアスによるエントロピー損失は、図１ａおよび１ｂにおいて参照番号１５で示されている。
【００３４】
エントロピーフローが与えられた量の応答エントロピーのために設計されているファジー抽出器を仮定する。図１ａは、わずかなバイアスの場合を示す略図である。ＰＵＦ応答１１の陰影部分１５は、バイアスによる図１ａの元々の状況に関するエントロピーの低減である。応答エントロピーが低減されるので、これは、ノイズ低減データ公開および鍵データ１３内の残りのエントロピーに対しても影響し、最終的な暗号鍵は、鍵データ１３から導出される。始めにエントロピーが少なく、ノイズ低減データの公開後に残されているエントロピーが少ないので、残りの鍵エントロピーは低減される。これは、鍵データ１３がバイアスがない場合に予想されるのと比べてあまりランダムでないので、問題になり得る。ＰＵＦ応答におけるバイアスによって引き起こされる、鍵エントロピーのこの低減は、鍵漏洩と呼ばれる。
【００３５】
たとえば大きなバイアスがあることで、ＰＵＦ応答エントロピーが著しく低減される状況では、鍵漏洩は、非常に大きなものとなり得る。これは、図１ｂに示されている。その場合、応答エントロピーは小さいので、ノイズ低減データの公開後に残されているものはない。したがって、鍵を抽出する秘密の素材は残されていない。実際、このことは、ノイズ低減データは、鍵によって使用されるエントロピーを含む、応答エントロピーすべてを公開することを意味する。言い替えれば、鍵は、ノイズ低減データから導出され得る。ファジー抽出器は、したがって、全く安全でなくなる。
【００３６】
バイアス除去データを使用しない、鍵漏洩問題への可能な代替的ソリューションは、ＰＵＦ応答エントロピーが低減される最悪の場合に合わせてファジー抽出器を設計することである。言い替えれば、ファジー抽出器は、出来る限り低減されたエントロピーを取り扱うためのエントロピーマージンがあるように設計される。しかしながら、このソリューションには多数の問題がある：
１．エントロピーマージンは、ＰＵＦ応答エントロピーの小さな低減にしか対処できない（たとえば、数パーセントのオーダーの小さなバイアス）。マージンは、ＰＵＦ応答エントロピーが減少するときに非常に速く激減する。
２．ファジー抽出器の設計は、わずかに低減するエントロピーであってもＰＵＦを考慮するときにたちまち非常に不効率なものとなる。ＰＵＦ応答内に存在するほぼすべてのエントロピーは、ノイズ低減データによって公開されるので、ＰＵＦのサイズ（応答ビットの個数）は、安全な鍵を導出するためにある程度のエントロピーが残されるため非常に大きなサイズになる必要がある。
３．従来の方法を使用することで、ＰＵＦ応答エントロピーが著しく低減される場合に（たとえば、大きなバイアスにより）鍵エントロピーが残されているファジー抽出器を設計することは全く不可能になることがある。ＰＵＦのサイズを大きくしても、応答ビット毎の実効エントロピー寄与分が０になるので、その場合に役立ち得ない。
【００３７】
鍵漏洩問題に対する別のアプローチは、非常に高い、または完全ですらあるエントロピーを持つ応答を生成するＰＵＦをのみを考慮するものである。このアプローチは、バイアス除去データを必要としない。これは、ファジー抽出器設計からＰＵＦ構築に鍵漏洩問題をシフトすることなので、実際にはソリューションにならない。理想的とは言えないＰＵＦ設計だが、それを使用し続けることが望まれている。さらに、このオプションには多数の問題がある：
１．バイアスしていないＰＵＦ応答のために設計されているファジー抽出器には、常に偶然に一致して生じる可能性のある最もわずかなバイアスですら対処するためのマージンはほとんどまたは全くない。
２．その構造のせいで、いくつかのタイプのＰＵＦは、本質的に、バイアスされた、または低減されたエントロピー応答を有する。したがって、このソリューションは、これらのタイプのＰＵＦに対して適用可能でない。
３．典型的には高エントロピー応答を有するＰＵＦタイプであっても、完全にバイアスしていない応答をほんの滅多にしか有しない。ＰＵＦタイプのバイアスを推定するときに特定のレベルの不確定性を常に有する。さらに、現場における数千または数百万のＰＵＦインスタンスを用いる実用的なアプリケーションでは、バイアスが平均的な「バイアスしていない」場合から著しく逸脱する可能性のある外れ値のインスタンスも考慮しなければならない。
４．ＰＵＦ応答のバイアスは、ＰＵＦ構造の外部の条件、たとえば、温度の影響も受け得る。すべての状況下でファジー抽出器を安全に動作させたい場合、ＰＵＦ応答が（わずかに）バイアスされる可能性のあることを考慮する必要がある。
【００３８】
以下で説明されている実施形態は、バイアスされたＰＵＦ応答の場合に鍵漏洩問題を軽減する。発明者らは、初期登録ステップの前のおよび／または初期登録ステップと一体になったバイアス除去動作を導入することがＰＵＦ応答におけるバイアスを低減することを発見した。次いで、これは、ノイズ低減データなどのサイド情報の鍵漏洩を改善する。
【００３９】
図２は、電子暗号デバイス１００の一実施形態の一例を示す略図である。
【００４０】
デバイス１００は、通常ＰＵＦと称される、いわゆる物理的複製不可能関数１１０を備える。デバイス１００は、暗号鍵を決定するように配置構成される。暗号デバイスは、登録フェーズおよびその後の再構築フェーズのために配置構成される。ＰＵＦ１１０は、登録フェーズでは第１のノイズのあるビット列１１２を、再構築フェーズでは第２のノイズのあるビット列１１４を生成するように配置構成される。複数回繰り返され得る、再構築フェーズでは、同じ暗号鍵が生成される。登録フェーズでは、暗号鍵の繰り返される同一の生成を可能にし、および／またはＰＵＦ内のバイアスを低減するデータが生成され得る。
【００４１】
ＰＵＦ１１０の信頼性が例外的に高く、および／またはアプリケーションの信頼性の重要性が低い場合に、ノイズ低減データなしで済ませることができる。後者の場合、バイアス除去は、鍵の低減されたエントロピーを回避するために、まだ価値があり得る。この場合、バイアス除去されたＰＵＦ応答は、たとえば、保持ビットを連結すること、鍵導出関数を適用すること、などによって鍵を導入するために使用することが可能である。
【００４２】
その後生成されるノイズのあるビット列の間の変化の量は、異なるタイプのＰＵＦ同士の間で異なり、変化の量に応じて、この誤り量を訂正するために、誤り訂正符号が選択され得る。ノイズのあるビット列は、暗号鍵を生成するのに十分な安定性および十分な長さを有する。ＰＵＦのノイズのあるビット列の長さは、所望の鍵長さ、ＰＵＦの誤りパーセンテージ、および／またはＰＵＦのバイアスレベルなどに関して選択され得る。
【００４３】
ＰＵＦ１１０は、ノイズのあるビット列を再び生成するために、パワーサイクル、たとえば、電源をオフにした後に電源をオンにする操作を必要とし得る。電源オン信号は、チャレンジとみなされ得る。デバイス１００において、ＰＵＦ１１０は、ノイズのあるビット列を少なくとも２回生成する。登録フェーズにおいて１回、ＰＵＦ１１０は、第１のノイズのあるビット列を生成する。その後使用フェーズにおいて、ＰＵＦ１１０は、第２のノイズのあるビット列を生成する。第１および第２のノイズのあるビット列は、互いに十分に近く、たとえば、その差のハミング重みは、閾値よりも小さい。
【００４４】
ＰＵＦは、物理的デバイスに結び付けられた確率関数であり、その結び付きは実際にその物理的デバイスを使用してそれを評価しないと関数の出力を予測することが計算的に実行不可能であるような仕方である。さらに、ＰＵＦは物理的システムによって実現されているので、複製作成が難しい。完全には制御されない（すなわち、何らかのランダム性を含む）生産プロセスによって生産される物理的システムは、ＰＵＦの良好な候補であることがわかる。一実施形態において、ＰＵＦ１１０およびしたがって暗号デバイス１００は、ＰＵＦ１１０によって与えられる応答と、それから導出される鍵とに基づき一意に識別され得る。鍵は、デバイスを識別する、識別子として使用され得る。
【００４５】
ＰＵＦの物理的システムは、刺激と複雑な仕方で相互作用し、一意であるが、予測不可能な応答を引き起こすように設計される。ＰＵＦの刺激は、チャレンジと称される。何らかのＰＵＦは、より広い範囲の異なるチャレンジを可能にし、異なる応答を生成する。ＰＵＦチャレンジおよび対応する応答は、まとめてチャレンジ−応答（レスポンス）−ペアと呼ばれる。しかしながら、ＰＵＦは、単一のチャレンジも有し得る。ＰＵＦ１１０は、単一チャレンジＰＵＦであってよい。ＰＵＦ１１０は、複数チャレンジＰＵＦであってもよい。後者の場合、ＰＵＦ１１０は、ノイズのあるビット列、特に、第１および第２のノイズのあるビット列を生成するときに同じチャレンジまたはチャレンジのセットでチャレンジされる。
【００４６】
ＰＵＦの好適なソースは、電源がオンした時に、メモリの識別に有用な電源オン値の応答パターンを含む電子的揮発性メモリによって形成され、その応答パターンはメモリ素子の物理的特性に依存する。
【００４７】
デバイスを一意に識別するために使用されるＰＵＦの知られている一例は、いわゆるＳＲＡＭ  ＰＵＦであり、これは、ＳＲＡＭセルが起動されるときに、トランジスタの閾値電圧のばらつきに起因してランダムな状態で起動するという事実に基づくが、そのばらつきは同様にドーピングのばらつきに起因している。これが複数回で実行されるときに、各セルは時間の大半において同じ状態で起動する。これらのＰＵＦは、オンボードにＳＲＡＭメモリを有する任意のデバイス上で実現され得る。
【００４８】
メモリを識別するために十分に安定しているランダム起動挙動を示すメモリは、チャレンジ可能なメモリと呼ばれる。起動挙動がランダムであると、２つの異なるメモリは、その起動メモリパターンに大きな差異を有し、起動挙動が安定していると、同じメモリの２つの起動メモリパターンは、小さな差異を有する。そのようなメモリの例は、述べたようなＳＲＡＭメモリセルであるが、フリップフロップに似たメモリ素子でもある。実際、フィードバックループを備える任意のタイプの揮発性メモリが使用され得る。
【００４９】
第２の種類のＳＲＡＭベースＰＵＦが、デュアルポートＲＡＭで構成され得る。両方のポートに同時に異なる情報を書き込むことによって、メモリセルは、未定義状態にされ、ＰＵＦに似た挙動を示す。この種類のＰＵＦは、ＷＯ２００９０２４９１３号においてより詳しく説明される。他のいわゆる固有（Ｉｎｔｒｉｎｓｉｃ）ＰＵＦは、遅延現象に基づくものであり、たとえば、ＵＳ２００３０２０４７４３号を参照。ＰＵＦは、ＦＰＧＡ上でＳＲＡＭメモリセルをシミュレートすることによって、たとえば、交差結合インバータまたはラッチ、いわゆるバタフライ型ＰＵＦによって構築されるものとしてよく、これは、ＥＰ２１９１４１０Ｂ１号およびＷＯ２０１１０１８４１４Ａ２号を参照。ＰＵＦ１１０は、たとえば、ＷＯ２０１２０６９５４５号で説明されているような、複数のバスキーパーを含む物理的複製不可能関数であってよい。
【００５０】
デバイス１００は、バイアス除去ユニット１２０を備える。バイアス除去ユニット１２０は、ＰＵＦ１１０の出力、特に、第１のノイズのあるビット列１１２におけるバイアスを低減するように配置構成される。バイアス除去ユニット１２０は、登録フェーズにおいて第１のノイズのあるビット列１１２からバイアス除去データ１４２を決定するように配置構成される。バイアス除去データは、第１のノイズのあるビット列内のビットを保持または破棄としてマークする。
【００５１】
バイアス除去データは、バイアス除去の後のＰＵＦ１１０の出力がＰＵＦ１１０の直接の応答よりも低いバイアスを有するように選択される。一実施形態において、バイアス除去ユニット１２０は、バイアス除去情報によって保持としてマークされている第１のビット列のビットの中の１ビットの割合と０ビットの割合との間の絶対差が、第１のノイズのあるビット列の間よりも小さくなるように配置構成される。一実施形態において、バイアス除去ユニット１２０は、バイアス除去情報によって保持としてマークされている第１のビット列のビットの中の１ビットの割合と０ビットの割合との間の絶対差が、０になるように配置構成され得る。
【００５２】
より単純な一実施形態において、バイアス除去ユニットは、ＰＵＦ応答のビット長よりも小さい、所定の数ｋにより配置構成され得る。この数は、バイアスを考慮して、ＰＵＦ１１０が少なくともｋ個の０ビットおよび少なくともｋ個の１ビットを有する高い確率を有するように選択される。実際、実用的なバイアスについて、この確率は、ＰＵＦ応答のビット長が十分に大きく取れると仮定して、任意に高くできる。
【００５３】
バイアス除去ユニットは、保持されている第１のＰＵＦ応答１１２内のビットのうちからｋ個の０ビットおよびｋ個の１ビットをランダムに選択し、他のすべてを破棄するように配置構成され得る。バイアス除去データ１４２は、登録フェーズにおいてどのビットが保持としてマークされて、どのビットが破棄されたかを示す。この情報は、いく通りもの仕方で記録され得る。たとえば、バイアス除去データ１４２は、保持ビットを示すためのビットマスクを含み得る。保持ビットは、後で、たとえば、ビット単位の「ａｎｄ」演算により選択され得る。たとえば、バイアス除去データ１４２は、選択されたビットを指すインデックスのリストを含み得る。
【００５４】
ｋ個の０ビットおよびｋ個の１ビットをランダムに選択するこの方法は、バイアスを低減するか、または取り除くことすらするように働くが、それでも、少しの欠点がある。まず第一に、正確にｋ個の０および１が選択されるので、予測不可能性（すなわち、エントロピー）は、攻撃者が正確にｋ個の０および１があることを知っているため、事実上少ししか低減されず、真にランダムな列では、それは必ずしも０ビットおよび１ビットの同じ数にならない。さらに、０と１とをランダムに選択するために確率的手法を使用することもできる。しかしながら、独立したランダム性の発生源は利用可能でない場合がある。以下の実施形態のうちのいくつかは、独立したランダム性の発生源を必要としないが、これに対するビット列内の固有のランダム性を使用する。
【００５５】
最後に、バイアスが一様でない場合、非一様性の一部は、「バイアス除去された」ビット列の中に存続し得る。たとえば、ＰＵＦに位置依存のバイアスがある場合、たとえば、ＰＵＦ応答の第１の部分がＰＵＦ応答の第２の部分と異なるバイアスを有する（たとえば、応答の半分の一方が０にバイアスされ、応答の半分の他方が１にバイアスされる）場合、この方法はそれを取り除くことができない可能性もある、すなわち、「バイアス除去された」ビット列は、同じ位置ベースのバイアスをそのまま有することになる。以下に示されている実施形態では、バイアス除去が局所的なので、この弱点はない。
【００５６】
デバイス１００は、鍵再構築ユニット１５０を備える。鍵再構築ユニット１５０は、バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定するように配置構成される。暗号鍵は、バイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している。たとえば、鍵再構築ユニット１５０は、バイアス除去データ１４２によって保持としてマークされているビットを第２のＰＵＦ応答１１４から選択し、破棄としてマークされているビットを無視するように配置構成され得る。
【００５７】
鍵再構築ユニット１５０は、新たなバイアス除去動作を実行せず、その結果、新しい選択は元の選択と極めて異なることがあり得ることに留意されたい。その結果、登録および再構築時に、または異なる再構築フェーズの間で、同じ鍵を導出することが可能でなくなる。その代わりに、再構築ユニット１５０は、登録フェーズにおいて取得されたバイアス除去データを適用する。たとえば、バイアス除去データは、たとえば、ローカルのデバイス１００に、または外部の、たとえばデバイス１００に接続可能であるものとしてよいサーバ内に、たとえば、電子データ接続を通じて、格納され得る。
【００５８】
暗号デバイス１００は、ノイズ低減機能により拡張され得る。たとえば、保持ビットにノイズ低減のための従来のファジー抽出器が適用され得る。
【００５９】
たとえば、暗号デバイス１００は、登録フェーズにおいてバイアス除去データによって保持としてマークされる第１のノイズのあるビット列内のビットに対するノイズ低減データを決定するように配置構成されているノイズ低減ユニットと、前記ノイズ低減データに依存する形で再構築フェーズにおいてバイアス除去データによって保持としてマークされる第２のノイズのあるビット列内のビット内のノイズを低減するように配置構成されている誤り訂正器とを備え得る。
【００６０】
図３は、電子暗号デバイス１０１の一実施形態の一例を示す略図である。電子暗号デバイス１０１は、デバイス１００の改良であり、ノイズ低減機能を備える。
【００６１】
電子暗号デバイス１００と同様に、デバイス１０１は、第１のノイズのあるビット列１１２、第２のノイズのあるビット列１１４を生成するＰＵＦ１１０、バイアス除去データ１４２を生成するバイアス除去ユニット１２０、および鍵再構築ユニット１５０を備える。
【００６２】
デバイス１０１は、ノイズ低減ユニット１３０を備える。ノイズ低減ユニット１３０は、第１の誤り訂正符号から１つまたは複数の第１の符号語を取得し、１つまたは複数の符号語から保持としてバイアス除去データによってマークされている第１のノイズのあるビット列内のビットに対するノイズ低減データ１４４を決定するように配置構成される。ノイズ低減データは、登録フェーズにおいて決定される。
【００６３】
デバイス１０１は、正規化器１５２を、たとえば、鍵再構築ユニット１５０の一部として備える。正規化器１５２は、再構築フェーズにおいてバイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットにノイズ低減データを適用し、ノイズと一緒に１つまたは複数の第１の符号語を決定するように配置構成される。
【００６４】
デバイス１０１は、前記１つまたは複数のノイズのある第１の符号語を訂正し１つまたは複数の訂正された符号語を取得するように配置構成されている誤り訂正器１５４を備える。誤り訂正器１５４は、複数ラウンドの訂正を行うように配置構成され得る。
【００６５】
デバイス１０１は、鍵導出ユニット１５６を備え得る。鍵導出は、誤り訂正器１５４の出力から暗号鍵を導出する。たとえば、鍵導出ユニット１５６は、鍵導出関数を１つまたは複数の訂正された符号語に適用し得る。代替的に、鍵導出ユニット１５６は、鍵導出関数（ＫＤＦ）を１つまたは複数の訂正された符号語の復号、または訂正され保持されているＰＵＦ応答ビットに適用し得る。そのような鍵導出関数の例は、ＩＥＥＥ  Ｓｔｄ  １３６３−２０００、ＮＩＳＴ−ＳＰ８００−１０８、および５６−Ｃにおいて定義されているＫＤＦ１ならびにＡＮＳＩ  Ｘ９．４２における類似の関数、などを含む。鍵導出関数は、ハッシュ関数であってもよい。
【００６６】
任意選択で、デバイス１０１は、バイアス除去データ１４２およびノイズ低減データ１４４を記憶するためにストレージ１４０、たとえば、不揮発性メモリ、たとえば、フラッシュメモリを備える。ストレージ１４０がデバイス１０１に備えられる代わりに、一実施形態では、バイアス除去データ１４２およびノイズ低減データ１４４を外部に格納する。バイアス除去データ１４２およびノイズ低減データ１４４は、組み合わされて単一のビット列にされてよい。
【００６７】
ノイズ低減データを決定する一方法は、誤り訂正符号に基づくいわゆる符号オフセット方法である。正規化器と誤り訂正器との組合せは、ときにはファジー抽出器とも称される。鍵導出は、ファジー抽出器に含めることもできる。
【００６８】
たとえば、登録段階において、１つまたは複数のランダム符号語がブロック符号から、たとえば、ランダム選択されたシードを符号化することによって選択され、符号語と保持としてマークされている第１のＰＵＦ応答のビットとの間の差が計算される。第１のＰＵＦ応答は、登録応答とも称され、１つまたは複数のランダム符号語は、登録符号語とも称される。
【００６９】
第１のＰＵＦ応答の保持部分は、保持部分を符号語のサイズの倍数にする必要がある場合にパディングされるか、または短縮され得る。
【００７０】
この差は、オフセットとも称される。２進値の場合、２つのベクトルの間のオフセットは、排他的ＯＲ（ＸＯＲ）演算によって取得され得る。この符号オフセットは、ノイズ低減データとして使用され得る。一実施形態において、ノイズ低減データ１４４は、オフセット、たとえば、第１のＰＵＦ応答の保持部分と１つまたは複数の符号語とのＸＯＲを含む。
【００７１】
再構築段階において、ＰＵＦは再評価され、登録されたＰＵＦ応答のノイズのあるバージョンが、すなわち、第２のＰＵＦ応答が取得される。ノイズ低減データ１４４に含まれる符号オフセットによって第２のＰＵＦ応答の保持部分をシフトすることによって、登録符号語のノイズのあるバージョンに辿り着く。２進値の場合、このシフトは、再び、ＸＯＲ演算に帰着する。ノイズのある符号語は、登録符号語が取られた誤り訂正符号に対応する誤り訂正アルゴリズムを使用して訂正され得る。再構築時にＰＵＦ応答ビット誤りの数が大きすぎないとした場合、訂正された符号語は、最初に登録されている符号語に等しい。
【００７２】
好ましければ、この訂正された符号語を符号オフセットでもう一度シフトすることによって最初に登録されたＰＵＦ応答の保持部分を再構築することができる。この応答から、登録された鍵は、結果として、抽出され得る。代替的に、鍵は、最初に登録されたＰＵＦ応答を再構築することなく訂正された符号語から取得され得る。また、訂正された符号語を復号し、場合によっては復号の１つまたは複数のさらなるラウンドの後に、鍵を導出することも可能である。
【００７３】
符号オフセットファジー抽出器の下にある誤り訂正ブロック符号が、次元ｋおよび長さｎを有する場合（（ｎ，ｋ）−符号とも表される）、ノイズ低減データの公開は（ｎ−ｋ）を上限とすることを示され得る。したがって、ノイズ低減データが、第１のＰＵＦ応答について計算された場合、バイアス除去を適用することなく、鍵抽出のために残っているエントロピーは、少なくともＨ（Ｘ）−（ｎ−ｋ）であり、ここで第１のＰＵＦ応答Ｘは、エントロピーＨ（Ｘ）を有するとした。いくつかの単純な符号構築（特に小さい次元ｋの符号、たとえば、反復符号）について、ノイズ低減データの公開は、より正確に計算されるものとしてよく、より厳密な上限が決定され得る。
【００７４】
符号パラメータ（ｎ，ｋ）は、符号に対する必要な誤り訂正能力によって決定されることに留意されたい。より大きい誤り訂正能力は、典型的には、より低い率ｋ／ｎの符号を生み出す。多くの誤りを訂正することができる必要のある符号は、ｎ＞＞ｋを有し、したがって、ノイズ低減データ公開上限（ｎ−ｋ）は、非常に大きくなる。その結果、そのような符号に対する実効ノイズ低減データ公開は、典型的には、非常に高くもなり、その結果、鍵抽出に対する残っているエントロピーはほとんどないか、または全くないことすらある。残念なことに、バイアスはＨ（Ｘ）を小さくし、したがって、残っているエントロピーに対する下限、すなわち、Ｈ（Ｘ）−（ｎ−ｋ）は０に近くなるか、または負にすらなり得る。これは、明らかに、鍵漏洩問題を示している。
【００７５】
符号オフセット方法の代替となる、ノイズ低減データを構築する方法がある。たとえば、ＰＵＦ出力は、誤り訂正符号によりパリティビットが計算されるデータビットとしてみなされ得る。パリティビットは、ノイズ低減データとして格納される。ＰＵＦ応答を再構築するために、格納されているパリティビットとともに同じパリティビットが計算され、格納される。パリティビットの差から、第１のノイズのあるＰＵＦ応答ビットと第２のノイズのある応答ビットとの間の差が、復号されるものとしてよく、第１のＰＵＦ応答は、第２のＰＵＦ応答をしかるべく訂正することによって再構築され得る。この構築は、ときにはシンドローム構築ヘルパーデータ（Ｓｙｎｄｒｏｍｅ−ｃｏｎｓｔｒｕｃｔｉｏｎ  ｈｅｌｐｅｒ  ｄａｔａ）と称される。これは、バイアス除去と組み合わされ得る。たとえば、パリティビットは、保持としてマークされているビットについて計算され得る。再構築時に、パリティビットは、保持としてマークされている第２のＰＵＦ応答のビットに付加され得る。
【００７６】
電子暗号デバイスの実施形態において、バイアス除去ユニットは、最初に、ノイズ低減データを計算する前に、たとえば、それを登録する前に、場合によってバイアスされているＰＵＦ応答をバイアス除去する。バイアス除去演算は、第１のＰＵＦ応答の長さ縮小に匹敵する、ＰＵＦ応答の特定のエントロピー損失を引き起こす。これは、バイアス除去損失と呼ばれ得る。しかしながら、結果として得られるバイアス除去されたＰＵＦ応答を登録することによって、ＰＵＦ応答におけるバイアスによるさらなる鍵漏洩をもはや必要としない。概念的には、ＰＵＦ応答におけるバイアスによるエントロピー低減は、バイアス除去損失によって吸収され、その結果、応答バイアスによる鍵漏洩は、低減されるか、または取り除かれる、と言える。
【００７７】
バイアスが、低減された応答エントロピーの唯一の原因であると仮定した場合、バイアス除去されたＰＵＦ応答は、完全エントロピーを有することができ、何であれ鍵漏洩はなくなる。しかしながら、バイアス以外の、低減されたエントロピーの他の原因、たとえば、ビット相関があり得る。バイアスは、ＰＵＦ応答におけるＰＵＦ応答におけるエントロピー低減の重要な原因のように見える。
【００７８】
ＰＵＦ応答のビットを破棄するのにコストがかかる。このコストは、バイアス除去損失と称され、ノイズ低減データ公開による損失の上に来る。ＰＵＦのサイズ、たとえば、応答ビットの数は、この追加の損失を補償するためにしかるべく増やす必要があり得る。バイアス除去損失は、バイアスによるエントロピー低減のみと比べて著しく大きくなり得ることに留意されたい。たとえば、バイアス除去をすでにバイアスしていない応答に適用するときに、バイアスによるＰＵＦ応答のエントロピー低減は０であるが（すでにバイアスしていないので）、バイアス除去損失は、典型的には０よりも大きくなる。
【００７９】
図４ａは、電子暗号デバイスの一実施形態の一例における登録フェーズを示す略図である。図４ｂは、電子暗号デバイスの一実施形態の一例における再構築フェーズを示す略図である。図４ａおよび４ｂを参照しつつ開示されている方法は、電子暗号デバイス１０１または１００の実施形態によって実行され得る。
【００８０】
図４ａには、たとえば、ＰＵＦ１１０によって生成される、第１のＰＵＦ応答４１２が図示されている。ＰＵＦ１１０は、バイアスされる、たとえば、１および０ビットの異なる確率を有し、ノイズがある、たとえば、複数回チャレンジされたときにわずかに異なる応答を発生するものとしてよい。
【００８１】
第１のノイズのあるビット列４１２は、一連のビットペアとしてみなされ得る。これは、一連の波括弧によって図４ａ内で示されている。
【００８２】
便宜上、ビット列内のビットは、たとえば、ビット列内のビットに、たとえば１から始まる整数を割り当てることによって、インデックスに関連付けられ得る。第１の応答は、同じビットペアｉにおいて２ｉ−１および２ｉのビットインデックスを有することによって、ビットペアに区分され得る。２つの等しいビットを含むビットペアは、等ビットペアと呼ばれる。２つの等しくないビットを含むビットペアは、不等ビットペアと呼ばれる。ビットペアは、ＰＵＦ応答中で必ずしも連続している必要はない。
【００８３】
バイアス除去ユニット１２０は、第１の一連のビットペア内の不等ビットペアを識別し、第１のノイズのあるビット列内の不等ビットペアを保持としてマークするように配置構成され得る。一実施形態において、バイアス除去ユニットは、バイアス除去データにおいてすべての等ビットペアを破棄としてマークするように配置構成される。それでも、後者は、以下で説明されているように、必要というわけではない。一連のビットペア４１２の下には、不等または等として識別されたビットペアが示されている。保持ビットペアの両方のビットが保持されることに留意されたい。
【００８４】
一実施形態において、第１のＰＵＦ応答のビットは、不等ビットペアを選択し、等ビットペアを破棄することによってバイアス除去される連続したペアに分割される。不等ビットペアは、全体として考えられる。結果は、図４ａに、バイアス除去された第１のＰＵＦ応答４１４として示されている。
【００８５】
バイアス除去された第１のＰＵＦ応答４１４内のビットペアはすべて不等であることに留意されたい。その結果、列４１４のエントロピーは、たとえば、各ペアの第１のビットのみを取ることによって取得されるのと同じである。しかしながら、ビット列４１４は、ノイズ低減ユニットについて選択された誤り訂正符号と組み合わせて考えたときにより良好なノイズ低減が得られるという利点を有する。さらに、バイアス除去されたＰＵＦ応答４１４が、まだ完全なエントロピーのものではないとしても、ノイズ低減データにより結果として生じる鍵漏洩はもはやない。エントロピーは、たとえば、鍵導出関数を使用して、後から濃縮させられ得る。
【００８６】
第１の誤り訂正符号からの１つまたは複数の第１の符号語４１５は、たとえば、ノイズ低減ユニット１３０によって取得される。好ましくは、誤り訂正符号の符号語は、偶数の長さを有する。必要な場合、バイアス除去された応答４１４のいくつかのビットペアは、破棄され得るか、またはバイアス除去された応答４１４は、１つまたは複数の第１の符号語内のビットの数がバイアス除去されたビット列４１４内のビットの数に等しくなるように、たとえば、ゼロビットでパディングされ得る。図４ａに示されている例では、２つの符号語が、長さ４の反復符号から取られる。反復符号は、（ｎ，ｋ）型（４，１）を有する。同じ符号語に属するビットは、破線のボックスで示されている。
【００８７】
反復符号は、非常に高い誤り訂正能力を有し、効率的に復号可能である。しかしながら、他の符号、たとえば、アダマール符号、ＢＣＨ符号なども可能である。
【００８８】
第１の符号語４１５は、ランダム登録シードのビットを符号化することによって、たとえば、誤り訂正符号に関連付けられている誤り訂正符号器を使用してアンコーディングされているたとえば平文、データ語を符号語にマッピングすることによって、生成され得る。いくつかの実施形態では、第１の符号語を、第２の誤り訂正符号から１つまたは複数の第２の符号語のビットを符号化することによって、取得する。第２の符号語は、ランダム登録シードのビットなどを符号化することによって生成され得る。２つの符号を使用することには、誤り訂正に対する高い能力が得られ、さらに効率的な符号化および復号を行える利点がある。
【００８９】
一実施形態において、ノイズ低減データ１４４は、たとえば、ノイズ低減ユニット１３０によって取得され、これは保持としてバイアス除去情報によってマークされた第１のビット列４１２内のビット、たとえば、バイアス除去された列４１４内に示されているビットと１つまたは複数の符号語４１５との間の差を含む。この差は、ＸＯＲ演算によって得ることができる。
【００９０】
しかしながら、バイアス除去情報によって破棄としてマークされている第１のビット列内のビットと第１のノイズのあるビット列内の破棄ビットに対応する１つまたは複数の符号語内のビットとの間の差は、取得されない。ノイズ低減データは、後者の差を含まない。したがって、第１のＰＵＦ応答のバイアスされた部分は漏洩しない。
【００９１】
一実施形態において、ノイズ低減データは、バイアス除去情報によって保持としてマークされている第１のビット列内のビットの連結と１つまたは複数の符号語との間の差を含む。
【００９２】
バイアス除去データとノイズ低減データとを符号化するための方法は多数ある。図４ａは、両方のデータを組み合わせて単一のビット列にするバイアス除去データおよびノイズ低減データ４４０を示している。１つまたは複数の符号語の各ビットは、第１のビット列の保持ビットに対応する。たとえば、１つまたは複数の符号語４１５は、１、２、３、４、５、６、などのビットが第１の応答４１２の１、２、５、６、９、１０などのビットに対応する列を一緒に形成する。保持ビットに対応するビット列４４０におけるインデックスは、同じインデックスを持つ第１のＰＵＦ応答内のビットと前記保持ビットに対応する１つまたは複数の符号語のビットとの間の差を格納する。
【００９３】
たとえば、「ａ」とマークされているビットペアは、列４１２の第１の２つの保持ビットと１つまたは複数の符号語４１５の第１の２つのビットとの間の差に対応する。
【００９４】
破棄されるビットのインデックスを有する列４４０内のビットペアは、すべてゼロのビットペアで埋められるものとしてよい。代替的に、すべて１のペアも使用され得る。たとえば、「ｂ」とマークされているビットペアはすべてゼロである。列４４０内の等ビットペアは、破棄ビットペアをマークする。列４４０の不等ビットペアは、ノイズ低減データを含む。
【００９５】
一実施形態において、組み合わされたバイアス除去およびノイズ低減データ４４０は、元のバイアスされた第１のＰＵＦ応答４１２と同じ長さを有するものとしてよい。
【００９６】
この情報を記録するための代替的方法が多数あり、そのうちのいくつかが図４ａに示されている。たとえば、バイアス除去データ４４２は、１ビットが、たとえば、保持ビットを指し、ゼロビットが破棄ビットを示すビットマスクである。たとえば、バイアス除去データ４４２’は、保持ビットペアのこの場合における、インデックスのリストである。ノイズ低減データ４４４は、ノイズ低減データのみを含むビット列である。ノイズ低減データ４４４は、たとえば列４４２または４４２’を使用して保持ビットが識別された後に使用され得る。わかりやすくするために、ノイズ低減データ４４４は、対応するビットの下に描かれているが、しかしながら、これらは、連結された形態で格納され得る。
【００９７】
バイアス除去データおよびノイズ低減データは、たとえば、ストレージ１４０に格納されるか、または外部に、たとえば、外部サーバ（図示せず）上に格納され得る。
【００９８】
再構築フェーズにおいて、第２のＰＵＦ応答４２２は、第１のＰＵＦ応答４１２を生成した同じＰＵＦによって、たとえば、ＰＵＦ１１０によって、生成される。第２のＰＵＦ応答は、たとえば、ハミング距離を用いた場合に、第１の応答４１２に近く、しかしながら、ある量のノイズがある。第２の応答４２２内のビットのうちのいくつかは、応答４１２と異なる。図４ｂに示されている例の中の異なるビットは、矢印で示されている。
【００９９】
第２のＰＵＦ応答４２２は、ビットペアに区分される。バイアス除去データにおいて破棄としてマークされているビットペアが破棄される。比較のため、データ４４０は、第２の応答４２２の下に図示されており、そこでは、破棄ビットペアを示すゼロビットペアはずらされている。保持としてマークされているビットは、バイアス除去された第２のＰＵＦ応答４２３を形成する。
【０１００】
バイアスは、たとえば、環境、たとえば温度の変化により、第１の応答の生成時と第２の応答の生成時とでわずかに異なり得ることに留意されたい。これは、しかしながら、ノイズ低減データが第２のＰＵＦ応答に対して生成されていないのであまり重要なものでなく、したがって追加の鍵漏洩が生じない。
【０１０１】
バイアス除去されたＰＵＦ応答４２３のビットペア、すなわち、保持としてマークされているビットは、ノイズ低減データとＸＯＲされ、その結果、ノイズのある符号語４２４が形成される。正規化器１５２は、バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットにノイズ低減データを追加、たとえばＸＯＲ、することができる。
【０１０２】
ノイズのある符号語４２４は、ノイズが加えられた１つまたは複数の第１の符号語４１５である。ノイズが存在しなかった場合、ノイズのある符号語４２４は、符号語４１５と同一である。図４ｂの例では、両方の符号語が誤りを含んでいる。
【０１０３】
ノイズのある符号語４２４は、たとえば、誤り訂正器１５４によって訂正され、訂正された符号語４２６を取得し得る。誤り訂正器１５４は、訂正された符号語４２６を復号し、１つまたは複数の復号された符号語４２７を取得することを続けることも可能である。この場合、復号された符号語は、これがｋ＝１の符号であるので、符号語毎に単一のビットである。しかし、この復号ステップは、必要というわけではない。
【０１０４】
一実施形態において、鍵は、復号された符号語４２７として直接みなすことも可能である。しかしながら、鍵導出関数を、復号された符号語４２７、または訂正された符号語４２６のいずれかに適用することが好ましい。後者は、鍵導出ユニット１５６によって実行され得る。
【０１０５】
代替的に、復号されたビット４２７は、連結符号構築の場合に上位レベルの符号語の符号ビットとみなされ得る。その場合、反復符号語のハミング重みは、上位レベルの復号器に対する軟判定情報としても使用され得る。
【０１０６】
図４ａおよび４ｂを参照しつつ説明されている実施形態の利点は、バイアスされたＰＵＦ応答による鍵漏洩は、ノイズ低減データが計算される前にＰＵＦ応答がバイアス除去されるので取り除かれたという点である。したがって、このバイアス除去ファジー抽出器は、鍵漏洩なしの、または少なくとも鍵漏洩が低減されて、バイアスされたＰＵＦからの鍵生成に使用され得る。
【０１０７】
別の利点は、不等ビットペアの両方のビットが考慮されるという事実により効率が改善されることである。一目では、これは、結果として得られるバイアス除去されたＰＵＦ応答が実際にはバイアスしていないので、直観に反しているが、各ビットペアのパリティは奇数なのでもはや独立したビットを有しない。この結果、バイアス除去されたＰＵＦ応答に対するエントロピーが低減され、実効エントロピーは、応答の長さの半分にすぎない。古典的なフォンノイマンバイアス除去は、選択されたペアの第２のビットも破棄することによってこれを回避してしまう。
【０１０８】
しかしながら、ここで、ノイズ低減データ公開とバイアス除去損失のインテリジェントな組合せが効果を現す。バイアス除去された応答内のビットペアのパリティは、公然と知られているという事実は、この情報が反復符号オフセットノイズ低減データを通じてとにかく公開されるので問題にならない。反復符号オフセットはすでに偶数個のＰＵＦ応答ビットの各組合せのパリティを公開していることに留意されたい。安全性の点で見ると、仮想攻撃者は、とにかくノイズ低減データから同じ情報を得るので、これらのパリティに関する知識を利用して生成された鍵素材を攻撃することはできない。ファジー抽出器によって提供される鍵素材は、所与のノイズ低減データの公開について安全なので、所与のビットペアパリティの公開によるこのエントロピー低減について安全なままである。したがって、保持ビットペアの両方のビットを使用することによって追加のエントロピー損失はないが、誤り訂正は改善される。
【０１０９】
バイアス除去されたＰＵＦ応答内のエントロピーは、鍵の中に濃縮される、たとえば、鍵導出関数によって、たとえば、保持ビットの長さの半分以下に濃縮され得る。
【０１１０】
符号オフセットノイズ低減データは、とにかくビットペアパリティ情報を公開するので、古典的なフォンノイマンバイアス除去が行うように不等ペアの第２のビットを破棄することによってＰＵＦ応答エントロピーから２回目に減算される必要はない。したがって、バイアスの同じレベルについて、ここに提示されているソリューションは、古典的なフォンノイマンバイアス除去と比較したときにバイアス除去されたビットの数の２倍を保持する。たとえば、元のＰＵＦ応答がすでにバイアスしていないときに、古典的なフォンノイマンバイアス除去は、平均してビットの１／４（３／４の実効バイアス除去損失）を保持するが、図４ａに示されている実施形態ではビットの１／２（１／２の実効バイアス除去損失）を保持する。実効バイアス除去損失のこの低減は、実際のバイアス除去損失の一部がノイズ低減データ公開と重なり合い、したがってもはや実効損失はないので、可能である。
【０１１１】
図４ａおよび４ｂの実施形態は、バイアスされたＰＵＦ応答に対する鍵漏洩問題に効果的に対処し、バイアス除去損失をノイズ低減データ公開とインテリジェントに組み合わせてその結果著しい改善をもたらす。
【０１１２】
ノイズ低減ユニットは、登録フェーズにおいてバイアス除去されたＰＵＦ応答４１４に対するノイズ低減データを決定するように配置構成されるものとしてよく、誤り訂正器は、前記ノイズ低減データに依存して再構築フェーズにおいてバイアス除去されたＰＵＦ応答４２３内のビットのノイズを低減するように配置構成され得る。たとえば、ノイズ低減データは、たとえば、正規化器によって、バイアス除去されたＰＵＦ応答をノイズ符号語にマッピングするために使用され得る。
【０１１３】
図５ａは、電子暗号デバイスの一実施形態の一例における登録フェーズを示す略図である。図５ｂは、電子暗号デバイスの一実施形態の一例における再構築フェーズを示す略図である。図５ａおよび５ｂを参照しつつ開示されている方法は、図４ａおよび４ｂを参照しつつ説明されている方法に基づいており、これらは、電子暗号デバイス１０１または１００の実施形態によって実行され得る。
【０１１４】
図４ａのように、登録は、一連のビットペアとみなされる、第１のＰＵＦ応答５１２を生成するステップを含む。不等ビットペアは、たとえば、バイアス除去ユニット１２０によって識別され、保持としてマークされる。不等ビットペアは、参照番号５１３ａで不等号によりマークされている。等ビットペアのうち、第１および第２の等ビットペアは、たとえば、バイアス除去ユニット１２０によって、第１の等ビットペアが第２の等ビットペアの逆である、一連のビットペア内で識別される。
【０１１５】
たとえば、バイアス除去ユニット１２０は、第１のＰＵＦ応答５１２内の第１の等ビットペアを識別し、第１のＰＵＦ応答５１２内の次の等ビットペアを識別するように配置構成され得る。第１の等ビットペアが次の等ビットペアに等しい場合、両方とも破棄としてマークされ、そうでない場合、少なくとも第１の等ビットペアは、保持としてマークされる。バイアス除去ユニット１２０は、次の２つの等ビットペアを繰り返し見つけて、等しい場合にそれらを両方とも破棄し、２つのペアが不等である場合に少なくとも第１のペアを保持するように配置構成され得る。
【０１１６】
一実施形態において、バイアス除去は、複数ラウンドで実行され、第１ラウンドで、不等ビットペアは保持としてマークされ、等ビットペアは破棄としてマークされる。第２ラウンドで、前の回に破棄された等ビットペアは、次に、バイアス除去の第２ラウンドで再考察されている。破棄ビットは、四つ組みにグループ分けされる。（０，０，１，１）および（１，１，０，０）の形の四つ組みが保持される、保持としてマークすることによってバイアス除去されたＰＵＦに追加されるものとしてよく、（０，０，０，０）および（１，１，１，１）の形の四つ組みは、依然として破棄される。
【０１１７】
これでバイアス除去されたＰＵＦ応答はペアと四つ組みのリスト（ランダムな順序の）からなるので、偶数の長さの反復符号語の終わりは四つ組みの終わりとアラインメントしないことがあり得る。しかしながら、この実施形態の安全性は、単一の選択されたグループ（ペア、四つ組み、．．．など）のビットが同じ符号語（反復符号語など）内で常に使用される場合に改善される。これは、ビット選択（たとえば、四つ組み）が異なる符号語にわたって使用される場合に、攻撃者がこのことを利用してこれらの符号語上のパリティを学習し得るからである。反復符号の場合、攻撃者は、たとえば、２つの連続する反復符号語が同じであるか、または異なるかを学習し得る。これは、エントロピー損失、したがって鍵漏洩を引き起こす。
【０１１８】
単一の選択されたグループ（ペア、四つ組み、．．．）のビットが同じ符号語内で常に使用されることを確実にするために、場合によっては、反復符号語の落ちるグループのトレーリングビットは破棄され得る。図５の例では、これは、例示的なＰＵＦ応答の終わり（「ｅ」）で生じる：最後の選択された四つ組みについて、現在の反復符号語に第１のビットペアのみが使用され得る。この場合、その四つ組みの最後のビットペアは、破棄されるべきであり、これは次の反復符号語の開始としては使用できない。
【０１１９】
一実施形態において、ビットの不等ペアの両方のビットが保持としてマークされる。しかしながら、一実施形態において、等ビットペアの中のペアの第２の等ビットペアは、第１および第２のビットペアが１つまたは複数の符号語のうちの同じ符号語との差において使用される場合にバイアス除去データによって保持として、および他の場合には破棄としてのみマークされる。
【０１２０】
第１の符号語５１５は、図５ａに示されている。第１の符号語のビットは、第１の応答５１２の対応する保持ビット、すなわち、差が計算されるビットとアライメントされる。
【０１２１】
第１の応答５１２内の第１の２つの等ビットペアは、「ｃ」で参照される。両方とも等しい、この場合、両方とも０であるので、両方とも破棄される。第２の２つの等ビットペアは、「ｄ」で参照され、２つのペアは不等であり、したがって少なくとも第１のペアが保持される。第２のペアは、第１のペアと同じ符号語内のビットと対応するので、第２のペアも保持される。第３のペアは、「ｅ」で参照され、２つのペアは不等であり、したがって少なくとも第１のペアが保持される。第２のペアは、第１のペアと異なる符号語内のビットと対応するので、第２のペアは破棄される。バイアス除去された第１のＰＵＦ応答５１４内の「ｆ」、すなわち、第１のＰＵＦ応答５１２の保持ビットでは、等ビットペアの保持ペアの４つのすべてのビットは、同じ符号語内に入る場合に保持されるが、「ｇ」では、第１のビットペアのみが、入らない場合に保持されることに留意されたい。２つのゼロビットは、第１の応答５１２の最終的な２つのビットが、たとえば、より多くの符号語が続く場合に破棄されることを指示するためにバイアス除去データ５４２に付加され得る。
【０１２２】
グループのトレーリングビットを破棄する代わりに、グループの順序が変更されてよく、たとえば、グループ（ペア、四つ組み、またはセット）の終わりが常に反復符号語終わりとアライメントするようにすることが可能である。たとえば、バイアス除去ユニット１２０は、第１のＰＵＦ応答１１０内のビットの、請求項において第１の転置とも称される、転置を選択し、その転置をバイアス除去データ１４２の一部として格納することができる。鍵を再構築するときに、転置は、最初に、たとえば、再構築ユニットによって、第２のＰＵＦ応答に適用され、その後、バイアス除去およびノイズ除去が本明細書で説明されているように進行する。たとえば、前記転置は、ペアよりも大きいグループ、たとえば四つ組みを符号語の先頭に置くものとしてよく、これは、トレーリングビット（図に示されていない）を回避する。一実施形態において、バイアス除去ユニットは、第１および第２の等ビットペアが１つまたは複数の符号語の同じ符号語との差で使用されるように第１の一連のビットペアの転置を決定するように配置構成される。転置は、第１のＰＵＦ応答のより多くのビットが、ノイズ低減データを生成し、したがってバイアス除去損失を減らすために使用できるという利点を有する。
【０１２３】
ビットペアまたは四つ組みを識別する上記のバイアス除去方法は、２ラウンドよりも多いラウンド数に拡張され得る。たとえばより多くのラウンドのために、八つ組み（８ビット）に働く第３ラウンドが、直接的に、追加され得る。これは、バイアス除去損失をなおいっそう低減する。しかしながら、より多くのラウンドを追加する追加の利得は、たちまち非常に小さくなる。たとえば、第１ラウンドは、不等ビットペアを識別し得る。第２ラウンドは、残りのペアの間で、不等四つ組みを識別し得る。第３ラウンドは、第２ラウンドの不等八つ組みの後にまだ保持されていないビットペア間を識別し得る。
【０１２４】
たとえば、一実施形態では、バイアス除去ユニットは、一連のビットペア内の等ビットペアの第１および第２のセットを識別するように配置構成され、第１および第２のセットは同じサイズを有し、第１のセット内のすべての等ビットペアは同じであり、第２のセット内のすべての等ビットペアは同じであり、第１のセットのビットペアは第２のセット内のビットペアの逆であり、バイアス除去データは第１のセットの少なくとも等ビットペアを保持としてマークする。
【０１２５】
追加の選択の結果は、バイアス除去された第１のＰＵＦ応答５１４である。等ビットペアのいくつかが保持されるので、第１のＰＵＦ応答は、図４ａの方法が有しているのよりも小さいバイアス除去損失を有する。図４ａのように、第１の符号語５１５が取得される。図５ｂの例では、６ビット反復符号が使用される。バイアス除去データ５４２の可能な表現が、図５ａに示されている。バイアス除去データ５４２は、１ビットを使用して、破棄ビットを示すために保持ビットおよびゼロビットを指示する。１つまたは複数の符号語５１５の各ビットは、第１のＰＵＦ応答５１２内の保持ビットに対応する。ノイズ低減データ５４４は、保持ビットと１つまたは複数の符号語５１５の対応するビットとの間の差を含む。ノイズ低減データ５４４は、第１の応答ビットと符号語ビットとの間の差を表すノイズ低減データ５４４内のビットのインデックスが第１の応答内の前記第１の応答ビットのインデックスと同じであるように格納され得る。データ５４４内の残りのビットは、任意、たとえば、ランダムに埋められる、ゼロに設定される、空のままにされる、などとしてよく、図５ａでは、これらは０で埋められる。
【０１２６】
図４ａおよび５ａにおいて、１つまたは複数の符号語（たとえば、４１５、５１５）の各ビットは、第１のＰＵＦ応答内の保持ビットに対応することに留意されたい。ノイズ低減データは保持ビットと対応する符号語ビットとの間の差を含む。
【０１２７】
図５ｂによって示されている再構築フェーズは、図４ｂの場合と大部分同じである。第２のＰＵＦ応答５２２は、たとえば、ＰＵＦ１１０から取得され、登録された応答に関するビット誤りは、説明を目的として矢印でマークされている。この応答５２２から、保持ビットは、バイアス除去データを使用して選択され、それによりバイアス除去された第２のＰＵＦ応答５２３を取得する。バイアス除去された第２のＰＵＦ応答５２３は、ノイズ低減データに追加され、ノイズのある符号語５２４を取得する。図４ａのように、訂正された符号語は復号され、復号された符号語５２７を取得することができる。代替的に、符号語は、直接的に、たとえば、これらをハッシュすることなどによって、使用され得る。
【０１２８】
バイアス除去データ５４２、４４２、ノイズ低減データ５４４、４４４、ただし、組み合わされたデータ４４０も、かなり高いレベルの構造を有し、その結果より効率的な処理および通信を行えるように圧縮され得ることに留意されたい。
【０１２９】
たとえば、反復符号が第１の符号に使用される場合、およびビットペアが第１ラウンドのバイアス除去によって選択される場合、対応するノイズ低減データビットペアは、常に、奇数パリティを有し、したがって単一ビットによって表されるものとしてよく、その結果、そのペアに対して５０％の圧縮が行われ得る。四つ組みの符号オフセットノイズ低減データについても類似の圧縮が可能である。
【０１３０】
図５ａおよび５ｂによって示されているバイアス除去は、図４ａおよび４ｂで例示されている方法のすべての利点を有し、さらに、バイアス除去損失がさらに低減されるので改善された効率を有する。この低減は、基本的な抽出器によって破棄されたビットペアのいくつかが現在保持されているという事実に由来する。
【０１３１】
第２ラウンドにおける選択された四つ組みは、ここでもまた、単一ビットのみではなく、全体として使用され得ることに留意されたい。すなわち、等ビットペアの保持ペアのすべてのビットが保持としてマークされる。ビットの各選択された四つ組みは、効果的に、情報の１ビットを含むだけであり、したがって、３つのビットのエントロピー低減がある。しながら、この低減は、ここでもまた、反復符号オフセットノイズ低減データによって公開される情報と完全に重なり合い、したがって２回目に減算される必要はない。言い替えれば、選択された四つ組みについても、バイアス除去損失および反復符号オフセットノイズ低減データ公開は組み合わされる。
【０１３２】
図６ａは、電子暗号デバイスの一実施形態の一例における登録フェーズを示す略図である。図６ｂは、電子暗号デバイスの一実施形態の一例における再構築フェーズを示す略図である。図６ａおよび６ｂを参照しつつ開示されている方法は、電子暗号デバイス１０１または１００の実施形態によって実行され得る。
【０１３３】
図４ａおよび５ａの方法は、特別な攻撃シナリオに対する脆弱性を有し、われわれはこれを多重登録公開問題と称する。
【０１３４】
多重登録公開問題は、同じＰＵＦがバイアス除去符号オフセットファジー抽出器において複数回使用されるときに生じる。したがって、登録されたＰＵＦ応答は、いくつかのランダムビット誤りまで等しい。たとえば、攻撃者は、バイアス除去およびノイズ低減データが同じＰＵＦについて２回計算されるようにデバイスを操作する。
【０１３５】
多重登録公開問題の根本の原因は、バイアス除去ステップが確率論的である、すなわち、同じＰＵＦを２回バイアス除去すると、その結果、特定の時点までランダムである２つの異なるバイアス除去選択がなされる、という事実であり、異なるインデックスを有する、異なるビットが保持される。バイアス除去選択のランダム性は、ＰＵＦ応答上のノイズによって引き起こされる。この確率論的性質により、両方の登録におけるバイアス除去されたＰＵＦ応答は、元のＰＵＦ応答の異なる選択に基づき得る。その結果、両方の登録におけるバイアス除去損失およびノイズ低減データ公開も、元のＰＵＦ応答エントロピーの異なる部分を公開する。その結果、ノイズ低減データおよび両方の登録のバイアス除去損失によって公開される組み合わされた情報は、１つの単一の登録の情報よりも大きい。
【０１３６】
多重登録問題は、いくつかの実施形態において生じる必要はない。たとえば、登録は、安全な場所、たとえば、そこでしか利用できない何らかの機器を必要とする場所で行われ得る。たとえば、デバイスは、同じＰＵＦに基づく複数の登録を防ぐように配置構成され得る。これは、ＰＵＦの登録状態を格納することによって、たとえば、ワンタイムプログラマブル（ＯＴＰ）メモリ素子を用いて行われ得る（たとえば、ヒューズが、ＰＵＦが登録されるときに切れる）。
【０１３７】
図６ａおよび６ｂには、多重登録公開問題に対する低減された脆弱性を有するＰＵＦ応答をバイアス除去する実施形態が示されている。図６ａおよび６ｂの実施形態は、図４ａおよび４ｂの実施形態に基づく。
【０１３８】
図６ａには、一連のビットペアに区分されるものとしてみなされる、第１のＰＵＦ応答６１２が示されている。ビットペア内で、等ビットペアおよび不等ビットペアが、たとえば、バイアス除去ユニット１２０によって識別される。不等ビットのペアは保持され、等ビットのペアは破棄される。保持ビットペア内の両方のビットが保持される。
【０１３９】
図４ａおよび５ａと異なり、廃棄ビット位置は、登録時に役割を果たし続ける。概念的には、等ビットの破棄ペアは、消去記号（ε）のペアによって置き換えられる。消去は、特別な第３の記号（０および１とは異なる）としてみなされ得る。以下では、消去記号を実装するための様々な方法が説明されている。たとえば、記号０、１、およびεは、各々２つのビットで符号化され得る。代替的に、消去記号の効果は、消去記号位置などを示すインデックスのリストを格納することによって実装され得る。
【０１４０】
その結果得られるバイアス除去された第１のＰＵＦ応答６１４は、図６ａに示されている。その結果得られるバイアス除去された第１のＰＵＦ応答６１４は、不等ビットのペアおよび消去記号のペアを含む。バイアス除去されたＰＵＦ応答６１４は、元のバイアスされたＰＵＦ応答６１２と同じ長さであるが、ただし、バイアス除去されたＰＵＦ応答６１４が２つではなく３つの記号を有するより大きいアルファベットにわたることを考慮する。
【０１４１】
第１の誤り訂正符号からの１つまたは複数の第１の符号語６１５は、たとえば、ノイズ低減ユニット１３０によって取得される。図４ａおよび５ａについて指摘されているように、第１の誤り訂正符号は、第２の誤り訂正符号から１つまたは複数の第２の符号語のビットを符号化することによって取得され得る。この後者のオプションは、図６ａで使用されており、図６ｃおよび６ｄを参照しつつ以下でさらに説明される。図６ａにおいて、ここでもまた、反復符号が一例として使用されている。しかしながら、他の誤り訂正符号も、代わりに使用され得る。第１の誤り訂正符号は、好ましくは、偶数長符号であり、（ｎ，ｋ）表記で、ｎは偶数である。奇数符号は、たとえば、各符号語についてパディングビットをバイアス除去された列６１４に追加すること、または各符号語の１ビットを破棄することなどによっても使用され得ることに留意されたい。パディングビットは、ゼロであってもよい。
【０１４２】
図６ａにおいて、第１のＰＵＦ応答６１２およびバイアス除去されたＰＵＦ応答６１４の各ビットは、１つまたは複数の符号語６１５のビットに対応する。これは、図４ａおよび５ａにおいて重要な相違であり、そこでは、第１のＰＵＦ応答の保持ビットの間に対応関係のみがあったが、図６ａでは、第１のＰＵＦ応答の、保持と破棄の両方の、すべてのビットと１つまたは複数の符号語６１５のビットとの間に対応関係がある。これは、第１のＰＵＦ応答６１２のいかなるビットが、同じ符号語において、異なる登録にまたがっても、使用されることを意味する。
【０１４３】
組み合わされているバイアス除去およびノイズ低減データは、バイアス除去された第１のＰＵＦ応答６１４と１つまたは複数の符号語６１５との間の差を決定することによって取得される。図６ａの例では、符号は、長さ６の反復符号であるが、他の誤り訂正符号、たとえば、アダマール、ＢＣＨなどが適用可能である。
【０１４４】
組み合わされているバイアス除去およびノイズ低減データは、バイアス除去されたＰＵＦ応答６１４と１つまたは複数の符号語６１５との間の差を取得する、たとえば、それらのＸＯＲ演算を実行することによって取得される。ＸＯＲ演算は、追加の消去記号εを許容するように拡張される。われわれは、ときには拡張されたＸＯＲをε−ＸＯＲ演算と称する：０および１にのみ作用するときに、ε−ＸＯＲ演算は、ＸＯＲ演算と同じであるが、オペランドの１つがεであるときに、結果は、常に、他のオペランドに関係なくεとなる。したがって、ε−ＸＯＲ（０，０）＝ε−ＸＯＲ（１，１）＝０、およびε−ＸＯＲ（０，１）＝ε−ＸＯＲ（１，０）＝１、およびε−ＸＯＲ（ε，０）＝ε−ＸＯＲ（ε，１）＝εである。
【０１４５】
偶数長誤り訂正符号が使用される場合、好ましければ、常に、自然数個のバイアス除去されたＰＵＦ応答のペアがある（トレーリングビットはない）。図６ａにおいて、バイアス除去およびノイズ低減データ６４０は、バイアス除去されたＰＵＦ応答６１４および１つまたは複数の符号語６１５に対するε−ＸＯＲ演算の結果を示している。
【０１４６】
１つまたは複数の符号語の各符号語がビットの完全なセットと組み合わされるように図４ａおよび５ａにおいて行われているように第１のＰＵＦ応答からビットをスキップする代わりに、図６ａでは、ビットは、消去記号によって示されているように、破棄ビットに対応している場合に符号語から消去される。図６ａによる実施形態において、第１のＰＵＦ応答のビットと、１つまたは複数の符号語のビットとの間に固定された一対一の対応関係があり、ビットを破棄または保持としてマークしても、この関係は変化しない。
【０１４７】
組み合わされたバイアス除去およびノイズ低減データ６４０は、元の（バイアスされた）ＰＵＦ応答６１２と同じ長さを有する。２進値形式の０、１、およびε−記号の表現は、列６４０を符号化するために使用され得る。列６４０内の構造により、これは、演算および通信が容易であるように望ましいときにかなり圧縮され得る。圧縮は、列６４０に特有の圧縮形式を使用してよいが、任意の可逆圧縮アルゴリズムが使用され得る。
【０１４８】
消去記号は、概念的には、理解が比較的容易であるが、それにもかかわらず、追加の記号の使用を回避することは実施形態において可能である。たとえば、図６ａは、組み合わされたノイズおよびバイアス除去データ６４０の代替形態として、バイアス除去データ６４２およびノイズ低減データ６４４を示している。
【０１４９】
バイアス除去データ６４２は、第１のノイズのあるビット列内のどのビットが保持または破棄としてマークされているかを示す。図６ａの場合、バイアス除去データ６４２は、ビットマスクであり、そこでは、１ビットが保持ビットを指し、０ビットが破棄ビットを示す。この場合、破棄ビットは、ε記号としてみなされ得る。ノイズ低減データ６４４は、保持ビットと１つまたは複数の符号語の対応するビットとの差を含む。図６ａの例では、ノイズ低減データ６４４は、保持ビットおよび対応するビットとの差を第１のノイズのある応答６１２内の保持ビットのインデックスと同じインデックスとして格納し、破棄ビットに対応するノイズ低減データ６４４内のビットは、任意に、この場合、０で埋められるか、または空のままにされてよい。ノイズ低減データ６４４は、符号語ビットと破棄ビットとの間の差を含まない。
【０１５０】
一実施形態において、第１のノイズのあるビット列内のビット、１つまたは複数の符号語内のビット、およびノイズ低減データ内のビットは、すべて、インデックスを有する。インデックスを目的として、１つまたは複数の符号語は、たとえば、符号語を連結することによって、１つの長い列とみなされる。すべての３つの列は、同じ長さであり得るか、または、たとえば、第１のノイズのあるＰＵＦ応答をパディングすることによって、同じ長さにされ得る。インデックスは、都合よく、１からｎなど値をとり得る。第１のＰＵＦ応答内のビットと１つまたは複数の符号語の同じインデックスを持つビットとの間の差は、ノイズ低減データに、たとえば、同じインデックスを持つビットのところに格納される。第１のＰＵＦ応答内の破棄ビットと同じであるインデックスを持つノイズ低減データ内のビットは、０、１に設定されるか、またはランダムに埋められるなど操作が行われ得る。
【０１５１】
バイアス除去およびノイズ低減データは、次のように取得され得る：第１のＰＵＦ応答内の各ビットペアについて、ビットペアを等または不等として識別する。ビットペアが等しい場合、ビットペアをバイアス除去データ内で破棄としてマークする。ビットペアが不等である場合、第１のＰＵＦ応答内のビットペアと１つまたは複数の符号語内の対応するビットペアとの間の差を計算する、たとえば、ＸＯＲを実行し、その差をノイズ低減データ内に、たとえば、対応する位置にあるビットペアのところに格納する。たとえば、バイアス除去データ、たとえば、バイアス除去データ６４２およびノイズ低減データ、たとえば、ノイズ低減６４４は、次のアルゴリズム（擬似コードで表されている）によって取得され得る。
【０１５２】
ｉ＝１から第１のＰＵＦ応答におけるビットペアの数まで
ビットペアｉが等しい場合、ビットペアｉをバイアス除去データ内で破棄としてマークする
そうでなければ、第１のＰＵＦ応答内のビットペアｉと１つまたは複数の符号語内のビットペアｉとの間の差、たとえばＸＯＲを計算し、その差をノイズ低減データ内に格納する
次に
ビットペアｉは、ビット２ｉ−１および２ｉ（１から開始してカウントする）とみなされてよい。第１のノイズのあるビット列内のビットは、同じインデックスを有する１つまたは複数の符号語内のビットに対応し得る。ビットをノイズ低減データ内に格納するステップは、差分ビットペアを付加することによって行われ得る。代替的に、ビットをノイズ低減データ内に格納するステップは、差分を対応するビットペア位置に格納することなどによって行われ得る。ビットペアを破棄としてマークすることは、いろいろな仕方で、たとえば、インデックスをリスト内に列挙すること、ビット、またはビットマスク内のビットペアをマークすることなどによるものとしてよい。
【０１５３】
再構築段階は、図６ｂに従い、次のように動作し得る。図示されているのは、第２のＰＵＦ応答６２２であり、そこでは、登録ＰＵＦ応答６１２との差は、矢印で示されている。第２のＰＵＦ応答６２２の下で、登録段階で生成されたバイアス除去およびノイズ低減データ６４０は、ここでもまた示されている。
【０１５４】
ノイズのある第２のＰＵＦ応答６２２は、消去記号を考慮して、ここでは、バイアス除去およびノイズ低減データ６４０とのε−ＸＯＲを使用することによって追加され、その結果、バイアス除去され、正規化された第２のＰＵＦ応答６２４となる。バイアス除去された第２のＰＵＦ応答６２４は、バイアス除去およびノイズ低減データ６４０内の消去記号に対応する各ビットに対する消去記号εを含む。
【０１５５】
ビット列６２４は、ノイズと消去の両方による影響を受ける１つまたは複数の符号語とみなされ得る。誤り訂正符号内の消去記号は、位置が知られているノイズのタイプとしてみなされ得る。ノイズの影響のみを受けた符号語が訂正された図４ｂおよび５ｂの状況のように、ノイズおよび消去の影響を受けた符号語も、訂正され得る。いかなる符号の場合のように、訂正は、ノイズおよび消去の量が多すぎない場合にのみ可能である。より高いレベルのバイアスまたはノイズを持つＰＵＦは、たとえば、より高い最小距離（ｄ）を有する、より強力な誤り訂正符号を使用することによって訂正され得る。
【０１５６】
図６ａおよび６ｂの例では、第１の符号語は、長さ６の反復符号である。反復符号は、比較的容易な訂正アルゴリズムを可能にするが、より複雑な誤り訂正符号もノイズおよび／または消去の存在下で訂正を可能にすることに留意されたい。反復符号について、符号語は、０と１のどちらが非消去記号の間で過半数であるかをカウントすることによって復号され得る。過半数がない場合、符号語は、復号され得ない、すなわち、０または１復号記号は等しく可能性が高いことに留意されたい。必要ならば、元の符号語６１５は、必要ならば、復号したものを符号化することによって復元され得る。
【０１５７】
各符号語について特定の１つの復号が決定されるこの後者のタイプの復号は、硬判定復号と呼ばれる。硬復号符号語６２７は、図６ｂに示されている。第２の符号語について、硬判定は不正であったことに留意されたい。第３の符号語について、０および１は両方とも等しく可能性が高い。硬判定が必要な場合、ランダムな選択が行われてもよい。硬判定復号で偶然に第３の符号語に対して０を選択した場合、その結果得られる第２の符号語（０，０，０，１）は、正しく（０，１，０，１）に訂正されることに留意されたい。しかしながら、硬判定復号で偶然に１を選択した場合、誤りの数は、訂正する第２の誤り訂正符号に対して大きすぎる。より強力な誤り訂正符号がこれらの誤りを防ぐことができたが、より低い符号レート（分数ｋ／ｎ）と引き換えにあり得る。
【０１５８】
図６は、図４ａおよび５ａで示されている実施形態についても述べられた、誤り訂正符号の別の使用を示している。
【０１５９】
図６ｃに示されているのは、すべての符号語６５０がリストされている、第２の誤り訂正符号である。この例示的な符号は、（ｎ，ｋ，ｄ）型（４，２，２）符号である。たとえば、第２の誤り訂正符号は、リードソロモン誤り訂正符号であってよい。図６ｃに示されているのは、シード６３０とも呼ばれる、符号語の復号である。
【０１６０】
登録時に、１つまたは複数のランダムな符号語は、第２の誤り訂正符号６５０から選択され得る。代替的に、１つまたは複数のランダムシードが、シード６３０から選択され、第２の誤り訂正符号に従って符号化され得る。図６ａの場合、１つまたは複数の（この場合１つの）符号語（０，１，０，１）を取得するためにシード（０，１）がランダムに選択され、符号化された。１つまたは複数の第２の符号語のビットは、第１の誤り訂正符号に従って符号化される。長さ６の反復符号に従ってビット（０，１，０，１）を符号化するステップは、１つまたは複数の第１の符号語６１５をもたらす。
【０１６１】
復号時に、この連結符号構築は、有利に使用され得る。ノイズのあるおよび消去された符号語６２４を復号する硬判定の代わりに、１つまたは複数のノイズのある第１の符号語の訂正の信頼度を示す信頼度情報が計算される、すなわち、軟復号符号語６２８である。軟復号符号語６２８は、復号の信頼度を示すものである。この場合、軟復号符号語６２８は、０が負の値で復号され、１の復号が正の値で示されることを示す。決定不可能な復号は、０値で示される。軟復号符号語６２８の大きさは、訂正の信頼度を示す。より大きい大きさは、より高い信頼度値を示す。図６ａで使用されているような反復符号については、予想される復号および前記復号の信頼度の両方が、単一の、たとえば、正または負の整数で符号化され得る。より複雑な第１の誤り訂正符号については、２つの値が、各符号語、予想される復号、たとえば、複数のビット、および信頼度値、たとえば、整数に使用され得る。
【０１６２】
図６ｂでは、軟復号は、１ビットを＋１と、０ビットを−１とカウントし、消去を無視することによって取得された。
【０１６３】
１つまたは複数のノイズのある第１の符号語の訂正の信頼度を示す信頼度情報は、誤り訂正器の一部であるか、または組み合わされ得る、信頼度情報抽出器によって決定され得る。信頼度情報抽出器は、図３に別個に示されてはいない。軟判定復号器は、信頼度情報を使用して１つまたは複数の第２の符号語を復号するように構成され得る。軟判定復号器は、最小距離リスト復号器であってよい。代替的に、軟判定復号器は、異なるタイプの軟判定復号、たとえば、ターボ復号器、トレリスベース復号器などであってよい。一実施形態において、最小距離リスト復号器は、信頼度情報と第２の誤り訂正符号語の各１つとの間の距離を計算し、最小距離を復号として選択するように構成される。
【０１６４】
軟判定情報としても知られている、信頼度情報は、第２の符号語を復号するために使用され得る。図６ａの例において、軟判定値は、外れ値（第２の）符号語の軟判定復号を行うために使用される。この例では、これは、最小距離リスト復号器を用いて行われる。
【０１６５】
第２の誤り訂正符号６５０の第２の符号語の間の近さは、軟判定情報６２８と符号語の各１つとの間の内積、またはドット積を計算することによって求めることができる。軟判定復号、たとえば、最小距離、または最大相関復号は、図６ｄに示されている。内積については、０ビットは、−１値とみなされる。相関の結果は、６５１に示されている。符号語（０，１，０，１）は、最も高い内積を有し、したがって、最も可能性の高い復号であることに留意されたい。近さ値は、たとえば、何らかの最大相関値から、それらを減算することによって、距離値に変換されるものとしてよく、この場合、相関は、２４から減算される。距離値は、６５２に示されている。第２の符号語符号（０，１，０，１）は、最小距離を有する。
【０１６６】
この場合、軟判定復号は、４つの反復符号語のうちの２つが正しく復号されないことがあるという事実があるにもかかわらず、正しく復号されたシードを返す。
【０１６７】
図６ａおよび６ｂにより示されている消去バイアス除去符号オフセットファジー抽出器は、図４ａおよび４ｂに関して示されているバイアス除去のすべての利点を有し、さらに、多重登録問題に悩まされないか、または少なくともあまりない。消去は、誤り訂正の効率と無関係であり、誤り訂正に寄与することも、また悪化させることもないことに留意されたい。バイアス除去、たとえば、消去によって引き起こされる損失も、符号オフセットノイズ低減データに完全に含まれるので、この場合のバイアス除去損失がノイズ低減データ公開と完全に重なり合うことも観察され得る。
【０１６８】
重要なことは、消去バイアス除去符号オフセットファジー抽出器は、多重登録公開問題に悩まされないことである。元のＰＵＦ応答のすべてのビットペアが、無変更または消去として、保持されるので、バイアス除去手続きはもはや確率論的でないというのが、これに対する理由である。したがって、同じＰＵＦの多重登録が考慮されるときに蓄積情報漏洩はあり得ない。
【０１６９】
説明されている実施形態では、独立して分布するバイアスを扱う。すなわち、実施形態は、バイアスが均一である場合に最もよく働くように見える。それにもかかわらず、いくつかの形態の不均一なバイアスであっても、図４−６による実施形態を使用して扱われる。たとえば、第１の一連のビットが第１のバイアスを有し、その後の第２の一連のビットが第２のバイアスを有する場合に、バイアスは、正しく扱われる。それは、これらの実施形態が局所的ビットペアを使用してどのビットを保持し、どのビットを破棄するかを決定するからである。場合によっては、第１の一連と第２の一連との間の領域に、何らかのエントロピー損失があり得る。したがって、異なるバイアスレベルを持つ複数のゾーンを有することは、大きな問題になるようには思えない。
【０１７０】
しかしながら、他の形態の不均一なバイアスは、より大きいエントロピー損失を引き起こし得る。たとえば、奇数インデックスを持つビットに対するバイアスレベルが偶数インデックスを持つビットに対するバイアスと異なるＰＵＦを考える。バイアス除去の後であっても、そのようなＰＵＦは、バイアスが偶数／奇数のインデックスに依存しない他の何らかの形の類似のＰＵＦに比べて低いエントロピーを有し得る。バイアス除去は、バイアス除去データを選択する前に転置を実行することによって改善され得、この転置は、第２の転置とも称される。一般的に、第２の転置は、第１の転置の前に実行されることに留意されたい。
【０１７１】
たとえば、一実施形態において、バイアス除去ユニット１２０は、第１のノイズのあるビット列内のビットを保持または破棄としてマークする前に第２の転置により第１のノイズのあるビット列を転置し、それぞれ第１および第２のバイアスレベルを有する第１のノイズのあるビット列の第１および第２の部分内のビットを、一緒にグループ化するように配置構成される。鍵再構築ユニット１５０は、バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットを決定する前に第２の転置により第１のノイズのあるビット列を転置し、第１のノイズのあるビット列の第１および第２の部分内のビットを一緒にグループ化するように配置構成される。
【０１７２】
たとえば、第１の部分は、第１または第２のノイズのあるビット列の偶数ビット、すなわち、偶数インデックスを持つビットであってよく、第２の部分は、奇数ビット、すなわち、奇数インデックスを持つビットであってよく、その逆も可能である。たとえば第２の転置は、第１の部分のすべてのビットを第１または第２のノイズのあるビット列の前に転置し得る。たとえば、転置は、ベクトル、たとえば、インデックスのうちの各インデックスがビット位置を指しているインデックスの配列として表され得る。たとえば、ベクトルは、［０，２，４，６，８，１０，．．．，２ｌ，１，３，５，７，９，．．．，２ｌ−１］であり、偶数および奇数ビット位置を一緒にグループ化するものとしてよく、ここでｎ＝２ｌビットが使用される。一実施形態において、符号語は、偶数ビット位置のみ、またはいずれかの奇数ビット位置のみからのビットから減算されるだけである。
【０１７３】
第２の転置は、バイアス除去データ内に含まれ得る。しかしながら、第２の転置は、たとえば、同じタイプのメモリベースのＰＵＦを共有する、類似のＰＵＦによりあるクラスのデバイスに対して固定される形で選択され得る。後者の場合、第２の転置は、事前決定されるものとして含まれ、たとえば、デバイスに格納され得る。第２の転置は、ＰＵＦを読み出すために使用されるＰＵＦのアドレス復号器内に含まれ得る。
【０１７４】
第１の転置も第２の転置もビットがメモリ内で異なる位置に移動されることを（それは可能であるが）必要としないが、ビットを異なる形で取り扱うことによっても実装され得ることに留意されたい。異なるアドレッシングが、ソフトウェアで、たとえば、転置されたアドレスを使用して、またはハードウェアで、たとえば、転置アドレス復号器を使用して、実行され得る。
【０１７５】
図９ａは、電子暗号デバイス１０２の一実施形態の一例を示す略図である。暗号デバイス１０２は、以下で説明されていることを除きデバイス１０１と同じである。
【０１７６】
興味深いことに、ＰＵＦ応答は、２つの異なる用途に使用できる。一方で、ヘルパーデータを使用してノイズを抑制することによって、暗号鍵を生成するためにＰＵＦ応答が使用され得る。もう一方で、ノイズは、ＰＵＦ応答からランダムシードを生成することによって利用され得る。第１の場合においてＰＵＦ応答の安定性が使用され、第２の場合においてそのノイズが使用される。
【０１７７】
残念なことに、たまに、ＰＵＦ１１０が仕様の範囲内にない応答を生成することがあり得る。乱数を生成するために、特に、ＰＵＦのノイズエントロピーが重要である。ノイズエントロピーは、同じＰＵＦインスタンスを繰り返し測定したときのノイズの量に関係するエントロピーである。これは、乱数生成にＰＵＦを使用するときに重要である。高品質のランダムシードがＰＵＦから導出されることを確実にするために十分なランダム性が繰り返される測定になければならない。
【０１７８】
良好なＰＵＦに関して、典型的には、デバイス間エントロピー（デバイスの間のＰＵＦ応答の差に関係するエントロピー）がノイズエントロピーを決定付ける。したがって、残念なことに、第２のノイズのあるビット列についての従来の乱数検定、たとえば、ＦＩＰＳ  １４０−１検定は、エントロピーが低すぎても高い確率で成功する。
【０１７９】
暗号デバイス１０２は、物理的複製不可能関数のノイズレベルを検証するために再構築フェーズにおいて統計的検定を実行するように配置構成されている統計ユニット１６０を備える。統計的検定では、上で示されている第２の問題、すなわち、ランダムシードの信頼できる生成に対してＰＵＦが有するノイズエントロピーが小さすぎたと検出することに対処する。
【０１８０】
統計的検定は、バイアス除去データおよび第２のノイズのあるビット列にアクセスできる。バイアス除去データは、第１のノイズのあるビット列のビットを直接識別することを許さないが、バイアス除去は、第２のノイズのあるビット列と比較できる第１のノイズのあるビット列に関する情報をもたらす。一実施形態において、バイアス除去データは、第１のノイズのあるビット列内でどのビットパターンが等しいか、または等しくないかを指示する。統計的検定は、第２のノイズのあるビット列内の同じビットペアが依然等しいかまたは等しくないかを検証することができる。これは、それらが変化していることを必ずしも除外しない：たとえば、ビットペアは、００から１１へ、０１から１０へ変化している可能性があり、そのような変化を検出することは、このバイアス除去データでは可能でない。しかしながら、第１のノイズのあるビット列と第２のノイズのあるビット列との間でごく少数の変化しか検出されない場合、ＰＵＦは低ノイズエントロピーを有する可能性が高い。
【０１８１】
一実施形態において、統計的検定は、バイアス除去データおよび第２のノイズのあるビット列を使用して第１のノイズのあるビット列内では等しいが第２のノイズのあるビット列内では等しくなく、および／または第１のノイズのあるビット列内では等しくないが第２のノイズのあるビット列内では等しいビットペアの数をカウントするように配置構成される。統計的検定は、物理的複製不可能関数のノイズレベルが、カウントが閾値よりも高い場合に十分であると決定する。
【０１８２】
閾値は、その仕様に従ってＰＵＦの統計的分布、たとえば、ＰＵＦのノイズ率から決定され得る。さらに、第２のノイズのあるビット列内のビットの数および所望の偽陽性率が知られている。これらのパラメータから、閾値が決定され得る。
【０１８３】
たとえば、第１のノイズのあるビット列は、非負整数ｉについてビットペアｂ２ｉｂ２ｉ＋１で除算された、ｂ０ｂ１ｂ２ｂ３．．．とみなされ得る。第２のノイズのあるビット列は、ビットペアｓ２ｉｓ２ｉ＋１で除算されたビットｓ０ｓ１ｓ２ｓ３．．．とみなされ得る。統計的検定では、ｂ２ｉｂ２ｉ＋１が等ペアであるが、ｓ２ｉｓ２ｉ＋１が不等ペアである、および／またはその逆であるｉの数をカウントする。
【０１８４】
暗号デバイス１０２は、統計的検定が正しく機能していることを示している場合のみ物理的複製不可能関数によって生成されるノイズのあるビット列にエントロピー濃縮関数を適用することによってランダムシードを生成するように配置構成されているランダムシード生成ユニット１６５を備える。エントロピー濃縮関数は、より大きい列、この場合より小さい列内の第２のノイズのあるビット列１１４、この場合、ランダムシードにおけるエントロピーを濃縮する。エントロピー濃縮関数の例は、ハッシュ関数、特に、ＳＨＡ−１などの暗号学的ハッシュ関数、圧縮関数、およびたとえば、ＮＩＳＴ−ＳＰ８００−９０において定義されているような、シードを導出するための導出関数などである。
【０１８５】
ランダムシードは、ランダムシードに応じて一連の乱数を生成するように配置構成されている擬似乱数生成器において使用され得る。乱数は、多くの暗号プロトコルにおいて使用され、非暗号アプリケーションも有し得る。擬似乱数生成器は、図９ａに別個に示されてはいない。
【０１８６】
たとえば、擬似乱数生成器は、ランダムシードから始まる、カウンタモードで実行される、ブロック暗号、たとえば、ＡＥＳ、またはランダムシードを鍵とするＲＣ４、ランダムシードをシードとするＦｏｒｔｕｎａなどのストリーム暗号であってよい。
【０１８７】
理論上、ＰＵＦが正しく動作している、たとえば、安定しており、かつ十分にランダムである場合に、同じ第２のノイズのあるビット列は、暗号鍵を再構築し、ランダムシードを導出するために使用され得る。ランダムシードは、無訂正の第２のノイズのあるビット列から計算されるが、暗号鍵は、訂正された第２のノイズのあるビット列から再構築される。たとえば、一実施形態において、ランダムシード生成ユニット１６５は、統計的検定が正しく機能していることを示している場合のみ第２のノイズのあるビット列にエントロピー濃縮関数を適用することによってランダムシードを生成するように配置構成される。ランダムシードが十分に長く、十分にランダムである場合、訂正されていない第２のノイズのあるビット列内のノイズは、訂正されていない第２のノイズのあるビット内に存在するすべての情報を決定付ける。この場合、強不可逆エントロピー濃縮関数（ｓｔｒｏｎｇ  ｎｏｎ−ｉｎｖｅｒｔｉｂｌｅ  ｅｎｔｒｏｐｙ  ｃｏｎｃｅｎｔｒａｔｉｏｎ  ｆｕｎｃｔｉｏｎ）、たとえば暗号ハッシュ関数が、望ましい。
【０１８８】
しかしながら、暗号鍵に関する情報が乱数生成を通じて漏れるあらゆる可能性を回避するために、異なるＰＵＦ応答がランダムシードを生成するために使用され得る。たとえば、一実施形態では、物理的複製不可能関数１１０は、再構築フェーズにおいて第２のノイズのあるビット列１１４およびさらなるノイズのあるビット列１１６を生成するように配置構成され、第２のノイズのあるビット列１１４およびさらなるノイズのあるビット列１１６は重なり合わない。ランダムシード生成ユニット１６５は、統計的検定が正しく機能していることを示している場合のみさらなるノイズのあるビット列にエントロピー濃縮関数を適用するように配置構成される。これは、乱数が暗号鍵に関する情報を漏らすことができないという利点を有する。
【０１８９】
たとえば、一実施形態において、ＰＵＦは、メモリベースであり、第１および第２のノイズのあるビット列は第１のメモリアドレスから取得され、さらなるノイズのあるビット列は、第２のメモリアドレスから取得され、第１および第２のメモリアドレスは異なっており、好ましくは重なり合わない。第１および第２のノイズのあるビット列は、同じ第１のチャレンジ、たとえば、同じアドレスへの応答としてみなされてよく、さらなるノイズのあるビット列は、第１のチャレンジと異なる第２のチャレンジ、たとえば、異なるアドレスへの応答としてみなされてよい。他のＰＵＦは、この方式で使用されるものとしてよく、たとえば、遅延ＰＵＦは、第１のチャレンジでチャレンジされ、第１および第２のノイズのあるビット列を生成し、再構築時に第２のチャレンジでチャレンジされ、さらなるノイズのあるビット列を生成し得る。
【０１９０】
図９ａは、さらなるノイズのあるビット列１１６を使用する一実施形態を示している。たとえば、１つまたは複数の統計的検定が、第２のノイズのあるビット列１１４およびバイアス除去データ１４２に対して実行される。統計的検定が、ＰＵＦがその仕様内で働いている、たとえば、十分なエントロピーまたは十分なノイズなどを有していることを示す場合、そこでランダムシードがさらなるノイズのあるビット列１１６から導出される。一実施形態において、第２のおよびさらなるノイズのあるビット列は、ＰＵＦの異なる部分から取得されるときに統計的に独立しているが、第１および第２のビット列は、ノイズを除き同じである。
【０１９１】
実験は、第２のノイズのあるビット列から計算された統計量は、ＰＵＦ全体を代表する量であり、したがって、さらなるノイズのあるビット列についても代表する量であることを示している。この関係は、第２のノイズのあるビット列とさらなるノイズのあるビット列とをインタリーブすることによってさらに改善され得る。たとえば、ＰＵＦは、メモリベースのＰＵＦであり、第１および第３のメモリアドレスはさらなるビット列に寄与し、第２および第４のメモリアドレスは第２のビット列に寄与し、第１のアドレスは第２のアドレスよりも小さく、第２のアドレスは第３のアドレスよりも小さく、第３のアドレスは第４のアドレスよりも小さい。
【０１９２】
図９ｂは、図６のデータを使用する、異なる実施形態を示している。図９ｂは、一連のビットペア６１３に分割された第１のＰＵＦ応答６１２、バイアス除去データ６４２、および第２のＰＵＦ応答６２２を示している。バイアス除去データ６４２から、この第１のノイズのあるビット列（全体）が再構築時に利用可能でない場合があるとしても第１のノイズのあるビット列内でどのビットペアが等しく、どのビットペアが等しくないかが決定されるものとしてよく、この場合、バイアス除去データ６４２内のゼロペアは、第１のノイズのあるビット列６１２内の等ペアを示し、バイアス除去データ６４２内の１のペアは第１のノイズのあるビット列６１２内の不等ペアを示す。
【０１９３】
一実施形態において、統計ユニットは次のように配置構成される：
−  バイアス除去データから、第１のビット列内の不等ビットペアを決定する。
−  第２のノイズのあるビット列内の等ビットペアおよび第１のビット列内の不等ビットペアである第２のノイズのあるビット列内のビットペアの個数をカウントし、第１の数を取得する。図９ｂにおいて、そのようなペアは、波括弧で示されている。第１の数は、参照６３２のところに与えられており、この例では１である。
−  第１の数が第１の閾値よりも大きい場合に物理的複製不可能関数のノイズレベルを検証する。
【０１９４】
一実施形態において、統計ユニットは次のように配置構成される：
−  バイアス除去データから、第１のビット列内の等ビットペアを決定する。
−  第２のノイズのあるビット列内の不等ビットペアおよび第１のビット列内の等ビットペアである第２のノイズのあるビット列内のビットペアの個数をカウントし、第２の数を取得する。図９ｂにおいて、そのようなペアは、波括弧で示されている。第２の数は、参照６３４のところに与えられており、この例では４である。
−  第２の数が第２の閾値よりも大きい場合に物理的複製不可能関数のノイズレベルを検証する。
【０１９５】
一実施形態において、両方の組合せがカウントされ、その結果このカウントに対する第１および第２の数の和、この場合、５が得られる。
【０１９６】
（実践例）
本明細書で説明されているようなバイアス除去ソリューションの実施形態は、その後再構築時に破棄されるかまたは消去されるべき等ビットペアを登録時に識別する。検定の一実施形態では、再構築時に、特定のサイズのＰＵＦブロック内のこれらのマークされているペアが等ビットを有効に含むかどうかをチェックし、これがその場合でないペアの数をカウントし、この数がマークされているペアの総数に関する特定の閾値よりも大きいことを検証する。この閾値は、ブロックサイズ、必要なＰＵＦノイズエントロピー品質パラメータ、および所望の偽陽性率に基づき前もって決定され得る。
【０１９７】
同じ挙動に基づく他の検定統計量（等としてマークされた不等ペアの総数の代わりに）、たとえば等としてマークされた不等ペアの／間の最長連が使用され得る。
【０１９８】
この検定は、ＰＵＦ応答が登録と再構築との間で再評価されることを必要とする。これがその場合でなければ、この検定は、意味ある結果を生み出し得ず、実行されないか、または無視される。
【０１９９】
この例において：セキュリティ強度１２８ビットのシードをＤＲＢＧに与えるために、ＰＵＦ応答（さらなるノイズのあるビット列）の１Ｋバイト（８１９２ビット）部分が使用される。［ＮＩＳＴ、ＳＰ８００−９０Ａ、Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｉｏｎ  Ｕｓｉｎｇ  Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｒａｎｄｏｍ  Ｂｉｔ  Ｇｅｎｅｒａｔｏｒｓ］によれば、このＰＵＦ応答データのノイズの最小エントロピーは、少なくとも１９２ビットであるべきである。このＰＵＦは、最大［３０％−７０％］までバイアスされうることが知られている。そのようなＰＵＦが８１９２ビットの十分なノイズ最小エントロピーを与えるために、その（平均）ビット誤り率は、少なくとも２．９％でなければならないと決定される。
【０２００】
鍵生成のために、このＰＵＦ応答（第１および第２のノイズのあるビット列）の別の部分（６８６４ビット）が使用される。この部分は、ＤＲＢＧにシードを与えるために使用される部分から完全に分離しているものとしてよいが、これらは同じＰＵＦに由来するので、バイアスおよびビット誤り率に関して同じ品質を有すると仮定される。鍵生成に使用される部分は、フォンノイマンベースのバイアス除去前処理と組み合わせて符号オフセットヘルパーデータ構築を配備する（本明細書で説明されているような）誤り訂正機構に通される。バイアス除去前処理機能は、その後再構築において結果として無視される（破棄されるか、または消去される）等ビットペアを、登録時に検出する。
【０２０１】
検定詳細：
鍵再構築時に、バイアス除去を伴う鍵生成器は、等しくあるべきビットペアの知識を有しているので、等しいものとしてマークされたが、再構築時にはもはや等しくないビットペアの数を観察することによって平均ビット誤り率を推定することができる。分析では、われわれは、ＰＵＦを、互いに独立で同一の分布に従うビットを有するものとしてモデル化している。
【０２０２】
バイアスｐおよび平均ビット誤り率ｐｅを有する互いに独立で同一の分布（ｉ．ｉ．ｄ．）に従うビットを持つＰＵＦ応答では、等ビットペアを観察する確率は（１−ｐ）２＋ｐ２であり、ｎビットＰＵＦ応答内の観察された等ビットペアの数は、パラメータ（ｆｌｏｏｒ（ｎ／２），（１−ｐ）２＋ｐ２）により２項分布している。再構築時に不等ビットペアを観察する確率は、このペアが登録時に等しいものとしてマークされていたとした場合に、次のように決定され得る：
Ｐｒｏｂ（不等ペア＠再構築｜等ペア＠登録）
＝２＊（１−ｐｅ／（２（１−ｐ）））＊（ｐｅ／（２（１−ｐ）））＊（１−ｐ）２／（（１−ｐ）２＋ｐ２）＋２＊（１−ｐｅ／（２ｐ））＊（ｐｅ／（２ｐ））＊ｐ２／（（１−ｐ）２＋ｐ２）
＝ｐｅ＊（１−ｐｅ）／（ｐ２＋（１−ｐ）２）。
【０２０３】
その結果、再構築時に不等である等ペアを登録時に観察する確率は、次のようになる：
Ｐｒｏｂ（不等ペア＠再構築  かつ  等ペア＠登録）
＝Ｐｒｏｂ（不等ペア＠再構築｜等ペア＠登録）＊Ｐｒｏｂ（等ペア＠登録）
＝（ｐｅ＊（１−ｐｅ））／（ｐ２＋（１−ｐ）２）＊（（１−ｐ）２＋ｐ２）
＝ｐｅ＊（１−ｐｅ）。
【０２０４】
興味深いことに、この確率は、ＰＵＦ応答のバイアスから独立していて、平均ビット誤り率にのみ依存している。これは、このことが生じるビットペアの数が平均ビット誤り率にのみ依存し、この数の観察が平均ビット誤り率レベルを評価するために使用され得ることを伴う。
【０２０５】
この結果に基づき、登録時に等としてマークされた観察されたが、再構築時に不等であるペアの数に対する下側閾値は、与えられた例について、次のように設定され得る：
Ｔ＝ＢｉｎｏＣＤＦ−１（１０−６；６８６４／２，２．９％＊（１−２．９％））＝５４。
【０２０６】
したがって、平均ビット誤り率が、十分に高い場合、高い確率（＞１−１０−６）で、これらのビットペアのうちの５４を超えるペアが観察されるべきである。これがその場合でなければ、フォンノイマンバイアス除去ペア同等性検定（Ｖｏｎ  Ｎｅｕｍａｎｎ  Ｄｅｂｉａｓｉｎｇ  Ｐａｉｒ  Ｅｑｕａｌｉｔｙ  Ｔｅｓｔ）では失敗を出力する。この例示的な鍵生成器に対するこの検定の基本的な流れは、図１０に示されている。この状況における失敗検定は、原理上、バイアス除去および／または鍵生成それ自体に対する結果を伴わず、検定結果（バイアス除去に基づく）は、ＤＲＢＧのシード指定にとって重要であるにすぎないことに留意されたい。
【０２０７】
図１１は、許容可能なビット誤り率＝２．９％に対して失敗率＜１０−６を有するようにチューニングされた、フォンノイマンバイアス除去ペア同等性検定に対する失敗率曲線を示している。この特定の検定では、６８６４ビットＰＵＦ応答部分内で登録時に等しいとしてマークされた観察された不等ビットペアの数が５４よりも小さい場合に失敗を出力する。検定の失敗は、この検定により、ビット誤り率（ノイズ最小エントロピー）が許容できないことを示す。
【０２０８】
この検定で失敗を出力する確率は、ＰＵＦの実際の現実のビット誤り率（ａｃｔｕａｌ  ｒｅａｌ  ｂｉｔ  ｅｒｒｏｒ  ｒａｔｅ）に依存する。提示されている例について、この関係が図１１に示されている。この曲線は、２．９％よりも大きい許容可能なビット誤り率について、検定の失敗率は＜１０−６であることを示している（したがって、検定は、許容可能なビット誤り率を持つＰＵＦを誤って棄却する非常に小さな誤棄却率＜１０−６を有する）。しかしながら、平均ビット誤り率が、許容可能な限度よりも小さい場合、検定の失敗率は、１０−６を超えて上昇し、平均ビット誤り率＜１．３％について１００％に近づく（許容できない平均ビット誤り率の特定の区間、おおよそ［１．３％．．．２．６％］があり、これは１００％の確実性で検定によって検出されない）。
【０２０９】
典型的には、デバイス１００および１０１などの、バイアス除去データ生成、ノイズ低減データ生成、および／または鍵再構築を実行するためのデバイスは、各々、デバイス１００、１０１に格納されている適切なソフトウェアを実行するマイクロプロセッサ（図示せず）を備え、たとえば、そのソフトウェアは、ダウンロードされ、および／または対応するメモリ、たとえば、ＲＡＭなどの揮発性メモリまたはフラッシュ（図示せず）などの不揮発性メモリに記憶されていてよい。代替的に、デバイス１００および１０１は、全体としてまたは一部だけ、プログラマブルロジックで、たとえば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）として、実装され得る。デバイス１００および１０１は、全体としてまたは一部だけ、いわゆる特定用途向け集積回路（ＡＳＩＣ）、すなわち、その特定の用途のためにカスタマイズされた集積回路（ＩＣ）として実装されてもよい。
【０２１０】
一実施形態において、電子暗号デバイスは、バイアス除去回路および鍵再構築回路を備える。電子暗号デバイスは、ノイズ低減回路、誤り訂正器回路、信頼度情報抽出器回路、軟判定復号器回路、統計的検定回路、ランダムシード生成器回路のうちの１つまたは複数も備え得る。これらの回路は、本明細書で説明されている対応するユニットを実装する。回路は、プロセッサ回路およびストレージ回路であってよく、プロセッサ回路はストレージ回路内に電子的に表現される命令を実行する。これらの回路は、ＦＰＧＡ、ＡＳＩＣ、または同様のものであってもよい。
【０２１１】
図７は、暗号鍵を決定するように構成されている電子暗号方法７００の一実施形態を示す略図である。方法７００は、登録フェーズ７１０およびその後の再構築フェーズ７２０を有する。
【０２１２】
登録フェーズ７１０は
−  物理的複製不可能関数（ＰＵＦ）（１１０）を使用して第１のノイズのあるビット列を生成するステップ７１２と、
−  第１のノイズのあるビット列内のバイアスを低減するために第１のノイズのあるビット列からバイアス除去データを決定するステップ７１４であって、バイアス除去データは第１のノイズのあるビット列内のビットを保持または破棄としてマークする、決定するステップ７１４とを含む。
【０２１３】
再構築フェーズ７２０は
−  物理的複製不可能関数（ＰＵＦ）（１１０）を使用して第２のノイズのあるビット列を生成するステップ７２２と、
−  バイアス除去データによって保持としてマークされている第２のノイズのあるビット列内のビットから暗号鍵を決定するステップ７２４であって、暗号鍵はバイアス除去データによって破棄としてマークされている第２のノイズのあるビット列内のビットから独立している、決定するステップ７２４とを含む。
【０２１４】
暗号鍵は、また、登録フェーズにおいて、そのようなもので都合がよければ、たとえば、保持としてマークされている第１のノイズのあるビット列内のビットから、決定され得る。
【０２１５】
方法７００を実行する多くの異なる方法が、当業者に明らかなように、可能である。たとえば、ステップの順序は、変えることができるか、またはいくつかのステップが、並列に実行され得る。さらに、ステップとステップの間に、他の方法ステップが挿入されてもよい。挿入されたステップは、本明細書で説明されているような方法の改良を表し得るか、またはその方法に無関係であってもよい。さらに、与えられたステップは、次のステップが開始される前に完全に終了していなくてもよい。
【０２１６】
本発明による方法は、方法７００をプロセッサシステムに実行させるための命令を備える、ソフトウェアを使用して実行され得る。ソフトウェアは、システムの特定のサブエンティティによって実行されるステップのみを含み得る。ソフトウェアは、ハードディスク、フロッピー、メモリなどの、好適なストレージ媒体に記憶され得る。ソフトウェアは、電線を流れる信号として、またはワイヤレスで、またはデータネットワーク、たとえば、インターネットを使用して送信され得る。ソフトウェアは、ダウンロードおよび／またはサーバ上のリモートでの使用に利用可能にされ得る。本発明による方法は、方法を実行するようにプログラマブルロジック、たとえば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を構成するように配置構成されたビットストリームを使用して実行され得る。
【０２１７】
本発明は、コンピュータプログラム、特に、本発明を実施するように構成された、キャリア上のまたはキャリア内のコンピュータプログラムにも拡張されることは理解されるだろう。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、および部分的にコンパイルされた形態などのオブジェクトコードの形態、または本発明による方法の実装で使用するのに適している他の任意の形態をとり得る。コンピュータプログラム製品に関係する一実施形態は、説明されている方法のうちの少なくとも１つの処理ステップの各々に対応するコンピュータ実行可能命令を含む。これらの命令は、サブルーチンに細分され、および／または静的にもしくは動的にリンクされ得る１つまたは複数のファイルに格納され得る。コンピュータプログラム製品に関係する別の実施形態は、説明されているシステムおよび／または製品のうちの少なくとも１つの手段の各々に対応するコンピュータ実行可能命令を含む。
【０２１８】
図８ａは、コンピュータプログラム１０２０を含む書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示しており、コンピュータプログラム１０２０は一実施形態により暗号鍵を決定するための方法をプロセッサシステムに実行させるための命令を備える。コンピュータプログラム１０２０は、コンピュータ可読媒体１０００上に物理的マークとして、またはコンピュータ可読媒体１０００の磁化を用いて具現化され得る。しかしながら、他の好適な実施形態も同様に企図され得る。さらに、コンピュータ可読媒体１０００はここでは光ディスクとして示されているが、コンピュータ可読媒体１０００は、ハードディスク、ソリッドステートメモリ、フラッシュメモリなどの好適な任意のコンピュータ可読媒体であってよく、記録不可能または記録可能であってよい。コンピュータプログラム１０２０は、暗号鍵を決定する方法のうちの前記方法をプロセッサシステムに実行させるための命令を備える。
【０２１９】
図８ｂは、一実施形態による、プロセッサシステム１１００を示す概略配置図である。プロセッサシステムは、１つまたは複数の集積回路１１１０を備える。１つまたは複数の集積回路１１１０のアーキテクチャは、図８ｂに概略として示されている。回路１１１０は、一実施形態による方法を実行するためにおよび／またはそのモジュールもしくはユニットを実装するためにコンピュータプログラムコンポーネントを動作させるための処理ユニット１１２０、たとえば、ＣＰＵを備える。回路１１１０は、プログラミングコード、データなどを記憶するためのメモリ１１２２を備える。メモリ１１２２の一部は、リードオンリーであってよい。回路１１１０は、通信要素１１２６、たとえば、アンテナ、コネクタ、または両方、および同様のものを備え得る。回路１１１０は、方法において定義されている処理の一部または全部を実行するための専用集積回路１１２４を含み得る。プロセッサシステム１１００は、一実施形態において使用するためのＰＵＦ１１２８を備え得る。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４、ＰＵＦ１１２８、および通信要素１１２６は、相互接続部１１３０、たとえば、バスを介して互いに接続され得る。プロセッサシステム１１１０は、アンテナおよび／またはコネクタを、それぞれ使用して、接触型および／または非接触型通信を行うように配置構成され得る。
【０２２０】
上述の実施形態は、本発明を制限するのではなく本発明を例示するものであり、当業者であれば、多くの代替的実施形態を設計することができることに留意されたい。
【０２２１】
請求項において、括弧の間に入っている参照記号は、請求項を制限するものとして解釈されないものとする。「備える、含む」という動詞およびその活用形を使用していても、請求項で述べられているもの以外の要素もしくはステップの存在を除外しない。「ａ」または「ａｎ」という冠詞を要素の前に付けていても、複数のそのような要素の存在を除外しない。本発明は、いくつかの明確に異なる要素を含むハードウェアを用いて、および適切にプログラムされているコンピュータを用いて実装されてもよい。いくつかの手段を列挙しているデバイス請求項において、これらの手段のうちのいくつかは、ハードウェアの１つおよび同じ項目によって具現化され得る。特定の測定が、相互に異なる従属請求項において引用されているという単なる事実は、これらの測定の組合せが有利に使用され得ないことを示すものではない。
【０２２２】
請求項において、括弧内の参照は、実施形態の図面の中の参照記号または実施形態の公式を参照するものであり、それにより、請求項の理解度を高める。これらの参照は、請求項を制限するものとして解釈されないものとする。
【符号の説明】
【０２２３】
１０  物理的複製不可能関数（ＰＵＦ）
１１  ノイズのあるビット列
１２  ノイズ低減データ
１３  鍵データ
１５  エントロピー損失
１００  電子暗号デバイス
１０１  電子暗号デバイス
１１０  物理的複製不可能関数（ＰＵＦ）
１１２  第１のノイズのあるビット列
１１４  第２のノイズのあるビット列
１１６  さらなるノイズのあるビット列
１２０  バイアス除去ユニット
１３０  ノイズ低減ユニット
１４０  ストレージ
１４２  バイアス除去データ
１４４  ノイズ低減データ
１５０  鍵再構築ユニット
１５２  正規化器
１５４  誤り訂正器
１５６  鍵導出ユニット
１６０  統計ユニット
１６５  乱数シード発生ユニット
４１２  第１のＰＵＦ応答
４１３  一連のビットペア
４１４  バイアス除去された第１のＰＵＦ応答
４１５  第１の符号語
４２２  第２のＰＵＦ応答
４２３  バイアス除去された第２のＰＵＦ応答
４２４  ノイズのある符号語
４２６  訂正された符号語
４２７  復号された符号語
４４０  バイアス除去およびノイズ低減データ
４４２  バイアス除去データ
４４２’  バイアス除去データ
４４４  ノイズ低減データ
５１２  第１のＰＵＦ応答
５１３ａ、５１３ｂ  一連のビットペア
５１４  バイアス除去された第１のＰＵＦ応答
５１５  第１の符号語
５２２  第２のＰＵＦ応答
５２３  バイアス除去された第２のＰＵＦ応答
５２４  ノイズのある符号語
５２７  復号された符号語
５４２  バイアス除去データ
５４４  ノイズ低減データ
６１２  第１のＰＵＦ応答
６１３  一連のビットペア
６１４  バイアス除去された第１のＰＵＦ応答
６１５  第１の符号語
６２２  第２のＰＵＦ応答
６２４  バイアス除去され正規化された第２のＰＵＦ応答
６２７  硬復号された符号語
６２８  軟復号された符号語
６４０  バイアス除去およびノイズ低減データ
６４２  バイアス除去データ
６４４  ノイズ低減データ
６３０  シード
６５０  第２の符号語
６５１  相関
６５２  軟判定距離
【図１ａ】
2018504827.tif 000003
【図１ｂ】
2018504827.tif 000004
【図２】
2018504827.tif 000005
【図３】
2018504827.tif 000006
【図４ａ】
2018504827.tif 000007
【図４ｂ】
2018504827.tif 000008
【図５ａ】
2018504827.tif 000009
【図５ｂ】
2018504827.tif 000010
【図６ａ】
2018504827.tif 000011
【図６ｂ】
2018504827.tif 000012
【図６ｃ】
2018504827.tif 000013
【図６ｄ】
2018504827.tif 000014
【図７】
2018504827.tif 000015
【図８ａ】
2018504827.tif 000016
【図８ｂ】
2018504827.tif 000017
【図９ａ】
2018504827.tif 000018
【図９ｂ】
2018504827.tif 000019
【図１０】
2018504827.tif 000020
【図１１】
2018504827.tif 000021
【国際調査報告】
2018504827.tif 000022
2018504827.tif 000023
2018504827.tif 000024