(57)【要約】【課題】本発明の目的は、公開情報だけで暗号文の正当性を検証でき、かつ計算量が比較的少ない暗号方式を提供することである。【解決手段】本発明の公開鍵暗号方法では、使い捨て署名の秘密鍵を、公開鍵暗号の乱数としても用いることで、公開情報だけで暗号文の正当性を検証でき、かつ効率的な暗号方式を実現する。暗号化ステップでは、復号化装置の公開鍵ＰＫを取得し、乱数Ｒを選ぶ。乱数Ｒが使い捨て署名の秘密鍵、かつ公開鍵暗号に用いる乱数である。署名検証鍵Ｕを計算し、平文ｍを暗号化してｗを得、署名Σを乱数Ｒを用いて作成し、暗号文（Ｕ，ｗ，Σ）を得る。復号化ステップでは、暗号文（Ｕ，ｗ，Σ）を受信し、Σが（Ｕ，ｗ）に対する正しい署名であることを署名検証鍵Ｕを用いて検証し、検証が成功すれば秘密鍵ＳＫを用いて（Ｕ，ｗ）から平文ｍを求める。【選択図】図１
2008124988.tif 000002
【特許請求の範囲】
【請求項１】
ｆとｈを一方向性関数、ｍを平文とするときに、
あらかじめ復号化装置が、秘密鍵ＳＫと公開鍵ＰＫを生成して公開鍵ＰＫを公開する公開ステップと、
暗号化装置が、乱数Ｒを選び、署名検証鍵Ｕ＝ｆ(Ｒ)を計算し、ｗ＝ｈ（ＰＫ，Ｒ，ｍ）を計算し、署名Σを乱数Ｒを用いて作成し、暗号文（Ｕ，ｗ，Σ）を送信する暗号化ステップと、
復号化装置が、暗号文（Ｕ，ｗ，Σ）を受信し、Σが（Ｕ，ｗ）に対する正しい署名であることを署名検証鍵Ｕを用いて検証し、検証が成功すれば秘密鍵ＳＫを用いて（Ｕ，ｗ）から平文ｍを求める復号化ステップ
を有する公開鍵暗号方法。
【請求項２】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ∈｛０，１，…，ｐ−１｝、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
あらかじめ復号化装置が、秘密鍵ｘを生成して記録部に記録し、ｇ１とｇ２を選択し、ｙ１＝ｇ１Ｘとｙ２＝ｇ２Ｘを計算し、（ｇ１、ｇ２、ｙ１、ｙ２）を記録部に記録するとともに公開鍵として公開する公開ステップと、
暗号化装置が、｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２，ｍ）、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算し、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号化ステップと、
復号化装置が、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信し、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証し、成立すればｍ＝ＳｙｍＤｅｃ（ｕｘ，ｗ）を計算し、平文ｍを得る復号化ステップ
を有する公開鍵暗号方法。
【請求項３】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
あらかじめ復号化装置が、秘密鍵ｘとｓを生成して記録部に記録し、ｇ１とｇ２を選択し、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、ｚ１＝ｇ１ｓ、ｚ２＝ｇ２ｓを計算し、（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を記録部に記録するとともに公開鍵として公開する公開ステップと、
暗号化装置が、｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２，ｍ）、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算し、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号化ステップと、
復号化装置が、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信し、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証し、成立すればｍ＝ＳｙｍＤｅｃ（ｕｘｖｓ，ｗ）を計算し、平文ｍを得る復号化ステップ
を有する公開鍵暗号方法。
【請求項４】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、Ｇをあらかじめ定めた｛０，１，…，ｐ−１｝２から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
あらかじめ復号化装置が、秘密鍵ｘとｓを生成して記録部に記録し、ｇ１とｇ２を選択し、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘを計算し、（ｇ１、ｇ２、ｙ１、ｙ２）を記録部に記録するとともに公開鍵として公開する公開ステップと、
暗号化装置が、｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２，ｍ）、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算し、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号化ステップと、
復号化装置が、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信し、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証し、成立すればｍ＝ＳｙｍＤｅｃ（ｕｘｖＧ（ｕ，ｖ）ｘ，ｗ）を計算し、平文ｍを得る復号化ステップ
を有する公開鍵暗号方法。
【請求項５】
ｆとｈを一方向性関数、ｍを平文とするときに、
情報を記録する記録部と、
復号化装置の公開鍵ＰＫを取得し、前記記録部に記録する公開鍵取得部と、
乱数Ｒを選び、署名検証鍵Ｕ＝ｆ(Ｒ)を計算する署名検証鍵計算部と、
ｗ＝ｈ（ＰＫ，Ｒ，ｍ）を計算する平文暗号部と、
署名Σを、乱数Ｒを用いて作成する署名計算部と、
暗号文（Ｕ，ｗ，Σ）を送信する暗号文送信部と
を備える暗号化装置。
【請求項６】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘとｙ２＝ｇ２Ｘ、（ｇ１、ｇ２、ｙ１、ｙ２）を復号化装置の公開鍵、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数とするときに、
情報を記録する記録部と、
復号化装置の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を取得し、前記記録部に記録する公開鍵取得部と、
｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｙ１ｒ１ｙ２ｒ２を計算するべき乗演算部と、
ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２，ｍ）を計算する平文暗号部と、
σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算する署名計算部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号文送信部と、
を備える暗号化装置。
【請求項７】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、ｚ１＝ｇ１ｓ、ｚ２＝ｇ２ｓ、（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を復号化装置の公開鍵、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数とするときに、
情報を記録する記録部と、
復号化装置の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を取得し、前記記録部に記録する公開鍵取得部と、
｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２を計算するべき乗演算部と、
ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２，ｍ）を計算する平文暗号部と、
σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算する署名計算部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号文送信部と、
を備える暗号化装置。
【請求項８】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、（ｇ１、ｇ２、ｙ１、ｙ２）を復号化装置の公開鍵、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、Ｇをあらかじめ定めた｛０，１，…，ｐ−１｝２から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数とするときに、
情報を記録する記録部と、
復号化装置の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を取得し、前記記録部に記録する公開鍵取得部と、
｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２を計算するべき乗演算部と、
ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２，ｍ）を計算する平文暗号部と、
σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算する署名計算部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号文送信部と、
を備える暗号化装置。
【請求項９】
ＳＫを秘密鍵、ＰＫを公開鍵、ｆとｈを一方向性関数、Ｒを乱数、Ｕ＝ｆ(Ｒ)を署名検証鍵、ｗ＝ｈ（ＰＫ，Ｒ，ｍ）を平文ｍを暗号化した情報、Σを署名とするときに、
秘密鍵ＳＫ、公開鍵ＰＫなどの情報を記録する記録部と、
暗号文（Ｕ，ｗ，Σ）を受信する暗号文受信部と、
Σが（Ｕ，ｗ）に対する正しい署名であることを、署名検証鍵Ｕを用いて検証する署名検証部と、
秘密鍵ＳＫを用いて（Ｕ，ｗ）から平文ｍを求める平文復号部と
を備える復号化装置。
【請求項１０】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘとｙ２＝ｇ２Ｘ、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
秘密鍵ｘ、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）などの情報を記録する記録部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信する暗号文受信部と、
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証する署名検証部と、
ｍ＝ＳｙｍＤｅｃ（ｕｘ，ｗ）を計算する平文復号部と
を備える復号化装置。
【請求項１１】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、ｚ１＝ｇ１ｓ、ｚ２＝ｇ２ｓ、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
秘密鍵ｘとｓ、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）などの情報を記録する記録部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信する暗号文受信部と、
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証する署名検証部と、
ｍ＝ＳｙｍＤｅｃ（ｕｘｖｓ，ｗ）を計算する平文復号部と
を備える復号化装置。
【請求項１２】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、Ｇをあらかじめ定めた｛０，１，…，ｐ−１｝２から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
秘密鍵ｘとｓ、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）などの情報を記録する記録部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信する暗号文受信部と、
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証する署名検証部と、
ｍ＝ＳｙｍＤｅｃ（ｕｘｖＧ（ｕ，ｖ）ｘ，ｗ）を計算する平文復号部と
を備える復号化装置。
【請求項１３】
ｆとｈを一方向性関数、ｍを平文とするときに、
暗号化装置と復号化装置から構成され、
前記暗号化装置は、
情報を記録する暗号化装置記録部と、
前記復号化装置の公開鍵ＰＫを取得し、前記暗号化装置記録部に記録する公開鍵取得部と、
乱数Ｒを選び、署名検証鍵Ｕ＝ｆ(Ｒ)を計算する署名検証鍵計算部と、
ｗ＝ｈ（ＰＫ，Ｒ，ｍ）を計算する平文暗号部と、
署名Σを、乱数Ｒを用いて作成する署名計算部と、
暗号文（Ｕ，ｗ，Σ）を送信する暗号文送信部と
を備え、
前記復号化装置は、
秘密鍵ＳＫ、公開鍵ＰＫなどの情報を記録する復号化装置記録部と、
暗号文（Ｕ，ｗ，Σ）を受信する暗号文受信部と、
Σが（Ｕ，ｗ）に対する正しい署名であることを、署名検証鍵Ｕを用いて検証する署名検証部と、
秘密鍵ＳＫを用いて（Ｕ，ｗ）から平文ｍを求める平文復号部と
を備える
ことを特徴とする公開鍵暗号システム。
【請求項１４】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘとｙ２＝ｇ２Ｘ、（ｇ１、ｇ２、ｙ１、ｙ２）を復号化装置の公開鍵、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
暗号化装置と復号化装置から構成され、
前記暗号化装置は、
情報を記録する暗号化装置記録部と、
前記復号化装置の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を取得し、前記暗号化装置記録部に記録する公開鍵取得部と、
｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｙ１ｒ１ｙ２ｒ２を計算するべき乗演算部と、
ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２，ｍ）を計算する平文暗号部と、
σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算する署名計算部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号文送信部と、
を備え、
前記復号化装置は、
秘密鍵ｘ、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）などの情報を記録する復号化装置記録部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信する暗号文受信部と、
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証する署名検証部と、
ｍ＝ＳｙｍＤｅｃ（ｕｘ，ｗ）を計算する平文復号部と
を備える
ことを特徴とする公開鍵暗号システム。
【請求項１５】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、ｚ１＝ｇ１ｓ、ｚ２＝ｇ２ｓ、（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を復号化装置の公開鍵、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
暗号化装置と復号化装置から構成され、
前記暗号化装置は、
情報を記録する暗号化装置記録部と、
復号化装置の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を取得し、前記暗号化装置記録部に記録する公開鍵取得部と、
｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２を計算するべき乗演算部と、
ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２，ｍ）を計算する平文暗号部と、
σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算する署名計算部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号文送信部と、
を備え、
前記復号化装置は、
秘密鍵ｘとｓ、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）などの情報を記録する復号化装置記録部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信する暗号文受信部と、
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証する署名検証部と、
ｍ＝ＳｙｍＤｅｃ（ｕｘｖｓ，ｗ）を計算する平文復号部と
を備える
ことを特徴とする公開鍵暗号システム。
【請求項１６】
Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、（ｇ１、ｇ２、ｙ１、ｙ２）を復号化装置の公開鍵、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、Ｇをあらかじめ定めた｛０，１，…，ｐ−１｝２から｛０，１，…，ｐ−１｝への写像、ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とするときに、
暗号化装置と復号化装置から構成され、
前記暗号化装置は、
情報を記録する暗号化装置記録部と、
復号化装置の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を取得し、前記暗号化装置記録部に記録する公開鍵取得部と、
｛０，１，…，ｐ−１｝からランダムにｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２、ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２を計算するべき乗演算部と、
ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２，ｍ）を計算する平文暗号部と、
σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算する署名計算部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を送信する暗号文送信部と、
を備え、
前記復号化装置は、
秘密鍵ｘとｓ、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）などの情報を記録する復号化装置記録部と、
暗号文（ｕ，ｖ，ｗ，σ１，σ２）を受信する暗号文受信部と、
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証する署名検証部と、
ｍ＝ＳｙｍＤｅｃ（ｕｘｖＧ（ｕ，ｖ）ｘ，ｗ）を計算する平文復号部と
を備える
ことを特徴とする公開鍵暗号システム。
【請求項１７】
請求項５から１６のいずれかに記載の装置の各構成部を、コンピュータにより実現するプログラム。
【請求項１８】
請求項１７記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号方法、暗号化装置、復号化装置、公開鍵暗号システム、プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
従来、高い安全性を持つ（能動的攻撃に対しても安全な）公開鍵暗号方式が数多く提案されている。これらのほとんどの暗号方式は、暗号文の正当性（暗号文が、平文から正当な手続きで作られたか）を受信者の秘密鍵を用いて検証する（非特許文献１、非特許文献２）。例えば、このような暗号方式を、受信者の秘密鍵を分散して保有し、復号を分散処理で行うシステムで用いた場合、暗号文の正当性を検証するためには、暗号文を復号しなければならない。つまり、復号のための膨大な計算を行わなければ暗号文の正当性が判断できず、正当でないと判断された場合には、膨大な計算が無駄になる。したがって、受信者の秘密鍵を分散して保有するシステムなどでは、公開情報だけで暗号文の正当性を検証できることが重要である。
【０００３】
公開情報だけで暗号文の正当性を検証できる方法としては、pairing処理を行う方法がある（非特許文献３）。しかし、pairing処理を行う復号化では、一般的な楕円曲線を用いる暗号方式の復号化に比べ、多くの計算量が必要となってしまう。
【非特許文献１】M. Bellare and P. Rogaway, “Optimal asymmetric encryption”, In Advances in Cryptology-Eurocrypt’94, LNCS, Springer-Verlag, pp.92-111, 1994.
【非特許文献２】R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack”, In Advances in Cryptology-Crypto’98, LNCS, Springer-Verlag, pp.13-25, 1998.
【非特許文献３】X. Boyen, Q. Mei, and B. Waters, “Direct Chosen Ciphertext Security from Identity-Based Techniques”, the proceedings of 12th ACM Conference on Computer and Communications Security-CCS 2005, 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、公開情報だけで暗号文の正当性を検証でき、かつ効率的な（計算量が比較的少ない）暗号方式（pairingを用いない暗号方式）を提供することである。
【課題を解決するための手段】
【０００５】
本発明の公開鍵暗号方法では、使い捨て（one-time）署名の秘密鍵を、公開鍵暗号の乱数としても用いることで、公開情報だけで暗号文の正当性を検証でき、かつ効率的な暗号方式を実現する。
【０００６】
以下に基本的な考え方を説明する。まず、ｆとｈを一方向性関数、ｍを平文とする。本発明の公開鍵暗号方法では、公開ステップ、暗号化ステップ、復号化ステップを有する。公開ステップでは、復号化装置が、あらかじめ秘密鍵ＳＫと公開鍵ＰＫを生成して公開鍵ＰＫを公開する。暗号化ステップでは、暗号化装置が、復号化装置の公開鍵ＰＫを取得し、乱数Ｒを選ぶ。乱数Ｒが使い捨て（one-time）署名の秘密鍵、かつ公開鍵暗号に用いる乱数である。署名検証鍵Ｕ＝ｆ(Ｒ)を計算し、ｗ＝ｈ（ＰＫ，Ｒ，ｍ）を計算し、署名Σを乱数Ｒを用いて作成し、暗号文（Ｕ，ｗ，Σ）を復号化装置に送信する。復号化ステップでは、復号化装置が、暗号文（Ｕ，ｗ，Σ）を受信し、Σが（Ｕ，ｗ）に対する正しい署名であることを署名検証鍵Ｕを用いて検証し、検証が成功すれば秘密鍵ＳＫを用いて（Ｕ，ｗ）から平文ｍを求める。
【０００７】
第１の具体例としては、まず、Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ∈｛０，１，…，ｐ−１｝、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像とする。暗号化装置では、乱数Ｒとして、｛０，１，…，ｐ−１｝からランダムに選択されたｒ１、ｒ２、ｔ１、ｔ２を用いる。署名検証鍵Ｕとしてｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２を用い、平文の暗号化には鍵（ＰＫ，Ｒ）としてｙ１ｒ１ｙ２ｒ２を用いる。そして、署名Σとして、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを用いる。復号化装置では、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証することで、暗号文の正当性を検証する。成立すれば、ｕｘを鍵として平文に復号化する。
【０００８】
第２の具体例としては、まず、Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像とする。暗号化装置では、乱数Ｒとして、｛０，１，…，ｐ−１｝からランダムに選択されたｒ１、ｒ２、ｔ１、ｔ２を用いる。署名検証鍵Ｕとしてｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２を用い、平文の暗号化には鍵（ＰＫ，Ｒ）としてｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２を用いる。そして、署名Σとして、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを用いる。復号化装置では、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証することで、暗号文の正当性を検証する。成立すれば、ｕｘｖｓを鍵として平文に復号化する。
【０００９】
第３の具体例としては、まず、Ｇを位数ｐの離散対数問題が難しい有限群、ｇ１とｇ２をＧの生成元、ｘ，ｓ∈｛０，１，…，ｐ−１｝、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像、Ｇをあらかじめ定めた｛０，１，…，ｐ−１｝２から｛０，１，…，ｐ−１｝への写像とする。暗号化装置では、乱数Ｒとして、｛０，１，…，ｐ−１｝からランダムに選択されたｒ１、ｒ２、ｔ１、ｔ２を用いる。署名検証鍵Ｕとしてｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２を用い、平文の暗号化には鍵（ＰＫ，Ｒ）としてｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２を用いる。そして、署名Σとして、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを用いる。復号化装置では、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかを検証することで、暗号文の正当性を検証する。成立すれば、ｕｘｖＧ（ｕ，ｖ）ｘを鍵として平文に復号化する。
【発明の効果】
【００１０】
本発明の公開鍵暗号方法によれば、使い捨て（one-time）署名の秘密鍵を、公開鍵暗号の乱数としても用いるので、適当な関数を選択すれば、公開情報だけで暗号文の正当性を検証できる。また、pairingを用いなくてもよいので、効率的な暗号方式を実現できる。
【発明を実施するための最良の形態】
【００１１】
以下にこの発明の実施形態を、図面を参照して説明する。
［第１実施形態］
図１に本発明の第１実施形態の暗号化装置の機能構成例を、図２に暗号化処理のフローを示す。図３に本発明の第１実施形態の復号化装置の機能構成例を、図４に復号化処理のフローを示す。暗号化装置１００は、公開鍵取得部１１０、署名検証鍵計算部１２０、平文暗号部１３０、署名計算部１４０、暗号文送信部１５０、記録部１９０で構成される。復号化装置２００は、暗号文受信部２１０、署名検証部２２０、平文復号部２３０、秘密鍵・公開鍵生成部２７０、公開鍵公開部２８０、記録部２９０で構成される。また、ｆとｈを一方向性関数、ｍを平文とする。
【００１２】
復号化装置２００は、あらかじめ秘密鍵・公開鍵生成部２７０で秘密鍵ＳＫと公開鍵ＰＫを生成し記録部２９０に記録する。そして、公開鍵公開部２８０で公開鍵ＰＫを公開しておく。また、平文ｍは、あらかじめ暗号化装置１００の記録部１９０に記録させておく。
【００１３】
暗号化装置１００では、公開鍵取得部１１０が、復号化装置２００の公開鍵ＰＫを取得する（Ｓ１１０）。公開鍵ＰＫは必要に応じて記録部１９０に記録される。署名検証鍵計算部１２０は、ランダムに署名生成鍵Ｒ（乱数）を選び、署名検証鍵Ｕ＝ｆ(Ｒ)を計算する（Ｓ１２０）。署名生成鍵Ｒが使い捨て（one-time）署名の秘密鍵、かつ公開鍵暗号に用いる乱数である。平文暗号部１３０は、公開鍵ＰＫと署名生成鍵Ｒを用いて（署名生成鍵Ｒを公開鍵暗号の乱数として用いて）、ｗ＝ｈ（ＰＫ，Ｒ，ｍ）を得る（Ｓ１３０）。署名計算部１４０は、Ｕとｗ（を含む情報）に対する署名Σを、署名生成鍵Ｒを用いて生成する（Ｓ１４０）。暗号文送信部１５０は、（Ｕ，ｗ，Σ）を暗号文として復号化装置２００に送信する（Ｓ１５０）。
【００１４】
復号化装置２００では、暗号文受信部２１０が、暗号文（Ｕ，ｗ，Σ）を暗号化装置１００から受信する（Ｓ２１０）。署名検証部２２０は、署名Σが（Ｕ，ｗ）に対する正しい署名であることを、署名検証鍵Ｕを用いて検証する（Ｓ２２０）。検証が成功すれば、平文復号部２３０が、秘密鍵ＳＫを用いて（Ｕ，ｗ）から平文ｍを求める（Ｓ２３０）。検証が失敗すれば、復号化処理を終了する。
【００１５】
なお、Ｕの一部を、暗号化装置１００と復号化装置２００が記録しておけば、Ｕの残りの部分を個々の暗号化処理では生成すればよいので、暗号化処理の高速化が期待できる。
このように使い捨て（one-time）署名の秘密鍵を、公開鍵暗号の乱数としても用いるので、公開情報だけで暗号文の正当性を検証できる。また、pairingを用いなくてもよいので、効率的な暗号方式を実現できる。
【００１６】
［第２実施形態］
まず、第２実施形態で使ういくつかの記号の説明を行う。第２実施形態では、離散対数問題が難しいような有限群Ｇを用いる。有限群Ｇの位数をｐとする。有限群Ｇの具体例としては、楕円曲線暗号がある（岡本龍明、山本博資、「現代暗号」、産業図書、pp.119-123.）。ｇ１とｇ２をＧの生成元、秘密鍵ｘ∈｛０，１，…，ｐ−１｝とする。また、Ｈをあらかじめ定めた｛０，１，…，ｐ−１｝３から｛０，１，…，ｐ−１｝への写像とする。Ｈには、例えば、ハッシュ関数のような一方向性関数を用いればよい。ｍを平文、ＳｙｍＥｎｃ（Ｋ，ｍ）を、鍵Ｋを用いて平文ｍの暗号化する共通鍵暗号関数、ＳｙｍＤｅｃ（Ｋ，ｃ）を、鍵Ｋを用いて暗号文ｃの復号化する共通鍵復号関数とする。
【００１７】
図５に第２実施形態の暗号化装置の機能構成例を、図６に暗号化処理のフローを示す。図７に第２実施形態の復号化装置の機能構成例を、図８に復号化処理のフローを示す。暗号化装置３００は、公開鍵取得部３１０、べき乗演算部３２０、平文暗号部３３０、署名計算部３４０、暗号文送信部３５０、記録部３９０で構成される。署名計算部３４０は、Ｈ計算手段３４１と剰余加算手段３４２を有している。復号化装置４００は、暗号文受信部４１０、署名検証部４２０、平文復号部４３０、秘密鍵・公開鍵生成部４７０、公開鍵公開部４８０、記録部４９０で構成される。平文復号部４３０は、べき乗演算手段４３１と復号化手段４３２を有している。
【００１８】
復号化装置４００は、あらかじめ秘密鍵・公開鍵生成部４７０で秘密鍵ｘを生成して記録部４９０に記録する。また、秘密鍵・公開鍵生成部４７０は、ｇ１とｇ２を選択し、ｙ１＝ｇ１Ｘとｙ２＝ｇ２Ｘを計算し、（ｇ１、ｇ２、ｙ１、ｙ２）を公開鍵として記録部４９０に記録する。公開鍵公開部４８０は、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を公開する。また、平文ｍは、あらかじめ暗号化装置３００の記録部３９０に記録しておく。
【００１９】
暗号化装置３００では、公開鍵取得部３１０が、復号化装置４００の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を取得する（Ｓ３１０）。公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）は記録部３９０に記録される。べき乗演算部３２０は、｛０，１，…，ｐ−１｝からランダムに署名生成鍵ｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２を計算する（Ｓ３２０）。べき乗演算部３２０は、ｙ１ｒ１ｙ２ｒ２も計算する。（ｕ，ｖ）が署名検証鍵、ｙ１ｒ１ｙ２ｒ２が共通鍵暗号関数ＳｙｍＥｎｃの鍵である。署名生成鍵（ｒ１、ｒ２、ｔ１、ｔ２）が使い捨て（one-time）署名の秘密鍵、かつ公開鍵暗号に用いる乱数である。平文暗号部３３０は、ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２，ｍ）の計算により、ｗを得る（Ｓ３３０）。署名計算部３４０は、Ｈ計算手段３４１で、Ｈ（ｕ，ｖ，ｗ）を計算する（Ｓ３４１）。剰余加算手段３４２は、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算し、署名（σ１，σ２）を生成する（Ｓ３４２）。この処理で、署名生成鍵（ｒ１、ｒ２、ｔ１、ｔ２）が使い捨て（one-time）署名の秘密鍵として用いられている。暗号文送信部３５０は、（ｕ，ｖ，ｗ，σ１，σ２）を暗号文として復号化装置４００に送信する（Ｓ３５０）。
【００２０】
復号化装置４００では、暗号文受信部４１０が、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を暗号化装置３００から受信する（Ｓ４１０）。署名検証部４２０は、署名（σ１，σ２）が（ｕ，ｖ，ｗ）に対する正しい署名であること（暗号文の正当性）を、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかで検証する（Ｓ４２０）。成立すれば、平文復号部４３０のべき乗演算手段が、ｕｘを計算する（Ｓ４３１）。そして、復号化手段４３２が、ｍ＝ＳｙｍＤｅｃ（ｕｘ，ｗ）を計算し、平文ｍを得る（Ｓ４３２）。ステップＳ４２０が成立しなければ、復号化処理を終了する。
【００２１】
上述の処理で、暗号と復号が正しく行われることを説明する。ｕ，ｖ，σ１，σ２が正しく作られていれば、次のようにステップＳ４２０の式（暗号文の正当性を検証する式）が成り立つ。
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１ｒ１ｇ２ｒ２（ｇ１ｔ１ｇ２ｔ２）Ｈ（ｕ，ｖ，ｗ）
＝ｇ１ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１ｇ２ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２
＝ｇ１σ１ｇ２σ２
この式が成り立つならば、ステップＳ３３０で用いた共通鍵暗号関数ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２，ｍ）の鍵ｙ１ｒ１ｙ２ｒ２は、次のように変形できる。
ｙ１ｒ１ｙ２ｒ２＝ｇ１ｘｒ１ｇ２ｘｒ２
＝（ｇ１ｒ１ｇ２ｒ２）ｘ
＝ｕｘ
つまり、ステップＳ４３２で用いた共通鍵復号関数ＳｙｍＤｅｃ（ｕｘ，ｃ）の鍵ｕｘは、共通鍵暗号関数ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２，ｍ）の鍵と同じである。したがって、上述の処理で暗号と復号が正しく行われる。
【００２２】
なお、ｕとｖのいずれか一方を、暗号化装置３００と復号化装置４００が記録しておき、ｕとｖの他方を個々の暗号化処理では生成すれば、暗号化処理の高速化が期待できる。
このように使い捨て（one-time）署名の秘密鍵を、公開鍵暗号の乱数としても用いるので、公開情報だけで暗号文の正当性を検証できる。また、pairingを用いなくてもよいので、効率的な暗号方式を実現できる。
【００２３】
［変形例１］
第２実施形態の変形例１では、さらに、ｓ∈｛０，１，…，ｐ−１｝を復号化装置の秘密鍵として用いる。その他の記号の意味は第２実施形態と同じである。
【００２４】
図９に変形例１の暗号化装置の機能構成例を、図１０に暗号化処理のフローを示す。図１１に変形例１の復号化装置の機能構成例を、図１２に復号化処理のフローを示す。暗号化装置５００は、公開鍵取得部５１０、べき乗演算部５２０、平文暗号部５３０、署名計算部５４０、暗号文送信部５５０、記録部５９０で構成される。署名計算部５４０は、Ｈ計算手段５４１と剰余加算手段５４２を有している。復号化装置６００は、暗号文受信部６１０、署名検証部６２０、平文復号部６３０、秘密鍵・公開鍵生成部６７０、公開鍵公開部６８０、記録部６９０で構成される。平文復号部６３０は、べき乗演算手段６３１と復号化手段６３２を有している。
【００２５】
復号化装置６００は、あらかじめ秘密鍵・公開鍵生成部６７０で秘密鍵ｘとｓを生成して記録部６９０に記録する。また、秘密鍵・公開鍵生成部６７０は、ｇ１とｇ２を選択し、ｙ１＝ｇ１Ｘ、ｙ２＝ｇ２Ｘ、ｚ１＝ｇ１ｓ、ｚ２＝ｇ２ｓを計算し、（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を公開鍵として記録部６９０に記録する。公開鍵公開部６８０は、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を公開する。また、平文ｍは、あらかじめ暗号化装置５００の記録部５９０に記録しておく。
【００２６】
暗号化装置５００では、公開鍵取得部５１０が、復号化装置６００の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）を取得する（Ｓ５１０）。公開鍵（ｇ１、ｇ２、ｙ１、ｙ２、ｚ１、ｚ２）は記録部５９０に記録される。べき乗演算部５２０は、｛０，１，…，ｐ−１｝からランダムに署名生成鍵ｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２を計算する（Ｓ５２０）。べき乗演算部５２０は、ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２も計算する。（ｕ，ｖ）が署名検証鍵、ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２が共通鍵暗号関数ＳｙｍＥｎｃの鍵である。署名生成鍵（ｒ１、ｒ２、ｔ１、ｔ２）が使い捨て（one-time）署名の秘密鍵、かつ公開鍵暗号に用いる乱数である。平文暗号部５３０は、ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２，ｍ）を計算し、ｗを得る（Ｓ５３０）。署名計算部５４０は、Ｈ計算手段５４１で、Ｈ（ｕ，ｖ，ｗ）を計算する（Ｓ５４１）。剰余加算手段５４２は、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算し、署名（σ１，σ２）を生成する（Ｓ５４２）。この処理で、署名生成鍵（ｒ１、ｒ２、ｔ１、ｔ２）が使い捨て（one-time）署名の秘密鍵として用いられている。暗号文送信部５５０は、（ｕ，ｖ，ｗ，σ１，σ２）を暗号文として復号化装置６００に送信する（Ｓ５５０）。
【００２７】
復号化装置６００では、暗号文受信部６１０が、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を暗号化装置５００から受信する（Ｓ６１０）。署名検証部６２０は、署名（σ１，σ２）が（ｕ，ｖ，ｗ）に対する正しい署名であること（暗号文の正当性）を、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかで検証する（Ｓ６２０）。成立すれば、平文復号部６３０のべき乗演算手段が、ｕｘｖｓを計算する（Ｓ６３１）。そして、復号化手段６３２が、ｍ＝ＳｙｍＤｅｃ（ｕｘｖｓ，ｗ）を計算し、平文ｍを得る（Ｓ６３２）。ステップＳ６２０が成立しなければ、復号化処理を終了する。
【００２８】
上述の処理で、暗号と復号が正しく行われることを説明する。ｕ，ｖ，σ１，σ２が正しく作られていれば、次のようにステップＳ６２０の式（暗号文の正当性を検証する式）が成り立つ。
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１ｒ１ｇ２ｒ２（ｇ１ｔ１ｇ２ｔ２）Ｈ（ｕ，ｖ，ｗ）
＝ｇ１ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１ｇ２ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２
＝ｇ１σ１ｇ２σ２
この式が成り立つならば、ステップＳ５３０で用いた共通鍵暗号関数ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２，ｍ）の鍵ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２は、次のように変形できる。
ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２＝ｇ１ｘｒ１ｇ２ｘｒ２ｇ１ｓｒ１ｇ２ｓｒ２
＝（ｇ１ｒ１ｇ２ｒ２）ｘ（ｇ１ｔ１ｇ２ｔ２）ｓ
＝ｕｘｖｓ
つまり、ステップＳ６３２で用いた共通鍵復号関数ＳｙｍＤｅｃ（ｕｘｖｓ，ｃ）の鍵ｕｘｖｓは、共通鍵暗号関数ＳｙｍＥｎｃ（ｙ１ｒ１ｙ２ｒ２ｚ１ｔ１ｚ２ｔ２，ｍ）の鍵と同じである。したがって、上述の処理で暗号と復号が正しく行われる。
【００２９】
なお、ｕとｖのいずれか一方を、暗号化装置５００と復号化装置６００が記録しておき、ｕとｖの他方を個々の暗号化処理では生成すれば、暗号化処理の高速化が期待できる。
本変形例でも、使い捨て（one-time）署名の秘密鍵を、公開鍵暗号の乱数としても用いるので、公開情報だけで暗号文の正当性を検証できる。また、pairingを用いなくてもよいので、効率的な暗号方式を実現できる。
【００３０】
［変形例２］
第２実施形態の変形例２では、さらに、Ｇをあらかじめ定めた｛０，１，…，ｐ−１｝２から｛０，１，…，ｐ−１｝への写像とする。Ｇも、例えばハッシュ関数のような一方向性関数を用いればよい。その他の記号の意味は第２実施形態と同じである。
【００３１】
図１３に変形例２の暗号化装置の機能構成例を、図１４に暗号化処理のフローを示す。図１５に変形例２の復号化装置の機能構成例を、図１６に復号化処理のフローを示す。暗号化装置７００は、公開鍵取得部７１０、べき乗演算部７２０、平文暗号部７３０、署名計算部７４０、暗号文送信部７５０、記録部７９０で構成される。べき乗演算部７２０は、Ｇ計算手段も有している。署名計算部７４０は、Ｈ計算手段７４１と剰余加算手段７４２を有している。復号化装置８００は、暗号文受信部８１０、署名検証部８２０、平文復号部８３０、秘密鍵・公開鍵生成部８７０、公開鍵公開部８８０、記録部８９０で構成される。平文復号部６３０は、Ｇ計算手段８３１、べき乗演算手段８３２、復号化手段８３３を有している。
【００３２】
復号化装置８００は、あらかじめ秘密鍵・公開鍵生成部８７０で秘密鍵ｘとｓを生成して記録部８９０に記録する。また、秘密鍵・公開鍵生成部８７０は、ｇ１とｇ２を選択し、ｙ１＝ｇ１Ｘとｙ２＝ｇ２Ｘを計算し、（ｇ１、ｇ２、ｙ１、ｙ２）を公開鍵として記録部８９０に記録する。公開鍵公開部８８０は、公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を公開する。また、平文ｍは、あらかじめ暗号化装置７００の記録部７９０に記録しておく。
【００３３】
暗号化装置７００では、公開鍵取得部７１０が、復号化装置８００の公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）を取得する（Ｓ７１０）。公開鍵（ｇ１、ｇ２、ｙ１、ｙ２）は記録部７９０に記録される。べき乗演算部７２０は、｛０，１，…，ｐ−１｝からランダムに署名生成鍵ｒ１、ｒ２、ｔ１、ｔ２を選び、ｕ＝ｇ１ｒ１ｇ２ｒ２、ｖ＝ｇ１ｔ１ｇ２ｔ２を計算する（Ｓ７２０）。べき乗演算部７２０のＧ計算手段７２１はＧ（ｕ，ｖ）を計算する。そして、べき乗演算部７２０は、さらにｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２も計算する。（ｕ，ｖ）が署名検証鍵、ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２が共通鍵暗号関数ＳｙｍＥｎｃの鍵である。署名生成鍵（ｒ１、ｒ２、ｔ１、ｔ２）が使い捨て（one-time）署名の秘密鍵、かつ公開鍵暗号に用いる乱数である。平文暗号部７３０は、ｗ＝ＳｙｍＥｎｃ（ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２，ｍ）の計算により、ｗを得る（Ｓ７３０）。署名計算部７４０は、Ｈ計算手段７４１で、Ｈ（ｕ，ｖ，ｗ）を計算する（Ｓ７４１）。剰余加算手段７４２は、σ１＝ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１  ｍｏｄｐ、σ２＝ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２  ｍｏｄｐを計算し、署名（σ１，σ２）を生成する（Ｓ７４２）。この処理で、署名生成鍵（ｒ１、ｒ２、ｔ１、ｔ２）が使い捨て（one-time）署名の秘密鍵として用いられている。暗号文送信部７５０は、（ｕ，ｖ，ｗ，σ１，σ２）を暗号文として復号化装置８００に送信する（Ｓ７５０）。
【００３４】
復号化装置８００では、暗号文受信部８１０が、暗号文（ｕ，ｖ，ｗ，σ１，σ２）を暗号化装置７００から受信する（Ｓ８１０）。署名検証部８２０は、署名（σ１，σ２）が（ｕ，ｖ，ｗ）に対する正しい署名であること（暗号文の正当性）を、ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１σ１ｇ２σ２が成立するかで検証する（Ｓ８２０）。成立すれば、平文復号部８３０のＧ計算手段８３１がＧ（ｕ，ｖ）を計算し（Ｓ８３１）、べき乗演算手段８３２がｕｘｖＧ（ｕ，ｖ）ｘを計算する（Ｓ８３２）。そして、復号化手段８３３が、ｍ＝ＳｙｍＤｅｃ（ｕｘｖＧ（ｕ，ｖ）ｘ，ｗ）を計算し、平文ｍを得る（Ｓ８３３）。ステップＳ８２０が成立しなければ、復号化処理を終了する。
【００３５】
上述の処理で、暗号と復号が正しく行われることを説明する。ｕ，ｖ，σ１，σ２が正しく作られていれば、次のようにステップＳ８２０の式（暗号文の正当性を検証する式）が成り立つ。
ｕｖＨ（ｕ，ｖ，ｗ）＝ｇ１ｒ１ｇ２ｒ２（ｇ１ｔ１ｇ２ｔ２）Ｈ（ｕ，ｖ，ｗ）
＝ｇ１ｒ１＋Ｈ（ｕ，ｖ，ｗ）ｔ１ｇ２ｒ２＋Ｈ（ｕ，ｖ，ｗ）ｔ２
＝ｇ１σ１ｇ２σ２
この式が成り立つならば、ステップＳ７３０で用いた共通鍵暗号関数ＳｙｍＥｎｃ（ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２，ｍ）の鍵ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２は、次のように変形できる。
ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２＝ｇ１ｘ（ｒ１＋Ｇ（ｕ，ｖ）ｔ１）ｇ２ｘ（ｒ２＋Ｇ（ｕ，ｖ）ｔ２）
＝（ｇ１ｒ１ｇ２ｒ２）ｘ（ｇ１ｔ１ｇ２ｔ２）Ｇ（ｕ，ｖ）ｘ
＝ｕｘｖＧ（ｕ，ｖ）ｘ
つまり、ステップＳ８３２で用いた共通鍵復号関数ＳｙｍＤｅｃ（ｕｘｖＧ（ｕ，ｖ）ｘ，ｃ）の鍵ｕｘｖＧ（ｕ，ｖ）ｘは、共通鍵暗号関数ＳｙｍＥｎｃ（ｙ１ｒ１＋Ｇ（ｕ，ｖ）ｔ１ｙ２ｒ２＋Ｇ（ｕ，ｖ）ｔ２，ｍ）の鍵と同じである。したがって、上述の処理で暗号と復号が正しく行われる。
【００３６】
なお、ｕとｖのいずれか一方を、暗号化装置７００と復号化装置８００が記録しておき、ｕとｖの他方を個々の暗号化処理では生成すれば、暗号化処理の高速化が期待できる。
【００３７】
本変形例でも使い捨て（one-time）署名の秘密鍵を、公開鍵暗号の乱数としても用いるので、公開情報だけで暗号文の正当性を検証できる。また、pairingを用いなくてもよいので、効率的な暗号方式を実現できる。
【００３８】
なお、上記の実施形態は、図１７に示すコンピュータの記録部２０２０に、上記方法の各ステップを実行させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などに動作させることで実施できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【００３９】
【図１】第１実施形態の暗号化装置の機能構成例を示す図。
【図２】第１実施形態の暗号化装置の処理フローを示す図。
【図３】第１実施形態の復号化装置の機能構成例を示す図。
【図４】第１実施形態の復号化装置の処理フローを示す図。
【図５】第２実施形態の暗号化装置の機能構成例を示す図。
【図６】第２実施形態の暗号化装置の処理フローを示す図。
【図７】第２実施形態の復号化装置の機能構成例を示す図。
【図８】第２実施形態の復号化装置の処理フローを示す図。
【図９】変形例１の暗号化装置の機能構成例を示す図。
【図１０】変形例１の暗号化装置の処理フローを示す図。
【図１１】変形例１の復号化装置の機能構成例を示す図。
【図１２】変形例１の復号化装置の処理フローを示す図。
【図１３】変形例２の暗号化装置の機能構成例を示す図。
【図１４】変形例２の暗号化装置の処理フローを示す図。
【図１５】変形例２の復号化装置の機能構成例を示す図。
【図１６】変形例２の復号化装置の処理フローを示す図。
【図１７】コンピュータの機能構成例を示す図。
【図１】
2008124988.tif 000003
【図２】
2008124988.tif 000004
【図３】
2008124988.tif 000005
【図４】
2008124988.tif 000006
【図５】
2008124988.tif 000007
【図６】
2008124988.tif 000008
【図７】
2008124988.tif 000009
【図８】
2008124988.tif 000010
【図９】
2008124988.tif 000011
【図１０】
2008124988.tif 000012
【図１１】
2008124988.tif 000013
【図１２】
2008124988.tif 000014
【図１３】
2008124988.tif 000015
【図１４】
2008124988.tif 000016
【図１５】
2008124988.tif 000017
【図１６】
2008124988.tif 000018
【図１７】
2008124988.tif 000019