The Ultimate Short Undeniable Signatures
by Jean Monnerat and Serge Vaudenay
Last update: May 17th, 2004.
Content
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, ecommerce, traceability of goods and non
traceable orders transmission.
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
 a key pair generation algorithm which produces the secret key and the
public key;
 a signature algorithm which takes a digital document and the secret
key and produces the signature;
 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;
 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.
 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 offline 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
offline, so this attack is not possible and the signature can
substantially be shrunk.
Since the verification must be performed online
the signer can detect that someone tries to forge a signature.
Here it is not unreasonable to talk about 40bit 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,
 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.
From this we can define the notation a+b+c, or ab, 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 a^{n}.
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(a
^{n})=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
a^{2}+b^{2}=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 cr 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 j
^{3}=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 j
^{2}.
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 i^{4}=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
IrelandRosen [IR90].
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
Parameters=[Lkey,Lsig,Icon,Iden]
and one of the following variants.
(In what follows we will use multiplicative notations for Xgroup and Ygroup.)
 The signer picks a random string seed and pseudorandomly generate
Xkey_{1}, ..., Xkey_{Lkey}
from seed.
He then computes
Ykey_{j} = Hom(Xkey_{j}) for j = 1, ..., Lkey.
 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.
 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
K_{p} =
(Xgroup,Ygroup,seed,Parameters,Ykey_{1},...,Ykey_{Lkey})
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
Ykey_{j} = Hom(Xkey_{j}) for j = 1, ..., Lkey.
We say that Hom
interpolates the set of points
{(Xkey_{1},Ykey_{1}),...,
(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
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
{(X_{1},Y_{1}),...,(X_{s},Y_{s})}
with X
_{j} taken from Xgroup and Y
_{j} 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
zeroknowledge.
The proof protocol between a
prover and a
verifier works as
follows.
 The verifier picks some random combination
x = r^{d} . X_{1}^{a1} ...
X_{s}^{as}
where r is taken from Xgroup and all a_{j} are taken from
{0, 1, ..., d1} and where d is the cardinality of Ygroup.
He then sends x to the prover.
 The prover computes y = Hom(x) and sends a commitment <y> to
the verifier.
 The verifier reveals r and all a_{j} to the prover.
 The prover checks that the verifier computed x well from the revealed
values and then opens <y> to the verifier.
 The verifier checks that y is consistent with the commitment <y> and
checks that
y = Y_{1}^{a1} ...
Y_{s}^{as}.
 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.
 The verifier picks some random combinations
x_{i} = r_{i}^{d} .
X_{1}^{ai,1} ...
X_{s}^{ai,s} for i = 1, ..., I
and sends them to the prover.
 The prover computes all y_{i} = Hom(x_{i}) and sends a
commitment
to the verifier.
 The verifier reveals all r_{i} and a_{i,j} to the prover.
 The prover checks that the verifier computed the x_{i} well from
the revealed values and then opens the commitment to the verifier.
 The verifier checks that all y_{i} are consistent with the
commitment and checks that
y_{i} = Y_{1}^{ai,1} ...
Y_{s}^{ai,s} for i = 1, ..., I.
2.3 Signature algorithm
In order to sign a digital document Message, the signer simply generates
pseudorandomly some Xmes
_{1}, ..., Xmes
_{Lsig} in Xgroup from
Message and computes
Ymes_{j} = Hom(Xmes_{j}) for j = 1, ..., Lsig.
The signature for Message is the sequence
Signature = (Ymes_{1},...,Ymes_{Lsig})
2.4 Confirmation protocol
The confirmation for the validity of a signature
Signature = (Ymes_{1},...,Ymes_{Lsig})
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
{(Xkey_{1},Ykey_{1}),...,
(Xkey_{Lkey},Ykey_{Lkey}),
(Xmes_{1},Ymes_{1}),...,
(Xmes_{Lsig},Ymes_{Lsig})}
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
Signature = (Zmes_{1},...,Zmes_{Lsig})
when he knows that the right signature for the message is
(Ymes_{1},...,Ymes_{Lsig}).
Both the signer and the verifier can compute
(Xmes_{1},...,Xmes_{Lsig})
from Message.
 The verifier picks some random
lambda_{1}, ..., lambda_{Iden}
in {0,1,...,p1} 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_{1}^{ai,1,k} ...
Xkey_{Lkey}^{ai,Lkey,k} .
Xmes_{k}^{lambdai}
z_{i,k} =
Ykey_{1}^{ai,1,k} ...
Ykey_{Lkey}^{ai,Lkey,k} .
Zmes_{k}^{lambdai}
for i = 1, ..., Iden and k = 1, ..., Lsig.
and send all x_{i,k} and z_{i,k} to the signer.
 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} )^{lambdai} the
signer can deduce all lambda_{i} for i = 1, ..., Iden.
He sends a commitment
<lambda_{1},...,lambda_{Iden}>
to all lambda_{i}.
 The verifier reveals all values.
 The signer checks that all values were well generated then open the
commitment <lambda_{1},...,lambda_{Iden}>.
 The verifier checks the commitment.
2.6 Proof of validity of K_{p}
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
x = r^{d} . X_{1}^{a1} ...
X_{Lkey}^{aLkey}
with unknown r, a
_{1}, ..., a
_{Lkey}.
We use an additional parameter Ival to be put in Parameters.
The interactive proof runs as follows.
 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.
 The verifier picks x_{i,2} in Xgroup at random
for i = 1, ..., Ival and sends them to the prover.
 The prover solves
x_{i,1} . x_{i,2} = r_{i}^{d} .
X_{1}^{ai,1} ...
X_{Lkey}^{ai,Lkey}
for i = 1, ..., Ival,
sends all r_{i} and a_{i,j} to the verifier and opens the
commitment.
 The verifier checks the commitment and the above equations.
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.
protocol  signer  verifier 
registration authority  note 
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 K_{p} 
solve Ival equations x =
r^{d} . X_{1}^{a1} ...
X_{Lkey}^{aLkey} 
Ival combinations
r^{d} .
x_{1}^{a1} ...
x_{Lkey}^{aLkey}
in Xgroup  
this protocol is used only for set up variant 3 
signature 
Lsig applications of Hom 
 

confirmation 
Icon applications of Hom
Icon combinations
r^{d} .
x_{1}^{a1} ...
x_{Lkey+Lsig}^{aLkey+Lsig}
in Xgroup

Icon combinations
r^{d} .
x_{1}^{a1} ...
x_{Lkey+Lsig}^{aLkey+Lsig}
in Xgroup
the same combinations in Ygroup



denial 
Iden.Lsig applications of Hom
Iden.Lsig combinations
r^{d} .
x_{1}^{a1} ...
x_{Lkey+Lsig}^{aLkey+Lsig}
in Xgroup

Iden.Lsig combinations
r^{d} .
x_{1}^{a1} ...
x_{Lkey+Lsig}^{aLkey+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 mediumsize 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
twolevel 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.

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

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.

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.

All interactive proof protocols are zeroknowledge: no malicious verifier can
extract some useful information out from the protocol.

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 p1 and q1 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 1  2  20  80 
making 2 prime numbers 
20 Legendre symbols 
20 Legendre symbols, 730 multiplications 
variant 2  2  20  20 
making 2 prime numbers 
20 Legendre symbols 
20 Legendre symbols, 280 multiplications 
variant 3  2  20  2 
making 2 prime numbers 
20 Legendre symbols 
20 Legendre symbols, 145 multiplications 
variant 1  3  13  52 
52* Jacobi_{3} symbols 
13* Jacobi_{3} symbols 
13* Jacobi_{3} symbols, 489* multiplications 
variant 2  3  13  13 
13* Jacobi_{3} symbols 
13* Jacobi_{3} symbols 
13* Jacobi_{3} symbols, 188* multiplications 
variant 3  3  13  2 
making 2 prime numbers 
13 Jacobi_{3} symbols 
13 Jacobi_{3} symbols, 103 multiplications 
* with a larger modulus due to the special set up scheme
The asymptotic complexity of Legendre symbols, multiplications, and
Jacobi
_{3} 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 q1 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.(q1).
We take a random kth 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 )
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 = 2
^{20}+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 1  2^{20}+7  1  4 
making 2 prime numbers 
1 Hom 
1 Hom, 65 multiplications 
variant 2  2^{20}+7  1  1 
making 2 prime numbers 
1 Hom 
1 Hom, 35 multiplications 
variant 3  2^{20}+7  1  1 
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
 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.
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 20bit 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 80bit string to disclose when
opening the commitment, and val is the value to commit.
Note that the prover does not have to reveal the y
_{j} 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 4move protocol, but
we can propose a 2move 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 y
_{i}.
The signer who recomputes the y
_{i} can derive the seed and do the
check as in the original third move.
If it is correct, he can send the y
_{i} (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
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 2level 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.1 Untraceable Transactions
MOVA signatures are based on the link between three quantities.
 the the signer (represented by its public key),
 the message to be signed,
 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. handwritten
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 online 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 4move (or 2move) 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 preagreement 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 (d
^{Lsig}1)/2 and variance
(d
^{2.Lsig}1)/12.
For d
^{Lsig} approximately equal to 2
^{20}, 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 online.
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.
[CV90] 
Undeniable Signatures.
By Chaum and van Antwerpen.
In Advances in Cryptology CRYPTO'89, SantaBarbara, USA,
Lecture Notes in Computer Science, No. 435, pp. 212216,
SpringerVerlag, 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. 6985,
SpringerVerlag, 2004. 
[RSA78] 
A Method for Obtaining Digital Signatures and Publickey
Cryptosystem.
By Rivest, Shamir and Adleman.
In Communications of the ACM, vol. 21, pp. 120126, 1978. 
LASEC 
http://lasec.epfl.ch/ 
EPFL 
http://www.epfl.ch/ 