The Ultimate Short Undeniable Signatures

Last update: May 17th, 2004.

Content

0. Abstract

A digital signature is a string of characters allowing to bind a document to a person or an entity. After he received the document and the signature, the recipient can authenticate them, by his own, using a public key.

The undeniable signatures have the particularity to be verifiable only with the cooperation of the signer. Indeed, an interactive protocol is established in order to specify the validity of the signature.

Benefiting from the fact that an attack against an undeniable signature must be done online, Professor Serge Vaudenay and his assistant Jean Monnerat have developed a scheme of signature leading to a signature length far smaller than the standard ones. The mathematical techniques used for this new scheme are based on particular functions named group characters.

Precise applications for this algorithm will be thoroughly studied by the inventors, but nevertheless, we can specify already some, such as electronic payment, software protection, e-commerce, traceability of goods and non traceable orders transmission.

1. Preliminaries

1.1 Classical Signature Schemes versus Undeniable Signature Schemes

Traditional digital signatures are called universally verifiable in the sense that anyone who received the public key of the signer can check if the signature of some document is valid or not. The signer has indeed two keys: a secret one, which enables the signing process, and a public one, which enables the verification process. As the name of the key suggests, the public key can be publicly released without compromising the security of the scheme.

Undeniable signatures are special purpose signature schemes in which the verification process is not possible without the collaboration of the signer himself. Here, the public key is not enough. Anyone who would like to verify the validity of a signature must request to the putative signer a proof of validity or invalidity of the signature. Of course, the signer can freely decline the request, but as the name of this technique suggests, it is impossible for the signer to prove that a signature is invalid when it is valid and vice versa. Originally, the notion of undeniable signature was proposed by David Chaum and Hans van Antwerpen in 1989 [CV90] in order to increase the privacy of the signer: a signer may not like that anyone can check that he signed some private document.

Formally, an undeniable signature scheme consists of

1. a key pair generation algorithm which produces the secret key and the public key;
2. a signature algorithm which takes a digital document and the secret key and produces the signature;
3. a confirmation protocol by which the signer who owns the secret key can formally prove that a given (valid) signature to a given document is valid to anyone who processes the public key;
4. a denial protocol by which the signer who owns the secret key can formally prove that a given (invalid) signature to a given document is not valid to anyone who possesses the public key.

• Anyone who does not possess the secret key cannot generate a digital document with a valid signature.
• If a signature is not valid, a cheating signer cannot successfully complete the confirmation protocol.
• If a signature is valid, a cheating signer cannot successfully complete the denial protocol.
• Running either protocols with the signer does not provide any extra information but the evidence that a signature is valid or not.
• Anyone who does not possess the secret key cannot distinguish a valid signature from an invalid one.

Besides the privacy aspect of undeniable signatures, there is another very nice characteristic property of these schemes: the length of the signature can be substantially reduced. Indeed, if a traditional signature is too short (say 40 bits), then anyone can forge it by exhaustive search: we can use the verification algorithm in order to check if a guess for the signature is correct or not until it is correct. This forgery attack is performed in an off-line way so it cannot be detected. Actually, when recent papers talk about "short signatures", they usually mean about a hundred bits by using elliptic curve techniques. (This can be compared to traditional RSA signatures on about a thousand bits.) With undeniable signatures, the forger cannot run a verification off-line, so this attack is not possible and the signature can substantially be shrunk. Since the verification must be performed on-line the signer can detect that someone tries to forge a signature. Here it is not unreasonable to talk about 40-bit signatures. Indeed, if someone can make a million attempts to forge a signature without being detected, then he can best produce a valid forgery with probability about one over a million.

1.2 Groups, Homomorphisms, and Characters

• for any a and b in G, the a+b is an element of G;
• for any a, b, and c in G, we have a+(b+c)=(a+b)+c;
• for any a and b in G, a+b=b+a;
• there exists an element of G which can be denoted 0 such that for any a in G, a+0=a;
• for any a in G, there exists an element of G which can be denoted -a and such that a+(-a)=0.

We can also consider groups with multiplicative notations. If * denotes the group operation, we can denote 1 the neutral element, 1/a the element such that a*(1/a)=1, so we can define a/b or aⁿ.

When considering two groups (say G with operation *, and H with operation +), a mapping f from G to H is called a group homomorphism if it preserves the group structure, i.e. if for any a and b in G we have

f( a*b ) = f(a) + f(b)

Characters over a group G are group homomorphisms from G to the group of complex numbers z=a+ib of module 1, i.e. such that a²+b²=1. As an example, we can consider G as the group of nonzero real numbers with the usual multiplication and f such that f(a)=1 if a is positive and f(b)=-1 if b is negative. Both +1 and -1 are complex numbers of module 1 and we easily check the group homomorphism property.

Let us now consider an integer n and the set G of all integers a such that

• 0 < a < n,
• gcd(a,n) = 1.

a*b = product(a,b) mod n

To conclude, we know that given integers a and n, we can easily compute the Jacobi symbol (a/n) which is a character of order 2. Conversely, unless the factorization into prime numbers of n is known, we do not know so far how to compute another character of order 2 in the group of invertible residues modulo n.

1.3 Eisenstein Integers, Gauss Integers

All we need to know here is that given integers a and n, and given an Eisenstein factor alpha of n, we can easily compute (a/alpha)₃. Conversely, unless the factorization into prime numbers of n is known, we do not know so far how to compute a character of order 3 in the group of invertible residues modulo n.

Let i denote the traditional imaginary number whose imaginary part is 1. We know that i⁴=1. The ring of Gauss integers is the set of all complex numbers which can be written a+ib where a and b are regular integers. We can also define the notion of Euclidean division and gcd, hence define the group of invertible residues modulo some Gauss integer alpha. We can define a character of order 4 where residues are mapped to some (a/alpha)₄ which is a power of i. Going back to invertible residues modulo a regular integer n, we can define a character (a/alpha)₄ for any alpha which divides n as a Gauss integer.

All we need to know here is that given integers a and n, and given a Gauss factor alpha of n, we can easily compute (a/alpha)₄. Conversely, unless the factorization into prime numbers of n is known, we do not know so far how to compute a character of order 4 in the group of invertible residues modulo n.

More information about Eisenstein and Gauss integers can be found in Ireland-Rosen [IR90].

2. MOVA Schemes

2.1 Set up of Signer's keys

Parameters=[Lkey,Lsig,Icon,Iden]

1. The signer picks a random string seed and pseudorandomly generate
   Xkey₁, ..., Xkey_Lkey
   from seed. He then computes
   Ykey_j = Hom(Xkey_j) for j = 1, ..., Lkey.
2. The signer interacts with a Registration Authority (RA). He first sends his choice for Xgroup, Ygroup and the parameters to RA. The RA picks a random seed and sends it to the signer. The signer generates all Xkey_j and Ykey_j like in the previous variant.
3. The signer does like in the first variant, but may be asked to prove the validity of his public key through an interactive protocol.

K_p = (Xgroup,Ygroup,seed,Parameters,Ykey₁,...,Ykey_Lkey)

K_s=Hom.

Note 1: the third variant is not always possible. This depends on the initial choice for Xgroup and Ygroup.

Note 2: following this set up scheme, the secret key consists of a group homomorphism Hom such that

Ykey_j = Hom(Xkey_j) for j = 1, ..., Lkey.

{(Xkey₁,Ykey₁),..., (Xkey_Lkey,Ykey_Lkey)}.

Note 3: a public key is called valid if there exists no more than one group homomorphism which interpolates this set of points. If there exist several group homomorphisms, then the signer can change it and deny his signatures. Since this violates one of the security requirements, it is important to make sure that the key is valid. Depending on which of the set up variants is chosen, the security parameter can be small or not. In the first variant, Lkey must be large in order to make impossible to generate a key with several possible group homomorphisms. In the second variant, the interaction with the RA limits the ability to forge an invalid key with a medium Lkey. In the third variants, when the proof protocol is possible without compromising the secrecy of Hom, Lkey can be very small.

2.2 Proof of interpolation

{(X₁,Y₁),...,(X_s,Y_s)}

1. The verifier picks some random combination
   x = r^d . X₁^a₁ ... X_s^a_s
   where r is taken from Xgroup and all a_j are taken from {0, 1, ..., d-1} and where d is the cardinality of Ygroup. He then sends x to the prover.
2. The prover computes y = Hom(x) and sends a commitment <y> to the verifier.
3. The verifier reveals r and all a_j to the prover.
4. The prover checks that the verifier computed x well from the revealed values and then opens <y> to the verifier.
5. The verifier checks that y is consistent with the commitment <y> and checks that
   y = Y₁^a₁ ... Y_s^a_s.
6. The sequence of previous steps is iterated I times in total.

Note 1: the commitment scheme is a classical cryptographic protocol which makes possible to commit to some value and postpone its disclosure. We cannot change the value after it is committed, so that opening the commitment discloses the value and proves that the it is the one we committed before.

Note 2: the iteration can be run in parallel as follows.

1. The verifier picks some random combinations
   x_i = r_i^d . X₁^a_i,1 ... X_s^a_i,s for i = 1, ..., I
   and sends them to the prover.
2. The prover computes all y_i = Hom(x_i) and sends a commitment
   <y₁,...,y_I>
   to the verifier.
3. The verifier reveals all r_i and a_i,j to the prover.
4. The prover checks that the verifier computed the x_i well from the revealed values and then opens the commitment to the verifier.
5. The verifier checks that all y_i are consistent with the commitment and checks that
   y_i = Y₁^a_i,1 ... Y_s^a_i,s for i = 1, ..., I.

2.3 Signature algorithm

Ymes_j = Hom(Xmes_j) for j = 1, ..., Lsig.

Signature = (Ymes₁,...,Ymes_Lsig)

2.4 Confirmation protocol

Signature = (Ymes₁,...,Ymes_Lsig)

{(Xkey₁,Ykey₁),..., (Xkey_Lkey,Ykey_Lkey), (Xmes₁,Ymes₁),..., (Xmes_Lsig,Ymes_Lsig)}

2.5 Denial protocol

Signature = (Zmes₁,...,Zmes_Lsig)

(Ymes₁,...,Ymes_Lsig).

(Xmes₁,...,Xmes_Lsig)

1. The verifier picks some random
   lambda₁, ..., lambda_Iden
   in {0,1,...,p-1} where p is the smallest prime factor of the cardinality of Ygroup. The verifier picks a random combinations
   x_i,k = r_i,k^d . Xkey₁^a_i,1,k ... Xkey_Lkey^a_i,Lkey,k . Xmes_k^lambda_i
   z_i,k = Ykey₁^a_i,1,k ... Ykey_Lkey^a_i,Lkey,k . Zmes_k^lambda_i
   for i = 1, ..., Iden and k = 1, ..., Lsig. and send all x_i,k and z_i,k to the signer.
2. The signer can compute
   y_i,k = Hom(x_i,k) for i = 1, ..., Iden and k = 1, ..., Lsig.
   Since we should have z_i,k / y_i,k = ( Zmes_k / Ymes_k )^lambda_i the signer can deduce all lambda_i for i = 1, ..., Iden. He sends a commitment
   <lambda₁,...,lambda_Iden>
   to all lambda_i.
3. The verifier reveals all values.
4. The signer checks that all values were well generated then open the commitment <lambda₁,...,lambda_Iden>.
5. The verifier checks the commitment.

2.6 Proof of validity of K_p

x = r^d . X₁^a₁ ... X_Lkey^a_Lkey

1. The prover picks x_i,1 in Xgroup at random for i = 1, ..., Ival and sends a commitment <x_1,1,...,x_Ival,1> to the verifier.
2. The verifier picks x_i,2 in Xgroup at random for i = 1, ..., Ival and sends them to the prover.
3. The prover solves
   x_i,1 . x_i,2 = r_i^d . X₁^a_i,1 ... X_Lkey^a_i,Lkey
   for i = 1, ..., Ival, sends all r_i and a_i,j to the verifier and opens the commitment.
4. The verifier checks the commitment and the above equations.

3. Performances, Examples, and Variants

3.1 Complexity Summary

3.2 Original MOVA Scheme versus Generalizations

A nice property of the original description is that there exists a variant in which no prime number generation is required. For instance, if we pick

n = a² + 3.b²

Ygroup = {1,j,j²}

Another interesting property of the original description is that for characters of order 3 and modulus n generated from prime numbers, we have a two-level hard problem: a first level enables signing, and a second level enables solving harder problems involving the factorization of n. We can imagine signatures with proxy in which the proxy can sign and the original signer can convert undeniable signatures into universally verifiable signatures.

3.3 Examples based on Characters

1. Any prover being able to pass the confirmation (resp. denial) protocol with probability larger than 1/1'000'000 must be able to extract the secret key from public information have the secret key, and the signature must be valid (resp. invalid).
2. Anyone being able to forge a valid signature with a probability greater than 1/1'000'000 must be able to extract the secret key from public information.
3. Anyone being able to distinguish valid signatures from invalid signatures with a significantly small probability of error must be able to extract the secret key from public information.
4. All interactive proof protocols are zero-knowledge: no malicious verifier can extract some useful information out from the protocol.
5. For d=2, anyone able to extract the secret key from public information can solve the quadratic residue problem and become a famous mathematician. For d=3, the result is similar.

As an example we can pick two random (large) prime numbers p and q and compute n = p.q. We take the group Xgroup of invertible residues modulo n, and

Ygroup = {-1,+1}

Hom(x) = (x/p)₂.

Elements of Ygroup are represented by a single bit. Thus the signature is of Lsig bits.

Another example consists of picking two random (large) prime numbers p and q such that p-1 and q-1 are factors of 3, computing n = p.q, taking the group Xgroup of invertible residues modulo n, taking

Ygroup = {1,j,j²}

Hom(x) = (x/sigma)₃

We can set up this scheme without generating prime numbers. Indeed, we can generate

n = a² + 3.b²

A rough estimate of the complexity analysis led to the following figures which all use signatures of 20 bits.

Another approach consists of choosing a composite modulus n such that there exists a small subgroup of order d. For instance we can pick a prime number p = md+1 such that the gcd of m and d is 1 and a prime number q such that the gcd of q-1 and d is 1. Then we take n = p.q, the group Xgroup of invertible residues modulo n, and the group Ygroup of residues modulo d. Let k = m.(q-1). We take a random k-th power g of a residue modulo n until it has a multiplicative order of d. Note that g spans a subgroup of Xgroup which is isomorphic to Ygroup. The group homomorphism is defined by

Hom(x) = log_g( x^k mod n )

Real implementations are in process and concrete implementation throughputs will be put here.

3.4 Main Characteristics

• we devise undeniable signatures instead of regular ones, which leads us to many important properties, including the privacy protection of the signer, which can be used in various applications;
• security parameters, included signatures sizes, are fully scalable depending on the required security level;
• we can offer a quite small computational overhead, namely a quadratic complexity cost in terms of the modulus size, including for the key set up scheme.

We can also notice that the signer and the confirmer have only small messages to send: the signature is short (e.g. 20 bits), the commitment can be quite short (e.g. 80 bits), and opening the commitment can be short as well (e.g. 80 bits). Indeed, we can take the commitment defined by

<val> = H( open , val )

The confirmation is essentially a 4-move protocol, but we can propose a 2-move variant provided that Icon was chosen so that

Icon.log₂(d) ≥ 80.

In cases where the set up variant 3 is possible, we can easily convert an undeniable signature into a regular signature by expressing the Xmes_j in terms of the Xkey_j. This way no interaction is required any more to verify a converted signature. This property is known as the selective convertibility property.

The special d=3 or d=4 cases with Eisenstein or Gauss integers have the interesting property to lead to a 2-level secret (namely the secret sigma and the secret factorization). In this case we can imagine to have a possible delegation: a delegate can sign with sigma, but do not have the full factorization. The main signer can do some more advanced protocols (e.g. convertibility) with the help of the factorization.

Finally, a verifier can easily do some batch verification and decrease the total cost of verifying many signatures.

4. Potential Applications

4.1 Untraceable Transactions

1. the the signer (represented by its public key),
2. the message to be signed,
3. the signature itself.

(Note that if one wishes to perform a signature confirmation without compromising this property then special care must be considered in the implementation of the protocol.)

4.2 Goods Traceability

Note that the server and the custom can run batch confirmation if several MOVA signatures have to be confirmed. Further note that only the first message containing the information, signature, and challenge, from the verifier to the server, is large. Finally the whole confirmation is run through a 4-move (or 2-move) protocols in which only the first message is large.

4.3 Electronic Commerce

4.4 Electronic Payment

Note that digital coin creation can be performed with a blind MOVA signature so that the bank is not able to later trace the coin, for a better privacy of the customers. Similarly, the confirmation can be blinded.

4.5 Software Protection

5. References