Undeniable signature

Undeniable signature is a digital signature scheme and implementation invented by David Chaum and Hans van Antwerpen in 1989.^[1]

In this scheme, a signer possessing a private key can publish a signature of a messages. However, the signature reveals nothing to a recipient/verifier of the message and signature without taking part in either of two interactive protocols:

• Confirmation protocol, which confirms that a candidate is a valid signature of the message issued by the signer, identified by the public key.
• Disavowal protocol, which confirms that a candidate is not a valid signature of the message issued by the signer.

The motivation for the scheme is to allow the signer to determine to whom he verifies or disavows a signature, and it is the interactive nature of the protocols that allows this; i.e., the result of each protocol is non-transferable. However, if there were only a confirmation protocol, there would be no way to distinguish between:

• the case that the signature is not a valid signature by the signer at issue, and
• the case that the signature was a valid signature by the signer at issue, but the signer now chooses not to take part in verification.

The disavowal protocol provides an interactive (i.e., non-transferable) proof of the former case.

The designated verifier signature scheme improves upon deniable signatures by allowing, for each signature, the interactive portion of the scheme to be offloaded onto another party, a designated verifier, reducing the burden on the signer.

Chaum's implementation

The following protocol was suggested by David Chaum.^[2]

A group, G, is chosen in which the discrete logarithm problem is intractable, and all operation in the scheme take place in this group. Commonly, this will be the (finite) cyclic group or order p, Z/nZ, with p being a large prime number; this group is equipped with the group operation of integer multiplication modulo p. An arbitrary primitive element (or generator), g, of G is chosen; computed powers of g then combine obeying fixed axioms.

Alice generates a key pair, randomly choosing a private key, x, and the deriving the public key, y = g^x.

Message signing

1. Alice signs the message, m, by computing and publishing z = m^x

Confirmation (i.e., avowal) protocol

Bob wishes to verify the message.

1. Bob picks two random numbers: a and b, and then sends to Alice: c = m^ag^b.
2. Alice picks a random number, q, and, using her private key, sends to Bob: s₁ = cg^q and s₂ = s₁^x. Note that s₁^x = (cg^q)^x = (m^ag^b)^xg^qx = (m^x)^a(g^x)^b+q.
3. Bob reveals a and b.
4. Alice verifies that c is not dishonest and was computed from a and b, then reveals q.
5. Bob verifies s₁ = cg^q, proving q has not been chosen dishonestly, and s₂ = z^ay^b+q, proving z is valid signature issued by Alice's key. Note that z^ay^b+q = (m^x)^a(g^x)^b+q.

Alice can cheat at step 2 by attempting to randomly guess s₂.

Disavowal protocol

Alice wishes to convince Bob that z is not a valid signature under the key, g^x; i.e., z ≠ m^x. Alice and Bob are both aware of m and z and have agreed an integer, k, which sets the computational burden on Alice and likelihood that she should succeed by chance.

1. Bob picks random values, s ∈ {0, 1, ..., k} and a, and sends: v₁ = m^sg^a and v₂ = z^sy^a, where exponentiating by a is used to blind the sent values. Note that z^sy^a = z^s(g^x)^a.
2. Alice, using her private key, computes v₁^x and then the quotient v₁^xv₂⁻¹. Note that v₁^xv₂⁻¹ = (m^sg^a)^x(z^sg^xa)⁻¹ = m^sxz^−s = (m^xz⁻¹)^s and, if z = m^x, v₁^xv₂⁻¹ = 1.
3. Alice conjectures s_A to be s by testing (m^xz⁻¹)ⁱ = v₁^xv₂⁻¹ for i ∈ {0, 1, ..., k}; (m^xz⁻¹)ⁱ can be calculated efficiently by repeated multiplication rather than exponentiating for each i. If the tests are inconclusive, she conjectures random value; this is the case when z = m^x, and (m^xz⁻¹)ⁱ = v₁^xv₂⁻¹ = 1 for all i.
4. Alice commits to s_A: she picks a random r and sends hash(r, s_A) to Bob.
5. Bob reveals a.
6. Alice confirms v₁ and v₂ are honest (i.e., can be generated using a) then reveals r.
7. Bob checks hash(r, s_A) = hash(r, s); knowing s proves z ≠ m^x.

If Alice attempts to cheat at step 3 by guessing s at random, the probability of succeeding is 1/(k + 1). So, if k = 1023 and the protocol is conducted ten times, her chances are 1 to 2¹⁰⁰.

See also

• Non-repudiation
• Designated verifier signature
• Topics in cryptography

References

1. Chaum, David; van Antwerpen, Hans (1990). "Undeniable Signatures". LNCS 435: 212–216.
2. Chaum, David (1991). "Zero-Knowledge Undeniable Signatures". Advances in Cryptology EUROCRYPT '90 Proceedings: 458–462.