JPH11289329A - 認証形サ―チ・ツリ― - Google Patents
認証形サ―チ・ツリ―Info
- Publication number
- JPH11289329A JPH11289329A JP11053084A JP5308499A JPH11289329A JP H11289329 A JPH11289329 A JP H11289329A JP 11053084 A JP11053084 A JP 11053084A JP 5308499 A JP5308499 A JP 5308499A JP H11289329 A JPH11289329 A JP H11289329A
- Authority
- JP
- Japan
- Prior art keywords
- tree
- search
- node
- directory
- user
- 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.)
- Pending
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/3236—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 cryptographic hash functions
-
- 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/3263—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 certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements
-
- 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/50—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using hash chains, e.g. blockchains or hash trees
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/30—Compression, e.g. Merkle-Damgard construction
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Storage Device Security (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 集合内のアイテムのメンバーシップまたは非
メンバーシップを認証するよう作用する認証形サーチ・
ツリーを提供する。 【解決手段】 認証形サーチ・ツリーは、ノードとリー
フを有しかつこれらに関連してサーチ手法を有したサー
チ・ツリーを含む。ノードは、ダイナミック・サーチ値
を含み、リーフは集合のアイテムを含む。ノードの各々
には、暗号化ハッシュ関数値を関連付け、この暗号化ハ
ッシュ関数値は、子ノードの暗号化ハッシュ値と、ノー
ドのダイナミック・サーチ値とに暗号化ハッシュ関数を
適用することにより発生する。認証形サーチ・ツリーの
ルート・ノードは デジタル署名により認証する。
メンバーシップを認証するよう作用する認証形サーチ・
ツリーを提供する。 【解決手段】 認証形サーチ・ツリーは、ノードとリー
フを有しかつこれらに関連してサーチ手法を有したサー
チ・ツリーを含む。ノードは、ダイナミック・サーチ値
を含み、リーフは集合のアイテムを含む。ノードの各々
には、暗号化ハッシュ関数値を関連付け、この暗号化ハ
ッシュ関数値は、子ノードの暗号化ハッシュ値と、ノー
ドのダイナミック・サーチ値とに暗号化ハッシュ関数を
適用することにより発生する。認証形サーチ・ツリーの
ルート・ノードは デジタル署名により認証する。
Description
【０００１】
【発明の属する技術分野】本発明は、認証目的のための
デジタル署名の一般的な分野にある。
デジタル署名の一般的な分野にある。
【０００２】
【従来の技術】公開鍵暗号の幅広い使用は、公開鍵の真
正さを検証する能力を必要としている。これは、“公開
鍵インフラストラクチャ（Public Key Infrastructure
(PKI)）”における証明書の使用を通して実現される。
証明書とは、公的信用機関（証明機関（ＣＡ：certific
ation authority）であって、これの公開鍵の真正さは
他の手段によって提供され得る機関）により署名された
メッセージであり、これは、公開鍵と、追加の情報、例
えば、満了日、連続番号、および鍵と対象エンティティ
に関する情報を含んでいる。
正さを検証する能力を必要としている。これは、“公開
鍵インフラストラクチャ（Public Key Infrastructure
(PKI)）”における証明書の使用を通して実現される。
証明書とは、公的信用機関（証明機関（ＣＡ：certific
ation authority）であって、これの公開鍵の真正さは
他の手段によって提供され得る機関）により署名された
メッセージであり、これは、公開鍵と、追加の情報、例
えば、満了日、連続番号、および鍵と対象エンティティ
に関する情報を含んでいる。
【０００３】証明書が発行されたとき、その有効性は、
満了日によって制限されている。しかし、証明書をその
満了日前に取り消さなければならない状況がある（例え
ば、秘密鍵が漏れたとき、あるいは鍵保有者が加入また
は地位を変更したとき）。したがって、証明書が存在す
ることは、必要なことであるが、その有効性に対する十
分な証拠となるものではなく、そのため証明書が取り消
されたかどうかについて判定する機構が必要である。
満了日によって制限されている。しかし、証明書をその
満了日前に取り消さなければならない状況がある（例え
ば、秘密鍵が漏れたとき、あるいは鍵保有者が加入また
は地位を変更したとき）。したがって、証明書が存在す
ることは、必要なことであるが、その有効性に対する十
分な証拠となるものではなく、そのため証明書が取り消
されたかどうかについて判定する機構が必要である。
【０００４】応用の代表的なものは、クレジットカード
・システムであり、このシステムにおいては、クレジッ
ト会社が、クレジットカードを、例えばこのカードが盗
難にあったと報告があったとき、あるいはそのユーザの
銀行口座の残高にしたがって、その満了前に一時的にあ
るいは恒久的に取り消すことができる。
・システムであり、このシステムにおいては、クレジッ
ト会社が、クレジットカードを、例えばこのカードが盗
難にあったと報告があったとき、あるいはそのユーザの
銀行口座の残高にしたがって、その満了前に一時的にあ
るいは恒久的に取り消すことができる。
【０００５】
【発明が解決しようとする課題】証明書取り消しリスト
（Certificate Revocation List (CRL)） ＣＲＬは、ＣＡの発行する署名されたリストであって、
取り消された証明書全てをそれらの連続番号により識別
したものである。このリストは、（その新しさを示すも
のとして）タイムスタンプと連結され、そしてそれら証
明書を最初に発行したＣＡが署名する。これらＣＲＬ
は、たとえ変更がなくても、定期的にディレクトリに送
って、新しいＣＲＬではなく古いＣＲＬの悪意のリプレ
イを防止する。
（Certificate Revocation List (CRL)） ＣＲＬは、ＣＡの発行する署名されたリストであって、
取り消された証明書全てをそれらの連続番号により識別
したものである。このリストは、（その新しさを示すも
のとして）タイムスタンプと連結され、そしてそれら証
明書を最初に発行したＣＡが署名する。これらＣＲＬ
は、たとえ変更がなくても、定期的にディレクトリに送
って、新しいＣＲＬではなく古いＣＲＬの悪意のリプレ
イを防止する。
【０００６】ディレクトリは、照会に対する回答とし
て、最も更新されたＣＲＬを供給する（完全なＣＲＬは
商人に送られる）。 ・この手法の主たる利点は、その簡単さにある。 ・この手法の主たる欠点は、その高いディレクトリ−ユ
ーザ間の通信コストである（その理由は、ＣＲＬは非常
に長くなることがあるからである）。別の欠点は、ユー
ザが、その証明書の有効性に関する簡潔な証拠を持ち合
わせていないことがあることである。
て、最も更新されたＣＲＬを供給する（完全なＣＲＬは
商人に送られる）。 ・この手法の主たる利点は、その簡単さにある。 ・この手法の主たる欠点は、その高いディレクトリ−ユ
ーザ間の通信コストである（その理由は、ＣＲＬは非常
に長くなることがあるからである）。別の欠点は、ユー
ザが、その証明書の有効性に関する簡潔な証拠を持ち合
わせていないことがあることである。
【０００７】証明書に対しては、合理的な有効性満了期
間を選ぶべきである。この満了期間が短いと、証明書を
再発行するのに資源を浪費する。満了期間が長いと、Ｃ
ＲＬが長くなることがあり、通信コスト並びにＣＲＬ管
理の困難さを高くしてしまう。カウフマン外（Kaufman
et aL [15, Section 7.7.3]）は、ＣＲＬがある限界を
超えたときには常に全ての証明書を再発行することを提
案していた。その提案においては、証明書は、満了日で
はなく連続番号を付す。（連続番号は、発行した各証明
書に対して増分する。連続番号は、証明書全てを再発行
するときでも再使用しない。）。このＣＲＬは、“第１
有効”証明書を示すフィールドを含んでいる。全ての証
明書を再発行したとき、ＣＲＬの第１有効証明書フィー
ルドを更新することにより、第１の再発行した証明書の
連続番号を含むようにする。
間を選ぶべきである。この満了期間が短いと、証明書を
再発行するのに資源を浪費する。満了期間が長いと、Ｃ
ＲＬが長くなることがあり、通信コスト並びにＣＲＬ管
理の困難さを高くしてしまう。カウフマン外（Kaufman
et aL [15, Section 7.7.3]）は、ＣＲＬがある限界を
超えたときには常に全ての証明書を再発行することを提
案していた。その提案においては、証明書は、満了日で
はなく連続番号を付す。（連続番号は、発行した各証明
書に対して増分する。連続番号は、証明書全てを再発行
するときでも再使用しない。）。このＣＲＬは、“第１
有効”証明書を示すフィールドを含んでいる。全ての証
明書を再発行したとき、ＣＲＬの第１有効証明書フィー
ルドを更新することにより、第１の再発行した証明書の
連続番号を含むようにする。
【０００８】証明書取り消しシステム ミカリ（Micali [18]）は、ＣＲＬ通信コストを改善す
るため、証明書取り消しシステム（ＣＲＳ）を提案して
いる。その基礎となる思想は、どの証明書のメッセージ
にも署名して、これが取り消されたかどうかについて述
べ、そしてオフライン／オンライン署名法 [11]を使用
することによりこれら署名を周期的に更新するコストを
低減することである。
るため、証明書取り消しシステム（ＣＲＳ）を提案して
いる。その基礎となる思想は、どの証明書のメッセージ
にも署名して、これが取り消されたかどうかについて述
べ、そしてオフライン／オンライン署名法 [11]を使用
することによりこれら署名を周期的に更新するコストを
低減することである。
【０００９】証明書を作るため、ＣＡは、各証明書に対
し、２つの番号(Y365, N)を関連付け、これらは、’伝
統的’な証明書データと共に署名する。各証明書に対し
ては、ＣＡは、２つの番号N0, Y0を（擬似）ランダムに
選び、そして（一方向性関数fを使って）Y365 =f365 (Y
0) および N = f (N0)を計算する。（実際には、fに関
するより強力な仮定を必要とする、例えばfはその反復
が一方向性である、すなわち、y = f i(x)が与えられた
ときに、y = f(x')となるようなx'をみつけることは実
行不可能である。これは、fが一方向性転置である場合
に自動的に保証される。
し、２つの番号(Y365, N)を関連付け、これらは、’伝
統的’な証明書データと共に署名する。各証明書に対し
ては、ＣＡは、２つの番号N0, Y0を（擬似）ランダムに
選び、そして（一方向性関数fを使って）Y365 =f365 (Y
0) および N = f (N0)を計算する。（実際には、fに関
するより強力な仮定を必要とする、例えばfはその反復
が一方向性である、すなわち、y = f i(x)が与えられた
ときに、y = f(x')となるようなx'をみつけることは実
行不可能である。これは、fが一方向性転置である場合
に自動的に保証される。
【００１０】ディレクトリは、毎日、各証明書に対して
番号Ｃを送るＣＡによって、以下のように更新する。 １．非取り消しの証明書に対して、ＣＡは、fの１つの
アプリケーション、すなわち、C = Y365-i =f
365-i (Y0) を明らかにし、これにおいて、iは毎日増分
するカウンタであり、発行日においてはi＝０である。 ２．取り消した証明書に対しては、C = N0である。した
がって、Ｃの最も更新された値は、短い証拠（この証明
書xは取り消されたあるいは取り消されたものではな
い）として作用し、これは、ディレクトリが、ユーザの
照会xに対する返答として提示することができる。
番号Ｃを送るＣＡによって、以下のように更新する。 １．非取り消しの証明書に対して、ＣＡは、fの１つの
アプリケーション、すなわち、C = Y365-i =f
365-i (Y0) を明らかにし、これにおいて、iは毎日増分
するカウンタであり、発行日においてはi＝０である。 ２．取り消した証明書に対しては、C = N0である。した
がって、Ｃの最も更新された値は、短い証拠（この証明
書xは取り消されたあるいは取り消されたものではな
い）として作用し、これは、ディレクトリが、ユーザの
照会xに対する返答として提示することができる。
【００１１】・ ＣＲＬに優るＣＲＳの利点は、その照
会通信コストにある。連邦ＰＫＩ（Public Key Infrast
ructure）評価に基づき、ミカリ（Micali [18]）は、Ｃ
ＲＳの毎日の更新は、ＣＲＬの更新よりはより費用がか
かるが、ＣＲＳ照会のコストははるかに低い、というこ
とを示した。彼は、ＣＲＬに対して通信コスト全体で９
００倍の向上が生じると見積もった。
会通信コストにある。連邦ＰＫＩ（Public Key Infrast
ructure）評価に基づき、ミカリ（Micali [18]）は、Ｃ
ＲＳの毎日の更新は、ＣＲＬの更新よりはより費用がか
かるが、ＣＲＳ照会のコストははるかに低い、というこ
とを示した。彼は、ＣＲＬに対して通信コスト全体で９
００倍の向上が生じると見積もった。
【００１２】ＣＲＳの別の利点は、各ユーザが、彼の証
明書の有効性の簡潔な譲渡可能の証拠を保有することが
できる、ということである。ユーザがそのような証拠を
保持していてしかも彼らの証明書と共に提示するときに
は、ディレクトリ・アクセスを省略する。 ・ このシステムの主たる欠点は、ＣＡ−ディレクトリ
間の通信の増大である（これは、ディレクトリ−ユーザ
間の通信と同じ量であって、ディレクトリの存在がＣＡ
の通信を減少させると思われる。）。さらに、ＣＡの通
信コストはディレクトリ更新レートに比例するため、Ｃ
Ａ−ディレクトリ間の通信コストは、ディレクトリの更
新レートを制限する。
明書の有効性の簡潔な譲渡可能の証拠を保有することが
できる、ということである。ユーザがそのような証拠を
保持していてしかも彼らの証明書と共に提示するときに
は、ディレクトリ・アクセスを省略する。 ・ このシステムの主たる欠点は、ＣＡ−ディレクトリ
間の通信の増大である（これは、ディレクトリ−ユーザ
間の通信と同じ量であって、ディレクトリの存在がＣＡ
の通信を減少させると思われる。）。さらに、ＣＡの通
信コストはディレクトリ更新レートに比例するため、Ｃ
Ａ−ディレクトリ間の通信コストは、ディレクトリの更
新レートを制限する。
【００１３】証明書が取り消されていなかったというこ
とを検証することの複雑さは、更新レートにも比例す
る。例えば、１時間に１回の更新では、ユーザは、証明
書が取り消されていなかったことを検証するために関数
fを 365 x 24 = 8760回適用しなければならず、これは
検証における主要なファクタとなる。
とを検証することの複雑さは、更新レートにも比例す
る。例えば、１時間に１回の更新では、ユーザは、証明
書が取り消されていなかったことを検証するために関数
fを 365 x 24 = 8760回適用しなければならず、これは
検証における主要なファクタとなる。
【００１４】証明書取り消しツリー コーカー（Kocher [16]）は、証明書が取り消されてい
なかったことの短い証拠を証明書の検証者が得ることが
できるようにするため、証明書取り消しツリー（認証ツ
リーとも呼ぶ）の使用を提案している。ＣＲＴは、ハッ
シュ・ツリーであって、そのリーフがＣＡが発行する証
明書連続番号Ｘについてのステートメント集合CAXに対
応したものである。このステートメント集合は、各ＣＡ
の取り消した証明書の集合から発生する。これは、証明
書Ｘを取り消したか否か（あるいはその状態がＣＲＴ発
行者には未知であるかどうか）についての情報を提供す
る。２つのタイプのステートメントがある。すなわち、
未知のＣＡのレンジを指定するものと、証明書レンジを
指定するものであってこれの下側の証明書のみが取り消
されているものと、である。例えば、CA1が２つの証明
書X1< X2を取り消した場合、それらステートメントの内
の１つは、以下の通りとなる。
なかったことの短い証拠を証明書の検証者が得ることが
できるようにするため、証明書取り消しツリー（認証ツ
リーとも呼ぶ）の使用を提案している。ＣＲＴは、ハッ
シュ・ツリーであって、そのリーフがＣＡが発行する証
明書連続番号Ｘについてのステートメント集合CAXに対
応したものである。このステートメント集合は、各ＣＡ
の取り消した証明書の集合から発生する。これは、証明
書Ｘを取り消したか否か（あるいはその状態がＣＲＴ発
行者には未知であるかどうか）についての情報を提供す
る。２つのタイプのステートメントがある。すなわち、
未知のＣＡのレンジを指定するものと、証明書レンジを
指定するものであってこれの下側の証明書のみが取り消
されているものと、である。例えば、CA1が２つの証明
書X1< X2を取り消した場合、それらステートメントの内
の１つは、以下の通りとなる。
【００１５】CAX = CA1および X1 ≦ X < X2の場合、X
= vのときにXは取り消される。ＣＲＴを発生するには、
ＣＲＴ発行者は、上記ステートメントに対応したリーフ
をもつ２進ハッシュ・ツリー[17]を構築する。
= vのときにXは取り消される。ＣＲＴを発生するには、
ＣＲＴ発行者は、上記ステートメントに対応したリーフ
をもつ２進ハッシュ・ツリー[17]を構築する。
【００１６】証明書状態に関する証拠は、ハッシュ・ツ
リーにおけるルート（root）から、パス上の各ノードに
対してその子供の値を指定する適切なリーフ（ステート
メント）までのパスである。 ・ ＣＲＬに優るＣＲＴの主な利点は、ＣＲＬ全体があ
る特定の証明書を検証するのに必要でないこと、そして
ユーザが彼の証明書の有効性の簡潔な証拠を保持するこ
とができること、である。 ・ ＣＲＴの主な欠点は、ＣＲＴの更新に計算作業が必
要となることである。取り消した証明書の集合における
いかなる変更も、ＣＲＴ全体の再計算を生じることにな
る。
リーにおけるルート（root）から、パス上の各ノードに
対してその子供の値を指定する適切なリーフ（ステート
メント）までのパスである。 ・ ＣＲＬに優るＣＲＴの主な利点は、ＣＲＬ全体があ
る特定の証明書を検証するのに必要でないこと、そして
ユーザが彼の証明書の有効性の簡潔な証拠を保持するこ
とができること、である。 ・ ＣＲＴの主な欠点は、ＣＲＴの更新に計算作業が必
要となることである。取り消した証明書の集合における
いかなる変更も、ＣＲＴ全体の再計算を生じることにな
る。
【００１７】引用した従来技術のリスト 米国特許4,309,569 (以下マークル（Merkle）特許と呼
ぶ) [1] A. V. Aho, J. E. Hopcroft, J. D. Ullman. "Dat
a Structures and Algorithms". Addison-Wesley, 198
3. [2] R.G. Seidel., C.R Aragon "Randomized Search Tr
ees". Proc. 30th Annual IEEE Symp. on Foundations
of Computer Science, pp. 540-545, 1989. [6] M. Bellare, P. Rogaway. "Collision-Resistant H
ashing: Towards MakingUOWHFs Practical". Advances
in Cryptology - CRYPTO '97, Lecture Notesin Compu
ter Science, Springer-Verlag, 1997. [11] S. Even, O. Goldreich, S. Micali. "On-Line/O
ff-Line Digital Signatures". Journal of Cryptolog
y, Springer-Verlag, Vol. 9 pp. 35-67, 1996. [12] O. Goldreich, S. Goldwasser, and S. Halevi,.
"Collision-Free Hashing from Lattice Problems". E
CCC, TR96-042, 1996. http://www. eccc. unitrier. de/eccc/ [13] A. Herzberg, H. Yochai. "Mini-Pay: Charging
per Click on the Web".Proc. 6th International Worl
d Wide Web Conference, 1997. http: //www6. nttlabs. com/ [15] C. Kaufman, R- Perlman, M. Speciner. "Networ
k Security. Private Communication in a Public Wor
ld". Prentice Hall series in networking anddistri
buting systems, 1995. [16] P. Koeher. "A Quick Introduction to Certific
ate Revocation Trees (CRTs)". http://www. valicert. com/company/crt. html [17] P, C. Merkle. "A Certified Digital Signatur
e". Proc. Crypto '89,Lecture Notes in Computer Sc
ience 435, pp. 234-246, Springer-Verlag, 1989. [18] S. Micali. "Efficient Certificate revocatio
n". Technical Memo MIT/LCS/TM542b, 1996.
ぶ) [1] A. V. Aho, J. E. Hopcroft, J. D. Ullman. "Dat
a Structures and Algorithms". Addison-Wesley, 198
3. [2] R.G. Seidel., C.R Aragon "Randomized Search Tr
ees". Proc. 30th Annual IEEE Symp. on Foundations
of Computer Science, pp. 540-545, 1989. [6] M. Bellare, P. Rogaway. "Collision-Resistant H
ashing: Towards MakingUOWHFs Practical". Advances
in Cryptology - CRYPTO '97, Lecture Notesin Compu
ter Science, Springer-Verlag, 1997. [11] S. Even, O. Goldreich, S. Micali. "On-Line/O
ff-Line Digital Signatures". Journal of Cryptolog
y, Springer-Verlag, Vol. 9 pp. 35-67, 1996. [12] O. Goldreich, S. Goldwasser, and S. Halevi,.
"Collision-Free Hashing from Lattice Problems". E
CCC, TR96-042, 1996. http://www. eccc. unitrier. de/eccc/ [13] A. Herzberg, H. Yochai. "Mini-Pay: Charging
per Click on the Web".Proc. 6th International Worl
d Wide Web Conference, 1997. http: //www6. nttlabs. com/ [15] C. Kaufman, R- Perlman, M. Speciner. "Networ
k Security. Private Communication in a Public Wor
ld". Prentice Hall series in networking anddistri
buting systems, 1995. [16] P. Koeher. "A Quick Introduction to Certific
ate Revocation Trees (CRTs)". http://www. valicert. com/company/crt. html [17] P, C. Merkle. "A Certified Digital Signatur
e". Proc. Crypto '89,Lecture Notes in Computer Sc
ience 435, pp. 234-246, Springer-Verlag, 1989. [18] S. Micali. "Efficient Certificate revocatio
n". Technical Memo MIT/LCS/TM542b, 1996.
【００１８】用語解説 以下は、用語の解説であって、用語の一部は在来のもの
であり、また一部は新語である。
であり、また一部は新語である。
【００１９】証明機関（Certification Authority (C
A)） − 信頼のおける者（trusted party）であっ
て、すでに証明された公開鍵を有し、公開鍵および／ま
たはクレジットカード番号のようなその他の情報の真正
さを確立しその裏付けを行う責任がある者。
A)） − 信頼のおける者（trusted party）であっ
て、すでに証明された公開鍵を有し、公開鍵および／ま
たはクレジットカード番号のようなその他の情報の真正
さを確立しその裏付けを行う責任がある者。
【００２０】ＣＡは、必ずしも必要ではないが、好まし
くは、ユーザに対しオンライン証明書情報サービスを提
供しない。その代わりに、ＣＡは、ディレクトリを定期
的に更新する。以下に示すように、ある実施形態におい
ては、ディレクトリを使用しない。
くは、ユーザに対しオンライン証明書情報サービスを提
供しない。その代わりに、ＣＡは、ディレクトリを定期
的に更新する。以下に示すように、ある実施形態におい
ては、ディレクトリを使用しない。
【００２１】ＣＡは、ユーザの証明書を、証明書の連続
番号関連のデータと満了日とを含むメッセージにより発
行する。この証明書は、ディレクトリへ送ることとユー
ザへ与えることとの一方または両方を行う。ＣＡは、証
明書をその満了日前に取り消すことができる。証明書
は、決して後者の定義に拘束されず、例えば１またはそ
れ以上（例えば、レンジ）の公開鍵、クレジットカード
番号（単数または複数）、およびその他に関するデータ
を包含することができ、明示的な形態であるいはエンコ
ーディングまたは暗号化のような関数を受けさせた後に
提示する。（用語“アイテム”と“証明書”は、本明細
書で交換可能に使用する。）
番号関連のデータと満了日とを含むメッセージにより発
行する。この証明書は、ディレクトリへ送ることとユー
ザへ与えることとの一方または両方を行う。ＣＡは、証
明書をその満了日前に取り消すことができる。証明書
は、決して後者の定義に拘束されず、例えば１またはそ
れ以上（例えば、レンジ）の公開鍵、クレジットカード
番号（単数または複数）、およびその他に関するデータ
を包含することができ、明示的な形態であるいはエンコ
ーディングまたは暗号化のような関数を受けさせた後に
提示する。（用語“アイテム”と“証明書”は、本明細
書で交換可能に使用する。）
【００２２】ディレクトリ（Directory） − 信頼の
おけない１以上の者であって、ＣＡから更新された証明
書取り消し情報を得て、そしてユーザがアクセス可能な
証明書データベースとして作用する者。
おけない１以上の者であって、ＣＡから更新された証明
書取り消し情報を得て、そしてユーザがアクセス可能な
証明書データベースとして作用する者。
【００２３】ユーザ（User） − 信頼のおけない者で
あって、ＣＡからその証明書を受け、そして証明書情報
に対する照会を発する者。ユーザは、とりわけ、以下を
含むように構成すべきである。 (i) 他のユーザの証明書の有効性の照会を行う商人、(i
i) 彼／彼女の証明書の有効性の証拠を、他のユーザと
対面してそれを使用するために得るユーザ。
あって、ＣＡからその証明書を受け、そして証明書情報
に対する照会を発する者。ユーザは、とりわけ、以下を
含むように構成すべきである。 (i) 他のユーザの証明書の有効性の照会を行う商人、(i
i) 彼／彼女の証明書の有効性の証拠を、他のユーザと
対面してそれを使用するために得るユーザ。
【００２４】サーチ・ツリー（Search tree） − ル
ートからサーチしているアイテム（リーフと関連する）
までのツリー内のサーチ・パスを構成できるようにする
サーチ手法に関連した周知のデータ構造。サーチ・パス
は、ツリー・ノードそしておそらくはそのリンク内に存
在するサーチ値を利用する。サーチ・ツリーは、更新取
引を取り扱う（すなわち、アイテムをツリーから削除し
たりあるいはそれに追加したりする）ように本質的に設
計されている。代表的には、排他的なものではないが、
サーチ・ツリーの例は、2-3 tree, Btree, Btree+, Tri
S, treaps等である。
ートからサーチしているアイテム（リーフと関連する）
までのツリー内のサーチ・パスを構成できるようにする
サーチ手法に関連した周知のデータ構造。サーチ・パス
は、ツリー・ノードそしておそらくはそのリンク内に存
在するサーチ値を利用する。サーチ・ツリーは、更新取
引を取り扱う（すなわち、アイテムをツリーから削除し
たりあるいはそれに追加したりする）ように本質的に設
計されている。代表的には、排他的なものではないが、
サーチ・ツリーの例は、2-3 tree, Btree, Btree+, Tri
S, treaps等である。
【００２５】更新取引（Update Transactions） −
新たなアイテムをツリーに挿入し、ツリー内の既存のア
イテムを削除する。
新たなアイテムをツリーに挿入し、ツリー内の既存のア
イテムを削除する。
【００２６】認証ツリー（Authentication Tree） −
ルートをもつツリーであって、各内部ノードが、その
子供の値を暗号化ハッシュ関数によって認証し、そして
そのルートが、デジタル署名によって認証されたもの。
代表的には、排他的なものではないが、例は、マークル
特許に例示されている。
ルートをもつツリーであって、各内部ノードが、その
子供の値を暗号化ハッシュ関数によって認証し、そして
そのルートが、デジタル署名によって認証されたもの。
代表的には、排他的なものではないが、例は、マークル
特許に例示されている。
【００２７】暗号化ハッシュ関数（Cryptographic hash
function） − これは以下を含む。 (i) 衝突イントラクタブル関数（collision intractabl
e function）h()であって、h(x)= h(y)を満たす y≠xを
見つけるのが計算上本質的に実行不可能であるようなも
の。代表的には、排他的なものではないが、その例が、
マークル特許に例示されている。または、(ii) ユニバ
ーサル一方向性関数であって、関数h()のファミリが存
在していて、そのファミリからのどのxおよびランダム
なh()に対しても、h(x)= h(y)を満たす y≠xを見つける
のが計算上本質的に実行不可能であるもの（(I) および
(II)におけるその詳細な説明については、[6]を参
照）。
function） − これは以下を含む。 (i) 衝突イントラクタブル関数（collision intractabl
e function）h()であって、h(x)= h(y)を満たす y≠xを
見つけるのが計算上本質的に実行不可能であるようなも
の。代表的には、排他的なものではないが、その例が、
マークル特許に例示されている。または、(ii) ユニバ
ーサル一方向性関数であって、関数h()のファミリが存
在していて、そのファミリからのどのxおよびランダム
なh()に対しても、h(x)= h(y)を満たす y≠xを見つける
のが計算上本質的に実行不可能であるもの（(I) および
(II)におけるその詳細な説明については、[6]を参
照）。
【００２８】
【課題を解決するための手段】したがって、当該分野に
おいては、これまでに知られた技術に関連する欠点を、
アイテムを認証する新規な技術を提供することにより、
取り除くかあるいは実質的に削減する必要性がある。
おいては、これまでに知られた技術に関連する欠点を、
アイテムを認証する新規な技術を提供することにより、
取り除くかあるいは実質的に削減する必要性がある。
【００２９】本発明は、在来の認証ツリー、並びに２−
３ツリーまたはBtreeのような在来のサーチ・ツリーの
利用を組み込む。サーチ・ツリーの利用は、アイテム
（または複数のアイテム）の認証を可能にする一方、こ
の目的のために大量のデータを送信する必要を取り除
く。従来技術による認証ツリーの利用は、一連の取り消
されたアイテムあるいは（他の場合には）有効なアイテ
ムを送信できるようにする。
３ツリーまたはBtreeのような在来のサーチ・ツリーの
利用を組み込む。サーチ・ツリーの利用は、アイテム
（または複数のアイテム）の認証を可能にする一方、こ
の目的のために大量のデータを送信する必要を取り除
く。従来技術による認証ツリーの利用は、一連の取り消
されたアイテムあるいは（他の場合には）有効なアイテ
ムを送信できるようにする。
【００３０】認証ツリー、例えばマークル特許に開示さ
れた種類のものを使用するときの主要な欠点は、それが
修正取引を受けるときに生ずる。これは、リーフ中のア
イテムの新たな配列をもたらし、したがってその結果と
して、（以下に例示するように）ツリー中の多数のノー
ド（以下、修正ノード）の値の修正を必要とする。
れた種類のものを使用するときの主要な欠点は、それが
修正取引を受けるときに生ずる。これは、リーフ中のア
イテムの新たな配列をもたらし、したがってその結果と
して、（以下に例示するように）ツリー中の多数のノー
ド（以下、修正ノード）の値の修正を必要とする。
【００３１】修正ノードの値の更新のために広範な計算
が必要となるだけでなく、認証を利用することにより、
前記修正ノードの多数の値を例えばＣＡからディレクト
リに通信ネットワークを介して送信するときに高い通信
オーバーヘッドが課される。そのような修正がかなり頻
繁に発生することがあることを考慮すると、その述べた
オーバーヘッドは、従来技術の認証ツリーの使用を商業
的に実行不可能にする。
が必要となるだけでなく、認証を利用することにより、
前記修正ノードの多数の値を例えばＣＡからディレクト
リに通信ネットワークを介して送信するときに高い通信
オーバーヘッドが課される。そのような修正がかなり頻
繁に発生することがあることを考慮すると、その述べた
オーバーヘッドは、従来技術の認証ツリーの使用を商業
的に実行不可能にする。
【００３２】本発明によれば、在来の認証ツリーを、在
来のサーチ・ツリーに“重畳”し（認証サーチ・ツリー
をもたらし）、したがって、アイテムの認証に関する認
証ツリーの固有の利点と、サーチ・ツリー構造によるツ
リー・ノードに課される制限された変更と、の両方から
利益が得られる。
来のサーチ・ツリーに“重畳”し（認証サーチ・ツリー
をもたらし）、したがって、アイテムの認証に関する認
証ツリーの固有の利点と、サーチ・ツリー構造によるツ
リー・ノードに課される制限された変更と、の両方から
利益が得られる。
【００３３】したがって、本発明は、集合内のアイテム
のメンバーシップまたは非メンバーシップを認証するよ
う作用する認証形サーチ・ツリーを含むメモリを提供
し、前記認証形サーチ・ツリーが、ノードとリーフを有
しかつこれらに関連してサーチ手法を有したサーチ・ツ
リーであって、前記ノードがダイナミック・サーチ値を
含み、前記リーフが前記集合のアイテムを含み、前記ノ
ードの各々には、暗号化ハッシュ関数値を関連付け、該
暗号化ハッシュ関数値は、少なくとも（Ｉ）子ノードの
暗号化ハッシュ値と、（II）前記ノードの前記ダイナミ
ック・サーチ値と、に暗号化ハッシュ関数を適用するこ
とにより発生する、前記のサーチ・ツリーと、デジタル
署名により認証した前記認証形サーチ・ツリーの少なく
ともルート・ノードと、を備える。さらに、本発明は、
集合内のアイテムのメンバーシップまたは非メンバーシ
ップを認証する方法を提供し、該方法が、（ｉ）指定し
た種類の認証形サーチ・ツリーを提供し、（ii）前記集
合の少なくとも１つのアイテムの認証を、該少なくとも
１つのアイテムと前記ルートにより誘起される認証パス
を計算することにより行うこと、から成る。さらに、本
発明は、集合内の少なくとも１つのアイテムを認証形サ
ーチ・ツリーにおいて更新する方法を提供し、該方法
が、（ｉ）指定した種類の認証形サーチ・ツリーを提供
し、（ii）前記サーチ・ツリーを更新することにより、
更新したノードを獲得し、（iii）前記更新したノード
により誘起された認証パスを計算し、（iv）少なくとも
前記のルート修正したノードをデジタル署名により認証
すること、から成る。
のメンバーシップまたは非メンバーシップを認証するよ
う作用する認証形サーチ・ツリーを含むメモリを提供
し、前記認証形サーチ・ツリーが、ノードとリーフを有
しかつこれらに関連してサーチ手法を有したサーチ・ツ
リーであって、前記ノードがダイナミック・サーチ値を
含み、前記リーフが前記集合のアイテムを含み、前記ノ
ードの各々には、暗号化ハッシュ関数値を関連付け、該
暗号化ハッシュ関数値は、少なくとも（Ｉ）子ノードの
暗号化ハッシュ値と、（II）前記ノードの前記ダイナミ
ック・サーチ値と、に暗号化ハッシュ関数を適用するこ
とにより発生する、前記のサーチ・ツリーと、デジタル
署名により認証した前記認証形サーチ・ツリーの少なく
ともルート・ノードと、を備える。さらに、本発明は、
集合内のアイテムのメンバーシップまたは非メンバーシ
ップを認証する方法を提供し、該方法が、（ｉ）指定し
た種類の認証形サーチ・ツリーを提供し、（ii）前記集
合の少なくとも１つのアイテムの認証を、該少なくとも
１つのアイテムと前記ルートにより誘起される認証パス
を計算することにより行うこと、から成る。さらに、本
発明は、集合内の少なくとも１つのアイテムを認証形サ
ーチ・ツリーにおいて更新する方法を提供し、該方法
が、（ｉ）指定した種類の認証形サーチ・ツリーを提供
し、（ii）前記サーチ・ツリーを更新することにより、
更新したノードを獲得し、（iii）前記更新したノード
により誘起された認証パスを計算し、（iv）少なくとも
前記のルート修正したノードをデジタル署名により認証
すること、から成る。
【００３４】注意すべきであるが、上記の指定した順序
は、反復的手順において全てのステップを各反復におい
て実行する、ということを必ずしも意味するものではな
い。したがって、例えばステップ（ii）および（iii）
は、各反復において実行し、そしてステップ（iv）は最
後の反復において１回だけ適用することができる。これ
は、同様に、本文に記述する方法およびシステムの他の
ステップにも当てはまる。
は、反復的手順において全てのステップを各反復におい
て実行する、ということを必ずしも意味するものではな
い。したがって、例えばステップ（ii）および（iii）
は、各反復において実行し、そしてステップ（iv）は最
後の反復において１回だけ適用することができる。これ
は、同様に、本文に記述する方法およびシステムの他の
ステップにも当てはまる。
【００３５】本発明は、さらに、必要な変更を加えた認
証／更新のためのシステムを提供する。
証／更新のためのシステムを提供する。
【００３６】
【実施の形態】本発明について、図面を参照して詳細に
説明する。
説明する。
【００３７】まず図１を見ると、これは、従来技術、例
えば特定したマークル特許に開示されたものによる認証
ツリーを示している。尚、マークル特許の内容は、この
参照により本開示に含めるものとする。
えば特定したマークル特許に開示されたものによる認証
ツリーを示している。尚、マークル特許の内容は、この
参照により本開示に含めるものとする。
【００３８】例えば、証明書Y1−Y8が全ての有効なクレ
ジットカードの証明書リスト（ＣＬ）に対して有効であ
る場合について考察する。ここで、ユーザが、商人と対
面しての商取引において、彼のクレジットカードY5の使
用を希望しているとする。商人は、図１に開示した種類
の認証ツリー（すなわち、有効なクレジットカードY1−
Y8に対する認証ツリー）を保有するディレクトリをアド
レス指定する。ここで想起されるように、このディレク
トリは、信頼のおけない者であり、したがって商人は、
Y5がこのツリー内に確かに現れているかについて検証を
したい。
ジットカードの証明書リスト（ＣＬ）に対して有効であ
る場合について考察する。ここで、ユーザが、商人と対
面しての商取引において、彼のクレジットカードY5の使
用を希望しているとする。商人は、図１に開示した種類
の認証ツリー（すなわち、有効なクレジットカードY1−
Y8に対する認証ツリー）を保有するディレクトリをアド
レス指定する。ここで想起されるように、このディレク
トリは、信頼のおけない者であり、したがって商人は、
Y5がこのツリー内に確かに現れているかについて検証を
したい。
【００３９】衝突イントラクタブル関数h()は、クレジ
ットカード番号、例えば昇順にしたがって記憶したアイ
テム（クレジットカード）Y1−Y8を認証するために作用
する。したがって、Y5を認証するには、ディレクトリが
商人に対し、ツリーのリーフとノードの値Y5, H(6,6,
Y), H(7,8,Y)およびH(1,4,Y)を送信することで十分であ
る。ただし、そのルート値H(1,8,Y)が、デジタル署名を
使って、その前に認証されていたと仮定する。もちろ
ん、追加のツリー値も送信することができるが、以下の
説明から判るように、追加のツリー値を送信することは
全く冗長なものである。
ットカード番号、例えば昇順にしたがって記憶したアイ
テム（クレジットカード）Y1−Y8を認証するために作用
する。したがって、Y5を認証するには、ディレクトリが
商人に対し、ツリーのリーフとノードの値Y5, H(6,6,
Y), H(7,8,Y)およびH(1,4,Y)を送信することで十分であ
る。ただし、そのルート値H(1,8,Y)が、デジタル署名を
使って、その前に認証されていたと仮定する。もちろ
ん、追加のツリー値も送信することができるが、以下の
説明から判るように、追加のツリー値を送信することは
全く冗長なものである。
【００４０】したがって、Y5を認証するには、商人（前
のH()を知っている）は、認証パス、すなわち、（Y5に
基づいて）H(5,5,Y)、そしてH(5,5,Y)と受けたH(6,6,Y)
とに基づいて、商人は、H(5,6,Y)を計算する。この後者
は、受けたH(7,8,Y)と合わさってH(5,8,Y)を生じる。こ
の後者は、受けたH(1,4,Y)と合わさってH(1,8,Y)を生
じ、これは、ＰＫＩ技術を受けさせ（例えば、公開鍵ｎ
を適用する）、そしてその結果は、それ以前に認証した
H(1,8,Y)値と比較し、そして一致した場合には、アイテ
ムY5はこの有効クレジットカードリストに属しているこ
とを保証する。
のH()を知っている）は、認証パス、すなわち、（Y5に
基づいて）H(5,5,Y)、そしてH(5,5,Y)と受けたH(6,6,Y)
とに基づいて、商人は、H(5,6,Y)を計算する。この後者
は、受けたH(7,8,Y)と合わさってH(5,8,Y)を生じる。こ
の後者は、受けたH(1,4,Y)と合わさってH(1,8,Y)を生
じ、これは、ＰＫＩ技術を受けさせ（例えば、公開鍵ｎ
を適用する）、そしてその結果は、それ以前に認証した
H(1,8,Y)値と比較し、そして一致した場合には、アイテ
ムY5はこの有効クレジットカードリストに属しているこ
とを保証する。
【００４１】もちろん、この認証ツリーの利点は、ほん
のいくつかのノード値をユーザに送信し、そしてユーザ
がそれにも拘わらず、問題のアイテムY5を認証すること
ができることである。以下に説明するように、従来技術
の認証ツリーに関してアイテムを認証するためのこの詳
細な説明は、本発明のサーチ認証形ツリーにも同様に当
てはまる。
のいくつかのノード値をユーザに送信し、そしてユーザ
がそれにも拘わらず、問題のアイテムY5を認証すること
ができることである。以下に説明するように、従来技術
の認証ツリーに関してアイテムを認証するためのこの詳
細な説明は、本発明のサーチ認証形ツリーにも同様に当
てはまる。
【００４２】図１の認証ツリーの主要な欠点は、例えば
新たなクレジットカードをＣＡにおけるリストに追加す
る場合に、この認証ツリーに修正取引を受けさせるとき
に生ずる。Y4 < Y4' < Y5となる新たなアイテムY4'を追
加するとする。この結果の認証ツリー（図示せず）は、
このツリー内のノードのほとんどについての広範な更
新、並びに更新情報の過度の伝送オーバーヘッドを必要
とすることになり、これは、明らかに望ましくなく、Ｃ
Ａを新たなアイテムで更新するレートが一般にかなり高
いことを考慮すれば特にである。
新たなクレジットカードをＣＡにおけるリストに追加す
る場合に、この認証ツリーに修正取引を受けさせるとき
に生ずる。Y4 < Y4' < Y5となる新たなアイテムY4'を追
加するとする。この結果の認証ツリー（図示せず）は、
このツリー内のノードのほとんどについての広範な更
新、並びに更新情報の過度の伝送オーバーヘッドを必要
とすることになり、これは、明らかに望ましくなく、Ｃ
Ａを新たなアイテムで更新するレートが一般にかなり高
いことを考慮すれば特にである。
【００４３】無効にしたまたは取り消したアイテム（例
えば、無効のクレジットカード）を保有する証明書取り
消しリスト（ＣＲＬ）を考慮するときには、上記の利点
および欠点が等しく当てはまる。
えば、無効のクレジットカード）を保有する証明書取り
消しリスト（ＣＲＬ）を考慮するときには、上記の利点
および欠点が等しく当てはまる。
【００４４】次に、本発明の１実施形態による例示のサ
ーチ認証形ツリーについて、例えばＣＲＬ（例えば、リ
ーフにおいて保持された取り消したクレジットカードの
リスト：図２のＡ，Ｂを参照）を備えた２−３サーチ・
ツリーを利用して考察する。
ーチ認証形ツリーについて、例えばＣＲＬ（例えば、リ
ーフにおいて保持された取り消したクレジットカードの
リスト：図２のＡ，Ｂを参照）を備えた２−３サーチ・
ツリーを利用して考察する。
【００４５】これに関連して、注意されたいことに、本
発明は、このサーチ・ツリーとこの目的に利用する任意
の既知の技術との実際の実現法に決して限定するもので
はなく、特定の応用に依存して必要とされまた適当とな
る全ての場合に適用可能である。したがって、限定目的
でない例として、アイテムを保持するどのような方法も
適用可能であり、例えば、レコード、リンク・リスト、
ツリー、ブロック（長いアイテムの場合）等である。こ
の記述は、認証ツリーに対しても同様に有効である。
発明は、このサーチ・ツリーとこの目的に利用する任意
の既知の技術との実際の実現法に決して限定するもので
はなく、特定の応用に依存して必要とされまた適当とな
る全ての場合に適用可能である。したがって、限定目的
でない例として、アイテムを保持するどのような方法も
適用可能であり、例えば、レコード、リンク・リスト、
ツリー、ブロック（長いアイテムの場合）等である。こ
の記述は、認証ツリーに対しても同様に有効である。
【００４６】したがって、この特定の実施形態により、
２−３ツリーは、昇順での取り消した証明書の連続番号
（ｃ１−ｃ７）に対応するリーフを備えて維持する。
（２−３ツリーにおいては、あらゆる内部ノードは、２
つまたは３つの子を有し、そしてルートからリーフへの
パスは同じ長さを有する。）。メンバーシップをテスト
しそして修正する、すなわち単一のエレメントを挿入
し、削除しあるいは更新することは、対数時間で行い、
ここで、その修正は、その修正パス上のノードにのみ影
響を与える。２−３ツリーの詳細な提示については、
[1, pp. 169-180]を参照されたい。２−３ツリーの特性
は、テストおよび修正がサーチ・パス上のノードに対す
る変更のみを含むこと、すなわち、あらゆる変更は、局
部的であって、影響されるパスの数は少ない。
２−３ツリーは、昇順での取り消した証明書の連続番号
（ｃ１−ｃ７）に対応するリーフを備えて維持する。
（２−３ツリーにおいては、あらゆる内部ノードは、２
つまたは３つの子を有し、そしてルートからリーフへの
パスは同じ長さを有する。）。メンバーシップをテスト
しそして修正する、すなわち単一のエレメントを挿入
し、削除しあるいは更新することは、対数時間で行い、
ここで、その修正は、その修正パス上のノードにのみ影
響を与える。２−３ツリーの詳細な提示については、
[1, pp. 169-180]を参照されたい。２−３ツリーの特性
は、テストおよび修正がサーチ・パス上のノードに対す
る変更のみを含むこと、すなわち、あらゆる変更は、局
部的であって、影響されるパスの数は少ない。
【００４７】このツリーは、最初は空の２−３ツリーに
取り消した証明書の連続番号を１つ１つ挿入することに
より作成するか、あるいは、連続番号のリストを分類し
そしてこの分類したリスト内の連続番号に対応するリー
フをもつ２段階ツリー（degree 2 tree）を構築するこ
とによって、作成することができる（理由は、通信の複
雑さは、ツリーが２段階のものでは最小となる）。どの
ツリー・ノードにも、以下の手順による値を割り当て
る。 ・ 各リーフは、取り消した証明書の連続番号をその値
として記憶する。 ・ 内部ノードの値は、暗号化ハッシュ関数H()をその
子供の値とそして内部ノード（これは、当てはまる場合
には常に、リンクも包含する）の少なくともダイナミッ
クなサーチ値とに適用することによって計算する。義務
ではないが、暗号化一方向性ハッシュ関数H()は、ノー
ドに関連したダイナミックなサーチ値以外の情報にも適
用可能であり、例えば、ツリーをバランスさせるのに関
連した情報等である。
取り消した証明書の連続番号を１つ１つ挿入することに
より作成するか、あるいは、連続番号のリストを分類し
そしてこの分類したリスト内の連続番号に対応するリー
フをもつ２段階ツリー（degree 2 tree）を構築するこ
とによって、作成することができる（理由は、通信の複
雑さは、ツリーが２段階のものでは最小となる）。どの
ツリー・ノードにも、以下の手順による値を割り当て
る。 ・ 各リーフは、取り消した証明書の連続番号をその値
として記憶する。 ・ 内部ノードの値は、暗号化ハッシュ関数H()をその
子供の値とそして内部ノード（これは、当てはまる場合
には常に、リンクも包含する）の少なくともダイナミッ
クなサーチ値とに適用することによって計算する。義務
ではないが、暗号化一方向性ハッシュ関数H()は、ノー
ドに関連したダイナミックなサーチ値以外の情報にも適
用可能であり、例えば、ツリーをバランスさせるのに関
連した情報等である。
【００４８】衝突イントラクタブル関数とは異なって、
ユニバーサル一方向性ハッシュ関数を内部ノードに対し
指定した方法で適用することは、各ノードに対する固有
の関数の利用を必要とする。この場合、上記に加えて、
子供の値と内部ノードのダイナミック・サーチ値と、そ
してこの内部ノードに関連したこの関数の固有の値とを
認証する必要がある。
ユニバーサル一方向性ハッシュ関数を内部ノードに対し
指定した方法で適用することは、各ノードに対する固有
の関数の利用を必要とする。この場合、上記に加えて、
子供の値と内部ノードのダイナミック・サーチ値と、そ
してこの内部ノードに関連したこの関数の固有の値とを
認証する必要がある。
【００４９】次に、以下は、本発明の１実施形態による
サーチ認証形ツリーの修正法に関する説明である。
サーチ認証形ツリーの修正法に関する説明である。
【００５０】したがって、１つのアイテムを削除するに
は、在来の２−３アイテム削除ステップを実行する。す
なわち、 １． 各々の満了した証明書の連続番号を２−３ツリー
から削除し、削除パス上のノードの値を更新する。
は、在来の２−３アイテム削除ステップを実行する。す
なわち、 １． 各々の満了した証明書の連続番号を２−３ツリー
から削除し、削除パス上のノードの値を更新する。
【００５１】同様に、１つのアイテムを挿入するには、
在来の２−３アイテム挿入ステップを実行する。すなわ
ち、 ２． 各々の新しい取り消した証明書連続番号をツリー
に挿入し、この挿入パス上のノードの値を更新する。ツ
リー更新の間、２−３ツリーのバランスのため、新たな
ノードのあるものを作成したりあるいはあるノードを削
除したりすることができる。これらノードは、挿入／削
除したノード（以下、修正ノード）に対するサーチ・パ
ス上においてのみ生起する。
在来の２−３アイテム挿入ステップを実行する。すなわ
ち、 ２． 各々の新しい取り消した証明書連続番号をツリー
に挿入し、この挿入パス上のノードの値を更新する。ツ
リー更新の間、２−３ツリーのバランスのため、新たな
ノードのあるものを作成したりあるいはあるノードを削
除したりすることができる。これらノードは、挿入／削
除したノード（以下、修正ノード）に対するサーチ・パ
ス上においてのみ生起する。
【００５２】証明機関は、このツリーの認証を、そのル
ートの認証により行い、そしてこの目的のために、修正
したノードにより誘起されたサーチ・パスのみを比較す
べきである。
ートの認証により行い、そしてこの目的のために、修正
したノードにより誘起されたサーチ・パスのみを比較す
べきである。
【００５３】このサーチ認証形ツリーのより簡単な実現
のためには、２−３ツリーではなく他のツリー例えばラ
ンダム・トリープ（random treap）[2]を使用すること
ができる。トリープは、２進ツリーであって、そのノー
ドが（鍵、優先順位）ペアで関連しているものである。
このツリーは、ノード鍵に関しては２進サーチ・ツリー
であり（すなわち、どのノードに対しても、左（または
右）のサブツリー内の鍵は、その鍵よりも小さい（また
は大きい）。）、そしてノード優先順位に関しては山
（heap）である（すなわち、どのノードに関しても、そ
の優先順位は、その子孫の優先順位よりも高い）。
（鍵、優先順位）ペアのどの有限の集合も、トリープと
しての固有の表現を有している。ランダム・トリープに
おいては、優先順位は、十分大きな整然とした集合から
ランダムに引き出す（したがって、これらは、区別（di
stinct）できると仮定する）。
のためには、２−３ツリーではなく他のツリー例えばラ
ンダム・トリープ（random treap）[2]を使用すること
ができる。トリープは、２進ツリーであって、そのノー
ドが（鍵、優先順位）ペアで関連しているものである。
このツリーは、ノード鍵に関しては２進サーチ・ツリー
であり（すなわち、どのノードに対しても、左（または
右）のサブツリー内の鍵は、その鍵よりも小さい（また
は大きい）。）、そしてノード優先順位に関しては山
（heap）である（すなわち、どのノードに関しても、そ
の優先順位は、その子孫の優先順位よりも高い）。
（鍵、優先順位）ペアのどの有限の集合も、トリープと
しての固有の表現を有している。ランダム・トリープに
おいては、優先順位は、十分大きな整然とした集合から
ランダムに引き出す（したがって、これらは、区別（di
stinct）できると仮定する）。
【００５４】シーデルとアラゴン[2]（Seidel and Arag
on [2]）は、メンバーシップの照会、挿入、削除を、ト
リープ内に記憶された集合Ｓサイズの予測時間複素（co
mplexity）対数をもって、処理するための単純なアルゴ
リズムを提示する。ランダム・トリープは、２−３ツリ
ーと同様に、２−３ツリーに容易に変換することができ
る。これら手法の通信コストは、同様であるが、理由
は、ランダム・トリープの予想される深さがその２−３
ツリーの対応部分と類似しているからである。
on [2]）は、メンバーシップの照会、挿入、削除を、ト
リープ内に記憶された集合Ｓサイズの予測時間複素（co
mplexity）対数をもって、処理するための単純なアルゴ
リズムを提示する。ランダム・トリープは、２−３ツリ
ーと同様に、２−３ツリーに容易に変換することができ
る。これら手法の通信コストは、同様であるが、理由
は、ランダム・トリープの予想される深さがその２−３
ツリーの対応部分と類似しているからである。
【００５５】・ ランダム・トリープの主な利点は、そ
れらの実現が、２−３ツリーの実現と比べはるかに簡単
であることである。 ・ ランダム・トリープの使用における短所は、これら
の性能は、最悪の場合に保証されないことであり、例え
ば、あるユーザは、（確率は低いが）長い認証パスを得
ることがある。 ・ 別の短所は、より強力な仮定がディレクトリに関し
て必要となることである。ランダム・トリープの分析
は、敵（adversary）がトリープの正確な表現を知るこ
とはない、ということに基づいている。証明書の状態を
変更する能力をもつ信用できないディレクトリは、この
システムの計算作業および通信コストを増大させるおそ
れがある。
れらの実現が、２−３ツリーの実現と比べはるかに簡単
であることである。 ・ ランダム・トリープの使用における短所は、これら
の性能は、最悪の場合に保証されないことであり、例え
ば、あるユーザは、（確率は低いが）長い認証パスを得
ることがある。 ・ 別の短所は、より強力な仮定がディレクトリに関し
て必要となることである。ランダム・トリープの分析
は、敵（adversary）がトリープの正確な表現を知るこ
とはない、ということに基づいている。証明書の状態を
変更する能力をもつ信用できないディレクトリは、この
システムの計算作業および通信コストを増大させるおそ
れがある。
【００５６】本発明のシステムの動作は、図３に示した
本発明の１実施形態を参照する１つの非限定の動作シー
ケンスにおいて例示する。
本発明の１実施形態を参照する１つの非限定の動作シー
ケンスにおいて例示する。
【００５７】一般的に言えば、ＣＡ、ディレクトリ、ユ
ーザの手法において、次のステップを含む方法を提供す
る。 (a) ユーザは、ディレクトリに対し、少なくとも１つの
アイテムのリストであって、ある集合内のその少なくと
も１つのメンバーシップまたは非メンバーシップを認証
するためのリストを提供し、(b) ディレクトリは、ユー
ザに対し、上記少なくとも１つのアイテムにより誘起さ
れた認証パス（単数または複数）を計算し送信し、そし
て(c) ユーザは、上記アイテムを検証する。
ーザの手法において、次のステップを含む方法を提供す
る。 (a) ユーザは、ディレクトリに対し、少なくとも１つの
アイテムのリストであって、ある集合内のその少なくと
も１つのメンバーシップまたは非メンバーシップを認証
するためのリストを提供し、(b) ディレクトリは、ユー
ザに対し、上記少なくとも１つのアイテムにより誘起さ
れた認証パス（単数または複数）を計算し送信し、そし
て(c) ユーザは、上記アイテムを検証する。
【００５８】さらにまた、ＣＡ、ディレクトリ、ユーザ
の手法において、次のステップから成る方法を提供す
る。上記ＣＡは、(ｉ) 上記サーチ・ツリーを更新し
て、更新したノードを得るようにし、(ii) 前記更新さ
れたノードにより誘起された認証パスを計算し、そして
(iii) 少なくとも上記のルート修正されたノードをデジ
タル署名により認証し、(iv) 修正したパラメータを上
記ディレクトリに送信すること、を実行し、上記ディレ
クトリは、(ｉ) 上記の修正パラメータを適用すること
により、認証されたディレクトリ・ルート値を得るよう
にし、(ii) 上記認証されたＣＡルート値が上記認証さ
れたディレクトリ値と一致したか検証すること、を実行
する。次に、この一般的な態様の具体的な説明をする。
の手法において、次のステップから成る方法を提供す
る。上記ＣＡは、(ｉ) 上記サーチ・ツリーを更新し
て、更新したノードを得るようにし、(ii) 前記更新さ
れたノードにより誘起された認証パスを計算し、そして
(iii) 少なくとも上記のルート修正されたノードをデジ
タル署名により認証し、(iv) 修正したパラメータを上
記ディレクトリに送信すること、を実行し、上記ディレ
クトリは、(ｉ) 上記の修正パラメータを適用すること
により、認証されたディレクトリ・ルート値を得るよう
にし、(ii) 上記認証されたＣＡルート値が上記認証さ
れたディレクトリ値と一致したか検証すること、を実行
する。次に、この一般的な態様の具体的な説明をする。
【００５９】ＣＡ処理： ・証明書の作成： ＣＡは、証明書データ（例えば、ユ
ーザ名と公開鍵）、証明書連続番号、および満了日を含
むメッセージを認証することにより証明書を生成する。 ・初期化： ＣＡは、最初は取り消されている証明書の
集合に対して、上記のように２−３ツリーを作成する。
ＣＡは、ツリー・ノード全ての値を計算し記憶し、そし
てディレクトリに対し、取り消された証明書の連続番号
の（記憶された）リストを、ツリー・ルート値、ツリー
の高さおよびタイムスタンプを含む署名したメッセージ
と共に送る。 ・更新： ＣＡは、ツリーに対し証明書の挿入／削除を
行うことによりツリーを更新する。各挿入／削除の後、
全ての誘起されたノードを更新し、そしてそれにしたが
って認証されたパスを計算する。ディレクトリを更新す
るには、ＣＡは、修正パラメータを送る。これは、例え
ば誘起されたノードのリスト、取引のリストである。実
際には、修正パラメータは、ディレクトリがツリーをデ
ィレクトリ端において更新できるようにする情報であれ
ばどのような種類のものをも包含する。もちろん、ルー
トを認証することには、もちろん新たなルート値を含む
だけでなく、他の認証された情報、例えばツリーの高さ
およびタイムスタンプも同様に含むことができる。
ーザ名と公開鍵）、証明書連続番号、および満了日を含
むメッセージを認証することにより証明書を生成する。 ・初期化： ＣＡは、最初は取り消されている証明書の
集合に対して、上記のように２−３ツリーを作成する。
ＣＡは、ツリー・ノード全ての値を計算し記憶し、そし
てディレクトリに対し、取り消された証明書の連続番号
の（記憶された）リストを、ツリー・ルート値、ツリー
の高さおよびタイムスタンプを含む署名したメッセージ
と共に送る。 ・更新： ＣＡは、ツリーに対し証明書の挿入／削除を
行うことによりツリーを更新する。各挿入／削除の後、
全ての誘起されたノードを更新し、そしてそれにしたが
って認証されたパスを計算する。ディレクトリを更新す
るには、ＣＡは、修正パラメータを送る。これは、例え
ば誘起されたノードのリスト、取引のリストである。実
際には、修正パラメータは、ディレクトリがツリーをデ
ィレクトリ端において更新できるようにする情報であれ
ばどのような種類のものをも包含する。もちろん、ルー
トを認証することには、もちろん新たなルート値を含む
だけでなく、他の認証された情報、例えばツリーの高さ
およびタイムスタンプも同様に含むことができる。
【００６０】ディレクトリ処理： ・初期化： 最初は取り消されている証明書リストを受
け取ったときに、ディレクトリは、ディレクトリ自身で
２−３ツリー全体を計算し、そのルート値、ツリー高
さ、およびタイムスタンプをチェックし、そしてこれら
の値におけるＣＡの署名を検証する。
け取ったときに、ディレクトリは、ディレクトリ自身で
２−３ツリー全体を計算し、そのルート値、ツリー高
さ、およびタイムスタンプをチェックし、そしてこれら
の値におけるＣＡの署名を検証する。
【００６１】・ＣＡの更新に対する応答： ディレクト
リは、ＣＡから受けた修正されたパラメータにしたがっ
てツリーを更新する。これにより、再計算したパスと認
証されたディレクトリ・ルートが生じる。これを行うこ
とにより、ＣＡから受けた受信した認証されたルート値
に対してその得たルート値をチェックし検証することに
より、一致するか判定し、そして一致する場合には、こ
の手順は、首尾良く終了する。この特定の実施形態で
は、上記のルート値、ツリー高さおよびタイムスタンプ
全てが一致しなければならない（時間は、もちろん妥当
なインターバル内である）。
リは、ＣＡから受けた修正されたパラメータにしたがっ
てツリーを更新する。これにより、再計算したパスと認
証されたディレクトリ・ルートが生じる。これを行うこ
とにより、ＣＡから受けた受信した認証されたルート値
に対してその得たルート値をチェックし検証することに
より、一致するか判定し、そして一致する場合には、こ
の手順は、首尾良く終了する。この特定の実施形態で
は、上記のルート値、ツリー高さおよびタイムスタンプ
全てが一致しなければならない（時間は、もちろん妥当
なインターバル内である）。
【００６２】・ユーザの照会に対する応答： ユーザの
照会に回答するため、ディレクトリは、ユーザに対し、
その認証したルート値、ツリー高さおよびタイムスタン
プを供給する。 １． その照会された証明書が取り消されている場合、
そのルートから照会された証明書に対応するリーフまで
のパスにおける各ノードに関して、ディレクトリは、ユ
ーザにその値およびその子供の値を供給する。 ２． 照会された証明書が取り消されていない（リスト
にない）場合、ディレクトリは、ユーザに対し、隣接す
る２つのリーフl1, l2へのパスを供給することにより、
l1（またはl2）の値が照会された連続番号よりも小さく
なる（または大きくなる）ようにする。
照会に回答するため、ディレクトリは、ユーザに対し、
その認証したルート値、ツリー高さおよびタイムスタン
プを供給する。 １． その照会された証明書が取り消されている場合、
そのルートから照会された証明書に対応するリーフまで
のパスにおける各ノードに関して、ディレクトリは、ユ
ーザにその値およびその子供の値を供給する。 ２． 照会された証明書が取り消されていない（リスト
にない）場合、ディレクトリは、ユーザに対し、隣接す
る２つのリーフl1, l2へのパスを供給することにより、
l1（またはl2）の値が照会された連続番号よりも小さく
なる（または大きくなる）ようにする。
【００６３】ここで、通信コストを削減するため、ディ
レクトリは、ルートからのパス上のノード値を送る必要
はないが、ユーザがサーチ・パス全体を計算するのに必
要なもののみを送る必要がある。これは、図１を参照し
て例示したものであり、ここで想起されるように、Y5,
H(6,6,Y), H(7,8,Y)およびH(1,4,Y)のみが、Y5のサーチ
・パスを認証するのに必要だったものである。
レクトリは、ルートからのパス上のノード値を送る必要
はないが、ユーザがサーチ・パス全体を計算するのに必
要なもののみを送る必要がある。これは、図１を参照し
て例示したものであり、ここで想起されるように、Y5,
H(6,6,Y), H(7,8,Y)およびH(1,4,Y)のみが、Y5のサーチ
・パスを認証するのに必要だったものである。
【００６４】ユーザ処理：ユーザは、まず初めに証明書
に対するＣＡの署名を検証し、そして証明書の満了日を
チェックする。次に、ユーザは、その証明書連続番号s
をディレクトリに送ることにより照会を発する。照会に
対するディレクトリからの回答を受け取ると、ユーザ
は、そのルート値、ツリー高さおよびタイムスタンプに
対するＣＡの署名を検証する。 １． ディレクトリが、照会に係る証明書が取り消され
ていると主張した場合、ユーザは、ハッシュ関数hを適
用することにより、ディレクトリが供給したリーフから
ルートまでのパスをチェックする。 ２． ディレクトリが、その照会に係る証明書が取り消
されていないと主張した場合、ユーザは、ディレクトリ
が供給した２つのパスをチェックし、そしてこれらが２
−３ツリー内の値l1, l2をもつ２つの隣接リーフに至る
ことをチェックする。ユーザは、l1< s < l2であること
をチェックする。図２のＢに示すように、xを認証する
（すなわち、xが取り消しリストに属していないことを
主張する）ため、隣接メンバx1, x2を認証するサーチ・
パスを送信する。ただし、x1 < x < x2である。
に対するＣＡの署名を検証し、そして証明書の満了日を
チェックする。次に、ユーザは、その証明書連続番号s
をディレクトリに送ることにより照会を発する。照会に
対するディレクトリからの回答を受け取ると、ユーザ
は、そのルート値、ツリー高さおよびタイムスタンプに
対するＣＡの署名を検証する。 １． ディレクトリが、照会に係る証明書が取り消され
ていると主張した場合、ユーザは、ハッシュ関数hを適
用することにより、ディレクトリが供給したリーフから
ルートまでのパスをチェックする。 ２． ディレクトリが、その照会に係る証明書が取り消
されていないと主張した場合、ユーザは、ディレクトリ
が供給した２つのパスをチェックし、そしてこれらが２
−３ツリー内の値l1, l2をもつ２つの隣接リーフに至る
ことをチェックする。ユーザは、l1< s < l2であること
をチェックする。図２のＢに示すように、xを認証する
（すなわち、xが取り消しリストに属していないことを
主張する）ため、隣接メンバx1, x2を認証するサーチ・
パスを送信する。ただし、x1 < x < x2である。
【００６５】上記手法においては、証明書が取り消され
ていなかったことを検証する通信コストは、証明書がリ
ストにあることを検証するときの通信コストの２倍とな
ることがある。これを克服するには、ツリーは、どのノ
ードも連続した２つの連続番号に対応するように構築し
て、いずれの場合においても１つのパスのみを送るだけ
で済むようにできる。１つのツリー・ノードの値を保持
するのに必要なビット数、すなわち、ハッシュ関数のセ
キュリティ・パラメータ（以下ではlhashと記す）は、
証明書の連続番号を保持するのに必要なビットの２倍以
上であるため、これは、ツリー・サイズに影響を及ぼさ
ない。これと関係して、想起されるように、“証明書”
または“アイテム”は、とりわけ値のレンジを含む。
ていなかったことを検証する通信コストは、証明書がリ
ストにあることを検証するときの通信コストの２倍とな
ることがある。これを克服するには、ツリーは、どのノ
ードも連続した２つの連続番号に対応するように構築し
て、いずれの場合においても１つのパスのみを送るだけ
で済むようにできる。１つのツリー・ノードの値を保持
するのに必要なビット数、すなわち、ハッシュ関数のセ
キュリティ・パラメータ（以下ではlhashと記す）は、
証明書の連続番号を保持するのに必要なビットの２倍以
上であるため、これは、ツリー・サイズに影響を及ぼさ
ない。これと関係して、想起されるように、“証明書”
または“アイテム”は、とりわけ値のレンジを含む。
【００６６】次に、図４を参照すると、これは、本発明
の別の実施形態によるシステム構成を示している。これ
では、ある種のプロトコルが、短期証明書（short-term
certificate）を使用することにより、取り消しシステ
ムの必要性を回避している（例えば、証明書の所有者が
ある限られた損害を起こし得る場合には、マイクロペイ
メント・プロトコル（micropayments protocols）[1
3]）。これら証明書は、毎日発行し、そしてその発行日
の終わりに満了する。実際には、さらに短い期間が望ま
しいが、主要な制限は、短期証明書が生じさせる証明機
関の計算（ユーザ全てに対する証明書を毎日計算しなけ
ればならない）と通信（証明書はその所有者に送らなけ
ればならない）の増大に起因する。
の別の実施形態によるシステム構成を示している。これ
では、ある種のプロトコルが、短期証明書（short-term
certificate）を使用することにより、取り消しシステ
ムの必要性を回避している（例えば、証明書の所有者が
ある限られた損害を起こし得る場合には、マイクロペイ
メント・プロトコル（micropayments protocols）[1
3]）。これら証明書は、毎日発行し、そしてその発行日
の終わりに満了する。実際には、さらに短い期間が望ま
しいが、主要な制限は、短期証明書が生じさせる証明機
関の計算（ユーザ全てに対する証明書を毎日計算しなけ
ればならない）と通信（証明書はその所有者に送らなけ
ればならない）の増大に起因する。
【００６７】（ＣＲＳのような）オンライン／オフライ
ンのデジタル署名手法は、ＣＡが実行しなければならな
い計算を低減させるけれども、通信コストを大きく減少
させないが、それは、ＣＡが“異なった”メッセージを
“異なった”ユーザに送らなければならず、ＣＡを通信
のボトルネックとするからである。これは解決を必要と
し、この解決では、ＣＡは、（例えば、新たなユーザと
証明書が更新されていないユーザのみに関して）単純な
計算を実行し、そして共通の更新メッセージを“全て”
のユーザに送る。このメッセージを使えば、非取り消し
の証明書をもつ正確に全てのユーザは、彼らの証明書の
有効性を証明することができることになる。この実施形
態に合うようにするには、証明書取り消し手法に対する
簡単な修正を提案し、これにより、ＣＡが同一の更新メ
ッセージを全てのユーザに送る効率的な証明書更新手法
がもたらされる。この解決法においては、全ての証明書
についての情報を備えたディレクトリ（図４参照）の存
在を全く仮定していないが、ディレクトリが送出した最
新のメッセージを保有することができるローカルのディ
レクトリの存在を仮定している。
ンのデジタル署名手法は、ＣＡが実行しなければならな
い計算を低減させるけれども、通信コストを大きく減少
させないが、それは、ＣＡが“異なった”メッセージを
“異なった”ユーザに送らなければならず、ＣＡを通信
のボトルネックとするからである。これは解決を必要と
し、この解決では、ＣＡは、（例えば、新たなユーザと
証明書が更新されていないユーザのみに関して）単純な
計算を実行し、そして共通の更新メッセージを“全て”
のユーザに送る。このメッセージを使えば、非取り消し
の証明書をもつ正確に全てのユーザは、彼らの証明書の
有効性を証明することができることになる。この実施形
態に合うようにするには、証明書取り消し手法に対する
簡単な修正を提案し、これにより、ＣＡが同一の更新メ
ッセージを全てのユーザに送る効率的な証明書更新手法
がもたらされる。この解決法においては、全ての証明書
についての情報を備えたディレクトリ（図４参照）の存
在を全く仮定していないが、ディレクトリが送出した最
新のメッセージを保有することができるローカルのディ
レクトリの存在を仮定している。
【００６８】前と同じように、この手法は、上記に提示
した証明機関が作成した取り消した証明書（あるいはさ
もなければ有効な証明書）のツリーに基づいている。デ
ィレクトリから証明書を抽出する方法が全くないため、
どのユーザも、初期の証明書を得て、そしてこれは、Ｃ
Ａのメッセージを使用して更新することができる。詳細
には、ＣＡは、どの発行された証明書をも、その有効性
を証明するパスで拡大し、そしてこれのみが、証明書の
周期的に更新される部分である。
した証明機関が作成した取り消した証明書（あるいはさ
もなければ有効な証明書）のツリーに基づいている。デ
ィレクトリから証明書を抽出する方法が全くないため、
どのユーザも、初期の証明書を得て、そしてこれは、Ｃ
Ａのメッセージを使用して更新することができる。詳細
には、ＣＡは、どの発行された証明書をも、その有効性
を証明するパスで拡大し、そしてこれのみが、証明書の
周期的に更新される部分である。
【００６９】全ての証明書を同時に更新するには、ＣＡ
は、ツリーのそのコピーを更新し、そして前の更新から
変更したツリー・パス（誘起されたサブツリーの１つの
非限定の形態を構成する）を発表する。（図５Ａを参照
されたい）。非取り消しの証明書を保持する各ユーザ
は、好ましくはその自己パスと一致するパス上の最下位
のノードvを位置づけることにより誘起されたツリーと
その自己パスを交差させ、そしてvから（ルートまで）
新たなノード値をコピーすることにより彼のパスを更新
する。取り消された証明書を保持する全てのユーザは、
関数hlの一方向性特性を壊さない限り、彼らのパスを更
新することができない。図５Ｂに示したように、ユーザ
は、自己パスを誘起されたサブツリーと一致するように
し、そして最下位の不一致のノード（図５Ａにおいてド
ット１００で示す）を求める。行うべき残っていること
は、上記の検出したノードからルートまでのノードを更
新し、そしてそのルートを認証してこれをＣＡから送信
された認証されたルート値に対し検証することである。
この手順は、各ユーザに課される計算オーバーヘッドの
点からは、明らかに非常にコスト的に効果がある。
は、ツリーのそのコピーを更新し、そして前の更新から
変更したツリー・パス（誘起されたサブツリーの１つの
非限定の形態を構成する）を発表する。（図５Ａを参照
されたい）。非取り消しの証明書を保持する各ユーザ
は、好ましくはその自己パスと一致するパス上の最下位
のノードvを位置づけることにより誘起されたツリーと
その自己パスを交差させ、そしてvから（ルートまで）
新たなノード値をコピーすることにより彼のパスを更新
する。取り消された証明書を保持する全てのユーザは、
関数hlの一方向性特性を壊さない限り、彼らのパスを更
新することができない。図５Ｂに示したように、ユーザ
は、自己パスを誘起されたサブツリーと一致するように
し、そして最下位の不一致のノード（図５Ａにおいてド
ット１００で示す）を求める。行うべき残っていること
は、上記の検出したノードからルートまでのノードを更
新し、そしてそのルートを認証してこれをＣＡから送信
された認証されたルート値に対し検証することである。
この手順は、各ユーザに課される計算オーバーヘッドの
点からは、明らかに非常にコスト的に効果がある。
【００７０】ＣＡ通信を低減するため、例えば証明書を
１時間毎に更新する、というようにこの更新手法を使用
することができる。これは、あるユーザが彼らの証明書
の更新に遅れを生じることがあり、したがってローカル
・ディレクトリは、（例えば在来のプロキシ・サーバを
使用することにより）いくつかの最新の更新メッセージ
を蓄えておくべきであり、そしていくつかの集団が、更
新をして（１日の更新メッセージを結合する）数日遅れ
たユーザが証明書の更新をすることを可能にする。
１時間毎に更新する、というようにこの更新手法を使用
することができる。これは、あるユーザが彼らの証明書
の更新に遅れを生じることがあり、したがってローカル
・ディレクトリは、（例えば在来のプロキシ・サーバを
使用することにより）いくつかの最新の更新メッセージ
を蓄えておくべきであり、そしていくつかの集団が、更
新をして（１日の更新メッセージを結合する）数日遅れ
たユーザが証明書の更新をすることを可能にする。
【００７１】この後者の詳細な説明は、より一般的には
以下の通り定め、ＣＡ、ユーザ手法における請求項６記
載の方法は、以下から成る。上記ＣＡは、(ｉ)上記サー
チ・ツリーを更新して、更新したノードを取得し、(ii)
上記更新したノードが誘起した認証パスを計算し、(ii
i)少なくとも上記のルート修正したノードをデジタル署
名により認証し、(iv)誘起したサブツリーを上記ユーザ
に送信すること、を実行し、上記ユーザは、(ｉ)前記誘
起されたサブツリーをユーザの自己パスと交差させ、そ
してユーザ認証されたルート値を取得し、(ii)認証され
たＣＡルート値が認証されたユーザ値と一致したことを
検証すること、を実行する。
以下の通り定め、ＣＡ、ユーザ手法における請求項６記
載の方法は、以下から成る。上記ＣＡは、(ｉ)上記サー
チ・ツリーを更新して、更新したノードを取得し、(ii)
上記更新したノードが誘起した認証パスを計算し、(ii
i)少なくとも上記のルート修正したノードをデジタル署
名により認証し、(iv)誘起したサブツリーを上記ユーザ
に送信すること、を実行し、上記ユーザは、(ｉ)前記誘
起されたサブツリーをユーザの自己パスと交差させ、そ
してユーザ認証されたルート値を取得し、(ii)認証され
たＣＡルート値が認証されたユーザ値と一致したことを
検証すること、を実行する。
【００７２】当業者には容易に理解されるように、図３
および図４の実施形態の実現は、どのような特定のハー
ドウェアあるいはソフトウェア・アーキテクチャにも拘
束されるものではない。したがって、非限定の例では、
ＣＡ、ディレクトリおよびユーザは、任意の利用可能な
通信ネットワーク、例えばインターネットにより相互に
リンクすることができる。別の非限定の例では、詳細な
構成要素の各々は、特定の用途に依存して、必要でかつ
適当な限り、例えば在来のＰＣコンピュータ、メインフ
レーム・コンピュータ、あるいはコンピュータのネット
ワークで実現できる。
および図４の実施形態の実現は、どのような特定のハー
ドウェアあるいはソフトウェア・アーキテクチャにも拘
束されるものではない。したがって、非限定の例では、
ＣＡ、ディレクトリおよびユーザは、任意の利用可能な
通信ネットワーク、例えばインターネットにより相互に
リンクすることができる。別の非限定の例では、詳細な
構成要素の各々は、特定の用途に依存して、必要でかつ
適当な限り、例えば在来のＰＣコンピュータ、メインフ
レーム・コンピュータ、あるいはコンピュータのネット
ワークで実現できる。
【００７３】評価 以下においては、ＣＲＬと、ＣＲＳと、本発明のシステ
ム／方法の１つの非限定の実施形態との通信コストを比
較する。この分析に基づき、提案したシステムは、パラ
メータの変化に対しより強じんであり、そして他のもの
と比べより高い更新レートを可能にすることが示され
た。提案した手法の他の利点は、以下の通りである。 ・ ＣＡは、ＣＲＳにおけるよりもより少ない機密しか
保持する必要がない。 ・ ＣＡ−ディレクトリ間通信が低いため、ＣＡは、Ｃ
Ａのコンピュータへの侵入に対し安全な低速通信回線を
使ってディレクトリと通信するようにすることができる
（このシステム・セキュリティは、ＣＡの機密を保護す
る能力に基づいたものである。）。 ・ ２−３ツリーの場合においては、更新するのにツリ
ー全体を再計算する必要が決してない。これは、ＣＲＴ
と比べより高い更新レートを可能にする。 ・ 低いＣＡ−ディレクトリ間通信の別の結果として、
ＣＡは、多くのディレクトリを更新することができ、通
信ネットワークにおけるボトルネックを回避できる。
ム／方法の１つの非限定の実施形態との通信コストを比
較する。この分析に基づき、提案したシステムは、パラ
メータの変化に対しより強じんであり、そして他のもの
と比べより高い更新レートを可能にすることが示され
た。提案した手法の他の利点は、以下の通りである。 ・ ＣＡは、ＣＲＳにおけるよりもより少ない機密しか
保持する必要がない。 ・ ＣＡ−ディレクトリ間通信が低いため、ＣＡは、Ｃ
Ａのコンピュータへの侵入に対し安全な低速通信回線を
使ってディレクトリと通信するようにすることができる
（このシステム・セキュリティは、ＣＡの機密を保護す
る能力に基づいたものである。）。 ・ ２−３ツリーの場合においては、更新するのにツリ
ー全体を再計算する必要が決してない。これは、ＣＲＴ
と比べより高い更新レートを可能にする。 ・ 低いＣＡ−ディレクトリ間通信の別の結果として、
ＣＡは、多くのディレクトリを更新することができ、通
信ネットワークにおけるボトルネックを回避できる。
【００７４】通信コスト 我々が考察するパラメータは、以下の通りである。 ・n−証明書の見積もり総数（n = 3, 000, 000） ・k−１つのＣＡが取り扱う証明書の見積もり平均数（k
= 30, 000） ・p−満了前に取り消される証明書の見積もり割合（p =
0. 1）。（証明書は１年間に発行され、したがって毎
日取り消される証明書の数は、n.p.lsn/365である、と
仮定する。） ・q−１日当たりに証明書の状態が照会される見積もり
数(q = 3, 000, 000) ・T−１日当たりの更新数（T = 1） ・lsn−証明書の連続番号を保持するのに必要なビット
数（Isn= 20） ・lstat−証明書取り消し状態数Y365-iおよびN0を保持
するのに必要なビット数（lstat = 100） ・lsig−署名の長さ（lsig = 1, 000） ・lhash−ハッシュ関数のセキュリティ・パラメータ（l
hash = 128） n, k, p, q, T, lsn, lstatの値は、Micali [18]から取
得し、そしてlsig , l hashは、本発明の手法に特有であ
る。
= 30, 000） ・p−満了前に取り消される証明書の見積もり割合（p =
0. 1）。（証明書は１年間に発行され、したがって毎
日取り消される証明書の数は、n.p.lsn/365である、と
仮定する。） ・q−１日当たりに証明書の状態が照会される見積もり
数(q = 3, 000, 000) ・T−１日当たりの更新数（T = 1） ・lsn−証明書の連続番号を保持するのに必要なビット
数（Isn= 20） ・lstat−証明書取り消し状態数Y365-iおよびN0を保持
するのに必要なビット数（lstat = 100） ・lsig−署名の長さ（lsig = 1, 000） ・lhash−ハッシュ関数のセキュリティ・パラメータ（l
hash = 128） n, k, p, q, T, lsn, lstatの値は、Micali [18]から取
得し、そしてlsig , l hashは、本発明の手法に特有であ
る。
【００７５】ＣＲＬコスト ・ ＣＲＬの毎日の更新コストは、T.n.p-= lsnであ
り、これは、各ＣＡが各更新においてＣＲＬ全体をディ
レクトリに送るためである。代替の更新手順では、ＣＡ
は、ディレクトリに対し、差リストのみ（前のＣＲＬに
対し追加／除去する連続番号）を送り、これのコスト
は、n.p.lsn/365である。 ・ ＣＲＬの毎日の照会コストは、q.p.k.lsnである
が、それは、各照会に関して、ディレクトリがＣＲＬ全
体を照会側のユーザに送るからである。
り、これは、各ＣＡが各更新においてＣＲＬ全体をディ
レクトリに送るためである。代替の更新手順では、ＣＡ
は、ディレクトリに対し、差リストのみ（前のＣＲＬに
対し追加／除去する連続番号）を送り、これのコスト
は、n.p.lsn/365である。 ・ ＣＲＬの毎日の照会コストは、q.p.k.lsnである
が、それは、各照会に関して、ディレクトリがＣＲＬ全
体を照会側のユーザに送るからである。
【００７６】ＣＲＳコスト ・ ＣＲＳの毎日の更新コストは、T.n.(lsn + lstat)
であるが、それは、どの証明書に関しても、ＣＡは、l
statビットの証明書取り消し状態を送るからである。 ・ ＣＲＳの毎日の照会コストは、lstat.qである。
であるが、それは、どの証明書に関しても、ＣＡは、l
statビットの証明書取り消し状態を送るからである。 ・ ＣＲＳの毎日の照会コストは、lstat.qである。
【００７７】提案した手法 ディレクトリを更新するためには、ＣＡは、n.p. lsn/3
65+T. lsigの毎日の総合の長さの差リストを送る。 ・ ユーザの照会に回答するため、ディレクトリは、2.
log2(p・k)までの数を送り、各々がlhashビット長であ
り、全部で2.q.lhash.log2(p・k)ビットである。
65+T. lsigの毎日の総合の長さの差リストを送る。 ・ ユーザの照会に回答するため、ディレクトリは、2.
log2(p・k)までの数を送り、各々がlhashビット長であ
り、全部で2.q.lhash.log2(p・k)ビットである。
【００７８】以下の表は、３つの手法による毎日の通信
コスト（ビット）の見積もりを示している。
コスト（ビット）の見積もりを示している。
【００７９】
【表１】
【００８０】この表に示したように、提案した手法のコ
ストは、ＣＲＬのコストと比べ、ＣＡ−ディレクトリ間
並びにディレクトリ−ユーザ間の両方の通信において低
い。ＣＡ−ディレクトリ間コストは、対応するＣＲＳの
コストよりもはるかに低いが、ディレクトリ−ユーザ間
（したがって全て）の通信コストは増大している。尚、
実際には、通信オーバーヘッドのため、ディレクトリ−
ユーザ間通信におけるＣＲＳと本提案方法との間の差
は、それ程でもない。
ストは、ＣＲＬのコストと比べ、ＣＡ−ディレクトリ間
並びにディレクトリ−ユーザ間の両方の通信において低
い。ＣＡ−ディレクトリ間コストは、対応するＣＲＳの
コストよりもはるかに低いが、ディレクトリ−ユーザ間
（したがって全て）の通信コストは増大している。尚、
実際には、通信オーバーヘッドのため、ディレクトリ−
ユーザ間通信におけるＣＲＳと本提案方法との間の差
は、それ程でもない。
【００８１】本提案手法は、ＣＲＬおよびＣＲＳよりも
パラメータの変化に対してより強じんである。何故な
ら、それらＣＲＬとＣＲＳは時間変化に拘束されるた
め、あるいは異なった実施の特定の必要によるため、そ
のような変化に対し強じんなシステムとすることが重要
である。
パラメータの変化に対してより強じんである。何故な
ら、それらＣＲＬとＣＲＳは時間変化に拘束されるた
め、あるいは異なった実施の特定の必要によるため、そ
のような変化に対し強じんなシステムとすることが重要
である。
【００８２】変化は、主に証明書の総数（n）および更
新レート（T）に起きる。提案方法においては、nの変化
は、pのファクタで加減している。Tの変化は、更新通信
コストがnTではなくTに比例しているということにより
適度にされている。図８は、３つの方法のＣＡ−ディレ
クトリ間の更新通信コストがどのように更新レート（そ
の他の全てのパラメータは一定とする）に依存している
かを示している。この更新通信コストは、ＣＲＳを１日
に１回の更新に制限する（この更新レートを制限する別
のファクタは、証明書が取り消されていなかったことを
検証するためユーザが必要とする計算の量である。）。
提案手法は、はるかに強じんであり、１時間に１回の更
新でも許容できる。
新レート（T）に起きる。提案方法においては、nの変化
は、pのファクタで加減している。Tの変化は、更新通信
コストがnTではなくTに比例しているということにより
適度にされている。図８は、３つの方法のＣＡ−ディレ
クトリ間の更新通信コストがどのように更新レート（そ
の他の全てのパラメータは一定とする）に依存している
かを示している。この更新通信コストは、ＣＲＳを１日
に１回の更新に制限する（この更新レートを制限する別
のファクタは、証明書が取り消されていなかったことを
検証するためユーザが必要とする計算の量である。）。
提案手法は、はるかに強じんであり、１時間に１回の更
新でも許容できる。
【００８３】以上、本発明についてある程度具体的に説
明したが、特許請求の範囲に定めた本発明の範囲および
要旨から逸脱せずに種々の変更および置換が行えること
は理解されるべきである。
明したが、特許請求の範囲に定めた本発明の範囲および
要旨から逸脱せずに種々の変更および置換が行えること
は理解されるべきである。
【図１】従来技術による認証ツリーを示す。
【図２】ＡとＢは、本発明の１実施形態によるサーチ認
証形ツリーを示す。
証形ツリーを示す。
【図３】本発明の１実施形態によるシステム構成を示
す。
す。
【図４】本発明の別の実施形態によるシステム構成を示
す。
す。
【図５】ＡとＢは、サーチ認証形ツリーを図４の実施形
態により更新する方法を示す。
態により更新する方法を示す。
Y1−Y8 クレジットカード ｃ１−ｃ７ 証明書の連続番号
Claims (9)
- 【請求項１】 集合内のアイテムのメンバーシップまた
は非メンバーシップを認証するよう作用する認証形サー
チ・ツリーを含むメモリにおいて、前記認証形サーチ・
ツリーが、 ノードとリーフを有しかつこれらに関連してサーチ手法
を有したサーチ・ツリーであって、前記ノードがダイナ
ミック・サーチ値を含み、前記リーフが前記集合のアイ
テムを含み、前記ノードの各々には、暗号化ハッシュ関
数値を関連付け、該暗号化ハッシュ関数値は、少なくと
も（Ｉ）子ノードの暗号化ハッシュ値と、（II）前記ノ
ードの前記ダイナミック・サーチ値と、に暗号化ハッシ
ュ関数を適用することにより発生する、前記のサーチ・
ツリーと、 デジタル署名により認証した前記認証形サーチ・ツリー
の少なくともルート・ノードと、を備えたこと、を特徴
とする認証形サーチ・ツリー。 - 【請求項２】 請求項１記載のサーチ認証形ツリーにお
いて、前記暗号化ハッシュ関数がユニバーサル一方向性
関数タイプのものであり、前記暗号化一方向性関数を、
各内部ノードに固有のユニバーサル一方向性関数にさら
に適用したこと、を特徴とするサーチ認証形ツリー。 - 【請求項３】 請求項１記載のサーチ認証形ツリーにお
いて、前記サーチ・ツリーはBtreeであること、を特徴
とするサーチ認証形ツリー。 - 【請求項４】 請求項１記載のサーチ認証形ツリーにお
いて、前記サーチ・ツリーは２−３ツリーであること、
を特徴とするサーチ認証形ツリー。 - 【請求項５】 集合内のアイテムのメンバーシップまた
は非メンバーシップを認証する方法が、 （ｉ）請求項１記載の認証形サーチ・ツリーを提供し、 （ii）前記集合の少なくとも１つのアイテムの認証を、
該少なくとも１つのアイテムと前記ルートにより誘起さ
れる認証パスを計算することにより行うこと、から成る
認証方法。 - 【請求項６】 集合内の少なくとも１つのアイテムを認
証形サーチ・ツリーにおいて更新する方法が、 （ｉ）請求項１記載の認証形サーチ・ツリーを提供し、 （ii）前記サーチ・ツリーを更新することにより更新し
たノードを獲得し、 （iii）前記更新したノードにより誘起された認証パス
を計算し、 （iv）少なくとも前記のルート修正したノードをデジタ
ル署名により認証すること、から成る更新方法。 - 【請求項７】 請求項５記載の方法において、ＣＡ、デ
ィレクトリ、ユーザの手法において、前記ステップ（i
i）は、 （ａ）前記ユーザが、集合内の少なくとも１つのアイテ
ムのメンバーシップまたは非メンバーシップを認証する
ため、前記少なくとも１つのアイテムのリストをディレ
クトリに提供し、 （ｂ）前記ディレクトリが、前記少なくとも１つのアイ
テムにより誘起された前記認証パス（複数）を計算しこ
れをユーザに送信し、前記ディレクトリがさらに前記認
証パスを送信し、 （ｃ）前記ユーザが前記アイテムを検証すること、を含
むこと、を特徴とする認証方法。 - 【請求項８】 請求項６記載の方法において、ＣＡ、デ
ィレクトリ、ユーザの手法において、 前記ＣＡが （ｉ）前記サーチ・ツリーを更新することにより、更新
したノードを獲得し、 （ii）前記更新したノードにより誘起された認証パスを
計算し、 （iii）少なくとも前記のルート修正したノードをデジ
タル署名により認証し、 （iv）修正したパラメータを前記ディレクトリに送信す
ること、を実行し、 前記ディレクトリが、 （ｉ）前記修正パラメータを適用することにより認証し
たディレクトリ・ルート値を獲得し、 （ii）前記認証したＣＡルート値が前記認証したディレ
クトリ値と一致したか検証すること、を実行すること、
を特徴とする認証方法。 - 【請求項９】 請求項６記載の方法において、ＣＡ、ユ
ーザの手法においては、 前記ＣＡが、 （ｉ）前記サーチ・ツリーを更新することにより更新し
たノードを獲得し、 （ii）前記更新したノードにより誘起された認証パスを
計算し、 （iii）少なくとも前記のルート修正したノードをデジ
タル署名により認証し、 （ｖ）誘起されたサブツリーを前記ユーザに送信するこ
と、を実行し、 前記ユーザが、 （iii）前記誘起されたサブツリーをユーザの自己パス
と交差させそしてユーザ認証されたルート値を獲得し、 （iv）前記認証されたＣＡルート値が前記認証されたユ
ーザ値と一致したか検証すること、を実行すること、を
特徴とする認証方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US010571 | 1998-01-22 | ||
| US09/010,571 US6226743B1 (en) | 1998-01-22 | 1998-01-22 | Method for authentication item |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11289329A true JPH11289329A (ja) | 1999-10-19 |
Family
ID=21746367
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11053084A Pending JPH11289329A (ja) | 1998-01-22 | 1999-01-22 | 認証形サ―チ・ツリ― |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6226743B1 (ja) |
| EP (1) | EP0932109A3 (ja) |
| JP (1) | JPH11289329A (ja) |
| IL (1) | IL128040A (ja) |
Cited By (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001015381A1 (en) * | 1999-08-21 | 2001-03-01 | Danal Co., Ltd. | User authentication system using second connection path |
| JP2002072876A (ja) * | 2000-08-30 | 2002-03-12 | Hitachi Ltd | 証明書の有効性確認方法および装置 |
| JP2003533940A (ja) * | 2000-05-16 | 2003-11-11 | シュアティー ドット コム | デジタルレコードを自己認証するための方法及び装置 |
| WO2005117336A1 (ja) * | 2004-05-28 | 2005-12-08 | Matsushita Electric Industrial Co., Ltd. | 親子カード認証システム |
| KR100625154B1 (ko) * | 2003-10-10 | 2006-09-20 | 가부시키가이샤 히타치세이사쿠쇼 | 공개 키 증명서 검증의 고속화 방법, 및 장치 |
| JP2006287455A (ja) * | 2005-03-31 | 2006-10-19 | Nec Corp | 証明書検証装置及び方法並びに証明書検証サーバ |
| JP2007505555A (ja) * | 2003-09-10 | 2007-03-08 | 株式会社エヌ・ティ・ティ・ドコモ | 安全で小額の信用課金をサービスプロバイダが認証可能に測定するための方法及び装置 |
| JP2007506365A (ja) * | 2003-09-19 | 2007-03-15 | 株式会社エヌ・ティ・ティ・ドコモ | 証明書を効率的に無効にする方法及び装置 |
| JP2007515837A (ja) * | 2003-11-21 | 2007-06-14 | エリコス ピッツォス | データ管理処理およびデータ配送処理において完全性および信頼を提供する方法およびシステム |
| JP2007515890A (ja) * | 2003-12-22 | 2007-06-14 | リナックスプローブ株式会社 | デジタル証明書を生成するためのシステムおよび方法 |
| JP2008524931A (ja) * | 2004-12-17 | 2008-07-10 | 株式会社エヌ・ティ・ティ・ドコモ | 証明書の有効性／無効性証明用暗号化証明データを用いた複数証明書失効 |
| JP2008263645A (ja) * | 2001-03-29 | 2008-10-30 | Matsushita Electric Ind Co Ltd | 暗号化を施すことによりデータを保護するデータ保護システム |
| US7512786B2 (en) | 1999-12-10 | 2009-03-31 | Microsoft Corporation | Client-side boot domains and boot rules |
| US8006086B2 (en) | 2004-08-31 | 2011-08-23 | Ntt Docomo, Inc. | Revocation of cryptographic digital certificates |
Families Citing this family (65)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5903651A (en) * | 1996-05-14 | 1999-05-11 | Valicert, Inc. | Apparatus and method for demonstrating and confirming the status of a digital certificates and other data |
| US6901509B1 (en) * | 1996-05-14 | 2005-05-31 | Tumbleweed Communications Corp. | Apparatus and method for demonstrating and confirming the status of a digital certificates and other data |
| US6701434B1 (en) * | 1999-05-07 | 2004-03-02 | International Business Machines Corporation | Efficient hybrid public key signature scheme |
| US6826687B1 (en) * | 1999-05-07 | 2004-11-30 | International Business Machines Corporation | Commitments in signatures |
| US6393420B1 (en) * | 1999-06-03 | 2002-05-21 | International Business Machines Corporation | Securing Web server source documents and executables |
| US6546376B1 (en) * | 1999-06-25 | 2003-04-08 | Institute For Information Industry | Electronic payment device using balanced binary tree and the method of the same |
| AU6097000A (en) * | 1999-07-15 | 2001-02-05 | Frank W Sudia | Certificate revocation notification systems |
| US6769068B1 (en) * | 1999-09-02 | 2004-07-27 | International Business Machines Corporation | Dynamic credential refresh in a distributed system |
| US6816900B1 (en) * | 2000-01-04 | 2004-11-09 | Microsoft Corporation | Updating trusted root certificates on a client computer |
| US7269726B1 (en) | 2000-01-14 | 2007-09-11 | Hewlett-Packard Development Company, L.P. | Lightweight public key infrastructure employing unsigned certificates |
| US7340600B1 (en) * | 2000-01-14 | 2008-03-04 | Hewlett-Packard Development Company, L.P. | Authorization infrastructure based on public key cryptography |
| JP2001308841A (ja) * | 2000-04-21 | 2001-11-02 | Sony Corp | 送信装置および送信方法、受信装置および受信方法、ならびに、送受信システムおよび送受信方法 |
| KR100731491B1 (ko) * | 2000-10-12 | 2007-06-21 | 주식회사 케이티 | 인증서 폐지목록 분산 관리 방법 |
| US20020053028A1 (en) * | 2000-10-24 | 2002-05-02 | Davis Steven B. | Process and apparatus for improving the security of digital signatures and public key infrastructures for real-world applications |
| US20020147904A1 (en) * | 2001-04-10 | 2002-10-10 | Moritaka Nakamura | Electronic notarization on net system |
| US7043024B1 (en) * | 2001-04-18 | 2006-05-09 | Mcafee, Inc. | System and method for key distribution in a hierarchical tree |
| US7590247B1 (en) * | 2001-04-18 | 2009-09-15 | Mcafee, Inc. | System and method for reusable efficient key distribution |
| US20030061481A1 (en) * | 2001-09-26 | 2003-03-27 | David Levine | Secure broadcast system and method |
| US7194004B1 (en) * | 2002-01-28 | 2007-03-20 | 3Com Corporation | Method for managing network access |
| US7240194B2 (en) | 2002-03-22 | 2007-07-03 | Microsoft Corporation | Systems and methods for distributing trusted certification authorities |
| AU2003226458A1 (en) * | 2002-05-09 | 2003-11-11 | Matsushita Electric Industrial Co., Ltd. | Public key certificate revocation list generation apparatus, revocation judgement apparatus, and authentication system |
| RU2005100851A (ru) * | 2002-06-17 | 2005-06-10 | Конинклейке Филипс Электроникс Н.В. (Nl) | Способ аутентификации между устройствами |
| US20030236976A1 (en) * | 2002-06-19 | 2003-12-25 | Microsoft Corporation | Efficient membership revocation by number |
| US7451310B2 (en) * | 2002-12-02 | 2008-11-11 | International Business Machines Corporation | Parallelizable authentication tree for random access storage |
| US7543140B2 (en) * | 2003-02-26 | 2009-06-02 | Microsoft Corporation | Revocation of a certificate and exclusion of other principals in a digital rights management (DRM) system based on a revocation list from a delegated revocation authority |
| JP4646509B2 (ja) * | 2003-10-27 | 2011-03-09 | 株式会社東芝 | 情報保管サーバおよび情報保管プログラム |
| JP2007514361A (ja) * | 2003-12-15 | 2007-05-31 | コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ | セキュリティ関連のアプリケーションのための使用認証装置 |
| AU2005207062A1 (en) * | 2004-01-23 | 2005-08-04 | Mastercard International Incorporated | System and method for generating collison-free identifiers for financial transaction cards |
| EP1716663A1 (en) * | 2004-02-10 | 2006-11-02 | Cryptico A/S | Methods for generating identification values for identifying electronic messages |
| CN100349407C (zh) * | 2004-02-19 | 2007-11-14 | 华夏银行 | 电子保管箱及其管理方法 |
| US20060036627A1 (en) * | 2004-08-06 | 2006-02-16 | Roger Deran | Method and apparatus for a restartable hash in a trie |
| US8954751B2 (en) * | 2004-10-08 | 2015-02-10 | International Business Machines Corporation | Secure memory control parameters in table look aside buffer data fields and support memory array |
| US7657756B2 (en) * | 2004-10-08 | 2010-02-02 | International Business Machines Corporaiton | Secure memory caching structures for data, integrity and version values |
| US7266692B2 (en) | 2004-12-17 | 2007-09-04 | Ntt Docomo, Inc. | Use of modular roots to perform authentication including, but not limited to, authentication of validity of digital certificates |
| GB0428377D0 (en) * | 2004-12-24 | 2005-02-02 | British Telecomm | Radio frequency identification tag security |
| EP1836652B1 (en) | 2005-01-12 | 2017-06-21 | BRITISH TELECOMMUNICATIONS public limited company | Radio frequency identification transponder security |
| CN101103365B (zh) | 2005-01-12 | 2010-04-21 | 英国电讯有限公司 | 操作射频识别系统的方法及用于该方法的装置和系统 |
| KR100670010B1 (ko) * | 2005-02-03 | 2007-01-19 | 삼성전자주식회사 | 하이브리드 브로드캐스트 암호화 방법 |
| WO2007004107A2 (en) * | 2005-06-30 | 2007-01-11 | Koninklijke Philips Electronics N.V. | Method and apparatus for managing digital right licenses |
| US7434253B2 (en) * | 2005-07-14 | 2008-10-07 | Microsoft Corporation | User mapping information extension for protocols |
| US8874477B2 (en) | 2005-10-04 | 2014-10-28 | Steven Mark Hoffberg | Multifactorial optimization system and method |
| US7853018B2 (en) * | 2005-11-10 | 2010-12-14 | Atallah Mikhail J | Method and apparatus for hiding a private key |
| US7716180B2 (en) | 2005-12-29 | 2010-05-11 | Amazon Technologies, Inc. | Distributed storage system with web services client interface |
| US7702640B1 (en) * | 2005-12-29 | 2010-04-20 | Amazon Technologies, Inc. | Stratified unbalanced trees for indexing of data items within a computer system |
| US8589574B1 (en) | 2005-12-29 | 2013-11-19 | Amazon Technologies, Inc. | Dynamic application instance discovery and state management within a distributed system |
| US7836313B2 (en) * | 2006-03-21 | 2010-11-16 | Oracle America, Inc. | Method and apparatus for constructing a storage system from which digital objects can be securely deleted from durable media |
| US20080201260A1 (en) * | 2007-02-16 | 2008-08-21 | Toby Unwin | Internet micro payments system |
| IL187037A0 (en) * | 2007-10-30 | 2008-02-09 | Sandisk Il Ltd | Fast update for hierarchical integrity schemes |
| IL187041A0 (en) * | 2007-10-30 | 2008-02-09 | Sandisk Il Ltd | Optimized hierarchical integrity protection for stored data |
| WO2010024931A1 (en) | 2008-08-29 | 2010-03-04 | Brown University | Cryptographic accumulators for authenticated hash tables |
| US8676855B2 (en) * | 2009-05-01 | 2014-03-18 | Brother Kogyo Kabushiki Kaisha | Distributed storage system, management apparatus, node apparatus, recording medium on which node program is recorded, page information acquisition method, recording medium on which page information sending program is recorded, and page information sending method |
| JP2010267028A (ja) * | 2009-05-13 | 2010-11-25 | Brother Ind Ltd | 管理装置、管理処理プログラム、ノード装置、ノード処理プログラム、及び有効期限切れレコード判定方法 |
| US9477947B2 (en) | 2009-08-24 | 2016-10-25 | International Business Machines Corporation | Retrospective changing of previously sent messages |
| US8254580B2 (en) * | 2009-09-30 | 2012-08-28 | Telefonaktiebolaget L M Ericsson (Publ) | Key distribution in a hierarchy of nodes |
| US9584322B2 (en) * | 2010-03-08 | 2017-02-28 | Intel Corporation | System and method for hypervisor-based remediation and provisioning of a computer |
| US8572699B2 (en) * | 2010-11-18 | 2013-10-29 | Microsoft Corporation | Hardware-based credential distribution |
| US8538920B2 (en) * | 2011-08-08 | 2013-09-17 | Hewlett-Packard Development Company, L.P. | System and method for storage service |
| CN102546108A (zh) * | 2011-12-28 | 2012-07-04 | 深圳市新为软件有限公司 | 一种通过树形结构对网络资源进行传输的方法和装置 |
| US9397982B2 (en) * | 2012-06-28 | 2016-07-19 | Ologn Technologies Ag | Secure key storage systems, methods and apparatuses |
| CN102930185B (zh) * | 2012-11-28 | 2015-07-29 | 中国人民解放军国防科学技术大学 | 运行时程序安全关键数据的完整性验证方法及装置 |
| SE537697C2 (sv) | 2013-08-08 | 2015-09-29 | Enigio Time Ab | Förfarande för att skapa signaler för tidsstämpling av dokument och förfarande för tidsstämpling av dokument |
| CN103941719B (zh) * | 2014-03-21 | 2017-03-15 | 上海富欣智能交通控制有限公司 | 安全关键数据的反向验证方法 |
| US10333696B2 (en) | 2015-01-12 | 2019-06-25 | X-Prime, Inc. | Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency |
| CN111400752A (zh) * | 2020-03-12 | 2020-07-10 | 杭州城市大数据运营有限公司 | 一种基于区块链的数据查询方法、系统及电子设备 |
| US20240248624A1 (en) * | 2023-01-24 | 2024-07-25 | VMware LLC | Tiered memory data structures and algorithms for dynamic searching via treaps |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4309569A (en) * | 1979-09-05 | 1982-01-05 | The Board Of Trustees Of The Leland Stanford Junior University | Method of providing digital signatures |
| US5231666A (en) * | 1992-04-20 | 1993-07-27 | International Business Machines Corporation | Cryptographic method for updating financial records |
| US5826254A (en) * | 1995-04-18 | 1998-10-20 | Digital Equipment Corporation | System for selectively browsing a large, distributed directory tree using authentication links |
| US5903651A (en) * | 1996-05-14 | 1999-05-11 | Valicert, Inc. | Apparatus and method for demonstrating and confirming the status of a digital certificates and other data |
-
1998
- 1998-01-22 US US09/010,571 patent/US6226743B1/en not_active Expired - Lifetime
-
1999
- 1999-01-14 IL IL12804099A patent/IL128040A/en not_active IP Right Cessation
- 1999-01-21 EP EP99400130A patent/EP0932109A3/en not_active Withdrawn
- 1999-01-22 JP JP11053084A patent/JPH11289329A/ja active Pending
Cited By (21)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001015381A1 (en) * | 1999-08-21 | 2001-03-01 | Danal Co., Ltd. | User authentication system using second connection path |
| US7512786B2 (en) | 1999-12-10 | 2009-03-31 | Microsoft Corporation | Client-side boot domains and boot rules |
| JP2003533940A (ja) * | 2000-05-16 | 2003-11-11 | シュアティー ドット コム | デジタルレコードを自己認証するための方法及び装置 |
| US7409551B2 (en) | 2000-08-30 | 2008-08-05 | Hitachi, Ltd. | Certificate validity authentication method and apparatus |
| JP2002072876A (ja) * | 2000-08-30 | 2002-03-12 | Hitachi Ltd | 証明書の有効性確認方法および装置 |
| US7080251B2 (en) | 2000-08-30 | 2006-07-18 | Hitachi, Ltd. | Certificate validity authentication method and apparatus |
| JP2008263645A (ja) * | 2001-03-29 | 2008-10-30 | Matsushita Electric Ind Co Ltd | 暗号化を施すことによりデータを保護するデータ保護システム |
| JP2007505555A (ja) * | 2003-09-10 | 2007-03-08 | 株式会社エヌ・ティ・ティ・ドコモ | 安全で小額の信用課金をサービスプロバイダが認証可能に測定するための方法及び装置 |
| US8321664B2 (en) | 2003-09-19 | 2012-11-27 | Ntt Docomo, Inc. | Method and apparatus for efficient certificate revocation |
| JP2007506365A (ja) * | 2003-09-19 | 2007-03-15 | 株式会社エヌ・ティ・ティ・ドコモ | 証明書を効率的に無効にする方法及び装置 |
| KR100625154B1 (ko) * | 2003-10-10 | 2006-09-20 | 가부시키가이샤 히타치세이사쿠쇼 | 공개 키 증명서 검증의 고속화 방법, 및 장치 |
| JP2007515837A (ja) * | 2003-11-21 | 2007-06-14 | エリコス ピッツォス | データ管理処理およびデータ配送処理において完全性および信頼を提供する方法およびシステム |
| JP2007515890A (ja) * | 2003-12-22 | 2007-06-14 | リナックスプローブ株式会社 | デジタル証明書を生成するためのシステムおよび方法 |
| WO2005117336A1 (ja) * | 2004-05-28 | 2005-12-08 | Matsushita Electric Industrial Co., Ltd. | 親子カード認証システム |
| US8006086B2 (en) | 2004-08-31 | 2011-08-23 | Ntt Docomo, Inc. | Revocation of cryptographic digital certificates |
| US8024562B2 (en) | 2004-08-31 | 2011-09-20 | Ntt Docomo, Inc. | Revocation of cryptographic digital certificates |
| JP4794560B2 (ja) * | 2004-08-31 | 2011-10-19 | 株式会社エヌ・ティ・ティ・ドコモ | 暗号デジタル証明書の失効 |
| US8156327B2 (en) | 2004-08-31 | 2012-04-10 | Ntt Docomo, Inc. | Revocation of cryptographic digital certificates |
| US8209531B2 (en) | 2004-08-31 | 2012-06-26 | Ntt Docomo, Inc. | Revocation of cryptographic digital certificates |
| JP2008524931A (ja) * | 2004-12-17 | 2008-07-10 | 株式会社エヌ・ティ・ティ・ドコモ | 証明書の有効性／無効性証明用暗号化証明データを用いた複数証明書失効 |
| JP2006287455A (ja) * | 2005-03-31 | 2006-10-19 | Nec Corp | 証明書検証装置及び方法並びに証明書検証サーバ |
Also Published As
| Publication number | Publication date |
|---|---|
| IL128040A (en) | 2004-01-04 |
| IL128040A0 (en) | 1999-11-30 |
| EP0932109A3 (en) | 2003-06-18 |
| EP0932109A2 (en) | 1999-07-28 |
| US6226743B1 (en) | 2001-05-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH11289329A (ja) | 認証形サ―チ・ツリ― | |
| JP4796971B2 (ja) | Ｏｃｓｐ及び分散型ｏｃｓｐのための効率的に署名可能なリアルタイム・クレデンシャル | |
| CN109829326B (zh) | 基于区块链的跨域认证与公平审计去重云存储系统 | |
| US9654298B2 (en) | Signature # efficient real time credentials for OCSP and distributed OCSP | |
| US6763459B1 (en) | Lightweight public key infrastructure employing disposable certificates | |
| US6553493B1 (en) | Secure mapping and aliasing of private keys used in public key cryptography | |
| US5774552A (en) | Method and apparatus for retrieving X.509 certificates from an X.500 directory | |
| US8744077B2 (en) | Cryptographic encoding and decoding of secret data | |
| US5606617A (en) | Secret-key certificates | |
| US20100122082A1 (en) | User identity validation system and method | |
| GB2594312A (en) | Digital Signatures | |
| CN117240452B (zh) | 一种基于区块链的高原数据安全共享方法 | |
| CN109687965A (zh) | 一种保护网络中用户身份信息的实名认证方法 | |
| GB2600684A (en) | Identifying denial-of-service attacks | |
| EP2384562B1 (en) | Management of cryptographic credentials in data processing systems | |
| CN111080299B (zh) | 一种交易信息的防抵赖方法及客户端、服务器 | |
| Harn et al. | A protocol for establishing secure communication channels in a large network | |
| Nissim et al. | Certificate Revocation and Certificate Update. | |
| Koga et al. | A distributed online certificate status protocol with a single public key | |
| CN115720137B (zh) | 一种信息管理的系统、方法以及装置 | |
| CN1985460B (zh) | 用于ocsp和分布式ocsp的通信有效实时凭证 | |
| US20020152383A1 (en) | Method for measuring the latency of certificate providing computer systems | |
| CN113449032B (zh) | 一种数据上链可验证的区块链离链数据交互系统及方法 | |
| EP4552280A1 (en) | A system and method for the consistency and correctness of storage and database management operations among data entities and their hashed key values | |
| CN120639300A (zh) | 一种应用于大型企业数字资产监督管理方法 |