english only
School of Computer and Communication Sciences
LASEC - Security and Cryptography Laboratory
EPFL > IC > LASEC > publications
Banner IC
INDEX
Home
People
Research
Teaching
Publications
Softwares & Events
Intranet
How to reach us

CONTACT

EPFL - I&C - ISC - LASEC
Station 14 - Building INF
CH-1015 Lausanne
Switzerland

Tel. +41 21 693 7603
Fax. +41 21 693 7689

The Ultimate Short Undeniable Signatures

by Jean Monnerat and Serge Vaudenay

Last update: May 17th, 2004.


Content

0.Abstract
1.Preliminaries
2.MOVA Schemes
3.Performances, Examples, and Variants
4.Potential Applications
5.References

0. Abstract

The Security and Cryptography Laboratory (LASEC) of EPFL has recently developed a new undeniable digital signature scheme.

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

Digital signatures are bitstrings which are attached to electronic documents in order to bind them to some secret key. A valid signature proves that the document was seen by someone (or some process) who possesses the secret key. The similarity with handwritten signature is quite straightforward: if the handwritten signature is valid, it proves that the signer has seen and approved the document. But the similarity stops here. Indeed, handwritten signatures can easily be imitated or separated from the signed document. In the electronic world, the signature depends on both the secret key and the document itself. Actually, a valid digital signature for a document A is an invalid signature for a document B.

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.
This scheme should complete the following security requirements.

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

Groups are algebraic structures which consist of a set with an internal operation which satisfies the usual properties: associativity, existence of a neutral element, and invertibility. Additionally, we concentrate on groups for which the operation is commutative. If G denotes the set and + denotes the operation, From this we can define the notation a+b+c, or a-b, or even n.a for a positive or negative integer n.

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 an.

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

from which we can deduce that f(1)=0, f(1/a)=-f(a), and f(an)=n.f(a). For instance, if G is the group of non negative real numbers with the usual multiplication operation and H is the group of all real numbers with the usual addition operation, the logarithm function is a group homomorphism from G to H. As a more sophisticated example we can consider G as the group of nonzero complex numbers with the usual multiplication and H as the group of angles measurements in Degrees taken modulo 360 with the addition modulo 360, and the mapping f which maps a complex number z to the angle measurement u such that z divided by cos(u)+i.sin(u) is a positive real number. f(z) actually defines the argument of the complex number z, and we know from the definition of complex multiplication that f is a group homomorphism from G to H.

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 a2+b2=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

We consider the operation * defined by where product(a,b) denotes the usual multiplication of a by b and mod is the modulo operation: c mod n is the remainder of the Euclidean division of c by n. In other words: c mod n is the only positive integer r no greater than n such that c-r is a multiple of n. From number theory we know that G with * is a group: the group of invertible residues modulo n. We can further define an important function called the Jacobi symbol where an element a of G is mapped to an element denoted (a/n) (which has, by the way, nothing to do with the usual notion of division) which is either equal to +1 or to -1 and which indeed defines a character on G. It is furthermore computationally easy to compute (a/n) given a and n. We say it is a character of order 2 because all possible values are roots of order 2 of unity. When n is not a prime number, for any factor alpha of n we can define another character (a/alpha) of order 2 which is, in general, hard to compute unless we know alpha.

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

Let j denote the complex number whose real part is -1/2 and whose imaginary part is sqrt(3)/2. It is well known that j3=1. The ring of Eisenstein integers is the set of all complex numbers which can be written a+jb where a and b are regular integers. Like for regular integers, we can define the notion of Euclidean division and gcd, hence define the group of invertible residues modulo some Eisenstein integer alpha. Like for the Jacobi symbol, we can define a character of order 3 where a residue a is mapped onto a complex number (a/alpha)3 which is equal to either 1, or j, or j2. Going back to invertible residues modulo a regular integer n, we can define a character (a/alpha)3 for any alpha which divides n as an Eisenstein integer.

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)3. 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 i4=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)4 which is a power of i. Going back to invertible residues modulo a regular integer n, we can define a character (a/alpha)4 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)4. 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

The MOVA schemes (from the name of the inventors MOnnerat and VAudenay) can be described as follows.

2.1 Set up of Signer's keys

The signer selects groups Xgroup and Ygroup, a group homomorphism Hom from Xgroup to Ygroup, some set of security parameters and one of the following variants. (In what follows we will use multiplicative notations for Xgroup and Ygroup.)
  1. The signer picks a random string seed and pseudorandomly generate
      Xkey1, ..., XkeyLkey
    from seed. He then computes
      Ykeyj = Hom(Xkeyj) 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 Xkeyj and Ykeyj 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.
The public key is the tuple and the secret key is the group homomorphism 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

We say that Hom interpolates the set of points

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

A key technique in the MOVA schemes is the possibility to interactively prove that there exists a group homomorphism which interpolates a set of points with Xj taken from Xgroup and Yj taken from Ygroup. The proof protocol is such that it is probabilistically impossible to complete it if the group homomorphism does not exist, and it brings no extra information but the existence of it. We say that the proof protocol is zero-knowledge. The proof protocol between a prover and a verifier works as follows.
  1. The verifier picks some random combination
      x = rd . X1a1 ... Xsas
    where r is taken from Xgroup and all aj 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 aj 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 = Y1a1 ... Ysas.
  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
      xi = rid . X1ai,1 ... Xsai,s for i = 1, ..., I
    and sends them to the prover.
  2. The prover computes all yi = Hom(xi) and sends a commitment
      <y1,...,yI>
    to the verifier.
  3. The verifier reveals all ri and ai,j to the prover.
  4. The prover checks that the verifier computed the xi well from the revealed values and then opens the commitment to the verifier.
  5. The verifier checks that all yi are consistent with the commitment and checks that
      yi = Y1ai,1 ... Ysai,s for i = 1, ..., I.

2.3 Signature algorithm

In order to sign a digital document Message, the signer simply generates pseudorandomly some Xmes1, ..., XmesLsig in Xgroup from Message and computes The signature for Message is the sequence

2.4 Confirmation protocol

The confirmation for the validity of a signature for a document Message is performed by an interactive proof protocol in which the signer proves the existence of a group homomorphism which interpolates the set of points with Lkey + Lsig points in total. The proof protocol is run with Icon iterations.

2.5 Denial protocol

The denial works a little like the interpolation proof protocol. Assuming that the signer wants to deny the signature when he knows that the right signature for the message is Both the signer and the verifier can compute from Message.
  1. The verifier picks some random
      lambda1, ..., lambdaIden
    in {0,1,...,p-1} where p is the smallest prime factor of the cardinality of Ygroup. The verifier picks a random combinations
      xi,k = ri,kd . Xkey1ai,1,k ... XkeyLkeyai,Lkey,k . Xmesklambdai
      zi,k = Ykey1ai,1,k ... YkeyLkeyai,Lkey,k . Zmesklambdai
    for i = 1, ..., Iden and k = 1, ..., Lsig. and send all xi,k and zi,k to the signer.
  2. The signer can compute
      yi,k = Hom(xi,k) for i = 1, ..., Iden and k = 1, ..., Lsig.
    Since we should have zi,k / yi,k = ( Zmesk / Ymesk )lambdai the signer can deduce all lambdai for i = 1, ..., Iden. He sends a commitment
      <lambda1,...,lambdaIden>
    to all lambdai.
  3. The verifier reveals all values.
  4. The signer checks that all values were well generated then open the commitment <lambda1,...,lambdaIden>.
  5. The verifier checks the commitment.

2.6 Proof of validity of Kp

For the set up variant 3, the signer must convince any potential verifier that his public key is valid. For instance he can convince the Registration Authority (RA) that the key is valid and ask the RA to sign a certificate of validity. Convincing is done by another interactive proof between a prover and a verifier. This proof protocol is possible when the signer knows how to solve equations like with unknown r, a1, ..., aLkey. We use an additional parameter Ival to be put in Parameters. The interactive proof runs as follows.
  1. The prover picks xi,1 in Xgroup at random for i = 1, ..., Ival and sends a commitment <x1,1,...,xIval,1> to the verifier.
  2. The verifier picks xi,2 in Xgroup at random for i = 1, ..., Ival and sends them to the prover.
  3. The prover solves
      xi,1 . xi,2 = rid . X1ai,1 ... XLkeyai,Lkey
    for i = 1, ..., Ival, sends all ri and ai,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

To summarize, here is the list of all operations which have to be performed. We recall that Lkey, Lsig, Icon, Iden are parameters from the protocol, that we do computations in two groups Xgroup and Ygroup, that d is the cardinality of Ygroup, and that p is the smallest prime factor of d. In this summary we neglected cryptographic operations such as pseudorandom generation and commitment since they typically are negligible against the others.
protocolsignerverifier registration authoritynote
set up variant 1
  • Lkey applications of Hom
  • Lkey is large
    set up variant 2
  • Lkey applications of Hom
  • management of the registration
  • Lkey is medium
    set up variant 3
  • Lkey applications of Hom
  • Lkey is small
    but the proof of validity must be performed
    proof of validity of Kp
  • solve Ival equations x = rd . X1a1 ... XLkeyaLkey
  • Ival combinations rd . x1a1 ... xLkeyaLkey in Xgroup
  • this protocol is used only for set up variant 3
    signature
  • Lsig applications of Hom
  • confirmation
  • Icon applications of Hom
  • Icon combinations rd . x1a1 ... xLkey+LsigaLkey+Lsig in Xgroup
  • Icon combinations rd . x1a1 ... xLkey+LsigaLkey+Lsig in Xgroup
  • the same combinations in Ygroup
  • denial
  • Iden.Lsig applications of Hom
  • Iden.Lsig combinations rd . x1a1 ... xLkey+LsigaLkey+Lsig in Xgroup
  • Iden.Lsig combinations rd . x1a1 ... xLkey+LsigaLkey+Lsig in Xgroup
  • the same combinations in Ygroup
  • 3.2 Original MOVA Scheme versus Generalizations

    In the original paper on MOVA (Ref. [MV04a]) the signature protocol is described with characters instead of group homomorphisms. In such a case Ygroup is typically a very small group, e.g. {-1,+1} and Lkey is a medium-size integer. The above description generalizes to arbitrary group homomorphism and provide more freedom in the selection of Xgroup, Ygroup, and Hom.

    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

    with a and b secretly chosen at random, we can take the group Xgroup of invertible residues modulo n, and where j is a complex cubic root of 1. Given a and b we can define a character Hom from Xgroup to Ygroup. So the set up scheme is very efficient. (Unfortunately, the variant 3 of the set up scheme is not possible in this case.)

    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

    We concentrate on MOVA signatures which can be represented on 20 bits. We can prove the following security results.
    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

    (hence d = 2). The group homomorphism is the Legendre symbol defined by

    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

    (hence d = 3) computing an Eisenstein integer sigma such that, as a complex number, the squared module of sigma is equal to n, and using the homomorphism where (x/sigma)3 denotes a generalization of the Jacobi symbol of order 3. Number theory tells us that this is quite easy to implement when p and q are known but it is quite hard to compute Hom(x) in general without knowing sigma. It is further hard to compute sigma from n without its factorization.

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

    from random a and b and compute some sigma from a and b. For security reasons, n should be significantly larger than other n generated from prime numbers. This should be considered when comparing complexities.

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

    set up type d Lsig,Icon,Iden Lkey set up signature confirmation
    variant 122080 making 2 prime numbers 20 Legendre symbols 20 Legendre symbols,
    730 multiplications
    variant 222020 making 2 prime numbers 20 Legendre symbols 20 Legendre symbols,
    280 multiplications
    variant 32202 making 2 prime numbers 20 Legendre symbols 20 Legendre symbols,
    145 multiplications
    variant 131352 52* Jacobi3 symbols 13* Jacobi3 symbols 13* Jacobi3 symbols,
    489* multiplications
    variant 231313 13* Jacobi3 symbols 13* Jacobi3 symbols 13* Jacobi3 symbols,
    188* multiplications
    variant 33132 making 2 prime numbers 13 Jacobi3 symbols 13 Jacobi3 symbols,
    103 multiplications

    * with a larger modulus due to the special set up scheme
    The asymptotic complexity of Legendre symbols, multiplications, and Jacobi3 symbols are roughly quadratic in the size of the modulus n.

    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

    Note that we can precompute tables in order to speed up the computation of Hom. Without any precomputed table and in the worst case when d is prime, the complexity is roughly of 3.sqrt(d) multiplications. As an example, for d = 220+7, the complexity of Hom vary between no precomputed table and 3000 multiplications and a table of 3 MegaBytes and negligible computations. A rough estimate of the complexity analysis led to the following figures which all use signatures of 20 bits.
    set up type d Lsig,Icon,Iden Lkey set up signature confirmation
    variant 1220+714 making 2 prime numbers 1 Hom 1 Hom,
    65 multiplications
    variant 2220+711 making 2 prime numbers 1 Hom 1 Hom,
    35 multiplications
    variant 3220+711 making 2 prime numbers 1 Hom 1 Hom,
    35 multiplications
    Hence variant 3 is much faster than RSA signatures [RSA78].

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

    3.4 Main Characteristics

    As we previously detailed, the characteristic properties of our scheme is that Transmitting very short signature can be quite useful when transmitting at all is not easy. For instance human beings have some difficulties to transmit 100 bits by voice or by writing it on a paper but they can easily transmit 20 bits. Some technologies have low bandwidth such as (regular) bar code or SMS. Other technologies such as RFID tags do not have enough power to transmit too long messages. For all those cases we can easily imagine that transmitting a 20-bit signature is doable.

    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

    where H is a hash function, open is a random 80-bit string to disclose when opening the commitment, and val is the value to commit. Note that the prover does not have to reveal the yj to the verifier in the confirmation proof since the verifier should know them. The second message of the verifier can consist of a seed which was used to pseudorandomly generate the values in his first message. So only the first message of the verifier is a large one.

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

    The idea is that, in the first move, the verifier can additionally send the XOR between the seed he used to generate the random values and the hashed value of all yi. The signer who re-computes the yi can derive the seed and do the check as in the original third move. If it is correct, he can send the yi (or just simply a checksum of appropriate length, depending on the security level). So the protocol can be very light in terms of number of moves (but figures about computational costs in the confirmation protocol from the previous section may be multiplied by a factor of 4).

    In cases where the set up variant 3 is possible, we can easily convert an undeniable signature into a regular signature by expressing the Xmesj in terms of the Xkeyj. 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

    MOVA signatures are based on the link between three quantities.
    1. the the signer (represented by its public key),
    2. the message to be signed,
    3. the signature itself.
    In addition to the lack of visible link between the signature and the signer, there is no visible link between the signature and the message itself. Hence, if the three parts are given separately so that only a legitimate receiver can pool them together, nobody else can link the signature with anything else. In cases where the message represents a transaction, we cannot trace the agreement and the transaction 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

    In the long process of delivering goods (e.g. swiss watches) for export we can easily imagine that cases will carry a lot of unique digital information such as identification, serial number, travel plan with indicative schedule, carrier, etc. These information can be stored in a RFID tag or magnetic stripe. On the case itself can be written the MOVA signature of it e.g. hand-written or with a bar code. The custom can easily check if the provided information is sound, and can request a confirmation that the MOVA signature is correct to an on-line server. This can be very convenient for the server to trace the case.

    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

    In a special application where mobile delagates of a central server need to send orders with little communication facilities, we can imagine the following scenario. An agent (i.e. delegate) of some company is traveling and making transactions in the name of the company. He regularly synchronizes with his company, but need to send some kind of formal pre-agreement to the bank with no delay. One possibility is to append to the transaction a MOVA signature which can be transmitted by voice over the telephone, or by SMS. When receiving the order and the MOVA signature, the bank can ask the server of the company to confirm the signature. Later the delegate will forward the agreement to his company and the company will consider converting the MOVA signature into a regular one as for a final agreement. Agreements are in two steps: the instant undeniable delegate signature, and the final regular signature. One advantage is that the communication overhead for the delegate is very small. In addition to the digital order and a memo to his company, only a MOVA signature has to be communicated. Another advantage is in the resilience to a delegate key loss. When the delegate realizes that his signature key was lost, he can contact his company as soon as possible in order to prevent signatures to be confirmed. Here, liability in cases where the key was lost and a signature was issued and confirmed before a security alert has to be addressed by legal means.

    4.4 Electronic Payment

    MOVA signatures can be used to implement untraceable digital money. The idea is to have coins which consist of a unique identification number ID, a random number rand, and a MOVA signature on H( ID , rand ). Real coins can be converted into digital ones and vice versa at a bank for a value Vc. An online server can be used in order to check if a coin is valid or not. Since the server could be over used, or used in order to try to forge digital coins, the verification should be charged for some value Vi when the coin is not valid. An attacker who wants to forge a coin (of value Vc) must query a random number of unsuccessful trials with expected value (dLsig-1)/2 and variance (d2.Lsig-1)/12. For dLsig approximately equal to 220, the expected value is about 524'000 and the standard deviation is about 302'000. This means that the attacker has to pay Vi many times before forging a value of Vc. We can adjust Vc and Vi accordingly.

    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

    Provided that softwares are spread with unique characteristics (e.g. by obfuscation techniques), we can prove that a software is genuine with a MOVA signature. This signature can be checked on-line. Note that the MOVA signature and the software itself can be separate: the MOVA signature can be sent by an operator over the telephone upon reception of a payment. Confirming signature is nice for traitor tracing.

    5. References

    [CV90] Undeniable Signatures. By Chaum and van Antwerpen. In Advances in Cryptology CRYPTO'89, Santa-Barbara, USA, Lecture Notes in Computer Science, No. 435, pp. 212-216, Springer-Verlag, 1990.
    [IR90] A Classical Introduction to Modern Number Theory: Second Edition. By Ireland and Rosen. Graduate Texts in Mathematics vol. 84, Springer, 1990.
    [MV04a] Undeniable Signatures Based on Characters: how to Sign with One Bit. By Monnerat and Vaudenay. In Advances in Cryptology PKC'04, Singapore, Lecture Notes in Computer Science, No. 2947, pp. 69-85, Springer-Verlag, 2004.
    [RSA78] A Method for Obtaining Digital Signatures and Public-key Cryptosystem. By Rivest, Shamir and Adleman. In Communications of the ACM, vol. 21, pp. 120-126, 1978.
    LASEC http://lasec.epfl.ch/
    EPFL http://www.epfl.ch/

    © 2009, EPFL