Undeniable Signatures

Prepared by Antonius Cahya Prihandoko Undeniable signature is a digital signature scheme that was invented by Chaum and van Antwerpen (1990). At least there are two special features of this scheme. First, signature verification process requires the cooperation of the signer, otherwise the signature cannot be verified. This feature prevent illegal duplication and distribution of the signed document as these actions cannot be done without the signer’s approval. Second, this scheme prevent the signer from denying a signature he made previously. This second feature can be achieve by incorporating a disavowal protocol.

An undeniable signature scheme consists of three components: signing algorithm, verification protocol, and disavowal protocol. Preparation stages for signing process are follows.

• Determine two primes, p and q, such that p=2q+1 such that the discrete log problem in $\mathbb{Z}_{p}$ is intractable
• Determine a non zero $\alpha \in \mathbb{Z}_{p}$, which is of order q. Note that $\alpha$ is a generator of G; a multiplicative subgroup of $\mathbb{Z}_{p}-\{0\}$ of order q which contains quadratic residues modulo p.
• Choose an element $a \in [1,q-1]$ and compute $\beta \equiv \alpha^{a} \bmod p$. For $\mathcal{P}=\mathcal{A}=G$ and $\mathcal{K} = \{(p,\alpha,a,\beta) | \beta \equiv \alpha^{a} \bmod p\}$, the values p, $\alpha$, and $\beta$ are public and a is secret.

When Bob want to send a message, $x \in G$, to Alice, he signs the message using his secret key, a, $y=sig_{K}(x) \equiv x^{a} \bmod p,$

and send the pair (x,y) to Alice.

Subsequently, Alice can verifies the signature y, using Bob’s public keys and the following protocol:

1. Alice randomly chooses $e_{1}, e_{2} \in \mathbb{Z}_{q}-\{0\}$; computes $c \equiv y^{e_{1}}\beta^{e_{2}} \bmod p$ and sends it to Bob;
2. Bob computes $d \equiv c^{a^{-1} \bmod q} \bmod p$ and send it back to Alice;
3.  Alice accepts y as a valid signature if and only if $d \equiv x^{e_{1}} \alpha^{e_{2}} \bmod p$

Where does this validity condition come from?. Starting from Bob’s response. He sent Alice, $d \equiv c^{a^{-1} \bmod q} \bmod p.$

Since $c \equiv y^{e_{1}} \beta^{e_{2}} \bmod p$, hence $d \equiv y^{a^{-1}e_{1}} \beta^{a^{-1}e_{2}} \bmod p.$

In addition, $\beta \equiv \alpha^{a} \bmod p$ implies that $\alpha \equiv \beta^{a^{-1}} \bmod p$. Similarly, $y \equiv x^{a} \bmod p$ implies that $x \equiv y^{a^{-1}} \bmod p$, and thus, $d \equiv x^{e_{1}} \alpha^{e_{2}} \bmod p.$

Can a fraudulent signature be accepted as valid?. Since y and $\beta$ are both elements of the multiplicative group G of prime order q, then each possible c corresponds to exactly q ordered pairs $(e_{1},e_{2})$ . Thus, it is hard for Bob to justify which pairs Alice used to compute c. Besides y, it can be analyzed that c, d and x are also in G. Since G is generated by $\alpha$, those elements can be expressed as a power of $\alpha$. Let $c = \alpha^{k}$, $d = \alpha^{l}$, $x = \alpha^{m}$, and $y = \alpha^{n}$, where $k,l,m,n \in \mathbb{Z}_{q}$. Thus, the congruences system: $c \equiv y^{e_{1}} \beta^{e_{2}} \bmod p$ $d \equiv x^{e_{1}} \alpha^{e_{2}} \bmod p$

is equivalent to the following system: $k \equiv ne_{1} + ae_{2} \bmod q$ $l \equiv me_{1} + e_{2} \bmod q.$

If $y \neq x^{a} \bmod p$ then $n \neq ma \bmod q$. Hence, the coefficient matrix of the linear equation system has non zero determinant, and thus the system has a unique solution. It means that every $d \in G$ is the correct response for exactly one of the q possible ordered pairs $(e_{1},e_{2})$. Therefore, the probability that the verification is failed, that is a fraudulent signature be accepted as valid, is 1/q.

Example:

The following illustration make those algorithm and protocol, clear.

Let p=359 and q=179. Clearly, they satisfy the requirement. Since 7 is a primitive root of 359, hence $7^{2}=49$ is a generator of group of quadratic residues modulo 359 and of order of 179. So we can take $\alpha=49$. Suppose a=163, then $\beta = \alpha^{a} \bmod 359 = 37$.
The values p=359, $\alpha=49$, and $\beta=37$ are public, while a=163 is secret.

• Bob sign the message x=235 with the signature $y=x^{a} \bmod 359 = 24$ and send the pairs (235,24) to Alice.
• When receiving the message x, Alice wants to verify the signature y. Suppose Alice chooses $e_{1}=143$ and $e_{2}=72$, then she will compute $c=y^{e_{1}}\beta^{e_{2}} \bmod 359 = 24^{143}37^{72} \bmod 359 = 303$

and send it to Bob.

•   Bob will then compute $d=c^{a^{-1} \bmod 179} \bmod 359 = 303^{163^{-1} \bmod 179} \bmod 359 = 202$

and send it back to Alice.

• Alice check Bob’s response by verifying that $x^{e_{1}} \alpha^{e_{2}} \bmod 359 = 235^{143}49^{72} \bmod 359 = 202 = d$

Hence, Alice accepts that the signature y=24 is valid for the message x=235.

It should be noted that in the real implementation, p and q are very big primes such that the discrete log problem in $\mathbb{Z}_{p}$ is hard to be break.

Disavowal Protocol

In case when $d \neq x^{e_{1}} \alpha^{e_{2}} \bmod p$, Alice has to consider whether y is a forgery or Bob denies his signature. To evaluate this, Alice continues the verification using the following disavowal protocol.

1. Alice randomly chooses $f_{1}, f_{2} \in \mathbb{Z}_{q}^{*}$, computes $C \equiv y^{f_{1}} \beta^{f_{2}} \bmod p$ and send it to Bob;
2. Bob computes $D \equiv C^{a^{-1} \bmod q} \bmod p$ and send it to Alice;
3. Alice verifies that $D \neq x^{f_{1}} \alpha^{f_{2}} \bmod p$
4. Alice concludes that y is a forgery and Bob did not deny  if and only if $(d \alpha^{-e_{2}})^{f_{1}} \equiv (D \alpha^{-f_{2}})^{e_{1}} \bmod p$

How does this decision come?. After Bob’s second response also does not match to the validity condition, then in order to ensure that Bob is consistent, Alice compares two responses of Bob: d and D. Since $d \equiv c^{a^{-1}} \bmod p$, $c \equiv y^{e_{1}} \beta^{e_{2}} \bmod p$, and $\beta \equiv \alpha^{a} \bmod p$, it can be obtained that $(d \alpha^{-e_{2}})^{f_{1}} \equiv y^{e_{1}a^{-1}f_{1}} \bmod p.$

Similarly, since $D \equiv C^{a^{-1}} \bmod p$ and $C \equiv y^{f_{1}} \beta^{f_{2}} \bmod p$, then $(D \alpha^{-f_{2}})^{e_{1}} \equiv y^{e_{1}a^{-1}f_{1}} \bmod p.$

So Bob does not disavow and Alice is convinced that the invalid signature is forgery.

Can Bob deny the signature he has made?. If Bob want to fool Alice that the valid signature is forgery, he has to be consistent in responding Alice’s verification request. In other words, if $y \equiv x^{a} \bmod p$, can Bob find exact d and D to response Alice, such that $d \neq x^{e_{1}} \alpha^{e_{2}} \bmod p$ and $D \neq x^{f_{1}} \alpha^{f_{2}} \bmod p$, and meets $(d \alpha^{-e_{2}})^{f_{1}} \equiv (D \alpha^{-f_{2}})^{e_{1}} \bmod p ?$

It will be hard for Bob to do so as he cannot predict the pairs $(e_{1},e_{2})$ and $(f_{1},f_{2})$ Alice used to construct c and C, respectively. Following the previous explanation, the probability that Bob disavows is 1/q.

The main characteristic of undeniable signatures is invisibility: the signatures cannot be recognized without the signature’s aids. The basic notion to accomplish this characteristic in the undeniable signature schemes is that a signature can only be verified by an interactive protocol between the signer and the recipient. With this characteristic, the signer is protected and ensured that the signature will be not subsequently misused by the recipient. The recipient, on the other hand, is convinced that the signer cannot deny a valid signature. For example, a content supplier may signs the content and allows costumers to inspect that the content is genuine. It is claimed that with undeniable signature, only paying customers are able to verify the signature and they are ensured that the supplier remains accountable for the content. When the customer wants later to convince others, the subsequent verifications still requires the signer’s cooperation. Additionally, a zero-knowledge proof is also provided for confirmation (verification) protocol which does not allow the recipient to convince others.

Although the undeniable signature provides a good concept to protect both signer and receiver, some issues rise from its confirmation protocol. The protection scenario is less applicable for many practical application as it relies on the signer cooperation in subsequent signature verification. If the signer is later unavailable or refuse to cooperate, then the recipient cannot make use of the signature. To overcome this problem, some improvement schemes are proposed, such as the convertible undeniable signature and the designated confirmer signature.

The convertible undeniable signature employs secret information which would be used to convert undeniable signature into ordinary signature. In the ordinary form, the signature can be verified without aids of the signer but still be difficult to counterfeit. For example, using convertible undeniable signature, a software company can give some staffs the capability to verify signature, but unable to create signature. When the company later collapse, it can release the secret information needed to verify the signature, so the software can still be used appropriately.

The designated confirmer signature involves three parties: signer, recipient and confirmer. The signing protocol consists only of the signer and recipient. At this stage the recipient is convinced that the signature is produced using the signer’s private key and the confirmer’s public key. In the end of signing protocol, the recipient is convinced that the signature is valid but has no ability to prove it to others. Any subsequent confirmation protocol includes the confirmer and the verifier. The verifier could be another confirmer or recipient. In this protocol the confirmer convinces the verifier that the signature is valid without releases any transferable proof, thus the verifier cannot convince anyone else.

Besides availability of the signer, another issue also relies on the verification protocol, that is the signer has no control on the number of verifiers he proofs the signature validity to. While the signer thinks that he is confirming the validity of the signature to a certain person, he could  unconsciously be confirming it to a large group of people. This weakness can be shown  by simulating a distributed secure mental game. Some verifiers work together in a hidden protocol, unknown by the signer, generate a random string of bit to be used in the validation protocol with the signer. This leads a conclusion that undeniable signature is insecure against a multi-verifier attack. Another attack  is divertible zero-knowledge proof. A pirate (P) may stand between the signer (S) and the recipient (R) in the confirmation protocol. For example, let S is a software company and  R is a customer. P pretends a representative of S and is able to convince R,  so R pays P to buy the software. P does this and then sells it to colleague pirates. R plays the confirmation protocol with P and P then plays simultaneously the protocol with S. P modifies all responses he received from R and forwards them to S as well as the reverse. In the end of protocol, R is convinced that the software is genuine but is unconscious that P plays a divertible zero-knowledge proof. Nor does S.

Townsville, 27 February 2013