(57)【特許請求の範囲】
【請求項１】
送信装置と受信装置を含む公開鍵暗号システムであって、
前記受信装置は、
適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する情報鍵対生成部と、
標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第１鍵暗号化鍵ｐｋ１と第１鍵復号鍵ｓｋ１を生成する第１鍵対生成部と、
前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第２鍵暗号化鍵ｐｋ２と第２鍵復号鍵ｓｋ２を生成する第２鍵対生成部と、
第１鍵Ｋ１を無作為に生成し、当該第１鍵Ｋ１を、前記第１鍵暗号化鍵ｐｋ１を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第１鍵暗号文ｃ１を生成する第１鍵暗号化部と、
第２鍵Ｋ２を無作為に生成し、当該第２鍵Ｋ２を、前記第２鍵暗号化鍵ｐｋ２を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第２鍵暗号文ｃ２を生成する第２鍵暗号化部と、
前記第１鍵Ｋ１と前記第２鍵Ｋ２とから前記情報復号鍵ｓｋ０とビット長が等しい乱数Ｋを生成し、当該乱数Ｋと前記情報復号鍵ｓｋ０との排他的論理和を計算することで、前記情報復号鍵暗号文ｅを生成する情報鍵暗号化部と、
前記情報復号鍵ｓｋ０を消去する鍵消去部と、
前記情報暗号化鍵ｐｋ０と前記第１鍵暗号化鍵ｐｋ１と前記第２鍵暗号化鍵ｐｋ２と前記第１鍵暗号文ｃ１と前記第２鍵暗号文ｃ２と前記情報復号鍵暗号文ｅを一組とした公開鍵ＰＫ：＝（ｐｋ０，ｐｋ１，ｐｋ２，ｃ１，ｃ２，ｅ）を生成する鍵公開部と、
前記第１鍵復号鍵ｓｋ１と前記第２鍵復号鍵ｓｋ２を一組とした秘密鍵ＳＫ：＝（ｓｋ１，ｓｋ２）を記憶する鍵記憶部と、
前記第１鍵暗号文ｃ１を、前記第１鍵復号鍵ｓｋ１を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、前記第１鍵Ｋ１を取得する第１鍵復号部と、
前記第２鍵暗号文ｃ２を、前記第２鍵復号鍵ｓｋ２を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、前記第２鍵Ｋ２を取得する第２鍵復号部と、
前記第１鍵Ｋ１と前記第２鍵Ｋ２とから前記乱数Ｋを生成し、当該乱数Ｋと前記情報復号鍵暗号文ｅとの排他的論理和を計算することで前記情報復号鍵ｓｋ０を取得する情報鍵復号部と、
前記送信装置から受信した暗号文ｃを、前記情報復号鍵ｓｋ０を用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、平文ｍを取得する情報復号部と、
を備え、
前記送信装置は、
暗号化乱数ωを生成する暗号化乱数生成部と、
前記平文ｍを、前記受信装置の前記情報暗号化鍵ｐｋ０と前記暗号化乱数ωを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化して、前記暗号文ｃを生成し、前記受信装置へ送信する情報暗号化部と、
を備えることを特徴とする公開鍵暗号システム。
【請求項２】
請求項１に記載の公開鍵暗号システムであって、
前記暗号化乱数生成部は、乱数ｒ１と乱数ｒ２を生成し、当該乱数ｒ１と当該乱数ｒ２とから前記暗号化乱数ωを生成する
ことを特徴とする公開鍵暗号システム。
【請求項３】
送信装置と受信装置からなる公開鍵暗号システムであって、
前記受信装置は、
乱数ρ１と乱数ρ２を生成し、当該乱数ρ１と当該乱数ρ２とから鍵生成乱数ρを生成する鍵生成乱数生成部と、
前記鍵生成乱数ρを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する情報鍵対生成部と、
前記情報復号鍵ｓｋ０と前記鍵生成乱数ρを消去する鍵消去部と、
前記情報暗号化鍵ｐｋ０を公開鍵ＰＫ：＝（ｐｋ０）として生成する鍵公開部と、
前記乱数ρ１と前記乱数ρ２を一組とした秘密鍵ＳＫ：＝（ρ１，ρ２）を記憶する鍵記憶部と、
前記乱数ρ１と前記乱数ρ２とから前記鍵生成乱数ρを取得する鍵生成乱数復元部と、
前記鍵生成乱数ρを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により前記情報暗号化鍵ｐｋ０と前記情報復号鍵ｓｋ０を取得する情報鍵対復元部と、
前記送信装置から受信した暗号文ｃを、前記情報復号鍵ｓｋ０を用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、平文ｍを取得する情報復号部と、
を備え、
前記送信装置は、
乱数ｒ１と乱数ｒ２を生成し、当該乱数ｒ１と当該乱数ｒ２とから暗号化乱数ωを生成する暗号化乱数生成部と、
前記平文ｍを、前記受信装置の前記情報暗号化鍵ｐｋ０と前記暗号化乱数ωを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化して、前記暗号文ｃを生成し、前記受信装置へ送信する情報暗号化部と、
を備えることを特徴とする公開鍵暗号システム。
【請求項４】
適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する情報鍵対生成部と、
標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第１鍵暗号化鍵ｐｋ１と第１鍵復号鍵ｓｋ１を生成する第１鍵対生成部と、
前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第２鍵暗号化鍵ｐｋ２と第２鍵復号鍵ｓｋ２を生成する第２鍵対生成部と、
第１鍵Ｋ１を無作為に生成し、当該第１鍵Ｋ１を、前記第１鍵暗号化鍵ｐｋ１を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第１鍵暗号文ｃ１を生成する第１鍵暗号化部と、
第２鍵Ｋ２を無作為に生成し、当該第２鍵Ｋ２を、前記第２鍵暗号化鍵ｐｋ２を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第２鍵暗号文ｃ２を生成する第２鍵暗号化部と、
前記第１鍵Ｋ１と前記第２鍵Ｋ２とから前記情報復号鍵ｓｋ０とビット長が等しい乱数Ｋを生成し、当該乱数Ｋと前記情報復号鍵ｓｋ０との排他的論理和を計算することで、前記情報復号鍵暗号文ｅを生成する情報鍵暗号化部と、
前記情報復号鍵ｓｋ０を消去する鍵消去部と、
前記情報暗号化鍵ｐｋ０と前記第１鍵暗号化鍵ｐｋ１と前記第２鍵暗号化鍵ｐｋ２と前記第１鍵暗号文ｃ１と前記第２鍵暗号文ｃ２と前記情報復号鍵暗号文ｅを一組とした公開鍵ＰＫ：＝（ｐｋ０，ｐｋ１，ｐｋ２，ｃ１，ｃ２，ｅ）を生成する鍵公開部と、
前記第１鍵復号鍵ｓｋ１と前記第２鍵復号鍵ｓｋ２を一組とした秘密鍵ＳＫ：＝（ｓｋ１，ｓｋ２）を記憶する鍵記憶部と、
前記第１鍵暗号文ｃ１を、前記第１鍵復号鍵ｓｋ１を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、前記第１鍵Ｋ１を取得する第１鍵復号部と、
前記第２鍵暗号文ｃ２を、前記第２鍵復号鍵ｓｋ２を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、前記第２鍵Ｋ２を取得する第２鍵復号部と、
前記第１鍵Ｋ１と前記第２鍵Ｋ２とから前記乱数Ｋを生成し、当該乱数Ｋと前記情報復号鍵暗号文ｅとの排他的論理和を計算することで前記情報復号鍵ｓｋ０を取得する情報鍵復号部と、
前記送信装置から受信した暗号文ｃを、前記情報復号鍵ｓｋ０を用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、平文ｍを取得する情報復号部と、
を備える受信装置。
【請求項５】
乱数ρ１と乱数ρ２を生成し、当該乱数ρ１と当該乱数ρ２とから鍵生成乱数ρを生成する鍵生成乱数生成部と、
前記鍵生成乱数ρを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する情報鍵対生成部と、
前記情報復号鍵ｓｋ０と前記鍵生成乱数ρを消去する鍵消去部と、
前記情報暗号化鍵ｐｋ０を公開鍵ＰＫ：＝（ｐｋ０）として生成する鍵公開部と、
前記乱数ρ１と前記乱数ρ２を一組とした秘密鍵ＳＫ：＝（ρ１，ρ２）を記憶する鍵記憶部と、
前記乱数ρ１と前記乱数ρ２とから前記鍵生成乱数ρを取得する鍵生成乱数復元部と、
前記鍵生成乱数ρを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により前記情報暗号化鍵ｐｋ０と前記情報復号鍵ｓｋ０を取得する情報鍵対復元部と、
前記送信装置から受信した暗号文ｃを、前記情報復号鍵ｓｋ０を用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、平文ｍを取得する情報復号部と、
を備える受信装置。
【請求項６】
受信装置が、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する情報鍵対生成ステップと、
前記受信装置が、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第１鍵暗号化鍵ｐｋ１と第１鍵復号鍵ｓｋ１を生成する第１鍵対生成ステップと、
前記受信装置が、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第２鍵暗号化鍵ｐｋ２と第２鍵復号鍵ｓｋ２を生成する第２鍵対生成ステップと、
前記受信装置が、第１鍵Ｋ１を無作為に生成し、当該第１鍵Ｋ１を、前記第１鍵暗号化鍵ｐｋ１を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第１鍵暗号文ｃ１を生成する第１鍵暗号化ステップと、
前記受信装置が、第２鍵Ｋ２を無作為に生成し、当該第２鍵Ｋ２を、前記第２鍵暗号化鍵ｐｋ２を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第２鍵暗号文ｃ２を生成する第２鍵暗号化ステップと、
前記受信装置が、前記第１鍵Ｋ１と前記第２鍵Ｋ２とから前記情報復号鍵ｓｋ０とビット長が等しい乱数Ｋを生成し、当該乱数Ｋと前記情報復号鍵ｓｋ０との排他的論理和を計算することで、前記情報復号鍵暗号文ｅを生成する情報鍵暗号化ステップと、
前記受信装置が、前記情報復号鍵ｓｋ０を消去する鍵消去ステップと、
前記受信装置が、前記情報暗号化鍵ｐｋ０と前記第１鍵暗号化鍵ｐｋ１と前記第２鍵暗号化鍵ｐｋ２と前記第１鍵暗号文ｃ１と前記第２鍵暗号文ｃ２と前記情報復号鍵暗号文ｅを一組とした公開鍵ＰＫ：＝（ｐｋ０，ｐｋ１，ｐｋ２，ｃ１，ｃ２，ｅ）を生成する鍵公開ステップと、
前記受信装置が、前記第１鍵復号鍵ｓｋ１と前記第２鍵復号鍵ｓｋ２を一組とした秘密鍵ＳＫ：＝（ｓｋ１，ｓｋ２）を記憶する鍵記憶ステップと、
送信装置が、暗号化乱数ωを生成する暗号化乱数生成ステップと、
前記送信装置が、平文ｍを、前記受信装置の前記情報暗号化鍵ｐｋ０と前記暗号化乱数ωを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化して、暗号文ｃを生成し、前記受信装置へ送信する情報暗号化ステップと、
前記受信装置が、前記第１鍵暗号文ｃ１を、前記第１鍵復号鍵ｓｋ１を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、前記第１鍵Ｋ１を取得する第１鍵復号ステップと、
前記受信装置が、前記第２鍵暗号文ｃ２を、前記第２鍵復号鍵ｓｋ２を用いて、前記標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、前記第２鍵Ｋ２を取得する第２鍵復号ステップと、
前記受信装置が、前記第１鍵Ｋ１と前記第２鍵Ｋ２とから前記乱数Ｋを生成し、当該乱数Ｋと前記情報復号鍵暗号文ｅとの排他的論理和を計算することで前記情報復号鍵ｓｋ０を取得する情報鍵復号ステップと、
前記受信装置が、前記送信装置から受信した前記暗号文ｃを、前記情報復号鍵ｓｋ０を用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、前記平文ｍを取得する情報復号ステップと、
を含む公開鍵暗号方法。
【請求項７】
受信装置が、乱数ρ１と乱数ρ２を生成し、当該乱数ρ１と当該乱数ρ２とから鍵生成乱数ρを生成する鍵生成乱数生成ステップと、
前記受信装置が、前記鍵生成乱数ρを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する情報鍵対生成ステップと、
前記受信装置が、前記情報復号鍵ｓｋ０と前記鍵生成乱数ρを消去する鍵消去ステップと、
前記受信装置が、前記情報暗号化鍵ｐｋ０を公開鍵ＰＫ：＝（ｐｋ０）として生成する鍵公開ステップと、
前記受信装置が、前記乱数ρ１と前記乱数ρ２を一組とした秘密鍵ＳＫ：＝（ρ１，ρ２）を記憶する鍵記憶ステップと、
送信装置が、乱数ｒ１と乱数ｒ２を生成し、当該乱数ｒ１と当該乱数ｒ２とから暗号化乱数ωを生成する暗号化乱数生成ステップと、
前記送信装置が、平文ｍを、前記受信装置の前記情報暗号化鍵ｐｋ０と前記暗号化乱数ωを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化して、暗号文ｃを生成し、前記受信装置へ送信する情報暗号化ステップと、
前記受信装置が、前記乱数ρ１と前記乱数ρ２とから前記鍵生成乱数ρを取得する鍵生成乱数復元ステップと、
前記受信装置が、前記鍵生成乱数ρを用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により前記情報暗号化鍵ｐｋ０と前記情報復号鍵ｓｋ０を取得する情報鍵対復元ステップと、
前記受信装置が、前記送信装置から受信した前記暗号文ｃを、前記情報復号鍵ｓｋ０を用いて、前記適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、前記平文ｍを取得する情報復号ステップと、
を含む公開鍵暗号方法。
【請求項８】
請求項４または５に記載の受信装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、電気通信システムにおいて情報を秘匿しながら安全に送受信する公開鍵暗号方式を実現する公開鍵暗号技術に関する。
【背景技術】
【０００２】
情報を秘匿しながら安全に送受信するために公開鍵暗号方式が広く用いられている。公開鍵暗号方式では情報を暗号化する鍵と復号する鍵が異なっており、通常は暗号化に用いる鍵を一般に公開し、復号に用いる鍵は利用者が秘密に保持する。ここでは、暗号化に用いる鍵を公開鍵と呼び、復号に用いる鍵は秘密鍵と呼ぶものとする。
【０００３】
従来の公開鍵暗号方式は、秘密鍵の情報が部分的にも漏洩することがないことを前提として安全性が定義されていた。しかし近年、サイドチャネル攻撃と呼ばれる攻撃方法が進展している。サイドチャネル攻撃とは、暗号を解読するための手法であり、暗号を処理する装置が発する電力や電磁波などを外部から観測することで暗号解読の手がかりを得ようとする（非特許文献１参照）。これらのサイドチャネル攻撃に対抗するために、秘密鍵が漏洩した場合の安全性を考慮する必要があると考えられている。
【０００４】
一般に、公開鍵暗号の安全性は各種の攻撃法に対する達成度として捉えられる。達成度としては、強秘匿性が用いられることが多い。強秘匿性とは、暗号文から平文のいかなる部分情報も得られないことである。強秘匿性は、攻撃者が適当な平文を２つ選び、そのどちらかを暗号化した暗号文を受け取ったときにどちらが暗号化されたのかを識別不可能であるということにより定式化されている。攻撃法は、選択平文攻撃、選択暗号文攻撃、適応的選択暗号文攻撃などに分類される。選択平文攻撃とは、標的とする暗号文を受け取る前後に、攻撃者は自分で選んだ平文に対する暗号文を得ることができる条件下での攻撃である。選択暗号文攻撃とは、標的とする暗号文を受け取る前に、攻撃者は自分で選んだ暗号文を送ることでその復号結果を得ることができる条件下での攻撃である。適応的選択暗号文攻撃とは、標的とする暗号文を受け取る前後に、攻撃者は自分で選んだ暗号文を送ることでその復号結果を得ることができる条件下での攻撃である。
【０００５】
公開鍵暗号方式では、暗号化に用いる鍵は公開されているため平文から暗号文を得ることは通常でも可能である。一方、復号に用いる鍵は秘匿されているため暗号文から平文を得ることは通常不可能である。したがって、選択平文攻撃よりも選択暗号文攻撃の方が攻撃者に有利な条件が設定されている。また、標的とする暗号文が確定した後の方が攻撃者は適切な暗号文を選択できる。したがって、選択暗号文攻撃よりも適応的選択暗号文攻撃の方が攻撃者に有利な条件が設定されている。このため、適応的選択暗号文攻撃に対して安全であることの方がより安全性が高い暗号方式であると言える。また同様に、標的暗号文確定後に秘密鍵が漏洩したとしても安全であることの方がより安全性が高いと言える。
【０００６】
秘密鍵が部分的に漏洩したとしても安全な公開鍵暗号方式が複数提案されている。非特許文献２は、標的暗号文確定前の秘密鍵漏洩を想定しており、選択平文攻撃に対して識別不可能な公開鍵暗号方式である。非特許文献３は、標的暗号文確定前の秘密鍵漏洩を想定しており、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式である。非特許文献４は、標的暗号文確定後の秘密鍵漏洩をも想定しており、選択平文攻撃に対して識別不可能な公開鍵暗号方式である。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. “Lest we remember: cold-boot attacks on encryption keys.” Commun. ACM, 52(5), 2009.
【非特許文献２】A. Akavia, S. Goldwasser, and V. Vaikuntanathan. “Simultaneous Hardcore Bits and Cryptography against Memory Attacks.” In TCC, volume 5444 of Lecture Notes in Computer Science, pages 474-495. Springer, 2009.
【非特許文献３】M. Naor and G. Segev. “Public-Key Cryptosystems Resilient to Key Leakage.” In CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 18-35. Springer, 2009.
【非特許文献４】S. Halevi and H. Lin. “After-the-Fact Leakage in Public-Key Encryption.” In TCC, volume 6597 of Lecture Notes in Computer Science, pages 107-124. Springer, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記の通り、既知の秘密鍵漏洩耐性のある公開鍵暗号方式は、適応的選択暗号文攻撃に対して識別不可能であるが標的暗号文確定前の秘密鍵漏洩耐性しか達成していない公開鍵暗号方式か、標的暗号文確定後の秘密鍵漏洩耐性を達成しているが選択平文攻撃に対する安全性しか達成していない公開鍵暗号方式のいずれかであった。つまり、標的暗号文確定後の秘密鍵漏洩耐性と適応的選択暗号文攻撃に対する安全性を同時に達成している公開鍵暗号方式は提案されていなかった。
【０００９】
この発明はこのような点に鑑みてなされたものであり、標的暗号文確定後の秘密鍵漏洩耐性があり、かつ適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により安全に情報を送受信することができる公開鍵暗号システム、公開鍵暗号方法、送信装置、受信装置、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、この発明の公開鍵暗号システムは、送信装置と受信装置を含む。
【００１１】
受信装置は、情報鍵対生成部と第１鍵対生成部と第２鍵対生成部と第１鍵暗号化部と第２鍵暗号化部と情報鍵暗号化部と鍵消去部と鍵公開部と鍵記憶部と第１鍵復号部と第２鍵復号部と情報鍵復号部と情報復号部とを備える。情報鍵対生成部は、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する。第１鍵対生成部は、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第１鍵暗号化鍵ｐｋ１と第１鍵復号鍵ｓｋ１を生成する。第２鍵対生成部は、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により第２鍵暗号化鍵ｐｋ２と第２鍵復号鍵ｓｋ２を生成する。第１鍵暗号化部は、第１鍵Ｋ１を無作為に生成し、第１鍵Ｋ１を、第１鍵暗号化鍵ｐｋ１を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第１鍵暗号文ｃ１を生成する。第２鍵暗号化部は、第２鍵Ｋ２を無作為に生成し、第２鍵Ｋ２を、第２鍵暗号化鍵ｐｋ２を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により暗号化して、第２鍵暗号文ｃ２を生成する。情報鍵暗号化部は、第１鍵Ｋ１と第２鍵Ｋ２とから情報復号鍵ｓｋ０とビット長が等しい乱数Ｋを生成し、乱数Ｋと情報復号鍵ｓｋ０との排他的論理和を計算することで、情報復号鍵暗号文ｅを生成する。鍵消去部は、情報復号鍵ｓｋ０を消去する。鍵公開部は、情報暗号化鍵ｐｋ０と第１鍵暗号化鍵ｐｋ１と第２鍵暗号化鍵ｐｋ２と第１鍵暗号文ｃ１と第２鍵暗号文ｃ２と情報復号鍵暗号文ｅを一組とした公開鍵ＰＫ：＝（ｐｋ０，ｐｋ１，ｐｋ２，ｃ１，ｃ２，ｅ）を生成する。鍵記憶部は、第１鍵復号鍵ｓｋ１と第２鍵復号鍵ｓｋ２を一組とした秘密鍵ＳＫ：＝（ｓｋ１，ｓｋ２）を記憶する。第１鍵復号部は、第１鍵暗号文ｃ１を、第１鍵復号鍵ｓｋ１を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、第１鍵Ｋ１を取得する。第２鍵復号部は、第２鍵暗号文ｃ２を、第２鍵復号鍵ｓｋ２を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式により復号して、第２鍵Ｋ２を取得する。情報鍵復号部は、第１鍵Ｋ１と第２鍵Ｋ２とから乱数Ｋを生成し、乱数Ｋと情報復号鍵暗号文ｅとの排他的論理和を計算することで情報復号鍵ｓｋ０を取得する。情報復号部は、送信装置から受信した暗号文ｃを、情報復号鍵ｓｋ０を用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により復号して、平文ｍを取得する。
【００１２】
送信装置は、暗号化乱数生成部と情報暗号化部とを備える。暗号化乱数生成部は、暗号化乱数ωを生成する。情報暗号化部は、平文ｍを、受信装置の情報暗号化鍵ｐｋ０と暗号化乱数ωを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化して、暗号文ｃを生成し、受信装置へ送信する。
【発明の効果】
【００１３】
この発明の公開鍵暗号システムは、平文を適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化するため、適応的選択暗号文攻撃によっても暗号文から平文のいかなる部分情報も得られることがない。また、暗号文の復号に用いる秘密鍵を標的確定後秘密鍵漏洩耐性がある鍵カプセル化方式により暗号化するため、標的とする暗号文が確定した後に秘密鍵が部分的に漏洩したとしても暗号の秘匿性が保証される。すなわち、この発明の公開鍵暗号システムによれば、標的暗号文確定後の秘密鍵漏洩耐性があり、かつ適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により安全に情報を送受信することができる。
【図面の簡単な説明】
【００１４】
【図１】実施例１の公開鍵暗号システムの構成を示すブロック図。
【図２】実施例１の公開鍵暗号システムを構成する装置の構成を示すブロック図。
【図３】実施例１の公開鍵暗号システムが鍵生成する動作を示すフロー図。
【図４】実施例１の公開鍵暗号システムが情報を送受信する動作を示すフロー図。
【図５】実施例１の暗号化処理・復号処理を説明する図。
【図６】実施例２の公開鍵暗号システムの構成を示すブロック図。
【図７】実施例２の公開鍵暗号システムを構成する装置の構成を示すブロック図。
【図８】実施例２の公開鍵暗号システムが情報を送受信する動作を示すフロー図。
【図９】実施例３の公開鍵暗号システムの構成を示すブロック図。
【図１０】実施例３の公開鍵暗号システムを構成する装置の構成を示すブロック図。
【図１１】実施例３の公開鍵暗号システムが鍵生成する動作を示すフロー図。
【図１２】実施例３の公開鍵暗号システムが情報を送受信する動作を示すフロー図。
【図１３】実施例３の暗号化処理・復号処理を説明する図。
【図１４】この発明で用いる公開鍵暗号方式と従来技術との比較を示す図。
【発明を実施するための形態】
【００１５】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
［この明細書で利用する表記方法］
【００１６】
【数１】
0005689839.tif 000002
【００１７】
は、ある値ａ，ｂについて、ａにｂを代入する、またはａをｂで定義することを表す。
【００１８】
【数２】
0005689839.tif 000003
【００１９】
は、ある有限集合Ｓについて、集合Ｓから要素ｒを一様ランダムに選ぶことを表す。
【００２０】
【数３】
0005689839.tif 000004
【００２１】
は、ある確率的多項式時間アルゴリズムＡについて、アルゴリズムＡがｘを入力にとり、乱数を生成して動作し、ａを出力することを表す。
【００２２】
【数４】
0005689839.tif 000005
【００２３】
は、ある確率的多項式時間アルゴリズムＡについて、アルゴリズムＡがｘを入力にとり、乱数ｒを明示的に使用して動作し、ａを出力することを表す。
【００２４】
ΣＣＣＡ＝（ＧｅｎＣＣＡ，ＥｎｃＣＣＡ，ＤｅｃＣＣＡ）は適応的選択暗号文攻撃（Adaptive Chosen Ciphertext Attack）に対して識別不可能な公開鍵暗号方式を表す。ΣＬＲ−ＣＰＡ＝（ＧｅｎＬＲ−ＣＰＡ，ＥｎｃＬＲ−ＣＰＡ，ＤｅｃＬＲ−ＣＰＡ）は２分割モデル（2-split-state model）において標的確定後秘密鍵漏洩耐性（Leakage Resilient）がある選択平文攻撃（Chosen Plaintext Attack）に対して識別不可能な公開鍵暗号方式を表す。それぞれ、Ｇｅｎは鍵生成アルゴリズムを、Ｅｎｃは暗号化アルゴリズムを、Ｄｅｃは復号アルゴリズムを意味している。例えば、ＧｅｎＣＣＡであれば、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の鍵生成アルゴリズムを表している。なお、暗号学の分野では、ＣＣＡは、選択暗号文攻撃（Non-Adaptive Chosen Ciphertext Attack）を表し、適応的選択暗号文攻撃（Adaptive Chosen Ciphertext Attack）をＣＣＡ２と表す場合があるが、この明細書においては、ＣＣＡは、適応的選択暗号文攻撃（Adaptive Chosen Ciphertext Attack）を表すものとする。
【００２５】
【数５】
0005689839.tif 000006
【００２６】
は、一様性の比較的低い擬似乱数ｒ１とｒ２を入力として、２情報源乱数抽出器（2-source extractor）を用いて、より一様性の高い乱数Ｒを生成することを表す。
【００２７】
［鍵カプセル化メカニズム］
この発明では、鍵カプセル化メカニズム（Key Encapsulation Mechanism。以下、ＫＥＭともいう。）を用いる。鍵カプセル化メカニズムは、共通鍵暗号方式で用いる共通鍵を公開鍵暗号方式で暗号化し、二者間で鍵共有を行うためのメカニズムである。鍵カプセル化メカニズムについての詳細は「D. Moriyama, R. Nishimaki, and T. Okamoto. “公開鍵暗号の数理” 共立出版, 2011.（参考文献１）」を参照されたい。
【００２８】
［２情報源乱数抽出器の定義］
ある関数Ｅｘｔ２：｛０，１｝ｔ×｛０，１｝ｔ→｛０，１｝ｍが、average-case(ｓ，ε)-two source extractorであるとは、任意の確率変数Ａ，Ｂ∈｛０，１｝ｔとＣに対して、Ｃの条件付きの下、ＡとＢが独立であり、ＡとＢの平均最小エントロピーがｓであり、かつΔ（（Ｅｘｔ２（Ａ，Ｂ），Ｃ），（Ｕｍ，Ｃ））≦εが成立することをいう。ここで、Δ（Ｘ，Ｙ）は確率変数ＸとＹの統計的距離を表す。統計的距離については参考文献１を参照されたい。Ｕｍ∈｛０，１｝ｍはｍビットの一様乱数である。平均最小エントロピーは最小エントロピーの拡張であり、確率変数Ａの最小エントロピーを
【００２９】
【数６】
0005689839.tif 000007
【００３０】
と書いたとき、確率変数Ｂの条件下でのＡの平均最小エントロピーは
【００３１】
【数７】
0005689839.tif 000008
【００３２】
と定義される。ただし、Ｅは期待値を表す。
【００３３】
２情報源乱数抽出器についての定義や具体的な構成方法などの詳細は、例えば「Y. Dodis, A. Elbaz, R. Oliveira, and R. Raz. “Improved Randomness Extraction from Two Independent Sources.” In APPROX-RANDOM, volume 3122 of Lecture Notes in Computer Science, pages 334-344. Springer, 2004.」を参照されたい。
【００３４】
［２分割モデルにおける公開鍵暗号の定義］
２分割モデルにおける公開鍵暗号Σ＝（Ｇｅｎ，Ｅｎｃ，Ｄｅｃ）は以下のように構成される。秘密鍵は一対のビット列ｓｋ＝（ｓｋ１，ｓｋ２）から構成され、同様に公開鍵も一対のｐｋ＝（ｐｋ１，ｐｋ２）からなる。鍵生成アルゴリズムＧｅｎは２つの関数Ｇｅｎ１，Ｇｅｎ２からなり、各ｉ＝１，２について、ｐｋｉとｓｋｉを生成する。したがって、鍵生成アルゴリズムＧｅｎは以下の式のように表すことができる。
【００３５】
【数８】
0005689839.tif 000009
【００３６】
暗号化アルゴリズムＥｎｃは、各ｉ＝１，２について、乱数ｘｉを生成し、公開鍵ｐｋｉと乱数ｘｉを入力にとり部分暗号文ｃｉを生成し、さらに平文ｍと乱数ｘｉを入力として暗号文ｃを出力する。したがって、暗号化アルゴリズムＥｎｃは以下の式のように表すことができる。
【００３７】
【数９】
0005689839.tif 000010
【００３８】
復号アルゴリズムＤｅｃは２つの部分復号アルゴリズムＤｅｃ１，Ｄｅｃ２および組み合わせアルゴリズムＣｏｍｂからなる。Ｄｅｃｉは各ｉ＝１，２について暗号文ｃとｓｋｉを入力にとり部分復号情報ｔｉを生成する。Ｃｏｍｂは暗号文ｃと一対の（ｔ１，ｔ２）を入力にとり平文ｍを出力する。したがって、復号アルゴリズムＤｅｃは以下の式のように表すことができる。
【００３９】
【数１０】
0005689839.tif 000011
【００４０】
２分割モデルにおいては、秘密鍵ｓｋ１，ｓｋ２はそれぞれ独立に漏洩し、互いに依存した状態で漏洩することはないものとする。２分割モデルにおける公開鍵暗号の詳細は、非特許文献４を参照されたい。
【実施例１】
【００４１】
図１〜５を参照して、この発明の実施例１の公開鍵暗号システム１０の動作を詳細に説明する。図１は、公開鍵暗号システム１０の構成を示すブロック図である。図２は、公開鍵暗号システム１０を構成する装置の構成を示すブロック図である。図３は、公開鍵暗号システム１０が鍵生成する動作を示すフロー図である。図４は、公開鍵暗号システム１０が情報を送受信する動作を示すフロー図である。図５は、公開鍵暗号システム１０の暗号化処理・復号処理を説明する図である。
【００４２】
図１，２を参照して、公開鍵暗号システム１０の構成を説明する。この実施例の公開鍵暗号システム１０は、ネットワーク１と送信装置１００と受信装置２００から構成される。送信装置１００と受信装置２００はネットワーク１に接続される。ネットワーク１は送信装置１００と受信装置２００が相互に通信可能であればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。送信装置１００は、暗号化乱数生成部１１０と情報暗号化部１２０を備える。受信装置２００は、情報鍵対生成部２１１と第１鍵対生成部２１２と第２鍵対生成部２１３と第１鍵暗号化部２２１と第２鍵暗号化部２２２と情報鍵暗号化部２２３と鍵消去部２３０と鍵公開部２４０と鍵記憶部２９０と第１鍵復号部２５１と第２鍵復号部２５２と情報鍵復号部２５３と情報復号部２６０を備える。
【００４３】
図３を参照して、公開鍵暗号システム１０が鍵生成する動作を実際に行われる手続きの順に従って説明する。
【００４４】
受信装置２００の情報鍵対生成部２１１は、入力されたセキュリティパラメータ１λに基づいて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の鍵生成アルゴリズムＧｅｎＣＣＡにより情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０からなる情報鍵対を生成する（Ｓ２１１）。したがって、情報鍵対生成部２１１の処理は、以下の式のように表すことができる。
【００４５】
【数１１】
0005689839.tif 000012
【００４６】
適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式は、既知のいかなる適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式をも用いることができる。例えば、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号（詳細は、「R. Cramer and V. Shoup. “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack.” In Advances in Cryptology-Crypto '98, pages 13-25,1998.」参照）などを適用することができる。ただし、以降の処理において、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式を用いる処理では、すべて同一の公開鍵暗号方式を用いなければならない。
【００４７】
受信装置２００の第１鍵対生成部２１２は、入力されたセキュリティパラメータ１λに基づいて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式の鍵生成アルゴリズムＧｅｎＬＲ−ＣＰＡにより第１鍵暗号化鍵ｐｋ１と第１鍵復号鍵ｓｋ１からなる第１鍵対を生成する（Ｓ２１２）。したがって、第１鍵対生成部２１２の処理は、以下の式のように表すことができる。
【００４８】
【数１２】
0005689839.tif 000013
【００４９】
標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式は、既知のいかなる標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式をも用いることができる。例えば、非特許文献４に記載の鍵カプセル化方式を適用することができる。ただし、以降の処理において、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式を用いる処理では、すべて同一の鍵カプセル化方式を用いなければならない。
【００５０】
受信装置２００の第２鍵対生成部２１３は、入力されたセキュリティパラメータ１λに基づいて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式の鍵生成アルゴリズムＧｅｎＬＲ−ＣＰＡにより第２鍵暗号化鍵ｐｋ２と第２鍵復号鍵ｓｋ２からなる第２鍵対を生成する（Ｓ２１３）。したがって、第２鍵対生成部２１３の処理は、以下の式のように表すことができる。
【００５１】
【数１３】
0005689839.tif 000014
【００５２】
受信装置２００の第１鍵暗号化部２２１は、第１鍵Ｋ１を無作為に生成する。次に、第１鍵Ｋ１を、第１鍵対生成部２１２の生成した第１鍵暗号化鍵ｐｋ１を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式の暗号化アルゴリズムＥｎｃＬＲ−ＣＰＡにより暗号化して、第１鍵暗号文ｃ１を生成する（Ｓ２２１）。したがって、第１鍵暗号化部２２１の処理は、以下の式のように表すことができる。
【００５３】
【数１４】
0005689839.tif 000015
【００５４】
受信装置２００の第２鍵暗号化部２２２は、第２鍵Ｋ２を無作為に生成する。次に、第２鍵Ｋ２を、第２鍵対生成部２１３の生成した第２鍵暗号化鍵ｐｋ２を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式の暗号化アルゴリズムＥｎｃＬＲ−ＣＰＡにより暗号化して、第２鍵暗号文ｃ２を生成する（Ｓ２２２）。したがって、第２鍵暗号化部２２２の処理は、以下の式のように表すことができる。
【００５５】
【数１５】
0005689839.tif 000016
【００５６】
受信装置２００の情報鍵暗号化部２２３は、第１鍵Ｋ１と第２鍵Ｋ２とを入力として、２情報源乱数抽出器により、情報復号鍵ｓｋ０とビット長が等しい乱数Ｋを生成し、乱数Ｋと情報復号鍵ｓｋ０との排他的論理和を計算することで、情報復号鍵暗号文ｅを生成する（Ｓ２２３）。したがって、情報鍵暗号化部２２３の処理は、以下の式のように表すことができる。
【００５７】
【数１６】
0005689839.tif 000017
【００５８】
受信装置２００の鍵消去部２３０は、情報鍵対生成部２１１の生成した情報復号鍵ｓｋ０を消去する（Ｓ２３０）。
【００５９】
受信装置２００の鍵公開部２４０は、情報暗号化鍵ｐｋ０と第１鍵暗号化鍵ｐｋ１と第２鍵暗号化鍵ｐｋ２と第１鍵暗号文ｃ１と第２鍵暗号文ｃ２と情報復号鍵暗号文ｅを一組とした公開鍵ＰＫ：＝（ｐｋ０，ｐｋ１，ｐｋ２，ｃ１，ｃ２，ｅ）を生成する（Ｓ２４０）。生成した公開鍵ＰＫは送信装置１００が利用できるように、送信装置１００が一連の処理を実行する前に送信装置１００へ送信される。ただし、送信装置１００が公開鍵ＰＫを利用できるようになればよく、受信装置２００から送信装置１００へ直接送信しなくともよい。例えば、公開鍵基盤（Public Key Infrastructure）を利用して送信装置１００が受信装置２００の公開鍵ＰＫを取得できるようにしてもよい。
【００６０】
第１鍵対生成部２１２が生成した第１鍵復号鍵ｓｋ１と第２鍵対生成部２１３が生成した第２鍵復号鍵ｓｋ２は、一組の秘密鍵ＳＫ：＝（ｓｋ１，ｓｋ２）として鍵記憶部２９０へ記憶される。
【００６１】
図４を参照して、公開鍵暗号システム１０が情報を送受信する動作を実際に行われる手続きの順に従って説明する。
【００６２】
送信装置１００の暗号化乱数生成部１１０は、暗号化乱数ωを生成する（Ｓ１１０）。
【００６３】
送信装置１００の情報暗号化部１２０は、送信対象である平文ｍを、受信装置２００から受信した公開鍵ＰＫに含まれる情報暗号化鍵ｐｋ０と暗号化乱数生成部１１０の生成した暗号化乱数ωを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の暗号化アルゴリズムＥｎｃＣＣＡにより暗号化して、暗号文ｃを生成する（Ｓ１２０）。次に、生成した暗号文ｃを受信装置２００へ送信する。したがって、情報暗号化部１２０の処理は、以下の式のように表すことができる。
【００６４】
【数１７】
0005689839.tif 000018
【００６５】
受信装置２００の第１鍵復号部２５１は、送信装置１００から暗号文ｃを受信すると、公開鍵ＰＫに含まれる第１鍵暗号文ｃ１を、鍵記憶部２９０に記憶された秘密鍵ＳＫに含まれる第１鍵復号鍵ｓｋ１を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式の復号アルゴリズムＤｅｃＬＲ−ＣＰＡにより復号して、第１鍵Ｋ１を取得する（Ｓ２５１）。したがって、第１鍵復号部２５１の処理は、以下の式のように表すことができる。
【００６６】
【数１８】
0005689839.tif 000019
【００６７】
受信装置２００の第２鍵復号部２５２は、公開鍵ＰＫに含まれる第２鍵暗号文ｃ２を、鍵記憶部２９０に記憶された秘密鍵ＳＫに含まれる第２鍵復号鍵ｓｋ２を用いて、標的確定後秘密鍵漏洩耐性のある鍵カプセル化方式の復号アルゴリズムＤｅｃＬＲ−ＣＰＡにより復号して、第２鍵Ｋ２を取得する（Ｓ２５２）。したがって、第２鍵復号部２５２の処理は、以下の式のように表すことができる。
【００６８】
【数１９】
0005689839.tif 000020
【００６９】
受信装置２００の情報鍵復号部２５３は、第１鍵復号部２５１の復号した第１鍵Ｋ１と第２鍵復号部２５２の復号した第２鍵Ｋ２とを入力として、２情報源乱数抽出器により、乱数Ｋを生成し、乱数Ｋと情報復号鍵暗号文ｅとの排他的論理和を計算することで情報復号鍵ｓｋ０を取得する（Ｓ２５３）。したがって、情報鍵復号部２５３の処理は、以下の式のように表すことができる。
【００７０】
【数２０】
0005689839.tif 000021
【００７１】
受信装置２００の情報復号部２６０は、送信装置１００から受信した暗号文ｃを、情報鍵復号部２５３の復号した情報復号鍵ｓｋ０を用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の復号アルゴリズムＤｅｃＣＣＡにより復号して、平文ｍを取得する（Ｓ２６０）。したがって、情報復号部２６０の処理は、以下の式のように表すことができる。
【００７２】
【数２１】
0005689839.tif 000022
【００７３】
図５（Ａ）に、公開鍵暗号システム１０が用いる公開鍵暗号方式の暗号化処理の概要を示す。図中の記号は明細書中の記号と対応している。点線で囲まれている記号は、その情報が公開情報であることを示している。平文ｍは、情報暗号化鍵ｐｋ０を用いて暗号化され、暗号文ｃが生成される。情報暗号化鍵ｐｋ０と対になる情報復号鍵ｓｋ０は、第１鍵Ｋ１と第２鍵Ｋ２を入力とする２情報源乱数抽出器の出力との排他的論理和を計算することで暗号化され、情報復号鍵暗号文ｅが生成される。情報復号鍵ｓｋ０は情報復号鍵暗号文ｅの生成後に消去される。第１鍵Ｋ１は、第１鍵暗号化鍵ｐｋ１を用いて暗号化され、第１鍵暗号文ｃ１が生成される。第２鍵Ｋ２は、第２鍵暗号化鍵ｐｋ２を用いて暗号化され、第２鍵暗号文ｃ２が生成される。第１鍵暗号文ｃ１と第２鍵暗号文ｃ２と情報復号鍵暗号文ｅは、情報暗号化鍵ｐｋ０、第１鍵暗号化鍵ｐｋ１、第２鍵暗号化鍵ｐｋ２と共に、公開鍵として公開される。
【００７４】
図５（Ｂ）に、公開鍵暗号システム１０が用いる公開鍵暗号方式の復号処理の概要を示す。暗号文ｃは、情報暗号化鍵ｐｋ０と対になる情報復号鍵ｓｋ０を用いて復号され、平文ｍが生成される。情報復号鍵ｓｋ０は、情報復号鍵暗号文ｅを、第１鍵Ｋ１と第２鍵Ｋ２を入力とする２情報源乱数抽出器の出力との排他的論理和を計算することで復号し、取得される。第１鍵Ｋ１は、公開鍵である第１鍵暗号文ｃ１を、秘密鍵である第１鍵復号鍵ｓｋ１を用いて復号し、取得される。第２鍵Ｋ２は、公開鍵である第２鍵暗号文ｃ２を、秘密鍵である第２鍵復号鍵ｓｋ２を用いて復号し、取得される。
【００７５】
このように、暗号文ｃの復号に用いる鍵である情報復号鍵ｓｋ０は、第１鍵Ｋ１と第２鍵Ｋ２により暗号化されているため、暗号文ｃを復号するためには、第１鍵暗号文ｃ１を復号するための第１鍵復号鍵ｓｋ１と、第２鍵暗号文ｃ２を復号するための第２鍵復号鍵ｓｋ２の両方が必要とされる。ここでは２分割モデルにおける公開鍵暗号を想定しているので、第１鍵復号鍵ｓｋ１と第２鍵復号鍵ｓｋ２が互いの情報が依存して漏洩することはない。よって、この実施例の公開鍵暗号方式は秘密鍵漏洩耐性があると言える。サイドチャネル攻撃に対して２つの秘密鍵が同時に漏洩しないようにするためには、例えばそれぞれを異なる物理デバイス（ハードディスクドライブや不揮発性メモリなど）に記憶させるなどの実装を検討する必要がある。
【００７６】
非特許文献４に記載されている従来の標的暗号文確定後の秘密鍵漏洩耐性をもつ公開鍵暗号方式は、送信装置側で第１鍵Ｋ１と第２鍵Ｋ２を生成し、第１鍵Ｋ１と第２鍵Ｋ２を用いて暗号化した暗号文ｃと共に、第１鍵暗号文ｃ１と第２鍵暗号文ｃ２を受信装置へ送信する構成となっていた。一方、この発明は、ＫＥＭとして標的暗号文確定後の秘密鍵漏洩耐性をもつ鍵カプセル化方式を適用することで、送信装置が平文を暗号化する際の公開鍵暗号方式を選択する自由度を高めている。そのためより安全性が高い適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式を適用することができる。その結果、公開鍵暗号方式全体として適応的選択暗号文攻撃に対する安全性を達成している。
【００７７】
この実施例の公開鍵暗号システム１０は、送信装置１００の備える情報暗号化部１２０が平文ｍを適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化するため、適応的選択暗号文攻撃によっても暗号文から平文のいかなる部分情報も得られることがない。また、受信装置２００が備える情報鍵暗号化部２２３が暗号文ｃの復号に用いる秘密鍵である情報復号鍵ｓｋ０を標的確定後秘密鍵漏洩耐性がある鍵カプセル化方式により暗号化し、鍵消去部２４０が情報復号鍵ｓｋ０を消去するため、標的とする暗号文が確定した後に秘密鍵が部分的に漏洩したとしても秘匿性が保証される。すなわち、この実施例の公開鍵暗号システム１０によれば、標的暗号文確定後の秘密鍵漏洩耐性があり、かつ適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により安全に情報を送受信することができる。
【実施例２】
【００７８】
従来の公開鍵暗号方式では、一般的に暗号化実行時に乱数を生成して利用する。この乱数を暗号化乱数と呼ぶ。サイドチャネル攻撃の進展により、暗号化乱数が部分的に漏洩した場合の安全性も考慮する必要があると考えられている。暗号化乱数が部分的に漏洩したとしても安全な公開鍵暗号方式として、「H. Namiki, K. Tanaka, and K. Yasunaga. “Randomness Leakage in the KEM/DEM Framework.” In ProvSec, volume 6980 of Lecture Notes in Computer Science, pages 309-323. Springer, 2011.（参考文献２）」が提案されている。参考文献２の公開鍵暗号方式は、暗号化乱数漏洩耐性があり選択平文攻撃に対して識別不可能な公開鍵暗号方式である。一方で、参考文献２の公開鍵暗号方式は秘密鍵漏洩耐性を有さない。この実施例は、実施例１の標的暗号文確定後の秘密鍵漏洩耐性があり、かつ適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式を、さらに暗号化乱数漏洩耐性を有するように構成したものである。
【００７９】
図６〜８を参照して、この発明の実施例２の公開鍵暗号システム２０の動作を詳細に説明する。図６は、公開鍵暗号システム２０の構成を示すブロック図である。図７は、公開鍵暗号システム２０を構成する装置の構成を示すブロック図である。図８は、公開鍵暗号システム２０が情報を送受信する動作を示すフロー図である。
【００８０】
図６，７を参照して、公開鍵暗号システム２０の構成を説明する。この実施例の公開鍵暗号システム２０は、ネットワーク１と送信装置１０１と受信装置２００から構成される。送信装置１０１と受信装置２００はネットワーク１に接続される。ネットワーク１は送信装置１０１と受信装置２００が相互に通信可能であればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。送信装置１０１は、暗号化乱数生成部１１１と情報暗号化部１２０を備える。したがって、この実施例の公開鍵暗号システム２０と実施例１の公開鍵暗号システム１０とは、送信装置の暗号化乱数生成部の処理が異なることが相違点である。
【００８１】
公開鍵暗号システム２０が鍵生成する動作は、実施例１の公開鍵暗号システム１０が鍵生成する動作と同様であるため、説明は省略する。
【００８２】
図８を参照して、公開鍵暗号システム２０が情報を送受信する動作を実際に行われる手続きの順に従って説明する。
【００８３】
送信装置１０１の暗号化乱数生成部１１１は、乱数ｒ１，ｒ２を生成する（Ｓ１１１１）。次に、乱数ｒ１，ｒ２を入力として、２情報源乱数抽出器により、暗号化乱数ωを生成する（Ｓ１１１２）。したがって、暗号化乱数生成部１１１の処理は、以下の式のように表すことができる。
【００８４】
【数２２】
0005689839.tif 000023
【００８５】
送信装置１０１の情報暗号化部１２０は、送信対象である平文ｍを、受信装置２００から受信した公開鍵ＰＫに含まれる情報暗号化鍵ｐｋ０と暗号化乱数生成部１１１の生成した暗号化乱数ωを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の暗号化アルゴリズムＥｎｃＣＣＡにより暗号化して、暗号文ｃを生成する。次に、生成した暗号文ｃを受信装置２００へ送信する（Ｓ１２０）。したがって、情報暗号化部１２０の処理は、以下の式のように表すことができる。
【００８６】
【数２３】
0005689839.tif 000024
【００８７】
この実施例の公開鍵暗号システム２０は、送信装置１０１の備える情報暗号化部１２０が平文ｍを適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化する際に利用する暗号化乱数ωを、２つの乱数ｒ１，ｒ２を用いて生成するため、暗号化乱数が部分的に漏洩したとしても秘匿性が保証される。すなわち、この実施例の公開鍵暗号システム２０によれば、標的暗号文確定後の秘密鍵漏洩耐性があり、かつ適応的選択暗号文攻撃に対して識別不可能であり、さらに暗号化乱数漏洩耐性を有する公開鍵暗号方式により安全に情報を送受信することができる。
【実施例３】
【００８８】
図９〜１３を参照して、この発明の実施例３の公開鍵暗号システム３０の動作を詳細に説明する。図９は、公開鍵暗号システム３０の構成を示すブロック図である。図１０は、公開鍵暗号システム３０を構成する装置の構成を示すブロック図である。図１１は、公開鍵暗号システム３０が鍵生成する動作を示すフロー図である。図１２は、公開鍵暗号システム３０が情報を送受信する動作を示すフロー図である。図１３は、公開鍵暗号システム３０の暗号化処理・復号処理を説明する図である。
【００８９】
図９，１０を参照して、公開鍵暗号システム３０の構成を説明する。この実施例の公開鍵暗号システム３０は、ネットワーク１と送信装置１０１と受信装置２０１から構成される。送信装置１０１と受信装置２０１はネットワーク１に接続される。ネットワーク１は送信装置１０１と受信装置２０１が相互に通信可能であればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。受信装置２０１は、鍵生成乱数生成部２１４と情報鍵対生成部２１５と鍵消去部２３１と鍵公開部２４１と鍵記憶部２９１と鍵生成乱数復元部２５４と情報鍵対復元部２５５と情報復号部２６０を備える。
【００９０】
図１１を参照して、公開鍵暗号システム３０が鍵生成する動作を実際に行われる手続きの順に従って説明する。
【００９１】
受信装置２０１の鍵生成乱数生成部２１４は、乱数ρ１と乱数ρ２を生成する（Ｓ２１４１）。次に、乱数ρ１と当該乱数ρ２とを入力として、２情報源乱数抽出器により、鍵生成乱数ρを生成する（Ｓ２１４２）。したがって、鍵生成乱数生成部２１４の処理は、以下の式のように表すことができる。
【００９２】
【数２４】
0005689839.tif 000025
【００９３】
受信装置２０１の情報鍵対生成部２１５は、入力されたセキュリティパラメータ１λに基づいて、鍵生成乱数生成部２１４の生成した鍵生成乱数ρを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の鍵生成アルゴリズムＧｅｎＣＣＡにより情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を生成する（Ｓ２１５）。したがって、情報鍵対生成部２１５の処理は、以下の式のように表すことができる。
【００９４】
【数２５】
0005689839.tif 000026
【００９５】
受信装置２０１の鍵消去部２３１は、情報鍵対生成部２１５の生成した情報復号鍵ｓｋ０と鍵生成乱数生成部２１４の生成した鍵生成乱数ρを消去する（Ｓ２３１）。
【００９６】
受信装置２０１の鍵公開部２４１は、情報暗号化鍵ｐｋ０を公開鍵ＰＫ：＝（ｐｋ０）として生成する（Ｓ２４１）。生成した公開鍵ＰＫは送信装置１０１が利用できるように、送信装置１０１が一連の処理を実行する前に送信装置１０１へ送信される。ただし、送信装置１０１が公開鍵ＰＫを利用できるようになればよく、受信装置２０１から送信装置１０１へ直接送信しなくともよい。例えば、公開鍵基盤（Public Key Infrastructure）を利用して送信装置１０１が受信装置２０１の公開鍵ＰＫを取得できるようにしてもよい。
【００９７】
鍵生成乱数生成部２１４が生成した乱数ρ１と乱数ρ２は、一組の秘密鍵ＳＫ：＝（ρ１，ρ２）として鍵記憶部２９１へ記憶される。
【００９８】
図１２を参照して、公開鍵暗号システム３０が情報を送受信する動作を実際に行われる手続きの順に従って説明する。
【００９９】
送信装置１０１の暗号化乱数生成部１１１は、乱数ｒ１，ｒ２を生成する。次に、乱数ｒ１，ｒ２を入力として、２情報源乱数抽出器により、暗号化乱数ωを生成する（Ｓ１１１）。したがって、暗号化乱数生成部１１１の処理は、以下の式のように表すことができる。
【０１００】
【数２６】
0005689839.tif 000027
【０１０１】
送信装置１０１の情報暗号化部１２０は、送信対象である平文ｍを、受信装置２０１から受信した公開鍵ＰＫに含まれる情報暗号化鍵ｐｋ０と暗号化乱数生成部１１１の生成した暗号化乱数ωを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の暗号化アルゴリズムＥｎｃＣＣＡにより暗号化して、暗号文ｃを生成する（Ｓ１２０）。次に、生成した暗号文ｃを受信装置２０１へ送信する。したがって、情報暗号化部１２０の処理は、以下の式のように表すことができる。
【０１０２】
【数２７】
0005689839.tif 000028
【０１０３】
受信装置２０１の鍵生成乱数復元部２５４は、鍵記憶部２９０に記憶された秘密鍵ＳＫに含まれる乱数ρ１と乱数ρ２とを入力として、２情報源乱数抽出器により、鍵生成乱数ρを生成する（Ｓ２５４）。したがって、鍵生成乱数復元部２５４の処理は、以下の式のように表すことができる。
【０１０４】
【数２８】
0005689839.tif 000029
【０１０５】
受信装置２０１の情報鍵対復元部２５５は、入力されたセキュリティパラメータ１λに基づいて、鍵生成乱数復元部２５４の生成した鍵生成乱数ρを用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の鍵生成アルゴリズムＧｅｎＣＣＡにより情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０を取得する（Ｓ２５５）。したがって、情報鍵対復元部２５５の処理は、以下の式のように表すことができる。
【０１０６】
【数２９】
0005689839.tif 000030
【０１０７】
情報鍵対復元部２５５は、情報鍵対生成部２１５と同じ鍵生成アルゴリズムＧｅｎＣＣＡを、同じ鍵生成乱数ωを指定して実行する。そのため、情報鍵対復元部２５５が生成する情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０は、情報鍵対生成部２１５が生成した情報暗号化鍵ｐｋ０と情報復号鍵ｓｋ０と同じものとなる。
【０１０８】
受信装置２０１の情報復号部２６０は、送信装置１０１から受信した暗号文ｃを、情報鍵対復元部２５５の復号した情報復号鍵ｓｋ０を用いて、適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式の復号アルゴリズムＤｅｃＣＣＡにより復号して、平文ｍを取得する（Ｓ２６０）。したがって、情報復号部２６０の処理は、以下の式のように表すことができる。
【０１０９】
【数３０】
0005689839.tif 000031
【０１１０】
図１３（Ａ）に、公開鍵暗号システム３０が用いる公開鍵暗号方式の暗号化処理の概要を示す。図中の記号は明細書中の記号と対応している。点線で囲まれている記号は、その情報が公開情報であることを示している。平文ｍは、情報暗号化鍵ｐｋ０を用いて暗号化され、暗号文ｃが生成される。情報暗号化鍵ｐｋ０は、乱数ρ１と乱数ρ２を入力とする２情報源乱数抽出器の出力である鍵生成乱数ρを用いて生成される。情報暗号化鍵ｐｋ０と対になる情報復号鍵ｓｋ０は生成後そのまま消去される。
【０１１１】
図１３（Ｂ）に、公開鍵暗号システム３０が用いる公開鍵暗号方式の復号処理の概要を示す。暗号文ｃは、情報復号鍵ｓｋ０を用いて復号され、平文ｍが生成される。情報復号鍵ｓｋ０は、秘密鍵ＳＫに含まれる乱数ρ１と乱数ρ２を入力とする２情報源乱数抽出器の出力である鍵生成乱数ρを用いて生成される。上述の通り、同じ鍵生成乱数ρを用いることで、同じ情報復号鍵ｓｋ０を生成することができる。
【０１１２】
このように、暗号文ｃの復号に用いる秘密鍵である情報復号鍵ｓｋ０を取得するためには、乱数ρ１と乱数ρ２の両方が必要とされる。ここでは乱数ρ１と乱数ρ２が同時に漏洩することは想定しないため、この実施例の公開鍵暗号方式は秘密鍵漏洩耐性があると言える。サイドチャネル攻撃に対して２つの秘密鍵が同時に漏洩しないようにするためには、例えばそれぞれを異なる物理デバイス（ハードディスクドライブや不揮発性メモリなど）に記憶させるなどの実装を検討する必要がある。
【０１１３】
この実施例の公開鍵暗号システム３０は、送信装置１０１の備える情報暗号化部１２０が、平文ｍを適応的選択暗号文攻撃に対して識別不可能な公開鍵暗号方式により暗号化するため、適応的選択暗号文攻撃によっても暗号文から平文のいかなる部分情報も得られることがない。また、情報暗号化部１２０が、暗号化する際に利用する暗号化乱数ωを、２つの乱数ｒ１，ｒ２を用いて生成するため、暗号化乱数が部分的に漏洩したとしても秘匿性が保証される。さらに、受信装置２０１が備える情報鍵対生成部２１５が情報復号鍵ｓｋ０を生成する時と、情報鍵対復元部２５５が情報復号鍵ｓｋ０を生成する時に利用する鍵生成乱数ρが２つの乱数ρ１，ρ２によって生成され、乱数ρ１，ρ２が秘密鍵ＳＫとして別々に記憶されており、鍵消去部２４０が情報復号鍵ｓｋ０を消去するため、標的とする暗号文が確定した後に秘密鍵が部分的に漏洩したとしても秘匿性が保証される。すなわち、この実施例の公開鍵暗号システム３０によれば、標的暗号文確定後の秘密鍵漏洩耐性があり、かつ適応的選択暗号文攻撃に対して識別不可能であり、さらに暗号化乱数漏洩耐性を有する公開鍵暗号方式により安全に情報を送受信することができる。
【０１１４】
この実施例の公開鍵暗号方式は安全性に関しては実施例２と同等であるが、ＫＥＭとして標的確定後秘密鍵漏洩耐性がある選択平文攻撃に対して識別不可能な公開鍵暗号方式を利用しないため、実施例２の公開鍵暗号方式よりも計算量が削減でき効率がよい。
【０１１５】
［この発明と従来技術との比較］
図１４に各実施例で利用する公開鍵暗号方式と従来技術との比較を示す。“方式”列は、この明細書における文献の番号、もしくはこの明細書における実施例の番号を表す。“安全性”列は、それぞれの方式が達成している安全性を表す。「ＣＰＡ安全」とは、選択平文攻撃（Chosen Plaintext Attack）に対して識別不可能であることを表す。「ＣＣＡ安全」とは、適応的選択暗号文攻撃（Adaptive Chosen Ciphertext Attack）に対して識別不可能であることを表す。“秘密鍵漏洩耐性”列は、それぞれの方式が達成している秘密鍵漏洩耐性を表す。「なし」は秘密鍵漏洩耐性を有さないことを表す。「標的確定前」は標的暗号文確定前の秘密鍵漏洩耐性を有するが、標的暗号文確定後の秘密鍵漏洩耐性を有さないことを表す。「標的確定後」は標的暗号文確定前後の秘密鍵漏洩耐性を有することを表す。“暗号化乱数”列は、それぞれの方式が達成している暗号化乱数漏洩耐性を表す。「なし」は暗号化乱数漏洩耐性を有さないことを表す。「あり」は暗号化乱数漏洩耐性を有することを表す。
【０１１６】
非特許文献または参考文献には、適応的選択暗号文攻撃に対して識別不可能であり、標的暗号文確定後の秘密鍵漏洩耐性を有する方式は存在しないことがわかる。一方、この発明の実施例はいずれも、適応的選択暗号文攻撃に対して識別不可能であり、標的暗号文確定後の秘密鍵漏洩耐性を有している。また、適応的選択暗号文攻撃に対して識別不可能であり、標的暗号文確定後の秘密鍵漏洩耐性を有し、さらに暗号化乱数漏洩耐性を有する方式は、この発明の実施例２，３しか存在しないことがわかる。なお、実施例２と実施例３は同等の安全性を達成しているが、上述の通り、ＫＥＭの公開鍵暗号方式が異なることによる計算効率の差異がある。
【０１１７】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１１８】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１１９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１２３】
１  ネットワーク
１０，２０，３０  公開鍵暗号システム
１００，１０１  送信装置                
１１０，１１１  暗号化乱数生成部        １２０  情報暗号化部
２００，２０１  受信装置
２１１  情報鍵対生成部                  ２１２  第１鍵対生成部
２１３  第２鍵対生成部                  ２１４  鍵生成乱数生成部
２１５  情報鍵対生成部                  ２２１  第１鍵暗号化部
２２２  第２鍵暗号化部                  ２２３  情報鍵暗号化部
２３０，２３１  鍵消去部                ２４０，２４１  鍵公開部
２５１  第１鍵復号部                    ２５２  第２鍵復号部
２５３  情報鍵復号部                    ２５４  鍵生成乱数復元部
２５５  情報鍵対復元部                  ２６０  情報復号部
２９０  鍵記憶部
【図１】
0005689839.tif 000032
【図２】
0005689839.tif 000033
【図３】
0005689839.tif 000034
【図４】
0005689839.tif 000035
【図５】
0005689839.tif 000036
【図６】
0005689839.tif 000037
【図７】
0005689839.tif 000038
【図８】
0005689839.tif 000039
【図９】
0005689839.tif 000040
【図１０】
0005689839.tif 000041
【図１１】
0005689839.tif 000042
【図１２】
0005689839.tif 000043
【図１３】
0005689839.tif 000044
【図１４】
0005689839.tif 000045