(57)【要約】【課題】実装コストの過度な上昇を抑えつつ、ＰＵＦ出力の誤り訂正を行う。【解決手段】本発明の実施形態による情報処理装置は、第１のＰＵＦ出力を取得するＰＵＦ出力取得部と、前記第１のＰＵＦ出力に基づく送信データを外部装置に送信し、前記外部装置に前記第１のＰＵＦ出力の誤り訂正を実行させる送信部と、前記外部装置から誤り訂正結果を受信する受信部と、前記誤り訂正結果に基づいて情報を生成する計算部を有する。【選択図】  図３
2018157411.tif 000002
【特許請求の範囲】
【請求項１】
第１のＰＵＦ出力を取得するＰＵＦ出力取得部と、
前記第１のＰＵＦ出力に基づく送信データを外部装置に送信し、前記外部装置に前記第１のＰＵＦ出力の誤り訂正を実行させる送信部と、
前記外部装置から誤り訂正結果を受信する受信部と、
前記誤り訂正結果に基づいて情報を生成する計算部を有する情報処理装置。
【請求項２】
第１の乱数を生成する乱数生成部と、
前記第１の乱数を誤り訂正符号化して符号を得る符号化部とを更に有し、
前記送信部は前記第１のＰＵＦ出力と前記符号から得られる前記送信データを前記外部装置に送信する請求項１に記載の情報処理装置。
【請求項３】
前記符号化部によって実行される誤り訂正符号は、線形符号である請求項２に記載の情報処理装置。
【請求項４】
前記送信データは、第２の乱数を誤り訂正符号化して得られるデータに第２のＰＵＦ出力を重畳した補助データに前記第１のＰＵＦ出力と前記符号とを重畳して得られる請求項２または３に記載の情報処理装置。
【請求項５】
前記計算部は、前記誤り訂正結果に前記第１の乱数を重畳した結果に基づいて前記情報を生成する請求項２乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
ＰＵＦ出力を生成するＰＵＦ回路と、
前記ＰＵＦ回路が生成したＰＵＦ出力を取得し、ＰＵＦ出力と乱数から訂正対象データを計算する訂正対象データ計算回路と、
前記訂正対象データを外部装置へ送信する送信回路と、
復号された訂正対象データを受信する受信回路と、
前記復号された訂正対象データと前記乱数からデータを計算する目的データ計算回路を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は情報処理装置に関する。
【背景技術】
【０００２】
デバイスの持つ物理的特性に中には、デバイスの製造時にその値を制御しきれず、デバイス毎に異なる値を持つ物理的特性が生じることが知られている。ＰＵＦ（physically unclonable function）は、この物理的特性のデバイス毎の差異を利用して、デバイス毎に異なる情報を生成する機能である。ＰＵＦに利用される物理的特性として望ましい性質は次のようなものである。ＰＵＦが出力する値がデバイス毎に異なるだけでなく、あるデバイスの出力と同じ出力をもつ別のデバイスを偽造することが困難であり、また同一デバイスのＰＵＦは何度出力しても同じ値を出力するという再現性という性質を有する。そこで、これらのＰＵＦの性質を利用して、デバイス固有のＩＤを生成し、デバイスの識別に用いることができる。また、デバイス内での暗号処理で用いられる鍵をそれが必要となるタイミングでＰＵＦ出力から導出し、鍵が必要でないときにはそれをデバイス内部のメモリから消去することにより、攻撃者がデバイス内のメモリを解析して不正に鍵を盗む脅威に対する対策を施した、より安全な鍵管理に用いられる。
【０００３】
ＰＵＦ出力には再現性があるとはいえ、物理的特性のわずかな差異を利用しているため、ノイズが発生する場合がある。ノイズは、熱雑音や温度によるデバイスの物理的特性の変化や経年劣化、ＰＵＦ以外の回路動作の干渉などによって起きる。デバイスの識別にＰＵＦを応用した場合、ノイズはデバイスの正しいＩＤを生成することを妨げるため、デバイスの識別が困難になる。鍵管理にＰＵＦを応用した場合、ノイズは鍵生成の際にそれまでとは異なる鍵を生成してしまい、正しい暗号処理の実行が困難になる。そこで、ノイズに対応するために、ＰＵＦ出力に対して誤り訂正を行うことが多い。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】S.K. Mathew, et al., A 0.19pJ/b PVT-Variation-Tolerant Hybrid Physically Unclonable Function Circuit for 100% Stable Secure Key Generation in 22nm CMOS, ISSCC 2014, 16.2, pp.278-280, 2014.
【非特許文献２】Y. Dodis, R. Ostrovsky, L. Reyzin, A Smith, “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data,”(A preliminary version of this paper appeared in Eurocrypt 2004.) SIAM J. Comput., 38(1), pp. 97-139, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一般に、ＰＵＦ出力は誤り率が高い。そのため、ＰＵＦを応用する装置は、高い訂正能力を持つ誤り訂正符号（Error Correcting Code（ＥＣＣ））を持つことが望ましい。しかし、一般に、ＥＣＣの訂正能力が高くなるにつれ、その実装コストが大きくなる。特にＢＣＨ符号やＲＳ符号などの符号では、連立方程式を解く復号部は単に畳み込み計算を行うだけの符号化部よりも実装コストがはるかに大きくなる。
【０００６】
そこで、本発明の実施形態にかかる情報処理装置では、実装コストの過度な上昇を抑えつつ、ＰＵＦ出力の誤り訂正を行うことを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明の実施形態による情報処理装置は、第１のＰＵＦ出力を取得するＰＵＦ出力取得部と、前記第１のＰＵＦ出力に基づく送信データを外部装置に送信し、前記外部装置に前記第１のＰＵＦ出力の誤り訂正を実行させる送信部と、前記外部装置から誤り訂正結果を受信する受信部と、前記誤り訂正結果に基づいて情報を生成する計算部を有する。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態に係る鍵生成装置と他の装置との接続を示す図。
【図２】本発明の実施形態に係る鍵生成装置の鍵初期化フェーズにおける機能ブロック図。
【図３】本発明の実施形態に係る鍵生成装置の鍵再生成フェーズにおける機能ブロック図。
【図４】本発明の実施形態に係るＩＤ生成装置の鍵初期化フェーズにおける機能ブロック図。
【図５】本発明の実施形態に係るＩＤ生成装置の鍵再生成フェーズにおける機能ブロック図。
【図６】本発明の実施形態に係る鍵生成装置のＨＷ構成図。
【図７】本発明の実施形態に係る計算装置のＨＷ構成図。
【図８】本発明の実施形態に係る計算装置のＨＷ構成図。
【図９】本発明の実施形態に係る計算装置のＨＷ構成図。
【図１０】本発明の実施形態に係る計算装置のＨＷ構成図。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態について図面を参照して説明する。本実施形態では、ＰＵＦ出力を用いて鍵を生成する鍵生成装置を例に説明する。本実施形態の鍵生成装置は、鍵初期化フェーズと鍵再生成フェーズの２つの動作フェーズを有する。
【００１０】
図１は、本実施形態の鍵生成装置と他の装置との接続を示す図である。鍵生成装置１は、電子回路２、不揮発性メモリ３、復号装置４と接続される。本実施形態の鍵生成装置に用いるＰＵＦは、例えばＳＲＡＭ−ＰＵＦにより実現される。ＳＲＡＭ−ＰＵＦは、複数のＳＲＡＭメモリセルから構成される。本実施形態の電子回路２は、複数のＳＲＡＭメモリセルである。ＳＲＡＭの各メモリセルは、電源投入後に１または０のいずれかの状態に落ち着く。その値を読み出してＰＵＦ出力とする。
【００１１】
鍵初期化フェーズで鍵生成装置１は電子回路２からＰＵＦ出力を取得し、鍵および補助データを生成し、補助データＨを不揮発性メモリ３に記憶する。鍵再生成フェーズで鍵生成装置１は電子回路２からＰＵＦ出力を取得し、不揮発性メモリ３から補助データを取得し、鍵を再生成する。補助データが漏洩してもセキュリティは破られない。補助データとＰＵＦ出力を用いて鍵を再生成することができるため、鍵を記憶しておく必要が無く、セキュリティを保つことができる。
【００１２】
また、鍵再生成フェーズで、鍵生成装置１は、鍵を再生成する際に必要な復号処理を復号装置４に実行させる。鍵生成装置１と復号装置４は、１つの装置として同一の筐体内に設けられていても良いし、有線または無線のネットワークで接続された２つの装置であっても良い。鍵生成装置１がＩｏＴのエッジデバイスであるならば、復号装置４はゲートウェイ装置でも良いし、クラウドサーバでも良い。例えば、復号装置４は、複数の鍵生成装置１に接続されて、複数の鍵生成装置１から復号処理の委託を受ける構成でも良い。
【００１３】
このように、本実施形態の鍵生成装置１は、復号処理を外部の装置である復号装置４に委託する。そのため、実装コストの大きい復号処理部を鍵生成装置１内に設ける必要が無い。
【００１４】
図２は、鍵初期化フェーズで機能する鍵生成装置１の機能ブロック図である。乱数生成部１２は乱数系列（Ｒ）を生成する。乱数生成部１２は、真正乱数回路が望ましいが、デバイス内に十分なエントロピーを持つエントロピースースが確保できるならば、そこから乱数シードを得て疑似乱数生成回路によって実現しても良い。
【００１５】
符号化部１４は乱数系列（Ｒ）を情報ビット列として誤り訂正符号の符号化を行い、符号語（ＥＮＣ（Ｒ））を生成する。ＰＵＦ出力取得部１６はＰＵＦ出力（Ｉ）を取得する。補助データ（Ｈ）は、符号語にＰＵＦ出力がビット毎の排他的論理和演算（ＸＯＲ）により重畳されて得られるデータであり、式（１）のように表される。
【数１】
2018157411.tif 000003
【００１６】
補助データ（Ｈ）は、不揮発性メモリ３に記憶される。補助データ（Ｈ）は、鍵再生成フェーズで使用される。また、ＰＵＦ出力（Ｉ）はハッシュ値計算部１８に入力される。ハッシュ値計算部１８は、ＰＵＦ出力（Ｉ）のハッシュ値を計算して得られる鍵（Ｋ）を出力する。なお、補助データ（Ｈ）は鍵生成装置１の外部に出力されてもセキュリティは破られない。一方、鍵（Ｋ）を鍵生成装置１の外部に出力し、鍵（Ｋ）が第三者に漏洩した場合にはセキュリティが破られる。
【００１７】
図３は、鍵再生成フェーズで機能する鍵生成装置１の機能ブロック図である。鍵再生成フェーズの符号化部１４ａ、１４ｂと、ＰＵＦ出力取得部１６と、ハッシュ値計算部１８は、それぞれ、鍵初期化フェーズの符号化部１４と、ＰＵＦ出力取得部１６と、ハッシュ値計算部１８と同一の回路を用いても良い。鍵再生成フェーズの乱数生成部１２は、鍵初期化フェーズの乱数生成部１２と同じ回路を用いても良いし、異なる回路を用いても良い。ただし、鍵初期化フェーズで生成された乱数列Ｒと鍵再生成フェーズで生成された乱数列Ｒ´との間に相関があってはならない。
【００１８】
鍵再生成フェーズの符号化部１４ａ、１４ｂと鍵初期化フェーズの符号化部１４は同じ誤り訂正符号を行う符号化部である。また、符号化部１４、１４ａ、１４ｂの誤り訂正符号は、例えば２元ＢＣＨ符号のような線形符号である。
【００１９】
本実施形態では、符号化部１４、１４ａ、１４ｂの誤り訂正符号として、訂正能力が高い２元ＢＣＨ符号を用いる。例えば、ＰＵＦ出力のビット誤り率が５％ならば、符号長１２７ビット、情報ビット長７１ビット、パリティビット長５６ビット、訂正能力９（９ビット誤りまで訂正できる）の原始ＢＣＨ符号を用いる。十分な誤り訂正能力を期待して、ビット誤り率（５％）に対して約１．４倍の訂正能力（９／１２７）を設定しているので、ＰＵＦ出力のノイズにより鍵生成に失敗する可能性はかなり小さくなる。
【００２０】
仮に鍵生成に失敗した場合には、その後、その鍵を用いて通信やデータの復号等の処理を正常に行うことが出来なくなるので、鍵生成に失敗したことが分かる。その場合には、鍵再生成フェーズを最初からやり直せば良い。符号長が１２７ビットあるので、デバイス毎に異なるＰＵＦ出力のエントロピーがビット数で平均して仮に０．２１と小さいケースを想定したとしても、標準的な共通鍵暗号であるＡＥＳ暗号の２５６ビット鍵を生成するには、ＰＵＦとして、１２７ビットの１０倍の１２７０ビットの出力ビット数を持つものを実装すればよい。１２７０×０．２１＝２６６．７＞２５６である。ＳＲＡＭ−ＰＵＦならばＰＵＦ用に１２７０ビットのメモリセルを確保すればよい。
【００２１】
鍵再生成フェーズでは、まず不揮発性メモリ３に記憶した補助データ（Ｈ）を読み出す。そして、補助データ（Ｈ）にＰＵＦ出力取得部１６が取得したＰＵＦ出力（Ｉ´）が重畳される。ＰＵＦ出力にはノイズが発生することがある。そのため、鍵初期化フェーズでＰＵＦ出力取得部１６が取得するＰＵＦ出力（Ｉ）と鍵再生成フェーズでＰＵＦ出力取得部１６が取得するＰＵＦ出力（Ｉ´）とは異なり得る。
【００２２】
次に、乱数生成部１２が乱数系列（Ｒ´）を生成し、符号化部１４ａがそれを誤り訂正符号の符号化をして符号語（ＥＮＣ（Ｒ´））を得る。そして、符号語（ＥＮＣ（Ｒ´））を、補助データとＰＵＦ出力の重畳データにさらに重畳する。この重畳結果は、式（２）のように表すことができる。
【数２】
2018157411.tif 000004
【００２３】
本実施形態の鍵再生成フェーズにおいて、乱数生成部１２は７１０ビットの乱数列Ｒ´を生成する。そして、この乱数列Ｒ´を１０個の７１ビットの乱数列に分割し、符号化部１４ａが７１ビットの各乱数列をＢＣＨ符号で符号化し、１０個の１２７ビット符号語を生成する。こうして得られた１２７０ビットの符号語（ＥＮＣ（Ｒ´））を、補助データとＰＵＦ出力の重畳データにさらに重畳する。
【００２４】
そして、送信部２２は重畳結果を外部の復号装置４の復号部４１に送信し、復号を委託する。復号部４１は、誤り訂正符号の復号を行う。この復号では、鍵初期化フェーズのＰＵＦ出力（Ｉ）と鍵再生成フェーズのＰＵＦ出力（Ｉ´）の間の差異が符号語に印可されたノイズと見なせる。誤り訂正符号が線形符号であるとすると、鍵初期化フェーズのＰＵＦ出力（Ｉ）と鍵再生成フェーズのＰＵＦ出力（Ｉ´）の差分の重みが誤り訂正符号の訂正能力の範囲内であれば、復号部４１は誤り訂正に成功する。線形符号では、誤り訂正が成功した場合には、式（３）に示す性質が成り立つ。
【数３】
2018157411.tif 000005
【００２５】
本実施形態の復号部４１は、鍵生成装置１から受け取った１２７０ビットのデータを１０個の１２７ビットのデータに分割し、それぞれに対してＢＣＨ符号の復号を行う。そして、得られた１０個の７１ビットの復号結果、すなわち７１０ビットの誤り訂正されたデータを鍵生成装置１に返す。
【００２６】
鍵生成装置１の受信部２４は復号装置４の復号部４１から復号結果を受信する。そして、鍵生成装置１は、復号装置４から得た復号結果と、乱数生成部１２から得た乱数（Ｒ´）とを重畳して、乱数（Ｒ）を得る。そして、符号化部１４ｂが乱数（Ｒ）に対して誤り訂正符号の符号化を行い、符号語（ＥＮＣ（Ｒ））を得る。つまり、復号部４１が誤り訂正に成功している場合、符号化部１４ｂから出力される符号語（ＥＮＣ（Ｒ））は、鍵初期化フェーズにおいて符号化部１４が出力した符号語（ＥＮＣ（Ｒ））と一致する。
【００２７】
本実施形態の鍵生成装置１によると、７１０ビットの復号結果に対して、乱数生成部１２から得られた乱数列を重畳し、重畳した結果の７１０ビットのデータを１０個の７１ビットのデータに分割する。そして、符号化部１４ｂが１０個の７１ビットのデータそれぞれに対して、ＢＣＨ符号の符号化を行う。
【００２８】
この符号語ＥＮＣ（Ｒ）を補助データ（Ｈ）と重畳する。式（１）から明らかなように、符号語ＥＮＣ（Ｒ）を補助データ（Ｈ）と重畳することによって、鍵初期化フェーズで用いたＰＵＦ出力（Ｉ）を得ることができる。そして、鍵初期化フェーズと同様にハッシュ値計算部１８が、ＰＵＦ出力（Ｉ）のハッシュ値を計算することで、鍵（Ｋ）を得ることができる。
【００２９】
このように、復号部４１を鍵生成装置１とは異なる外部の装置に設けることで、復号部を鍵生成装置１内に設ける必要が無い。そのため、実装コストや計算量や消費電力を小さくすることができる。また、鍵生成装置１と復号装置４との間のメッセージは、乱数Ｒ´や符号化された乱数Ｒ´でマスクされており、情報理論的に安全に復号を外部に委託することができる。
【００３０】
ローエンドのデバイスでは、鍵を保存する耐タンパーな不揮発性メモリを実装することは、実装コストの大きさのために敬遠されることが多い。例えば、ＩｏＴのエッジデバイスはセンサ−や単純なコントローラであって、大量に安く生産されることが多い。そのようなローエンドのデバイスでもＰＵＦを用いると、安全に鍵管理を行うことができる。さらに、本実施形態の鍵生成装置１によれば、鍵生成装置１内に復号部４１を設ける実装コストを省くことができるため、様々な製品やサービスにＰＵＦを適用することができる。
【００３１】
なお、本実施形態では、ＰＵＦ出力を用いて鍵を生成する装置を例にして説明したが、鍵の生成に限らない。例えば、ＰＵＦ出力を用いてＩＤを生成する場合に本実施形態で説明した処理を用いても良い。図４にＰＵＦ出力を用いてＩＤを生成するＩＤ生成装置１００のＩＤ初期化フェーズの機能ブロック図を示す。また、図５にＩＤ生成装置１００のＩＤ再生成フェーズの機能ブロック図を示す。ＩＤ生成装置１００の機能ブロック図の詳細については、鍵生成装置１の機能ブロック図と同様であるため、説明を省略する。
【００３２】
本実施形態に係る、乱数生成部１２、符号化部１４・１４ａ・１４ｂ、ＰＵＦ出力取得部１６、ハッシュ値計算部１８、復号部４１は、例えば、それぞれ専用の処理回路として実現される。また、符号化部１４・１４ａ・１４ｂ、復号部４１、ハッシュ値計算部１８は、プロセッサで動作するソフトウェアとして実現しても良い。
【００３３】
図６に、鍵生成装置１の各部をＨＷで構成した場合の例を示す。初期化フェーズでは、乱数生成回路５０２が乱数Ｒを生成する。誤り訂正符号符号化回路５０３は乱数Ｒを符号化し、符号語（ＥＮＣ（Ｒ））を生成する。符号語（ＥＮＣ（Ｒ））は、符号化された乱数Ｒ｜｜ＲＰである。ここで、ＲＰは乱数Ｒに対して誤り訂正符号の符号化を行い計算されたパリティである。記号｜｜はビット列の連接を表す。ＢＣＨ符号のような組織符号では、符号語（ＥＮＣ（Ｒ））は、このように情報部分（Ｒ）とパリティ部分（ＲＰ）とを連接した形にすることができる。ＰＵＦ回路５０１はＰＵＦ出力値（Ｉ）を出力する。出力されたＰＵＦ出力値（Ｉ）は、ビット列重畳回路５０４により、誤り訂正符号符号化回路５０３から出力された符号語（ＥＮＣ（Ｒ））＝Ｒ｜｜ＲＰと重畳される。その計算結果が補助データ（Ｈ）である。
【００３４】
補助データ（Ｈ）は、式（１）のように計算される。補助データは、補助データ記憶回路５０５に記憶される。
【００３５】
次に、鍵を計算する鍵再生成フェーズの動作を説明する。ＰＵＦ回路５０１は改めてＰＵＦ出力値（Ｉ´）を出力する。初期化フェーズにおける出力（Ｉ）に対して、ノイズＥが重畳されている可能性がある。そのため、鍵再生成フェーズのＰＵＦ出力値（Ｉ´）は、式（４）のように表される。
【数４】
2018157411.tif 000006
【００３６】
乱数２生成回路５０７は、Ｒとは別の乱数Ｒ´を生成する。生成された乱数Ｒ´は、誤り訂正符号符号化回路５０８と乱数２記憶回路５１０に送られる。誤り訂正符号符号化回路５０８は受け取った乱数Ｒ´を符号化して符号語（ＥＮＣ（Ｒ´））＝Ｒ´｜｜Ｒ´Ｐを計算する。ここで、Ｒ´ＰはＲ´に対するパリティである。また、乱数２記憶回路は乱数Ｒ´を記憶する。ここで、乱数２生成回路５０７は、乱数生成回路５０２と同じ回路を用いても良い。ビット列重畳回路５０６は、補助データ記憶回路から補助データ（Ｈ）を読出し、ＰＵＦ回路５０１の出力（Ｉ´）と誤り訂正符号符号化回路５０８から出力された符号語（ＥＮＣ（Ｒ´））＝Ｒ´｜｜Ｒ´Ｐとビット毎に重畳する。重畳結果は、式（２）のように表される。この重畳結果は、ビット列送信回路５０９に渡され、ビット列送信回路５０９は鍵生成装置１の外（復号装置４）へ送信する。ビット列送信回路５０９から送信された送信ビット列は、別の装置のビット列受信回路５１１により受信され、その装置の誤り訂正符号復号装置５１２により復号される。ノイズＥが訂正能力の範囲内ならば、ノイズＥは取り除かれる。復号装置４のビット列送信回路５１３は誤りが取り除かれた結果である
【数５】
2018157411.tif 000007
からパリティ部分を取り除き、
【数６】
2018157411.tif 000008
をビット列送信回路５１３から鍵生成装置１に送信する。ビット列受信回路５１４は復号装置４から式（６）のビット列を受信し、ビット列重畳回路５１５へ渡す。ビット列重畳回路５１５は乱数２記憶回路から乱数Ｒ´を読出し、ビット列受信回路５１４から受け取ったビット列にビット毎に重畳する。その結果、乱数（Ｒ）を得ることができる。鍵計算回路５１６は、ビット列重畳回路５１５が計算した結果である乱数（Ｒ）から鍵を生成する。乱数（Ｒ）が十分にデバイス毎にランダムな性質を持つならばそのまま鍵としてもよいが、もし統計的に偏りがあるならば、ハッシュ値を計算してその結果を鍵としても良い。
【００３７】
なお、本実施形態では、鍵生成装置１が鍵初期化フェーズと鍵再生成フェーズの両方を実行するとして説明したが、鍵初期化フェーズと鍵再生成フェーズを実行する装置が異なる装置であっても良い。
【００３８】
（変形例）
上述の説明では、ＰＵＦ出力を用いて鍵やＩＤを生成する装置を例にして説明した。しかし、これに限らず、ＰＵＦの出力に依存した任意のデータを計算する装置であってよい。
【００３９】
図７は、ＰＵＦ出力に依存した任意のデータを計算する計算装置１０００のＨＷ構成を示す図である。ＰＵＦ回路１００１は、ＰＵＦ出力を出力する。このＰＵＦ出力には、ノイズが重畳していることもあり得る。このノイズが存在するＰＵＦ出力をそのまま用いて目的データの計算を行うと、正しい目的データの計算を行うことができない。そこで、訂正対象データ計算回路１００２は、ノイズが重畳している恐れのあるＰＵＦ出力が入力されると、訂正対象データを計算し、それを外部装置へ出力する。この訂正対象データ計算の際には、乱数を使用する。目的データが秘匿すべき鍵やＩＤなどのデータの場合、ＰＵＦ出力の値を攻撃者に推定されることを防ぐ必要がある。そこで、訂正対象データからＰＵＦ出力値を推定できないように乱数を用いる。ビット列送信回路１００３は、計算された訂正対象データを計算装置１０００の外へ送信する。送信された訂正対象データは、計算装置１０００外にある外部装置により訂正処理をされた後、計算装置１０００に送信して返される。ビット列受信回路１００４は、外部装置により訂正された訂正対象データを受信し、目的データ計算回路１００５に入力する。また、目的データ計算回路１００５は、ビット列受信回路１００４から受け取った訂正された訂正対象データのほかに、訂正対象データ計算回路１００２から、訂正対象データ計算時に用いられた乱数を受け取る。目的データ計算回路１００５は、この乱数と訂正された訂正対象データから、目的データを計算する。
訂正対象データ計算回路１００２と目的データ計算回路１００５の構成についてより詳細に説明する。訂正対象データ計算回路１００２は、まず、ＰＵＦ回路１００１が出力したＰＵＦ出力
【数７】
2018157411.tif 000009
に対して、パリティＰ＝（ｐ１、ｐ２、・・・、ｐ（ｎ−ｋ））を連接する。この連接されたデータを
【数８】
2018157411.tif 000010
とする。ここで、Ｉ＝（ｉ１、ｉ２、・・・、ｉｋ）はノイズが無い場合のＰＵＦ出力値、Ｅ＝（ｅ１、ｅ２、・・・、ｅｋ）はノイズを表すビット列とする。ＰＵＦの出力の長さはｋビットであり、連接されたデータの全体の長さはｎビットであり、パリティの長さは（ｎ−ｋ）ビットであるとする。記号｜｜はビット列の連接を表し、ＸＯＲの記号はビット列に対してはビット毎のＸＯＲによる重畳、ビットに対してはＸＯＲを表すとする。また、パリティＰは、ノイズが無い場合のＰＵＦ出力値に対して、誤り訂正符号の符号化を行い生成されるパリティであり、回路内にハードワイヤー化されていてもよいし、図７のように、派生データ記憶回路１００６に記録されていてもよい。訂正対象データ計算回路１００２は、次に、乱数Ｒ＝（ｒ１、ｒ２、・・・、ｒｋ）を生成し、乱数Ｒに対して誤り訂正符号の符号化を行い、パリティＲＰ＝（ｒｐ１、・・・、ｒｐ（ｎ−ｋ））を生成する。乱数Ｒと乱数ＲのパリティＲＰを連接し、その結果Ｒ｜｜ＲＰを式（８）の連接データにビット毎に重畳する。こうして得られるデータ
【数９】
2018157411.tif 000011
が訂正対象データである。
【００４０】
この訂正対象データはビット列送信回路により装置の外へ送信ビット列として送信される。外部装置は、ビット列受信回路１００７と誤り訂正符号復号回路１００８とビット列装置送信回路１００９とを有する。外部装置は、図６を用いて説明したビット列受信回路５１１、誤り訂正符号回路５１２、ビット列送信回路５１３と同様の構成であるため説明を省略する。送信ビット列は、外部装置にある誤り訂正符号復号回路により訂正される。ＰＵＦ出力値に伴っていたノイズＥが誤り訂正符号の訂正能力の範囲内ならば、このノイズＥは復号により取り除くことができる。その場合、訂正後のデータは、
【数１０】
2018157411.tif 000012
となる。このうちパリティ部分を取り除いたデータ
【数１１】
2018157411.tif 000013
が受信ビット列として返されてくる。ビット受信回路１００４が受信して、目的データ計算回路１００５へ渡す訂正された訂正対象データは、式（１１）に表された受信ビット列である。
【００４１】
目的データ計算回路は、ビット列受信回路１００４から受け取った訂正された訂正対象データと訂正対象データ計算回路１００２から受け取った乱数Ｒをビット毎に重畳して目的データを計算する。目的データは、
【数１２】
2018157411.tif 000014
となり、ノイズが無い場合のＰＵＦ出力と一致する。ＰＵＦ出力はデバイス毎に異なるランダム性を持つことが期待されるが、もしそのランダム性が十分なエントロピーを持たない場合には、計算装置１０００は、さらにハッシュ値計算回路を持ち、目的データ計算回路１００５により計算されたＰＵＦ出力Ｉに対するハッシュ値を計算して、計算されたハッシュ値を目的データとしてもよい。
【００４２】
なお、図７では、訂正対象データ計算回路１００２が乱数Ｒを生成し、生成した乱数Ｒを目的データ計算回路１００５へ渡す構成としたが、図８のように、独立の乱数生成回路１０１０が乱数Ｒを生成し、生成した乱数Ｒを訂正対象データ計算回路１００２ａと目的データ計算回路１００５の両方へ渡す構成でもよい。
【００４３】
また、図７では、ＰＵＦ出力ＩのパリティＰは、ハードワイアードあるいは派生データ記憶回路１００６に保存していた。ＰＵＦ出力値Ｉは、デバイス毎に異なるので、デバイス毎に異なる回路を実装したり、デバイス毎に異なるデータを記憶させたりすることはコストがかかる。そこで、図９に示す計算装置１０００では、派生データ計算回路１０１１を追加して、派生データ計算回路１０１１がパリティを計算し、それを派生データ記憶回路１０１１に記憶している。この実施形態では、デバイス毎に異なる回路の実装を行う必要はない。派生データ記憶回路１０１１に記憶されるパリティの値はデバイス毎に異なるが、その計算は全てのデバイスで同一の回路で実現される。
【００４４】
図１０は、計算装置１０００の派生データ計算をより詳細に説明する図である。まず、初期化フェーズの動作を説明する。ＰＵＦ回路６０１は、ＰＵＦ出力値Ｉを出力する。誤り訂正符号符号化回路６０２はＰＵＦ出力値を符号化し符号化されたＰＵＦ出力Ｉ｜｜Ｐを出力する。ここで、Ｐは符号化回路で計算されたパリティである。パリティ切り出し回路６０３は、符号化されたＰＵＦ出力Ｉ｜｜ＰからパリティＰを切り出し、パリティ記憶回路６０４は、そのパリティＰを記憶する。次に、目的データの例としてＰＵＦ出力を計算する目的データ計算フェーズの動作を説明する。ＰＵＦ回路６０１は、ノイズが重畳されている可能性のあるＰＵＦ出力を出力する。ノイズが重畳されている可能性のあるＰＵＦ出力は、式（７）によって表される。パリティ連接回路６０５は、パリティ記憶回路６０４に記憶されているパリティＰを読出し、ＰＵＦ出力と連接する。パリティ連接回路６０５が連接したデータは式（８）によって表される。
【００４５】
乱数生成回路６０７は、乱数Ｒを生成する。生成された乱数Ｒは誤り訂正符号符号化回路６０８と乱数記憶回路６１０へ送られる。ここで、誤り訂正符号符号化回路６０８は誤り訂正符号符号化回路６０２と同じ回路を用いた構成であっても良い。誤り訂正符号符号化回路６０８は乱数Ｒを符号化してＲ｜｜ＲＰを計算する。ここでＲＰは乱数Ｒに対するパリティである。ビット列重畳回路６０９は、パリティ連接回路６０５が計算した式（８）のデータと誤り訂正符号符号化回路６０８が計算したＲ｜｜ＲＰをビット毎に重畳して式（９）に示された訂正対象データを計算する。ビット列送信回路６１１は、この計算された訂正対象データを送信ビット列として送信する。送信されたビット列は、計算装置１０００の外にある外部装置のビット列受信回路６１２により受信され、別の装置の誤り訂正符号復号回路６１３により誤り訂正符号の復号が行われる。ＰＵＦ出力に重畳していた誤りが訂正能力の範囲内であれば、この誤りは取り除かれる。別の装置のビット列送信回路６１４から誤りが取り除かれた受信ビット列が返される。受信ビット列は、式（１１）で表される。ビット列受信回路６１５は受信ビット列をビット列重畳回路６１６へ渡す。ビット列重畳回路６１６は、ビット列受信回路６１５から受け取った受信ビット列と乱数記憶回路６１０から受け取った乱数Ｒをビット毎に重畳してＰＵＦ出力Ｉを計算する。ビット列重畳回路６１６はビット列重畳回路６０９と同じ回路を用いてもよい。
【００４６】
本発明の実施形態を説明したが、この実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００４７】
１…鍵生成装置、２…電子回路、３…不揮発性メモリ、４…復号装置、１２…乱数生成部、１４・１４ａ・１４ｂ…符号化部、１６…ＰＵＦ出力取得部、１８…ハッシュ値計算部、４１…復号部、１００…ＩＤ生成装置、１０００…計算装置
【図１】
2018157411.tif 000015
【図２】
2018157411.tif 000016
【図３】
2018157411.tif 000017
【図４】
2018157411.tif 000018
【図５】
2018157411.tif 000019
【図６】
2018157411.tif 000020
【図７】
2018157411.tif 000021
【図８】
2018157411.tif 000022
【図９】
2018157411.tif 000023
【図１０】
2018157411.tif 000024