JP5548218B2 - 物理的システムに依存する暗号鍵を確立するためのシステム - Google Patents

Description

本発明は、構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムと、構成に依存する初期ビットストリングを確立するための初期ビットストリングプロデューサ（ｂｉｔ−ｓｔｒｉｎｇ ｐｒｏｄｕｃｅｒ）とを含む、暗号鍵を再現できるように確立するための暗号システムに関する。

本発明は、さらに符号語（ｃｏｄｅ ｗｏｒｄ）を再現できるように確立するための暗号システムに関する。

本発明は、さらに対応する方法およびコンピュータプログラムに関する。

物理的クローン不能関数（Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎｅａｂｌｅ Ｆｕｎｃｔｉｏｎ：ＰＵＦ）とは、物理的システムに刺激（ｓｔｉｍｕｌｕｓ）の形で入力を与えること、および刺激と物理的システムの間の相互作用の結果として発生する挙動を出力にマッピングすることにより、入力に対する関数の出力が得られるような方法で、物理的システムとして具体化される関数である。この場合、相互作用は、予測することができず、また物理的システムに物理的にアクセスすることなしに出力を得ることが実行不可能であり、かつ物理的システムを再現することが実行不可能な程度まで、物理的システム内の本質的にランダムな構成要素に依存する。好ましくは、ＰＵＦはまた、評価することが容易である。実際に使用するためには、ＰＵＦは製造費用が低いことが好ましい。

従来、ＰＵＦが受け入れる入力または刺激は、「チャレンジ（ｃｈａｌｌｅｎｇｅ）」と呼ばれている。ＰＵＦの出力、すなわち刺激との相互作用後にＰＵＦが示す挙動は、「レスポンス（ｒｅｓｐｏｎｓｅ）」と呼ばれる。ＰＵＦのチャレンジおよび対応するレスポンスを含む１対がチャレンジ−レスポンス対と呼ばれる。広範な異なる入力を可能にするタイプのＰＵＦがあり、より限定された範囲の入力を可能にするタイプがあり、または単一入力だけを可能にすることができるタイプさえある。同じチャレンジに対して多数回評価されたとき、ＰＵＦが、すべて同じとなる多数のレスポンスを生成する場合が最も好ましい。しかし、この特性は必須ではなく、実際には、大部分のＰＵＦがこの特性を有していない。多数のレスポンスが互いに十分近くにある限り、ＰＵＦは、有用に適用されることができる。

刺激と物理的システムの間の相互作用は、システムへのアクセスなしに予測されることができないので、ＰＵＦを特徴付けすることおよびモデル化することが困難である。したがって、入力に対する特定のＰＵＦの出力は、特定のＰＵＦの基になる特定の物理的システムを使用してしか得られることができない。チャレンジ−レスポンス対を所有していることは、ＰＵＦの基となる固有の物理的システムに任意の時点でチャレンジが与えられたという証明である。この特性のために、すなわちチャレンジ−レスポンス対が固有の物理機器に結びつけられるという特性のために、ＰＵＦはクローン不能と呼ばれる。機器にＰＵＦを装備することにより、機器もクローン不能になる。

少なくとも部分的に制御できない製造工程、すなわち何らかのランダム性を必然的に導入する製造工程によって製造される物理的システムは、ＰＵＦのよい候補になる。

ＰＵＦの１つの有利な点が、耐タンパー（ｔａｍｐｅｒ ｒｅｓｉｓｔａｎｔ）特性を本質的に持っているということであり、ＰＵＦを分解してＰＵＦの働きを観測することもランダムな要素を乱し、したがって、入力が出力にマッピングされる方法も乱す。光学的ＰＵＦおよび電子的ＰＵＦを含む様々なタイプのＰＵＦが当技術分野で知られている。

ＰＵＦを構築する１つの方法として、スタティックＲＡＭ（ＳＲＡＭ）を使用するものがあり、これらのＰＵＦはＳＲＡＭ ＰＵＦと呼ばれる。ＳＲＡＭは、電源が投入された後、オンビットおよびオフビットのランダムパターンで満たされるという特性を有する。ＳＲＡＭが次回、電源を投入された場合、パターンは、それ自体を正確に再現することができないが、２つのそのようなパターン間の差は、典型的にはその状態中のビット数の半分よりもはるかに少ない。

第２の種類のＳ−ＲＡＭ ＰＵＦが、デュアルポートＲＡＭを使って構築される。両方のポートに異なる情報を同時に書き込むことにより、メモリセルが、ＰＵＦに似た挙動を示す、規定されない状態に至らせられる。

製造中の不可避の変動により、互いに対するＳＲＡＭの構成要素の構成が少なくとも少しランダムである。これらの変動は、たとえばＳＲＡＭのメモリセルの少し異なるしきい値電圧に反映される。ＳＲＡＭが規定されない状態で、たとえば書込動作の前に読み出されるとき、ＳＲＡＭの出力は、ランダムな構成に依存する。同じ特徴的挙動を有する新しいＳＲＡＭを製造することは、同じ構成、すなわちランダムに達成された構成を有するＳＲＡＭを製造することを必要とする。これは実現できないので、ＳＲＡＭは物理的システムとしてクローン不能であり、すなわち、ＳＲＡＭはＰＵＦである。

ＰＵＦの別の例が、いわゆる遅延ＰＵＦである。集積回路、たとえばＦＰＧＡの２つの領域間の接続によりもたらされる遅延が正確に測定され、ＰＵＦ出力として使用される。遅延は、たとえばリング発振器に接続を組み入れて、リング発振器の周波数を決定することによって測定されることができる。接続はＰＵＦの入力に応じて経路設定されることができる。たとえば、接続が、少なくとも２つの可能な経路をそれぞれの遅延構成要素を含む、一連の遅延要素を通して経路設定されることができる。ＰＵＦへの入力は多数のセレクタビットを含み、特定の遅延要素で使用される経路が、特定のセレクタビットに依存する。遅延要素内の構成要素は少なくとも少し異なるので、遅延要素により引き起こされる正確な遅延も少し異なる。したがって、遅延ＰＵＦの出力は、構成要素のランダムな構成に依存する。

ＰＵＦについて、何らかの前処理または後処理が使用されることがあることに留意されたい。たとえば、遅延ＰＵＦが多数の出力ビットを生成するために多数回使用されることがあり、多数の出力ビットは、ビットストリングを生成するために共に連結される。また、ＰＵＦが、ＰＵＦの処理を手助けするための処理データを使用することがある。たとえば、実際の遅延を平均遅延と比較するために、平均遅延時間が遅延ＰＵＦと共に記憶されることがある。

ＰＵＦの１つの応用例が、電子回路上で暗号鍵を導出することである。電子回路は、典型的には集積回路（ＩＣ）および／またはプログラマブル論理回路（ｐｒｏｇｒａｍｍａｂｌｅ ｌｏｇｉｃ）を含む。プログラマブル論理回路は、たとえばフィールドプログラマブルゲートアレイ（ｆｉｅｌｄ−ｐｒｏｇｒａｍｍａｂｌｅ ｇａｔｅ ａｒｒａｙ：ＦＰＧＡ）、プログラマブル論理デバイス（ｐｒｏｇｒａｍｍａｂｌｅ ｌｏｇｉｃ ｄｅｖｉｃｅ：ＰＬＤ）、またはデジタルシグナルプロセッサ（ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ：ＤＳＰ）、マイクロプロセッサなどを含む。何らかの種類の不揮発性メモリ内に暗号鍵を記憶する代わりに、鍵が機器により必要とされるときだけ、鍵がＰＵＦから生成される。鍵は、もはや必要とされないときに削除されることができる。次回、鍵が必要とされるとき、鍵はＰＵＦから再度導出されることができる。ＰＵＦは同じチャレンジが２度評価されるときに正確に同じ結果を与えることができないので、ファジーエクストラクタ（Ｆｕｚｚｙ Ｅｘｔｒａｃｔｏｒ）としても知られているいわゆるヘルパデータ（Ｈｅｌｐｅｒ Ｄａｔａ）アルゴリズムが、鍵が得られるたびに鍵が同じであることを保証するために使用されることができる。ノイズのある測定結果から再現できる値を構築するためにヘルパデータを使用する１つの方法が、たとえば国際公開第２００６／１２９２４２号、「Ｔｅｍｐｌａｔｅ Ｒｅｎｅｗａｌ ｉｎ Ｈｅｌｐｅｒ Ｄａｔａ Ｓｙｓｔｅｍｓ」などで説明されている。

ＰＵＦを使用して暗号鍵を生成するための１つの方法が以下の通りである。まず、登録段階中、チャレンジ−レスポンス対が生成される。次に、ファジーエクストラクタを使用して、ヘルパデータが生成される。機器上で、チャレンジおよびヘルパデータが不揮発性メモリ内に記憶される。暗号鍵を導出するために、チャレンジに対してＰＵＦを再度評価することにより新しいレスポンスが得られる。記憶されたヘルパデータと新しいレスポンスを組み合わせることにより、ヘルパデータアルゴリズムに従って鍵が得られる。ヘルパデータは、鍵が導出されるたびに、鍵が同じであることを保証する。

国際公開第２００６／１２９２４２号

ＰＵＦがなければ、暗号鍵は、鍵が従来記憶される不揮発性メモリに対して物理的攻撃を仕掛けることにより攻撃者によって回復されることができる。たとえば、攻撃者はメモリを開いてメモリの内容を探ることができる。ＰＵＦを開けることが、典型的にはＰＵＦが入力と相互作用する正確な方法を乱すので、ＰＵＦを使用することは、このタイプの攻撃をはるかに困難にする。したがって、攻撃者が探査から知る情報は、暗号鍵を生成するために使用された相互作用に関連付けられない。このことが、攻撃者が物理的攻撃を使用して鍵を見つけ出すことをより困難にする。

都合の悪いことに、侵入する物理的攻撃は、攻撃者がＰＵＦの内部状態に関する少なくとも一部の情報を得ることができる唯一の攻撃ベクトルではない。いわゆるサイドチャネルも情報を漏洩することがある。サイドチャネルとは、システムの外側から観測されることができ、かつシステムの意図された観測できる入出力挙動以外のシステムの内部動作および／または内部状態と少なくともある程度相関のある情報を明らかにする、システムの内側で起こる物理現象に関連付けられるシステムに関する情報源である。

電力消費、時間消費、および電磁放射が、暗号システムに関係のあるサイドチャネルの例である。たとえば、システムが暗号鍵を使用する間に監視される暗号システムの電力消費が、鍵とある程度相関があり得る。暗号鍵を秘密に保つことが最も重要なので、その鍵と相関がある情報のどんな漏洩も問題がある。

ＰＵＦに基づく暗号システムがサイドチャネルを通してその内部動作に関する情報を明らかにすることが従来技術の問題である。

ＰＵＦに基づくシステムのサイドチャネルを通した機密情報の漏洩を回避し、または軽減することが本発明の目的である。

この目的および別の目的が、本発明により暗号鍵を再現できるように確立するための暗号システムにより達成される。暗号鍵を再現できるように確立するための暗号システムは、構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムと、構成に依存する初期ビットストリングを確立するための初期ビットストリングプロデューサと、誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを初期ビットストリングに依存して確立するためのノーマライザ（ｎｏｒｍａｌｉｚｅｒ）であって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが誤り訂正符号に関連付けられるノーマライザと、誤り訂正アルゴリズムを使用して、第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するための誤り訂正器（ｅｒｒｏｒ−ｃｏｒｒｅｃｔｏｒ）と、所定の鍵導出アルゴリズムを適用することにより第１の符号語に依存する暗号鍵を確立するための鍵エスタブリッシャ（ｅｓｔａｂｌｉｓｈｅｒ）とを含む。暗号システムは、ランダム化する構成要素を生成するためのランダマイザ（ｒａｎｄｏｍｉｚｅｒ）をさらに含み、第１の訂正可能ビットストリングの確立がランダム化する構成要素にさらに依存し、暗号鍵の確立が、ランダム化する構成要素の影響を取り除くことにより暗号鍵を再現できるようにするためのランダム化する構成要素にさらに依存する。

本発明による暗号システムの有利な点は、誤り訂正器のあり得るサイドチャネルが不明瞭にされることである。第１の符号語に関する情報が暗号システムの外側に漏洩された場合でも、ランダム化する構成要素を使用して値がランダム化されるので、この情報は攻撃者にとってほとんど価値がなくなる。ランダム化する構成要素が攻撃者には知られていないので、このことが、攻撃者がサイドチャネルから得ることができる情報を低減する。

概略で、この効果は以下のように達成される。ノーマライザは、初期ビットストリングに依存するたけでなく、ランダム化する構成要素にも依存して第１の訂正可能ビットストリングを変換する。したがって、第１の訂正可能ビットストリングを第１の符号語にマッピングする間に、誤り訂正器の動作もランダム化される。誤り訂正器のあり得るサイドチャネルがランダム化を通してマスクされる。サイドチャネルを通して漏洩される情報は、第１の訂正可能ビットストリングおよび／または第１の符号語に関連付けられた情報であり、これらの情報はいずれもランダム化されている。

暗号鍵のその後の確立も、ランダム化する構成要素に依存し、その結果、ランダム化する構成要素の影響は取り除かれることができる。この方法では、ランダム化する構成要素が誤り訂正器の動作中に使用されたとしても、鍵は依然として再現できる。

本発明による暗号システムは、暗号鍵を使用する応用で、たとえば銀行業務、携帯電話通信、およびセットトップボックスなどに関連付けられる応用で利用されることができる。具体的には、本発明によるシステムはアクセス制御のためにスマートカード内に含まれることがある。たとえば建物への物理的出入管理、またはたとえばＤＲＭシステムでのデジタルアクセス管理は、いずれも本発明を使用して行われることができる。本発明はまた、一意の識別子として使用される暗号鍵を確立するためにデスクトップコンピュータに適用されることができる。

初期ビットストリングおよび推測によって暗号鍵は、完全にランダムではないことがある。たとえば、可能な物理的システム全体への初期ビットストリングの分布が一律でないことがある。したがって、鍵導出を適用することにより初期ビットストリングの分布を少なくともマスクすることが有利である。好ましくは、暗号鍵は初期ビットストリングよりも少ないビットを含む。好ましくは、暗号鍵は、第１の符号語内のビットデータ数よりも、すなわち第１の符号語内のビット数から冗長ビット数を減算した数よりも少ないビットを含む。

好ましい実施形態では、暗号システムは、符号語加算器および符号語減算器を含み、この場合、ランダム化する構成要素は誤り訂正符号のランダムな符号語を含み、ノーマライザは、少なくともランダムな符号語を少なくとも初期ビットストリングに加算するために符号語加算器に結合され、鍵エスタブリッシャは、ランダムな符号語を第１の符号語から減算するために符号語減算器に結合される。

符号語を含むビットストリングをマスクする効果的方法が、ビットストリングに別のビットストリングを加算する方法である。加算器は、排他的論理和加算を使用する排他的論理和加算器でもよく、この場合、減算器は加算器に等しくなり得る。好ましくは、誤り訂正符号は線形符号である。情報理論により、既知のビットにランダムなビットを加算することは、既知のビットを完全にマスクすることが知られている。ランダムな符号語は符号語でなければならないという点で制限されるが、それにもかかわらず初期ビットストリングを大部分マスクする。

好ましい実施形態では、暗号システムは、初期ビットストリングプロデューサにより確立される登録ビットストリングと、誤り訂正符号の第２の符号語との間の差であるヘルパデータビットストリングを記憶するためのヘルパデータストアを含み、符号語加算器が少なくともヘルパデータビットストリング、初期ビットストリング、およびランダムな符号語を加算して第１の訂正可能ビットストリングを確立するように構成される。

ヘルパデータが、初期ビットストリングに加算されなければならないビットストリングを含む場合、このことは初期ビットストリングを訂正可能ビットストリングにマッピングする１つの方法であるが、この加算はランダムな符号語の加算と効果的に組み合わせられることができる。たとえば、加算器は、再利用可能なハードウェアおよび／またはソフトウェアであってもよい。

好ましくは、暗号鍵の確立は第２の符号語に依存する。暗号鍵は、第２の符号語への暗号鍵の依存性を通してのみ第１の符号語に依存し得ることが留意される。

鍵は、様々な中間の決定段階を通して第１の符号語に依存し得る。たとえば、好ましい実施形態では、登録ビットストリングは第２の符号語およびヘルパデータから確立される。この場合、鍵は登録ビットストリングから得られることができる。たとえば、ヘルパデータが第２の符号語と登録ビットストリングとの間の排他的論理和として得られる場合、登録ビットストリングは、ヘルパデータと第２の符号語の排他的論理和加算を決定することにより第２の符号語から再構築されることができる。

好ましい実施形態では、符号語加算器は、まずヘルパデータビットストリングとランダムな符号語を加算して中間のビットストリングを得るように、および初期ビットストリングを中間のビットストリングに加算するように構成される。好ましい実施形態では、符号語加算器は、まずランダムな符号語と初期ビットストリングを加算して中間のビットストリングを得るように、およびヘルパデータビットストリングを中間のビットストリングに加算するように構成される。

一部の応用例では、初期ビットストリングとヘルパデータの両方を秘密に保つことが好ましい。ランダムな符号語を第１の加算の要素にすることにより、暗号システムの動作は初めからマスクされる。

好ましい実施形態では、ランダム化する構成要素は置換クラス（ｐｅｒｍｕｔａｔｉｏｎ ｃｌａｓｓ）からのランダムな置換を含み、誤り訂正符号は置換クラスの下で不変であり、ノーマライザは、訂正可能な近傍内にある中間の訂正可能ビットストリングを初期ビットストリングに依存して確立するように構成され、ノーマライザは、ランダムな置換に従って中間の訂正可能ビットストリングを置換して第１の訂正可能ビットストリングを確立するように構成され、トランスフォーマ（ｔｒａｎｓｆｏｒｍｅｒ）はランダムな置換の逆に従って第１の符号語を置換するように構成される。

ビットストリングを置換することは、ランダム化を通してビットストリングを不明確にする別の方法である。置換は、非線形符号が使用されるとき、有利であり得る。たとえば、誤り訂正符号はたとえばＺ_４上の、すなわち４つの要素を有する加算環（ａｄｄｉｔｉｖｅ ｒｉｎｇ）上の非線形巡回符号となるように選択されることができる。好ましい実施形態では、置換クラスは巡回置換からなり、誤り訂正符号は巡回符号である。

好ましい実施形態では、第１の訂正可能ビットストリングに依存する第１の符号語を確立するための誤り訂正器の実行時間が、第１の訂正可能ビットストリングから実質的に独立している。

誤り訂正器により使用される実行時間の量はまた、サイドチャネルを構成し得る。たとえば、一部の符号について、実行時間が、入力での誤り数に、または符号語のハミング重みなどに関連付けられる。この方法では、暗号システムの内部動作に関する情報が、システムの外部に漏洩し得る。実行時間は、一定の復号時間を有する誤り訂正アルゴリズムを使用することにより無関係にされることができる。暗号システムはまた、実際の実行時間を不明瞭にするダミー動作を導入するために実行時間ランダマイザを含むことができる。あるいは、暗号システムは、実行時間最大値の未使用時間を埋めるためのダミー動作を実行するための手段を含むことができる。

実行時間と第１の訂正可能ビットストリングの間の相関を低減することが、好ましい実施形態で達成されるが、この場合、誤り訂正器が、第１の訂正可能ビットストリングを複数のサブストリングに分割するように構成され、複数のサブストリングの特定のサブストリングが、別の誤り訂正符号の別の訂正可能な近傍内にあって、別の誤り訂正符号内の別の符号語すべての列挙から実質的に所定の時間の範囲内にある、所定の距離関数に従って特定のサブストリングに最も近い特定の別の符号語を選択する。第１の符号語を確立することは、特定の別の符号語にさらに依存する。

すべての別の符号語を列挙することは、一定量の時間がかかる。また、列挙からの選択は一定量の時間がかかる。したがって、特定のサブストリングを特定の符号語にマッピングするために誤り訂正器により必要とされる実行時間は、特定のサブストリングから独立している。したがって、特定のサブストリングに関連付けられる部分である実行時間サイドチャネルを通して漏洩されることができる情報の少なくとも一部がマスクされ、それに従って実行時間と第１の訂正可能ビットストリングの間の相関が低減される。

好ましい実施形態では、別の誤り訂正符号内の各符号語は、データ部分および冗長部分を含む。誤り訂正符号は、別の誤り訂正符号内の符号語のデータ部分の集まりが整数の順次リストを形成する順序付けを有する。システムは、順序付けに従って符号語の冗長部分を記憶するための記憶装置を含む。

多くの誤り訂正符号が、それらの符号語をデータビットおよび冗長ビット、たとえばパリティビットに分割されることができるという特性を有する。典型的には、データビットはデータを符号化するために使用されるが、冗長ビットはデータビットに依存する割り当てられた値である。たとえば、線形符号がこの特性を有する。誤り訂正符号の一定の復号時間を保証する１つの方法が、誤り訂正符号を含むテーブルを記憶装置内に記憶することである。しかし、データビットを冗長ビットと共に記憶する必要はない。誤り訂正符号が、データビットが順次整数のリストを形成するように順序付けられる場合、正しい符号語をインデックスするためにアドレスが使用されることができる。データ部分は、冗長部分のアドレスを取り出して、第１の冗長部分のアドレスを減算することにより形成されることができる。この演算は、必要とされる記憶領域の量を大きく低減することができる。

誤り訂正符号を記憶するこの方法はまた、データビットの一定時間の符号化を可能にすることに留意されたい。符号語たとえばランダムな符号語を生成するためには、データ部分が、たとえばランダムなデータ部分が生成され、ランダムなデータ部分は適切に探索された冗長部分と組み合わせられる。組み合わせることは連結により行われることができる。

好ましい実施形態では、鍵導出アルゴリズムはインデックスにさらに依存し、暗号システムは、インデックスを確立するためのインデックスエスタブリッシャを含む。暗号システムを使用して別のシステムを認証する一部の機器では、鍵を頻繁に更新することが有益である。鍵導出にインデックスを導入することにより、これが達成される。インデックスはその他のシステムに伝達されることができる。次に、その他のシステムは、第２の符号語のコピーから、または非ランダム化された（ｄｅ−ｒａｎｄｏｍｉｚｅｄ）第１の符号語などから、使用される鍵を構築する、たとえば登録ビットストリングのコピーを形成することができる。インデックスはまた、ハッシュ関数のファミリからハッシュ関数を選択するために使用されることができる。選択されたハッシュ関数は、鍵導出関数として使用されることができる。

好ましい実施形態では、鍵導出アルゴリズムは、インデックスに依存するハッシュ関数のファミリからハッシュ関数を選択するステップを含む。鍵エスタブリッシャは、前記選択されたハッシュ関数を第１の符号語に適用するように構成される。ランダム化する構成要素の影響を取り除くことは、ランダム化する構成要素に適用される選択されるハッシュ関数に依存する。

鍵導出をハッシュ関数のファミリと結びつけることは、発明者の洞察力であった。ハッシュ関数の選択はインデックスを通してランダム化されるので、ファミリ内のハッシュ関数の個々の暗号要件は、少なくともより機密性の低い応用例に対して低減されることができる。具体的には、ハッシュ関数が鍵導出に適用された後までランダム化する構成要素の削除を延期する限り、このことが十分な暗号強度を可能にする。

再現できる符号語を再現できるように確立するための暗号システムがまた、本発明の原理を使用して構築されることができる。一部の応用例では、暗号鍵を確立することが必須でないことがある。一意のビットストリングだけが、たとえば再現できる符号語が十分なことがある。再現できる符号語は、冗長を取り除くために最初に復号されることができることに留意されたい。

暗号鍵を再現できるように確立するための暗号方法が、物理的システム内に含まれる構成要素の物理的な少なくとも部分的にランダムな構成に依存する初期ビットストリングを確立するステップと、誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを、初期ビットストリングに依存して確立するステップであって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが、誤り訂正符号に関連付けられるステップと、誤り訂正アルゴリズムを使用して、第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するステップと、所定の鍵導出アルゴリズムを適用することにより第１の符号語に依存する暗号鍵を確立するステップとを含む。方法は、ランダム化する構成要素を生成するステップをさらに含み、第１の訂正可能ビットストリングを確立するステップが、ランダム化する構成要素にさらに依存し、暗号鍵を確立するステップが、ランダム化する構成要素の影響を取り除くことにより暗号鍵を再現できるようにするためのランダム化する構成要素にさらに依存する。

暗号方法の好ましい実施形態が、第１の訂正可能ビットストリングを複数のサブストリングに分割するステップを含み、複数のサブストリングの特定のサブストリングが、別の誤り訂正符号の別の訂正可能な近傍内にあって、別の誤り訂正符号内の別の符号語すべての列挙から実質的に所定の時間の範囲内で特定の別の符号語選択し、特定の別の符号語が所定の距離関数に従って特定のサブストリングに最も近くにあり、第１の符号語を確立するステップが特定の別の符号語にさらに依存する。

暗号方法の好ましい実施形態がインデックスを確立するステップを含み、暗号鍵を確立するステップがインデックスにさらに依存する。

本発明による方法がまた、コンピュータに実装される方法としてコンピュータ上に実装されることができる。本発明による方法のための実行可能コードは、コンピュータプログラム製品上に記憶されることができる。

コンピュータプログラムは、コンピュータ上で実行されるとき、本発明による方法のステップをすべて実行するように適合されるコンピュータプログラムコード手段を含む。好ましくは、コンピュータプログラムはコンピュータ読出可能媒体上に具体化される。

物理的クローン不能関数（ＰＵＦ）に依存する暗号鍵を確立するためのシステムでは、内部の暗号鍵と相関がある内部情報が、サイドチャネルを介してシステムの外側に漏洩されることが問題となり得る。この問題は、本発明に従って暗号鍵を再現できるように確立するための暗号システムによって軽減される。システムは、初期ビットストリングが得られる構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムを含む。誤り訂正器が、初期ビットストリング内に発生する偏差値を訂正する。ランダム化の使用を通して、誤り訂正器はランダム化されたデータに対して作用する。それにより、サイドチャネルを通した情報漏洩が低減される。誤り訂正後、初期ビットストリングから暗号鍵が得られることができる。

本発明が実施例により、および添付の図面を参照してより詳細に説明される。

暗号システムの一実施形態のアーキテクチャを略示する構成図である。 ノーマライザの一実施形態のアーキテクチャを略示する構成図である。 誤り訂正符号を略示する図である。 誤り訂正器の一実施形態のアーキテクチャを略示する構成図である。 符号語を略示する構成図である。 符号語を略示する構成図である。

（参照符号のリスト）
図を通して、同様のまたは対応する特徴が同じ参照符号により示される。
１００ 暗号システム
１１０ 初期ビットストリングプロデューサ
１１２ 物理的システム
１２０ ノーマライザ
１３０ ランダマイザ
１４０ 誤り訂正器
１４２ 電源
１５０ トランスフォーマ
１６０ 鍵エスタブリッシャ
２０４ ヘルパデータストア
２０６ 加算器
２１２ 乱数発生器
２１４ 符号器
３００ ベクトル空間
３０２ａ 初期ビットストリングへのヘルパデータの加算
３０２ｂ 第２のビットストリングへのヘルパデータの加算
３０４ａ 第２の訂正可能ビットストリングへのランダムな符号語の加算
３０４ｂ 初期ビットストリングへのランダムな符号語の加算
３０６ 第１の符号語からのランダムな符号語の減算
３１０ 初期ビットストリング
３２０ 第２のビットストリング
３３０ 第１の訂正可能ビットストリング
３３２ 第１の符号語
３４０ 第２の訂正可能ビットストリング
３４２ 第２の符号語
３５０ 初期領域
３６０ 第１の訂正可能な近傍
３７０ 第２の訂正可能な近傍
４１０ ビットストリング受信機
４２２ 第１の訂正器
４２４ 第２の訂正器
４３０ ビットストリング連結器（ｃｏｎｃａｔｅｎａｔｏｒ）
５１０、５２０ 符号語
５２１ 小さな符号語

後半で、ＰＵＦに関連する３つの主要な発明の説明が示される。本発明は共に使用されることができるが、互いに独立に、または別の技術と組み合わせて使用されることができる。

要約すると、主要な発明は以下の通りである：
１．誤り訂正入力のランダム化
誤り訂正前にランダム化を使用することがＰＵＦの出力を再現できるようにし、一方でサイドチャネルを通して誤り訂正器から出る情報を低減する。

２．独立した実行時間を有する誤り訂正器
誤り訂正器の動作に対する実行時間が誤り訂正器の入力から独立しているように誤り訂正器を構成することが、時間消費のサイドチャネルを通して漏洩される情報を低減する。

可能な実施形態は、以下の通りである。暗号鍵を再現できるように確立するための暗号システムが、構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムと、構成に依存する初期ビットストリングを確立するための初期ビットストリングプロデューサと、誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを初期ビットストリングに依存して確立するためのノーマライザであって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが、誤り訂正符号に関連付けられるノーマライザと、誤り訂正アルゴリズムを使用して第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するための誤り訂正器と、所定の鍵導出アルゴリズムを適用することにより第１の符号語に依存する暗号鍵を確立するための鍵エスタブリッシャとを含み、誤り訂正器が第１の訂正可能ビットストリングを複数のサブストリングに分割するように構成され、複数のサブストリングの特定のサブストリングが、別の誤り訂正符号の別の訂正可能な近傍内にあり、かつ別の誤り訂正符号内のすべての別の符号語の列挙から実質的に所定の時間の範囲内に、所定の距離関数に従って特定のサブストリングに最も近い特定の別の符号語を選択し、第１の符号語を確立することが特定の別の符号語にさらに依存する。

３．鍵確立でのインデックス使用
鍵導出をインデックスに依存させることにより、鍵更新が達成される。通信のために使用される鍵は、異なるインデックスが使用されるたびに異なることがある。さらに、鍵導出関数、たとえばハッシュ関数のあり得るサイドチャネルがインデックスの使用を通してマスクされる。

可能な実施形態が以下の通りである。暗号鍵を再現できるように確立するための暗号システムが、構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムと、構成に依存する初期ビットストリング（３１０）を確立するための初期ビットストリングプロデューサと、誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを初期ビットストリングに依存して確立するためのノーマライザであって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが誤り訂正符号に関連付けられるノーマライザと、誤り訂正アルゴリズムを使用して第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するための誤り訂正器と、所定の鍵導出アルゴリズムを適用することにより第１の符号語に依存する暗号鍵を確立するための鍵エスタブリッシャとを含み、鍵導出アルゴリズムがインデックスにさらに依存し、暗号システムがインデックスを確立するためのインデックスエスタブリッシャを含む。

これらの発明は多くの異なる形態の実施形態が可能であるが、本開示は本発明の原理の例示として考えられるべきであり、かつ示され説明される具体的実施形態に本発明を限定することを意図されるものではないという条件で、１つまたは複数の具体的実施形態が図面で示され本明細書で詳細に説明される。

図１は暗号システム１００の第１の実施形態のアーキテクチャを略示する構成図である。この実施形態、および一部がその他の図面と共に説明されるこの実施形態の様々な構成要素に対して、様々な代替形態が存在することが留意される。

暗号システム１００は初期ビットストリングプロデューサ１１０、ノーマライザ１２０、誤り訂正器１４０、および鍵エスタブリッシャ１６０を含む。暗合システム１００は、鍵エスタブリッシャ１６０と共に使用するためのトランスフォーマ１５０をさらに含む。

初期ビットストリングプロデューサ１１０は物理的システム１１２に結合されるが、たとえば物理的システム１１２を含む。物理的システム１１２は、構成要素の物理的な少なくとも部分的にランダムな構成を含む。初期ビットストリングプロデューサ１１０は、構成に依存する初期ビットストリングを確立するように構成される。そのような物理的システムの様々な例が存在する。たとえば、物理的システム１１２は、ＳＲＡＭに電源を供給した後であるが、データがＳ−ＲＡＭメモリに書かれる前に初期ビットストリングプロデューサ１１０により読み出されるＳ−ＲＡＭメモリであってもよい。Ｓ−ＲＡＭメモリは様々な構成要素から構築され、互いに対するそれらの構成要素の正確な構成は、製造プロセスの変動のために常に少しランダムになる。これらのランダムな変動が、規定されない読出動作、すなわち先行する書込動作なしの読出動作の結果を少なくとも部分的に決定する。

初期ビットストリングプロデューサ１１０は、初期ビットストリングの正規化のためにノーマライザ１２０に伝達可能に結合される。初期ビットストリングは、典型的には正確に再現できない。初期ビットストリングプロデューサ１１０が多数回物理的システム１１２を読み出す場合、多数の多分異なる初期ビットストリングを得る。ノーマライザ１２０は初期ビットストリングに依存して第１の訂正可能ビットストリング３３０を確立するように構成される。第１の訂正可能ビットストリング３３０を含む様々な変数の可能な構成が略示される図３を参照する。図３は以下により十分に説明される。第１の訂正可能ビットストリング３３０は、誤り訂正符号の訂正可能な近傍内に、すなわち、誤り訂正符号内の一部の誤り訂正符号語の訂正可能な近傍内にある。たとえば、初期ビットストリングプロデューサが多くても１２７ビットのビットストリングを生成する一実施形態では、ＢＣＨ符号（１２７、１５、５５）誤り訂正符号が使用されることがある。ＢＣＨ符号は巡回符号であることに留意されたい。この符号からの符号語が１２７ビット長であるが、望まれれば符号語はパディングされることができる。たとえば、１つのパディングビット、たとえばゼロのビットを追加して、１２７ビットの符号語が１６バイトに好都合に記憶されることができる。図５ａは、１２７ビットの符号語５１０を略示する。

符号語の動作については、ノーマライザ１２０が、ランダム化する構成要素を符号語に提供するためにランダマイザ１３０に依存する。図１では、ランダマイザ１３０はノーマライザ１２０内に含まれる。しかし、ランダマイザ１３０はまた、ノーマライザ１２０に伝達可能に結合されることができる。ランダマイザ１３０は、初期ビットストリングから得られる訂正可能ビットストリングをランダム化するために使用される。初期ビットストリングプロデューサ１１０が多数回使用される場合、多数の初期ビットストリングが、接近していることが好ましい。しかし、ランダム化する構成要素の適用を通して、ノーマライザ１２０が多数の初期ビットストリングに対して確立する多数の訂正可能ビットストリングは、接近していないことが好ましい。別のところで説明されるように、ノーマライザ１２０については様々な可能な実施形態があり得る。

ノーマライザ１２０は、訂正可能な近傍の要素を符号語にマッピングする所定の誤り訂正アルゴリズムを使用して、第１の訂正可能ビットストリング３３０を第１の符号語３３２にマッピングするように誤り訂正器１４０に伝達可能に結合される。たとえば、誤り訂正器は符号語５１０を生成することができる。誤り訂正器１４０は任意の適切な誤り訂正アルゴリズムを使用することができる。たとえば、誤り訂正符号がＢＣＨ符号である場合、誤り訂正器は、訂正可能ビットストリングを符号語にマッピングするためにたとえばＢｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズムを使用することができる。

誤り訂正器１４０は、自己の動作のために電源１４２を使用する。たとえば、誤り訂正器１４０は電源１４２により電力を供給される集積回路として実現されることができる。誤り訂正器１４０はまた、電源１４２により電力を供給されるマイクロプロセッサ上で実行されるソフトウェアの形で実現されることができる。いずれの場合も、誤り訂正器１４０の動作が、電源１４２を観測することによりいくらか観測できるということがあり得る。誤り訂正器１４０と電源１４２の間の結合は安全な周囲の外側にあることがあり、攻撃者にアクセスできることがあることに留意されたい。たとえば、使用される電子機器のタイプに応じて、高いハミング重みを有する語（ｗｏｒｄ）の処理が、低いハミング重みを有する語の処理よりも多くの電力を消費することがあり、この差が電源１４２の観測を通して観測できることがある。誤り訂正器１４０の内部動作も、別のサイドチャネルを介して暗号システム１００の外側に漏洩することがある。たとえば、機器の電磁放射が誤り訂正器１４０の動作の影響を受けて変化することがある。

誤り訂正中にサイドチャネルを通して漏洩される情報が、第１の符号語３３２および／または第１の訂正可能ビットストリング３３０に関連付けられることがある。しかし正規化は、第１の訂正可能ビットストリング３３０をランダム化する、ランダム化する構成要素に依存する。したがって、誤り訂正中にサイドチャネルを通して漏洩される情報もランダム化され、そのことがサイドチャネル問題を軽減する。

暗号システム１００の別の構成要素が動作の自己の内部状態に関する情報を、サイドチャネルを通して漏洩することがあるが、より大規模な構成要素、たとえば誤り訂正器１４０がそうする可能性が高いことが留意される。より大規模な構成要素は、典型的にはより多くの電力を使用する、および／またはより長い実行時間を有する。

第１の訂正可能ビットストリング３３０がランダム化する構成要素に依存するということは、別の有利な点に結びつけられる。ランダム化する構成要素のために、第１の訂正可能ビットストリング３３０は、実質的に暗号システム１００のそれぞれの、または大部分の、または一部の使用に対して相当に異なることがあり得る。使用できる情報をサイドチャネルから抽出することが、多数の実際の測定値、たとえば電力測定値の統計解析を必要とすることが観測された。典型的には、多くの測定値が何らかの基準に従って選択され、次に平均される。測定値の中にランダムな要素を導入することにより、多数の測定値が互いに関連付けられることがより少なくなり、解析を複雑にする。ランダム化する構成要素が典型的には攻撃者に知られていないので、測定値がより関連付けられなくなる方法は攻撃者に未知である。

暗号システム１００の別の構成要素は、図に示される構成要素も、示されない構成要素もともに電源１４２を使用することができることに留意されたい。

誤り訂正器１４０は、この実施形態ではトランスフォーマ１５０を通して鍵エスタブリッシャ１６０に伝達可能に結合される。トランスフォーマ１５０は、ランダム化する構成要素の影響を取り除くことにより、第１の符号語３３２を第２の符号語３４２に変換する。第２の符号語３４２は第１の符号語３３２と異なることが好ましい。好ましくは、第１の符号語３３２および第２の符号語３４２は互いに少しだけ関連付けられる。より好ましくは、第１の符号語３３２および第２の符号語３４２は、両方が符号語であること以外、関連がない。すなわち、第１の符号語の完全な知識がある場合でさえ、第２の符号語に関する追加の知識が全くない。

トランスフォーマ１５０は、鍵エスタブリッシャ１６０に伝達可能に結合される。鍵エスタブリッシャ１６０は、所定の鍵導出アルゴリズムを第１の符号語に適用することにより暗号鍵を確立する。初期ビットストリング３１０内の偏差は誤り訂正器により取り除かれ、ランダム化する構成要素により引き起こされた偏差はトランスフォーマ１５０により取り除かれたので、暗号鍵は再現できる。

鍵エスタブリッシャ１６０は、たとえば誤り訂正符号の復号機能を適用して、第２の符号語３４２内の冗長を取り除くことができる。あるいは、またはさらに、鍵エスタブリッシャ１６０はハッシュ関数を適用することができる。また、鍵エスタブリッシャ１６０は、インターネット標準ＲＦＣ２８９８に記載されるような鍵導出関数（ＫＤＦ）に対する入力として第２の符号語３４２または復号版を使用することができる。

機密性を要する応用については、鍵を探索するための所要時間を低減するために、サイドチャネルから少しずつ収集されるどんな情報でも利用されることができるという危険性が存在するので、攻撃者が暗号鍵に関してどんなことでも知る場合が問題である。したがって、誤り訂正器がランダム化された情報に対して作用する場合が有利な点である。

暗号システム１００の様々な構成要素が、専用集積回路から作られることができる。それらの構成要素はまた、汎用回路、たとえばソフトウェアを実行するマイクロプロセッサから作られることができる。また、ハイブリッド、たとえばある種の専用回路を使用するマイクロプロセッサもあり得る。しかし、物理的システム１１２は、少なくとも何らかの物理的構成要素を含む。

図３を使用してランダム化の実施形態をさらに説明する。

図３は、ベクトル空間の概略表示を示す。好ましくはベクトル空間の要素はビットストリングである。図３内の点はベクトル空間の要素を表す。たとえば、ベクトル空間は一定の長さのすべてのビットストリングの集合である。ベクトル空間を使用して、加法関数および距離関数が関連付けられる。好ましくは、２つのバイナリビットストリングが排他的論理和加算（ＸＯＲ）を使用して加算される。すなわち、２つのビットストリングが、対応するビットの排他的論理和をとることにより加算される、すなわち、第１のビットストリングの第１のビットが、第２のビットストリングの第１のビットと排他的論理和をとられ、以下同様に、最後に、第１のビットストリングの最後のビットが、第２のビットストリングの最後のビットと排他的論理和をとられる。加算に関連して減算があり得る。減算は、特定のビットストリングに特定のビットストリングを加算し、次に特定のビットストリングを減算することが特定のビットストリングをもたらすという特性を有する。排他的論理和加算は、特定のビットストリングに同じビットストリングを２度加算することが特定のビットストリングをもたらすという特性を有することに留意されたい。すなわち、排他的論理和を使用するとき、加算関数が減算関数と同等となる。

好ましくは、距離関数として、いわゆるハミング距離が使用される。２つのビットストリングが、異なる値を有する対応する場所でビット数に等しいハミング距離を有する。２つのビットストリングのハミング距離を計算する１つの方法が、排他的論理和関数を使用してビットストリングを共に加算し、次に、結果の「１」ビットの数をカウントすること、すなわち、結果のハミング重みを決定することである。

様々な加法関数および距離関数を有する多くのタイプのベクトル空間が存在することが留意される。具体的には、それぞれ３値誤り訂正符号および４値誤り訂正符号を有する３値ビットストリングおよび４値ビットストリングが使用されることができることが指摘される。３値ビットストリングも４値ビットストリングも、任意選択でバイナリビットストリングとして表現されることができる。説明を容易にするために、バイナリビットストリングおよび対応するバイナリ誤り訂正符号が実施例で使用される。

ベクトル空間内のビットストリングのサブセットが誤り訂正符号の符号語を形成する。誤り訂正符号の任意の２つの異なる要素の最短距離が最小距離と呼ばれ、しばしば「ｄ」で示される。また、誤り訂正符号に関連付けられるのが、ｄ／２に等しく切り捨てられた最大訂正可能距離である。訂正可能距離は、しばしば「ｔ」で示される。特定の符号語が自己のビットに多くてもｔの修正を使用して異なるビットストリングに変更された場合、特定の符号語は異なるビットストリングから一意に再現されることができる。特定の符号語からせいぜい距離ｔにあるビットストリングの集まりが、その特定の符号語の訂正可能な近傍と呼ばれる。誤り訂正符号内の符号語のすべての訂正可能な近傍の和集合が、誤り訂正符号の訂正可能な近傍と呼ばれる。しばしば、誤り訂正符号のパラメータが３つ組（ｎ、ｋ、ｄ）として要約される。ここで、ｄは最小距離を示し、ｎはビットストリング中のビット数を、具体的には訂正可能ビットストリングのビット数を示し、ｋは符号語空間の次元である。具体的には、コードがバイナリである場合、符号語の数は２＾ｄに等しい。

誤り訂正符号に関連付けられるのが、訂正可能な近傍の要素を誤り訂正符号に関連付けられる符号語にマッピングするための誤り訂正アルゴリズムである。誤り訂正アルゴリズムは、特定の符号語の訂正可能な近傍の要素を入力として受け取り、出力として特定の符号語を生成する。好ましくは、誤り訂正符号に関連付けられる符号器もある。符号器は符号語数までの範囲で入力として数値を受け取り、出力として符号語を生成する。たとえば、乱数を符号化することによりランダムな符号語が生成されることができる。好ましくは、復号器も誤り訂正符号に関連付けられる。復号器は入力として符号語を受け取り、出力として数値を生成する。好ましくは、復号器は符号器の逆として動作する。符号器は数値に冗長を追加するが、復号器は冗長を取り除く。数値はまた、誤り訂正符号内のビットストリングよりも短い長さのｋビットのビットストリングとして表されることできる。

図３は２つの符号語を、すなわち第１の符号語３３２および第２の符号語３４２を示す。第１の訂正可能ビットストリング３３０が、第１の符号語３３２近くの第１の訂正可能な近傍３６０内に含まれ、誤り訂正アルゴリズムにより第１の符号語３３２にマッピングされる。第２の訂正可能ビットストリング３４０が、第２の符号語３４２近くの第２の訂正可能な近傍３７０内に含まれ、誤り訂正アルゴリズムにより第２の符号語３４２にマッピングされる。誤り訂正符号の訂正可能な近傍内に存在しないビットストリングがあり得ることに留意されたい。

好ましくは、誤り訂正符号は線形である、すなわち、任意の２つの符号語の加算もまた符号語である。線形符号を使用することには、ランダム化することがより容易であるという有利な点がある。線形符号には、第１の訂正可能ビットストリング３３０とランダムな符号語の和の誤り訂正が、ランダムな符号語と第１の訂正可能ビットストリングの誤り訂正の和に等しいという特性がある。

ランダムな符号語は、ランダム化する構成要素の役割を果たす。符号語がまた、異なる方法で選択され、依然としてランダム化する構成要素であり得ることに留意されたい。たとえば、いくつかのランダムだが固定の符号語を含む所定のリストが使用されることができる。暗号鍵のそれぞれの次の決定に対して、リストからの次の符号語がランダム化する構成要素として使用される。次の符号語は順次、またはランダムになどで選択されることができる。ランダム化する構成要素は、真のランダムソース、擬似ランダムソース、リストからのランダムな選択肢、リストからの変化する選択肢などから得られることができる。

動作中、暗号システム１００は以下のように動作することができる。初期ビットストリング３１０を確立するための初期ビットストリングプロデューサ１１０が、典型的には常に等しいわけではないが、いくらか変化することがあるビットストリングを生成する。初期ビットストリングプロデューサ１１０は、ベクトル空間の初期領域３５０内にあるビットストリングを生成する。初期ビットストリングプロデューサ１１０により生成されるビットストリングは常に同じではないが、ビットストリングの任意の２つがそれらの間に短い距離を有する。例外があり得る、すなわち、初期ビットストリングプロデューサ１１０は初期領域３５０内にない孤立値（ｏｕｔｌｉｅｒ）をときどき生成することがあることに留意されたい。これが応用にとって十分まれであるとき、これが問題となる必要がない。

初期ビットストリングは、ヘルパデータの適用を通して符号語にマッピングされることができる。ヘルパデータは登録段階中に得られることができる。好ましくは、初期ビットストリングプロデューサは登録ビットストリング（示されていない）を確立し、ヘルパデータが、登録ビットストリングを符号語、たとえば第２の符号語３４２にマッピングするように確立される。ヘルパデータは、登録ビットストリングに十分近いビットストリングに適用されたとき、訂正可能な近傍３７０内にあるビットストリングが得られるようなものである。具体的には、ヘルパデータが初期ビットストリング３１０に適用された場合、第２の訂正可能ビットストリング３４０が得られる。

当技術分野では、ヘルパデータを生成するための様々の方法が知られている。２つのそのような方法が説明される。ヘルパデータを生成する第１の方法では、ヘルパデータは、初期ビットストリング内のビットのどのサブセットが、どの順序で使用されるべきかを示す選択データ構造を含むことができる。ヘルパデータが初期ビットストリング３１０に適用された後、登録ビットストリング内の対応するビットストリングとして異なる値を有する初期ビットストリング内のビットが、第２の符号語３４２と多くても１ビットの差をもたらす。

ヘルパデータを生成する第２の方法では、ヘルパデータは、登録ビットストリングと第２の符号語３４２の間の差であるビットストリングを含む。たとえば、排他的論理和加算を使用するとき、ヘルパデータは、登録ビットストリングと第２の符号語の排他的論理和加算を含むことができる。

これらの２つの方法の間の様々な組合せが可能である。たとえば、ヘルパデータは、どのビットがどの順序で使用されるかも示し、ビットの一部が使用される前に反転させられるかをも示すことができる。ヘルパデータは、ヘルパデータストア内に記憶されることができる。

登録段階後の運用使用では、初期ビットストリングプロデューサ１１０が初期ビットストリング３１０を生成する。初期ビットストリング３１０に対して、ヘルパデータは、ノーマライザ１２０、および第１の訂正可能ビットストリング３３０をもたらすランダム化する構成要素により適用される。誤り訂正器１４０は、第１の訂正可能ビットストリング３３０を第１の符号語３３２にマッピングする。第１の符号語３３２から鍵が得られ、その間、ランダム化する構成要素が取り除かれる。初期ビットストリング３１０から第１の訂正可能ビットストリング３３０に、または第１の符号語３３２から鍵に進むことが、様々な方法で行われることができる。

たとえば、初期ビットストリング３１０から第１の訂正可能ビットストリング３３０に進むには、ノーマライザ１２０が初期ビットストリング３１０にヘルパデータをまず適用することができ、図では３０２ａで示され、これが第２の訂正可能ビットストリング３４０を与える。次に、第１の訂正可能ビットストリング３３０を得るために、第２の訂正可能ビットストリング３４０にランダム化が適用されることができる。このステップは３０４ａで示される。あるいは、ランダマイザ１２０が、初期ビットストリング３１０にランダム化をまず適用して、第２のビットストリング３２０を得ることができる。このステップは３０４ｂで示される。次に、第１の訂正可能ビットストリング３３０を得るために、ヘルパデータが適用されることができる。このステップは３０２ｂで示される。

初期ビットストリング３１０が登録ビットストリングに十分近い場合、第１の訂正可能ビットストリング３３０は、第１の訂正可能な近傍３６０の範囲内に、すなわち第１の符号語３３２に対して訂正可能な距離の範囲内にある。その場合、誤り訂正アルゴリズムは、第１の訂正可能ビットストリング３３０を第１の符号語３３２にマッピングすることができる。

第１の符号語３３２から暗号鍵に進むためには、トランスフォーマ１５０がランダム化する構成要素をまず取り除いて、第２の符号語３４２を得ることができる。このステップは３０６で示される。次に、たとえばハッシュ関数を適用することにより、または第２の符号語３４２を復号することにより、第２の符号語３４２から鍵を導出する。

あるいは、第１の復号されたビットストリングを得るために、第１の符号語３３２がまず復号され、次に、ランダム化が取り除かれることができる。たとえば、第１の符号語がまず復号されることができる、すなわち、たとえば第１の復号されたビットストリング（示されていない）の中のパリティビットを取り除くことにより、第１の符号語内の冗長が捨てられることができる。第１の復号されたビットストリングは、依然としてランダム化する構成要素に依存する。次に、第２の復号されたビットストリング（示されていない）を得るために、ランダム化する構成要素の影響が第１の復号されたビットストリングから取り除かれる。たとえば、ランダム化する構成要素がランダムな符号語である場合、ランダムな復号されたビットストリングに復号されることができる。次に、第２の復号されたビットストリングを得るために、ランダムな復号されたビットストリングが、第１の復号されたビットストリングから減算されることができる。第２の復号されたビットストリングは、もはやランダム化する構成要素に依存しない。第２の復号されたビットストリングは暗号鍵として使用されることができる、または別の鍵導出アルゴリズムが第２の復号されたビットストリングに適用されることができる。すなわち、誤り訂正器が第１の符号語を生成した後、まず冗長を低減するためのステップが行われることができ、非ランダム化されるステップが続き、多分、別の冗長低減ステップが続く。

誤り訂正器が第１の訂正可能ビットストリング３３０を第１の符号語３３２にマッピングするので、登録ビットストリングからの初期ビットストリングの偏差が取り除かれる。ランダム化する構成要素の影響も取り除かれた後、暗号システム１００により暗号鍵が再現されることができる。

鍵導出を適用する前に、鍵エスタブリッシャ１６０は、暗号システム１００の動作をさらに不明瞭にするために固定した秘密のビットストリングを加えることができる。これが、暗号鍵をＰＵＦ内に記憶されるビットストリングと秘密のビットストリングの両方に結びつける。秘密のビットストリングは、メモリ内に、好ましくは安全な記憶装置、たとえば安全なポリヒューズ（ｐｏｌｙ ｆｕｓｅ）内に記憶されることができる。

図２には、ノーマライザ１２０の具体的実施形態に対する概略アーキテクチャが示されている。初期ビットストリング１１０は、一定の長さのバイナリ初期ビットストリング３１０を生成するように構成される。

ノーマライザ１２０内には、ヘルパデータビットストリングを記憶するためにヘルパデータストア２０４が含まれる。ヘルパデータビットストリングは、初期ビットストリングプロデューサ１１０により確立される登録ビットストリングと第２の符号語３４２の間の差として前に得られることができる。たとえば、ヘルパデータビットストリングはヘルパデータビットストリングエスタブリッシャを使用して確立される。ヘルパデータビットストリングエスタブリッシャは暗号システム１００内に含まれることがあり、その上、登録中に暗号システム１００に一時的に結合されることができる。登録段階の後、ヘルパデータストア２０４は、ヘルパデータの少なくとも１つの表現を記憶し、たとえば、ヘルパデータは暗号化された形態で記憶されることができ、その場合、ヘルパデータストア２０４はデクリプタ（ｄｅｃｒｙｐｔｏｒ）に結合される。ノーマライザ１２０はまた、たとえば排他的論理和加算を使用してビットストリングを加算するための加算器２０６を含む。ランダマイザ１３０は乱数発生器２１２および符号器２１４を含む。ランダマイザ１３０は、乱数を符号化することによりランダムな符号語を生成するように構成される。

動作については、加算器２０６がヘルパデータビットストリング、初期ビットストリング３１０、およびランダムな符号語を共に加算する。これは任意の順序で行われることができることに留意されたい。たとえば、ヘルパデータを初期ビットストリング３１０に加算する（３０２ａ）ことにより、第２の訂正可能ビットストリング３４０が得られる。ランダムな符号語を第２の訂正可能ビットストリング３４０に加算する（３０４ａ）ことにより、第１の訂正可能ビットストリング３３０が得られる。あるいは、ランダムな符号語を初期ビットストリング３１０に加算する（３０４ｂ）ことにより、原理的にベクトル空間３００の任意のランダムなビットストリングとなることができる第２のビットストリング３２０が得られる。ランダムなビットストリングを第２のビットストリング３２０に加算する（３０２ｂ）ことにより、第１の訂正可能ビットストリング３３０が得られる。最後に、ランダムな符号語を第１の符号語３３２から減算する（または排他的論理和が使用される場合は加算する）ことにより、第２の符号語３４２が得られる。あるいは、ヘルパデータおよびランダムな符号語はまた、まず共に加算され、次に、その結果に初期ビットストリング３１０を加算することができる。

加算器２０６の出力は、誤り復号のために誤り訂正器１４０に転送される。

さらにマスクするために、ノーマライザ１２０は追加の誤りを導入することができる。たとえば、ランダム化する構成要素は、所定の境界未満のハミング重みを有する誤りビットストリングを含むことができる。誤りビットストリングはまた、加算器２０６により初期ビットストリングに加算されることができる。好ましくは、境界は、登録ビットストリング境界からの初期ビットストリングの予想される偏差の数値に所定の境界を加算したものが、誤り訂正符号の訂正可能距離未満であるように選択される。予想される偏差の数値は、多数の初期ビットストリングに対して偏差の数値を得て、数値の分布を確立することによって確立されることができる。好ましくは、誤りビットストリング内のハミング重みはランダムである、たとえば区間、たとえば０から境界までの区間からランダムに選択される。このタイプのランダム化に対して、トランスフォーマは補償する必要がないことに留意されたい。ランダムな数値の誤りを導入することは、暗号システムを含む機器が、制御された数値の誤りが導入されるような方法で動作させられ、その結果、機器の出力が機器の内部動作に関する情報を明らかにすることがある誤り攻撃を防ぐまたは遮断するのに役立つことができる。追加の誤りを導入することにより、攻撃者にとって未知のいくつかの数の追加の誤りが導入されるので、攻撃者によって導入される誤りと機器の動作の間の関係が分かりにくくされるようになる。

ノーマライザ１２０を構成する１つの方法が、第一に、たとえば誤りを導入するステップやマスキングビットストリングを加算するステップなどを含む、たとえば第１のランダマイザを使用して、初期ビットストリングに対して第１のランダム化する変換を適用すること、第二に、ヘルパデータに依存するできあがったビットストリングに対して第２の変換を適用して、たとえばマッパ（ｍａｐｐｅｒ）を使用して、できあがったストリングを中間の訂正可能ビットストリングにマッピングすること、第三に、たとえばランダムな符号語を加算するステップを含む、中間の訂正可能ビットストリングに対する第３のランダム化動作を適用し、ランダムな置換を適用し、誤りを導入するなどして第１の訂正可能ビットストリングを得ることである。この構成を使用するとき、第１の変換または第３の変換が任意選択である。好ましくは、第３のランダム化が中間の訂正可能ビットストリングの訂正可能な性質を保存する。たとえば、誤り訂正符号および第３の変換が、誤り訂正符号が第３の変換の下で不変であるように選択されることができる。変換が符号語を符号語にマッピングする場合、誤り訂正符号が変換の下で不変である。

ランダム化の１つの有利な方法が以下である。置換のクラスの下で不変である誤り訂正符号が選択される。ノーマライザは、適切な方法を使用して、たとえばヘルパデータビットストリングを加算する、または選択データ構造を初期ビットストリングに適用して、中間の訂正可能ストリングにマッピングする。ランダム化する構成要素は、置換クラスから選択されるランダムな置換を含み、第１の訂正可能ビットストリングを得るために中間の訂正可能ビットストリングに適用される。誤り訂正後、ランダムな置換の逆が第１の符号語に適用される。たとえば、誤り訂正符号は、いわゆる巡回符号、たとえばＢＣＨ符号として選択され、置換クラスは巡回置換を含む。

ヘルパデータを構築するために、多くの誤り訂正符号が、たとえばＢＣＨ符号、リード−マラー（Ｒｅｅｄ−Ｍｕｌｌｅｒ）符号、ゴレイ（Ｇｏｌａｙ）符号、リード−ソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号、ＬＤＰＣ符号などが使用されることができる。第１の訂正可能ビットストリング内のビット数以上のブロック長を使用して単一の訂正器だけを含む誤り訂正器１４０が作製されることができることが留意される。しかし、たとえば異なる符号を組み合わせるまたは連結することにより、多数のレベルの符号化を使用することも可能である。有利に多数の符号を組み合わせる１つの方法が、図４に図示されるアーキテクチャで使用される。

好ましくは、第１の訂正可能ビットストリング３３０に依存する第１の符号語を確立するための誤り訂正器の動作時間は、第１の訂正可能ビットストリングから実質的に独立している。これは様々な手段を使って達成されることができる。たとえば、誤り訂正器は時間補償器（ｔｉｍｅ−ｃｏｍｐｅｎｓａｔｏｒ）を含むことができる。時間補償器は、合わせてランダムな量の時間がかかるランダムな数の動作、たとえば待ち合わせ動作または好ましくはダミー動作を実行する。誤り訂正によりかけられた時間の総量は、この方法で不明瞭にされ、入力、すなわち第１の訂正可能ビットストリングから実質的に独立にさせられることができる。好ましくは、誤り訂正器は、実質的に一定時間で動作するように構成される。たとえば、時間補償器は、第１の符号語の確立中に経過した時間の量を測定し、この時間を所定の最大時間から減算し、次に、残りに等しい時間の量を待ち合わせ動作および／またはダミー動作で埋めることができる。

一定の実行時間を有する、誤り訂正符号に関連する誤り訂正アルゴリズムを使用することにより、この効果を達成することも可能である。そのような誤り訂正アルゴリズムの一例が、誤り訂正符号内の符号語をすべて列挙して、第１の訂正可能ビットストリングに最も近い符号語を選択するアルゴリズムである。これらの符号の倍数が連結されることができる。誤り訂正器の時間消費と誤り訂正器の入力との依存を低減することにより、何らかの漏洩低減が達成されることが留意される。

図４に、ビットストリング受信機４１０、多数の訂正器、およびビットストリング連結器４３０を含む誤り訂正器１４０の好ましい実施形態を示す。多数の訂正器のうち、２つが、すなわち第１の訂正器４２２および第２の訂正器４２４が示されている。

第１の訂正可能ビットストリングを受け取るために、ビットストリング受信機４１０が誤り訂正器１４０の入力に接続される。ビットストリング受信機４１０は、第１の訂正可能ビットストリング３３０を多数のサブストリングに分割するように構成される。各サブストリングは、何らかの別の誤り訂正符号の訂正可能な近傍内にある。たとえば、ビットストリング受信機４１０は、所定の固定した境界で分割することができる。多数の訂正可能サブストリングのそれぞれの１つが、多分並列に多数の訂正器の１つに渡される。誤り訂正器１４０は、ただ１つの別の訂正器を含み、別の訂正器を多数回、直列に使用することができることに留意されたい。

多数の訂正器の１つの訂正器が、好ましくは多数の訂正器のそれぞれの１つが、一定時間内に誤り訂正を実行する。たとえば、第１の訂正器４２２が別の訂正可能ビットストリングを受け取り、別の誤り訂正アルゴリズムを使用するように構成される。別の誤り訂正アルゴリズムは、別の誤り訂正アルゴリズムが関連付けられる別の誤り訂正符号内の各符号語と別の訂正可能ビットストリングを比較するように構成されることができる。別の訂正可能ビットストリングに対して訂正可能距離未満の距離を有する別の符号語が検出されたとき、その別の符号語はビットストリング連結器４３０に転送されることができる。好ましくは、別の符号語を検出した後、別の符号語が前に検出されたか後に検出されたかに関係なく、処理時間の量が一定であることを保証するために、第１の訂正器４２２が続けて別の訂正可能ビットストリングをそれぞれの別の符号語と比較する。第１の訂正器４２２が機能しない場合、すなわち、別の符号語を検出しない場合、このことをビットストリング連結器４３０に信号で伝達することができ、その上、誤ったビットストリング、たとえばランダムなビットストリング、またはすべてゼロのビットストリングなどを転送することができる。

誤り訂正符号語内の符号語の数は典型的には大きいが、多数の訂正器全体に分散されることができる連結された符号を使用することにより、別の誤り訂正符号内のすべての符号語を列挙する時間は、処理しやすい大きさまで低減される。連結された符号がまた、サブストリングに順次適用される単一の誤り訂正器により復号されることができる。

好ましくは、ビットストリング受信機４１０は、誤りビットのバーストが多数の訂正器全体に分配されるように、第１の訂正可能ビットストリング３３０内のビットをインターリーブするためのインターリーバ（ｉｎｔｅｒｌｅａｖｅｒ）を含む。

ビットストリング連結器４３０は、多数の訂正器のそれぞれの１つから別の符号語を受け取り、別の符号語を結合して第１の符号語を生成する。

好ましくは、ビットストリング連結器４３０は、多数の別の符号語を連結するための連結器を含む。好ましくは、ビットストリング連結器４３０は、大きな訂正符号およびアルゴリズムを使用して、前記の連結されたビットストリングを誤り訂正するための大規模誤り訂正器を含む。多数の訂正器の１つが故障し、ビットストリングを転送しない、または誤ったビットストリングを転送することが実際に起こり得るので、大規模誤り訂正器は、大規模誤り訂正器を使用してこれを補償することができる。好ましくは、大規模誤り訂正器は大きなブロックサイズ、すなわち、第１の符号語以上のブロックサイズ、および高速を有する。多数の訂正器は誤りのすべてではなくとも大部分を訂正するので、大きな誤り訂正符号は少ない訂正可能距離を有しさえすればよい。

さらに、多数の小規模誤り訂正器を使用することは、１つの一体構造の誤り訂正符号よりも高い効率の復号を与えるが、この効率の増加が結合される符号の速度の低下により補償されることがあることにかかわらない。

たとえば、いくつかのより小さな符号を連結することにより誤り訂正符号が構築されることができる。たとえば、長さ１３５ビットの符号語がＢＣＨ（１５、５、７）誤り訂正符号から取り出される９つのより小さな符号語を連結することにより構築されることができる。図５ｂは連結により得られる符号語の概略図である。図５ｂは、いくつかのより小さな符号語から作られる符号語５２０を示す。各符号語は、より小さな誤り訂正符号から好ましくは互いに独立に取り出された。これらのより小さな符号語のうち９つが示され、そのうちの１つが参照符号５２１でラベル付けされている。

連結された誤り訂正符号から符号語に訂正可能ビットストリングを復号することが、様々な方法で行われることができる。たとえば、第１の訂正可能ビットストリングが複数のサブストリングに分割されることができる。この分割は固定した境界で、たとえば１５ビット後ごとに行われることができる。しかし、分割はより複雑となることがある。たとえば、インターリーブする置換がまず適用されることができる。または、第１の訂正可能ビットストリングに対して複数のサブストリング生成関数を、好ましくは線形関数を適用することにより、サブストリングが得られることができる。後で連結される複数のより小さな符号語を生成するために、誤り訂正器１４０、たとえば第１の誤り訂正器４２２内に含まれることができるより小規模の誤り訂正器が、サブストリングのそれぞれの１つに順次適用されることができる。多数の誤り訂正器が利用できる場合、複数のサブストリングに対して並列に動作させられることができる。たとえば、２つの誤り訂正器、たとえば第１の誤り訂正器４２２および第２の誤り訂正器４２４が利用できる場合、９つのより小さな符号語が５回のバッチで誤り訂正されることができる。

好ましくは、訂正可能ストリング、たとえば訂正可能サブストリングが、誤り訂正符号内のすべての符号語の列挙を使用して復号される。たとえば、符号語プロデューサが、誤り訂正符号内のすべての符号語を順次生成することができる。それぞれの生成された符号語に対して、生成された符号語と訂正可能ビットストリングの間の距離が決定される。好ましくは、誤り訂正符号と関連付けられる距離基準が使用される。好ましくは、距離基準が、ハミング距離である。そのように得られた最も近い符号語が、誤り訂正器の出力で使用されることができる。あるいは、すべての符号語を列挙するルックアップテーブルが使用されることができる。復号が必要とされるたびに、ルックアップテーブルが、符号語を生成する費用を節約する。あるいは、訂正可能ビットストリングを対応する符号語にマッピングする、すべての符号語を含むすべての訂正可能ビットストリングを列挙するルックアップテーブルが使用される。多分、ルックアップテーブルはまた、訂正不能ビットストリングも含む。訂正不能ビットストリングが、誤り、たとえば訂正不具合を示す特殊なビットストリングにマッピングされることができる。あるいは、訂正不能ビットストリングが、最も可能性の高い符号語に、たとえば訂正不能ビットストリングに最も近い符号語の任意の１つにマッピングされる。

誤り訂正符号内のすべての符号語を列挙することにより、誤り訂正符号の実行時間が一定となり、入力から独立していることが保証される。

連結された符号が使用される場合、好ましくは一定時間のアルゴリズム、たとえば上記で説明されたアルゴリズムが各サブストリングに対して使用される。しかし、一定時間のアルゴリズムはまた、より少ないより小さな符号語に対して、またはより小さい符号語の１つに対してさえ利用されることができる。これが利用されるとき、誤り訂正器の実行時間がいくらかマスクされ、それに対応して時間のサイドチャネルを通した漏洩がいくらか低減される。

誤り率に応じて、連結された誤り訂正符号が、代替の誤り訂正符号として使用されることができる。たとえば、ＢＣＨ（１５、５、７）から取り出された９つのより小さな符号語を含む誤り訂正符号が、ＢＣＨ（１２７、１５、５５）符号を置換するためにときどき使用されることがある。まず第一に、そのような符号語は１２７ビットよりも長い。余分な８ビットが、ゼロに設定される、ランダムにされる、または任意の別の都合のよい値に設定される。さらに、ＢＣＨ（１２７、１５、５５）は、２７の誤りまで、すなわち１２７ビットの約２０％まで訂正することができる。ＢＣＨ（１５、５、７）符号語は、同様に１５ビットの２０％となる３つの誤りを訂正することができる。したがって、連結された符号は同等の長さであり、同等の誤り訂正強度がある。長い符号語を使用することはバースト誤りに対してより強いという有利な点を有することができるが、連結された符号はインターリーブする置換の使用によりバースト誤りに対してより弾力性があるようにされることができる。

図５ｂでは、９つのより小さな符号語がそれぞれ順次記憶される。しかし、代替実施形態では、ビットは、たとえばバースト誤りを低減するために置換された順序で記憶される。たとえば、誤り訂正が行われる前に、より小さな符号語に対応するビットを収集するために置換が行われることができる。たとえば、インターリーブする置換がインターリーバを使用して行われることができる。

一実施形態では、誤り訂正符号の符号語、あるいは別の誤り訂正符号、たとえば訂正器４２２および／または４２４により使用されることができるような別の誤り訂正符号の符号語が、ルックアップテーブル内に、たとえば記憶装置（示されてない）内に記憶されることができる。

誤り訂正符号の選択で、記憶領域のサイズの低減を可能にするものがある。誤り訂正符号の一部が、容易に生成されることができる簡単なシーケンスでもよい。具体的には、誤り訂正符号が、符号語のデータ部分内の整数の順次リストを含む場合、この部分の記憶領域を省くことにより実質的節約が実現されることができる。

一例として、以下のテーブルが小さな誤り訂正符号を列挙する。テーブルはブロックサイズが７であり次元が４であるハミング符号である。テーブルは２＾４＝１６の符号語を有する。

符号語は１列目に列挙されている。一実装では、この列は記憶装置内に記憶されることができる。ビットストリングが復号されなければならない場合、リスト内の各符号語が、ビットストリングに最も近い符号語を検出するためにビットストリングと比較される。

理解されることができるように、符号語は、この場合最初の４ビットにより形成され２列目に示されるデータ部分が、順次リストを形成するように、順序よく配置されている。この場合、整数は、バイナリ形式の０から１５である。残りのビットは３列目に示される。誤り訂正特性は、データ部分と、対応する冗長部分の組合せから生まれる。

３列目だけを記憶することにより３／７の節約が達成され、節約は約４３％になる。テーブル内のインデックスを対応する冗長部分と連結することにより符号語が再構築されることができる。ビットストリングを復号するためには、ビットストリングの最初の４ビットがテーブルインデックスと比較され、ビットストリングの最後の３ビットがテーブルインデックスの場所で検出されるテーブルエントリと比較される。

好ましい実施形態では、鍵導出アルゴリズムはインデックスにさらに依存し、暗号システムはインデックスエスタブリッシャを含む。インデックスエスタブリッシャは、たとえば、インデックスを生成するための乱数発生器を含むことができる。暗号鍵が一部の別の関係者との通信のために使用されるとき、暗号システム１００は、インデックスを別の関係者に伝達するように構成される。別の関係者が登録ビットストリングの、または第２の符号語のコピーを有する場合、別の関係者は、インデックスを使って、暗号システム１００が使用したのと同じステップを使用して暗号鍵を導出することができる。好ましくは、別の関係者は、それが可能であっても、別の関係者のノーマライザ内で、ランダム化する構成要素を使用しない。

好ましい実施形態では、鍵導出アルゴリズムは、インデックスに依存するハッシュ関数のファミリからハッシュ関数を選択するステップを含む。鍵エスタブリッシャは、前記選択されたハッシュ関数を第１の符号語に適用するように構成される。ランダム化する構成要素の影響を取り除くことは、ランダム化する構成要素に適用される選択されたハッシュ関数に依存する。

この実施形態に従ってシステムの暗号特性を改善するために、好ましくは、ハッシュ関数のファミリ、およびインデックスに依存するハッシュ関数のファミリからハッシュ関数を選択するための選択関数が、一般的なハッシュ関数である。

ハッシュ関数のすべてのファミリが、ハッシングが実行された後にランダム化する構成要素の影響が取り除かれることができるという要件に適合するわけではない。しかし、ランダム化する構成要素に依存する第１の訂正可能ビットストリングの確立に関して同形のハッシュ関数のファミリが選択されることができる。同形性は、ランダムな構成要素がハッシング後に取り除かれることができるようにする。選択されたハッシュ関数をランダムな構成要素に適用することにより、ランダム化する構成要素が適用された逆の方法で取り除かれることができる、ハッシングされランダム化された構成要素が得られる。

鍵導出をハッシュ関数のファミリと組み合わせることは発明者の洞察であった。ハッシュ関数の選択がインデックスを通してランダム化されるので、ファミリ内のハッシュ関数の個々の暗号要件は、少なくとも機密性の低い応用に対して低減されることができる。具体的には、このことが、ランダム化する構成要素の除去を延期しながら、十分な暗号強度を可能にする。

たとえば、鍵導出関数（圧縮関数としても知られる）については、線形性の特性を有する、インデックスを伴う一般的なハッシュ関数が選択されることができる。このことはランダム化手順がさらに１ステップ行われることができるようにする。ランダム化する構成要素は、ハッシュの出力を適切に補償することにより一般的なハッシュ計算の後、計算の終わりに取り除かれさえすればよい。これはサイドチャネル攻撃に対する実施形態の耐性を改善する。

一例として、ハッシュ関数のファミリについては、いわゆる多項式ハッシュが使用されることができる。多項式ハッシュは、一般的なハッシュ関数の一例である。

多項式ハッシュは、以下のように定義される。すなわち、メッセージｍ、すなわちこの場合第１の符号語が、長さｎビットの部分に分割され、必要であれば、最後の部分はパディングされることができる。すなわち、ｍ＝ｍ１｜｜ｍ２｜｜…｜｜ｍｌである。インデックスｋに対応するハッシュ関数がＧ＿ｋ（ｍ）＝Ｓｉｇｍａ（ｍｉ．ｋ＾ｉ）と定義され、ここで計算は領域ＧＦ（２＾ｎ）全体で行われる。これらの関数はＧＦ（２＾ｎ）内の加法に関して線形であることに留意されたい。ブロック長はあらかじめ決定され、固定され、効果的計算を可能にするように選択され、たとえば、一部の応用例ではｎ＝３２が適切な選択肢である。

マスク、たとえばランダムな符号語がメッセージに、したがってメッセージブロックに加えられた場合、このマスクは式を一通り計算して、マスクのハッシュを計算することにより取り除かれることができる。

別のＧＦ−線形（排他的論理和−線形）な例がテプリッツ（Ｔｏｅｐｌｉｔｚ）ハッシング、バケット（ｂｕｃｋｅｔ）ハッシングである。

算術マスキング、たとえばｍｏｄ ｐまたはｍｏｄ ２＾３２、ｍｏｄ ２＾６４などの加算を使う別の例が使用されることがある。これらはたとえばいわゆるハッシュ、すなわちＭＭＨ、ＮＨ、ＮＭＨなどに含まれる。一部のハッシュ関数については、具体的にはこの範疇では、ハッシュ関数が適用された後に、ランダム化する構成要素が取り除かれることができるようにメッセージの一部だけをマスクすることが必要とされることがある。

上述の実施形態が本発明を限定するのではなく図示していること、および当業者が添付の特許請求の範囲を逸脱することなく多くの代替実施形態を設計することができることに留意されたい。特許請求の範囲では、括弧の間に置かれた任意の参照符号が請求項を限定すると解釈されてはならない。動詞の「含む（ｃｏｍｐｒｉｓｅ）」および「含む（ｉｎｃｌｕｄｅ）」およびその活用の使用が、請求項内で述べられた要素またはステップ以外の要素またはステップの存在を排除しない。要素に先行する冠詞「ａ」または「ａｎ」は複数のそのような要素の存在を排除しない。本発明は、いくつかの別個の要素を含むハードウェアを用いて、および適切にプログラムされたコンピュータを用いて実現されることができる。コンピュータプログラム製品が、適切な媒体、たとえば光記憶装置上に記憶される、および／または配布されることができるが、同様に、別の形態で配布される、たとえばインターネット、あるいは有線または無線の通信システムを介して配布されることができる。いくつかの手段を列挙するシステム／機器／装置の請求項では、これらの手段のいくつかが１つまたは同じ項目のハードウェアにより具体化されることができる。ある種の基準が相互に異なる従属クレームで列挙されているという単なる事実が、これらの手段の組合せが有利に使用されることができないことを示さない。

Claims (17)

1. 暗号鍵を再現できるように確立するための暗号システムであって、
   構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムと、
   構成に依存する初期ビットストリング（３１０）を確立するための初期ビットストリングプロデューサと、
   誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを初期ビットストリングに依存して確立するためのノーマライザであって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが誤り訂正符号に関連付けられるノーマライザと、
   誤り訂正アルゴリズムを使用して第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するための誤り訂正器と、
   所定の鍵導出アルゴリズムを適用することにより第１の符号語に依存する暗号鍵を確立するための鍵エスタブリッシャとを含み、
   暗号システムがランダム化する構成要素を生成するためのランダマイザをさらに含み、
   第１の訂正可能ビットストリングを確立することが、ランダム化する構成要素にさらに依存し、
   暗号鍵を確立することが、ランダム化する構成要素の影響を取り除くことにより、暗号鍵を再現できるようにするためのランダム化する構成要素にさらに依存する、暗号システム。
2. 符号語加算器および符号語減算器を含み、ランダム化する構成要素が誤り訂正符号のランダムな符号語を含み、ノーマライザが、少なくともランダムな符号語を少なくとも初期ビットストリングに加算するために符号語加算器に結合され、鍵エスタブリッシャが、ランダムな符号語を第１の符号語から減算するために符号語減算器に結合される、請求項１に記載の暗号システム。
3. 初期ビットストリングプロデューサにより確立される登録ビットストリングと誤り訂正符号の第２の符号語の間の差であるヘルパデータビットストリングを記憶するためのヘルパデータストアを含み、符号語加算器が、第１の訂正可能ビットストリングを確立するために、少なくともヘルパデータビットストリング、初期ビットストリング、およびランダムな符号語を加算するように構成される、請求項２に記載の暗号システム。
4. 符号語加算器が、中間のビットストリングを得るためにヘルパデータビットストリングとランダムな符号語をまず加算し、かつ初期ビットストリングを中間のビットストリングに加算するように構成される、または中間のビットストリングを得るためにランダムな符号語と初期ビットストリングをまず加算し、かつヘルパデータビットストリングを中間のビットストリングに加算するように構成される、請求項３に記載の暗号システム。
5. ランダム化する構成要素が置換クラスからのランダムな置換を含み、誤り訂正符号が置換クラスの下で不変であり、ノーマライザが、訂正可能な近傍内にある中間の訂正可能ビットストリングを初期ビットストリングに依存して確立するように構成され、ノーマライザが、第１の訂正可能ビットストリングを確立するためにランダムな置換に従って中間の訂正可能ビットストリングを置換するように構成され、鍵エスタブリッシャがランダムな置換の逆に従って第１の符号語を置換するように構成される、請求項１から４のいずれか一項に記載の暗号システム。
6. 置換クラスが巡回置換からなり、誤り訂正符号が巡回符号である、請求項５に記載の暗号システム。
7. 第１の訂正可能ビットストリングに依存する第１の符号語を確立するための誤り訂正器の実行時間が第１の訂正可能ビットストリングから実質的に独立している、請求項１から６のいずれか一項に記載の暗号システム。
8. 誤り訂正器が、
   第１の訂正可能ビットストリングを複数のサブストリングに分割し、複数のサブストリングの特定のサブストリングが、別の誤り訂正符号の別の訂正可能な近傍内にあり、
   別の誤り訂正符号内のすべての別の符号語の列挙から実質的に所定の時間の範囲内に、所定の距離関数に従って特定のサブストリングに最も近い特定の別の符号語を選択し
   第１の符号語を確立することが、特定の別の符号語にさらに依存するように構成される、請求項１から７のいずれか一項に記載の暗号システム。
9. 別の誤り訂正符号内の各符号語がデータ部分および冗長部分を含み、誤り訂正符号が、別の誤り訂正符号内の符号語のデータ部分の集まりが整数の順次リストを形成する順序付けを有し、システムが順序付けに従って符号語の冗長部分を記憶するための記憶装置を含む、請求項８に記載の暗号システム。
10. 鍵導出アルゴリズムがインデックスにさらに依存し、暗号システムが、インデックスを確立するためのインデックスエスタブリッシャを含む、請求項１から９のいずれか一項に記載の暗号システム。
11. 鍵導出アルゴリズムが、インデックスに依存するハッシュ関数のファミリからのハッシュ関数を選択するステップを含み、
    鍵エスタブリッシャが、前記選択されたハッシュ関数を第１の符号語に適用するように構成され、
    ランダム化する構成要素の影響を取り除くことが、ランダム化する構成要素に適用される選択されたハッシュ関数に依存する、請求項１０に記載の暗号システム。
12. 再現できる符号語を再現できるように確立するための暗号システムであって、
    構成要素の物理的な少なくとも部分的にランダムな構成を含む物理的システムと、
    構成に依存する初期ビットストリング（３１０）を確立するための処理ビットストリングプロデューサと、
    誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを初期ビットストリングに依存して確立するためのノーマライザであって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが誤り訂正符号に関連付けられるノーマライザと、
    誤り訂正アルゴリズムを使用して第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するための誤り訂正器とを含み、
    暗号システムが、ランダム化する構成要素を生成するためのランダマイザをさらに含み、
    第１の訂正可能ビットストリングを確立することが、ランダム化する構成要素にさらに依存し、
    暗号システムが、第１の符号語を、再現できる符号語に変換するためのトランスフォーマをさらに含み、変換することが、ランダム化する構成要素の影響を取り除くことにより再現できる符号語を再現できるようにするためのランダム化する構成要素に依存する、暗号システム。
13. 暗号鍵を再現できるように確立するための暗号方法であって、
    誤り訂正符号の訂正可能な近傍内にある第１の訂正可能ビットストリングを、物理的システムに備わる構成要素の物理的かつ少なくとも部分的にランダムな構成に応じた初期ビットストリングに依存して確立するステップであって、訂正可能な近傍の要素を符号語にマッピングするための所定の誤り訂正アルゴリズムが誤り訂正符号に関連付けられるステップと、
    誤り訂正アルゴリズムを使用して第１の訂正可能ビットストリングに依存する誤り訂正符号の第１の符号語を確立するステップと、
    所定の鍵導出アルゴリズムを適用することにより第１の符号語に依存する暗号鍵を確立するステップとを含み、
    方法が、ランダム化する構成要素を生成するステップをさらに含み、
    第１の訂正可能ビットストリングを確立するステップが、ランダム化する構成要素にさらに依存し、
    暗号鍵を確立するステップが、ランダム化する構成要素の影響を取り除くことにより暗号鍵を再現できるようにするためのランダム化する構成要素にさらに依存する、暗号方法。
14. 第１の訂正可能ビットストリングを複数のサブストリングに分割するステップであって、複数のサブストリングの特定のサブストリングが別の誤り訂正符号の別の訂正可能な近傍内にあるステップと、
    所定の距離関数に従って特定のサブストリングに最も近い特定の別の符号語を、別の誤り訂正符号内のすべての別の符号語の列挙から実質的に所定の時間の範囲内に選択するステップとを含み、
    第１の符号語を確立するステップが、特定の別の符号語にさらに依存する、請求項１３に記載の暗号方法。
15. インデックスを確立するステップを含み、暗号鍵を確立するステップがインデックスにさらに依存する、請求項１３および１４のいずれか一項に記載の暗号方法。
16. コンピュータ上で実行されるとき、請求項１３、１４、および１５のいずれか一項に記載の方法のステップをすべて実行するように適合されるコンピュータプログラムコード手段を含む、コンピュータプログラム。
17. コンピュータ読出可能媒体上で具体化される、請求項１６に記載のコンピュータプログラム。

Images