JPH11231781A - 認証方法および装置 - Google Patents

認証方法および装置

Info

Publication number
JPH11231781A
JPH11231781A JP10029552A JP2955298A JPH11231781A JP H11231781 A JPH11231781 A JP H11231781A JP 10029552 A JP10029552 A JP 10029552A JP 2955298 A JP2955298 A JP 2955298A JP H11231781 A JPH11231781 A JP H11231781A
Authority
JP
Japan
Prior art keywords
document
information
ticket
calculating
message
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP10029552A
Other languages
English (en)
Other versions
JP3812123B2 (ja
Inventor
Taro Terao
太郎 寺尾
Rumiko Kakehi
るみ子 筧
Hitoki Kiyoujima
仁樹 京嶋
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujifilm Business Innovation Corp
Original Assignee
Fuji Xerox Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fuji Xerox Co Ltd filed Critical Fuji Xerox Co Ltd
Priority to JP02955298A priority Critical patent/JP3812123B2/ja
Priority to US09/240,876 priority patent/US6567916B1/en
Publication of JPH11231781A publication Critical patent/JPH11231781A/ja
Application granted granted Critical
Publication of JP3812123B2 publication Critical patent/JP3812123B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3271—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • H04L9/3073—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/321—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving a third party or a trusted authority
    • H04L9/3213—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving a third party or a trusted authority using tickets or tokens, e.g. Kerberos
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Storage Device Security (AREA)

Abstract

(57)【要約】 【課題】 小規模な検証装置で権利や資格を認証する場
合でも、認証の特徴情報が第三者に洩れることのないよ
うにする。 【解決手段】 チケット発行装置４００は、利用者の所
持する対話装置３００の秘密関数ｆと対話を生成する際
に対話装置３００に伝達すべきドキュメントｍよりドキ
ュメント秘密情報μを算出し、認証の特徴情報ｘとドキ
ュメント秘密情報μより生成したチケットｔを利用者に
発行する。対話装置３００は、ドキュメントｍを入力さ
れると、その対話装置３００に固有の秘密関数ｆを用い
てドキュメント秘密情報を生成し、ドキュメント秘密情
報に基づいた対話を行なう。対話は、コミットメントｒ
の出力、チャレンジｃの入力、レスポンスσの出力、メ
ッセージの出力からなる。利用者は、対話（ｒ，χ，
Ｍ，σ）を、チケットｔを用いて対話（ｒ，χ，Ｍ，
ｓ）へ変換し、Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ
認証を行う。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、情報セキュリティ
技術に関するものであり、特に、零化域決定問題の困難
性に安全性の根拠を置く認証符号方式において、システ
ムの利用者に秘密情報に基づいた証明者の機能を付与し
ながら秘密情報自体を隠蔽することを可能にする方法お
よび装置に関するものである。
【０００２】
【従来の技術】［従来技術の概要］従来の公開鍵暗号に
おける復号鍵、署名における署名鍵、認証における認証
鍵は、これらの秘密情報を所持するものであることを認
証するための特徴情報である。例えば、Ｇｕｉｌｌｏｕ
とＱｕｉｓｑｕａｔｅｒによって”Ａ ｐｒａｃｔｉｃ
ａｌ ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ ｐｒｏｔｏｃｏ
ｌｆｉｔｔｅｄ ｔｏ ｓｅｃｕｒｉｔｙ Ｍｉｃｒｏ
ｐｒｏｃｅｓｓｏｒ ｍｉｎｉｍｉｚｉｎｇｂｏｔｈ
ｔｒａｎｓｍｉｓｓｉｏｎ ａｎｄ Ｍｅｍｏｒｙ”，
Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ ＥＵ
ＲＯＣＲＹＰＴ’８７，Ｃ．Ｇ．Ｇｕｅｎｔｈｅｒ（ｅ
ｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．１２
３−１２８で提案された認証方式に基づく認証符号方式
を例にとって説明する。
【０００３】図１は、この認証符号方式の流れを説明す
る図である。
【０００４】ｎを素因数分解の困難な合成数、Ｇを有理
整数環のｎを法とする剰余類環の乗法群（Ｚ／ｎ
Ｚ）*、ｐをｎのＣａｒｍｉｃｈａｅｌ関数λ（ｎ）を
割らない素数、Ｒをコミットメントの空間、πをＧから
Ｒへの関数、Ｃをチャレンジの空間、Ｓをメッセージの
空間、φをＣとＳとの集合論的積Ｃ×ＳからＦpへの写
像、Ｉ∈Ｇを公開の検証情報として、Ｉｘp＝１を満た
すｘ∈Ｇを認証の特徴情報とする。
【０００５】認証の特徴情報ｘの保持者は、以下の証明
者２００の動作を行なうことによって、なりすましと改
竄を防いで任意のメッセージＭ∈Ｓを安全に発信するこ
とができる。
【０００６】乱数ｋ∈Ｇを生成し、コミットメントｒ
＝π（ｋp）を送る。
【０００７】与えられたチャレンジχと発信するメッ
セージＭより指数ｃ＝φ（χ，Ｍ）を計算し、メッセー
ジＭとレスポンスｓ＝ｋｘcを送る。
【０００８】検証情報Ｉを知り得るものは誰でも、以下
の検証者１００の動作を行なうことによって、証明者２
００の動作を検証することが可能であり、証明者２００
が確かに認証の特徴情報を保持し、発信されたメッセー
ジが改竄を受けていないことを確かめることができる。
【０００９】コミットメントｒを与えられた後に、ラ
ンダムに生成したチャレンジχを証明者２００に送る。
【００１０】与えられたメッセージＭとレスポンスｓ
が
【００１１】
【数２】 を満たすことを確かめる。
【００１２】これらの技術は、上記の秘密情報を所持す
るものが、これを公開しないことを前提に作られてい
る。それゆえに、これらの秘密情報を所持するもののみ
が復号できる暗号文、これらの秘密情報を所持するもの
のみが生成できる署名や、これらの秘密情報を所持する
もの以外の誰にもなりすませない認証が可能となる。
【００１３】したがって、上記技術は、これらの秘密情
報の所持者にとって、これを暴露することが不利益な状
況である場合にのみ利用できる。このような状況の典型
的な例は、上記秘密情報が、特定の個人のみが所持する
ものであり、その個人を認証する特徴情報である場合で
ある。
【００１４】この場合、上記特徴情報はちょうど自宅の
鍵や個人の印鑑のような役割を担っている。実際、実世
界における鍵や印鑑をディジタル情報として構成するこ
とは、これらの暗号学的手法の直接的な応用として実現
できることは易しい。たとえば、自宅の錠を上記Ｇｕｉ
ｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒの方式における検証者
として構成し、検証に成功した場合のみ開錠するように
構成すれば、認証の特徴情報ｘの所持は、ちょうど自宅
の鍵の所持に対応することになる。
【００１５】［従来技術の問題点］上記の、個人の自宅
の鍵のように、認証の特徴情報の暴露が個人の不利益に
なる場合とは逆に、その暴露が暴露した者の利益につな
がる場合が存在する。それは、認証する者が、特定のサ
ービスを受ける権利や資格である場合である。 この場
合、上記の個人を認証する例と同様に、権利や資格を持
つ者に、権利や資格を表す特徴情報を配布し、その特徴
情報を所持していることを検証するというやりかたはと
れない。なぜなら、特徴情報の暴露が、特徴情報の所持
者には不利益にならないため、特徴情報を権利や資格を
持たない第三者に教え、その第三者から利益を得るとい
った不正行為が可能であるからである。
【００１６】したがって、従来は、上記の公開鍵暗号技
術をそのまま使った認証方式を取らず、以下の３種の方
式をとっていた。
【００１７】第１の方法は、個人が個人に帰属する秘
密の特徴情報を保持し、権利や資格の保持を検証する側
が、権利や資格を保持している個人とその個人が持つ秘
密の特徴情報を保持する方法である。この方法によれ
ば、特徴情報を漏洩させることは個人にとって不利益に
なるので、権利や資格の認証に利用可能である。
【００１８】第２の方法は、個人が個人に帰属する秘
密の特徴情報を保持し、権利や資格の保持を検証する側
が、権利や資格を保持している個人とその個人が持つ秘
密の特徴情報に対応する公開情報を保持する方法であ
る。この方法によれば、特徴情報を漏洩させることは個
人にとって不利益になるので、権利や資格の認証に利用
可能である。
【００１９】第３の方法は、権利や資格を付与する者
が、自身が持つ特徴情報で作成した署名を権利や資格を
付与される者に渡し、検証側が、その署名を検証するこ
とで、権利や資格を持つことを認証するものである。こ
の方式の例としては、Ｄ．Ｃｈａｕｍによる”Ｏｎｌｉ
ｎｅ Ｃａｓｈ Ｃｈｅｃｋｓ”，Ａｄｖａｎｃｅｓｉ
ｎ Ｃｒｙｐｔｏｌｏｇｙ ＥＵＲＯＣＲＹＰＴ’８
９，Ｊ．Ｊ．Ｑｕｉｓｑｕａｔｅｒ，Ｊ．Ｖａｎｄｅｗ
ａｌｌｅ（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａ
ｇ，ｐｐ．２８８−２９３がある。
【００２０】この方法によれば、権利や資格の所持を証
明する側が、特徴情報を持たないので、特徴情報の漏洩
の問題は起こらない。
【００２１】しかし、第１の方法では、検証側が権利や
資格を保持している者のリストを保持しなければならな
い。これは、リストの記憶と管理の負荷を検証側に課す
ことになり、必然的に高性能な検証装置を必要とするこ
とになる。また、権利や資格を付与する者と独立に検証
装置を作ることができないので、検証装置と、権利や資
格を付与する者との間の情報の交換が、常に必要にな
る。また、検証側が個人の特徴情報を持つことになるの
で、この方法によって認証される個人は、検証側による
不正な特徴情報の漏洩のリスクを負うことになる。
【００２２】第２の方法では、検証側が権利や資格を保
持している者のリストを保持しなければならない。これ
は、リストの記憶と管理の負荷を検証側に課すことにな
り、必然的に高性能な検証装置を必要とすることにな
る。また、権利や資格を付与する者と独立に検証装置を
作ることができないので、検証装置と、権利や資格を付
与する者との間の情報の交換が、常に必要になる。
【００２３】第３の方法では、配布した署名情報は誰に
よっても使用可能なので、その複製を防がなければなら
ない。これは、署名値の二重使用を防ぐという方法で行
われる。具体的には、一度認証に使用された署名値をす
べて検証側で記憶し、検証側が二重使用でないことをチ
ェックできるようにする。しかし、この機能を検証側に
設けるためには、必然的に高性能な検証装置を必要とす
ることになる。また、同じ権利や資格を認証する全ての
検証装置で、一度認証に使用された署名値のリストを共
有しなければならず、検証装置同士の情報の交換が、常
に必要となる。
【００２４】このように、従来の３つの方式には、どれ
も重大な問題があり、とくに検証側を小規模な装置やソ
フトウエアで構成することを困難にしている。
【００２５】これに対し、前述の権利や資格を示す特徴
情報を使った認証の方式は、検証側で行うことが権利や
資格を示す特徴情報を保持していることの認証だけで済
むので、有利である。
【００２６】以上述べたとおり、従来の技術では、権利
や資格を認証する場合に、小規模の検証装置で構成する
と認証の特徴情報が第三者に洩れる危険があり、その危
険をなくそうとすれば、検証装置が大規模なものになる
という問題点があった。
【００２７】
【発明が解決しようとする課題】以上に説明してきたよ
うに、本発明は、権利や資格を認証する際に、小規模な
検証装置で、認証の特徴情報が第三者に洩れることのな
い認証符号技術を実現することを目的としている。
【００２８】
【課題を解決するための手段】本発明の認証符号技術
は、 チケットの発行時に定められ、公開可能な情報である
ドキュメントよりドキュメント秘密情報を生成し、ドキ
ュメント秘密情報に基づいて対話を行なう対話装置と ドキュメント秘密情報と認証の特徴情報より生成さ
れ、公開可能な情報であるチケットとに基づく。
【００２９】すなわち、本発明によれば、ｐを素数、Ｆ
pをｐ元体、Ｇを零化域を求めることが計算量的に困難
な有限アーベル群（記法を固定する目的のためにのみ乗
法的に記す。例えば、楕円曲線のような慣習的に加法的
に記される群に対しても、零化域を求めることが計算量
的に困難である限り、本発明は適用できる）、Ｒをコミ
ットメントの空間、πをＧからＲへの写像、Ｃをチャレ
ンジの空間、Ｓをメッセージの空間、φをＣとＳの集合
論的積Ｃ×ＳからＦpへの写像として、コミットメント
ｒを生成し、ドキュメントｍとチャレンジχに対してレ
スポンスσとメッセージＭとを生成する対話方法におい
て、つぎのステップを実行する。
【００３０】（ａ）非再現性秘密情報ｋ∈Ｇをランダム
に生成するステップ （ｂ）コミットメントｒ＝π（ｋp）を計算するステッ
プ （ｃ）ｆをＧへの秘密関数として、ドキュメント秘密情
報μ＝ｆ（ｍ）を計算するステップ （ｄ）メッセージＭを生成するステップ （ｅ）指数Ｃ＝φ（χ，Ｍ）を計算するステップ （ｆ）レスポンスσ＝ｋμcを計算するステップ この構成においては、公開鍵暗号における認証の特徴情
報を開示することなく、認証の特徴情報に基づいた証明
の機能を配布することができる。したがって、従来不可
能であった、利害関係を持たない複数の個人が同一の認
証の特徴情報に基づいた証明を安全に行なえるようにな
った。またＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証
をベースの公開鍵暗号として採用しているので零知識性
が証明されている。さらに、メッセージを安全に伝達す
ることができる。
【００３１】
【発明の実施の形態】実施例の詳細な説明に入る前に、
本発明の利用形態について簡略に説明する。
【００３２】図２は、本発明の全体の構成を表してい
る。
【００３３】チケット発行者は、固有の秘密関数で特徴
付けられる対話装置３００を発行し、利用者に配布す
る。対話装置３００を特徴付ける秘密関数が利用者に知
られると、対話装置３００の複製が自由に行なえて、チ
ケット発行者の制御不能なチケットの濫用が可能とな
る。そこで、対話装置３００の秘密関数は、対話装置３
００の正当な保持者であっても、これを窃取することが
できないように保護されるようにできる。
【００３４】対話装置３００は、例えば、スマートカー
ド（ＩＣカード）として構成しても良い。
【００３５】対話装置３００は、ドキュメントと呼ばれ
るデータｍを入力されると、その対話装置３００に固有
の秘密関数ｆを用いてドキュメント秘密情報μを生成
し、ドキュメント秘密情報に基づいた対話を行なう。
【００３６】対話は具体的には、 コミットメントｒの出力 チャレンジχの入力 メッセージＭとレスポンスσの出力 という形になっている。
【００３７】Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認
証における証明者の行なう対話と形の上では同一であ
る。図１はＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証
の流れを示している。
【００３８】ドキュメントは、必ずしも、ドキュメント
秘密情報を生成するために利用されるだけとは限らな
い。例えば、ドキュメントは対話装置３００が実行可能
なプログラムやコマンド、対話装置３００の行なう処理
のパラメータ、あるいは、発信するメッセージなどであ
りえる。
【００３９】チケット発行者が、認証の特徴情報ｘに対
応付けてチケットｔを発行するときは、認証の特徴情報
に基づく対話（ｒ，χ，Ｍ，ｓ）を生成する機能を、以
下に述べる方法で利用者に頒布することによって実現す
る。
【００４０】チケット発行者は、チケット発行装置４０
０を用いて、利用者の所持する対話装置３００の秘密関
数ｆと対話を生成する際に対話装置に伝達すべきドキュ
メントｍよりドキュメント秘密情報μを算出し、認証の
特徴情報ｘとドキュメント秘密情報μより生成したチケ
ットｔを利用者に発行する。
【００４１】認証の特徴情報ｘとドキュメント秘密情報
μとは、利用者に対して秘匿される。
【００４２】利用者は、指定されたドキュメントｍを対
話装置３００に入力することによって、対話（ｒ，χ，
Ｍ，σ）を生成し、発行されたチケットｔを用いて、そ
の対話（ｒ，χ，Ｍ，σ）をチケットの対応する認証の
特徴情報に基づいた対話（ｒ，χ，Ｍ，ｓ）へ変換す
る。
【００４３】ドキュメントに対話装置３００への処理の
指示が記述される場合、チケットを用いた対話生成はド
キュメントに記述された指示に関係付けられ、これによ
ってチケットの有効性に条件を付けることが可能とな
る。
【００４４】対話の変換は、具体的には、チャレンジχ
と対話装置のレスポンスσとメッセージＭとチケットｔ
とより、レスポンスｓを計算することが可能である。
【００４５】変換された対話（ｒ，χ，Ｍ，ｓ）が、図
１におけるＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認証
の証明者が生成する対話に他ならないことを実施例にお
いて説明する。
【００４６】チケットの対応する認証の特徴情報ｘは、
各々の対話装置３００の様々なドキュメント毎に異なる
ドキュメント秘密情報μとは独立に生成される。
【００４７】チケット発行者は、任意の認証の特徴情報
ｘに基づく対話の機能を、認証の特徴情報自体を開示す
ることなく任意のドキュメントと対応付けてチケットの
形で利用者に頒布することができる。
【００４８】
【実施例】
【００４９】［基本構成要素］本発明においては、
【００５０】
【数３】 ｐ 素数 Ｆp ｐ元体 Ｇ 零化域の決定が計算量的に困難なアーベル群 Ｄ コミットメントの空間 π ＧからＤへの写像 が暗号学的な基本構成要素である。
【００５１】以後、特に説明せずに使用される数学的な
概念はいずれも基礎的なものであるのでとくに説明しな
い。例えば、岩波数学辞典第３版、日本数学会編集、岩
波書店を参照されたい。
【００５２】一般に、アーベル群Ｇの零化域Ａｎｎ
（Ｇ）とは、群の算法を乗法的に記すとして、
【００５３】
【数４】 で定義される有理整数環Ｚのイデアルであり、有理整数
環は単項イデアル整域であるので、Ａｎｎ（Ｇ）の生成
元λ∈ＺによってＡｎｎ（Ｇ）＝λＺと書ける（ここに
λＺはλの倍元の全体）。零化域を決定することは、Ａ
ｎｎ（Ｇ）の生成元λ∈Ｚを求めることに他ならない。
【００５４】ｎ∈Ｚを合成数とし、Ｇをｎを法とする有
理整数環の剰余類環の乗法群（Ｚ／ｎＺ）*としたと
き、λ＝λ（ｎ）となる。ここにλ（ｎ）はｎのＣａｒ
ｍｉｃｈａｅｌ関数であり、ｎが２の冪の場合は
【００５５】
【数５】 であり、ｎが奇素数ｐの冪の場合はλ（ｎ）＝ｎ（１−
ｐ-1）であり、一般のｎに対しては、ｎ＝Πｐepをｎの
素因数分解とすると、λ（ｎ）はλ（ｐep）の最小公倍
数である。
【００５６】したがって、ｎの素因数分解を既知とすれ
ば、Ｇの零化域をｌｏｇ ｎの多項式時間で求めること
ができ、また、逆に、零化域の生成元λを既知とする
と、非自明な１の平方根、つまり、
【００５７】
【数６】 を満たすＧを生成することによって、ｌｏｇ ｎの確率
的多項式時間でｎの素因数分解を求めることができるこ
とから、この場合の零化域決定問題は計算量的に素因数
分解問題と同程度に困難であると期待できる。 また、
ｐ1、ｐ2をｐ1≡ｐ2≡２ ｍｏｄ ３となる相異なる奇
素数、ｎ＝ｐ1ｐ2、ｂをｎと互いに素な整数、Ｅを同次
式
【００５８】
【数７】Ｙ2＝Ｘ3＋ｂＺ3 でＺ／ｎＺ上に定義されるアーベル概型；つまり、
【００５９】
【数８】Ｅ＝Ｐｒｏｊ Ｚ／ｎＺ［Ｘ，Ｙ，Ｚ］／（Ｙ
2Ｚ−Ｘ3−ｂＺ3） とし、ＧをＥのＺ／ｎＺ値点のなす有限群Ｅ（Ｚ／ｎ
Ｚ）としたとき、λはｐ1＋１とｐ2＋１の最小公倍数で
あり、この場合も零化域決定問題は計算量的に困難であ
ることが期待できる。
【００６０】πは、例えば、恒等写像ｉｄ：Ｇ→Ｇとし
ても良いし、あるいは、ハッシュ関数ｈを用いてｈ：Ｇ
→Ｄとしても良い。
【００６１】ハッシュ関数とは、ｈ（ｍ）＝ｈ（ｍ’）
を満たす相異なるｍ、ｍ’を見い出すことが計算量的に
困難であることが期待されている関数であり、例えば、
ＲＳＡ Ｄａｔａ Ｓｅｃｕｒｉｔｙ Ｉｎｃ．による
ＭＤ５や米国連邦政府による規格ＳＨＳ（Ｓｅｃｕｒｅ
Ｈａｓｈ Ｓｔａｎｄａｒｄ）が良く知られている。
【００６２】πが恒等写像である場合は、もちろん、π
を計算するコストは不要である。また、πがハッシュ関
数であり、Ｄの元を表現するのに必要なビット長がＧの
元を表現するのに必要なビット長より小さい場合には通
信量を削減する効果がある。
【００６３】例えば、素因数分解の困難な１０２４ビッ
ト程度の合成数ｎに対して、Ｇ＝（Ｚ／ｎＺ）*とし、
πとしてＳＨＳを用いれば、コミットメントｒのサイズ
を１６０ビットまで圧縮できる。
【００６４】ちなみに、ｐのビット長は、質疑応答型の
認証の場合は４０ビット程度、署名の場合でも１６０ビ
ット程度で良く、これがＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕ
ａｔｅｒ認証が高速に行なえることの根拠となってい
る。
【００６５】［対話装置］図３は対話装置３００の構成
を示している。対話装置３００は耐タンパー性を有する
容器として実装され、固有の秘密関数によって特徴付け
られて、利用者に配布される。対話装置３００をスマー
トカードなどの携帯可能な小型演算装置として構成して
も良い。対話装置３００は、入出力部３０１、記憶部３
０２、ドキュメント処理部３０３、乱数生成部３０４、
Ｇの算法実行部３０５、π計算部３０６、ｆ計算部３０
７、φ計算部３０８およびメッセージ生成部３０９を含
んで構成されている。
【００６６】図４は対話装置３００の動作を示してい
る。以下、対話装置３００の動作を説明する。
【００６７】［１］乱数生成部３０４を用いて、非再現
性秘密情報ｋ∈Ｇを生成し、記憶部３０２に保持する。
［２］Ｇにおける算法実行部３０５とπ計算部３０６を
用いて、記憶部３０２に保持された非再現性秘密情報ｋ
からコミットメントｒを
【００６８】
【数９】 ｒ＝π（ｋp） として計算し、記憶部３０２に保持する。
【００６９】もちろん、πが恒等写像である場合は、π
計算部３０６は不要である。 ［３］入出力部３０１を用いて、記憶部３０２に保持さ
れたコミットメントｒを出力する。 ［４］入出力部３０１を用いて、チャレンジχを入力
し、記憶部３０２に保持する。 ［５］入出力部３０１を用いて、ドキュメントｍを入力
し、記憶部３０２に保持する。 ［６］ドキュメント処理部３０３を用いて、記憶部３０
２に保持されたドキュメントｍに応じた処理を行なう。 ［７］対話装置固有の秘密関数ｆの計算部３０７を用い
て、記憶部３０２に保持されたドキュメントｍからドキ
ュメント秘密情報μ∈Ｇを
【００７０】
【数１０】μ＝ｆ（ｍ） として計算し、記憶部３０２に保持する。
【００７１】関数ｆの計算部３０７は、例えば、対話装
置固有の秘密情報ｄの記憶部３０２とハッシュ関数ｈの
計算部とで構成し、
【００７２】
【数１１】ｆ（ｍ）＝ｈ（ｄ｜ｍ） を計算するようにしても良い。ここで、「｜」はビット
の連結を表す。 ［８］メッセージ生成部３０９を用いて、メッセージＭ
を生成し、記憶部３０２に保持する。 ［９］φの計算部３０８を用いて、記憶部３０２に保持
されたチャレンジχとメッセージＭから指数ｃを
【００７３】
【数１２】ｃ＝φ（χ，Ｍ） として計算し、記憶部３０２に保持する。 ［１０］Ｇにおける算法実行部３０５を用いて、記憶部
３０２に保持された非再現性秘密情報ｋとドキュメント
秘密情報μと指数ｃからレスポンスσを
【００７４】
【数１３】σ＝ｋμc として計算し、記憶部３０２に保持する。［１１］入出
力部３０１を用いて、記憶部３０２に保持されたメッセ
ージＭとレスポンスσを出力する。 動作［６］は、応
用によっては、必ずしも必須ではない。したがって、ド
キュメント処理部３０３を持たない対話装置３００の構
成も可能である。 ドキュメント処理部３０３を設ける
ことによって、対話毎に対話装置３００の実行する処理
を可変にでき、後述するチケットに多様な機能性を付与
することができるようになる。
【００７５】［動作の実行順序についての制約］動作１
ないし動作１１は、必ずしもこの順序で逐次的になされ
る必要はない。動作「い」が動作「こ」に先だって実行
されなければならないという順序関係を
【００７６】
【数１４】い→こ で表すものとして、諸動作の実行順序についての制約を
説明する。
【００７７】
【数１５】１→２→３→４ ５→６，７ ４，８→９ ７，９→１０→１１ は常に満たされなければならない実行順序についての制
約となっている。
【００７８】ドキュメント処理部３０３の動作が他の動
作に影響を与える場合は、さらに、以下に説明するよう
な実行順序の制約が生じる。
【００７９】［Ｇ，ｐ，πが可変な場合］ドキュメント
ｍが、Ｇを規定する場合、６→２が要請される。これ
は、ドキュメントｍにＧを規定するパラメターが記述さ
れており、動作［６］において、これらのパラメターが
設定され、Ｇにおける算法実行部は設定されたパラメタ
ータにしたがって計算を行なえるように構成した場合で
ある。
【００８０】ドキュメントｍが、ｐを規定する場合、６
→２が要請される。これは、ドキュメントｍにｐを規定
するパラメターが記述されており、動作［６］におい
て、これらのパラメターが設定され、Ｇにおける算法実
行部は設定されたパラメターにしたがって計算を行なえ
るように構成した場合である。
【００８１】ドキュメントｍが、πを規定する場合、６
→２が要請される。これは、ドキュメントｍにπを規定
するパラメターが記述されており、動作［６］におい
て、このパラメターが設定され、πの計算部は設定され
たパラメターにしたがって計算を行なえるように構成し
た場合である。
【００８２】これらの例では、Ｇ，ｐ，πは対話の都度
に可変だが、これらを固定する構成も、もちろん可能で
ある。
【００８３】［冪計算の事前実行］ここでは、Ｇ，ｐ，
πは固定されたものとする。
【００８４】記憶部３０２に非再現性秘密情報とコミッ
トメントの組（ｋ，ｒ）を複数保持することができるな
らば、動作［１］および動作［２］をこの順序で予め繰
り返し実行しておくことによって、チャレンジχが入力
される直前にコミットメントｒを生成しなくて良いの
で、対話装置の対話に要する時間を短縮することができ
る。
【００８５】また、対話装置の装置毎に固有な部分は秘
密関数ｆのみであり、コミットメントｒの生成部分を分
離して共有化することができる。
【００８６】図８は冪計算部を分離した構成を示してい
る。この構成例では、対話装置３００は、レスポンス生
成部３１０およびコミットメント生成部３１１に分か
れ、動作［１］および動作［２］はコミットメント生成
部３１１において行なわれる。なお、図８において図３
に対応する箇所には対応する符号を付した。
【００８７】コミットメント生成部３１１からレスポン
ス生成部３１０に、非再現性秘密情報ｋが秘密通信によ
って伝達される。
【００８８】レスポンス生成部をスマートカードとして
構成しても良い。
【００８９】［レスポンス生成の条件が可変な場合］ド
キュメントｍが、レスポンス生成の条件を規定する場
合、これは、ドキュメントｍにレスポンス生成の条件が
記述されており、動作［６］において、条件が満たされ
なければ、処理を中断するように構成すれば良い。
【００９０】ドキュメントｍに応じた処理の具体例を述
べる。
【００９１】例えば、ドキュメントｍにレスポンスの生
成を許すチャレンジχの条件が記述されており、動作
［６］において、情報記憶部３０２に保持されたチャレ
ンジχが条件を満たされなければ対話装置３００の処理
を中断するように構成する。
【００９２】レスポンスの生成を許すチャレンジの条件
の例を挙げる。ドキュメントｍにレスポンス生成の有効
期限を規定するパラメターが記述されており、また、チ
ャレンジχをビット列として表現した場合の特定のビッ
トフィールドを現在時刻の表現と見なし、有効期限と現
在時刻を比較し、有効期限を過ぎていた場合は対話装置
３００の処理を中断するように構成する。
【００９３】また、例えば、ドキュメント処理部３０３
が現在時刻を保持する計時部を持ち、ドキュメントｍに
レスポンス生成の有効期限を規定するパラメターが記述
されており、動作［６］において、有効期限と現在時刻
を比較し、有効期限を過ぎていた場合は対話装置３００
の処理を中断するように構成する。
【００９４】また、例えば、ドキュメント処理部３０３
がカウンターを持ち、ドキュメントｍにカウンターの値
をディクリメントするかしないかを規定するフラグが記
述されており、動作［６］において、フラグがディクリ
メントを指示した場合、カウンターの値が０でなけれ
ば、カウンターの値を１だけディクリメントし、０であ
れば対話装置３００の処理を中断するように構成する。
【００９５】また、例えば、ドキュメント処理部３０３
がカウンターを持ち、ドキュメントｍにカウンターをデ
ィクリメントする値が記述されており、動作［６］にお
いて、カウンターの値がディクリメントする値より小さ
くなければカウンターの値を指示された値だけディクリ
メントし、そうでなければ対話装置３００の処理を中断
するように構成する。
【００９６】また、例えば、ドキュメント処理部３０３
が複数のカウンターを持ち、ドキュメントｍに対応する
カウンターを規定するポインターが記述されており、動
作［６］において、規定されたカウンターの値が０でな
ければ、カウンターの値を１だけディクリメントし、０
であれば対話装置３００の処理を中断するように構成す
る。
【００９７】また、例えば、ドキュメント処理部３０３
が複数のカウンターを持ち、ドキュメントｍに対応する
カウンターを規定するポインターとディクリメントする
値が記述されており、動作［６］において、規定された
カウンターの値がディクリメントする値より小さくなけ
ればカウンターの値を指示された値だけディクリメント
し、そうでなければ対話装置３００の処理を中断するよ
うに構成する。
【００９８】［メッセージの生成方法がドキュメントに
規定される場合］ドキュメントｍが、メッセージ生成の
方法を規定する場合、これは、ドキュメントｍにメッセ
ージ生成を規定するパラメターが記述されており、動作
［６］において、これらのパラメターが設定され、メッ
セージ生成部３０９は設定されたパラメターにしたがっ
てメッセージ生成を行なえるように構成した場合であ
る。
【００９９】ドキュメントｍに応じた処理の具体例を述
べる。
【０１００】最も簡単なものは、メッセージＭがドキュ
メントｍの関数として決まる場合、例えば、ドキュメン
トｍの特定のビットフィールドをメッセージＭとするよ
うに構成する。
【０１０１】例えば、ドキュメントｍにレスポンスの生
成を許すチャレンジχの条件が記述されており、動作
［６］において、情報記憶部３０２に保持されたチャレ
ンジχが条件を満たされなければ対話装置３００の処理
を中断するように構成する。
【０１０２】レスポンスの生成を許すチャレンジの条件
の例を挙げる。ドキュメントｍにレスポンス生成の有効
期限を規定するパラメターが記述されており、また、チ
ャレンジχをビット列として表現した場合の特定のビッ
トフィールドを現在時刻の表現と見なし、有効期限と現
在時刻を比較し、有効期限を過ぎていた場合は対話装置
３００の処理を中断するように構成する。
【０１０３】また、例えば、ドキュメント処理部３０３
が現在時刻を保持する計時部を持ち、ドキュメントｍに
レスポンス生成の有効期限を規定するパラメターが記述
されており、動作［６］において、有効期限と現在時刻
を比較し、有効期限を過ぎていた場合は対話装置３００
の処理を中断するように構成する。
【０１０４】また、例えば、ドキュメント処理部３０３
がカウンターを持ち、ドキュメントｍにカウンターの値
をディクリメントするかしないかを規定するフラグが記
述されており、動作［６］において、フラグがディクリ
メントを指示した場合、カウンターの値が０でなけれ
ば、カウンターの値を１だけディクリメントし、メッセ
ージ生成部３０９の保持するフラグ（ディクリメントに
成功に成功したか否か）をオンにし、カウンターの値が
０であれば、メッセージ生成部３０９の保持するフラグ
をオフにして、メッセージ生成部３０９は、メッセージ
をカウンターの値とディクリメントに成功したか否かの
フラグの値の組として生成するように構成する。
【０１０５】また、例えば、ドキュメント処理部３０３
がカウンターを持ち、ドキュメントｍにカウンターをデ
ィクリメントする値が記述されており、動作［６］にお
いて、カウンターの値がディクリメントする値より小さ
くなければカウンターの値を指示された値だけディクリ
メントし、メッセージ生成部３０９の保持するフラグ
（ディクリメントに成功に成功したか否か）をオンに
し、カウンターの値がディクリメントする値より小さけ
ればメッセージ生成部３０９の保持するフラグをオフに
して、メッセージ生成部３０９は、メッセージをカウン
ターの値とディクリメントに成功したか否かのフラグの
値の組として生成するように構成する。
【０１０６】また、例えば、ドキュメント処理部３０３
が複数のカウンターを持ち、ドキュメントｍに対応する
カウンターを規定するポインターが記述されており、動
作［６］において、規定されたカウンターの値が０でな
ければ、カウンターの値を１だけディクリメントし、メ
ッセージ生成部３０９の保持するフラグをオンにし、規
定されたカウンターの値が０であれば、メッセージ生成
部３０９の保持するフラグをオフにして、メッセージ生
成部３０９は、メッセージを規定されたカウンターの値
とフラグの値の組として生成するように構成する。
【０１０７】また、例えば、ドキュメント処理部３０３
が複数のカウンターを持ち、ドキュメントｍに対応する
カウンターを規定するポインターとディクリメントする
値が記述されており、動作［６］において、規定された
カウンターの値がディクリメントする値より小さくなけ
ればカウンターの値を指示された値だけディクリメント
し、メッセージ生成部３０９の保持するフラグをオンに
し、規定されたカウンターの値がディクリメントする値
より小さければメッセージ生成部３０９の保持するフラ
グをオフにして、メッセージ生成部３０９は、メッセー
ジを規定されたカウンターの値とフラグの値の組として
生成するように構成する。
【０１０８】［ドキュメント処理のその他の例］例え
ば、ドキュメント処理部３０３がカウンターを持ち、ド
キュメントｍにインクリメントする値が記述されてお
り、動作［６］において、カウンターの値を指示された
値だけインクリメントするように構成する。
【０１０９】また、例えば、ドキュメント処理部３０３
が複数のカウンターを持ち、ドキュメントｍに対応する
カウンターを規定するポインターとインクリメントする
値が記述されており、動作［６］において、規定された
カウンターの値を指示された値だけインクリメントする
ように構成する。
【０１１０】また、例えば、ドキュメント処理部３０３
が現在時刻を保持する計時部と履歴の保持部を持ち、ド
キュメントｍに履歴を記録するか記録しないかを規定す
るフラグが記述されており、動作［６］において、フラ
グが履歴の記録を指示した場合、履歴の保持部に、計時
部に保持された現在時刻とドキュメントｍのタプルを保
持するように構成する。
【０１１１】［複数ドキュメントの一括処理］以上に述
べた諸例では、一回の対話において一つのドキュメント
ｍしか関与しないが、複数のドキュメント
ｍ1，．．．，ｍNが関与するように構成することも可能
である。
【０１１２】図１０は、複数ドキュメントの一括処理を
行なう対話装置の動作を示している。
【０１１３】複数のドキュメントを一回の対話において
扱う場合、動作［５］ないし動作［７］を以下の動作
［１０］ないし動作［１２］に置き換えれば良い。
【０１１４】［１０］入出力部３０１を用いて、ドキュ
メントｍ1，．．．，ｍNを入力し、記憶部３０２に保持
する。 ［１１］ドキュメント処理部３０３を用いて、記憶部３
０２に保持されたドキュメントｍ1，．．．，ｍNに応じ
た処理を順次行なう。 ［１２］対話装置固有の秘密関数ｆの計算部３０７を用
いて、記憶部３０２に保持されたドキュメント
ｍ1，．．．，ｍNからドキュメント秘密情報μ∈Ｇを
【０１１５】
【数１６】μ＝ｆ（ｍ1）・・・ｆ（ｍN） として計算し、記憶部３０２に保持する。
【０１１６】もちろん、複数のドキュメントを一回の対
話において扱う場合には、各ドキュメントｍiに応じた
処理の実行結果が競合しないようにしなければならな
い。
【０１１７】［チケット発行装置］チケット発行装置４
００は以下の検証情報Ｉおよび認証の特徴情報ｘを利用
する。
【０１１８】
【数１７】 Ｉ∈Ｇ 検証情報 ｘ∈Ｇ 認証の特徴情報 とする。ここで、認証の特徴情報ｘと検証情報Ｉとは、
Ｉｘp＝１という関係を満たす。
【０１１９】Ｇの零化域Ａｎｎ（Ｇ）の生成元λを既知
とする。ｐがλと互いに素ならば、
【０１２０】
【数１８】ｐｄ≡１ ｍｏｄ λ を満たすｄが計算できるので任意の検証情報Ｉに対し
て、対応する認証の特徴情報ｘを
【０１２１】
【数１９】ｘ＝Ｉ-d として求めることができる。
【０１２２】ｐ＝２の場合も、Ｇ＝（Ｚ／ｎＺ）*でｎ
がＢｌｕｍ数ならば、Ｉをほとんど任意に定めることが
できる。詳しくは、ＦｉａｔとＳｈａｍｉｒによる”Ｈ
ｏｗｔｏ ｐｒｏｖｅ ｙｏｕｒｓｅｌｆ：ｐｒａｃｔ
ｉｃａｌ ｓｏｌｕｔｉｏｎｓｔｏ ｉｄｅｎｔｉｆ
ｉｃａｔｉｏｎ ａｎｄ ｓｉｇｎａｔｕｒｅ ｐｒｏ
ｂｌｅｍｓ”，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏ
ｌｏｇｙ ＣＲＹＰＴＯ’８６，Ａ．Ｍ．Ｏｄｌｙｚｋ
ｏ（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐ
ｐ．１８６−１９４を参照されたい。
【０１２３】図５はチケット発行装置の構成を示し、図
６はチケット発行装置の動作を示している。チケット発
行装置４００は入出力部４０１、記憶部４０２、Ｇの算
法実行部４０３、ｆ計算部４０４を含んで構成されてい
る。以下、チケット発行装置４００の動作を説明する。 ［１］入出力部４０１を用いて、認証の特徴情報ｘを入
力し、記憶部４０２に保持する。 ［２］入出力部４０１を用いて、ドキュメントｍを入力
し、記憶部４０２に保持する。 ［３］入出力部４０１を用いて、対話装置３００の識別
子Ｕを入力し、記憶部４０２に保持する。 ［４］記憶部４０２に保持された識別子Ｕに対応する対
話装置３００固有の秘密関数ｆの計算部４０４を用い
て、記憶部４０２に保持されたドキュメントｍからドキ
ュメント秘密情報μを
【０１２４】
【数２０】μ＝ｆ（ｍ） として計算し、記憶部４０２に保持する。 ［５］Ｇにおける算法実行部４０３を用いて、記憶部４
０２に保持された認証の特徴情報ｘとドキュメント秘密
情報μからチケットｔを
【０１２５】
【数２１】ｔ＝ｘμ-1 として計算し、記憶部４０２に保持する。 ［６］入出力部４０１を用いて、記憶部４０２に保持さ
れたチケットｔを出力する。
【０１２６】対話装置３００固有の秘密関数ｆは、例え
ば、対話装置の項で述べたように対話装置３００固有の
秘密情報ｄとハッシュ関数ｈを用いて、ｆ（ｍ）＝ｈ
（ｄ｜ｍ）として計算するようにしても良い。
【０１２７】対話装置３００固有の秘密情報ｄは、例え
ば、チケット発行者がランダムに生成し、対話装置３０
０の識別子Ｕとのタプル（Ｕ，ｄ）を保持するようにし
ても良い。
【０１２８】また、チケット発行者の秘密情報Ｄを用い
て、対話装置３００の識別子Ｕに対して、対話装置３０
０固有の秘密情報ｄを
【０１２９】
【数２２】ｄ＝Ｕ｜Ｄ としても良い。ただし、このようにｄを生成すると、対
話装置３００の耐タンパー性が崩れた場合チケット発行
者の秘密情報Ｄが漏洩するという問題をはらんでいる。
【０１３０】ハッシュ関数ｈを用いて、
【０１３１】
【数２３】ｄ＝ｈ（Ｕ｜Ｄ） としてｄを生成すれば、対話装置３００にはＤを保持す
る必要がなく、ハッシュ関数の一方向性よりｄからＤを
求めることは困難であるのでより望ましい。
【０１３２】ドキュメントｍは、秘密関数ｆの入力値と
なりえる任意の値を与えることができる。
【０１３３】さらに、ドキュメントｍは、対話装置の項
で述べたように対話装置３００のドキュメント処理部３
０３に与える処理を記述するようにしても良い。
【０１３４】さらに、ドキュメントｍには、チケットを
識別する情報を記述するようにしても良い。
【０１３５】例えば、プロバイダーの識別子やチケット
が対応するサービスの識別子、チケット発行順に振られ
るシーケンシャルＩＤが含まれても良い。
【０１３６】また、例えば、チケットの発行者が認証の
特徴情報ｘとその識別子を管理し、その識別子を含ませ
るようにしても良い。
【０１３７】また、例えば、認証の特徴情報ｘに対応す
る公開情報Ｉから定まる値を含ませるようにしても良
い。
【０１３８】［チケット合成方法］ここでは、Ｇ，ｐ，
πはシステムに共通であり、対話装置３００は複数ドキ
ュメントに対応するものとする。
【０１３９】ｔ1，．．．，ｔN∈Ｇを、固有の秘密関数
ｆを持つ対話装置３００に対して生成されたチケットと
し、１≦ｉ≦Ｎに対して、Ｉi∈Ｇを各チケットｔiに対
応する検証情報とする。
【０１４０】合成された検証情報Ｉ＝Ｉ1・・・ＩNに対
応する合成されたチケットｔを
【０１４１】
【数２４】ｔ＝ｔ1・・・ｔN として生成することができる。
【０１４２】チケットｔiにドキュメントｍiが対応し、
検証情報Ｉiに認証の特徴情報ｘiが対応している、つま
り、Ｉiｘi P＝１とすると、ドキュメントｍiに対応す
るドキュメント秘密情報μi＝ｆ（ｍi）は
【０１４３】
【数２５】μi＝ｔi -1ｘi なので、ｘ＝ｘ1・・・ｘNとすると、ｘは合成された検
証情報Ｉに対応する認証の特徴情報、つまり、Ｉｘp＝
１であり、複数ドキュメントｍ1，．．．，ｍNに対応す
るドキュメント秘密情報μ＝ｆ（ｍ1）・・・ｆ（ｍN）
は
【０１４４】
【数２６】μｔ-1ｘ を満たしている。
【０１４５】［チケットを用いた証明方法］図１１はチ
ケットを用いた証明方法の流れを示している。
【０１４６】以下、チケットと対話装置を用いた証明方
法を説明する。
【０１４７】利用者は、秘密関数ｆで特徴付けられる対
話装置とｔ＝ｘｆ（ｍ）-1を満たすドキュメントｍとチ
ケットｔを保持するものとする。
【０１４８】コミットメントｒと、チャレンジχに対す
るメッセージＭとレスポンスｓを生成する方法は以下の
とおり。
【０１４９】［１］対話装置３００を用いて、コミット
メントｒを取得する。 ［２］対話装置３００を用いて、ドキュメントｍとチャ
レンジχに対応するメッセージＭとレスポンスσを取得
する。 ［３］チャレンジχと取得したメッセージＭより指数ｃ
をｃ＝φ（χ，Ｍ）として計算する。
【０１５０】［４］チケットｔと指数ｃと取得したレス
ポンスσよりレスポンスｓを
【０１５１】
【数２７】ｓ＝ｔcσとして計算する。このとき、
（ｒ，χ，Ｍ，ｓ）は
【０１５２】
【数２８】 を満たしている。
【０１５３】このようにして、利用者に認証の特徴情報
ｘを知らすことなく、対話装置３００とチケットｔを用
いることによって、検証情報Ｉに対応する図１に記載の
証明者の機能を頒布することができる。
【０１５４】この証明者に対応する検証者は、図１に記
載された従来例と全く同一なので、検証装置は唯一の検
証情報Ｉを保持する必要があるだけで、極めて小規模な
装置で多数の利用者の認証を、完結して行なうことがで
きる。
【０１５５】［Ｆｉａｔ−Ｓｈａｍｉｒ認証］特に、ｐ
＝２の場合、
【０１５６】
【数２９】ｒ＝π（ｓ2Ｉc） を満たしており、いわゆるＦｉａｔ−Ｓｈａｍｉｒ認証
の関係を満たしている。
【０１５７】このようにして、利用者に秘密情報ｘを知
らすことなく、対話装置とチケットｔを用いることによ
って、検証情報Ｉに対応するＦｉａｔ−Ｓｈａｍｉｒ認
証の証明者の機能を頒布することができる。
【０１５８】なお、Ｆｉａｔ−Ｓｈａｍｉｒ認証の詳細
については、前述の”Ｈｏｗ ｔｏｐｒｏｖｅ ｙｏｕ
ｒｓｅｌｆ：ｐｒａｃｔｉｃａｌ ｓｏｌｕｔｉｏｎ
ｓｔｏ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ ｓｉ
ｇｎａｔｕｒｅ ｐｒｏｂｌｅｍｓ”を参照されたい。
【０１５９】［Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ
認証］特に、ｐがＧの零化域の生成元λと互いに素な場
合、利用者はＧｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ認
証の証明者としてふるまったことになる。
【０１６０】このようにして、利用者に秘密情報ｘを知
らすことなく、対話装置とチケットｔを用いることによ
って、検証情報Ｉに対応するＧｕｉｌｌｏｕ−Ｑｕｉｓ
ｑｕａｔｅｒ認証の証明者の機能を頒布することができ
る。
【０１６１】［チケット検証装置］図９はチケット検証
装置の構成を示し、図７はチケット検証装置の動作を示
している。
【０１６２】チケット検証装置は、対話装置と対話を行
なうことによってチケットの検証を行なう。チケット検
証装置５００は入出力部５０１、記憶部５０２、乱数生
成部５０３、Ｇの算法実行部５０４、π計算部５０５、
φ計算部５０６を含んで構成されている。
【０１６３】以下、チケット検証装置５００の動作を説
明する。
【０１６４】チケット検証装置５００は、検証情報Ｉと
チケットｔを記憶部５０２に保持している。
【０１６５】［１］入出力部５０１を用いて、コミット
メントｒを入力し、記憶部５０２に保持する。 ［２］乱数生成部５０３を用いて、チャレンジχを生成
し、記憶部５０２に保持する。 ［３］入出力部５０１を用いて、記憶部５０２に保持さ
れたチャレンジχを出力する。 ［４］入出力部５０１を用いて、メッセージＭとレスポ
ンスσを入力し、記憶部５０２に保持する。 ［５］φの計算部５０６を用いて、記憶部５０２に保持
されたチャレンジχとメッセージＭより指数ｃをｃ＝φ
（χ，Ｍ）として計算し、記憶部５０２に保持する。
【０１６６】［６］Ｇにおける算法実行部５０４と、必
要ならば、πの計算部５０５を用いて、記憶部５０２に
保持されたｃ，σ，Ｉとチケットｔから
【０１６７】
【数３０】ｒ’＝π（（ｔcσ）pＩc） を計算し、記憶部５０２に保持する。
【０１６８】もちろん、πが恒等写像である場合は、π
の計算部５０５は不要である。
【０１６９】また、ｒ’は、例えば、ｒ’＝π（（ｔp
Ｉ）cσp）として計算しても構わない。
【０１７０】［７］記憶部５０２に保持されたｒ，ｒ’
を比較する。
【０１７１】チケットｔがドキュメント秘密情報μと認
証の特徴情報ｘに対応したものであるならば
【０１７２】
【数３１】μ＝ｔ-1ｘ を満たしており、ドキュメント秘密情報μに基づいた対
話では、（ｒ，χ，Ｍ，σ）は
【０１７３】
【数３２】 を満たしている。したがって、秘密関数ｆがμ＝ｆ
（ｍ）を満たす対話装置３００と検証装置５００との対
話のときにはｒ＝ｒ’が満たされる。
【０１７４】［チケットが可変な構成］ここでは、入出
力部５０１にチケットを入力し、入力されたチケットを
記憶部５０２に保持する構成を述べる。
【０１７５】動作［１］ないし動作［６］に先だって、
チケット検証装置５００は、以下の動作を実行する。
【０１７６】［８］入出力部５０１を用いて、チケット
ｔを入力し、記憶部５０２に保持する。
【０１７７】このように構成することによって複数のチ
ケットの検証を行なうことができる。
【０１７８】また、コミットメントの空間Ｒとチャレン
ジの空間Ｃとが等しく、指数を生成する関数φがハッシ
ュ関数ｈを用いて
【０１７９】
【数３３】φ（χ，Ｍ）＝ｈ（χ｜Ｍ） である場合、チャレンジχをコミットメントｒそのも
の、つまり、χ＝ｒとして、検証に成功した対話に対し
て、署名（Ｍ，Ｒ，ｓ）を検証の履歴として記憶部に保
持するように構成しても良い。
【０１８０】このように構成することによってチケット
の検証を確かに行なったことを第三者に証明することが
できる。
【０１８１】もちろん、第三者が署名（Ｍ，Ｒ，ｓ）を
検証する際の検証式は、
【０１８２】
【数３４】 である。
【０１８３】［応用例：メンバーズカード］以上に述べ
てきた対話装置３００とチケットを用いた証明者の機能
を、実際の応用上の局面に適用した例について述べる。
【０１８４】まず、メンバーズカードに適用した例を図
１２を用いて説明する。この応用例では、認証の特徴情
報ｘをあるサービスに対応させ、チケットはそのサービ
スの利用資格であり、証明時に伝達されるメッセージは
サービス名称とサービス利用者としての識別子、つま
り、会員番号に対応する。
【０１８５】この応用例におけるチケットは、通常、プ
ラスティックのカード等で実現されているメンバーズカ
ード等をビット列で実現するものである。
【０１８６】チケット発行者はサービス提供者であり、
メンバーズカード検証器１０００を （１）スマートカードリーダー５１０ （２）会員番号表示部５１１ （３）スマートカードリーダー内のＲＯＭに焼き付けら
れたプログラムとして実現されたチケット検証器５００
によって構成する。
【０１８７】表示部５１１は、チケット検証に成功した
場合、伝達されたメッセージ、つまり、会員番号の表示
を行ない、チケット検証に失敗した場合はエラー表示を
行なう。
【０１８８】スマートカードリーダー５１０は、スマー
トカードを挿入するスロットを持ち、スマートカードと
の通信を行なう。
【０１８９】サービス利用者は、チケット保持部３１
２、ドキュメント保持部３１３および対話装置３００か
らなるスマートカード２０００を所有するものとする。
【０１９０】サービス利用者は、会員登録を行なう際、
自分の所有する対話装置３００の識別子を提示して、そ
の対話装置３００に対応するチケットを発行してもら
い、例えば、所有するスマートカード２０００にドキュ
メントと併せて入力する。
【０１９１】ドキュメントは、サービス名称（例えば”
Ｘｅｒｏｘ Ｃｌｕｂ”）を表すフィールドと会員番号
（例えば”００１７ ２５７ ６５５３７”）を表すフ
ィールドとからなる。
【０１９２】サービスを利用する場合、利用者はメンバ
ーズカード検証器１０００にスマートカード２０００を
挿入し、チケット認証を行なう。
【０１９３】ここで、対話装置３００の生成するメッセ
ージはドキュメントそのものとなるように構成する。
【０１９４】チケットおよびドキュメントをメンバーズ
カード検証器１０００に入力するスマートカードリーダ
ー５１０とは異なる入力手段を設ければ、チケットやド
キュメントは必ずしもスマートカード２０００に保持し
ておく必要はない。
【０１９５】例えば、利用者は対話装置３００のみから
なるスマートカード２０００を携帯し、チケットやドキ
ュメントはスマートカード２０００とは異なる携帯型情
報機器に保持したり、自宅のＰＣに保持し、利用時に携
帯型通信機器を用いて取得するようにしても良い。
【０１９６】また、チケットの発行は、必ずしも会員登
録の際に行なわなくとも、利用者が既に保持していたプ
ラステックのメンバーズカードと代替するようにしても
良い。
【０１９７】また、チケット発行者をサービス提供者と
は独立に設け、サービス提供者がサービス利用者にチケ
ットを発行する場合、独立なチケット発行者にチケット
発行を委託するようにしても良い。
【０１９８】チケット発行者を独立して設ければ、多種
のサービスに対応するチケットを単一の対話装置３００
に対して発行できるので、利用者は唯一の対話装置３０
０さへ保持していれば、複数のメンバーズカード等を純
粋に電子情報としてのみ保持することが可能となる。
【０１９９】［応用例：プリペイドカード］つぎにプリ
ペイドカードへの適用例について図１３を参照して説明
する。
【０２００】この応用例では、認証の特徴情報ｘをある
サービスに対応させ、チケットはそのサービスで利用さ
れるプリペイドカードであり、証明時に伝達されるメッ
セージはプリペイドカードからの引き落としに成功した
か否かとプリペイドカードの残高情報である。
【０２０１】チケット発行者はサービス提供者であり、
プリペイドカード取扱器１５００を （１）スマートカードリーダー５１０ （２）引き落とし額入力部５１２ （３）表示部５１３ （４）ＰＩＮ入力部５１４ （５）スマートカードリーダー内のＲＯＭに焼き付けら
れたプログラムとして実現されたチケット検証器５００
によって構成する。
【０２０２】スマートカードリーダー５１０は、スマー
トカード２０００を挿入するスロットを持ち、スマート
カード２０００との通信を行なう。
【０２０３】引き落とし額入力部５１２は、例えば、テ
ンキーによって構成され、引き落とし額の入力を行な
う。
【０２０４】表示部５１３は、引き落とし額入力部５１
２で入力された引き落とし額を表示し、ついで、チケッ
ト検証に成功した場合、伝達されたメッセージ、つま
り、引き落としに成功したか否かとプリペイドカードの
残高の表示を行ない、チケット検証に失敗した場合はエ
ラー表示を行なう。
【０２０５】ＰＩＮ入力部５１４は、例えば、テンキー
によって構成され、利用者によるＰＩＮの入力を行な
う。
【０２０６】サービス利用者は、チケット保持部３１２
と対話装置３００からなるスマートカード２０００を所
有するものとする。
【０２０７】サービス利用者は、プリペイドカードの購
入を行なう際、自分の所有する対話装置３００の識別子
とプリペイドカードに対応付けるＰＩＮとプリペイドカ
ードの額面を提示して、その対話装置３００に対応する
チケットを発行してもらい、例えば、所有するスマート
カード２０００に入力し、また、対話装置３００のカウ
ンターにプリペイドカードの額面情報を設定する。
【０２０８】ドキュメントは、サービス名称（例え
ば、”Ｘｅｒｏｘ Ｓｔｏｒｅ”）を表すフィールドと
ＰＩＮ（例えば、”０９１７”）を表すフィールドとか
らなる。
【０２０９】サービスを利用する場合、利用者はプリペ
イドカード取扱器１５００にスマートカード２０００を
挿入し、チケット認証を行なう。
【０２１０】まず、スマートカードリーダー５１０はス
マートカード２０００に保持されたチケットを取得し、
チケット検証器５００に設定し、対話を開始する。
【０２１１】チケット検証器５００の送信するチャレン
ジの特定のビットフィールドに引き落とし額入力部５１
２で入力された引き落とし額（例えば、”３５０”円）
を埋め込み、また、サービス名称（例えば、”Ｘｅｒｏ
ｘ Ｓｔｏｒｅ”）とＰＩＮ入力部５１４より入力され
たＰＩＮ（例えば、”０９１７”）を併せてドキュメン
トとして対話装置３００に入力する。
【０２１２】対話装置３００のメッセージ生成部３０９
（図３）が、チャレンジに埋め込まれた引き落とし額が
カウンタの値（例えば、”２０００”円）より大きくな
ければカウンタの値を引き落とし額だけディクリメント
し（つまり、”１６５０”円）、メッセージとして引き
落としの成功（”ＯＫ”）とカウンタ残高（”１６５
０”円）を生成する。引き落とし額がカウンタの値より
大きい場合は、カウンタのディクリメントは行なわず、
メッセージとして引き落としの失敗（”ＮＧ”）とカウ
ンタ残高を生成する。
【０２１３】チケット検証器５００は、送られたメッセ
ージを検証し、引き落としに失敗した場合は、例えば、
カード残高分のみをカードより引き落とし、差額分は現
金で支払ってもらう。
【０２１４】
【発明の効果】以上、説明してきたように、本発明は、
公開鍵暗号における認証の特徴情報を開示することな
く、認証の特徴情報に基づいた証明の機能を配布するこ
とができる。したがって、従来不可能であった、利害関
係を持たない複数の個人が同一の認証の特徴情報に基づ
いた証明を安全に行なえるようになった。このことは、
必ずしも個人に帰属しない性格を有するチケットを、そ
のまま、公開鍵暗号の認証の特徴情報に対応付けること
を可能にし、チケットの検証側は、公開された唯一の検
証情報に基づき公開された手順で、チケットの真贋を判
定するのみで検証を行なえるので検証側の負担を大幅に
軽減できる。また、チケットの所持を証明する利用者側
から見ても、検証側の有する先に述べた特質は、検証側
の公正が確認でき、チケットの検証に伴って個人の特定
がなされない（なぜならば個人に帰属しない認証の特徴
情報のみが検証に関わるので）ことなどの効用がある。
さらに、利用者にとっては、チケットおよび対話装置は
チケット発行者のみに理解し得るブラックボックスであ
り、チケットを対話装置に入力するならば、認証方式を
実現するのには関与していなコバートチャネルが存在し
ないことを確信できないが、本発明においては、対話装
置への情報伝達は、利用者にも完全な解釈を許してもプ
ロテクト側の安全性を損ねないドキュメントとして実現
し、ブラックボックスであるチケットをブラックボック
スである対話装置に入力することもない。
【０２１５】また、本発明においては、Ｇｕｉｌｌｏｕ
−Ｑｕｉｓｑｕａｔｅｒ認証をベースの公開鍵暗号とし
て採用しているが、Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔ
ｅｒ認証はＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによ
り”Ａ ’ｐａｒａｄｏｘｉｃａｌ’ ｉｄｅｎｔｉｔ
ｙ−ｂａｓｅｄ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅｒ
ｅｓｕｌｔｉｎｇ ｆｒｏｍ ｚｅｒｏ−ｋｎｏｗｌｅ
ｄｇｅ”，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏ
ｇｙ ＣＲＹＰＴ’８８，Ｓ．Ｇｏｌｄｗａｓｓｅｒ
（ｅｄ．），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，ｐｐ．
２１６−２３１において零知識性が証明されている。
【図面の簡単な説明】
【図１】 従来技術に係わる認証方法の原理を示す図で
ある。
【図２】 全体の構成を示す図である。
【図３】 対話装置の構成を示す図である。
【図４】 対話装置の動作を示す図である。
【図５】 チケット発行装置の構成を示す図である。
【図６】 チケット発行装置の動作を示す図である。
【図７】 チケット検証装置の動作を示す図である。
【図８】 対話装置の構成を示す図である。
【図９】 チケット検証装置の構成をを示す図である。
【図１０】 対話装置の動作を示す図である。
【図１１】 チケットを用いた証明方法の原理を示す図
である。
【図１２】 応用例の構成を示す図である。
【図１３】 応用例の構成を示す図である。
【符号の説明】
１００ 検証者 ２００ 証明者 ３００ 対話装置 ３０１ 対話装置の入出力部 ３０２ 対話装置の記憶部 ３０３ 対話装置のドキュメント処理部 ３０４ 対話装置の乱数生成部 ３０５ 対話装置のＧの算法実行部 ３０６ 対話装置のπ計算部 ３０７ 対話装置のｆ計算部 ３０８ 対話装置のφ計算部 ３０９ 対話装置のメッセージ生成部 ３１０ 対話装置のレスポンス生成部 ３１１ 対話装置のコミットメント生成部 ３１２ チケット保持部 ３１３ ドキュメント保持部 ４００ チケット発行装置 ４０１ チケット発行装置の入出力部 ４０２ チケット発行装置の記憶部 ４０３ チケット発行装置のＧの算法実行部 ４０４ チケット発行装置のｆ計算部 ５００ チケット検証装置 ５０１ チケット検証装置の入出力部 ５０２ チケット検証装置の記憶部 ５０３ チケット検証装置の乱数生成部 ５０４ チケット検証装置のＧの算法実行部 ５０５ チケット検証装置のπ計算部 ５０６ チケット検証装置のφ計算部 ５１０ スマートカードリーダー ５１１ 会員番号表示部 ５１２ 引き落とし額入力部 ５１３ 表示部 ５１４ ＰＩＮ入力部 １０００ メンバーズカード検証器 １５００ プリペイカード取扱器 ２０００ スマートカード

Claims (28)

    【特許請求の範囲】
  1. 【請求項１】 ｐを素数、Ｆpをｐ元体、Ｇを零化域を
    求めることが計算量的に困難な有限アーベル群（記法を
    固定する目的のためにのみ乗法的に記す）、Ｒをコミッ
    トメントの空間、πをＧからＲへの写像、Ｃをチャレン
    ジの空間、Ｓをメッセージの空間、φをＣとＳの集合論
    的積Ｃ×ＳからＦpへの写像として、コミットメントｒ
    を生成し、ドキュメントｍとチャレンジχに対してレス
    ポンスｓとメッセージＭとを生成し、検証情報Ｉ∈Ｇ、
    コミットメントｒおよびレスポンスｓに基づいて認証を
    行なう認証方法であって、 （ａ）非再現性秘密情報ｋ∈Ｇをランダムに生成するス
    テップと、 （ｂ）コミットメントｒ＝π（ｋp）を計算するステッ
    プと、 （ｃ）ｆをＧへの秘密関数として、ドキュメント秘密情
    報μ＝ｆ（ｍ）を計算するステップと、 （ｄ）メッセージＭを生成するステップと、 （ｅ）指数Ｃ＝φ（χ，Ｍ）を計算するステップと、 （ｆ）レスポンスσ＝ｋμcを計算するステップと、 （ｇ）レスポンスｓ＝ｔcσを計算するステップと、 （ｈ）生成されたレスポンスｓがｒ＝π（ｓpＩc）を満
    たすことを検証するステップとを有することを特徴とす
    る認証方法。
  2. 【請求項２】 ｐを素数、Ｆpをｐ元体、Ｇを零化域を
    求めることが計算量的に困難な有限アーベル群、Ｒをコ
    ミットメントの空間、πをＧからＲへの写像、Ｃをチャ
    レンジの空間、Ｓをメッセージの空間、φをＣとＳの集
    合論的積Ｃ×ＳからＦpへの写像として、コミットメン
    トｒを生成し、ドキュメントｍとチャレンジχに対して
    レスポンスｓとメッセージＭとを生成し、検証情報Ｉ∈
    Ｇ、コミットメントｒおよびレスポンスｓに基づいて認
    証を行なう認証装置であって、 （ａ）非再現性秘密情報ｋ∈Ｇをランダムに生成する手
    段と、 （ｂ）コミットメントｒ＝π（ｋp）を計算する手段
    と、 （ｃ）ｆをＧへの秘密関数として、ドキュメント秘密情
    報μ＝ｆ（ｍ）を計算する手段と、 （ｄ）メッセージＭを生成する手段と、 （ｅ）指数Ｃ＝φ（χ，Ｍ）を計算する手段と、 （ｆ）レスポンスσ＝ｋμcを計算する手段と、 （ｇ）レスポンスｓ＝ｔcσを計算する手段と、 （ｈ）生成されたレスポンスｓがｒ＝π（ｓpＩc）を満
    たすことを検証する手段とを有することを特徴とする認
    証装置。
  3. 【請求項３】 ｐを素数、Ｆpをｐ元体、Ｇを零化域を
    求めることが計算量的に困難な有限アーベル群、Ｒをコ
    ミットメントの空間、πをＧからＲへの写像、Ｃをチャ
    レンジの空間、Ｓをメッセージの空間、φをＣとＳの集
    合論的積Ｃ×ＳからＦpへの写像として、コミットメン
    トｒを生成し、ドキュメントｍとチャレンジχに対して
    レスポンスσとメッセージＭとを生成する対話方法であ
    って、 （ａ）非再現性秘密情報ｋ∈Ｇをランダムに生成するス
    テップと、 （ｂ）コミットメントｒ＝π（ｋp）を計算するステッ
    プと、 （ｃ）ｆをＧへの秘密関数として、ドキュメント秘密情
    報μ＝ｆ（ｍ）を計算するステップと、 （ｄ）メッセージＭを生成するステップと、 （ｅ）指数Ｃ＝φ（χ，Ｍ）を計算するステップと、 （ｆ）レスポンスσ＝ｋμcを計算するステップとから
    なることを特徴とする対話方法。
  4. 【請求項４】 特に、ｐ＝２であることを特徴とする請
    求項３に記載の対話方法。
  5. 【請求項５】 特に、ｐがＧの零化域の生成元λと互い
    に素であることを特徴とする請求項３に記載の対話方
    法。
  6. 【請求項６】 特に、Ｇが合成数ｎを法とする有理整数
    環の剰余類環の乗法群（Ｚ／ｎＺ）*であることを特徴
    とする請求項３に記載の対話方法。
  7. 【請求項７】 特に、Ｇが合成数ｎを法とする有理整数
    環の剰余類環Ｚ／ｎＺ上の群概型ＥのＺ／ｎＺに値を持
    つ点のなす群Ｅ（Ｚ／ｎＺ）であることを特徴とする請
    求項３に記載の対話方法。
  8. 【請求項８】 特に、πが恒等写像であることを特徴と
    する請求項３に記載の対話方法。
  9. 【請求項９】 特に、πがハッシュ関数を用いて計算さ
    れることを特徴とする請求項３に記載の対話方法。
  10. 【請求項１０】 特に、φがハッシュ関数を用いて計算
    されることを特徴とする請求項３に記載の対話方法。
  11. 【請求項１１】 コミットメントｒを出力し、ドキュメ
    ントｍとチャレンジχとを入力し、レスポンスσとメッ
    セージＭとを出力するにあたって、 （ａ）情報の入出力手段と、 （ｂ）情報の記憶手段と、 （ｃ）乱数を生成する手段と、 （ｄ）Ｇにおける算法を実行する手段と、 （ｅ）必要ならば、πを計算する手段と、 （ｆ）固有の秘密関数ｆを計算する手段と、 （ｇ）メッセージを生成する手段と、 （ｈ）φを計算する手段とを備え、少なくとも請求項３
    に記載の対話を実行することを特徴とする対話装置。
  12. 【請求項１２】 内部の実行処理過程が外部から観測す
    ることが困難であることを特徴とする請求項１１に記載
    の対話装置。
  13. 【請求項１３】 ＩＣカードなどの携帯可能な小型演算
    装置として構成されていることを特徴とする請求項１１
    に記載の対話装置。
  14. 【請求項１４】 固有の秘密関数ｆを計算する手段は、 （ａ）固有の秘密情報ｄを保持する手段と、 （ｂ）ハッシュ関数ｈを計算する手段とからなり、ドキ
    ュメント秘密情報μが、固有の秘密情報ｄとドキュメン
    トｍよりハッシュ関数ｈを用いて計算されることを特徴
    とする請求項１１に記載の対話装置。
  15. 【請求項１５】 ドキュメントｍに応じた処理を行なう
    手段をさらに備えたことを特徴とする請求項１１に記載
    の対話装置。
  16. 【請求項１６】 ドキュメントｍがＧ、ｐ、πの少なく
    とも一部を規定することを特徴とする請求項１５に記載
    の対話装置。
  17. 【請求項１７】 ドキュメントｍがレスポンス生成の条
    件を規定することを特徴とする請求項１５に記載の対話
    装置。
  18. 【請求項１８】 ドキュメントｍが生成されるメッセー
    ジを規定することを特徴とする請求項１５に記載の対話
    装置。
  19. 【請求項１９】 検証情報Ｉ∈Ｇに対応する認証の特徴
    情報ｘ∈ＧはＩｘp＝１を満たし、ドキュメントｍと請
    求項１１に記載の固有の秘密関数ｆを有する対話装置に
    対して、チケットｔ∈Ｇを生成するチケット発行方法で
    あって、 （ａ）ドキュメント秘密情報μ＝ｆ（ｍ）を計算するス
    テップと、 （ｂ）チケットｔ＝ｘμ-1を計算するステップとからな
    ることを特徴とするチケット発行方法。
  20. 【請求項２０】 ドキュメントｍが認証の特徴情報ｘに
    依存することを特徴とする請求項１９に記載のチケット
    発行方法。
  21. 【請求項２１】 ドキュメントｍが認証の特徴情報ｘを
    識別する情報を含むことを特徴とする請求項１９に記載
    のチケット発行方法。
  22. 【請求項２２】 認証の特徴情報ｘとドキュメントｍと
    対話装置を識別する情報を入力し、チケットｔを出力す
    るにあたって、 （ａ）情報の入出力手段と、 （ｂ）情報の記憶手段と、 （ｃ）固有の秘密関数ｆを計算する手段と、 （ｄ）Ｇにおける算法を実行する手段とを備え、請求項
    １９に記載のチケット発行を実行することを特徴とする
    チケット発行装置。
  23. 【請求項２３】 Ｉ1，ｔ1，．．．，ＩN，ｔNを、請求
    項１９に記載された検証情報Ｉi∈Ｇと固有の秘密関数
    ｆを有する対話装置に対応したチケットｔi∈Ｇとし
    て、合成された検証情報Ｉ＝Ｉ1・・・ＩNに対応する合
    成されたチケットｔをｔ＝ｔ1・・・ｔNとして生成する
    ことを特徴とするチケット合成方法。
  24. 【請求項２４】 複数のドキュメントｍ1，．．．，ｍN
    に対して、ドキュメント秘密情報μ＝ｆ（ｍ1）・・・
    ｆ（ｍN）を計算することを特徴とする請求項１１に記
    載の対話装置。
  25. 【請求項２５】 請求項１１に記載の対話装置と請求項
    １９あるいは請求項２３に記載の検証情報Ｉに対するチ
    ケットｔとドキュメントｍとを用いて、コミットメント
    ｒを生成し、チャレンジχに対して、メッセージＭとレ
    スポンスｓとを 【数１】 を満たすように生成する証明方法であって、 （ａ）対話装置を用いて、コミットメントｒを取得する
    ステップと、 （ｂ）対話装置を用いて、ドキュメントｍとチャレンジ
    χに対応するメッセージＭとレスポンスσを取得するス
    テップと、 （ｃ）指数ｃ＝φ（χ，Ｍ）を計算するステップと、 （ｄ）レスポンスｓ＝ｔcσを計算するステップとから
    なることを特徴とする証明方法。
  26. 【請求項２６】 チケットｔとドキュメントｍを保持
    し、請求項１１に記載の対話装置と通信することによっ
    て、コミットメントｒを出力し、チャレンジχを入力
    し、メッセージＭとレスポンスｓを出力するにあたっ
    て、 （ａ）情報の入出力手段と、 （ｂ）情報の記憶手段と、 （ｃ）Ｇにおける算法を実行する手段と、 （ｄ）φを計算する手段とを備え、請求項２５に記載の
    証明を実行することを特徴とする証明装置。
  27. 【請求項２７】 （チケット検証方法）｝請求項１９あ
    るいは請求項２３に記載の検証情報Ｉに対するチケット
    ｔの検証方法であって、 （ａ）コミットメントｒを取得するステップと、 （ｂ）チャレンジχをランダムに生成するステップと、 （ｃ）メッセージＭとレスポンスσを取得するステップ
    と、 （ｄ）指数ｃ＝φ（χ，Ｍ）を計算するステップと、 （ｅ）関係式ｒ＝π（（ｔcσ）pＩc）またはこの関係
    式と同等な関係式を満たすことを確認するステップとか
    らなることを特徴とするチケット検証方法。
  28. 【請求項２８】 検証情報Ｉとチケットｔを保持し、コ
    ミットメントｒを入力し、チャレンジχを出力し、メッ
    セージＭとレスポンスσを入力して正当性を検証するに
    あたって、 （ａ）情報の入出力手段と、 （ｂ）情報の記憶手段と、 （ｃ）乱数を生成する手段と、 （ｄ）Ｇにおける算法を実行する手段と、 （ｅ）必要ならば、πを計算する手段と、 （ｆ）φを計算する手段とを備え、少なくとも請求項２
    ７に記載の検証を実行することを特徴とするチケット検
    証装置。
JP02955298A 1998-02-12 1998-02-12 認証方法および装置 Expired - Fee Related JP3812123B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP02955298A JP3812123B2 (ja) 1998-02-12 1998-02-12 認証方法および装置
US09/240,876 US6567916B1 (en) 1998-02-12 1999-02-01 Method and device for authentication

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP02955298A JP3812123B2 (ja) 1998-02-12 1998-02-12 認証方法および装置

Publications (2)

Publication Number Publication Date
JPH11231781A true JPH11231781A (ja) 1999-08-27
JP3812123B2 JP3812123B2 (ja) 2006-08-23

Family

ID=12279317

Family Applications (1)

Application Number Title Priority Date Filing Date
JP02955298A Expired - Fee Related JP3812123B2 (ja) 1998-02-12 1998-02-12 認証方法および装置

Country Status (2)

Country Link
US (1) US6567916B1 (ja)
JP (1) JP3812123B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4768626B2 (ja) * 2003-11-10 2011-09-07 クゥアルコム・インコーポレイテッド 期限切れマーカを使用する無線通信の認証

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7412598B1 (en) * 2000-12-29 2008-08-12 Cisco Technology, Inc. Method and system for real-time insertion of service during a call session over a communication network
US20030014630A1 (en) * 2001-06-27 2003-01-16 Spencer Donald J. Secure music delivery
US20030014496A1 (en) * 2001-06-27 2003-01-16 Spencer Donald J. Closed-loop delivery system
US20030069854A1 (en) * 2001-10-09 2003-04-10 Hsu Michael M. Expiring content on playback devices
US6947910B2 (en) * 2001-10-09 2005-09-20 E-Cast, Inc. Secure ticketing
KR100445574B1 (ko) * 2001-12-19 2004-08-25 한국전자통신연구원 대화형 영 지식 증명을 이용한 패스워드 기반의 인증 및키 교환 프로토콜 설계 방법
US20030131226A1 (en) * 2002-01-04 2003-07-10 Spencer Donald J. Dynamic distributed configuration management system
AU2003259197A1 (en) * 2002-07-24 2004-02-09 Congruence Llc. Code for object identification
US20040078324A1 (en) * 2002-10-16 2004-04-22 Carl Lonnberg Systems and methods for authenticating a financial account at activation
US8239917B2 (en) * 2002-10-16 2012-08-07 Enterprise Information Management, Inc. Systems and methods for enterprise security with collaborative peer to peer architecture
US7840806B2 (en) * 2002-10-16 2010-11-23 Enterprise Information Management, Inc. System and method of non-centralized zero knowledge authentication for a computer network
CN100521191C (zh) * 2003-05-26 2009-07-29 Nxp股份有限公司 半导体器件、鉴别方法和系统
US7647498B2 (en) * 2004-04-30 2010-01-12 Research In Motion Limited Device authentication
JP4555859B2 (ja) * 2005-07-13 2010-10-06 日本電信電話株式会社 認証システム、認証方法、証明装置、検証装置、それらのプログラム及び記録媒体
JP4518056B2 (ja) * 2006-09-25 2010-08-04 富士ゼロックス株式会社 文書操作認証装置、及びプログラム
US8334891B2 (en) * 2007-03-05 2012-12-18 Cisco Technology, Inc. Multipoint conference video switching
US8264521B2 (en) * 2007-04-30 2012-09-11 Cisco Technology, Inc. Media detection and packet distribution in a multipoint conference
US10148285B1 (en) 2012-07-25 2018-12-04 Erich Schmitt Abstraction and de-abstraction of a digital data stream
US10795858B1 (en) 2014-02-18 2020-10-06 Erich Schmitt Universal abstraction and de-abstraction of a digital data stream
US12587517B2 (en) * 2024-05-14 2026-03-24 Oracle International Corporation Proof-of-work challenge to transmit data to a non-authenticated gateway

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4908861A (en) * 1987-08-28 1990-03-13 International Business Machines Corporation Data authentication using modification detection codes based on a public one way encryption function
US5218637A (en) * 1987-09-07 1993-06-08 L'etat Francais Represente Par Le Ministre Des Postes, Des Telecommunications Et De L'espace Method of transferring a secret, by the exchange of two certificates between two microcomputers which establish reciprocal authorization
FR2713419B1 (fr) * 1993-12-02 1996-07-05 Gemplus Card Int Procédé de génération de signatures DSA avec des appareils portables à bas coûts.
US5606617A (en) * 1994-10-14 1997-02-25 Brands; Stefanus A. Secret-key certificates
FR2733379B1 (fr) * 1995-04-20 1997-06-20 Gemplus Card Int Procede de generation de signatures electroniques, notamment pour cartes a puces
JPH11508707A (ja) * 1995-06-30 1999-07-27 ブランズ，ステファヌス・アルフォンスス 秘密鍵上の制限的にブラインド可能な証明書
US5870470A (en) * 1996-02-20 1999-02-09 International Business Machines Corporation Method and apparatus for encrypting long blocks using a short-block encryption procedure
US5761306A (en) * 1996-02-22 1998-06-02 Visa International Service Association Key replacement in a public key cryptosystem
US5796830A (en) * 1996-07-29 1998-08-18 International Business Machines Corporation Interoperable cryptographic key recovery system
WO1998043212A1 (en) * 1997-03-24 1998-10-01 Visa International Service Association A system and method for a multi-application smart card which can facilitate a post-issuance download of an application onto the smart card
DE69724235T2 (de) * 1997-05-28 2004-02-26 Siemens Ag Computersystem und Verfahren zum Schutz von Software
JPH11122240A (ja) * 1997-10-17 1999-04-30 Fuji Xerox Co Ltd 復号装置および方法ならびにアクセス資格認証装置および方法
US6076163A (en) * 1997-10-20 2000-06-13 Rsa Security Inc. Secure user identification based on constrained polynomials

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4768626B2 (ja) * 2003-11-10 2011-09-07 クゥアルコム・インコーポレイテッド 期限切れマーカを使用する無線通信の認証

Also Published As

Publication number Publication date
US6567916B1 (en) 2003-05-20
JP3812123B2 (ja) 2006-08-23

Similar Documents

Publication Publication Date Title
JP3562262B2 (ja) 認証方法および装置
JP3812123B2 (ja) 認証方法および装置
US7673144B2 (en) Cryptographic system for group signature
US6061791A (en) Initial secret key establishment including facilities for verification of identity
US7571324B2 (en) Method and device for anonymous signature with a shared private key
US4944007A (en) Public key diversification method
JP5497677B2 (ja) 公開鍵を検証可能に生成する方法及び装置
EP0824814B1 (en) Methods and apparatus for authenticating an originator of a message
US6072874A (en) Signing method and apparatus using the same
Brands A technical overview of digital credentials
US7490069B2 (en) Anonymous payment with a verification possibility by a defined party
EP0804003A2 (en) Digital signature method and communication system
US20040165728A1 (en) Limiting service provision to group members
JPH1131204A (ja) 電子チケットシステム
US20040059686A1 (en) On-line cryptographically based payment authorization method and apparatus
US20050114662A1 (en) Method for authentication
JP4818264B2 (ja) リスト署名を生成する方法及びシステム
US8121290B2 (en) Pseudo-random function calculating device and method and number-limited anonymous authentication system and method
Wang Public key cryptography standards: PKCS
JP3513324B2 (ja) ディジタル署名処理方法
JPH11508707A (ja) 秘密鍵上の制限的にブラインド可能な証明書
WO1990002456A1 (en) Public key diversification method
Fan et al. Anonymous fair transaction protocols based on electronic cash
Okada et al. Optimistic fair exchange protocol for E-Commerce
Paar et al. Digital Signatures

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20051206

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060206

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20060404

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20060412

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20060509

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20060522

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100609

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110609

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110609

Year of fee payment: 5

LAPS Cancellation because of no payment of annual fees