1 Introduction
Traditional digital signature provides non-repudiation property by universal verifiability, which means digital signature can be verified by anyone who knows signer's public key. However, such universal verifiability is undesirable in some situations because signer's private or sensitive information probably be contained in the signature. For example in e-auction system, bidder provides his bid's authenticity to tenderee by signing on it. Meanwhile, the bidder does not want tenderee disclosing the sealed bid to a potential competitor for that benefit tenderee and competitor but jeopardize the interests of the bidder. Mechanism to protect signer's privacy by preventing signature from being arbitrary dissemination is needed in such scenarios.
For solving such conflict between authenticity (non-repudiation) and privacy (controlled verifiability) in digital signature,
undeniable signature was firstly introduced by Chaum and van Antwerpen in 1989 [
1]. Verification of such signature requires the collaboration of the signer, so that the signer can control to whom the signed document is being disclosed.
The main drawback of undeniable signature is that if the signer become unavailable, then the recipient cannot make use of the signature. The concept of
designated confirmer signature (DCS) was introduced by Chaum [
2] to solve this weakness and concrete DCS scheme based on RSA [
3] was proposed. Confirming or denying signature can be accomplished with the assistance of a semi-trust third party, the confirmer in DCS scheme. Except of signer, anyone else cannot generate a valid DCS on behalf of signer. At the same time, confirmer cannot cheat verifier once he is involved in the signature verification. And the confirmer can selectively convert DCS into ordinary signature. Because such signature could protect signer's privacy, designated confirmer signature has many applications in fair contract signing and verifiable secret sharing.
Later, Okamoto presented a formal model and definition of DCS and proved that secure designated confirmer signature is equivalent to secure public-key encryption [
4]. However, it is shown that Okamoto's scheme is insecure because the confirmer can forge a signature [
5]. Michels and Stadler proposed a solution to Okamoto's problem by introducing a new tool-
confirmer commitments[
5]. Subsequently, a number of attempts have been made to design DCS schemes [
6-
10].
Unfortunately, till now, most previous DCS schemes are proved insecure [
2,
4,
5,
9,
10]. Jan Camenisch et al. pointed out that schemes [
2,
4,
5] are vulnerable to an
adaptive signature-transformation attack (which is similar to security against adaptive chosen-ciphertext attacks for encryption schemes)[
6]. Fangguo Zhang et al. presented denial attack and forge attack to Han et al.'s ID-based confirmer signature scheme [
10] and showed that it is actually an ID-based undeniable signature scheme [
11]. Guilin Wang et al. found several security flaws of Shangping Wang et al.'s scheme [
9] in invisibility, non-transferability and zero knowledge proof [
12].
On the other hand, there are secure DCS schemes such as Camenish-Michels scheme [
6]. However, their confirmation and disavowal protocol is not efficient because lots of double discrete logarithms and module exponential operation involve in it. Summing up the state of the art on DCS, most of DCS schemes are either insecure or secure at the sacrifice of efficiency. Therefore, designing new secure and efficient DCS scheme is the main motivation of this paper.
Our contributions. In this paper, we first present DCS and its formal security model based on Camenish-Michels scheme. By adopting interactive zero-knowledge proof of equality of two discrete logarithms as building block, we design a new designated confirmer signature scheme which has interactive confirmation and disavowal protocol. We show that the protocols satisfy completeness, soundness and non-transferability. Furthermore, unforgeability and invisibility of the new scheme are guaranteed by adopting DSA and RSA, which are widely employed in practice. Meanwhile, by comparing module exponential operation in confirmation and disavowal protocol, the new scheme is more efficient than the existing Camenish-Michels scheme. To the best of our knowledge, this is the first concrete implementation proposal based on DSA and RSA, provided with security and efficiency simultaneously.
Road-map. The rest of the paper is organized as follows: Some preliminary concept and notions are given in Section 2. In Section 3 we review the Camenish-Michels's DCS model and give new formal security definition. The new proposed DCS scheme based on DSA signature [
13] and RSA encryption is given in Section 4. In section 5, we present security analysis of the new scheme. In Section 6, new scheme is compared with other DCS schemes in security and efficiency analysis. Finally, conclusion is made in Section 7.
2 Preliminary notions
Let $p, q$ be two primes and $q \mid(p-1), g, h$ are generators of $Z_{p}^{*}$ with order $q.\langle g\rangle$ denotes subgroup generated by $g$. Assume that to determine two discrete logarithms equals or not is difficult in $\langle g\rangle. H:\{0,1\}^{*} \rightarrow Z_{q}$ is a collision resistant Hash function.
2.1 Interactive zero-knowledge proof
Assuming $x \in_{R} Z_{q}^{*}, y=g^{x}, z=h^{x}$, the following is an interactive zero-knowledge proof protocol of $\log _{g} y=\log _{h} z$.
(1)Verifier randomly chooses $a, b \in Z_{q}^{*}$ and computes $\alpha=h^{a} \cdot g^{b}$. Then, $\alpha$ is sent to prover.
(2)Prover randomly chooses $t \in Z_{q}^{*}$ and computes $\beta_{1}=\alpha \cdot g^{t}, \beta_{2}=\beta_{1}^{x}$. Prover sends $\left(\beta_{1}, \beta_{2}\right)$ to verifier.
(3)Verifier sends $(a, b)$ to prover.
(4)Prover validates $\alpha=h^{a} \cdot g^{b}$. If correct, $t$ is sent to verifier.
(5)Verifier validates whether equations $\beta_{1}=h^{a} \cdot g^{b+t}, \beta_{2}=z^{a} \cdot y^{b+t}$ hold or not.
The above protocol is proved to be zero-knowledge and the probability that prover cheats verifier is
$q^{-1}$ [
1].
2.2 Proof of knowledge
Proof of knowledge allows one entity to prove he knows a secret to others without leaking any useful information about the secret. We adopt notions in [
14]. For example,
$P K\left\{(\alpha, \beta, \gamma): y=g^{\alpha} h^{\beta} \wedge \tilde{y}=\tilde{g}^{\alpha} \tilde{h}^{\gamma} \wedge(u \leq \alpha \leq v)\right\}$
denotes zero-knowledge proofs of knowledge of $(\alpha, \beta, \gamma)$, such that $y=g^{\alpha} h^{\beta}$ and $\tilde{y}=\tilde{g}^{\alpha} \tilde{h}^{\gamma}$ holds, where $u \leq \alpha \leq v$. We use the convention that Greek letters denote the elements whose knowledge is proven and all other letters denote elements that are known to the verifier.
3 DCS model
In this section, we first briefly review Camenish-Michels's DCS model [
6], then we give new formal security definition for DCS scheme.
Let $S I G=(S K G, S i g, V e r)$ denote traditional digital signature scheme and $E N C=(E K G, E n c, D e c)$ denote public key encryption scheme. The players in a DCS scheme are signer $S$, confirmer $C$ and verifier $V$.
Definition 1. A designated confirmer signature scheme consists of the following components:
-Key generation: Let $C K G S\left(1^{l}\right)=S K G\left(1^{l}\right), C K G C\left(1^{l}\right)=E K G\left(1^{l}\right)$ and $C K G V\left(1^{l}\right)=E K G\left(1^{l}\right)$ be three probabilistic polynomial algorithms for signer, confirmer and verifier respectively. The parameter $l$ is a security parameter, $\left(x_{i}, y_{i}\right)(i \in\{S, C, V\})$ is a secret/public key pair for the signer, confirmer and verifier respectively.
-Signing: A probabilistic signature generation algorithm $C S i g\left(m, x_{S}, y_{S}, y_{C}\right) \rightarrow$ $\sigma$ that generates a signature $\sigma$ for message $m \in\{0,1\}^{*}$.
-Confirmation and disavowal: Given an alleged confirmer signature $\sigma$, message $m$ and public key $\left(y_{S}, y_{C}\right)$, the confirmer and verifier execute confirmation protocol $\operatorname{Conf}_{(C, V)}$ or disavowal protocol $\operatorname{Disavowal}_{(C, V)}$. The private input of the confirmer is $x_{C}$. The output of the verifier is either 1 (true) or 0 (false).
-Selective conversion algorithm: $\operatorname{CConv}\left(m, \sigma, y_{S}, x_{C}, y_{C}\right)$ outputs $s=$ $\operatorname{Dec}\left(\sigma, x_{C}, y_{C}\right)$, provided $\operatorname{Ver}\left(m, s, y_{S}\right)=1$, and $\bot $ otherwise.
-Public verification algorithm: $\operatorname{COVer}\left(m, s, y_{S}\right)=\operatorname{Ver}\left(m, s, y_{S}\right)$, for converted signature $s$.
In the following, we define the security requirements for DCS scheme. Informally speaking,
security for the signer guarantees that DCS as well as converted signature are unforgeable under an adaptive chosen-message attack [
15]. In other words, it assures that no one except the signer can generate a valid DCS signature.
Security for the confirmer or invisibility of signatures guarantees that the scheme is secure for the confirmer against adaptive chosen-confirmer-signature attacks (this is similar to security against chosen-ciphertext attacks for encryption schemes). This requirement assures that no one apart from the confirmer can confirm or deny signatures
11 The literature on confirmer signatures is inconsistent on whether the original signer has the ability to confirm and/or deny signatures. Here, we assume only confirmer can convince verifier whether DCS is valid or not.
. Finally,
non-transferability means that one cannot get more information out of the confirmation/disavowal protocol than whether a signature is valid or not.
Theorem 1. ([6]) If SIG is existentially unforgeable under an adaptive chosenmessage attack and ENC is secure against adaptive chosen-ciphertext attacks, then the above construction constitutes a secure confirmer signature scheme with perfect conversion.
Based on the above DCS model, formal security definition is given as follows.
Definition 2. Formally, a designated confirmer signature is secure if it satisfies the following properties,
·Security for signer (unforgeability): Let $\mathcal{A}$ be a probabilistic polynomial time (PPT) forging algorithm which, on input strings $\left(1^{n}, y_{S}, y_{C}\right)$ (and possibly also the secret key $s_{C}$ of the confirmer)
22 Considering the scenario of confirmer acting as an adversary.
.
$\mathcal{A}$ is allowed oracle access to the signer $S$ and receives S's signature of polynomially many adaptively messages $\left\{m_{i}\right\}$.
Finally, $\mathcal{A}$ halts and outputs a pair of strings $\left(m, s^{\prime}\right)$, where $m \neq m_{i}$ for all i.
We require that for all such $\mathcal{A}$,
all sufficiently large $n$ and for any message $m \notin\left\{m_{i}\right\}$,
$\operatorname{Pr}\left(C O V e r\left(m, s^{\prime}, y_{S}\right)=1\right)<\operatorname{negl}(n).$
The probability is taken over the coin tosses of the $S, \mathcal{A}$ and the key generation algorithms CKGS, CKGC.
·Security for the confirmer (invisibility): Let $\mathcal{A}$ be a PPT attacking algorithm which, on input strings $\left(1^{n}, y_{S}, y_{C}\right)$ can make oracle queries to the signers and confirmer via CSig, $\operatorname{Con} f_{(C, \mathcal{A})}$, Disavowal $_{(C, \mathcal{A})}$ for polynomially many inputs of his choice and finally, for a pair $\left(m, \sigma^{\prime}\right)$ of his choice, $\mathcal{A}$ executes $\operatorname{Conf}_{(\mathcal{A}, V)}\left(1^{n}, m, \sigma^{\prime}, y_{S}, y_{C}\right)$. For all such $\mathcal{A}$,
$\operatorname{Pr}\left(\operatorname{Con} f_{(\mathcal{A}, V)}\left(1^{n}, m, \sigma^{\prime}, y_{S}, y_{C}\right)=1\right)<\operatorname{negl}(n),$
where the probability is taken over all possible coin tosses of the $S, C, V, \mathcal{A}$ and the key generation algorithms CKGS, CKGC.
·Non-transferability of confirmation/disavowal: Let $\mathcal{A}$ be a PPT attacking algorithm which, on input strings $\left(1^{n}, y_{S}, y_{C}\right)$ can make oracle queries to the signers and confirmer. For every adversary $\mathcal{A}$, there exists simulator Sim, for all sufficiently large $n$ and $\left(x_{S}, y_{S}\right) \in\left\{C K G S\left(1^{n}\right)\right\},\left(x_{C}, y_{C}\right) \in\left\{C K G C\left(1^{n}\right)\right\}$,
$\left|\operatorname{Pr}\left(\operatorname{Conf}_{(C, \mathcal{A})}(\cdot)=1\right)-\operatorname{Pr}\left(\operatorname{Conf}_{(\operatorname{Sim}, \mathcal{A})}(\cdot)=1\right)\right|<\operatorname{negl}(n),$
where the probability is taken over all possible coin tosses of the $S, C, V, \mathcal{A}$ and the key generation algorithms CKGS, CKGC. Here, (•) denotes parameters $\left(1^{n}, m, \sigma, y_{S}, y_{C}\right)$.
4 New DCS scheme
In this section, we construct a new DCS scheme using DSA and RSA as building block. We refer the reader to [
13,
3] for more details about DSA and RSA algorithm.
(1) Signer's key generation algorithm: Signer chooses ( $p, q, g$ ) as system public parameters. The secret-public key pair is $\left(x_{S}, y_{S}=g^{x_{S}} \bmod p\right)$.
(2) Confirmer's key generation algorithm: Confirmer chooses RSA module $n$. The public key is $(n, e)$ and secret key is $d$.
(3) Verifier's key generation algorithm: The parameters is same as item 1. Verifier's secret-public key pair is $\left(x_{V}, y_{V}=g^{x_{V}} \bmod p\right)$.
(4) Signing: Given message $m$, signer $S$ first signs $m$ by DSA, $\operatorname{Sig}\left(m, x_{S}, y_{S}\right)=$ $(r, s)$. Then $S$ use confirmer's public key $y_{C}$ to encrypt $(r, s)$ by RSA. The designated confirmer signature is $\sigma=\left(c_{1}, c_{2}\right)$, where $c_{1}=r^{e} \bmod n, c_{2}=s^{e} \bmod n$.
(5) Confirm and disavowal protocol: Upon receipt of a request $m$ and $\sigma=\left(c_{1}, c_{2}\right)$ from verifier, confirmer first decrypts $\sigma$ using private key $d, r=c_{1}^{d} \bmod n, s=$ $c_{2}^{d} \bmod n$. Next, confirmer validates $(r, s)$ by DSA verification algorithm $V e r$, namely,
$r \stackrel{?}{=}\left(g^{H(m) s^{-1} \bmod q} y_{S}^{r s^{-1} \bmod q} \bmod p\right) \bmod q \text {. }$
If $\operatorname{Ver}\left(m, r, s, y_{S}\right)=1$ (or 0), then the confirmer convinces the verifier that the confirmer signature is valid (or invalid).
First, as showed in
Fig.1, confirmer and verifier execute interactive zeroknowledge proof protocol of
$\log _{g} u=\log _{h} v$ in order to convince verifier that confirmer knows secrete key
$d$ and the
$d$ can't be forged. If succeed, they execute the following procedures 5.1 or 5.2. Otherwise, protocol failure.
(5.1) (confirmation protocol): If
$\sigma$ is valid and
$\psi=h^{a} \cdot g^{b}$, confirmer convinces the verifier that decryption was successful and that decrypted value is a valid DSA signature with respect to
$m, p, q$ and
$g$ by executing the following protocol. The detailed step is described in
Fig.2.
$P K\left\{(\alpha, \beta): \begin{array}{l}c_{1}=\alpha^{e} \wedge c_{2}=\beta^{e} \wedge \\ c_{1}=\left(\left(g^{H(m) \beta^{-1} \bmod q} y_{S}^{\alpha \beta^{-1} \bmod q} \bmod p\right) \bmod q\right)^{e} \bmod n \end{array}\right\}. $
(5.2) (disavowal protocol): If $\sigma$ is invalid and $\psi=h^{a} \cdot g^{b}$, confirmer should convince verifier that
$P K\left\{(\alpha, \beta): \begin{array}{l} c_{1}=\alpha^{e} \wedge c_{2}=\beta^{e} \wedge \\ c_{1} \neq\left(\left(g^{H(m) \beta^{-1} \bmod q} y_{S}^{\alpha \beta^{-1}} \bmod q \bmod p\right) \bmod q\right)^{e} \bmod n\end{array}\right\}. $
The concrete implementation is presented in
Fig.3.
(6) Selective conversion algorithm: If $\sigma$ is valid, the confirmer converted $\sigma$ into normal DSA signature $(r, s)$, where $r=c_{1}^{d} \bmod n, s=c_{2}^{d} \bmod n$. Otherwise, confirmer outputs $\bot $.
(7) Public verification algorithm: $\operatorname{COVer}\left(m, s, y_{S}\right)=\operatorname{Ver}\left(m, s, y_{S}\right)$.
5 Security analysis
By Theorem 1, unforgeability and invisibility of signature is satisfied based on DSA and RSA's security. We mainly analyze confirmation and disavowal protocol's security as follows. Only proof sketch is presented here due to page limitation.
Theorem 2. The confirmation and disavowal protocol have the following properties:
·Completeness: given a valid (invalid) signature $\sigma$ on message $m$, if confirmer and verifier comply legally with the protocol, then the protocol always returns $\sigma$ as a valid (invalid) signature.
·Soundness: given an invalid (valid) signature $\sigma$ on message $m$, confirmer is unable to convince verifier of accepting it as valid (invalid) signature with nonnegligible probability.
Proof. (sketch) The completeness is trivial. For the soundness, generally there are two cases to be considered in case of confirmer is dishonest.
Case I: Confirmer forges designated confirmer signature.
Case II: Confirmer forges knowledge proof transcripts generated during confirmation and disavowal protocol.
The existence of case I conflicts with unforgeability. For case II, due to collision resistant property of hash function, it is computation infeasible to find different $\left(k_{1}\left\|k_{2}\right\| k_{3} \| k_{5}\right)$ (in confirmation protocol) or ($\alpha^{\prime}, \beta^{\prime}$) (in disavowal protocol) with the same hash value $c$. And equations $u^{e}=g, v^{e}=h$ guarantee secret $d$ can't be arbitrarily forged.
Therefore, given an invalid (valid) signature $\sigma$ on message $m$, confirmer is unable to convince verifier of accepting it as valid (invalid) signature with non-negligible probability.
Theorem 3. The confirmation and disavowal protocol satisfies non-transferability.
Proof. (sketch) We distinguish two cases of transferability:
Case I: Verifier tries to obtain ordinary signature $(r, s)$ then transfers it to other party.
Case II: Verifier directly transmits the proof transcripts to other party.
For case I, firstly, the confirmer's proof of secret key $d$ is zero-knowledge for that interactive zero-knowledge proof of equation of $\log _{g} u=\log _{h} v$ being adopted in scheme. Furthermore, verifier can't reverse to solve $(r, s)$ from $\left(s_{1}, s_{2}, s_{3}, s_{4}, c\right)$ or $\left(s_{1}, s_{2}, c\right)$ because secret $d$ is contained in the equations. (Particularly, it's unsolvable because there is five unknown quantities in four equations in confirmation protocol and three unknown quantities in two equations in disavowal protocol.)
For case II, if dishonest verifier stores and then transmits the transcripts $\left\{t, u, v, \beta_{1}, \beta_{2}, s_{1}, s_{2}, s_{3}, s_{4}, c\right\}$ or $\left\{t, u, v, \beta_{1}, \beta_{2}, s_{1}, s_{2}, c, c_{0}\right\}$ to other entity directly, verifier must executes interactive protocol to convince the other entity of transcripts' validity. In the interactive confirmation and disavowal protocol, other entity selects new random numbers $a^{\prime} \neq a$ and $b^{\prime} \neq b$ to compute $\psi^{\prime}=h^{a^{\prime}} \cdot g^{b^{\prime}}$, then sends it to verifier. After computing $\beta_{1}^{\prime}=\psi^{\prime} g^{t^{\prime}}$, verifier can't computes correct $\beta_{2}^{\prime}=\beta_{1}^{\prime d}$ for not knowing $d$. Deducing $d$ from $\beta_{1}, \beta_{2}$ will contradict discrete logarithm assumption. Furthermore, if verifier forge $d^{\prime} \neq d$, equations $u^{e}=g, v^{e}=h$ will not hold. Therefore, if verifier directly transfer transcripts to other entity, verifier can't convince its validity to other entity.
Summarizing the above two cases, non-transferability is satisfied.
To sum up, the new scheme satisfies unforgeability, invisibility and nontransferability.
Remark 1. The theorem is proved in the sense of honest verifier zero-knowledge and accomplished by sequential executing protocol. The concurrent scenario isn't considered in this paper.
Remark 2. Note that if
non-interactive knowledge proof protocol is used in confirmation and disavowal protocol, which verifier validates the transcripts provided by confirmer passively, verifier can leak signature validity information to other entity by transferring the signature and its corresponding proof transcripts. To assure nontransferability in such case, generally we can use designated verifier proof [
16] to make verifier obtaining ability to forge proof transcripts. Other entity can't trust verifier anymore because he can't distinguish transcripts generated by signer from transcripts generated by verifier.
6 Comparison with other schemes
Firstly, we compare security of DCS schemes mainly from unforgeability, invisibility and non-transferability aspects. (See
Table 1)
From the above table, we see that only Camenish-Michels scheme (CM00) and the new scheme satisfy three security properties simultaneously. Furthermore, under the precondition of having same security model and achieving same security level, new scheme is compared with CM00 on module exponential computing cost in confirmation and disavowal protocol. (see
Table 2). Let
$T_{\text {exp }}$ denotes module exponential computing time in
$G$.
By analyzing on most time-consuming operation in confirmation and disavowal protocol, module exponential cost of new scheme is less than CM00 scheme. Hence, it is more efficient than Camenish-Michels (CM00) scheme.
7 Conclusion
By adopting interactive zero-knowledge proof of equality of two discrete logarithms as building block, we design a new designated confirmer signature scheme which is based on DSA and RSA encryption. Comparing with the existing schemes, the new scheme satisfy unforgeability, invisibility, non-transferability. Meanwhile, the new scheme is more efficient than Camenish-Michels scheme.
National Grand Fundamental Research 973 Program of China under Grant(G1999035804)
PDF
(294KB)
