JPH09298536A - ディジタル署名方式およびそれを用いた情報通信システム - Google Patents

Abstract

(57)【要約】 【課題】 公開鍵暗号を応用した情報通信システムに
は、署名者の公開鍵を必要とし、零知識証明を用いるた
め、署名の確認には署名者と確認者との間で複数回の送
受信を行わなければならないものがある。 【解決手段】 指定者は、署名者を指定するために、第
一のディジタル署名方式により第一のディジタル署名を
生成する。指定者に指定された署名者は、第一のディジ
タル署名に基づき、第二のディジタル署名方式により第
二のディジタル署名を生成する。確認者は、第一および
第二のディジタル署名に基づき、第二のディジタル署名
が指定者により指定された署名者により生成されたもの
か否かを確認する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はディジタル署名方式
およびそれを用いた情報通信システムに関する。

【０００２】

【従来の技術】コンピュータおよび通信ネットワークの
発展と広範な普及に伴い、社会的活動のような機能をネ
ットワーク上においても実現できるようになった。しか
し、誰が、何時、何処で、何を行ったか、も容易に把握
することができ、それに対抗するため、匿名で処理を行
うことによりネットワーク上で多様な機能を実現し、か
つプライバシも保護する方法が考えられている。

【０００３】後述する公開鍵暗号を用いれば、送信者は
通信内容を意図する受信者だけに送り、しかも受信者は
その通信の送信者が誰であるかを確実に確認することが
可能である。後述する零知識証明を利用すれば、ユーザ
がある秘密情報を保持していることを、その秘密を明ら
かにすることなく他者に証明できる。これらを応用した
情報通信システムが、Masahiro MAMBO, Eiji OKAMOTO,
"A method to publicly specify a signer with hidin
g identity, The 18th Symposium on Information Theo
ry and Its Applications" (October 1995)で提案され
ている。これを、以下では「MOシステム」と呼ぶことに
する。

【０００４】以下、最初に公開鍵暗号を、次に零知識証
明を、それからMOシステムを詳細に説明する。

【０００５】［公開鍵暗号］公開鍵暗号とは、暗号鍵と
復号鍵とが異なり、暗号鍵を公開し、復号鍵を秘密にす
る暗号方式であり、以下のような特徴をもつ。 (1)暗号鍵と復号鍵とが異なり、暗号鍵を公開すること
ができるため、暗号鍵を秘密に配送する必要がなく、鍵
の配送が容易である。 (2)各利用者は、暗号鍵を公開し、各自、復号鍵だけを
秘密にし記憶しておけばよい。 (3)送られてきた通信文の送信者が偽者でないこと、お
よび、その通信文が改竄されていないことを、受信者が
確認するための認証機能（ディジタル署名）を実現でき
る。

【０００６】通信文（平文）Mに対して、公開の暗号鍵k
pを用いた暗号化操作をE(kp, M)とし、秘密の復号鍵ks
を用いた復号操作をD(ks, M)とすると、公開鍵暗号アル
ゴリズムは、まず次の二つの条件を満たす。 (1)暗号鍵kpが与えられたときE(kp, M)の計算は容易で
あり、復号鍵ksが与えられたときD(ks, M)の計算は容易
である。 (2)もし復号鍵ksを知らないなら、暗号鍵kp、暗号化操
作Eの計算手順、暗号であるC=E(kp, M)を知ったとして
も、平文Mを決定することは、その計算量から困難であ
る。

【０００７】さらに、上記(1)(2)に加えて、次の条件
(3)が成立することにより、秘密通信が実現できる。 (3)すべての平文Mに対し、E(kp, M)を定義することがで
き、次式が成立する。 D(ks, E(kp, M)) = M

【０００８】つまり、暗号鍵kpは公開されているため、
誰もがE(kp, M)を計算することができるが、D(ks, E(k
p, M))を計算して平文Mを得ることができるのは、秘密
の復号鍵ksを記憶している本人だけである。

【０００９】一方、上記(1)(2)に加えて、次の条件(4)
が成立することにより、認証通信（ディジタル署名）が
実現できる。 (4)すべての平文Mに対し、D(ks, M)を定義することがで
き、次式が成立する。 E(kp, D(ks, M)) = M

【００１０】つまり、D(ks, M)を計算できるのは秘密の
復号鍵ksを記憶している本人だけであり、他人が偽の鍵
ks'を用いてD(ks', M)を計算し、秘密の復号鍵ksを記憶
する本人になりすまそうとしても、E(kp, D(ks', M))≠
Mであり、受信者は受取った情報が不正なものであるこ
とを知ることができる。

【００１１】同様に、D(ks, M)が改竄されても、E(kp,
D(ks, M)')≠Mであり、受信者は受取った情報が不正な
ものであることを知ることができる。このD(ks, M)をM
に対する「ディジタル署名」と呼ぶ。

【００１２】代表的な公開鍵暗号方式を以下に挙げる。
秘密通信と認証通信ができる方式として、RSA暗号(R.
L. Rivest, A. Shamir and L. Adleman: "A method of
obtaining digital signatures and public key crypto
systems", Comm. of ACM, 1978)、R暗号(M. Rabin: "Di
gitalized signatures and public-key cryptosystem
s", MIT/LCS/TR-212, Technical Report MIT, 1979)、W
暗号(H. C. Williams: "Amodification of the RSA pub
lic-key encryption procedure", IEEE Trans. Inf. Th
eory, IT-26, 6, 1980)などがある。

【００１３】また、秘密通信だけができる方式として、
CR暗号(B. Chor and R. L. Rivest:"A knapsack type p
ublic key cryptosystem based on arithmetric in fin
itefield", Proc. Crypto 84)、M暗号(R. J. McEliece:
"A public-key cryptosystem based on algebraic cod
ing theory", DSN Progress Rep., Jet PropulsionLa
b., 1978)、E暗号(T. E. ElGamal: "A public key cryp
tosystem and a signature scheme based on discretre
logarithms", IEEE Transaction on Information Theo
ry, Vol. IT-31, No.4, pp.469-472, 1985)などがあ
る。

【００１４】認証通信だけができる方式として、S暗号
(A. Shamir: "A fast signature scheme", Report MIT/
LCS/TM-107, MIT laboratory for computer science, C
ambridge, Mass., 1978)、L暗号(K. Lieberherr: "Unif
orm complexity and digitalsignature", Lecture Note
s in Computer Science 115 Automata, Language andPr
ogramming, Eigtht Colloquium Acre, Israel, 1981)、
GMY暗号(S. Goldwasser, S. Micali and A. Yao: "Stro
ng signature schemes", ACM Symp. on Theory of Comp
uting, 1983)、GMR暗号(S. Goldwasser, S. Micali and
R. L. Rivest: "A 'paradoxical' solution to the si
gnature problem", ACM Symp. on Foundation of Compu
ter Science, 1984)、E暗号(T. E. ElGamal: "A public
key cryptosystem and a signature scheme based on
discretre logarithms", IEEE Transaction on Informa
tion Theory, Vol. IT-31, No.4, pp.469-472, 1985)、
OS暗号(岡本, 白石: "多項式演算によるディジタル署名
方式", 信学論(D), J68−D, 5, 1985; T. Okamoto and
A. Shiraisi: "A fast signature scheme based on qua
dratic inequalities", IEEE Symp. on Theory of Comp
uting, 1984)、

【００１５】Fiat-Shamir暗号(A. Fiat, A. Shamir: "H
ow to prove yourself: practicalsolutions of identi
fication and signature problems", Proc. of CRYPTO'
86,1987)、Schnorr暗号(C. P. Schnorr: "Efficient si
gnature generation by smart cards", Journal of Cry
ptology, vol.4, pp.161-174, 1991)などがある。

【００１６】具体的な一例として、離散対数を求めるこ
との困難性に安全性の根拠をおき、偽造に対する安全性
が極めて高いとされ、署名のサイズが小さい署名方式で
あるSchnorr暗号を説明する。なお、以下の説明におい
て、a^bはaのb乗を表す。

【００１７】例えば、大きな素数pと、q|p-1（qはp-1を
割り切る）なる大きな素数qを選ぶとき、{1, 2, …, q-
1}の中の一つをαとすると、α^x≡u (mod p)を満たすx
（=DL(u,α)と記す）は、ガロア体GF(p)上における離散
対数であり、p, q, α, uを与えられた上でxを効率的に
求めることは難しいとされている。

【００１８】Schnorr暗号では、鍵認証センタ(KAC: Key
Authentication Center)がシステムの初期化を行う。
署名者が鍵生成と署名生成を行い、認証者が署名を受取
り確認する。システムの中では、一方向性ハッシュ関数
を用いる。一方向性ハッシュ関数とは、衝突を起こしに
くい圧縮関数である。つまり、任意の長さの値を入力し
て固定の長さの値を出力し、同じ値を出力する異なる入
力を見つけることが困難である。Zは整数の集合で、Zq
は0以上q未満の整数の集合である。

【００１９】●システム初期化 (1)鍵認証センタ(KAC)は、大きな素数p(≧2^512)とq(≧
2^140)を選び公開する。ただし、q|p-1である。 (2)KACは、α∈Zpかつα^q = 1 (mod p)なるα(≠1)を
選び公開する。 (3)KACは、h: Zq×Z → {0, …, 2^t - 1}を選び公開す
る。ここで、tを「セキュリティパラメータ」と呼ぶ。 (4)KACは、自分の署名用の公開鍵と秘密鍵を選び、公開
鍵を公開する（例えば、Fiat-Shamir暗号など）。

【００２０】●鍵生成 システムに加入するユーザ（署名者）は、0 < s≦qなる
任意の整数sを選び、v= α^{-s} mod pを計算する。

【００２１】署名者の秘密鍵はsであり、公開鍵はvであ
る。認証者は、署名者の公開鍵の正当性を、例えば、署
名者の公開鍵に対してKACが（例えば、Fiat-Shamir暗号
で）署名を付ける、あるいは、署名者の公開鍵が公開デ
ータベースに登録される、などによって確認することが
できる。

【００２２】●署名生成（メッセージmに対する署名） (1)署名者は、乱数r∈{1, …, q}を選び、x = α^r (mo
d p)を計算する。 (2)署名者は、e = h(x, m)を求める。 (3)署名者は、y = r + s・e (mod q)を計算する。(e, y)
が、メッセージmに対する署名である。

【００２３】●署名検証 メッセージmと署名(e, y)を受取った認証者は、前述の
方法でvの正当性を確認し、次式を確認する。 x' = α^y・v^e (mod p) e = h(x', m)

【００２４】［零知識証明］零知識証明とは、ある命題
を証明者が検証者に証明することであり、以下の三条件
を満たす。 (1)完全性: 証明が正しければ、検証者は1または1に限
りなく近い確率（圧倒的確率）で受理する。 (2)健全性: 証明が誤っていれば、検証者は1または1に
限りなく近い確率（圧倒的確率）で棄却する。 (3)零知識性: 証明が正しければ、検証者がどのように
振る舞っても、証明の正しさ以外の情報は一切洩れな
い。

【００２５】ある秘密（数値）を知っている証明者が、
その秘密に関する情報を一切漏らさずに、その秘密を知
っていることを検証者に証明する零知識証明の方法が幾
つか提案されていて、身元証明やディジタル署名などに
応用され、情報セキュリティの分野における重要な基盤
技術になっている。

【００２６】具体的な一例として、J. Boyar, D. Chau
m, I. Damard, T. Pedersen, "Convertible undeniable
signatures", Proc. of CRYPTO'90において提案され
た、z =DL(u, α)を知っている証明者が、zを明らかに
することなくDL(v, w) = DL(u,α)を証明する零知識証
明プロトコルを説明する。ただし、DL(u, α)は適当な
群における離散対数を意味する（例えば、前述のGF(p)
の場合、α^{DL(u, α)} ≡(mod p)）。

【００２７】●DL(v, w) = DL(u, α)を証明する零知識
証明プロトコル 以下では、証明者をP(Prover)、検証者をV(Verifier)と
記す。PもVもv, w, u,αを知っている。 (1)検証者Vは、乱数aとbを選び(a, b∈Zq)、ch = w^a・
α^bを求め、chを証明者Pに送る。 (2)証明者Pは、乱数tを選び(t∈Zq)、h1 = ch・α^tとh2
= h1^zを求め、(h1, h2)を検証者Vに送る。 (3)検証者Vは、(a, b)を証明者Pに送る。 (4)証明者Pは、ch = w^a・α^bを確認し、tを検証者Vに
送る。 (5)検証者Vは、h1 = w^a・α^{b+t}とh2 = v^a・u^{b+t}
を確認する。

【００２８】［MOシステム］図1は公開鍵暗号と零知識
証明を応用したMOシステムを説明するための図で、MOシ
ステムは、指定者と複数のユーザ、ユーザの中から選ば
れる署名者、署名者の作成する署名を確認する確認者か
らなる。なお、以下の説明において、a_bはaに下付き添
字bが付いた状態を表す。

【００２９】図1において、「公開値(Public Values)」
は後述するシステム共通のデータ、「公開データベース
(Public Database)」は公開されたデータベース、矢印
はデータの取得，送信，受信を示し、括弧で囲まれた番
号は処理の手順を示す。また、「署名者(Specified Sig
ner)」は、「指定者(Specifier)」によりユーザの中か
ら選ばれた署名者を表し、「確認者(Verifier)」は署名
を確認する者を表す。

【００３０】Step 0（準備）: システム共通のデータと
して、素数pとq(q|p-1)、Zp*の元であり位数qのα（α^
q≡1 (mod p)、Zp*はZqかつpと互いに素である整数の集
合）、一方向性ハッシュ関数h: Zq×Z → {0, …, 2^t
- 1}を用意する。これらは、システムに参加しているす
べてのユーザがアクセスでき、かつ不当な改竄などが起
こらないように適切に管理されている公開のデータベー
スに登録されているものとする。

【００３１】指定者iは公開鍵v_iと秘密鍵s_i(v_i = α
^{-s_i} mod p)を生成し、公開鍵を公開のデータベース
に登録する。署名者になり得るユーザjは、公開鍵v_jと
秘密鍵v_j(v_j = α^{-s_j} mod p)を生成し、公開鍵を
公開のデータベースに登録する。ユーザは複数存在し、
署名者も複数存在し得る。

【００３２】Step 1（ユーザ指定と公開）: 指定者i
は、複数の中からあるユーザ、すなわち署名者jを選び
（図1に示す矢印101）、署名者jの公開鍵v_jを乱数rを
用いて変換したz_jを計算し、z_jに対する署名（Schnor
r暗号による署名）を求め（図1に示す手順(1)）、公開
データベースに登録する（図1に示す矢印102）。

【００３３】具体的には、指定者iは（秘密の）乱数r(r
∈ Zq*）を選び、次式により各パラメータを求め、署
名((y_j, e_j, x)，z_j)を公開データベースに登録す
る。なお、r ∈ Zq*は、Zq*からランダムにrを選ぶこと
を表している。 x = α^r mod p z_j = {v_j}^r mod p e_j = h(x, z_j) y_j = r + e_j・s_i mod q

【００３４】Step 2（情報のピックアップ）: ユーザ
は、公開データベースに登録された内容から、指定者i
が登録した署名((y_j, e_j, x)，z_j)が、自分に対する
ものであるか否かを次のように確認する（図1に示す手
順(2)、矢印103）。つまり、各ユーザkは、次式を確認
する。 e_j = h(α^{y_j}・{v_i}^{e_j} mod p, zj) …(1) z_j = x^{-s_k} mod q …(2)

【００３５】なお、式(2)の法の値qは誤りで、正しく
は、(3)式のようになると思われるが、敢えて、Masahir
o MAMBO, Eiji OKAMOTO, "A method to publicly speci
fy asigner with hiding identity", The 18th Symposi
um on Information Theory and Its Applications" (Oc
tober 1995)の原文のとおりに記載した。 z_j = x^{-s_k} mod p …(3)

【００３６】すべてのユーザは、式(1)が成り立つこと
を確認できる。それに加えて、署名者jは式(2)あるいは
(3)も成立することを確認でき、自分が指定者iに選ばれ
たことが分かる。

【００３７】一方、他の署名者λ（s_λ≠s_jとする）
は、式(2)あるいは(3)が自分の秘密鍵s_λでは成り立た
ないことがわかるが、式(2)あるいは(3)が、ほかのどの
署名者に対して成立するものかは分からない（ほかの署
名者の秘密鍵、例えばs_jを知らない）ので、ほかの誰
が選ばれたのかは分からない。

【００３８】Step 3（署名生成）: 署名者jは署名した
いメッセージmに対し、次の署名方式で署名を生成す
る。署名者jは、乱数r_jを選び(r_j ∈ Zq*)、次式を計
算する。 x1 = α^{r_j} mod p x2 = {v_j}^{r_j} mod p

【００３９】そして、次式を求める。 e' = h(x2, m) y = -(r_j - e')s_j mod q

【００４０】そして、((y_j, e_j, x), z_j, (y, e'，x
1), m)を署名として、必要な相手に送る（図1に示す手
順(3)、矢印104）。

【００４１】Step 4（署名確認）: 上記の署名を受信し
た確認者は最初に、上記の式(1)および次式を確認す
る。 e_j = h(z_j, α^{y_j}・{v_i}^{e_j} mod p)

【００４２】次に、次式を確認する（図1に示す手順
(4)）。 e' = h(m, x2) x2 = α^y・{v_j}^{e'} mod p …(4)

【００４３】上記が確認できたならば、署名者jは受信
者（確認者）との間で、DL(z_j, x)= DL(x2, x1)(=-s_
j)を証明する零知識証明を実行する（図1に示す手順
(5)、矢印105）。零知識証明が受理できるならば、受信
者はmに対する署名は指定者iに選ばれた署名者jによっ
て生成された署名であると納得する。

【００４４】上記MOシステムでは、ある指定者iがある
署名者jを選び、選ばれた署名者jは匿名で署名を生成で
き、その署名を受取った者は、指定者iによって選ばれ
た署名者jがその署名を生成したことは確認できるが、
その署名者jが誰であるかを特定することはできない、
と主張されている。また、以上の性質から、MOシステム
は福祉サービスやペイTVの視聴率調査に応用できると言
われている。

【００４５】つまり、福祉サービスや視聴率調査が確か
に行われていることを誰でも確認でき、かつ、受益者や
調査対象者は、そのサービスを受けるために必要な文書
（生活状態の報告）や調査の回答に対して、匿名のまま
で署名を付けて提出することができる。

【００４６】

【発明が解決しようとする課題】しかし、上述した技術
においては、次のような問題点がある。つまり、MOシス
テムにおいては、指定された署名者jが匿名で生成する
署名が正当であることを確認するにもかかわらず、その
際、署名者jの公開鍵を必要とする（式(4)においてv_j
が使われる）という性質がある。

【００４７】さらに、確認の際は、前述した零知識証明
を用いるため、署名者jと確認者との間で複数回の送受
信を行わなければならず、そのための計算も行う必要が
ある。

【００４８】また、同一相手と何度通信を行っても、匿
名性が保たれる通信ネットワークを前提としているの
で、一度だけの通信において匿名性を保つことができる
通信ネットワークと比較して、実用化するためのコスト
が高くなる。

【００４９】本発明は、上述の問題を解決するためのも
のであり、署名者の匿名性を保つことができるディジタ
ル署名方式を提供することを目的とする。

【００５０】また、通信回数を減らし、複数回の通信に
伴う計算も行わずに済ませることができるディジタル署
名方式を用いた情報通信システムを提供することを他の
目的とする。

【００５１】また、少なくとも一回の通信を行ったとき
に匿名性を保つことができる通信ネットワークを用いる
ことができるディジタル署名方式を用いた情報通信シス
テムを提供することを他の目的とする。

【００５２】

【課題を解決するための手段】本発明は、前記の目的を
達成する一手段として、以下の構成を備える。

【００５３】本発明にかかるディジタル署名方式は、各
ユーザが共通に使用する公開パラメータと、各ユーザに
固有の秘密情報とから、各ユーザに固有の公開情報を生
成する公開情報生成ステップと、所定のディジタル情報
に、前記秘密情報および前記公開パラメータを用いた変
換を施すことにより、前記ディジタル情報に対応する署
名情報を生成する署名生成ステップと、前記ディジタル
情報と前記署名情報との対応関係を、前記公開パラメー
タおよび前記公開情報を用いて判別する判別ステップ
と、前記秘密情報を変換せずに前記公開パラメータおよ
び前記公開情報を変換して、前記署名情報を生成するこ
とができる新たな公開パラメータおよび公開情報にする
変換ステップとを有することを特徴とする。

【００５４】また、複数ユーザ間で共通に使われる底の
値に対して各ユーザの秘密鍵を指数値として指数計算を
行った結果を各ユーザの公開鍵とするディジタル署名方
式であって、前記底に対して乱数を指数値として指数計
算を行った結果を新しい底とする底生成ステップと、所
定のユーザの公開鍵に対して前記乱数を指数値として指
数計算を行った結果を新しい公開鍵とする公開鍵生成ス
テップと、前記所定のユーザが、自身の秘密鍵を用い
て、任意の平文に対してディジタル署名を生成する署名
生成ステップと、前記底生成ステップおよび前記公開鍵
生成ステップにより生成された底と公開鍵とを用いて、
前記署名生成ステップで生成されたディジタル署名の正
当性を確認する確認ステップとを有することを特徴とす
る。

【００５５】本発明にかかる情報通信システムは、ディ
ジタル署名を生成する生成手段を指定する指定手段と、
少なくとも一つのディジタル署名方式を用いて、対象の
ディジタル署名が前記指定手段により指定された生成手
段により生成されたものか否かを確認する確認手段とを
備えた情報通信システムであって、前記ディジタル署名
方式の一つは、複数ユーザ間で共通に使われる底の値に
対して各ユーザの秘密鍵を指数値として指数計算を行っ
た結果を各ユーザの公開鍵とするディジタル署名方式で
あって、前記底に対して乱数を指数値として指数計算を
行った結果を新しい底とする底生成ステップと、所定の
ユーザの公開鍵に対して前記乱数を指数値として指数計
算を行った結果を新しい公開鍵とする公開鍵生成ステッ
プと、前記所定のユーザが、自身の秘密鍵を用いて、任
意の平文に対してディジタル署名を生成する署名生成ス
テップと、前記底生成ステップおよび前記公開鍵生成ス
テップにより生成された底と公開鍵とを用いて、前記署
名生成ステップで生成されたディジタル署名の正当性を
確認する確認ステップとを有するディジタル署名方式で
あることを特徴とする。

【００５６】また、離散対数を求めることの困難性に安
全性の根拠をおく第一のディジタル署名方式を用いて、
ディジタル署名を生成する署名生成手段を指定する指定
手段と、請求項5から請求項7の何れかに記載された第二
のディジタル署名方式により新しい底および新しい公開
鍵を得る取得手段と、前記取得手段により得られた新し
い底の値を用いて、前記取得手段により得られた新しい
公開鍵に対する第一のディジタル署名を、前記第一のデ
ィジタル署名方式により生成する第一の生成手段とを備
え、前記第一の生成手段により得られたディジタル署名
は、前記取得手段により得られた新しい公開鍵に対応す
る秘密鍵をもつ署名生成手段が指定されたことを示す証
拠であることを特徴とする。

【００５７】また、署名を生成する手段を指定するため
に、第一のディジタル署名方式により第一のディジタル
署名を生成する指定手段と、前記指定手段により生成さ
れた前記第一のディジタル署名に基づき、第二のディジ
タル署名方式により第二のディジタル署名を生成する署
名生成手段と、前記第一および第二のディジタル署名に
基づき、前記第二のディジタル署名が前記指定手段によ
り指定された署名生成手段により生成されたものか否か
を確認する確認手段とを有することを特徴とする。

【００５８】

【発明の実施の形態】以下、本発明にかかる一実施形態
の情報通信システムを図面を参照して詳細に説明する。

【００５９】本発明にかかるディジタル署名方式は、乱
数を指数とする計算により公開鍵と底を変換するが、秘
密鍵の値は変わらないという性質を利用して、離散対数
に基づくディジタル署名方式を構成し、MOシステムにお
ける零知識証明を用いるディジタル署名方式に代わっ
て、通常のディジタル署名方式を用いるものである。

【００６０】このような構成を備える本発明のディジタ
ル署名方式を用いた情報通信システムによれば、署名者
の公開鍵を必要とせずに署名を確認することができるの
で、署名者の匿名性を保つことができるとともに、零知
識証明により署名者と確認者との間で複数回の送受信を
行わずに、署名者から確認者へディジタル署名を送るだ
けで署名を確認することができ、通信回数を減らし、複
数回の通信に伴う計算も行わずに済ませることができ
る。さらに、同一の相手と何度も通信を行っても匿名性
が保たれる通信ネットワークを用いなくとも、少なくと
も一回の通信を行ったときに匿名性を保つことができる
通信ネットワークを用いることができる。

【００６１】

【第1実施形態】図2は本発明にかかるディジタル署名方
式およびそれを用いた情報通信システムを説明するため
の図、図3はディジタル署名に関する処理の流れの概要
を示すフローチャートである。

【００６２】Step 0（準備）: MOシステムと同じ。

【００６３】Step 1（ユーザ指定と公開）: 指定者i
は、複数の中からあるユーザ、すなわち署名者jを選び
（図2に示す矢印201）、署名者jの公開鍵v_jを乱数r_j
を用いて変換したz_jを計算し、z_jに対する署名（Schn
orr暗号による署名）を求め（図2に示す手順(1)）、公
開データベースに登録する（図2に示す矢印202）。

【００６４】具体的には、指定者iは（秘密の）乱数r_j
(r_j ∈ Zq*)を選び、次式により各パラメータを求め、
署名((y_j, e_j)，z_j)を公開データベースに登録す
る。 x_j = α^{r_j} mod p z_j = {v_j}^{r_j} mod p e_j = h(x_j, z_j) y_j = r_j + e_j・s_i mod q

【００６５】Step 2（情報のピックアップ）: 署名者j
は、公開データベースに登録された内容から、指定者i
が登録した署名((y_j, e_j), z_j)が、自分に対するも
のであるか否かを次のように確認する（図2に示す手順
(2)、矢印203）。つまり、各ユーザは、次式を確認す
る。 e_j = h(α^{y_j}・{v_i}^{e_j} mod p, z_j) …(5) z_j =(α^{y_i}・{v_i}^{e_j} mod p)^{-s_k} mod p …(6)

【００６６】ここで、x_j = α^{y_j}・{v_i}^{e_j} mod
pが成り立っているので、以降は、表記を簡略化するた
めにx_jを用いる。

【００６７】すべてのユーザは、式(5)が成り立つこと
を確認できる。それに加えて、署名者jは式(6)も成立す
ることを確認でき、自分が指定者iに選ばれたことがわ
かる。

【００６８】一方、ほかの署名者λ（s_λ≠s_jとす
る）は、式(6)が自分の秘密鍵s_λでは成り立たないこ
とがわかるが、式(6)が、ほかのどの署名者に対して成
立するものかは分からない（ほかの署名者の秘密鍵、例
えばs_jを知らない）ので、ほかの誰が選ばれたのかは
分からない。

【００６９】Step 3（署名生成）: 署名者jは、署名し
たいメッセージm(j)に対し、次の署名方式で署名を生成
する。署名者jは、秘密の乱数r(j)を選び(r(j) ∈ Zq
*)、次式を計算する。 x(j) = {x_j}^{r(j)} mod p e(j) = h(x(j), m(j)) y(j) = r(j) + e(j)・s_j mod q

【００７０】そして、(((y_j, e_j), z_j), ((y(j), e
(j)), m(j)))を署名として、必要な相手に送る（図2に
示す手順(3)、矢印204）。

【００７１】Step 4（署名確認）: 上記署名を受信した
確認者は最初に、式(5)を確認し、次に次式を確認する
（図2に示す手順(4)）。 e(j) = h({x_j}^{y(j)}・{z_j}^{e(j)} mod p, m(j))

【００７２】上記が確認できたならば、受信者（確認
者）は、メッセージm(j)に対する署名は指定者iに選ば
れた署名者jによって生成された署名であると納得す
る。

【００７３】なお、署名者jの公開鍵を変換したz_jに対
する指定者iの署名((y_j, e_j)，z_j)は、匿名の公開鍵
証明書とみなせる。

【００７４】以上の実施形態において、指定者、署名
者、確認者はそれぞれ、情報処理および通信に関する能
力をもつ情報処理装置、例えばパーソナルコンピュータ
上において実現可能である。指定者、署名者、確認者の
間における通信は、例えばインターネットのようなネッ
トワーク上で公開データベースや匿名通信を可能にする
サービスを運用することによって実現できる。

【００７５】そして、パーソナルコンピュータのような
装置により、上記の計算を行い、上記のサービスが利用
できる通信ネットワーク上で通信を行うことにより、上
記の各ステップを実行して、ディジタル署名を用いた情
報通信システムを構築することができる。勿論、インタ
ーネットに限らず外部と分離された環境、例えば企業内
においても、情報処理装置を用いて通信ネットワークお
よびサービスを構築することにより、ディジタル署名を
用いた情報通信システムを構築することができる。

【００７６】また、上記では、匿名の公開鍵証明書を、
公開データベースに登録することにより署名者に渡す例
を説明したが、指定者が本当に署名者の指定を行ってい
るか否かを他の多数のユーザが直接確認する必要がない
場合、指定者は、匿名の公開鍵証明書を指定した署名者
に直接渡してもよい。

【００７７】以上説明したように、本実施形態のディジ
タル署名を用いた情報通信システムは、MOシステムと異
なり、署名者の公開鍵を必用としないので、匿名性が保
つことができる。また、確認者との間で複数回の送受信
を行わなくてもよいので、前提とする匿名通信ネットワ
ークに対する要求条件を緩めることができ、実用化コス
トを下げることができる。さらに、通信回数、計算量に
関して、その効率を向上することができるので、ユーザ
に対して使い易く、かつユーザの負担を少なくすること
ができる。

【００７８】

【第2実施形態】以下、本発明にかかる第2実施形態の情
報通信システムを説明する。なお、第2実施形態におい
て、第1実施形態と略同様の構成については、同一符号
を付して、その詳細説明を省略する。

【００７９】前述した実施形態においては、z_jに対す
る公開鍵証明書をSchnorr暗号の署名を用いて生成し、
p, q, x_j, z_jを公開鍵、s_jを秘密鍵として、メッセ
ージm_jに対してSchnorr暗号の署名を適用した。これに
対し、第2実施形態においては、メッセージm_jに対し
て、Schnorr暗号の署名ではなくE暗号(T. E. ElGamal:
"Apublic key cryptosystem and a signature scheme
based on discretre logarithms, IEEE Transaction on
Information Theory, Vol. IT-31, No. 4, pp.469-47
2, 1985)を適用する。

【００８０】以下では、第1実施形態と異なる点だけを
説明する。

【００８１】Step 3（署名生成）: 署名者jは、署名を
したいメッセージm(j)に対し、次の方式で署名を生成す
る。署名者jは、秘密の乱数k(j)を選び(k(j) ∈ Zq*)、
次式を計算する。 r(j) = {x_j}^{k(j)} mod p s(j) = (m(j) + s_j・r(j))・k(j)^{-1} mod (p - 1)

【００８２】そして、(((y_j, e_j), z_j), ((r(j), s
(j)), m(j)))を署名として、必要な相手に送る。

【００８３】Step 4（署名確認）: 上記署名を受信した
確認者は最初に、式(5)を確認し、次に次式を確認す
る。 {x_j}^{m(j)} ≡ {z_j}^{r(j)}・r(j)^{s(j)} (mod p)

【００８４】上記が確認できたならば、受信者（確認
者）は、メッセージm(j)に対する署名は指定者iに選ば
れた署名者jによって生成された署名であると納得す
る。

【００８５】

【第3実施形態】以下、本発明にかかる第3実施形態の情
報通信システムを説明する。なお、第3実施形態におい
て、第1実施形態と略同様の構成については、同一符号
を付して、その詳細説明を省略する。

【００８６】前述した第1および第2実施形態において
は、z_jに対する公開鍵証明書をSchnorr暗号の署名を用
いて生成し、メッセージm_jに対してSchnorr暗号または
E暗号を適用する例を説明した。同様に、ディジタル署
名標準案としてNIST(NationalInstitute of Standard a
nd Technology)に提案されたDSA（Digital SignatureAl
gorthm: 岡本栄司著、暗号理論入門、共立出版、pp.136
-138参照）をメッセージm_jに対して用いることも可能
である。

【００８７】p, q, x_j, z_jを公開鍵、s_jを秘密鍵と
して用いる。

【００８８】Step 3（署名生成）: 署名者jは、署名を
したいメッセージm(j)に対し、次の方式で署名を生成す
る。署名者jは、秘密の乱数k(j)を選び(k(j) ∈ Zq*)、
次式を計算する。 r(j) = ({x_j}^{k(j)} mod p) mod q s(j) = k(j)^{-1}・(H(m(j)) - s_j・r(j)) mod q

【００８９】そして、(((y_j, e_j), z_j), ((r(j), s
(j)), m(j)))を署名として、必要な相手に送る。

【００９０】Step 4（署名確認）: 上記署名を受信した
確認者は最初に、式(5)を確認し、0< r(j) < q, 0 < s
(j) < q を確認した後、次の処理を行う。 w = (s(j)) - 1 mod q u1 = H(m(j))・w mod q u2 = r(j)・w mod q v = ({x_j}^{u1}・{z_j}^{u2} mod p) mod q

【００９１】そして、以上の計算結果からv = r(j)を確
認し、確認できたならば受信者はm(j)に対する署名は指
定者iに選ばれた署名者jによって生成された署名である
と納得する。

【００９２】

【第4実施形態】以下、本発明にかかる第4実施形態の情
報通信システムを説明する。なお、第4実施形態におい
て、第1実施形態と略同様の構成については、同一符号
を付して、その詳細説明を省略する。

【００９３】前述した第1から第3実施形態においては、
z_jに対する公開鍵証明書をSchnorr暗号の署名を用いて
生成し、メッセージm_jに対してSchnorr暗号、E暗号ま
たはDSAを適用する例を説明した。これに対して、z_jに
対する公開鍵証明書の生成にSchnorr暗号の署名の代わ
って、E暗号を適用することも可能である。ただし、x_j
とz_jが次式の関係を満たすことが保証できるように、
署名を適用することに注意する。 x_j = α^{r_j} mod p z_j = {v_j}^{r_j} mod p

【００９４】具体的には、以下のとおりである。指定者
iは、署名者jに対して、秘密の乱数r_jを選び(r_j ∈ Z
q*)、次式を計算する。 x_j = α^{r_j} mod p z_j = {v_j}^{r_j} mod p S_j = (z_j + s_i・x_j)・{r_j}^{-1} mod (p - 1)

【００９５】そして、((x_j, S_j)，z_j)を公開鍵証明
書とする。公開鍵証明書の正当性は、次式が成り立つこ
とで確認できる。 α^{z_j} ≡ {v_i}^{x_j}・{x_j}^{S_j} (mod p) z_j = {x_j}^{-S_j} mod p

【００９６】

【第5実施形態】以下、本発明にかかる第5実施形態の情
報通信システムを説明する。なお、第5実施形態におい
て、第1実施形態と略同様の構成については、同一符号
を付して、その詳細説明を省略する。

【００９７】前述した第4実施形態においては、z_jに対
する公開鍵証明書の生成にSchnorr暗号の署名の代わり
にE暗号を適用する例を説明した。これに対して、Schno
rr暗号やE暗号の代わりに、DSAを適用することも可能で
ある。ただし、x_jとz_jが次式の関係を満たすことが保
証できるように、署名を適用することに注意する。 x_j = α^{r_j} mod p z_j = {v_j}^{r_j} mod p

【００９８】具体的には、以下のとおりである。指定者
iは、署名者jに対して、秘密の乱数r_jを選び(r_j ∈ Z
q*)、次式を計算する。 x_j = α^{r_j} mod p z_j = {v_j}^{r_j} mod p S_j = {r_j}^{-1}・(H(z_j) - s_i・x_j) mod q

【００９９】そして、((x_j, S_j), z_j)を公開鍵証明
書とする。公開鍵証明書の正当性は、次のように確認で
きる。まず、0 < x_j < p, 0 < S_j < q を確認した
後、次の処理を行う。 w = {S_j}^{-1} mod q u1 = H(z_j)・w mod q u2 = x_j・w mod q v = α^{u1}・{v_i}^{u2} mod p

【０１００】そして、v = x_jを確認する。公開鍵証明
書の正当性は、次式が成り立つことで確認できる。 z_j = {x_j}^{-S_j} mod p

【０１０１】

【他の実施形態】なお、本発明は、複数の機器（例えば
ホストコンピュータ，インタフェイス機器，リーダ，プ
リンタなど）から構成されるシステムに適用しても、一
つの機器からなる装置（例えば、複写機，ファクシミリ
装置など）に適用してもよい。

【０１０２】また、本発明の目的は、前述した実施形態
の機能を実現するソフトウェアのプログラムコードを記
録した記憶媒体を、システムあるいは装置に供給し、そ
のシステムあるいは装置のコンピュータ（またはCPUやM
PU）が記憶媒体に格納されたプログラムコードを読出し
実行することによっても、達成されることは言うまでも
ない。この場合、記憶媒体から読出されたプログラムコ
ード自体が前述した実施形態の機能を実現することにな
り、そのプログラムコードを記憶した記憶媒体は本発明
を構成することになる。プログラムコードを供給するた
めの記憶媒体としては、例えば、フロッピディスク，ハ
ードディスク，光ディスク，光磁気ディスク，CD-ROM，
CD-R，磁気テープ，不揮発性のメモリカード，ROMなど
を用いることができる。

【０１０３】また、コンピュータが読出したプログラム
コードを実行することにより、前述した実施形態の機能
が実現されるだけでなく、そのプログラムコードの指示
に基づき、コンピュータ上で稼働しているOS（オペレー
ティングシステム）などが実際の処理の一部または全部
を行い、その処理によって前述した実施形態の機能が実
現される場合も含まれることは言うまでもない。

【０１０４】さらに、記憶媒体から読出されたプログラ
ムコードが、コンピュータに挿入された機能拡張カード
やコンピュータに接続された機能拡張ユニットに備わる
メモリに書込まれた後、そのプログラムコードの指示に
基づき、その機能拡張カードや機能拡張ユニットに備わ
るCPUなどが実際の処理の一部または全部を行い、その
処理によって前述した実施形態の機能が実現される場合
も含まれることは言うまでもない。

【０１０５】本発明を上記記憶媒体に適用する場合、そ
の記憶媒体には、先に説明したフローチャートに対応す
るプログラムコードを格納することになるが、簡単に説
明すると、図4Aおよび4Bのメモリマップ例に示す各モジ
ュールを記憶媒体に格納することになる。すなわち、少
なくとも「公開情報生成」「署名生成」「判別」および
「変換」の各モジュール、または、「底生成」「公開鍵
生成」「署名生成」および「確認」の各モジュールのプ
ログラムコードを記憶媒体に格納すればよい。

【０１０６】

【発明の効果】以上説明したように、本発明によれば、
署名者の匿名性を保つディジタル署名方式を提供するこ
とができる。

【０１０７】また、通信回数を減らし、複数回の通信に
伴う計算も行わずに済むディジタル署名方式を用いた情
報通信システムを提供することができる。

【０１０８】また、少なくとも一回の通信を行ったとき
に匿名性を保つことができる通信ネットワークを用いる
ディジタル署名方式を用いた情報通信システムを提供す
ることができる。

【図面の簡単な説明】

【図１】MOシステムの概念図、

【図２】本発明にかかるディジタル署名を用いた通信シ
ステムを説明するための図、

【図３】ディジタル署名に関する処理の流れの概要を示
すフローチャート、

【図４Ａ】本発明にかかるプログラムコードを格納した
記憶媒体のメモリマップ例を示す図、

【図４Ｂ】本発明にかかるプログラムコードを格納した
記憶媒体のメモリマップ例を示す図である。

Claims (16)

【特許請求の範囲】
1. 【請求項１】 各ユーザが共通に使用する公開パラメー
   タと、各ユーザに固有の秘密情報とから、各ユーザに固
   有の公開情報を生成する公開情報生成ステップと、 所定のディジタル情報に、前記秘密情報および前記公開
   パラメータを用いた変換を施すことにより、前記ディジ
   タル情報に対応する署名情報を生成する署名生成ステッ
   プと、 前記ディジタル情報と前記署名情報との対応関係を、前
   記公開パラメータおよび前記公開情報を用いて判別する
   判別ステップと、 前記秘密情報を変換せずに前記公開パラメータおよび前
   記公開情報を変換して、前記署名情報を生成することが
   できる新たな公開パラメータおよび公開情報にする変換
   ステップとを有することを特徴とするディジタル署名方
   式。
2. 【請求項２】 前記公開情報生成ステップは、前記公開
   パラメータおよび前記公開情報から前記秘密情報を求め
   ることが困難であるように、前記公開情報を生成するこ
   とを特徴とする請求項1に記載されたディジタル署名方
   式。
3. 【請求項３】 前記署名生成ステップは、前記秘密情報
   と、前記変換ステップで変換された公開パラメータとを
   用いて、所定のディジタル情報に対応する署名情報を生
   成することを特徴とする請求項1に記載されたディジタ
   ル署名方式。
4. 【請求項４】 前記判別ステップは、前記ディジタル情
   報と前記署名情報との対応関係を、前記変換ステップで
   変換された公開パラメータおよび公開情報とを用いて判
   別することを特徴とする請求項1に記載されたディジタ
   ル署名方式。
5. 【請求項５】 複数ユーザ間で共通に使われる底の値に
   対して各ユーザの秘密鍵を指数値として指数計算を行っ
   た結果を各ユーザの公開鍵とするディジタル署名方式で
   あって、 前記底に対して乱数を指数値として指数計算を行った結
   果を新しい底とする底生成ステップと、 所定のユーザの公開鍵に対して前記乱数を指数値として
   指数計算を行った結果を新しい公開鍵とする公開鍵生成
   ステップと、 前記所定のユーザが、自身の秘密鍵を用いて、任意の平
   文に対してディジタル署名を生成する署名生成ステップ
   と、 前記底生成ステップおよび前記公開鍵生成ステップによ
   り生成された底と公開鍵とを用いて、前記署名生成ステ
   ップで生成されたディジタル署名の正当性を確認する確
   認ステップとを有することを特徴とするディジタル署名
   方式。
6. 【請求項６】 離散対数を求めることの困難性に安全性
   の根拠をおくことを特徴とする請求項5に記載されたデ
   ィジタル署名方式。
7. 【請求項７】 Schnorr署名方式および/またはElGamal
   署名方式および/またはDSA方式を用いることにより、前
   記離散対数を求めることを困難にすることを特徴とする
   請求項6に記載されたディジタル署名方式。
8. 【請求項８】 ディジタル署名を生成する生成手段を指
   定する指定手段と、 少なくとも一つのディジタル署名方式を用いて、対象の
   ディジタル署名が前記指定手段により指定された生成手
   段により生成されたものか否かを確認する確認手段とを
   備えた情報通信システムであって、 前記ディジタル署名方式の一つは、請求項5から請求項7
   の何れかに記載されたディジタル署名方式であることを
   特徴とする情報通信システム。
9. 【請求項９】 離散対数を求めることの困難性に安全性
   の根拠をおく第一のディジタル署名方式を用いて、ディ
   ジタル署名を生成する署名生成手段を指定する指定手段
   と、 請求項5から請求項7の何れかに記載された第二のディジ
   タル署名方式により新しい底および新しい公開鍵を得る
   取得手段と、 前記取得手段により得られた新しい底の値を用いて、前
   記取得手段により得られた新しい公開鍵に対する第一の
   ディジタル署名を、前記第一のディジタル署名方式によ
   り生成する第一の生成手段とを備え、 前記第一の生成手段により得られたディジタル署名は、
   前記取得手段により得られた新しい公開鍵に対応する秘
   密鍵をもつ署名生成手段が指定されたことを示す証拠で
   あることを特徴とする情報通信システム。
10. 【請求項１０】 さらに、前記取得手段により得られた
    新しい底および新しい公開鍵を用いて、任意の平文に対
    して第二のディジタル署名を生成する第二の生成手段を
    有することを特徴とする請求項9に記載された情報通信
    システム。
11. 【請求項１１】 前記第一のディジタル署名方式の公開
    鍵を用いて前記第一のディジタル署名の正当性を確認す
    る第一の確認手段と、 前記第一の確認手段によりその正当性が確認された底お
    よび公開鍵を用いて前記第二のディジタル署名の正当性
    を確認する第二の確認手段と、 前記第一および第二の確認手段により得られた確認結果
    に基づき、対象とするディジタル署名が前記指定手段に
    より指定された署名生成手段により生成されたものか否
    かを判定する判定手段とを有することを特徴とする請求
    項10に記載された情報通信システム。
12. 【請求項１２】 前記第一のディジタル署名方式とし
    て、Schnorr署名方式および/またはElGamal署名方式お
    よび/またはDSA方式を用いることを特徴とする請求項9
    から請求項11に記載された情報通信システム。
13. 【請求項１３】 署名を生成する手段を指定するため
    に、第一のディジタル署名方式により第一のディジタル
    署名を生成する指定手段と、 前記指定手段により生成された前記第一のディジタル署
    名に基づき、第二のディジタル署名方式により第二のデ
    ィジタル署名を生成する署名生成手段と、 前記第一および第二のディジタル署名に基づき、前記第
    二のディジタル署名が前記指定手段により指定された署
    名生成手段により生成されたものか否かを確認する確認
    手段とを有することを特徴とする情報通信システム。
14. 【請求項１４】 ディジタル署名に関するプログラムコ
    ードが格納されたコンピュータ可読メモリであって、 各ユーザが共通に使用する公開パラメータと、各ユーザ
    に固有の秘密情報とから、各ユーザに固有の公開情報を
    生成する公開情報生成ステップのコードと、 所定のディジタル情報に、前記秘密情報および前記公開
    パラメータを用いた変換を施すことにより、前記ディジ
    タル情報に対応する署名情報を生成する署名生成ステッ
    プのコードと、 前記ディジタル情報と前記署名情報との対応関係を、前
    記公開パラメータおよび前記公開情報を用いて判別する
    判別ステップのコードと、 前記秘密情報を変換せずに前記公開パラメータおよび前
    記公開情報を変換して、前記署名情報を生成することが
    できる新たな公開パラメータおよび公開情報にする変換
    ステップのコードとを有することを特徴とするコンピュ
    ータ可読メモリ。
15. 【請求項１５】 複数ユーザ間で共通に使われる底の値
    に対して各ユーザの秘密鍵を指数値として指数計算を行
    った結果を各ユーザの公開鍵とするディジタル署名方式
    のプログラムコードが格納されたコンピュータ可読メモ
    リであって、 前記底に対して乱数を指数値として指数計算を行った結
    果を新しい底とする底生成ステップのコードと、 所定のユーザの公開鍵に対して前記乱数を指数値として
    指数計算を行った結果を新しい公開鍵とする公開鍵生成
    ステップのコードと、 前記所定のユーザが、自身の秘密鍵を用いて、任意の平
    文に対してディジタル署名を生成する署名生成ステップ
    のコードと、 前記底生成ステップおよび前記公開鍵生成ステップによ
    り生成された底と公開鍵とを用いて、前記署名生成ステ
    ップで生成されたディジタル署名の正当性を確認する確
    認ステップのコードとを有することを特徴とするコンピ
    ュータ可読メモリ。
16. 【請求項１６】 ディジタル署名方式を用いた情報通信
    システムのプログラムコードが格納されたコンピュータ
    可読メモリであって、 離散対数を求めることの困難性に安全性の根拠をおく第
    一のディジタル署名方式を用いて、ディジタル署名を生
    成する署名生成手段を指定する指定ステップのコード
    と、 請求項5から請求項7の何れかに記載された第二のディジ
    タル署名方式により新しい底および新しい公開鍵を得る
    取得ステップのコードと、 前記取得ステップで得た新しい底の値を用いて、前記取
    得ステップで得た新しい公開鍵に対する第一のディジタ
    ル署名を、前記第一のディジタル署名方式により生成す
    る第一の生成ステップとを有することを特徴とするコン
    ピュータ可読メモリ。