認証コンポーネント、被認証コンポーネントおよびその認証方法
【課題】認証コンポーネント、被認証コンポーネント間で、異なる秘密情報XYの秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証可能な認証・被認証コンポーネントおよびその認証方法を提供する。
【解決手段】実施形態によれば、被認証コンポーネントは、秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶するメモリ１１と、乱数Aを生成する生成部１６と、生成した前記乱数Aと、受領する乱数Bの少なくとも一部から構成される乱数Dを生成する生成部１８と、前記乱数Dと前記メモリからロードした前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成する演算部１３と、データν（νは１の出現確率がη（ただし、η<0.5））を生成する生成部１４と、前記データCに前記データνを付与して、演算結果Zを算出するビット毎加算部Ｃ１とを具備する。
【解決手段】実施形態によれば、被認証コンポーネントは、秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶するメモリ１１と、乱数Aを生成する生成部１６と、生成した前記乱数Aと、受領する乱数Bの少なくとも一部から構成される乱数Dを生成する生成部１８と、前記乱数Dと前記メモリからロードした前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成する演算部１３と、データν（νは１の出現確率がη（ただし、η<0.5））を生成する生成部１４と、前記データCに前記データνを付与して、演算結果Zを算出するビット毎加算部Ｃ１とを具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
認証コンポーネント、被認証コンポーネントおよびその認証方法に関するものである。
【背景技術】
【０００２】
一般に、セキュリティーを要する分野において、自己の正当性を証明する手段として暗号器と共有した秘密に基づく手法が採られている。
【０００３】
例えば、電子決済に用いるＩＣカード等では、カード内のＩＣに対して個別化されたＩＤ及び秘密情報が保持されており、更にＩＣカードは、ＩＤ及び秘密情報に基づく認証を行うための暗号処理機能を有している。別の例では、コンテンツの著作権保護において、ＳＤカード（登録商標）の正当性を証明する手段などもある。
【０００４】
上記の例は、いずれも被認証コンポーネントが、秘密鍵と暗号器とを保有していることが必要である。しかしながら、暗号器の実装は比較的大きな回路規模を要求されるため、回路規模上の制約が同時に課せられる環境においては自己の正当性を証明するのは非常に困難である。回路規模上の制約が課せられる代表例としては、例えば、RFID(Radio Frequency Identification)等があげられる。そのため、近年では、益々実装上の必要性が高まっているという背景がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国公開特許公報２０１０／０１６１９８８ Ａ１
【特許文献２】特開２０００−３５７２１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
秘密情報を認証コンポーネント、被認証コンポーネント以外の第三者に対する秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証可能とする。
【課題を解決するための手段】
【０００７】
実施形態によれば、一態様に係る秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶する被認証コンポーネントと、前記被認証コンポーネントを認証する認証コンポーネントとの間における認証方法は、前記認証コンポーネントが、前記被認証コンポーネントから受領した前記秘密情報XYEに対して、復号処理を行い、前記秘密情報XYを共有するステップと、前記被認証コンポーネントが、前記認証コンポーネントが生成する乱数Bを受領し、前記複製された秘密情報XYを複数ロードするステップと、前記被認証コンポーネントが、乱数Aおよびデータν（νは１の出現確率がη（ただし、η<0.5））を生成するステップと、前記被認証コンポーネントが、生成した前記乱数Aと受領した前記乱数Bの少なくとも一部から構成される乱数Dを生成するステップと、前記被認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、前記被認証コンポーネントが、前記データCに前記データνを付与した演算結果Zを、前記認証コンポーネントに送信するステップと、前記認証コンポーネントが、生成した前記乱数Bと受領した前記乱数Aの少なくとも一部から構成される乱数Dを生成するステップと、前記認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、前記認証コンポーネントが、受領した演算結果Zと生成したデータCとを用いて、判定処理を行うステップとを具備する。
【図面の簡単な説明】
【０００８】
【図１】比較例１に係るプロトコルを示すブロック図。
【図２】比較例２に係るプロトコルを示すブロック図。
【図３】第１実施形態に係る構成例を示すブロック図。
【図４】第１実施形態に係る認証フローを示すフロー図。
【図５】第２実施形態に係る構成例を示すブロック図。
【図６】第２実施形態に係る認証フローを示すフロー図。
【図７】第３実施形態に係る構成例を示すブロック図。
【図８】第３実施形態に係る認証フローを示すフロー図。
【図９】第３実施形態に係る秘密情報のデータ転送を示すブロック図。
【図１０】第４実施形態に係る構成例を示すブロック図。
【図１１】第４実施形態に係る認証フローを示すフロー図。
【図１２】第５実施形態に係る構成例を示すブロック図。
【図１３】第５実施形態に係る認証フローを示すフロー図。
【図１４】第６実施形態に係る構成例を示すブロック図。
【図１５】第６実施形態に係る認証フローを示すフロー図。
【図１６】第７実施形態に係る構成例を示すブロック図。
【図１７】第７実施形態に係る認証フローを示すフロー図。
【図１８】第８実施形態に係るID retrieval process(1)を示すブロック図。
【図１９】第８実施形態に係るID retrieval process(2)を示すブロック図。
【図２０】第８実施形態に係るID retrieval process(3)を示すブロック図。
【図２１】第８実施形態に係るID retrieval process(4)を示すブロック図。
【図２２】第９実施形態に係るID biding process(1)を示すブロック図。
【図２３】第９実施形態に係るID biding process(2)を示すブロック図。
【図２４】第１０実施形態に係る構成例を示すブロック図。
【図２５】第１１実施形態に係る構成例を示すブロック図。
【図２６】第１２実施形態に係る構成例を示すブロック図。
【発明を実施するための形態】
【０００９】
［比較例１（HB+プロトコルの一例）］
まず、図１を用い、比較例１について説明する。この比較例１は、HB+プロトコルの一例に関するものである。
【００１０】
HB+プロトコルは、２０００年にHopper とBlumらによって提案された、軽量の認証プロトコルであるHBプロトコルの改良プロトコルである。HBプロトコルは、雑音下におけるパリティ値の同定が困難であるということ（LPN：Learning Parity with Noise）に基づいており、受動攻撃に対する安全性が証明されている。ただし、HBプロトコルは、リーダー（Reader）へのなりすましといった能動攻撃に対して脆弱性がある。この点を解決するために、２００５年にJuelsらにより、HB+プロトコルとして提案されたものである。
【００１１】
HB+プロトコルの概要は、図１のように図示される。ここで、図１中の、a，b，x，yはベクトルであり、ν，zはビットである。
【００１２】
図示するように、HB+プロトコルでは、被認証コンポーネントであるタグ（Tag）と、認証コンポーネントであるリーダー（Reader）とが、各々秘密情報ベクトルx, yを共有する。
【００１３】
タグは、リーダーに対して一時乱数ベクトルbを渡す。
【００１４】
続いて、リーダーは、タグに対して一時乱数ベクトルaを渡す。
【００１５】
続いて、タグは、乱数aと秘密情報ベクトルxの内積（a・x）および乱数bと秘密情報ベクトルyとの内積（b・y）を計算する。さらに、タグは、ηの確率で１となる変数νを生成する。そして、内積（a・x）、内積（b・y）、変数νをそれぞれ加算して、z= ax(+)by(+)νを算出する。ここで、axは内積（a・x）を意味し、(+)は排他的論理和を意味する。
【００１６】
続いて、タグは、算出したzを、リーダーへと送信する。
【００１７】
続いて、リーダーは、受領したzと、自身で計算したax(+)byとを比較し、一致不一致を検査する。上記一連の処理を１単位として１ラウンドと称することもある。
【００１８】
これら上記1ラウンドの処理を複数回（例えば、数十回〜数万回程度）繰り返し、前述の不一致確率が、所定値tを下回った場合、タグが秘密情報を保持しているとみなし、認証が成功する。
【００１９】
尚、ax(+)byは、秘密情報x，yと、結合ベクトルa，bとのそれぞれの内積である。そのため、x，yの結合ベクトルxyを秘密情報とおき、a，bの結合ベクトルをConcat(a,b)とした場合、ax(+)byをConcat(a,b)xyと表現することも可能である。
【００２０】
［比較例２（Random HB#プロトコルの一例）］
次に、図２を用い、比較例２について説明する。この比較例２は、Random HB#プロトコルの一例に関するものである。Random HB#プロトコルは、上記比較例１に示したHB+プロトコルが更に改良されたプロトコルである。
【００２１】
上記HB+プロトコルは、受動的な攻撃と能動的な攻撃に対して解決策を提供したものの、Gilbertらによって提案された中間者攻撃に対して脆弱性がある傾向にある。この点を解決するために、GilbertらによりHB+プロトコルの改良方式プロトコルとして、Random HB＃プロトコルとして提案されたものである。
【００２２】
Random HB#プロトコルの概要は、図２のように図示される。ここで、図２中のX，Yは行列であり、a，b，z，νはベクトルである。
図示するように、Random HB#プロトコルでは、タグ（Tag）とリーダー（Reader）とが、各々秘密情報行列X, Yを共有する。
【００２３】
まず、タグは、リーダーに対して一時乱数ベクトルbを渡す。
【００２４】
続いて、リーダーは、タグに対して一時乱数ベクトルaを渡す。
【００２５】
続いて、タグは、乱数aと秘密情報行列xとの内積（aX）および乱数bと秘密情報行列yとの内積（bY）を計算する。ここで、X, Yは行列、a, bはベクトルであることから、各々の内積結果は、ベクトルとなる。また、タグは、ηの確率で１となる変数ベクトルνを生成する。そして、タグは、上記の値を加算して、z= aX(+)bY(+)νを算出する。ここでzはベクトルである。
【００２６】
続いて、タグは、算出したzを、リーダーへと送信する。
【００２７】
続いて、リーダーは、受領したzと自身で計算したaX(+)bYとのビット加算、すなわち排他的論理和演算を行った結果を用い、aX(+)bY(+)zのハミング重みHwt(aX(+)bY(+)z)を計算する。ハミング重みHwt(aX(+)bY(+)z)が、所定値t*clenを下回った場合、タグが秘密情報を保持しているとみなし、認証が成功する。ただし、η≦t<0.5、clenはAX(+)BYのビット長とする。
【００２８】
尚、aX(+)bYは秘密情報XとYの結合行列とaとbの結合ベクトルの内積であることから、X,Yの結合行列XYを秘密情報とおき、aとbの結合ベクトルをConcat(a,b)とした場合、aX(+)bYをConcat(a,b)XYと表現することも可能である。
【００２９】
＜実装上の改善点＞
しかしながら、上記比較例１、２に係るプロトコルでは、例えば、ＮＡＮＤ型フラッシュメモリ等に具体的に実装しようとした場合等に、以下（Ｉ）〜（ＩＶ）のような改善点が考えられる。
【００３０】
（Ｉ）秘密情報X及びYの共有手段
前述のように、上記比較例１、２では、リーダーとタグとは、秘密情報X, Yを共有している必要がある。しかしながら、上記比較例１、２では、秘密情報X, Yを共有するための具体的な共有方法が提示されていない。
【００３１】
そのため、仮にすべてのリーダーとタグとで同一のX, Yを事前に共有していた場合、一旦X, Yが露見してしまうと、システム全てに致命的な影響を与える。一方でタグ毎に異なるX, Yを適用した場合、リーダー側では全てのタグに適用されているX, Yを保持している、もしくはそれを統合的に管理しているデータベースへのアクセスなどが要求される。
その結果、リーダー側への負担が大きくなる。
【００３２】
尚、これに関連する先行技術として、特開２０００−３５７２１３号公報において、演算処理機能を有する記録媒体に複製コンテンツを記録する記録装置と該記録媒体との間の相互認証方法において、前記記録媒体は、少なくとも該記録媒体に依存する第１の情報と、前記記録装置と相互認証を行う際に該記録装置と共有すべき該記録媒体に依存する第２の情報とを記憶し、前記記録装置は、前記記録媒体から得られた前記第１の情報に基づき該記録媒体との間の相互認証を行う際に用いる認証情報を生成し、この生成された認証情報と前記第２の情報とを用いて前記記録装置と前記記録媒体との間で相互認証を行うことを特徴とする方法が提案されている。
【００３３】
（ＩＩ）コンポーネントPに対し、秘密情報X及びYを効率的に記録する手段
上記HB+プロトコル、Random HB#プロトコルにおいては、いわゆる上記LPN問題を現実的な計算量で同定を困難とするためには相応の秘密情報量、すなわちX, Yは相応のデータサイズである必要がある。ここで、X, Yが全てのタグで共通であれば、ハードワイヤードロジックで構成することも可能であるが、X,Yをタグ毎に異ならせる場合、タグはX, Yを保持するために十分なメモリ容量を持つ必要がある。また、これと同時にタグ製造において同データを個別に記録する必要性があり、記録時間はすなわち製造時間へと反映される。
その結果、メモリ容量の増加と記録時間の増加により、タグのコスト増大を招く。
【００３４】
（ＩＩＩ）コンポーネントPが保持する秘密情報X及びY損傷に対する保護手段
コンポーネントPが内部メモリにてX, Yを保持している場合、認証に用いる場合は同X, Yのデータ完全性が要求されるが、先行文献ではこれらについて言及されていない。データ完全性を保証するには、タグ内部のメモリにはエラー訂正符号を付与したX, Yを保有し、認証時に訂正処理を行うなどの方法が考えられる。しかしながら、一般に廉価メモリは必ずしも訂正機能を有しているわけではなく、メモリ側に訂正機能がない場合はメモリ以外のタグ内コンポーネントとして同訂正機能を有す必要がある。
その結果、タグのコスト増大を招く。
【００３５】
（ＩＶ）秘密情報X及びY露見時の秘密情報更新手段
上記Random HB#コンポーネントは、各々受動攻撃、能動攻撃、一定条件下での中間者攻撃に対する耐性が認められているものの、近年では一般化された中間者攻撃に対する脆弱性が報告されるなど、X, Yが露見する可能性を排除することはできない。X, Yの露見には、それ相応の攻撃コストが要求されるものの、一旦X,Yが露見した場合、同X,Yを用いた偽造タグなどの製造が可能となるため、仮にX, Yが露見した場合でも新たなX, Yへと移行できるように、秘密情報の更新手段がある方が望ましい。
【００３６】
そこで、上記の点を考慮し、以下において、実施形態について図面を参照して説明する。なお、これまでRFIDのリーダーとタグとを一例にとって説明をした。しかしながら、同様の要件はＮＡＮＤ型フラッシュメモリなどの回路面積が即座にコストに直結するメモリチップにおいても同様である。そのため、以下実施形態では、認証コンポーネントとしてのリーダー（Reader）としてＮＡＮＤ型フラッシュメモリを認証するホストデバイス（Host）、被認証コンポーネントとしてのタグ（Tag）としてＮＡＮＤ型フラッシュメモリ（NAND chip）を、一例に挙げて説明する。しかし、これに限られることはない。例えば、ＮＯＲ型フラッシュメモリ、抵抗変化式メモリ（ReRAM: Resistive Random Access Memory）、磁気抵抗メモリ(MRAM: Magnetoresistive Random Access Memory）、相変化メモリ（PRAM: Phase change Random Access Memory）、および強誘電体メモリ（FeRAM: Ferroelectric Random Access Memory）、ハードディスクドライブやソリッドステートドライブなどの演算機能及びメモリを有するストレージデバイス、RFIDやICカードなどの認証を要するコンポーネント、汎用演算素子と汎用メモリを有した計算器とソフトウェアから構成されるシステムなど、多様な実装形態に適用できる。尚、この説明においては、全図にわたり共通の部分には共通の参照符号を付す。
【００３７】
［第１実施形態］
図１および図２を用い、第１実施形態に係る認証コンポーネント、被認証コンポーネントおよびその認証方法について説明する。
【００３８】
＜１．構成例（メモリシステム）＞
まず、図３を用い、第１実施形態に係る構成例について説明する。
図３に示すメモリシステムは、被認証コンポーネントであるＮＡＮＤフラッシュメモリ１０、認証コンポーネントであるホストデバイス２０、両者を仲介するコントローラ１９を備える。図示するように、ホスト２０は、コントローラ１９と呼ばれるＮＡＮＤ型フラッシュメモリ１０に対するアクセス機能を有したデバイスを経由してＮＡＮＤ型フラッシュメモリにアクセスする。
【００３９】
ここで、半導体製品の製造工程について記載する。半導体製品の製造工程は、主に基板ウエハー上に回路を形成する前工程と、前記ウエハーを個片に切り分けた後、配線や樹脂パッケージ封入などを行う後工程に分けられる。ここで、コントローラ１９は、前工程においてＮＡＮＤ型フラッシュメモリ１０内に包含されるよう構成される場合、前工程においては包含されないが後工程において同一パッケージに包含されるよう構成される場合、ＮＡＮＤ型フラッシュメモリ１０とは異なるチップの形態をとる場合、など様々な場合がある。図３を含め、以下ではコントローラ１９は、ＮＡＮＤ型フラッシュメモリ１０とは異なるチップの形態をとる場合を例にとっている。しかしながら、本実施形態は、上記いずれのケースにおいても適用可能である。以下、特に断りのない限り、ホストデバイス２０とＮＡＮＤ型フラッシュメモリ１０間のデータや命令のやり取りにおいては、多くの場合コントローラが仲介するものであるが、これは省略することとする。なお、ＮＡＮＤ型フラッシュメモリ１０およびコントローラ１９の構成例については、後述する。
【００４０】
図３に示す各コンポーネント、データ処理については、以下の通り説明する。図示するように、秘密情報X, Yを共有する方法と、同方法をＮＡＮＤ型フラッシュメモリ１０に適用する場合の構成が示される。
【００４１】
１−１．ＮＡＮＤ型フラッシュメモリ
ＮＡＮＤ型フラッシュメモリ１０は、被認証コンポーネントである。本例に係るＮＡＮＤ型フラッシュメモリ１０は、セルアレイ１１、およびセルアレイ１１の周辺領域に配置されるデータキャッシュ１２、圧縮演算回路１３、バイアスドＲＮＧ１４、出力部１５、乱数生成器１６、順序交換回路１８、ビット毎加算回路Ｃ１等を備える。
【００４２】
セルアレイ（Cell array）１１には、図示しないビット線およびワード線の交差位置にマトリックス状に複数のメモリセルが配置される。メモリセルは、半導体基板上に順次、トンネル絶縁膜、浮遊ゲート、層間絶縁膜、およびワード線と接続される制御ゲートをそれぞれ備える。ビット線方向のメモリセルの電流経路は直列接続され、セルユニットを形成する。セルユニットは、ビット線、ソース線に接続される選択トランジスタにより選択される。ワード線方向の複数のメモリセルは、データ読み出しおよびデータ書き込みの単位である１ページ（Page）を形成する。また、複数のページはデータ消去の単位であるブロック（Block）を形成する。
【００４３】
セルアレイ（Cell array）１１は、ロム領域１１−１、秘匿領域１１−２、一般領域１１−３を備える。
ロム領域（Rom area）１１−１は、データ記録が禁止され、データ読み出しが許可される領域である。本例に係るロム領域１１−１には、秘密情報XYを暗号化し、更に訂正符号が付与されたデータXYE（xe bits）が記録される。暗号化には、対称鍵暗号であるAES（Advanced Encryption Standard）などの暗号器を、暗号モードはCTR(Counter)、CBC(Cipher block chain)などを利用しても良いし、非対称暗号であるECDSA(楕円曲線暗号)やRSAなどを利用しても良い。また誤り訂正符号としては、BCH符号、Reed Solomon符号、LDPC(Low density parity check)符号などを利用してもよい。このように、本例は、いずれの暗号方法、訂正符号にも適用することが可能である。ここで、XYEとは、秘密情報XYが暗号化され、更に訂正符号が付与されたものとして表記される。また、（xe bits）とは、ビット数を表記する。
【００４４】
秘匿領域（Hidden area）１１−２は、ＮＡＮＤ型フラッシュメモリ１０の外に対してはデータ記録が禁止され、データ読出も禁止される領域である（Read Program inhibit）。本例に係る秘匿領域１１−２には、上記認証に用いるX, Yに対応するデータXYが記録される。
【００４５】
一般領域（User area）１１−３は、データ記録およびデータ読み出しのいずれも自由に可能な領域である。一般領域１１−３には、例えば、写真などの画像データや、動画データ等が記録される。
【００４６】
尚、上記におけるロム領域、秘匿領域、一般領域は、物理的構成を異ならせることで実現してもよいし、物理的構成は同一であるがＮＡＮＤ型フラッシュメモリ内の論理的制御で実現してもよい。ここで、論理的制御とは、領域ごとにＮＡＮＤ型フラッシュメモリ外からのアクセスを制御する識別子を設け、これを保持し、ＮＡＮＤ型フラッシュメモリが外部から当該領域へのアクセスを受領した際に、同識別子によってアクセス制御を行う、などの方法である。
【００４７】
また、セルアレイ（Cell array）１１を構成する個々のメモリセルは、複数ビットを記憶するものであってもよいし（MLC: Multi Level Cell）、１ビットを記憶するものであってもよい（SLC: Single Level Cell）。更に、ロム領域及び秘匿領域についてはSLCで利用する構成とし、一般領域についてはMLCで利用する構成としてもよい。この時、SLC領域とMLC領域とはセルアレイの物理的構成が異なっていてもよいし、MLCとして利用可能なメモリセルの一部のビットのみを使用して、疑似的なSLC領域として利用してもよい。
【００４８】
データキャッシュ（Data Cache）１２は、セルアレイ１１から読出したデータを一時的に記憶する。
【００４９】
バイアスドＲＮＧ（Biased RNG）１４は、所定確率ηにて1となる乱数νを生成する。尚、バイアスドＲＮＧの入力元として下記の乱数生成器を用いてもよく、その場合乱数生成器から出力される複数の乱数列に対して、論理積や論理和などの演算を行うことで所定確率ηに対応した乱数を生成することが可能である。
【００５０】
乱数生成器（RNG: Random Number Generator）１６は、認証に用いる乱数Nonce_N（a bit）を生成する。
【００５１】
順序交換回路（Permutation & Concatenation）１８は、両者が共有したXYを用いて、ホスト２０から入力される乱数Nonce_Hと、メモリ１０から入力される乱数Nonce_Nとから構成した乱数Nonce（c bits）を生成する。ここで、aはNonce_Nのビット長を意味し、bはNonce_Hのビット長を意味し、cは圧縮演算回路の1処理当たりに入力されるビット長を意味する。すなわち、順序交換回路（Permutation & Concatenation）から出力される個々の乱数Nonceは圧縮演算回路の1処理用のデータであり、1処理用にNonce_NとNonceHの総ビットを用いてもよいし、部分ごとに選択的に用いてもよい。
【００５２】
圧縮演算回路（Compress (ex. inner product)）１３は、データキャッシュ１２の出力XY（c bit each）と順序交換回路１３の出力（c bits）について内積演算などの所定の演算を行い、データCを出力する。
【００５３】
ビット毎加算回路Ｃ１は、圧縮演算回路１３の出力ビットに対して、バイアスドＲＮＧによって生成されたνを付与したz=C+νを、出力部１５へ出力する。尚、前述の通り、ビット加算とは排他的論理和を意味する。すなわち、ビット毎加算回路は、2入力データのビット毎の排他的論理和を出力する。
【００５４】
出力部１５は、ビット毎加算回路Ｃ１の結果（z=C+ν）を、コントローラ１９を介してホスト２０に出力する。
【００５５】
なお、上記セルアレイ１１以外のデータキャッシュ１２等の構成要素は、メモリコントローラ１９に配置されることも同様に可能である。
【００５６】
１−２．ホスト
本例に係るホスト（Host）２０は、訂正処理部２１、暗号の復号部２２、鍵保持部２３、データ一時記憶部２５、圧縮演算部２６、乱数生成部２７、順序交換部２９、判定部３０等を備える。
【００５７】
訂正処理部（ECC）２１は、ＮＡＮＤ型フラッシュメモリ１０のロム領域１１−１から読み出されたデータXYEに誤り訂正処理（ＥＣＣ）を行う。
【００５８】
復号部（Decrypt）２２は、読み出したデータXYEに対してエラー訂正処理を行った後、鍵保持部２３が保持する鍵KEYによりデータデータXYE復号して、XYを得る。
【００５９】
データ一時記憶部（Data cache）２５は、復号したXYを一時的に保持する。これにより、ホストデバイス２０とＮＡＮＤ型フラッシュメモリ２０は、秘密情報XYを共有できる。
【００６０】
圧縮演算部（Compress (ex inner product)）２６は、データキャッシュ２５の出力（c bit each）と順序交換回路２９の出力（c bits）とについて内積演算などの所定の演算を行い、データCを出力する。
【００６１】
乱数生成部（RNG）２７は、ホストの一時乱数Nonce_H (b bit)を生成する。
【００６２】
順序交換部（Permutation & Concatenation）２９は、両者は共有したXYを用いて、ホスト２０から入力される乱数Nonce_Hと、メモリ１０から入力される乱数Nonce_Nとから構成した乱数Nonce（c bits）を生成する。
【００６３】
判定部（Accept if Hwt(Z(+)C) ≦ t*clen）３０は、圧縮演算部２６の出力Cおよび出力部１５の出力Zについて、上記のようにハミング重みHwt(Z(+)C)を行い、ハミング重みHwt(Z(+)C)が、所定値t*clenを下回った場合、秘密情報を保持しているとみなし、認証成功と判定する。ただし、η≦t<0.5、clenはZ(+)Cのビット長とする。
【００６４】
このように、ホスト２０は、バイアスドRNG処理２７を除き、判定部３０により同様の処理によって得られたCとzとを比較することで、被認証コンポーネントであるＮＡＮＤ型フラッシュメモリ１０の正当性を確認する。
【００６５】
尚、上記構成による同様の処理を複数回行うことで最終的に正当性を確認することも可能である。例えば、本図では、Cが複数ビットである場合を例としており、比較判定方法はzとCの加算ビット系列におけるハミング重みを判定に用いている。もし、Cが単一ビットであった場合、前述のHB+プロトコルと同様に、前述の処理は複数回行う必要があり、この場合はHB+プロトコルと同様にエラー変数の生起確率に基づいてzとCの不一致率を検査すればよい。
【００６６】
１−３．変形例
上記に限られず、本例の構成は、以下のように必要に応じて、変形することが可能である。
【００６７】
圧縮処理について、図１及び図２で示した比較例１、２に係る内積計算に対応しても良いが、必ずしも内積計算でなくともよい。例えば、圧縮処理を、LFSR(Linear Feedback Shift Registor)で構成する演算器に対してXYを基とするデータとNonce_H及びNonce_Nを基とするデータを入力し、全入力後のLFSR中のレジスタ値の一部もしくは全てを圧縮結果として用いてもよい。または、LFSRとしてCRC演算器を用いてもよい。更に、圧縮処理に用いる関数としてハッシュ関数を用いてもよい。ハッシュ関数は暗号器に基づいていてもよく、基づいていなくてもよい。いずれの演算方法を用いても本実施例にて提案している方法を適用することが可能である。また安全性の根拠となっているLPN問題に属していることに変わりはない。尚、ここで圧縮処理とは可逆圧縮であるか、非可逆圧縮であるか、は問わず、少なくとも入力されたデータよりも小さく、かつ入力データに依存するデータを出力する処理を意味する。
【００６８】
また、圧縮計算部に対してNonce_HとNonceNを元に生成したNonceを送出する処理について説明する。NonceはNonce_HとNonceNを所定の順序によって結合し送出されるデータであり、結合・送出方法としては、単純な順送りデータ結合・送出、互いのデータを交互に挿入したインターリーブデータ結合・送出などの方法であってよく、また前述の方法により複数回データを送出しても良い。いずれにせよ、Nonceは、Nonce_N及びNonceHの少なくとも一部のデータより生成されたデータであり、cビット長のデータとなる。ここで、Nonce_Nのデータ長はaとおき、Nonce_Hのデータ長はbとおき、両者の合計データ長をdとおく。仮にc=dであり、かつデータを複数回送出しない場合、圧縮計算部からの出力は1ビットとなる。仮にc=dであり、かつデータを複数回送出する場合、圧縮計算部からの出力は1ビットが複数回出力される。仮にc<dであり、かつデータを複数回送出する場合、圧縮計算部からの出力は1ビットが複数回出力される。
【００６９】
一方、Nonceとの圧縮を計算するXYにおいても、XY中のデータがcビット単位で圧縮計算部へと送出される。ここで、XYデータのビットサイズxはcと等しいもしくは整数倍である。cと等しい場合、圧縮計算部の出力は1ビットとなる。cの整数倍である場合、圧縮計算部の出力は1ビットが複数回となる。代表的な組み合わせについて記すと、
・c=d=xの場合、圧縮計算部の出力は1ビット
・c=d<xの場合、圧縮計算部の出力は1ビットが複数回
・c<d, c<xの場合、圧縮計算部の出力は1ビットが複数回
となる。尚、前記は圧縮計算部が2入力を1ビットに圧縮する場合の例であり、圧縮計算部が2入力を複数ビットに圧縮する場合は、1回あたりの出力値自体も複数ビットとなる。
【００７０】
＜２．認証フロー＞
次に、図４に沿って、図３に示した構成におけるメモリシステムの認証フローについて説明する。
【００７１】
認証開始（Start）すると、ステップＳ１１の際、ホストデバイス１０は、ＮＡＮＤ型フラッシュメモリ１０へXYEの読出し命令（Read XYE）を送出する。
【００７２】
続いて、ステップＳ１２の際、ＮＡＮＤ型フラッシュメモリ１０は、上記読出し命令に従って、XYEをセルアレイ１１−１よりロード（load XYE）し、これをホストデバイス２０へと送出する。
【００７３】
続いて、ステップＳ１３の際、ホストデバイス２０は、受領したXYEに対して、上記復号処理を行い、XYを得る（Retrieve XY）。
【００７４】
続いて、ステップＳ１４の際、ホストデバイス２０は、認証要求（Request authentication）を、ＮＡＮＤ型フラッシュメモリ１０へ送出する。ここで、認証要求にはNonce_Hを含んでいてもよい。
【００７５】
続いて、ステップＳ１５の際、ＮＡＮＤ型フラッシュメモリ１０は、Nonce_Hを受領し、XYをロードする（Load XY (if required)）。
【００７６】
続いて、ステップＳ１６の際、ＮＡＮＤ型フラッシュメモリ１０は、Nonce_Nおよびνを生成する（Create Nonce_N, Create ν）。
【００７７】
続いて、ステップＳ１７の際、ＮＡＮＤ型フラッシュメモリ１０は、上記のように、生成されたνを付与し、Zを計算する。ＮＡＮＤ型フラッシュメモリ１０は、Nonce_N及びZをホスト２０へと送出する。
【００７８】
続いて、ステップＳ１８の際、ホスト２０は、それらデータNonce_N及びZを受領後、内積演算などの所定の演算を行い、データCを計算する。
【００７９】
続いて、ステップＳ１９の際、ホスト２０は、ZとCのビット毎XOR値の系列に対してハミング重みHwt(Z(+)C)を計算し、これが所定値t*clenを下回るか否かの判定処理（Check Hwt(Z(+)C) ≦ t*clen）を行う。ここで、上記のように、tはＮＡＮＤフラッシュメモリ１０がZの算出時に用いたエラービットもしくはエラーベクトルνにおけるエラー付与確率（もしくはデータ中の1の出現確率）ηに基づく値であり、η≦t<0.5であるとする。またclenはCのビット長とする。
【００８０】
続いて、ステップＳ２０の際、上記ステップＳＴ１９の判定結果が所定を下回らなかった場合（fail）、ホスト２０は、失敗としてこの動作を停止する。
【００８１】
続いて、ステップＳ２１の際、上記ステップＳＴ１９の判定結果が所定を下回った場合（Success）、ホスト２０は、あらかじめ定められたラウンド数に達しているか否かを判定する（Enough round ?）。ここで、ラウンド数とは前記認証要求処理から前記判定処理までの一連の処理を指す。ラウンド数に達していない場合（No）には、再度認証要求処理（Ｓ１４〜）を繰り返す。
【００８２】
続いて、ステップＳ２２の際、ラウンド数に達している場合（Yes）には、認証が成功したとみなし、ホストデバイス１０は、必要に応じて、前記XYに基づきMedia IDを算出する処理を行う。Media IDの算出処理、Media IDの利用方法（Ｓ２３以下）については後述する。
【００８３】
以上の動作により、第１実施形態に係る認証フローを終了する（End）。
【００８４】
尚、Nonce_N、Nonce_H、νのパラメータは、ラウンド毎に異なるものを用いる必要がある。また、ＮＡＮＤ型フラッシュメモリ１０が認証要求を受領した際、前認証要求時のXYがData Cacheにロードされたままであった場合、セルアレイからのXYのロードを省略し、Data cache内の値を用いてもよい。また、ステップＳ１７の後、Data cache内のXYを消去してもよい。特に、ＮＡＮＤ型フラッシュメモリ１０がData cacheへのアクセス機能を外部に提供している場合、認証に要するデータZを計算した段階でData cache内の秘密情報XYを消去することはセキュリティー上有用である。
【００８５】
＜３．作用効果＞
第１実施形態に係る構成およびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも下記（１）の効果が得られる。
【００８６】
（１）認証コンポーネント、被認証コンポーネント間で、異なる秘密情報XYの秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証できる。
【００８７】
本例に係るＮＡＮＤ型フラッシュメモリ１０は、秘密情報XYを記録禁止・読出禁止領域である秘匿領域１１−２に保持し、同秘密情報XYを暗号化し更に訂正符号を付与したXYEを記録禁止・読出許可領域であるロム領域１１−１に保持する。さらに、ホスト２０は、XYEを読み出してエラー訂正処理２１、復号化処理２２をする機能、および復号に用いる鍵２３により、ＮＡＮＤ型フラッシュメモリ１０およびホスト２０の両者で、秘密情報XYを共有することができる。そのため、認証・被認証コンポーネントは、共有した秘密情報XYで、認証を行うことができる（ＳＴ１１〜ＳＴ２３）。
【００８８】
また、ＮＡＮＤ型フラッシュメモリ１０とホストデバイス２０は、各々一時乱数を生成するＲＮＧ１６，１７、順序交換部１８，２９、圧縮計算部１３，２６、一時乱数のビット毎加算部Ｃ１，２６、送出部１５を備える。また、ＮＡＮＤ型フラッシュメモリ１０は、バイアスドＲＮＧ１４を備える。ホスト２０は、ＮＡＮＤ型フラッシュメモリ２０から送出されたZとホストデバイス内部で計算したCとを比較し認証を行う判定部３０を備える。
【００８９】
このように、第１実施形態では、秘密情報XYを記録禁止・読出禁止領域である秘匿領域１１−２に保持し、これを用いてデータZを生成するため、秘匿性を保持できる。さらに、秘密情報XYを暗号化し更に訂正符号を付与したXYEを記録禁止・読出許可領域であるロム領域１１−１に保持する。ホスト２０は、ここから読み出したXYEに対して、エラー訂正処理２１、および鍵２３を用いた復号化処理２２を行うことで、XYを共有する。そのため、認証・被認証コンポーネント間で、異なるXYを秘密状態を維持したまま共有できる。
【００９０】
従って、第１実施形態に係る構成およびその認証方法によれば、認証・被認証コンポーネント間で、異なるXYを秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証できる点で有利である。
【００９１】
［第２実施形態］
次に、図５および図６を用い、第２実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。なお、以下の説明において、上記第１実施形態と重複する部分の説明については、省略する。
【００９２】
＜構成例（メモリシステム）＞
図５を用い、第２実施形態に係る構成例について説明する。
図示するように、第２実施形態に係る構成例では、ＮＡＮＤ型フラッシュメモリ１０が、ロム領域１１−１，秘匿領域１１−２に、それぞれ複数のXYEおよび複数のXYを記憶する点で、上記第１実施形態と相違する。ここで、iとjが異なる場合、XY[i]≠XY[j]、XYE[i]≠XYE[j]である。
【００９３】
このように、複数のXYEおよび複数のXYの組を保持することで、秘密情報X及びY露見時の秘密情報の更新手段を提供することができる。仮にある1つのXYとXYEの組が中間者攻撃その他によって露見し、露見したXY及びXYEを流用した偽造デバイスが製造された場合でも、本例では、ホスト２０が保持するKEY[1]２３を更新（例えば、KEY[1]=> 更新KEY[2]）することができる。このように、露見したXY及びXYE以外の組を利用することで、偽造デバイスの排除が可能となる。各XY[i]の暗号化に用いられるKEYはiが異なる場合、異なるものである方が望ましい。
【００９４】
その他は、上記第１実施形態と実質的に同様であるため、詳細な説明を省略する。
【００９５】
＜認証フロー＞
次に、図６に沿って、第２実施形態に係る認証動作について説明する。
第２実施形態では、ＮＡＮＤ型フラッシュメモリ１０内には複数のXY及び複数のXYEが記録されているため、ホスト２０がいずれのXYを用いるかを選択することで、認証を行う。
【００９６】
そのため、第２実施形態では、ステップＳ１４の際に、ホスト２０が、認証を要求する（Request authentication）場合、いずれのXYを用いるかを指定するパラメータiを、乱数Nonce_Hとともに、ＮＡＮＤ型フラッシュメモリ１０に送出する点で、相違する。
【００９７】
その他は、上記第１実施形態と実質的に同様であるため、詳細な説明を省略する。
【００９８】
＜作用効果＞
第２実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【００９９】
さらに、第２実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、ロム領域１１−１、秘匿領域１１−２に、それぞれ複数のXYEおよび複数のXYを記憶する点で、上記第１実施形態と相違する。
【０１００】
このように、複数のXYEおよび複数のXYの組を保持することで、秘密情報X及びY露見時の秘密情報の更新手段を提供することができる。仮にある1つのXYとXYEの組が中間者攻撃その他によって露見し、露見したXY及びXYEを流用した偽造デバイスが製造された場合でも、本例では、ホスト２０が保持するKEY[1]２３を更新（例えば、KEY[1]=> 更新KEY[2]）することができる。
【０１０１】
そのため、第２実施形態に係る認証フローでは、ステップＳ１４の際に、ホスト２０が、認証を要求する（Request authentication）場合、いずれのXYを用いるかを指定するパラメータiを、乱数Nonce_Hとともに、ＮＡＮＤ型フラッシュメモリ１０に送出する。
【０１０２】
このように、第２実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、複数のXY及び複数のXYEを有し、ホストデバイスからの命令によりXYEを選択的に送出する機能を有し、ホストデバイスからの命令により認証に用いるXYを選択的に設定する。また、ホストデバイスは、自身が保持する鍵に対応するXYEを選択的に読み出す機能を有し、それを復号する機能を有し、また自身が保持する鍵を所定の条件下で更新する機能を有する。
【０１０３】
その結果、露見したXY及びXYE以外の組を利用することで、偽造デバイスの排除が可能となる点で有利である。
【０１０４】
［第３実施形態］
次に、図７乃至図９を用い、第３実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１０５】
＜構成例（メモリシステム）＞
図７を用い、第３実施形態に係る構成例について説明する。
図示するように、本例に係るＮＡＮＤ型フラッシュメモリ１０は、ロム領域１１−１Ｂ、秘匿領域１１−２Ｂに、複数のXYsubEおよび複数のXYsubをそれぞれ記憶する点で、上記第２実施形態と相違する。ここで、iとjが異なる場合、XYsub[i]≠XYsub[j]、XYsubE[i]≠XYsubE[j]である。XYsubEはXYsubを暗号化した後、訂正符号を付与したデータである。
【０１０６】
XYsubは、XYと同様に記録禁止・読出禁止領域（秘匿領域）１１−２Ｂに記録され、XYsubEは、XYEと同様に記録禁止・読出許可領域（ロム領域）１１−１Ｂに記録される。
【０１０７】
ここで、XYmainのデータサイズは、XYsubよりも大きい（データサイズ：XYmain ＞ XYsub）。また、XYmainとXYsubから構成されるデータが、前述の秘密情報XYに対応する。
【０１０８】
このように、第３実施形態では、XYの組に加え、XYsub[i], XYsubE[i]の組を更に備えるため、秘密情報X及びYを効率的に記録することができる点で有利である。詳細については、後述する。
【０１０９】
さらに、ＮＡＮＤ型フラッシュメモリ１０は、上記XYsubを格納するためのデータキャッシュ１２Ｂ、およびXYmainと XYsubとをビット毎加算するためのビット毎加算部Ｃ２を備える。ビット毎加算部Ｃ２の出力値が、前述の認証に用いられるXY値に相当する。ここで、XYmainとXYsubのビット長が異なることから、ビット加算Ｃ２においては、XYsubの繰り返しデータが適用される。
【０１１０】
例えば、本図にあるように所定の演算としては、ビット加算が考えられ、XYmainのデータサイズがXYsubのデータサイズの整数倍であった場合、XYmainのデータを保持するData cacheからはXYmainが順送りに送出され、XYsubのデータを保持するData cacheからはXYsubが順送りかつ繰り返し送出される構成が考えられる。XYsubを保持するData cacheはリングバッファと考えてもよい。また、ビット毎加算以外にもXYmainとXYsubの結合値をXYとしてもよいし、XYmainとXYsubのインターリーブ結合値をXYとしてもよいし、XYmainとXYsubをLFSRに入力しLFSRの所定レジスタの値をXYとしてもよい。すなわち、本実施例ではビット毎加算部としているが、2入力から構成したデータをXYとして用いるいずれの演算方法も適用可能である。
【０１１１】
同様に、ホスト２０は、読み出したXYsubEに対応するための、訂正処理部２１Ｂ、暗号の復号部２２Ｂ、鍵保持部２３Ｂ、データ記憶部２５Ｂ、加算部Ｃ３を更に備える。ホスト２０は、上記構成により、同様に、エラー訂正処理を行い、対応するKEY_XYsubにより復号することでXYsubを得る。これにより、ホストデバイスとＮＡＮＤ型フラッシュメモリ間で、秘密情報XYmain及びXYsubを共有できる。ここで、本図においてはKEY_XYmainとKEY_XYsubは異なるオブジェクトとして描かれているが、実際には同じ鍵であっても良い。また、各XYsub[i]の暗号化に用いられるKEY_XYsubはiが異なる場合、異なるものである方が望ましい。さらに、ホストデバイス２０、メモリ１０は、XYmainとXYsubを用いて所定の演算を行ったXY値により、認証処理を行う。
【０１１２】
＜認証フロー＞
次に、図８に沿って、第３実施形態に係る認証動作について説明する。
第３実施形態では、ＮＡＮＤ型フラッシュメモリ１０内にはXYmainに加えてXYsubが、またそれらを暗号化したXYmainE及びXYsubEが記録される。
【０１１３】
そのため、図示するように、対応するステップＳ１３において、ホスト１０は、XYmainE , XYsubEを更に読み出して復号をし、秘密情報XYmain，XYsubに基づく秘密情報XYを生成する（Create XY）。続いて、ホスト２０は、秘密情報XYmainとXYsubから導出された情報を用いて、同様の認証を行う。
【０１１４】
また、ＮＡＮＤ型フラッシュメモリ１０側においても同様に、ステップＳ１５において、読み出した秘密情報XYmain，XYsubに基づいて秘密情報XYを生成する（Create XY）点で、上記第２実施形態と相違する。
【０１１５】
＜作用効果＞
第３実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。さらに、第３実施形態では、（２）の効果が得られる。
【０１１６】
（２）秘密情報X,Yを効率的に記録することができ、記録時間を高速化できる点で有利である。
【０１１７】
第３実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、複数のXYsub及び複数のXYsubEを有し、ホスト２０からの命令によりXYsubEを選択的に送出し、ホスト２０からの命令により認証に用いるXYsubを選択的に設定し、選択されたXYsubとXYを所定の演算で導出した値により認証を行う。
【０１１８】
また、ホストデバイスは、自身が保持する鍵２３Ｂに対応するXYsubEを選択的に読み出し、それを復号する機能２２Ｂを有し、また自身が保持する鍵２３Ｂを所定の条件下で更新する機能を更に有し、選択したXYsubとXYmainを所定の演算で導出した値により認証３０を行う。
【０１１９】
このように、XYmainの組に加え、XYsub[i], XYsubE[i]の組を更に備えるため、秘密情報X及びYを効率的に記録することができる点で有利である。
【０１２０】
より具体的には、例えば、図９のように示される。図示するように、ＮＡＮＤ型フラッシュメモリの製造工程において、XYmain、XYmainE、XYsub、XYsubEの複数の組は、ＸＹ発生装置（XY GEN）により生成され、書き込み装置（Writer）により、複数のＮＡＮＤ型フラッシュメモリ（ここでは、Chip1〜Chip4）にデータ書き込みがされる。
【０１２１】
ここで、XYmain及びXYmainEのデータは、複数のチップChip1〜Chip4から構成される集団内（例えばロット）で同一のデータで良い。一方、XYsub及びXYsubEは、チップChip1〜Chip4毎に異なるデータ（XYsub1〜XYsub4及びXYsubE1〜XYsubE4）とする必要がある。
【０１２２】
このように、第３実施形態では、データ書き込み動作において、データ量の多いXYmain及びXYmainEを複数のチップChip1〜Chip4で共通化することにより、メモリへのデータ書き込みプロセスを最適化でき、効率的に記録することが可能となる。
【０１２３】
仮に、XYmain及びXYmainEをハードワイヤードで構成する場合、実際に記録するデータは、データサイズが小さいXYsub及びXYsubEとなり記録時間を短縮できる。また、仮にXYmain及びXYmainEをセル上に記録する場合において、集団内で同一であることにより、ＮＡＮＤ型フラッシュメモリへのデータ記録装置に対して記録データを転送する時間を短縮できる。先に述べたように、記録時間の増加は、コストの増加となるため、第３実施形態によれば、製造コストを低減することができるというメリットも大きい。
【０１２４】
［第４実施形態（多重記録される一例）］
次に、図１０および図１１を用い、第４実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１２５】
＜構成例（メモリシステム）＞
図１０を用い、第４実施形態に係る構成例について説明する。
第４実施形態では、メモリ１０の秘匿領域１１−２に、複数のXY[i]を多重に複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有する点で、上記第２実施形態と相違する。
【０１２６】
すなわち、第２実施形態におけるXY[i]を複製したデータは、図１０において、XY[i,1],XY[i,2],...,XY[i,n]によって示され、1≦i≦mに対しXY[i,1]=XY[i,2]=…=XY[i,n]である。また、1≦j≦nに対しXY[1,j]≠XY[2,j]≠…≠XY[m,j]である。
【０１２７】
ここで、XYEがECCが付与されている一方で、XYにはECCが付与されていないため、ＮＡＮＤ型フラッシュメモリ内でセルから読み出したデータにエラーが含まれている場合、ＮＡＮＤ型フラッシュメモリが認証に用いるXYの完全性が失われることも考えられる。しかしながら、本例のように、複数のXY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有することにより、検査・選択部１２−０により、前記エラーが含まれているかどうかを複製データ間でのデータ比較により検出することができる。
【０１２８】
そのため、本例のメモリは、XY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃに対応するための検査・選択部（Check sum & select）１２−０を更に備える点で、第２実施形態と相違する。
【０１２９】
図１０において、セル１１−２からロードされた少なくとも2つ以上のXYのデータセットは所定の上記同様の方法により比較を行うことでエラーが含まれているか否かを検査する。仮にエラーが含まれていた場合もしくはエラーが除去できない場合、異なる2つ以上のXYのデータセットを再度ロードし、同様に検査する。これをエラーが含まれていないもしくは除去できるデータセットが見つかるまで繰り返し、同データセットが見つかった場合それを認証に用いる。上記所定の方法の例としては、2つのXYをロードし、ビット毎にXOR値を算出した後、XOR値がすべて0であるかどうか、により検査する方法が考えられる。また、3つ以上のXYをロードし、多数決判定によってビット毎にエラーを除去したXYを得る方法も考えられる。また、本図においては、XYの複製データはすべて同一データとしているが、複製データのうち奇数番号のデータと偶数番号のデータの極性が反転しているように相補関係にあるデータを構成して事前に記録しておく方法も考えられる。この場合、前記相補関係にある2つのXYをロードし、ビット毎にXOR値を算出した後、XOR値がすべて1であるかどうか、により検査することが可能である。
【０１３０】
＜認証フロー＞
次に、図１１に沿って、第４実施形態に係る認証動作について説明する。
図示するように、第４実施形態では、ＮＡＮＤ型フラッシュメモリ１０の秘匿領域１１−２内に、複数のXYが多重記録される。
【０１３１】
そのため、ステップＳ１５の際、ＮＡＮＤ型フラッシュメモリ１０は、少なくとも2つ以上のXYを読み出し、比較し、エラーを含んでいないXYを用いて認証を行う（Load / compare XYs）。
【０１３２】
＜作用効果＞
第４実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【０１３３】
さらに、第４実施形態によれば、メモリ１０の秘匿領域１１−２に、複数のXY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有する。
【０１３４】
ここで、XYEがECCが付与されている一方で、XYにはECCが付与されていないため、ＮＡＮＤ型フラッシュメモリ内でセルから読み出したデータにエラーが含まれている場合、ＮＡＮＤ型フラッシュメモリが認証に用いるXYの完全性が失われることも考えられる。
【０１３５】
しかしながら、第４実施形態によれば、複数のXY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有することにより、検査・選択部１２−０により、前記エラーが含まれているかどうかを複製データ間でのデータ比較により検出することができる。結果、メモリ１０内でセルから読み出したデータにエラーが含まれている場合であっても、メモリ１０が認証に用いるXYの完全性が失われることを防止できる点で更に有利である。
【０１３６】
［第５実施形態］
次に、図１２および図１３を用い、第５実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１３７】
＜構成例（メモリシステム）＞
図１２を用い、第５実施形態に係る構成例について説明する。第５実施形態に係る構成例は、上記第３、第４実施形態を組み合わせたものに関する一例である。
【０１３８】
図示するように、第５実施形態に係るＮＡＮＤ型フラッシュメモリ１０は、秘匿領域１１−２に、XYsub及びXYsubEについても複製データXYsub[i,j]及びXYsubE[i,j]を記録する点で、上記第４実施形態と相違する。
【０１３９】
また、上記に対応するための検査・選択部１２−０Ｂおよびデータキャッシュ１２Ｂを更に備える。
【０１４０】
＜認証フロー＞
次に、図１３に沿って、第５実施形態に係る認証動作について説明する。
第５実施形態では、ＮＡＮＤ型フラッシュメモリ１０内に、更にXYsubも多重記録される（XYsub[i,j]及びXYsubE[i,j]）。
【０１４１】
そのため、ステップＳ１５の際、ＮＡＮＤ型フラッシュメモリ１０は、更に少なくとも2つ以上のXYsubを読み出し、比較し、エラーを含んでいないXYsubを用いて認証を行う（Load / compare XYs and XYsubs）。
【０１４２】
＜作用効果＞
第５実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【０１４３】
さらに、第５実施形態によれば、ＮＡＮＤ型フラッシュメモリ１０は、秘匿領域１１−２に、XYsub及びXYsubEについても複製データXYsub[i,j]及びXYsubE[i,j]を記録する。
【０１４４】
必要に応じて、本例のような構成および方法を適用することが可能である。
【０１４５】
［第６実施形態］
次に、図１４および図１５を用い、第６実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１４６】
＜構成例（メモリシステム）＞
図１４を用い、第６実施形態に係る構成例について説明する。
第６実施形態でも同様に、ＮＡＮＤ型フラッシュメモリ１０が、更に複数のXY[i]を複製した情報を有する。すなわち、先の第２実施形態におけるXY[i]を複製したデータは本図においてXY[i,1],XY[i,2],...,XY[i,n]によって示され、1≦i≦mに対しXY[i,1]=XY[i,2]=…=XY[i,n]である。また、1≦j≦nに対しXY[1,j]≠XY[2,j]≠…≠XY[m,j]である。
【０１４７】
ここで、XYデータを複製することは第４実施形態と同様であるが、本第６実施形態においては、ＮＡＮＤ型フラッシュメモリ１０側では複製データの比較処理を行わず、その代わりにホスト２０で比較処理を行う点で、相違する。そのため、本例では、ホスト２０が、多数決判定部（Majority check）３０を備える点で、相違する。
【０１４８】
すなわち、ＮＡＮＤ型フラッシュメモリ１０は、ホスト２０により指定されたiに応じ、XY[i,1],XY[i,2],...,XY[i,n]のうち少なくとも2つ以上をロードし、各々のXYに対して前述の認証処理を行う。ここで、各々のXYに対しては同一のNonce_N及び同一のNonce_Hを利用し、またバイアスドRNGによって生成されたνについても同一のものを適用する。
【０１４９】
ＮＡＮＤ型フラッシュメモリ１０の送信部１５は、複数のXYに対して、他のパラメータが同一な条件で複数のz(z[i,1],z[i,2],…,z[i,n])を計算し、ホスト２０に送出する。
【０１５０】
ホストデバイスは、複数のz(z[i,1],z[i,2],…,z[i,n])を受領した後、多数決判定部３１により、多数決判定を行い、単一のzを得る。ここで、各zが複数のビット要素で構成されていた場合、圧縮計算部の出力が複数ビットからなる場合、前記多数決判定はビット要素毎に行う。
【０１５１】
ホストデバイスは、多数決判定によってエラーを除去したZを得たのち、前述と同様の判定処理３０を行うことで、ＮＡＮＤ型フラッシュメモリ１０を認証する。
【０１５２】
＜認証フロー＞
次に、図１５に沿って、第６実施形態に係る認証動作について説明する。
第６実施形態では、ＮＡＮＤ型フラッシュメモリ１０内に多重記録されているXYを用いて、ＮＡＮＤ型フラッシュメモリが複数のZを計算し、送出し、ホストデバイスは複数のZを多数決処理することで単一のZを得て、認証を行う。
【０１５３】
そのため、ステップＳ１７の際、ＮＡＮＤ型フラッシュメモリ１０は、計算した複数のZ,jをホスト２０に送信する。
【０１５４】
続いて、ステップＳ１８の際、ホスト２０は、複数のZの多数決判定部（Majority check）を更に行う点で、相違する。
【０１５５】
＜作用効果＞
第６実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【０１５６】
さらに、第６実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、更に複数のXY[i]を複製した情報を有する。さらに、ホスト２０が、多数決判定部（Majority check）３０を備える。
【０１５７】
そのため、計算資源に制約のあるＮＡＮＤ型フラッシュメモリ１０での比較処理を軽減でき、計算資源に余裕のあるホスト２０に比較処理（多数決処理）３０を依頼することができる。結果、ＮＡＮＤ型フラッシュメモリ１０へのコスト増加を抑制することができ、エラーの除去が可能となる点で有利である。
【０１５８】
［第７実施形態］
次に、図１６および図１７を用い、第７実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１５９】
＜構成例（メモリシステム）＞
図１６を用い、第７実施形態に係る構成例について説明する。第７実施形態は、上記第３、第６実施形態を組み合わせたものの一例に関する。
【０１６０】
図示するように、ＮＡＮＤ型フラッシュメモリ１０は、XYsub及びXYsubEについても複製データ１１−２Ｂ，１１−１Ｂを更に記録する。上記第６実施形態と同様に、複数のXYに対する認証用データzを算出して算出部１５でホスト２０に送信し、ホスト２０側で多数決処理３０を行う。
【０１６１】
＜認証フロー＞
次に、図１７に沿って、第７実施形態に係る認証動作について説明する。
第７実施形態では、ＮＡＮＤ型フラッシュメモリ１０内に、多重記録されているXYmain及びXYsubを用いて、ＮＡＮＤ型フラッシュメモリが複数のZを計算し、送出し、ホストデバイスは複数のZを多数決処理することで単一のZを得て、認証を行う。
【０１６２】
そのため、ステップＳ１１の際、ホスト２０は、多重記録されているXYmain及びXYsubの読み出し要求（Read XYmainE and XYsubE）を行う。
【０１６３】
続いて、ステップＳ１２の際、ＮＡＮＤ型フラッシュメモリ１０は、多重記録されているXYmain及びXYsubを読み出し（Load XYmainE and XYsubE）、ホスト２０に送信（XYmainE and XYsubE）する。
【０１６４】
＜作用効果＞
第７実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも下記（１）の効果が得られる。
【０１６５】
さらに、第７実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、XYsub及びXYsubEについても複製データ１１−２Ｂ，１１−１Ｂを更に記録する。上記第６実施形態と同様に、複数のXYに対する認証用データzを算出して算出部１５でホスト２０に送信し、ホスト２０側で多数決処理３０を行う。
【０１６６】
このように、必要に応じ、本例を適用することが可能である。
【０１６７】
［第８実施形態（Media ID retrieve process）］
次に、図１８乃至図２１を用い、第８実施形態について説明する。第８の実施形態は、上記ステップＳ２２において、メディアＩＤ（Media ID）を算出する種々の処理（Media ID retrieve process）に関するものである。
【０１６８】
ID retrieve process（１）
ID retrieve process（１）は、図１８のように示される。図示するように、この例（１）では、ステップＲＳ１の際、上記の認証に用いられたXYmain及びXYsubに対して、各々一方向性関数処理（One-way function）が行われる。その結果が、Media IDとして扱われる。
【０１６９】
ここで、一方向性関数処理としては、例えば、SHA-1、SHA-256、AEG-Hなどの暗号に基づく一方向性演算を用いることが可能である。
【０１７０】
ID retrieve process（２）
ID retrieve process（２）は、図１９のように示される。図示するように、この例（２）では、ステップＲＳ１，ＲＳ２の際、上記認証に用いられたXYmain及びXYsubは、前述の認証処理においてXYmainE及びXYsubEの復号に用いられたKEY_XYmainとKEY_XYsubのいずれか一方に相当するKEY_XYを用いて、更に復号処理（Decode）が行われる。
【０１７１】
続いて、ステップＲＳ３の際、同様の一方向性関数処理（One-way function）が行われ、その結果がMedia IDとして扱われる。
【０１７２】
ID retrieve process（３）
ID retrieve process（３）は、図２０のように示される。図示するように、この例（３）では、ステップＲＳ１，ＲＳ２の際、上記の認証に用いられたXYmain及びXYsubは、上記認証処理においてXYmainE及びXYsubEの復号に用いられたKEY_XYmain及びKEY_XYsubを用いて、更に復号処理（Decode）が行われる。
【０１７３】
続いて、ステップＲＳ３の際、同様の一方向性関数処理（One-way function）が行われ、その結果がMedia IDとして扱われる。
【０１７４】
ID retrieve process（４）
ID retrieve process（４）は、図２１のように示される。図示するように、この例（４）では、ステップＲＳ１，ＲＳ２の際、ステップＲＳ１，ＲＳ２の際、上記の認証に用いられたXYmain及びXYsubは、上記認証処理においてXYmainE及びXYsubEの復号に用いられたKEY_XYmain及びKEY_XYsub と異なるKEY_XYmain２及びKEY_XYsub２を用いて、更に復号処理（Decode）が行われる。ここで、KEY_XYmain２及びKEY_XYsub２は同一の値であってもよい。
【０１７５】
続いて、ステップＲＳ３の際、同様の一方向性関数処理（One-way function）が行われ、その結果がMedia IDとして扱われる。
【０１７６】
［第９実施形態（Media ID binding process）］
次に、図２２乃至図２３を用い、第９実施形態について説明する。第９実施形態は、Media IDの利用方法（Media ID binding process）に関するものである。
ここで、例えば、商用動画コンテンツ等を物理媒体に記録し、再生する場合、同物理媒体に固有な識別情報をコンテンツ記録時の暗号処理に用いてコンテンツを同物理媒体にバインドする方法がとられる。
【０１７７】
コンテンツ再生時は、前記識別情報に基づく復号処理もしくは検査処理などを行い、再生された識別情報とコンテンツ記録時の暗号処理に用いられた識別情報が一致しない場合、コンテンツの再生を停止するなどの方法がとられる。ここで物理媒体としては、例えば、SDカードなどのリムーバブルメディアの場合や、携帯電話などに内蔵されているエンベデッドメモリなどが考えられる。
【０１７８】
いずれにおいても、前記方法の目的は、あるメディアに記録された暗号処理済みコンテンツを、別のメディアへと不正複製された場合、不正複製コンテンツの再生を停止させることである。そのための情報として、メディア毎に異なる上記識別情報（メディアＩＤ）を利用している。
【０１７９】
ID binding process（１）
ID binding process（１）は、図２２のように示される。図示するように、この例（１）では、ＭＡＣ（Message Authentication Code）生成処理を行い、これを不正複製の防止に用いる。
【０１８０】
具体的には、ステップＢＰ１の際、前記識別情報としてMedia IDを用いる方法例として、コンテンツ暗号化に用いられるContent Keyにより、Media ID及びその他の情報に対し、ＭＡＣ生成処理を行う。
【０１８１】
続いて、コンテンツをメディアに記録する装置においては、同MACを生成し、これをメディアに記録しておく。コンテンツをメディアから再生する装置においては、記録されているMACをMedia ID、Content Keyにより検査し、正当性が確認された場合はコンテンツを再生し、正当性が確認されない場合はコンテンツの再生を停止するなどの方法を適用することが可能である。
【０１８２】
ID binding process（２）
ID binding process（２）は、図２３のように示される。図示するように、この例（１）では、コンテンツ暗号化に用いられるContent Keyを生成するための情報として、Media IDを利用する。
【０１８３】
ステップＢＰ１の際、コンテンツをメディアに記録する装置においては、Content Key Precursorと、Media ID及びContent Key Precursorを一方向性処理（One-way function）する。
【０１８４】
メディアに記録する装置においては、処理されたContent Keyによって暗号化されたコンテンツを記録しておく。
【０１８５】
コンテンツをメディアから再生する装置においては、記録されているContent Key PrecursorとMedia IDを同様の一方向性処理をすることでContent Keyを得て、コンテンツの復号と再生を行う。ここで、Media IDが一致しない場合、すなわち記録されているデータが異なるメディアに不正複製された場合など、には導出したContent Keyとコンテンツ暗号化に用いられているContent Keyが一致しないため、コンテンツの復号に失敗し、再生は停止される。
【０１８６】
［第１０実施形態（メモリ、記憶・再生ホストの一例）］
次に、図２４を用い、第１０実施形態について説明する。第１０実施形態は、上記実施形態の構成を組み合わせたメモリカード（inc. NAND chip）１０，記録ホスト（Recoding Device）２０Ａ，再生ホスト（Playback Device）２０Ｂのシステムにおいて、上記認証を行い、上記メディアＩＤを用い、ホスト２０Ｂにてコンテンツを再生する一例に関するものである。
【０１８７】
記録ホスト（Recoding Device）２０Ａがコンテンツをメモリカード（inc. NAND chip）１０に記録するに際し、まずメモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（１）により生成したMACをメモリカード（inc. NAND chip）１０に記録する。合わせて、ID binding process（１）において用いたContent Keyにより暗号化したコンテンツ（Encrypted Content）も記録する。更に、Content Key自身も安全な形で記録する。ここで安全な形とは、メモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で認証が成立した後にアクセスが可能となるモリカード（inc. NAND chip）１０内の記録エリアであってもよい。また、ここでいう認証は本願において記載されている認証方法でもよいし、メモリカード（inc. NAND chip）１０が持つ別の認証機能によって実現してもよい。また、安全な形の別な例としては、メモリカード（inc. NAND chip）１０もしくは記録ホスト（Recoding Device）２０Ａが有する鍵によって暗号化した形であってもよい。
【０１８８】
再生ホスト（Playback Device）２０Ｂがコンテンツをメモリカード（inc. NAND chip）１０から読出し、再生するに際し、まずメモリカード（inc. NAND chip）１０と再生ホスト（Playback Device）２０Ｂの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（１）に対応する処理により、メモリカード（inc. NAND chip）１０に記録されているMACを検証する。その後、Content Keyをメモリカード（inc. NAND chip）１０より読出し、暗号化したコンテンツ（Encrypted Content）の復号を行うことでコンテンツを再生する。
【０１８９】
［第１１実施形態（メモリ、記憶・再生ホストのその他の一例）］
次に、図２５を用い、第１１実施形態について説明する。第１１実施形態は、上記実施形態の構成を組み合わせたメモリカード（inc. NAND chip）１０、記録ホスト（Recoding Device）２０Ａ、再生ホスト（Playback Device）２０Ｂのシステムにおいて、上記認証を行い、上記メディアＩＤを用い、ホスト２０Ｂにてコンテンツを再生する一例に関するものである。
【０１９０】
記録ホスト（Recoding Device）２０Ａがコンテンツをメモリカード（inc. NAND chip）１０に記録するに際し、まずメモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（１）により生成したContent Keyをメモリカード（inc. NAND chip）１０に記録する。合わせて、ID binding process（２）において生成したContent Keyにより暗号化したコンテンツ（Encrypted Content）も記録する。更に、Content Key Precursor自身も安全な形で記録する。
【０１９１】
ここで安全な形とは、メモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で認証が成立した後にアクセスが可能となるモリカード（inc. NAND chip）１０内の記録エリアであってもよい。また、ここでいう認証は本願において記載されている認証方法でもよいし、メモリカード（inc. NAND chip）１０が持つ別の認証機能によって実現してもよい。また、安全な形の別な例としては、メモリカード（inc. NAND chip）１０もしくは記録ホスト（Recoding Device）２０Ａが有する鍵によって暗号化した形であってもよい。
【０１９２】
再生ホスト（Playback Device）２０Ｂがコンテンツをメモリカード（inc. NAND chip）１０から読出し、再生するに際し、まずメモリカード（inc. NAND chip）１０と再生ホスト（Playback Device）２０Ｂの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（２）に対応する処理により、メモリカード（inc. NAND chip）１０に記録されているContent Key PrecursorからContent Keyを生成する。その後、暗号化したコンテンツ（Encrypted Content）の復号を行うことでコンテンツを再生する。
【０１９３】
［第１２実施形態（メモリ、コントローラ、ホストの一例）］
次に、図２６を用い、第１２実施形態について説明する。第１２実施形態は、上記実施形態に適用可能な上記ＮＡＮＤ型フラッシュメモリ１０、コントローラ１９、およびホスト２０の一例に関するものである。本例では、メモリカードとしてＳＤカード（登録商標）を一例に挙げる。
【０１９４】
図示するように、本例では、メモリカードと接続されるホスト装置の機能ブロックも示されている。各機能ブロックは、ハードウェア、コンピュータソフトウェアのいずれかまたは両者を組み合わせたものとして実現することができる。このため、各ブロックがこれらのいずれでもあることが明確となるように、概してそれらの機能の観点から以下に説明する。このような機能が、ハードウェアとして実行されるか、またはソフトウェアとして実行されるかは、具体的な実施態様またはシステム全体に課される設計制約に依存する。当業者は、具体的な実施態様ごとに、種々の方法でこれらの機能を実現し得るが、いずれの実現の手法も本発明の範疇に含まれる。
【０１９５】
ホスト２０は、アプリケーション、オペレーティング・システム等のソフトウェア２１１を備えている。ソフトウェア２１１は、ユーザから、メモリカードへのデータの書き込み、メモリカードからのデータの読み出しを指示される。ソフトウェア２１１は、データの書き込みおよび読み出しをファイルシステム２１２に指示する。ファイルシステム２１２は、管理対象の記憶媒体に記録されているファイルデータを管理するための仕組みであり、記憶媒体の記憶領域内に管理情報を記録し、この管理情報を用いてファイルデータを管理する。
【０１９６】
ホスト２０は、ＳＤインターフェース２１３を有する。ＳＤインターフェース２１３は、ホスト２０とメモリカードとの間のインターフェース処理を行うのに必要なハードウェア、ソフトウェアからなる。ホスト２０は、ＳＤインターフェース２１３を介してメモリカードと通信を行う。ＳＤインターフェース２１３は、ホスト２０とメモリカードとが通信するのに必要な様々な取り決めを規定し、後述のメモリカードのＳＤインターフェース２３１と相互に認識可能な各種のコマンドの組を備えている。また、ＳＤインターフェース２１３は、メモリカードのＳＤインターフェース２３１と接続可能なハードウェア上の構成（ピンの配置、数等）も含む。
【０１９７】
メモリカードは、ＮＡＮＤ型フラッシュメモリ１０、メモリ１０を制御するためのコントローラ１９を有する。メモリカードは、ホスト２０に接続されたとき、およびオフ状態のホスト２０に挿入された状態でホスト２０がオンされたときに電源供給を受けて初期化動作を行った後、ホスト１からのアクセスに応じた処理を行う。
【０１９８】
ＮＡＮＤ型メモリ１０は、データを不揮発に記憶し、複数のメモリセルからなるページと呼ばれる単位でデータの書き込みおよび読み出しを行う。ページには、各ページに固有の物理アドレスが割り当てられている。また、メモリ１０は、複数のページからなる物理ブロック（消去ブロック）と呼ばれる単位でデータの消去を行う。なお、物理ブロック単位で物理アドレスが割り当てられていることもある。
【０１９９】
コントローラ１９は、メモリ１０によるデータの記憶状態を管理する。記憶状態の管理とは、どの物理アドレスのページ（または物理ブロック）が、どの論理アドレスのデータを保持しているかの関係、およびどの物理アドレスのページ（または物理ブロック）が消去状態（何も書き込まれていない、または無効なデータを保持している状態）であるかを管理することを含んでいる。
【０２００】
コントローラ１９は、ＳＤインターフェース３１、ＭＰＵ（micro processing unit）３２、ＲＯＭ（read only memory）３３、ＲＡＭ（『random access memory』）３４、ＮＡＮＤインターフェース３５を含んでいる。
【０２０１】
ＳＤインターフェース３１は、ホスト２０とコントローラ１９との間のインターフェース処理を行うのに必要なハードウェア、ソフトウェアからなり、ＳＤインターフェース１３と同様に、両者の通信を可能とする取り決めを規定し、各種のコマンドの組を備え、ハードウェア上の構成（ピンの配置、数等）も含む。メモリカード（コントローラ２２）は、ＳＤインターフェース３１を介してとホスト１と通信を行う。ＳＤインターフェース３１は、レジスタ３６を含んでいる。
【０２０２】
ＭＰＵ３２は、メモリカード２全体の動作を司る。ＭＰＵ３２は、例えば、メモリカード２が電源供給を受けた際に、ＲＯＭ３３内に格納されているファームウェア（制御プログラム）をＲＡＭ３４上に読み出して所定の処理を実行する。ＭＰＵ３２は、制御プログラムに従って各種のテーブルをＲＡＭ３４上で作成したり、ホスト１から受けたコマンドに従ってメモリ２１に対する所定の処理を実行したりする。
【０２０３】
ＲＯＭ３３は、ＭＰＵ３２により制御される制御プログラムなどを格納する。ＲＡＭ３４は、ＭＰＵ３２の作業エリアとして使用され、制御プログラムや各種のテーブルを一時的に記憶する。このようなテーブルとして、ファイルシステム１２によってデータに割り当てられた論理アドレスを有するデータを実際に記憶しているページの物理アドレスの変換テーブル（論物テーブル）が含まれる。ＮＡＮＤインターフェース３５は、コントローラ２２とメモリ２１とのインターフェース処理を行う。
【０２０４】
ＮＡＮＤ型フラッシュメモリ１０内の記憶領域は、保存されるデータの種類に応じて、例えばシステムデータ領域、機密データ領域、保護データ領域、ユーザデータ領域等を含んでいる。システムデータ領域は、コントローラ１９が、その動作に必要なデータを保存するためにメモリ１０内で確保しておく領域である。機密データ領域は、暗号化に用いる鍵情報や認証時に使用する機密データを保存しており、ホスト２０からアクセスできない。保護データ領域は、重要なデータ、セキュアなデータを格納する。ユーザデータ領域は、ホスト２０が自由にアクセスおよび使用することが可能で、例えばＡＶコンテンツファイルや画像データ等のユーザデータを格納する。なお、コントローラ１９は、ユーザデータ領域の一部を確保し、自身の動作に必要な制御データ（論物テーブル等）を保存する。
【０２０５】
本発明のいくつか実施形態を説明したが、これら実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２０６】
１０…ＮＡＮＤ型フラッシュメモリ（被認証コンポーネント）、１９…コントローラ、２０…ホストデバイス（認証コンポーネント）。
【技術分野】
【０００１】
認証コンポーネント、被認証コンポーネントおよびその認証方法に関するものである。
【背景技術】
【０００２】
一般に、セキュリティーを要する分野において、自己の正当性を証明する手段として暗号器と共有した秘密に基づく手法が採られている。
【０００３】
例えば、電子決済に用いるＩＣカード等では、カード内のＩＣに対して個別化されたＩＤ及び秘密情報が保持されており、更にＩＣカードは、ＩＤ及び秘密情報に基づく認証を行うための暗号処理機能を有している。別の例では、コンテンツの著作権保護において、ＳＤカード（登録商標）の正当性を証明する手段などもある。
【０００４】
上記の例は、いずれも被認証コンポーネントが、秘密鍵と暗号器とを保有していることが必要である。しかしながら、暗号器の実装は比較的大きな回路規模を要求されるため、回路規模上の制約が同時に課せられる環境においては自己の正当性を証明するのは非常に困難である。回路規模上の制約が課せられる代表例としては、例えば、RFID(Radio Frequency Identification)等があげられる。そのため、近年では、益々実装上の必要性が高まっているという背景がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国公開特許公報２０１０／０１６１９８８ Ａ１
【特許文献２】特開２０００−３５７２１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
秘密情報を認証コンポーネント、被認証コンポーネント以外の第三者に対する秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証可能とする。
【課題を解決するための手段】
【０００７】
実施形態によれば、一態様に係る秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶する被認証コンポーネントと、前記被認証コンポーネントを認証する認証コンポーネントとの間における認証方法は、前記認証コンポーネントが、前記被認証コンポーネントから受領した前記秘密情報XYEに対して、復号処理を行い、前記秘密情報XYを共有するステップと、前記被認証コンポーネントが、前記認証コンポーネントが生成する乱数Bを受領し、前記複製された秘密情報XYを複数ロードするステップと、前記被認証コンポーネントが、乱数Aおよびデータν（νは１の出現確率がη（ただし、η<0.5））を生成するステップと、前記被認証コンポーネントが、生成した前記乱数Aと受領した前記乱数Bの少なくとも一部から構成される乱数Dを生成するステップと、前記被認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、前記被認証コンポーネントが、前記データCに前記データνを付与した演算結果Zを、前記認証コンポーネントに送信するステップと、前記認証コンポーネントが、生成した前記乱数Bと受領した前記乱数Aの少なくとも一部から構成される乱数Dを生成するステップと、前記認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、前記認証コンポーネントが、受領した演算結果Zと生成したデータCとを用いて、判定処理を行うステップとを具備する。
【図面の簡単な説明】
【０００８】
【図１】比較例１に係るプロトコルを示すブロック図。
【図２】比較例２に係るプロトコルを示すブロック図。
【図３】第１実施形態に係る構成例を示すブロック図。
【図４】第１実施形態に係る認証フローを示すフロー図。
【図５】第２実施形態に係る構成例を示すブロック図。
【図６】第２実施形態に係る認証フローを示すフロー図。
【図７】第３実施形態に係る構成例を示すブロック図。
【図８】第３実施形態に係る認証フローを示すフロー図。
【図９】第３実施形態に係る秘密情報のデータ転送を示すブロック図。
【図１０】第４実施形態に係る構成例を示すブロック図。
【図１１】第４実施形態に係る認証フローを示すフロー図。
【図１２】第５実施形態に係る構成例を示すブロック図。
【図１３】第５実施形態に係る認証フローを示すフロー図。
【図１４】第６実施形態に係る構成例を示すブロック図。
【図１５】第６実施形態に係る認証フローを示すフロー図。
【図１６】第７実施形態に係る構成例を示すブロック図。
【図１７】第７実施形態に係る認証フローを示すフロー図。
【図１８】第８実施形態に係るID retrieval process(1)を示すブロック図。
【図１９】第８実施形態に係るID retrieval process(2)を示すブロック図。
【図２０】第８実施形態に係るID retrieval process(3)を示すブロック図。
【図２１】第８実施形態に係るID retrieval process(4)を示すブロック図。
【図２２】第９実施形態に係るID biding process(1)を示すブロック図。
【図２３】第９実施形態に係るID biding process(2)を示すブロック図。
【図２４】第１０実施形態に係る構成例を示すブロック図。
【図２５】第１１実施形態に係る構成例を示すブロック図。
【図２６】第１２実施形態に係る構成例を示すブロック図。
【発明を実施するための形態】
【０００９】
［比較例１（HB+プロトコルの一例）］
まず、図１を用い、比較例１について説明する。この比較例１は、HB+プロトコルの一例に関するものである。
【００１０】
HB+プロトコルは、２０００年にHopper とBlumらによって提案された、軽量の認証プロトコルであるHBプロトコルの改良プロトコルである。HBプロトコルは、雑音下におけるパリティ値の同定が困難であるということ（LPN：Learning Parity with Noise）に基づいており、受動攻撃に対する安全性が証明されている。ただし、HBプロトコルは、リーダー（Reader）へのなりすましといった能動攻撃に対して脆弱性がある。この点を解決するために、２００５年にJuelsらにより、HB+プロトコルとして提案されたものである。
【００１１】
HB+プロトコルの概要は、図１のように図示される。ここで、図１中の、a，b，x，yはベクトルであり、ν，zはビットである。
【００１２】
図示するように、HB+プロトコルでは、被認証コンポーネントであるタグ（Tag）と、認証コンポーネントであるリーダー（Reader）とが、各々秘密情報ベクトルx, yを共有する。
【００１３】
タグは、リーダーに対して一時乱数ベクトルbを渡す。
【００１４】
続いて、リーダーは、タグに対して一時乱数ベクトルaを渡す。
【００１５】
続いて、タグは、乱数aと秘密情報ベクトルxの内積（a・x）および乱数bと秘密情報ベクトルyとの内積（b・y）を計算する。さらに、タグは、ηの確率で１となる変数νを生成する。そして、内積（a・x）、内積（b・y）、変数νをそれぞれ加算して、z= ax(+)by(+)νを算出する。ここで、axは内積（a・x）を意味し、(+)は排他的論理和を意味する。
【００１６】
続いて、タグは、算出したzを、リーダーへと送信する。
【００１７】
続いて、リーダーは、受領したzと、自身で計算したax(+)byとを比較し、一致不一致を検査する。上記一連の処理を１単位として１ラウンドと称することもある。
【００１８】
これら上記1ラウンドの処理を複数回（例えば、数十回〜数万回程度）繰り返し、前述の不一致確率が、所定値tを下回った場合、タグが秘密情報を保持しているとみなし、認証が成功する。
【００１９】
尚、ax(+)byは、秘密情報x，yと、結合ベクトルa，bとのそれぞれの内積である。そのため、x，yの結合ベクトルxyを秘密情報とおき、a，bの結合ベクトルをConcat(a,b)とした場合、ax(+)byをConcat(a,b)xyと表現することも可能である。
【００２０】
［比較例２（Random HB#プロトコルの一例）］
次に、図２を用い、比較例２について説明する。この比較例２は、Random HB#プロトコルの一例に関するものである。Random HB#プロトコルは、上記比較例１に示したHB+プロトコルが更に改良されたプロトコルである。
【００２１】
上記HB+プロトコルは、受動的な攻撃と能動的な攻撃に対して解決策を提供したものの、Gilbertらによって提案された中間者攻撃に対して脆弱性がある傾向にある。この点を解決するために、GilbertらによりHB+プロトコルの改良方式プロトコルとして、Random HB＃プロトコルとして提案されたものである。
【００２２】
Random HB#プロトコルの概要は、図２のように図示される。ここで、図２中のX，Yは行列であり、a，b，z，νはベクトルである。
図示するように、Random HB#プロトコルでは、タグ（Tag）とリーダー（Reader）とが、各々秘密情報行列X, Yを共有する。
【００２３】
まず、タグは、リーダーに対して一時乱数ベクトルbを渡す。
【００２４】
続いて、リーダーは、タグに対して一時乱数ベクトルaを渡す。
【００２５】
続いて、タグは、乱数aと秘密情報行列xとの内積（aX）および乱数bと秘密情報行列yとの内積（bY）を計算する。ここで、X, Yは行列、a, bはベクトルであることから、各々の内積結果は、ベクトルとなる。また、タグは、ηの確率で１となる変数ベクトルνを生成する。そして、タグは、上記の値を加算して、z= aX(+)bY(+)νを算出する。ここでzはベクトルである。
【００２６】
続いて、タグは、算出したzを、リーダーへと送信する。
【００２７】
続いて、リーダーは、受領したzと自身で計算したaX(+)bYとのビット加算、すなわち排他的論理和演算を行った結果を用い、aX(+)bY(+)zのハミング重みHwt(aX(+)bY(+)z)を計算する。ハミング重みHwt(aX(+)bY(+)z)が、所定値t*clenを下回った場合、タグが秘密情報を保持しているとみなし、認証が成功する。ただし、η≦t<0.5、clenはAX(+)BYのビット長とする。
【００２８】
尚、aX(+)bYは秘密情報XとYの結合行列とaとbの結合ベクトルの内積であることから、X,Yの結合行列XYを秘密情報とおき、aとbの結合ベクトルをConcat(a,b)とした場合、aX(+)bYをConcat(a,b)XYと表現することも可能である。
【００２９】
＜実装上の改善点＞
しかしながら、上記比較例１、２に係るプロトコルでは、例えば、ＮＡＮＤ型フラッシュメモリ等に具体的に実装しようとした場合等に、以下（Ｉ）〜（ＩＶ）のような改善点が考えられる。
【００３０】
（Ｉ）秘密情報X及びYの共有手段
前述のように、上記比較例１、２では、リーダーとタグとは、秘密情報X, Yを共有している必要がある。しかしながら、上記比較例１、２では、秘密情報X, Yを共有するための具体的な共有方法が提示されていない。
【００３１】
そのため、仮にすべてのリーダーとタグとで同一のX, Yを事前に共有していた場合、一旦X, Yが露見してしまうと、システム全てに致命的な影響を与える。一方でタグ毎に異なるX, Yを適用した場合、リーダー側では全てのタグに適用されているX, Yを保持している、もしくはそれを統合的に管理しているデータベースへのアクセスなどが要求される。
その結果、リーダー側への負担が大きくなる。
【００３２】
尚、これに関連する先行技術として、特開２０００−３５７２１３号公報において、演算処理機能を有する記録媒体に複製コンテンツを記録する記録装置と該記録媒体との間の相互認証方法において、前記記録媒体は、少なくとも該記録媒体に依存する第１の情報と、前記記録装置と相互認証を行う際に該記録装置と共有すべき該記録媒体に依存する第２の情報とを記憶し、前記記録装置は、前記記録媒体から得られた前記第１の情報に基づき該記録媒体との間の相互認証を行う際に用いる認証情報を生成し、この生成された認証情報と前記第２の情報とを用いて前記記録装置と前記記録媒体との間で相互認証を行うことを特徴とする方法が提案されている。
【００３３】
（ＩＩ）コンポーネントPに対し、秘密情報X及びYを効率的に記録する手段
上記HB+プロトコル、Random HB#プロトコルにおいては、いわゆる上記LPN問題を現実的な計算量で同定を困難とするためには相応の秘密情報量、すなわちX, Yは相応のデータサイズである必要がある。ここで、X, Yが全てのタグで共通であれば、ハードワイヤードロジックで構成することも可能であるが、X,Yをタグ毎に異ならせる場合、タグはX, Yを保持するために十分なメモリ容量を持つ必要がある。また、これと同時にタグ製造において同データを個別に記録する必要性があり、記録時間はすなわち製造時間へと反映される。
その結果、メモリ容量の増加と記録時間の増加により、タグのコスト増大を招く。
【００３４】
（ＩＩＩ）コンポーネントPが保持する秘密情報X及びY損傷に対する保護手段
コンポーネントPが内部メモリにてX, Yを保持している場合、認証に用いる場合は同X, Yのデータ完全性が要求されるが、先行文献ではこれらについて言及されていない。データ完全性を保証するには、タグ内部のメモリにはエラー訂正符号を付与したX, Yを保有し、認証時に訂正処理を行うなどの方法が考えられる。しかしながら、一般に廉価メモリは必ずしも訂正機能を有しているわけではなく、メモリ側に訂正機能がない場合はメモリ以外のタグ内コンポーネントとして同訂正機能を有す必要がある。
その結果、タグのコスト増大を招く。
【００３５】
（ＩＶ）秘密情報X及びY露見時の秘密情報更新手段
上記Random HB#コンポーネントは、各々受動攻撃、能動攻撃、一定条件下での中間者攻撃に対する耐性が認められているものの、近年では一般化された中間者攻撃に対する脆弱性が報告されるなど、X, Yが露見する可能性を排除することはできない。X, Yの露見には、それ相応の攻撃コストが要求されるものの、一旦X,Yが露見した場合、同X,Yを用いた偽造タグなどの製造が可能となるため、仮にX, Yが露見した場合でも新たなX, Yへと移行できるように、秘密情報の更新手段がある方が望ましい。
【００３６】
そこで、上記の点を考慮し、以下において、実施形態について図面を参照して説明する。なお、これまでRFIDのリーダーとタグとを一例にとって説明をした。しかしながら、同様の要件はＮＡＮＤ型フラッシュメモリなどの回路面積が即座にコストに直結するメモリチップにおいても同様である。そのため、以下実施形態では、認証コンポーネントとしてのリーダー（Reader）としてＮＡＮＤ型フラッシュメモリを認証するホストデバイス（Host）、被認証コンポーネントとしてのタグ（Tag）としてＮＡＮＤ型フラッシュメモリ（NAND chip）を、一例に挙げて説明する。しかし、これに限られることはない。例えば、ＮＯＲ型フラッシュメモリ、抵抗変化式メモリ（ReRAM: Resistive Random Access Memory）、磁気抵抗メモリ(MRAM: Magnetoresistive Random Access Memory）、相変化メモリ（PRAM: Phase change Random Access Memory）、および強誘電体メモリ（FeRAM: Ferroelectric Random Access Memory）、ハードディスクドライブやソリッドステートドライブなどの演算機能及びメモリを有するストレージデバイス、RFIDやICカードなどの認証を要するコンポーネント、汎用演算素子と汎用メモリを有した計算器とソフトウェアから構成されるシステムなど、多様な実装形態に適用できる。尚、この説明においては、全図にわたり共通の部分には共通の参照符号を付す。
【００３７】
［第１実施形態］
図１および図２を用い、第１実施形態に係る認証コンポーネント、被認証コンポーネントおよびその認証方法について説明する。
【００３８】
＜１．構成例（メモリシステム）＞
まず、図３を用い、第１実施形態に係る構成例について説明する。
図３に示すメモリシステムは、被認証コンポーネントであるＮＡＮＤフラッシュメモリ１０、認証コンポーネントであるホストデバイス２０、両者を仲介するコントローラ１９を備える。図示するように、ホスト２０は、コントローラ１９と呼ばれるＮＡＮＤ型フラッシュメモリ１０に対するアクセス機能を有したデバイスを経由してＮＡＮＤ型フラッシュメモリにアクセスする。
【００３９】
ここで、半導体製品の製造工程について記載する。半導体製品の製造工程は、主に基板ウエハー上に回路を形成する前工程と、前記ウエハーを個片に切り分けた後、配線や樹脂パッケージ封入などを行う後工程に分けられる。ここで、コントローラ１９は、前工程においてＮＡＮＤ型フラッシュメモリ１０内に包含されるよう構成される場合、前工程においては包含されないが後工程において同一パッケージに包含されるよう構成される場合、ＮＡＮＤ型フラッシュメモリ１０とは異なるチップの形態をとる場合、など様々な場合がある。図３を含め、以下ではコントローラ１９は、ＮＡＮＤ型フラッシュメモリ１０とは異なるチップの形態をとる場合を例にとっている。しかしながら、本実施形態は、上記いずれのケースにおいても適用可能である。以下、特に断りのない限り、ホストデバイス２０とＮＡＮＤ型フラッシュメモリ１０間のデータや命令のやり取りにおいては、多くの場合コントローラが仲介するものであるが、これは省略することとする。なお、ＮＡＮＤ型フラッシュメモリ１０およびコントローラ１９の構成例については、後述する。
【００４０】
図３に示す各コンポーネント、データ処理については、以下の通り説明する。図示するように、秘密情報X, Yを共有する方法と、同方法をＮＡＮＤ型フラッシュメモリ１０に適用する場合の構成が示される。
【００４１】
１−１．ＮＡＮＤ型フラッシュメモリ
ＮＡＮＤ型フラッシュメモリ１０は、被認証コンポーネントである。本例に係るＮＡＮＤ型フラッシュメモリ１０は、セルアレイ１１、およびセルアレイ１１の周辺領域に配置されるデータキャッシュ１２、圧縮演算回路１３、バイアスドＲＮＧ１４、出力部１５、乱数生成器１６、順序交換回路１８、ビット毎加算回路Ｃ１等を備える。
【００４２】
セルアレイ（Cell array）１１には、図示しないビット線およびワード線の交差位置にマトリックス状に複数のメモリセルが配置される。メモリセルは、半導体基板上に順次、トンネル絶縁膜、浮遊ゲート、層間絶縁膜、およびワード線と接続される制御ゲートをそれぞれ備える。ビット線方向のメモリセルの電流経路は直列接続され、セルユニットを形成する。セルユニットは、ビット線、ソース線に接続される選択トランジスタにより選択される。ワード線方向の複数のメモリセルは、データ読み出しおよびデータ書き込みの単位である１ページ（Page）を形成する。また、複数のページはデータ消去の単位であるブロック（Block）を形成する。
【００４３】
セルアレイ（Cell array）１１は、ロム領域１１−１、秘匿領域１１−２、一般領域１１−３を備える。
ロム領域（Rom area）１１−１は、データ記録が禁止され、データ読み出しが許可される領域である。本例に係るロム領域１１−１には、秘密情報XYを暗号化し、更に訂正符号が付与されたデータXYE（xe bits）が記録される。暗号化には、対称鍵暗号であるAES（Advanced Encryption Standard）などの暗号器を、暗号モードはCTR(Counter)、CBC(Cipher block chain)などを利用しても良いし、非対称暗号であるECDSA(楕円曲線暗号)やRSAなどを利用しても良い。また誤り訂正符号としては、BCH符号、Reed Solomon符号、LDPC(Low density parity check)符号などを利用してもよい。このように、本例は、いずれの暗号方法、訂正符号にも適用することが可能である。ここで、XYEとは、秘密情報XYが暗号化され、更に訂正符号が付与されたものとして表記される。また、（xe bits）とは、ビット数を表記する。
【００４４】
秘匿領域（Hidden area）１１−２は、ＮＡＮＤ型フラッシュメモリ１０の外に対してはデータ記録が禁止され、データ読出も禁止される領域である（Read Program inhibit）。本例に係る秘匿領域１１−２には、上記認証に用いるX, Yに対応するデータXYが記録される。
【００４５】
一般領域（User area）１１−３は、データ記録およびデータ読み出しのいずれも自由に可能な領域である。一般領域１１−３には、例えば、写真などの画像データや、動画データ等が記録される。
【００４６】
尚、上記におけるロム領域、秘匿領域、一般領域は、物理的構成を異ならせることで実現してもよいし、物理的構成は同一であるがＮＡＮＤ型フラッシュメモリ内の論理的制御で実現してもよい。ここで、論理的制御とは、領域ごとにＮＡＮＤ型フラッシュメモリ外からのアクセスを制御する識別子を設け、これを保持し、ＮＡＮＤ型フラッシュメモリが外部から当該領域へのアクセスを受領した際に、同識別子によってアクセス制御を行う、などの方法である。
【００４７】
また、セルアレイ（Cell array）１１を構成する個々のメモリセルは、複数ビットを記憶するものであってもよいし（MLC: Multi Level Cell）、１ビットを記憶するものであってもよい（SLC: Single Level Cell）。更に、ロム領域及び秘匿領域についてはSLCで利用する構成とし、一般領域についてはMLCで利用する構成としてもよい。この時、SLC領域とMLC領域とはセルアレイの物理的構成が異なっていてもよいし、MLCとして利用可能なメモリセルの一部のビットのみを使用して、疑似的なSLC領域として利用してもよい。
【００４８】
データキャッシュ（Data Cache）１２は、セルアレイ１１から読出したデータを一時的に記憶する。
【００４９】
バイアスドＲＮＧ（Biased RNG）１４は、所定確率ηにて1となる乱数νを生成する。尚、バイアスドＲＮＧの入力元として下記の乱数生成器を用いてもよく、その場合乱数生成器から出力される複数の乱数列に対して、論理積や論理和などの演算を行うことで所定確率ηに対応した乱数を生成することが可能である。
【００５０】
乱数生成器（RNG: Random Number Generator）１６は、認証に用いる乱数Nonce_N（a bit）を生成する。
【００５１】
順序交換回路（Permutation & Concatenation）１８は、両者が共有したXYを用いて、ホスト２０から入力される乱数Nonce_Hと、メモリ１０から入力される乱数Nonce_Nとから構成した乱数Nonce（c bits）を生成する。ここで、aはNonce_Nのビット長を意味し、bはNonce_Hのビット長を意味し、cは圧縮演算回路の1処理当たりに入力されるビット長を意味する。すなわち、順序交換回路（Permutation & Concatenation）から出力される個々の乱数Nonceは圧縮演算回路の1処理用のデータであり、1処理用にNonce_NとNonceHの総ビットを用いてもよいし、部分ごとに選択的に用いてもよい。
【００５２】
圧縮演算回路（Compress (ex. inner product)）１３は、データキャッシュ１２の出力XY（c bit each）と順序交換回路１３の出力（c bits）について内積演算などの所定の演算を行い、データCを出力する。
【００５３】
ビット毎加算回路Ｃ１は、圧縮演算回路１３の出力ビットに対して、バイアスドＲＮＧによって生成されたνを付与したz=C+νを、出力部１５へ出力する。尚、前述の通り、ビット加算とは排他的論理和を意味する。すなわち、ビット毎加算回路は、2入力データのビット毎の排他的論理和を出力する。
【００５４】
出力部１５は、ビット毎加算回路Ｃ１の結果（z=C+ν）を、コントローラ１９を介してホスト２０に出力する。
【００５５】
なお、上記セルアレイ１１以外のデータキャッシュ１２等の構成要素は、メモリコントローラ１９に配置されることも同様に可能である。
【００５６】
１−２．ホスト
本例に係るホスト（Host）２０は、訂正処理部２１、暗号の復号部２２、鍵保持部２３、データ一時記憶部２５、圧縮演算部２６、乱数生成部２７、順序交換部２９、判定部３０等を備える。
【００５７】
訂正処理部（ECC）２１は、ＮＡＮＤ型フラッシュメモリ１０のロム領域１１−１から読み出されたデータXYEに誤り訂正処理（ＥＣＣ）を行う。
【００５８】
復号部（Decrypt）２２は、読み出したデータXYEに対してエラー訂正処理を行った後、鍵保持部２３が保持する鍵KEYによりデータデータXYE復号して、XYを得る。
【００５９】
データ一時記憶部（Data cache）２５は、復号したXYを一時的に保持する。これにより、ホストデバイス２０とＮＡＮＤ型フラッシュメモリ２０は、秘密情報XYを共有できる。
【００６０】
圧縮演算部（Compress (ex inner product)）２６は、データキャッシュ２５の出力（c bit each）と順序交換回路２９の出力（c bits）とについて内積演算などの所定の演算を行い、データCを出力する。
【００６１】
乱数生成部（RNG）２７は、ホストの一時乱数Nonce_H (b bit)を生成する。
【００６２】
順序交換部（Permutation & Concatenation）２９は、両者は共有したXYを用いて、ホスト２０から入力される乱数Nonce_Hと、メモリ１０から入力される乱数Nonce_Nとから構成した乱数Nonce（c bits）を生成する。
【００６３】
判定部（Accept if Hwt(Z(+)C) ≦ t*clen）３０は、圧縮演算部２６の出力Cおよび出力部１５の出力Zについて、上記のようにハミング重みHwt(Z(+)C)を行い、ハミング重みHwt(Z(+)C)が、所定値t*clenを下回った場合、秘密情報を保持しているとみなし、認証成功と判定する。ただし、η≦t<0.5、clenはZ(+)Cのビット長とする。
【００６４】
このように、ホスト２０は、バイアスドRNG処理２７を除き、判定部３０により同様の処理によって得られたCとzとを比較することで、被認証コンポーネントであるＮＡＮＤ型フラッシュメモリ１０の正当性を確認する。
【００６５】
尚、上記構成による同様の処理を複数回行うことで最終的に正当性を確認することも可能である。例えば、本図では、Cが複数ビットである場合を例としており、比較判定方法はzとCの加算ビット系列におけるハミング重みを判定に用いている。もし、Cが単一ビットであった場合、前述のHB+プロトコルと同様に、前述の処理は複数回行う必要があり、この場合はHB+プロトコルと同様にエラー変数の生起確率に基づいてzとCの不一致率を検査すればよい。
【００６６】
１−３．変形例
上記に限られず、本例の構成は、以下のように必要に応じて、変形することが可能である。
【００６７】
圧縮処理について、図１及び図２で示した比較例１、２に係る内積計算に対応しても良いが、必ずしも内積計算でなくともよい。例えば、圧縮処理を、LFSR(Linear Feedback Shift Registor)で構成する演算器に対してXYを基とするデータとNonce_H及びNonce_Nを基とするデータを入力し、全入力後のLFSR中のレジスタ値の一部もしくは全てを圧縮結果として用いてもよい。または、LFSRとしてCRC演算器を用いてもよい。更に、圧縮処理に用いる関数としてハッシュ関数を用いてもよい。ハッシュ関数は暗号器に基づいていてもよく、基づいていなくてもよい。いずれの演算方法を用いても本実施例にて提案している方法を適用することが可能である。また安全性の根拠となっているLPN問題に属していることに変わりはない。尚、ここで圧縮処理とは可逆圧縮であるか、非可逆圧縮であるか、は問わず、少なくとも入力されたデータよりも小さく、かつ入力データに依存するデータを出力する処理を意味する。
【００６８】
また、圧縮計算部に対してNonce_HとNonceNを元に生成したNonceを送出する処理について説明する。NonceはNonce_HとNonceNを所定の順序によって結合し送出されるデータであり、結合・送出方法としては、単純な順送りデータ結合・送出、互いのデータを交互に挿入したインターリーブデータ結合・送出などの方法であってよく、また前述の方法により複数回データを送出しても良い。いずれにせよ、Nonceは、Nonce_N及びNonceHの少なくとも一部のデータより生成されたデータであり、cビット長のデータとなる。ここで、Nonce_Nのデータ長はaとおき、Nonce_Hのデータ長はbとおき、両者の合計データ長をdとおく。仮にc=dであり、かつデータを複数回送出しない場合、圧縮計算部からの出力は1ビットとなる。仮にc=dであり、かつデータを複数回送出する場合、圧縮計算部からの出力は1ビットが複数回出力される。仮にc<dであり、かつデータを複数回送出する場合、圧縮計算部からの出力は1ビットが複数回出力される。
【００６９】
一方、Nonceとの圧縮を計算するXYにおいても、XY中のデータがcビット単位で圧縮計算部へと送出される。ここで、XYデータのビットサイズxはcと等しいもしくは整数倍である。cと等しい場合、圧縮計算部の出力は1ビットとなる。cの整数倍である場合、圧縮計算部の出力は1ビットが複数回となる。代表的な組み合わせについて記すと、
・c=d=xの場合、圧縮計算部の出力は1ビット
・c=d<xの場合、圧縮計算部の出力は1ビットが複数回
・c<d, c<xの場合、圧縮計算部の出力は1ビットが複数回
となる。尚、前記は圧縮計算部が2入力を1ビットに圧縮する場合の例であり、圧縮計算部が2入力を複数ビットに圧縮する場合は、1回あたりの出力値自体も複数ビットとなる。
【００７０】
＜２．認証フロー＞
次に、図４に沿って、図３に示した構成におけるメモリシステムの認証フローについて説明する。
【００７１】
認証開始（Start）すると、ステップＳ１１の際、ホストデバイス１０は、ＮＡＮＤ型フラッシュメモリ１０へXYEの読出し命令（Read XYE）を送出する。
【００７２】
続いて、ステップＳ１２の際、ＮＡＮＤ型フラッシュメモリ１０は、上記読出し命令に従って、XYEをセルアレイ１１−１よりロード（load XYE）し、これをホストデバイス２０へと送出する。
【００７３】
続いて、ステップＳ１３の際、ホストデバイス２０は、受領したXYEに対して、上記復号処理を行い、XYを得る（Retrieve XY）。
【００７４】
続いて、ステップＳ１４の際、ホストデバイス２０は、認証要求（Request authentication）を、ＮＡＮＤ型フラッシュメモリ１０へ送出する。ここで、認証要求にはNonce_Hを含んでいてもよい。
【００７５】
続いて、ステップＳ１５の際、ＮＡＮＤ型フラッシュメモリ１０は、Nonce_Hを受領し、XYをロードする（Load XY (if required)）。
【００７６】
続いて、ステップＳ１６の際、ＮＡＮＤ型フラッシュメモリ１０は、Nonce_Nおよびνを生成する（Create Nonce_N, Create ν）。
【００７７】
続いて、ステップＳ１７の際、ＮＡＮＤ型フラッシュメモリ１０は、上記のように、生成されたνを付与し、Zを計算する。ＮＡＮＤ型フラッシュメモリ１０は、Nonce_N及びZをホスト２０へと送出する。
【００７８】
続いて、ステップＳ１８の際、ホスト２０は、それらデータNonce_N及びZを受領後、内積演算などの所定の演算を行い、データCを計算する。
【００７９】
続いて、ステップＳ１９の際、ホスト２０は、ZとCのビット毎XOR値の系列に対してハミング重みHwt(Z(+)C)を計算し、これが所定値t*clenを下回るか否かの判定処理（Check Hwt(Z(+)C) ≦ t*clen）を行う。ここで、上記のように、tはＮＡＮＤフラッシュメモリ１０がZの算出時に用いたエラービットもしくはエラーベクトルνにおけるエラー付与確率（もしくはデータ中の1の出現確率）ηに基づく値であり、η≦t<0.5であるとする。またclenはCのビット長とする。
【００８０】
続いて、ステップＳ２０の際、上記ステップＳＴ１９の判定結果が所定を下回らなかった場合（fail）、ホスト２０は、失敗としてこの動作を停止する。
【００８１】
続いて、ステップＳ２１の際、上記ステップＳＴ１９の判定結果が所定を下回った場合（Success）、ホスト２０は、あらかじめ定められたラウンド数に達しているか否かを判定する（Enough round ?）。ここで、ラウンド数とは前記認証要求処理から前記判定処理までの一連の処理を指す。ラウンド数に達していない場合（No）には、再度認証要求処理（Ｓ１４〜）を繰り返す。
【００８２】
続いて、ステップＳ２２の際、ラウンド数に達している場合（Yes）には、認証が成功したとみなし、ホストデバイス１０は、必要に応じて、前記XYに基づきMedia IDを算出する処理を行う。Media IDの算出処理、Media IDの利用方法（Ｓ２３以下）については後述する。
【００８３】
以上の動作により、第１実施形態に係る認証フローを終了する（End）。
【００８４】
尚、Nonce_N、Nonce_H、νのパラメータは、ラウンド毎に異なるものを用いる必要がある。また、ＮＡＮＤ型フラッシュメモリ１０が認証要求を受領した際、前認証要求時のXYがData Cacheにロードされたままであった場合、セルアレイからのXYのロードを省略し、Data cache内の値を用いてもよい。また、ステップＳ１７の後、Data cache内のXYを消去してもよい。特に、ＮＡＮＤ型フラッシュメモリ１０がData cacheへのアクセス機能を外部に提供している場合、認証に要するデータZを計算した段階でData cache内の秘密情報XYを消去することはセキュリティー上有用である。
【００８５】
＜３．作用効果＞
第１実施形態に係る構成およびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも下記（１）の効果が得られる。
【００８６】
（１）認証コンポーネント、被認証コンポーネント間で、異なる秘密情報XYの秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証できる。
【００８７】
本例に係るＮＡＮＤ型フラッシュメモリ１０は、秘密情報XYを記録禁止・読出禁止領域である秘匿領域１１−２に保持し、同秘密情報XYを暗号化し更に訂正符号を付与したXYEを記録禁止・読出許可領域であるロム領域１１−１に保持する。さらに、ホスト２０は、XYEを読み出してエラー訂正処理２１、復号化処理２２をする機能、および復号に用いる鍵２３により、ＮＡＮＤ型フラッシュメモリ１０およびホスト２０の両者で、秘密情報XYを共有することができる。そのため、認証・被認証コンポーネントは、共有した秘密情報XYで、認証を行うことができる（ＳＴ１１〜ＳＴ２３）。
【００８８】
また、ＮＡＮＤ型フラッシュメモリ１０とホストデバイス２０は、各々一時乱数を生成するＲＮＧ１６，１７、順序交換部１８，２９、圧縮計算部１３，２６、一時乱数のビット毎加算部Ｃ１，２６、送出部１５を備える。また、ＮＡＮＤ型フラッシュメモリ１０は、バイアスドＲＮＧ１４を備える。ホスト２０は、ＮＡＮＤ型フラッシュメモリ２０から送出されたZとホストデバイス内部で計算したCとを比較し認証を行う判定部３０を備える。
【００８９】
このように、第１実施形態では、秘密情報XYを記録禁止・読出禁止領域である秘匿領域１１−２に保持し、これを用いてデータZを生成するため、秘匿性を保持できる。さらに、秘密情報XYを暗号化し更に訂正符号を付与したXYEを記録禁止・読出許可領域であるロム領域１１−１に保持する。ホスト２０は、ここから読み出したXYEに対して、エラー訂正処理２１、および鍵２３を用いた復号化処理２２を行うことで、XYを共有する。そのため、認証・被認証コンポーネント間で、異なるXYを秘密状態を維持したまま共有できる。
【００９０】
従って、第１実施形態に係る構成およびその認証方法によれば、認証・被認証コンポーネント間で、異なるXYを秘密状態を維持したまま共有でき、共有した秘密情報に基づく軽量な計算によって認証できる点で有利である。
【００９１】
［第２実施形態］
次に、図５および図６を用い、第２実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。なお、以下の説明において、上記第１実施形態と重複する部分の説明については、省略する。
【００９２】
＜構成例（メモリシステム）＞
図５を用い、第２実施形態に係る構成例について説明する。
図示するように、第２実施形態に係る構成例では、ＮＡＮＤ型フラッシュメモリ１０が、ロム領域１１−１，秘匿領域１１−２に、それぞれ複数のXYEおよび複数のXYを記憶する点で、上記第１実施形態と相違する。ここで、iとjが異なる場合、XY[i]≠XY[j]、XYE[i]≠XYE[j]である。
【００９３】
このように、複数のXYEおよび複数のXYの組を保持することで、秘密情報X及びY露見時の秘密情報の更新手段を提供することができる。仮にある1つのXYとXYEの組が中間者攻撃その他によって露見し、露見したXY及びXYEを流用した偽造デバイスが製造された場合でも、本例では、ホスト２０が保持するKEY[1]２３を更新（例えば、KEY[1]=> 更新KEY[2]）することができる。このように、露見したXY及びXYE以外の組を利用することで、偽造デバイスの排除が可能となる。各XY[i]の暗号化に用いられるKEYはiが異なる場合、異なるものである方が望ましい。
【００９４】
その他は、上記第１実施形態と実質的に同様であるため、詳細な説明を省略する。
【００９５】
＜認証フロー＞
次に、図６に沿って、第２実施形態に係る認証動作について説明する。
第２実施形態では、ＮＡＮＤ型フラッシュメモリ１０内には複数のXY及び複数のXYEが記録されているため、ホスト２０がいずれのXYを用いるかを選択することで、認証を行う。
【００９６】
そのため、第２実施形態では、ステップＳ１４の際に、ホスト２０が、認証を要求する（Request authentication）場合、いずれのXYを用いるかを指定するパラメータiを、乱数Nonce_Hとともに、ＮＡＮＤ型フラッシュメモリ１０に送出する点で、相違する。
【００９７】
その他は、上記第１実施形態と実質的に同様であるため、詳細な説明を省略する。
【００９８】
＜作用効果＞
第２実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【００９９】
さらに、第２実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、ロム領域１１−１、秘匿領域１１−２に、それぞれ複数のXYEおよび複数のXYを記憶する点で、上記第１実施形態と相違する。
【０１００】
このように、複数のXYEおよび複数のXYの組を保持することで、秘密情報X及びY露見時の秘密情報の更新手段を提供することができる。仮にある1つのXYとXYEの組が中間者攻撃その他によって露見し、露見したXY及びXYEを流用した偽造デバイスが製造された場合でも、本例では、ホスト２０が保持するKEY[1]２３を更新（例えば、KEY[1]=> 更新KEY[2]）することができる。
【０１０１】
そのため、第２実施形態に係る認証フローでは、ステップＳ１４の際に、ホスト２０が、認証を要求する（Request authentication）場合、いずれのXYを用いるかを指定するパラメータiを、乱数Nonce_Hとともに、ＮＡＮＤ型フラッシュメモリ１０に送出する。
【０１０２】
このように、第２実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、複数のXY及び複数のXYEを有し、ホストデバイスからの命令によりXYEを選択的に送出する機能を有し、ホストデバイスからの命令により認証に用いるXYを選択的に設定する。また、ホストデバイスは、自身が保持する鍵に対応するXYEを選択的に読み出す機能を有し、それを復号する機能を有し、また自身が保持する鍵を所定の条件下で更新する機能を有する。
【０１０３】
その結果、露見したXY及びXYE以外の組を利用することで、偽造デバイスの排除が可能となる点で有利である。
【０１０４】
［第３実施形態］
次に、図７乃至図９を用い、第３実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１０５】
＜構成例（メモリシステム）＞
図７を用い、第３実施形態に係る構成例について説明する。
図示するように、本例に係るＮＡＮＤ型フラッシュメモリ１０は、ロム領域１１−１Ｂ、秘匿領域１１−２Ｂに、複数のXYsubEおよび複数のXYsubをそれぞれ記憶する点で、上記第２実施形態と相違する。ここで、iとjが異なる場合、XYsub[i]≠XYsub[j]、XYsubE[i]≠XYsubE[j]である。XYsubEはXYsubを暗号化した後、訂正符号を付与したデータである。
【０１０６】
XYsubは、XYと同様に記録禁止・読出禁止領域（秘匿領域）１１−２Ｂに記録され、XYsubEは、XYEと同様に記録禁止・読出許可領域（ロム領域）１１−１Ｂに記録される。
【０１０７】
ここで、XYmainのデータサイズは、XYsubよりも大きい（データサイズ：XYmain ＞ XYsub）。また、XYmainとXYsubから構成されるデータが、前述の秘密情報XYに対応する。
【０１０８】
このように、第３実施形態では、XYの組に加え、XYsub[i], XYsubE[i]の組を更に備えるため、秘密情報X及びYを効率的に記録することができる点で有利である。詳細については、後述する。
【０１０９】
さらに、ＮＡＮＤ型フラッシュメモリ１０は、上記XYsubを格納するためのデータキャッシュ１２Ｂ、およびXYmainと XYsubとをビット毎加算するためのビット毎加算部Ｃ２を備える。ビット毎加算部Ｃ２の出力値が、前述の認証に用いられるXY値に相当する。ここで、XYmainとXYsubのビット長が異なることから、ビット加算Ｃ２においては、XYsubの繰り返しデータが適用される。
【０１１０】
例えば、本図にあるように所定の演算としては、ビット加算が考えられ、XYmainのデータサイズがXYsubのデータサイズの整数倍であった場合、XYmainのデータを保持するData cacheからはXYmainが順送りに送出され、XYsubのデータを保持するData cacheからはXYsubが順送りかつ繰り返し送出される構成が考えられる。XYsubを保持するData cacheはリングバッファと考えてもよい。また、ビット毎加算以外にもXYmainとXYsubの結合値をXYとしてもよいし、XYmainとXYsubのインターリーブ結合値をXYとしてもよいし、XYmainとXYsubをLFSRに入力しLFSRの所定レジスタの値をXYとしてもよい。すなわち、本実施例ではビット毎加算部としているが、2入力から構成したデータをXYとして用いるいずれの演算方法も適用可能である。
【０１１１】
同様に、ホスト２０は、読み出したXYsubEに対応するための、訂正処理部２１Ｂ、暗号の復号部２２Ｂ、鍵保持部２３Ｂ、データ記憶部２５Ｂ、加算部Ｃ３を更に備える。ホスト２０は、上記構成により、同様に、エラー訂正処理を行い、対応するKEY_XYsubにより復号することでXYsubを得る。これにより、ホストデバイスとＮＡＮＤ型フラッシュメモリ間で、秘密情報XYmain及びXYsubを共有できる。ここで、本図においてはKEY_XYmainとKEY_XYsubは異なるオブジェクトとして描かれているが、実際には同じ鍵であっても良い。また、各XYsub[i]の暗号化に用いられるKEY_XYsubはiが異なる場合、異なるものである方が望ましい。さらに、ホストデバイス２０、メモリ１０は、XYmainとXYsubを用いて所定の演算を行ったXY値により、認証処理を行う。
【０１１２】
＜認証フロー＞
次に、図８に沿って、第３実施形態に係る認証動作について説明する。
第３実施形態では、ＮＡＮＤ型フラッシュメモリ１０内にはXYmainに加えてXYsubが、またそれらを暗号化したXYmainE及びXYsubEが記録される。
【０１１３】
そのため、図示するように、対応するステップＳ１３において、ホスト１０は、XYmainE , XYsubEを更に読み出して復号をし、秘密情報XYmain，XYsubに基づく秘密情報XYを生成する（Create XY）。続いて、ホスト２０は、秘密情報XYmainとXYsubから導出された情報を用いて、同様の認証を行う。
【０１１４】
また、ＮＡＮＤ型フラッシュメモリ１０側においても同様に、ステップＳ１５において、読み出した秘密情報XYmain，XYsubに基づいて秘密情報XYを生成する（Create XY）点で、上記第２実施形態と相違する。
【０１１５】
＜作用効果＞
第３実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。さらに、第３実施形態では、（２）の効果が得られる。
【０１１６】
（２）秘密情報X,Yを効率的に記録することができ、記録時間を高速化できる点で有利である。
【０１１７】
第３実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、複数のXYsub及び複数のXYsubEを有し、ホスト２０からの命令によりXYsubEを選択的に送出し、ホスト２０からの命令により認証に用いるXYsubを選択的に設定し、選択されたXYsubとXYを所定の演算で導出した値により認証を行う。
【０１１８】
また、ホストデバイスは、自身が保持する鍵２３Ｂに対応するXYsubEを選択的に読み出し、それを復号する機能２２Ｂを有し、また自身が保持する鍵２３Ｂを所定の条件下で更新する機能を更に有し、選択したXYsubとXYmainを所定の演算で導出した値により認証３０を行う。
【０１１９】
このように、XYmainの組に加え、XYsub[i], XYsubE[i]の組を更に備えるため、秘密情報X及びYを効率的に記録することができる点で有利である。
【０１２０】
より具体的には、例えば、図９のように示される。図示するように、ＮＡＮＤ型フラッシュメモリの製造工程において、XYmain、XYmainE、XYsub、XYsubEの複数の組は、ＸＹ発生装置（XY GEN）により生成され、書き込み装置（Writer）により、複数のＮＡＮＤ型フラッシュメモリ（ここでは、Chip1〜Chip4）にデータ書き込みがされる。
【０１２１】
ここで、XYmain及びXYmainEのデータは、複数のチップChip1〜Chip4から構成される集団内（例えばロット）で同一のデータで良い。一方、XYsub及びXYsubEは、チップChip1〜Chip4毎に異なるデータ（XYsub1〜XYsub4及びXYsubE1〜XYsubE4）とする必要がある。
【０１２２】
このように、第３実施形態では、データ書き込み動作において、データ量の多いXYmain及びXYmainEを複数のチップChip1〜Chip4で共通化することにより、メモリへのデータ書き込みプロセスを最適化でき、効率的に記録することが可能となる。
【０１２３】
仮に、XYmain及びXYmainEをハードワイヤードで構成する場合、実際に記録するデータは、データサイズが小さいXYsub及びXYsubEとなり記録時間を短縮できる。また、仮にXYmain及びXYmainEをセル上に記録する場合において、集団内で同一であることにより、ＮＡＮＤ型フラッシュメモリへのデータ記録装置に対して記録データを転送する時間を短縮できる。先に述べたように、記録時間の増加は、コストの増加となるため、第３実施形態によれば、製造コストを低減することができるというメリットも大きい。
【０１２４】
［第４実施形態（多重記録される一例）］
次に、図１０および図１１を用い、第４実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１２５】
＜構成例（メモリシステム）＞
図１０を用い、第４実施形態に係る構成例について説明する。
第４実施形態では、メモリ１０の秘匿領域１１−２に、複数のXY[i]を多重に複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有する点で、上記第２実施形態と相違する。
【０１２６】
すなわち、第２実施形態におけるXY[i]を複製したデータは、図１０において、XY[i,1],XY[i,2],...,XY[i,n]によって示され、1≦i≦mに対しXY[i,1]=XY[i,2]=…=XY[i,n]である。また、1≦j≦nに対しXY[1,j]≠XY[2,j]≠…≠XY[m,j]である。
【０１２７】
ここで、XYEがECCが付与されている一方で、XYにはECCが付与されていないため、ＮＡＮＤ型フラッシュメモリ内でセルから読み出したデータにエラーが含まれている場合、ＮＡＮＤ型フラッシュメモリが認証に用いるXYの完全性が失われることも考えられる。しかしながら、本例のように、複数のXY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有することにより、検査・選択部１２−０により、前記エラーが含まれているかどうかを複製データ間でのデータ比較により検出することができる。
【０１２８】
そのため、本例のメモリは、XY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃに対応するための検査・選択部（Check sum & select）１２−０を更に備える点で、第２実施形態と相違する。
【０１２９】
図１０において、セル１１−２からロードされた少なくとも2つ以上のXYのデータセットは所定の上記同様の方法により比較を行うことでエラーが含まれているか否かを検査する。仮にエラーが含まれていた場合もしくはエラーが除去できない場合、異なる2つ以上のXYのデータセットを再度ロードし、同様に検査する。これをエラーが含まれていないもしくは除去できるデータセットが見つかるまで繰り返し、同データセットが見つかった場合それを認証に用いる。上記所定の方法の例としては、2つのXYをロードし、ビット毎にXOR値を算出した後、XOR値がすべて0であるかどうか、により検査する方法が考えられる。また、3つ以上のXYをロードし、多数決判定によってビット毎にエラーを除去したXYを得る方法も考えられる。また、本図においては、XYの複製データはすべて同一データとしているが、複製データのうち奇数番号のデータと偶数番号のデータの極性が反転しているように相補関係にあるデータを構成して事前に記録しておく方法も考えられる。この場合、前記相補関係にある2つのXYをロードし、ビット毎にXOR値を算出した後、XOR値がすべて1であるかどうか、により検査することが可能である。
【０１３０】
＜認証フロー＞
次に、図１１に沿って、第４実施形態に係る認証動作について説明する。
図示するように、第４実施形態では、ＮＡＮＤ型フラッシュメモリ１０の秘匿領域１１−２内に、複数のXYが多重記録される。
【０１３１】
そのため、ステップＳ１５の際、ＮＡＮＤ型フラッシュメモリ１０は、少なくとも2つ以上のXYを読み出し、比較し、エラーを含んでいないXYを用いて認証を行う（Load / compare XYs）。
【０１３２】
＜作用効果＞
第４実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【０１３３】
さらに、第４実施形態によれば、メモリ１０の秘匿領域１１−２に、複数のXY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有する。
【０１３４】
ここで、XYEがECCが付与されている一方で、XYにはECCが付与されていないため、ＮＡＮＤ型フラッシュメモリ内でセルから読み出したデータにエラーが含まれている場合、ＮＡＮＤ型フラッシュメモリが認証に用いるXYの完全性が失われることも考えられる。
【０１３５】
しかしながら、第４実施形態によれば、複数のXY[i]を複製した情報１１−２Ａ，１１−２Ｂ，１１−２Ｃを更に有することにより、検査・選択部１２−０により、前記エラーが含まれているかどうかを複製データ間でのデータ比較により検出することができる。結果、メモリ１０内でセルから読み出したデータにエラーが含まれている場合であっても、メモリ１０が認証に用いるXYの完全性が失われることを防止できる点で更に有利である。
【０１３６】
［第５実施形態］
次に、図１２および図１３を用い、第５実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１３７】
＜構成例（メモリシステム）＞
図１２を用い、第５実施形態に係る構成例について説明する。第５実施形態に係る構成例は、上記第３、第４実施形態を組み合わせたものに関する一例である。
【０１３８】
図示するように、第５実施形態に係るＮＡＮＤ型フラッシュメモリ１０は、秘匿領域１１−２に、XYsub及びXYsubEについても複製データXYsub[i,j]及びXYsubE[i,j]を記録する点で、上記第４実施形態と相違する。
【０１３９】
また、上記に対応するための検査・選択部１２−０Ｂおよびデータキャッシュ１２Ｂを更に備える。
【０１４０】
＜認証フロー＞
次に、図１３に沿って、第５実施形態に係る認証動作について説明する。
第５実施形態では、ＮＡＮＤ型フラッシュメモリ１０内に、更にXYsubも多重記録される（XYsub[i,j]及びXYsubE[i,j]）。
【０１４１】
そのため、ステップＳ１５の際、ＮＡＮＤ型フラッシュメモリ１０は、更に少なくとも2つ以上のXYsubを読み出し、比較し、エラーを含んでいないXYsubを用いて認証を行う（Load / compare XYs and XYsubs）。
【０１４２】
＜作用効果＞
第５実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【０１４３】
さらに、第５実施形態によれば、ＮＡＮＤ型フラッシュメモリ１０は、秘匿領域１１−２に、XYsub及びXYsubEについても複製データXYsub[i,j]及びXYsubE[i,j]を記録する。
【０１４４】
必要に応じて、本例のような構成および方法を適用することが可能である。
【０１４５】
［第６実施形態］
次に、図１４および図１５を用い、第６実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１４６】
＜構成例（メモリシステム）＞
図１４を用い、第６実施形態に係る構成例について説明する。
第６実施形態でも同様に、ＮＡＮＤ型フラッシュメモリ１０が、更に複数のXY[i]を複製した情報を有する。すなわち、先の第２実施形態におけるXY[i]を複製したデータは本図においてXY[i,1],XY[i,2],...,XY[i,n]によって示され、1≦i≦mに対しXY[i,1]=XY[i,2]=…=XY[i,n]である。また、1≦j≦nに対しXY[1,j]≠XY[2,j]≠…≠XY[m,j]である。
【０１４７】
ここで、XYデータを複製することは第４実施形態と同様であるが、本第６実施形態においては、ＮＡＮＤ型フラッシュメモリ１０側では複製データの比較処理を行わず、その代わりにホスト２０で比較処理を行う点で、相違する。そのため、本例では、ホスト２０が、多数決判定部（Majority check）３０を備える点で、相違する。
【０１４８】
すなわち、ＮＡＮＤ型フラッシュメモリ１０は、ホスト２０により指定されたiに応じ、XY[i,1],XY[i,2],...,XY[i,n]のうち少なくとも2つ以上をロードし、各々のXYに対して前述の認証処理を行う。ここで、各々のXYに対しては同一のNonce_N及び同一のNonce_Hを利用し、またバイアスドRNGによって生成されたνについても同一のものを適用する。
【０１４９】
ＮＡＮＤ型フラッシュメモリ１０の送信部１５は、複数のXYに対して、他のパラメータが同一な条件で複数のz(z[i,1],z[i,2],…,z[i,n])を計算し、ホスト２０に送出する。
【０１５０】
ホストデバイスは、複数のz(z[i,1],z[i,2],…,z[i,n])を受領した後、多数決判定部３１により、多数決判定を行い、単一のzを得る。ここで、各zが複数のビット要素で構成されていた場合、圧縮計算部の出力が複数ビットからなる場合、前記多数決判定はビット要素毎に行う。
【０１５１】
ホストデバイスは、多数決判定によってエラーを除去したZを得たのち、前述と同様の判定処理３０を行うことで、ＮＡＮＤ型フラッシュメモリ１０を認証する。
【０１５２】
＜認証フロー＞
次に、図１５に沿って、第６実施形態に係る認証動作について説明する。
第６実施形態では、ＮＡＮＤ型フラッシュメモリ１０内に多重記録されているXYを用いて、ＮＡＮＤ型フラッシュメモリが複数のZを計算し、送出し、ホストデバイスは複数のZを多数決処理することで単一のZを得て、認証を行う。
【０１５３】
そのため、ステップＳ１７の際、ＮＡＮＤ型フラッシュメモリ１０は、計算した複数のZ,jをホスト２０に送信する。
【０１５４】
続いて、ステップＳ１８の際、ホスト２０は、複数のZの多数決判定部（Majority check）を更に行う点で、相違する。
【０１５５】
＜作用効果＞
第６実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも上記（１）の効果が得られる。
【０１５６】
さらに、第６実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、更に複数のXY[i]を複製した情報を有する。さらに、ホスト２０が、多数決判定部（Majority check）３０を備える。
【０１５７】
そのため、計算資源に制約のあるＮＡＮＤ型フラッシュメモリ１０での比較処理を軽減でき、計算資源に余裕のあるホスト２０に比較処理（多数決処理）３０を依頼することができる。結果、ＮＡＮＤ型フラッシュメモリ１０へのコスト増加を抑制することができ、エラーの除去が可能となる点で有利である。
【０１５８】
［第７実施形態］
次に、図１６および図１７を用い、第７実施形態に係る認証・被認証コンポーネントおよびその認証方法について説明する。
【０１５９】
＜構成例（メモリシステム）＞
図１６を用い、第７実施形態に係る構成例について説明する。第７実施形態は、上記第３、第６実施形態を組み合わせたものの一例に関する。
【０１６０】
図示するように、ＮＡＮＤ型フラッシュメモリ１０は、XYsub及びXYsubEについても複製データ１１−２Ｂ，１１−１Ｂを更に記録する。上記第６実施形態と同様に、複数のXYに対する認証用データzを算出して算出部１５でホスト２０に送信し、ホスト２０側で多数決処理３０を行う。
【０１６１】
＜認証フロー＞
次に、図１７に沿って、第７実施形態に係る認証動作について説明する。
第７実施形態では、ＮＡＮＤ型フラッシュメモリ１０内に、多重記録されているXYmain及びXYsubを用いて、ＮＡＮＤ型フラッシュメモリが複数のZを計算し、送出し、ホストデバイスは複数のZを多数決処理することで単一のZを得て、認証を行う。
【０１６２】
そのため、ステップＳ１１の際、ホスト２０は、多重記録されているXYmain及びXYsubの読み出し要求（Read XYmainE and XYsubE）を行う。
【０１６３】
続いて、ステップＳ１２の際、ＮＡＮＤ型フラッシュメモリ１０は、多重記録されているXYmain及びXYsubを読み出し（Load XYmainE and XYsubE）、ホスト２０に送信（XYmainE and XYsubE）する。
【０１６４】
＜作用効果＞
第７実施形態に係る認証・被認証コンポーネントおよびその認証方法によれば、上記（Ｉ）〜（ＩＶ）を改善でき、少なくとも下記（１）の効果が得られる。
【０１６５】
さらに、第７実施形態では、ＮＡＮＤ型フラッシュメモリ１０が、XYsub及びXYsubEについても複製データ１１−２Ｂ，１１−１Ｂを更に記録する。上記第６実施形態と同様に、複数のXYに対する認証用データzを算出して算出部１５でホスト２０に送信し、ホスト２０側で多数決処理３０を行う。
【０１６６】
このように、必要に応じ、本例を適用することが可能である。
【０１６７】
［第８実施形態（Media ID retrieve process）］
次に、図１８乃至図２１を用い、第８実施形態について説明する。第８の実施形態は、上記ステップＳ２２において、メディアＩＤ（Media ID）を算出する種々の処理（Media ID retrieve process）に関するものである。
【０１６８】
ID retrieve process（１）
ID retrieve process（１）は、図１８のように示される。図示するように、この例（１）では、ステップＲＳ１の際、上記の認証に用いられたXYmain及びXYsubに対して、各々一方向性関数処理（One-way function）が行われる。その結果が、Media IDとして扱われる。
【０１６９】
ここで、一方向性関数処理としては、例えば、SHA-1、SHA-256、AEG-Hなどの暗号に基づく一方向性演算を用いることが可能である。
【０１７０】
ID retrieve process（２）
ID retrieve process（２）は、図１９のように示される。図示するように、この例（２）では、ステップＲＳ１，ＲＳ２の際、上記認証に用いられたXYmain及びXYsubは、前述の認証処理においてXYmainE及びXYsubEの復号に用いられたKEY_XYmainとKEY_XYsubのいずれか一方に相当するKEY_XYを用いて、更に復号処理（Decode）が行われる。
【０１７１】
続いて、ステップＲＳ３の際、同様の一方向性関数処理（One-way function）が行われ、その結果がMedia IDとして扱われる。
【０１７２】
ID retrieve process（３）
ID retrieve process（３）は、図２０のように示される。図示するように、この例（３）では、ステップＲＳ１，ＲＳ２の際、上記の認証に用いられたXYmain及びXYsubは、上記認証処理においてXYmainE及びXYsubEの復号に用いられたKEY_XYmain及びKEY_XYsubを用いて、更に復号処理（Decode）が行われる。
【０１７３】
続いて、ステップＲＳ３の際、同様の一方向性関数処理（One-way function）が行われ、その結果がMedia IDとして扱われる。
【０１７４】
ID retrieve process（４）
ID retrieve process（４）は、図２１のように示される。図示するように、この例（４）では、ステップＲＳ１，ＲＳ２の際、ステップＲＳ１，ＲＳ２の際、上記の認証に用いられたXYmain及びXYsubは、上記認証処理においてXYmainE及びXYsubEの復号に用いられたKEY_XYmain及びKEY_XYsub と異なるKEY_XYmain２及びKEY_XYsub２を用いて、更に復号処理（Decode）が行われる。ここで、KEY_XYmain２及びKEY_XYsub２は同一の値であってもよい。
【０１７５】
続いて、ステップＲＳ３の際、同様の一方向性関数処理（One-way function）が行われ、その結果がMedia IDとして扱われる。
【０１７６】
［第９実施形態（Media ID binding process）］
次に、図２２乃至図２３を用い、第９実施形態について説明する。第９実施形態は、Media IDの利用方法（Media ID binding process）に関するものである。
ここで、例えば、商用動画コンテンツ等を物理媒体に記録し、再生する場合、同物理媒体に固有な識別情報をコンテンツ記録時の暗号処理に用いてコンテンツを同物理媒体にバインドする方法がとられる。
【０１７７】
コンテンツ再生時は、前記識別情報に基づく復号処理もしくは検査処理などを行い、再生された識別情報とコンテンツ記録時の暗号処理に用いられた識別情報が一致しない場合、コンテンツの再生を停止するなどの方法がとられる。ここで物理媒体としては、例えば、SDカードなどのリムーバブルメディアの場合や、携帯電話などに内蔵されているエンベデッドメモリなどが考えられる。
【０１７８】
いずれにおいても、前記方法の目的は、あるメディアに記録された暗号処理済みコンテンツを、別のメディアへと不正複製された場合、不正複製コンテンツの再生を停止させることである。そのための情報として、メディア毎に異なる上記識別情報（メディアＩＤ）を利用している。
【０１７９】
ID binding process（１）
ID binding process（１）は、図２２のように示される。図示するように、この例（１）では、ＭＡＣ（Message Authentication Code）生成処理を行い、これを不正複製の防止に用いる。
【０１８０】
具体的には、ステップＢＰ１の際、前記識別情報としてMedia IDを用いる方法例として、コンテンツ暗号化に用いられるContent Keyにより、Media ID及びその他の情報に対し、ＭＡＣ生成処理を行う。
【０１８１】
続いて、コンテンツをメディアに記録する装置においては、同MACを生成し、これをメディアに記録しておく。コンテンツをメディアから再生する装置においては、記録されているMACをMedia ID、Content Keyにより検査し、正当性が確認された場合はコンテンツを再生し、正当性が確認されない場合はコンテンツの再生を停止するなどの方法を適用することが可能である。
【０１８２】
ID binding process（２）
ID binding process（２）は、図２３のように示される。図示するように、この例（１）では、コンテンツ暗号化に用いられるContent Keyを生成するための情報として、Media IDを利用する。
【０１８３】
ステップＢＰ１の際、コンテンツをメディアに記録する装置においては、Content Key Precursorと、Media ID及びContent Key Precursorを一方向性処理（One-way function）する。
【０１８４】
メディアに記録する装置においては、処理されたContent Keyによって暗号化されたコンテンツを記録しておく。
【０１８５】
コンテンツをメディアから再生する装置においては、記録されているContent Key PrecursorとMedia IDを同様の一方向性処理をすることでContent Keyを得て、コンテンツの復号と再生を行う。ここで、Media IDが一致しない場合、すなわち記録されているデータが異なるメディアに不正複製された場合など、には導出したContent Keyとコンテンツ暗号化に用いられているContent Keyが一致しないため、コンテンツの復号に失敗し、再生は停止される。
【０１８６】
［第１０実施形態（メモリ、記憶・再生ホストの一例）］
次に、図２４を用い、第１０実施形態について説明する。第１０実施形態は、上記実施形態の構成を組み合わせたメモリカード（inc. NAND chip）１０，記録ホスト（Recoding Device）２０Ａ，再生ホスト（Playback Device）２０Ｂのシステムにおいて、上記認証を行い、上記メディアＩＤを用い、ホスト２０Ｂにてコンテンツを再生する一例に関するものである。
【０１８７】
記録ホスト（Recoding Device）２０Ａがコンテンツをメモリカード（inc. NAND chip）１０に記録するに際し、まずメモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（１）により生成したMACをメモリカード（inc. NAND chip）１０に記録する。合わせて、ID binding process（１）において用いたContent Keyにより暗号化したコンテンツ（Encrypted Content）も記録する。更に、Content Key自身も安全な形で記録する。ここで安全な形とは、メモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で認証が成立した後にアクセスが可能となるモリカード（inc. NAND chip）１０内の記録エリアであってもよい。また、ここでいう認証は本願において記載されている認証方法でもよいし、メモリカード（inc. NAND chip）１０が持つ別の認証機能によって実現してもよい。また、安全な形の別な例としては、メモリカード（inc. NAND chip）１０もしくは記録ホスト（Recoding Device）２０Ａが有する鍵によって暗号化した形であってもよい。
【０１８８】
再生ホスト（Playback Device）２０Ｂがコンテンツをメモリカード（inc. NAND chip）１０から読出し、再生するに際し、まずメモリカード（inc. NAND chip）１０と再生ホスト（Playback Device）２０Ｂの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（１）に対応する処理により、メモリカード（inc. NAND chip）１０に記録されているMACを検証する。その後、Content Keyをメモリカード（inc. NAND chip）１０より読出し、暗号化したコンテンツ（Encrypted Content）の復号を行うことでコンテンツを再生する。
【０１８９】
［第１１実施形態（メモリ、記憶・再生ホストのその他の一例）］
次に、図２５を用い、第１１実施形態について説明する。第１１実施形態は、上記実施形態の構成を組み合わせたメモリカード（inc. NAND chip）１０、記録ホスト（Recoding Device）２０Ａ、再生ホスト（Playback Device）２０Ｂのシステムにおいて、上記認証を行い、上記メディアＩＤを用い、ホスト２０Ｂにてコンテンツを再生する一例に関するものである。
【０１９０】
記録ホスト（Recoding Device）２０Ａがコンテンツをメモリカード（inc. NAND chip）１０に記録するに際し、まずメモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（１）により生成したContent Keyをメモリカード（inc. NAND chip）１０に記録する。合わせて、ID binding process（２）において生成したContent Keyにより暗号化したコンテンツ（Encrypted Content）も記録する。更に、Content Key Precursor自身も安全な形で記録する。
【０１９１】
ここで安全な形とは、メモリカード（inc. NAND chip）１０と記録ホスト（Recoding Device）２０Ａの間で認証が成立した後にアクセスが可能となるモリカード（inc. NAND chip）１０内の記録エリアであってもよい。また、ここでいう認証は本願において記載されている認証方法でもよいし、メモリカード（inc. NAND chip）１０が持つ別の認証機能によって実現してもよい。また、安全な形の別な例としては、メモリカード（inc. NAND chip）１０もしくは記録ホスト（Recoding Device）２０Ａが有する鍵によって暗号化した形であってもよい。
【０１９２】
再生ホスト（Playback Device）２０Ｂがコンテンツをメモリカード（inc. NAND chip）１０から読出し、再生するに際し、まずメモリカード（inc. NAND chip）１０と再生ホスト（Playback Device）２０Ｂの間で、上記実施形態における認証処理を行う。ここで、認証処理が成立した後、上記実施形態におけるID retrieval processを行う。次いで、上記実施形態におけるID binding process（２）に対応する処理により、メモリカード（inc. NAND chip）１０に記録されているContent Key PrecursorからContent Keyを生成する。その後、暗号化したコンテンツ（Encrypted Content）の復号を行うことでコンテンツを再生する。
【０１９３】
［第１２実施形態（メモリ、コントローラ、ホストの一例）］
次に、図２６を用い、第１２実施形態について説明する。第１２実施形態は、上記実施形態に適用可能な上記ＮＡＮＤ型フラッシュメモリ１０、コントローラ１９、およびホスト２０の一例に関するものである。本例では、メモリカードとしてＳＤカード（登録商標）を一例に挙げる。
【０１９４】
図示するように、本例では、メモリカードと接続されるホスト装置の機能ブロックも示されている。各機能ブロックは、ハードウェア、コンピュータソフトウェアのいずれかまたは両者を組み合わせたものとして実現することができる。このため、各ブロックがこれらのいずれでもあることが明確となるように、概してそれらの機能の観点から以下に説明する。このような機能が、ハードウェアとして実行されるか、またはソフトウェアとして実行されるかは、具体的な実施態様またはシステム全体に課される設計制約に依存する。当業者は、具体的な実施態様ごとに、種々の方法でこれらの機能を実現し得るが、いずれの実現の手法も本発明の範疇に含まれる。
【０１９５】
ホスト２０は、アプリケーション、オペレーティング・システム等のソフトウェア２１１を備えている。ソフトウェア２１１は、ユーザから、メモリカードへのデータの書き込み、メモリカードからのデータの読み出しを指示される。ソフトウェア２１１は、データの書き込みおよび読み出しをファイルシステム２１２に指示する。ファイルシステム２１２は、管理対象の記憶媒体に記録されているファイルデータを管理するための仕組みであり、記憶媒体の記憶領域内に管理情報を記録し、この管理情報を用いてファイルデータを管理する。
【０１９６】
ホスト２０は、ＳＤインターフェース２１３を有する。ＳＤインターフェース２１３は、ホスト２０とメモリカードとの間のインターフェース処理を行うのに必要なハードウェア、ソフトウェアからなる。ホスト２０は、ＳＤインターフェース２１３を介してメモリカードと通信を行う。ＳＤインターフェース２１３は、ホスト２０とメモリカードとが通信するのに必要な様々な取り決めを規定し、後述のメモリカードのＳＤインターフェース２３１と相互に認識可能な各種のコマンドの組を備えている。また、ＳＤインターフェース２１３は、メモリカードのＳＤインターフェース２３１と接続可能なハードウェア上の構成（ピンの配置、数等）も含む。
【０１９７】
メモリカードは、ＮＡＮＤ型フラッシュメモリ１０、メモリ１０を制御するためのコントローラ１９を有する。メモリカードは、ホスト２０に接続されたとき、およびオフ状態のホスト２０に挿入された状態でホスト２０がオンされたときに電源供給を受けて初期化動作を行った後、ホスト１からのアクセスに応じた処理を行う。
【０１９８】
ＮＡＮＤ型メモリ１０は、データを不揮発に記憶し、複数のメモリセルからなるページと呼ばれる単位でデータの書き込みおよび読み出しを行う。ページには、各ページに固有の物理アドレスが割り当てられている。また、メモリ１０は、複数のページからなる物理ブロック（消去ブロック）と呼ばれる単位でデータの消去を行う。なお、物理ブロック単位で物理アドレスが割り当てられていることもある。
【０１９９】
コントローラ１９は、メモリ１０によるデータの記憶状態を管理する。記憶状態の管理とは、どの物理アドレスのページ（または物理ブロック）が、どの論理アドレスのデータを保持しているかの関係、およびどの物理アドレスのページ（または物理ブロック）が消去状態（何も書き込まれていない、または無効なデータを保持している状態）であるかを管理することを含んでいる。
【０２００】
コントローラ１９は、ＳＤインターフェース３１、ＭＰＵ（micro processing unit）３２、ＲＯＭ（read only memory）３３、ＲＡＭ（『random access memory』）３４、ＮＡＮＤインターフェース３５を含んでいる。
【０２０１】
ＳＤインターフェース３１は、ホスト２０とコントローラ１９との間のインターフェース処理を行うのに必要なハードウェア、ソフトウェアからなり、ＳＤインターフェース１３と同様に、両者の通信を可能とする取り決めを規定し、各種のコマンドの組を備え、ハードウェア上の構成（ピンの配置、数等）も含む。メモリカード（コントローラ２２）は、ＳＤインターフェース３１を介してとホスト１と通信を行う。ＳＤインターフェース３１は、レジスタ３６を含んでいる。
【０２０２】
ＭＰＵ３２は、メモリカード２全体の動作を司る。ＭＰＵ３２は、例えば、メモリカード２が電源供給を受けた際に、ＲＯＭ３３内に格納されているファームウェア（制御プログラム）をＲＡＭ３４上に読み出して所定の処理を実行する。ＭＰＵ３２は、制御プログラムに従って各種のテーブルをＲＡＭ３４上で作成したり、ホスト１から受けたコマンドに従ってメモリ２１に対する所定の処理を実行したりする。
【０２０３】
ＲＯＭ３３は、ＭＰＵ３２により制御される制御プログラムなどを格納する。ＲＡＭ３４は、ＭＰＵ３２の作業エリアとして使用され、制御プログラムや各種のテーブルを一時的に記憶する。このようなテーブルとして、ファイルシステム１２によってデータに割り当てられた論理アドレスを有するデータを実際に記憶しているページの物理アドレスの変換テーブル（論物テーブル）が含まれる。ＮＡＮＤインターフェース３５は、コントローラ２２とメモリ２１とのインターフェース処理を行う。
【０２０４】
ＮＡＮＤ型フラッシュメモリ１０内の記憶領域は、保存されるデータの種類に応じて、例えばシステムデータ領域、機密データ領域、保護データ領域、ユーザデータ領域等を含んでいる。システムデータ領域は、コントローラ１９が、その動作に必要なデータを保存するためにメモリ１０内で確保しておく領域である。機密データ領域は、暗号化に用いる鍵情報や認証時に使用する機密データを保存しており、ホスト２０からアクセスできない。保護データ領域は、重要なデータ、セキュアなデータを格納する。ユーザデータ領域は、ホスト２０が自由にアクセスおよび使用することが可能で、例えばＡＶコンテンツファイルや画像データ等のユーザデータを格納する。なお、コントローラ１９は、ユーザデータ領域の一部を確保し、自身の動作に必要な制御データ（論物テーブル等）を保存する。
【０２０５】
本発明のいくつか実施形態を説明したが、これら実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２０６】
１０…ＮＡＮＤ型フラッシュメモリ（被認証コンポーネント）、１９…コントローラ、２０…ホストデバイス（認証コンポーネント）。
【特許請求の範囲】
【請求項１】
秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶する被認証コンポーネントと、前記被認証コンポーネントを認証する認証コンポーネントとの間における認証方法は、
前記認証コンポーネントが、前記被認証コンポーネントから受領した前記秘密情報XYEに対して、復号処理を行い、前記秘密情報XYを共有するステップと、
前記被認証コンポーネントが、前記認証コンポーネントが生成する乱数Bを受領し、前記複製された秘密情報XYを複数ロードするステップと、
前記被認証コンポーネントが、乱数Aおよびデータν（νは１の出現確率がη（ただし、η<0.5））を生成するステップと、
前記被認証コンポーネントが、生成した前記乱数Aと受領した前記乱数Bの少なくとも一部から構成される乱数Dを生成するステップと、
前記被認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、
前記被認証コンポーネントが、前記データCに前記データνを付与した演算結果Zを、前記認証コンポーネントに送信するステップと、
前記認証コンポーネントが、生成した前記乱数Bと受領した前記乱数Aの少なくとも一部から構成される乱数Dを生成するステップと、
前記認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、
前記認証コンポーネントが、受領した演算結果Zと生成したデータCとを用いて、判定処理を行うステップとを具備する。
【請求項２】
前記秘密情報XYEは、誤り訂正符号を更に含み、
前記認証コンポーネントは、前記被認証コンポーネントから受領した前記秘密情報XYEに対して、誤り訂正処理を行うステップを更に具備する
請求項１に記載の認証方法。
【請求項３】
前記判定処理は、前記認証コンポーネントが受領した演算結果Zが複数のデータから構成されており、前記複数のデータの各々は多重に複製された前記秘密情報XYのうち少なくとも2つ以上のデータに対して同一パラメータを用いて計算されており、前記パラメータは前記乱数A、前記乱数B、前記データνに対応し、前記複数のデータ間の多数決処理を含む
請求項１または２に記載の認証方法。
【請求項４】
秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶するメモリと、
乱数Aを生成する生成部と、
生成した前記乱数Aと、受領する乱数Bの少なくとも一部から構成される乱数Dを生成する生成部と、
前記乱数Dと前記メモリからロードした前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成する演算部と、
データν（νは１の出現確率がη（ただし、η<0.5））を生成する生成部と、
前記データCに前記データνを付与して、演算結果Zを算出するビット毎加算部と
を具備する被認証コンポーネント。
【請求項５】
前記秘密情報XYEは、誤り訂正符号を更に含む
請求項４に記載の被認証コンポーネント。
【請求項６】
秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶する被認証コンポーネントを認証する認証コンポーネントは、
乱数Aを生成する生成部と、
暗号化された前記秘密情報XYEに対して、鍵を用いた復号処理を行って秘密情報XYを共有する復号部と、
乱数Bを生成する生成部と、
生成した前記乱数Bと、受領する乱数Aの少なくとも一部から構成される乱数Dを生成する生成部と、
前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成する演算部と、
生成した前記データCと受領する演算結果Zとを用いて、判定処理を行う判定部とを具備する。
【請求項７】
前記秘密情報XYEは、誤り訂正符号を更に含み、
前記秘密情報XYEに対して、誤り訂正処理を行う誤り訂正部を更に具備する
請求項６に記載の認証コンポーネント。
【請求項８】
前記判定部は、前記認証コンポーネントが受領した演算結果Zが複数のデータから構成されており、前記複数のデータの各々は多重に複製された前記秘密情報XYのうち少なくとも2つ以上のデータに対して同一パラメータを用いて計算されており、前記パラメータは前記乱数A、前記乱数B、前記データνに対応し、前記複数のデータ間の多数決処理を含む
請求項６または請求項７に記載の認証コンポーネント。
【請求項１】
秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶する被認証コンポーネントと、前記被認証コンポーネントを認証する認証コンポーネントとの間における認証方法は、
前記認証コンポーネントが、前記被認証コンポーネントから受領した前記秘密情報XYEに対して、復号処理を行い、前記秘密情報XYを共有するステップと、
前記被認証コンポーネントが、前記認証コンポーネントが生成する乱数Bを受領し、前記複製された秘密情報XYを複数ロードするステップと、
前記被認証コンポーネントが、乱数Aおよびデータν（νは１の出現確率がη（ただし、η<0.5））を生成するステップと、
前記被認証コンポーネントが、生成した前記乱数Aと受領した前記乱数Bの少なくとも一部から構成される乱数Dを生成するステップと、
前記被認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、
前記被認証コンポーネントが、前記データCに前記データνを付与した演算結果Zを、前記認証コンポーネントに送信するステップと、
前記認証コンポーネントが、生成した前記乱数Bと受領した前記乱数Aの少なくとも一部から構成される乱数Dを生成するステップと、
前記認証コンポーネントが、前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成するステップと、
前記認証コンポーネントが、受領した演算結果Zと生成したデータCとを用いて、判定処理を行うステップとを具備する。
【請求項２】
前記秘密情報XYEは、誤り訂正符号を更に含み、
前記認証コンポーネントは、前記被認証コンポーネントから受領した前記秘密情報XYEに対して、誤り訂正処理を行うステップを更に具備する
請求項１に記載の認証方法。
【請求項３】
前記判定処理は、前記認証コンポーネントが受領した演算結果Zが複数のデータから構成されており、前記複数のデータの各々は多重に複製された前記秘密情報XYのうち少なくとも2つ以上のデータに対して同一パラメータを用いて計算されており、前記パラメータは前記乱数A、前記乱数B、前記データνに対応し、前記複数のデータ間の多数決処理を含む
請求項１または２に記載の認証方法。
【請求項４】
秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶するメモリと、
乱数Aを生成する生成部と、
生成した前記乱数Aと、受領する乱数Bの少なくとも一部から構成される乱数Dを生成する生成部と、
前記乱数Dと前記メモリからロードした前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成する演算部と、
データν（νは１の出現確率がη（ただし、η<0.5））を生成する生成部と、
前記データCに前記データνを付与して、演算結果Zを算出するビット毎加算部と
を具備する被認証コンポーネント。
【請求項５】
前記秘密情報XYEは、誤り訂正符号を更に含む
請求項４に記載の被認証コンポーネント。
【請求項６】
秘密情報XYと前記秘密情報XYが少なくとも２回以上多重に複製された秘密情報XYと、前記秘密情報XYが暗号化された秘密情報XYEとを記憶する被認証コンポーネントを認証する認証コンポーネントは、
乱数Aを生成する生成部と、
暗号化された前記秘密情報XYEに対して、鍵を用いた復号処理を行って秘密情報XYを共有する復号部と、
乱数Bを生成する生成部と、
生成した前記乱数Bと、受領する乱数Aの少なくとも一部から構成される乱数Dを生成する生成部と、
前記乱数Dと前記秘密情報XYの少なくとも一部とについて、圧縮演算を行い、データCを生成する演算部と、
生成した前記データCと受領する演算結果Zとを用いて、判定処理を行う判定部とを具備する。
【請求項７】
前記秘密情報XYEは、誤り訂正符号を更に含み、
前記秘密情報XYEに対して、誤り訂正処理を行う誤り訂正部を更に具備する
請求項６に記載の認証コンポーネント。
【請求項８】
前記判定部は、前記認証コンポーネントが受領した演算結果Zが複数のデータから構成されており、前記複数のデータの各々は多重に複製された前記秘密情報XYのうち少なくとも2つ以上のデータに対して同一パラメータを用いて計算されており、前記パラメータは前記乱数A、前記乱数B、前記データνに対応し、前記複数のデータ間の多数決処理を含む
請求項６または請求項７に記載の認証コンポーネント。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２０１２−２２７９０１（Ｐ２０１２−２２７９０１Ａ）
【公開日】平成２４年１１月１５日（２０１２．１１．１５）
【国際特許分類】
【出願番号】特願２０１１−９６５００（Ｐ２０１１−９６５００）
【出願日】平成２３年４月２２日（２０１１．４．２２）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２４年１１月１５日（２０１２．１１．１５）
【国際特許分類】
【出願日】平成２３年４月２２日（２０１１．４．２２）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]