【手続補正書】
【提出日】平成19年1月23日(2007.1.23)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１以上の秘密値Ｑ1，Ｑ2，…Ｑmとそれぞれの公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）との集合を得るステップであって、ＱiとＧi（ｉ＝１，・・・，ｍ）の値のそれぞれのペアは、方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎ、または方程式Ｇi≡Ｑivｍｏｄ  ｎのいずれかを確認するものであり、ｎはｆ個の素因数ｐ1，ｐ2，…ｐf（ｆは２以上）の積に等しい公開係数であり、これらの素因数の少なくとも２つは互いに異なっており、ｖはｖ＝２kとなる公開指数であり、ｋは１より大きい機密保護パラメータであり、それぞれの公開値Ｇiは、（ｉ＝１，・・・，ｍについて）Ｇｉ≡ｇi2ｍｏｄ  ｎとなるものであり、ｇi（ｉ＝１，・・・，ｍ）は、１より大きい整数値であって前記素因数ｐ1，ｐ2，…ｐfのそれぞれよりも小さい基数であり、ｇiはモジュロｎの整数環の非平方剰余である、集合を得るステップと、
認証方法または署名方法において、少なくとも前記秘密値Ｑ1，Ｑ2，…Ｑmを使用するステップと
を含んでなる、コンピュータに実行される方法。
【請求項２】
Ｒ＝ｒvｍｏｄ ｎとなるように計算された値を有するコミットメントＲをデモンストレータから受信するステップであって、ここで、ｒは、該デモンストレータによって０＜ｒ＜ｎとなるようにランダムに選択された整数であるステップと、
ｍ個のチャレンジｄ1, ｄ2，・・・ｄmをランダムに選択するステップと、
前記チャレンジｄ1, ｄ2，・・・ｄmを前記デモンストレータに送信するステップと、
前記デモンストレータからの応答Ｄを受信するステップであって、該応答Ｄは、
【数１】
2003513480.tif 000001
となるように計算された値を有するものであるステップと、
【数２】
2003513480.tif 000002
（ｉ＝１，・・・，ｍ）が前記コミットメントＲに等しい値を前記応答Ｄが有する場合には、前記デモンストレータが真正であると決定するステップであって、ここで、Ｇi・Ｑiv＝１ｍｏｄ  ｎの場合にはεi＝＋１であり、Ｇi＝Ｑivｍｏｄ  ｎの場合にはεi＝−１である、決定するステップと
を含んでなる、認証されるエンティティを許可するための請求項１に記載のコンピュータに実行される方法。
【請求項３】
デモンストレータからコミットメントＲを受信するステップであって、該コミットメントＲは、コミットメント要素Ｒj（ｊ＝１，・・・，ｆ）の集合からチャイニーズ剰余を用いて計算された値を有し、各コミットメント要素Ｒjは、Ｒj＝ｒjvｍｏｄ  ｐjとなる値を有するものであるステップと
ｍ個のチャレンジｄ1, ｄ2，・・・ｄmをランダムに選択するステップと、
前記チャレンジｄ1, ｄ2，・・・ｄmを前記デモンストレータに送信するステップと、
前記デモンストレータからの応答Ｄを受信するステップであって、該応答Ｄは、チャイニーズ剰余を用いて応答要素Ｄjの集合から計算され、該応答要素Ｄjは、ｉ＝１，・・・ｍおよびｊ＝１，・・・ｆについてＱi,j＝Ｑiｍｏｄ ｐjであり、ｊ＝１，・・・，ｆについて
【数３】
2003513480.tif 000003
となるように計算された値を有するものであるステップと、
【数４】
2003513480.tif 000004
（ｉ＝１，・・・，ｍ）が前記コミットメントＲに等しい値を前記応答Ｄが有する場合には、前記デモンストレータが真正であると決定するステップであって、ここで、Ｇi・Ｑiv＝１ｍｏｄ  ｎの場合にはεi＝＋１であり、Ｇi＝Ｑivｍｏｄ  ｎの場合にはεi＝−１である、決定するステップと
をさらに含む、認証されるエンティティを許可するための請求項１に記載のコンピュータに実行される方法。
【請求項４】
デモンストレータからトークンＴを受信するステップであって、該トークンＴは、Ｔ＝ｈ（Ｍ，Ｒ）となる値を有し、ここで、ｈはハッシュ関数であり、Ｍは前記デモンストレータから受信したメッセージであり、Ｒは、Ｒ＝ｒvｍｏｄ  ｎとなるように計算された値を有しており、ここで、ｒは、前記デモンストレータによってランダムに選択された整数（０＜ｒ＜ｎ）である、ステップと、
ｍ個のチャレンジｄ1, ｄ2，・・・ｄmをランダムに選択するステップと、
前記チャレンジｄ1, ｄ2，・・・ｄmを前記デモンストレータに送信するステップと、
前記デモンストレータからの応答Ｄを受信するステップであって、該応答Ｄは、
【数５】
2003513480.tif 000005
となるように計算された値を有するものであるステップと、
【数６】
2003513480.tif 000006
（ｉ＝１，・・・，ｍ）が前記トークンＴに等しい値を前記応答Ｄが有する場合には、前記メッセージＭが真正であると決定するステップであって、ここで、Ｇi・Ｑiv＝１ｍｏｄ  ｎの場合にはεi＝＋１であり、Ｇi＝Ｑivｍｏｄ  ｎの場合にはεi＝−１である、決定するステップと
をさらに含む、認証されるエンティティを許可するための請求項１に記載のコンピュータに実行される方法。
【請求項５】
デモンストレータからトークンＴを受信するステップであって、該トークンＴは、Ｔ＝ｈ（Ｍ，Ｒ）となる値を有し、ここで、ｈはハッシュ関数であり、Ｍは前記デモンストレータから受信したメッセージであり、Ｒは、コミットメント要素Ｒj（ｊ＝１，・・・，ｆ）の集合からチャイニーズ剰余を用いて計算された値を有するコミットメントであり、各コミットメント要素ＲjはＲj＝ｒjvｍｏｄ  ｐjとなる値を有し、ここで、ｒjは、前記デモンストレータによってランダムに選択され、０＜ｒj＜ｐjとなる整数である、ステップと、
ｍ個のチャレンジｄ1, ｄ2，・・・ｄmをランダムに選択するステップと、
前記チャレンジｄ1, ｄ2，・・・ｄmを前記デモンストレータに送信するステップと、
前記デモンストレータからの応答Ｄを受信するステップであって、該応答Ｄは、チャイニーズ剰余を用いて応答要素Ｄjの集合から計算され、該応答要素Ｄjは、ｉ＝１，・・・ｍおよびｊ＝１，・・・ｆについてＱi,j＝Ｑiｍｏｄ ｐjであり、ｊ＝１，・・・，ｆについて
【数７】
2003513480.tif 000007
となるように計算された値を有するものであるステップと、
【数８】
2003513480.tif 000008
（ｉ＝１，・・・，ｍ）が前記トークンＴに等しい値を前記応答Ｄが有する場合には、前記メッセージＭが真正であると決定するステップであって、ここで、Ｇi・Ｑiv＝１ｍｏｄ  ｎの場合にはεi＝＋１であり、Ｇi＝Ｑivｍｏｄ  ｎの場合にはεi＝−１である、決定するステップと
をさらに含む、認証されるエンティティを許可するための請求項１に記載のコンピュータに実行される方法。
【請求項６】
前記チャレンジが、ｉ＝１，・・・ｍについて、０≦ｄi≦２k−１である、請求項２から５のいずれかに記載のコンピュータに実行される方法。
【請求項７】
署名されたメッセージＭを記録するステップと、
ｉ＝１，・・・，ｍについて、０＜ｒi＜ｎとなるｍ個の整数ｒiをランダムに選択するステップと、
ｉ＝１，・・・，ｍについて、Ｒｉ＝Ｒivｍｏｄ  ｎとなる値を有するコミットメントＲiを計算するステップと、
Ｔ＝ｈ（Ｍ、Ｒ1，Ｒ2，・・・，Ｒm）となる値を有するトークンＴを計算するステップと、ここで、ｈは、ｍビットからなるバイナリトレインを生成するハッシュ関数であり、
前記トークンＴのいくつかのビットを識別するステップと、
ｉ＝１，・・・，ｍについて、応答
【数９】
2003513480.tif 000009
を計算するステップと
をさらに含む、認証されるエンティティを許可するための請求項１に記載のコンピュータに実行される方法。
【請求項８】
前記トークンＴおよび前記応答Ｄi（ｉ＝１，・・・，ｍ）を集めるステップと、
【数１０】
2003513480.tif 000010
（ｉ＝１，・・・，ｍ）が前記トークンＴに等しい値を前記応答Ｄが有する場合には、前記メッセージＭが真正であると決定するステップであって、ここで、Ｇi・Ｑiv＝１ｍｏｄ  ｎの場合にはεi＝＋１であり、Ｇi＝Ｑivｍｏｄ  ｎの場合にはεi＝−１である、決定するステップと
をさらに含む、認証されるエンティティを許可するための請求項７に記載のコンピュータに実行される方法。
【請求項９】
１以上の秘密値Ｑ1，Ｑ2，…Ｑmとそれぞれの公開値Ｇ1，Ｇ2，…Ｇm（ｍは１以上）との集合を得るステップであって、ＱiとＧi（ｉ＝１，・・・，ｍ）の値のそれぞれのペアは、方程式Ｇi・Ｑiv≡１ｍｏｄ  ｎ、または方程式Ｇi≡Ｑivｍｏｄ  ｎのいずれかを確認するものであり、ｎはｆ個の素因数ｐ1，ｐ2，…ｐf（ｆは２以上）の積に等しい公開係数であり、これらの素因数の少なくとも２つは互いに異なっており、ｖはｖ＝２kとなる公開指数であり、ｋは１より大きい機密保護パラメータであり、それぞれの公開値Ｇiは、（ｉ＝１，・・・，ｍについて）Ｇｉ≡ｇi2ｍｏｄ  ｎとなるものであり、ｇi（ｉ＝１，・・・，ｍ）は、１より大きい整数値であって前記素因数ｐ1，ｐ2，…ｐfのそれぞれよりも小さい基数であり、ｇiはモジュロｎの整数環の非平方剰余である、集合を得るステップと、
認証方法または署名方法において、少なくとも前記秘密値Ｑ1，Ｑ2，…Ｑmを使用するステップと
をプロセッサに実行させる命令を記憶しているコンピュータに読み取り可能な記録媒体。