On-line Non-transferable Signatures Revisited
Jacob C.N. Schuldt1, and Kanta Matsuura2
1

Research Center for Information Security, AIST, Japanjacob.schuldt@aist.go.jp
2
Institute of Industrial Science, The University of Tokyo, Japankanta@iis.u-tokyo.ac.jp

Abstract. Undeniable signatures, introduced by Chaum and van
Antwerpen, and designated conﬁrmer signatures, introduced by Chaum,allow a signer to control the veriﬁability of his signatures by requiring
a veriﬁer to interact with the signer to verify a signature. An important security requirement for these types of signature schemes is nontransferability which informally guarantees that even though a veriﬁer
has conﬁrmed the validity of a signature by interacting with the signer,
he cannot prove this knowledge to a third party. Recently Liskov andMicali pointed out that the commonly used notion of non-transferability
only guarantees security against an oﬀ-line attacker which cannot inﬂuence the veriﬁer while he interacts with the signer, and that almost all
previous schemes relying on interactive protocols are vulnerable to online attacks. To address this, Liskov and Micali formalized on-line nontransferable signatures which are resistant to on-line attacks, and proposed a generic construction based on a standard signature scheme andan encryption scheme. In this paper, we revisit on-line non-transferable
signatures. Firstly, we extend the security model of Liskov and Micali
to cover not only the sign protocol, but also the conﬁrm and disavow
protocols executed by the conﬁrmer. Our security model furthermore
considers the use of multiple (potentially corrupted or malicious) conﬁrmers, and guarantees security against attacks related to the use ofsigner speciﬁc conﬁrmer keys. We then present a new approach to theconstruction of on-line non-transferable signatures, and propose a newconcrete construction which is provably secure in the standard model.
Unlike the construction by Liskov and Micali, our construction does not
require the signer to issue “fake” signatures to maintain security, andallows the conﬁrmer to both conﬁrm and disavow signatures. Lastly, ourconstruction provides noticeably shorter signatures than the construction
by Liskov and Micali.
Keywords: signatures, on-line non-transferability, standard model.

1

Introduction

An ordinary signature scheme provides public veriﬁability i.e. anyone is able
to verify the validity of a given signature using the public key of the signer.


The full version of this paper is available at http://eprint.iacr.org/2009/406
This author is supported by a JSPS scholarship.

D. Catalano et al. (Eds.): PKC 2011, LNCS 6571, pp. 369–386, 2011.
c International Association for Cryptologic Research 2011
370

J.C.N. Schuldt and K. Matsuura

While this property is useful in many scenarios, it might not always be desirable.
For example, a signer who signs a sensitive message might prefer to be able tocontrol who can verify the validity of his signature. Chaum et al. [5] addressed
this problem with their proposal of undeniable signatures in which a veriﬁer
is required to interact with the signer to verify a signature. Furthermore, topreserve non-repudiation, the signer is also able to prove invalidity of a signature
through a disavow protocol. Hence, in a dispute, the signer will either be able
to conﬁrm or disavow a purported signature. However, in some scenarios, asigner might become unavailable or might refuse to cooperate with a veriﬁer, inwhich case the validity of a signature cannot be determined. To address this,Chaum [4] introduced designated conﬁrmer signatures in which a third party,
the conﬁrmer, can interact with a veriﬁer to conﬁrm or disavow a signature on
behalf of the signer. Furthermore, the conﬁrmer can, in the case of a dispute,
extract a publicly veriﬁable signature (of the signer) from a valid designatedconﬁrmer signature. Since their introduction, a number of undeniable schemes
and designated conﬁrmer schemes have been proposed, e.g. see [3,7,12,14,2,8].
Oﬀ-line and On-line Non-transferability. An important security notion for thesetypes of signature schemes is non-transferability. Intuitively, non-transferability
guarantees that once a veriﬁer has veriﬁed a signature and is convinced about
its validity, he cannot transfer this conviction to a third party. This is achievedby ensuring that a veriﬁer is able to simulate a transcript of the interaction withthe signer/conﬁrmer i.e. any “evidence” of validity obtained through the interaction, could have been generated by the veriﬁer himself. A scheme providing
this property is said to be oﬀ-line non-transferable. However, Liskov and Micali[13] pointed out that almost all1 previous schemes relying on interactive protocols to provide oﬀ-line non-transferability are vulnerable to on-line attacks, i.e.
an attacker who is present while the veriﬁer interacts with a signer/conﬁrmer
might be able to determine the validity of a signature by inﬂuencing messages
sent by the veriﬁer. A scheme preventing these types of attacks is said to be online non-transferable and is constructed by enabling the veriﬁer to interactively
simulate the interaction with a signer/conﬁrmer. To preserve soundness of thescheme, only the veriﬁer should be able to simulate a proof, and to facilitate
this, Liskov and Micali [13] assumed the veriﬁer holds a public/private key pairi.e. to simulate the interaction between the signer/conﬁrmer and a veriﬁer, theprivate key of the veriﬁer is required. Note that this approach to on-line nontransferability requires that the veriﬁer knows the private key corresponding to
his public key to maintain security. More speciﬁcally, if it is possible for a veriﬁer
to convince a third party that he does not know his private key (e.g. by generating his public key by applying a hash function to a random seed pkV = H(x),and then presenting x to the third party), the scheme will no longer provide online non-transferability. To prevent this type of malicious behavior, veriﬁer key
registration is required i.e. a veriﬁer should prove knowledge of his private key
when registering his public key (see [13] for further discussion of this). In this1

See Related Work below for a few exceptions in the random oracle model.

On-line Non-transferable Signatures Revisited371

paper, we adopt the same general approach as [13], assume veriﬁers are equippedwith public/private key pairs, and will furthermore explicitly model veriﬁer key
registration in our security model2 .
In [13], Liskov and Micali illustrated the feasibility of constructing an online non-transferable signature scheme under the above described assumption of
veriﬁer key registration. More speciﬁcally, they proposed a generic construction
based on ind-cpa secure public key encryption and uf-cma secure signatures.
The resulting scheme provides on-line non-transferability of an interactive sign
protocol through which the signer both constructs and proves validity of a signature. Furthermore, the scheme supports the use of conﬁrmers and is proved
secure in the standard model. However, to achieve on-line non-transferability, asigner has to be willing to issue “fake” signatures to anyone requesting them.
This is essential since a veriﬁer will not be able to simulate the sign protocol
without the ability to ask the signer for fake signatures. This drawback limits thepractical applicability of the scheme. Furthermore, the functionality and security
guarantees of the conﬁrmer are somewhat limited. More speciﬁcally, a conﬁrmer
can disavow but not conﬁrm the validity of a signature, and neither oﬀ-line nor
on-line non-transferability are considered for the disavow protocol3 .
Our Contribution. In this paper, we address many of the limitations of the approach by Liskov and Micali. Firstly, we extend the security model to model not
only the on-line non-transferability of the sign protocol, but also of the conﬁrm
and disavow protocols executed by the conﬁrmer. Furthermore, we introduce
two additional security notions, conﬁrmer soundness and key unforgeability, required by the added ability of the conﬁrmer to conﬁrm signatures and to prevent
attacks related to the forgery of signer speciﬁc conﬁrmer keys which are usedboth in our construction and in [13] (see Section 3 for details). Unlike [13], oursecurity model also allows the signer to make use of multiple conﬁrmers andensures unforgeability even against malicious conﬁrmers, which will guarantee
security in a more realistic usage scenario.
We then propose a new general approach to the construction of on-line nontransferable signatures. More speciﬁcally, we show how a simple core conﬁrmer
signature scheme, which essentially implements the non-interactive functionality of an on-line non-transferable signature scheme, can be extended to a fully
secure scheme with the additional use of ordinary signatures, sigma protocols,
and trapdoor commitments with an enhanced binding property. Based on thisapproach, we propose a concrete instantiation which is provably secure in thestandard model assuming the computational Diﬃe-Hellman problem and thedecisional linear problem are hard.
Compared to the approach taken by Liskov and Micali, our scheme has several advantages. Besides implementing additional conﬁrmer functionality and2Note that while the security deﬁnitions in [13] does not explicitly describe veriﬁer
key registration, this is a requirement to ensure basic security, and we argue that
our security models are fundamentally the same.
3
The deﬁned disavow protocol in [13] is non-interactive and provides a publicly
veriﬁable proof of invalidity.

372

J.C.N. Schuldt and K. Matsuura

providing security in our extended security model, our scheme allows a veriﬁer
to independently simulate the sign, conﬁrm and disavow protocols, and does not
require the signer to issue “fake” signatures to maintain security. Lastly, ourconcrete instantiation provides eﬃcient protocols and short signatures consisting of four group elements and an integer, whereas the scheme by Liskov andMicali requires signatures consisting of more than 3k encryptions, where k is the
security parameter. However, we note that our concrete scheme requires large
public keys due to the use of the techniques by Waters [19].
Related Work. Jakobsson et al. [10] introduced an alternative approach to limiting the veriﬁability of signatures with their proposal of designated veriﬁer signatures in which only a speciﬁc veriﬁer chosen by the signer will be convinced
about the validity of a signature. This concept was extended by Steinfeld etal. [17] who introduced universal designated veriﬁer signatures which allow any
user to convert a publicly veriﬁable signature into a designated veriﬁer signature for a chosen veriﬁer. Since this type of schemes do not rely on interactive
protocols for signature conﬁrmation, on-line attacks are not a concern. However,these schemes do not provide a mechanism to determine the validity of a (converted) signature in a dispute, and most of the recently proposed schemes willin fact enable the designated veriﬁer to construct signatures which are perfectly
indistinguishable from signatures constructed by the signer. Hence, unlike undeniable and designated conﬁrmer signatures, non-repudiation cannot be enforcedin these schemes which make them unsuitable for a number of applications.
A few existing schemes, which are provably secure in the random oracle model,
implicitly provide protection against on-line attacks. For example, the undeniable signature schemes by Kudla et al. [11] and Huang et al. [9] provide noninteractive proofs which are simulatable by the veriﬁer, and hence avoid the
problem of on-line attacks. Furthermore, Monnerat et al. [15] proposed an undeniable signature scheme with interactive 2-move conﬁrm and disavow protocols.
While the used deﬁnition of non-transferability in [15] only guarantees transcript
simulatability (i.e. deﬁnes oﬀ-line non-transferability), the concrete scheme allows a veriﬁer to use his private key to simulate proofs interactively, and hence
the scheme provides on-line non-transferability. However, we emphasize that allof the above schemes are only provable secure in the random oracle model, andthat the schemes furthermore do not support the use of conﬁrmers to ensure
non-repudiation if the signer becomes oﬀ-line or refuses to cooperate.

2

On-line Non-transferable Signatures

An on-line non-transferable signature (ONS) scheme involves a signer S, a conﬁrmer C, and a veriﬁer V , and is given by the following probabilistic polynomial
time (PPT) algorithms:– Setup which, given a security parameter 1k , returns the public parameterspar.

On-line Non-transferable Signatures Revisited373– KeyGenS , KeyGenC , and KeyGenV which, given par, return public/private
key pairs (pkS , skS ), (pkC , skC ), and (pkV , skV ) for a signer, a conﬁrmer,
and a veriﬁer, respectively.
– CSetup which on input par, skC and pkS , returns a signer speciﬁc public/private conﬁrmer key pair (pkC,S , skC,S ). This algorithm is run once by
the conﬁrmer for each signer S, and the conﬁrmer stores skC,S for later
use. The public key pkC,S is given to the signer who is to use this whenconstructing signatures with conﬁrmer C.
– CKeyValid which, on input par, pkS , pkC , and pkC,S , outputs either accept
or reject.
– (Sign, Receive) which is a pair of interactive algorithms with common input (par, pkS , pkC , pkC,S , pkV , m). Sign is run by the signer and is given skS
as private input, and Receive is run by the veriﬁer. At the end of the interaction, both Sign and Receive will output a signature, σS and σR , andReceive will in addition output either accept or reject.
– Convert which, on input par, pkS , m, σ, and skC,S , returns a veriﬁcation
token tkσ .
– TkVerify which, on input par, pkS , pkC , pkC,S , m, σ, and tkσ , returns either
accept or reject.
– (Confirm, VC ) which is a pair of interactive algorithms with common input (par, pkS , pkC , pkC,S , pkV , m, σ). Confirm is run by the conﬁrmer and isgiven skC,S as private input, and VC is run by the veriﬁer. At the end of theinteraction, VC outputs either accept or reject.
– (Disavow, VD ) which is also a pair of interactive algorithms. Input for Disavow
and VD is exactly as in (Confirm, VC ) above, and the output of VD is either
accept or reject.
Like Liskov and Micali [13], we require that before signer S makes use of a
conﬁrmer C, he will approach C to obtain a signer speciﬁc conﬁrmer key pkC,Swhich C generates by running CSetup. This process can be seen as a registration
procedure in which the conﬁrmer agrees to act as a conﬁrmer for this speciﬁcsigner. Note that this does not require a conﬁdential channel between the signerand conﬁrmer. Our deﬁnition diﬀers slightly from that of [13] in that we explicitly
deﬁne a key validation algorithm CKeyValid for signer speciﬁc conﬁrmer keys4 ,and introduce (Confirm, VC ) to allow C to conﬁrm signatures. Furthermore, we
do not include a fake signature algorithm which is required to maintain the
security of the scheme in [13].
Using the above deﬁned algorithms, a conﬁrmer can verify a signature byﬁrst computing a veriﬁcation token using Convert and then verifying the signature using TkVerify. To simplify notation, we deﬁne an algorithm Valid which
performs these two steps:– Valid: given the input (par, pkS , pkC , pkC,S , m, σ, skC,S ), compute the veriﬁcation token tkσ ← Convert(par, pkS , m, σ, skC,S ) and return the output
of TkVerify(par, pkS , pkC , pkC,S , m, σ, tkσ ).
4This algorithm is required by our extended security model. More speciﬁcally, it isrequired to deﬁne key unforgeability (see Section 3).

374

J.C.N. Schuldt and K. Matsuura

We will use the notation {Sign(skS ) ↔ Receive}(par, pkS , pkC , pkC,S , pkV , m)
to denote the interaction between Sign and Receive on the common input(par, pkS , pkC , pkC,S , pkV , m) and private input skS to the Sign algorithm. To
shorten this notation, we will sometimes use P K = (pkS , pkC , pkC,S , pkV ) torepresent the public keys. We furthermore use (σS , (σR , z)) ← {Sign(skS ) ↔
Receive}(par, P K, m) to denote the output of Sign and Receive, respectively,
and use (σR , z) ←2 {Sign(skS ) ↔ Receive}(par, P K, m) when we are only
considering the output of Receive. Similar notation is used for the conﬁrm anddisavow protocols.
Correctness. We require that for all honestly generated public parameters par
and key pairs (pkS , skC ), (pkC , skC ), (pkV , skV ), and (pkC,S , skC,S ), that z ←CKeyValid(par, pkC , pkS , pkC,S ) yields z = accept and that, for all messages m,
the signature generation (σS , (σR , zR )) ← {Sign(skS ) ↔ Receive}(par, P K, m),where P K ← (pkS , pkC , pkC,S , pkV ), yields that zR = accept and σR = σS , that
Valid(par, pkS , pkC , pkC,S , skC,S , m, σ) = true and that zC ← {Confirm(skC,S )↔ VC }(par, P K, m, σ) results in zC = accept. Furthermore, for all (m , σ  )such that Valid(par, pkS , pkC , pkC,S , skC,S , m , σ  ) = false, we require thatzD ←2 {Disavow(skC,S ) ↔ VD }(par, P K, m , σ  ) yields zD = accept.

3

Security Model

An ONS scheme is required to satisfy the security notions unforgeability, key unforgeability, soundness, non-repudiation and non-transferability to be consideredsecure. However, before we can formally deﬁne these security notions, we requirea scheme to deﬁne the veriﬁer simulation algorithms SimSign(par, P K, m, skV ),SimCon(par, P K, m, σ, skV ) and SimDis(par, P K, m, σ, skV ) which simulates theSign, Confirm and Disavow algorithms, respectively. While these algorithms are
not part of the basic functionality of an ONS scheme, they must be deﬁned to ensure that a veriﬁer can simulate the interactive protocols of the scheme as requiredby the non-transferability notion deﬁned below. Furthermore, since an adversary
might observe the execution of these algorithms while attempting to mount attacks against other security properties of the scheme, we must provide the adversary with oracle access to these algorithms in the relevant security deﬁnitions.
Unforgeability. Our notion of unforgeability requires that, even for a maliciouslychosen conﬁrmer key, an adversary with oracle access to an honest signer cannot
produce a new message/signature pair and convince a veriﬁer about the validityof this pair, either by interacting with the veriﬁer in the conﬁrm protocol or by
producing a token such that TkVerify outputs accept. Our deﬁnition allows
the adversary to obtain signatures using any conﬁrmer key, and thereby ensures
security in a scenario where a signer makes use of multiple potentially malicious conﬁrmers. In comparison, the unforgeability notion deﬁned by Liskov andMicali only considers a signer using a single honest conﬁrmer. Formally, we deshown in
ﬁne unforgeability of an ONS scheme N via the experiment Expuf-cma
N,AFigure 1. In the experiment, A has access to the oracles O = {OV KeyReg , OSign ,On-line Non-transferable Signatures Revisited

375

OSimSign , OSimCon , OSimDis } which are deﬁned below. The oracle OV KeyReg
implements veriﬁer key registration and maintains a list, LV KeyReg , of registered keys. It is assumed that it can be veriﬁed that a key pair (pkV , skV ) is
valid i.e. that (pkV , skV ) lies in the range of KeyGenV .
– OV KeyReg : given (pkV , skV ), this oracle stores (pkV , skV ) in the list LV KeyReg
and returns  to A if (pkV , skV ) is a valid key pair. Otherwise, the oracle
returns ⊥ to A. In the following, if a query to an oracle involves a veriﬁer
key pkV , it is assumed that A has previously submitted pkV to this oracle
as part of a valid key pair. If this is not the case, the relevant oracle will
return ⊥ to A.
– OSign : given input (pkC , pkC,S , pkV , m), this oracle interacts with A by running Sign with common input (par, pkS , pkC , pkC,S , pkV , m) and secret input
skS . Local output of Sign will be a signature σ, and (pkC , pkC,S , m, σ) is
added to LSign .
– OSimSign : given input pkS , pkC , pkC,S , and m, this oracle interact with A
by running the simulation algorithm SimSign(par, pkS , pkC , pkC,S , m, skV ).
– OSimCon : given input pkS , pkC , pkC,S , m and σ, this oracle interacts with
A by running the algorithm SimCon(par, pkS , pkC , pkC,S , pkV , m, σ, skV ).
– OSimDis : given the same input as OSimCon , this oracle interacts with A byrunning the algorithm SimDis(par, pkS , pkC , pkC,S , pkV , m, σ, skV ).
Definition 1. An ONS scheme N is said to be unforgeable, if no PPT algorithm
uf-cma k
A with non-negligible advantage Advuf-cma
N,A (k) = Pr[ExpN,A (1 ) = 1] exists.
Key unforgeability. The use of the conﬁrmer setup, CSetup, warrants additional
security requirements. Key unforgeability requires that an adversary without
access to the private conﬁrmer key, cannot produce a new valid signer speciﬁc
conﬁrmer key i.e. a new key which is accepted by CKeyValid. The security
model in [13] does not have a similar security requirement and does in fact
not rule out the possibility that a signer is able to forge a signer speciﬁc conﬁrmer key and then use this forged key in the sign protocol. This would leave
the conﬁrmer unable to either conﬁrm, disavow or convert the signature. However, such concerns are eliminated by explicitly requiring key unforgeability.
Formally, key unforgeability of an ONS scheme N is deﬁned via the experiment
key-uf
ExpN,A (1k ) shown in Figure 1. In the experiment, A has access to the oracles
O = {OV KeyReg , OCSetup , OConvert , OCon , ODis } where OV KeyReg is deﬁned asabove, and the remaining oracles are deﬁned as follows:– OCSetup : given pkS , this oracle runs (pkC,S , skC,S ) ← CSetup(par, pkS , skC ),stores (pkS , pkC,S , skC,S ) in LCSetup , and returns pkC,S to A.
– OConvert : given pkS , pkC,S , m, and σ, this oracle searches for a matchingtuple (pkS , pkC,S , skC,S ) in LCSetup , and returns ⊥ if no such tuple is found.
Otherwise, the oracle returns tkσ ← Convert(par, pkS , m, σ, skC,S ).
– OCon : given pkS , pkC,S , pkV , m, and σ, the oracle searches for a tuple(pkS , pkC,S , skC,S ) in LCSetup . If no such tuple is found the oracle returns⊥. Otherwise, the oracle interacts with A by running Confirm with common
input (par, pkS , pkC , pkC,S , pkV , m, σ) and secret input skC,S .

376

J.C.N. Schuldt and K. MatsuurakExpuf-cma
S,A (1 )LSign ← {}; LV KeyReg ← {}kExpkey-uf
par ← Setup(1k )S,A (1 )LCSetup ← {}; LV KeyReg ← {}(pkS , skS ) ← KeyGenS (par)(pkV , skV ) ← KeyGenV (par)par ← Setup(1k )(pkC , pkC,S , m, σ, tkσ , st)(pkC , skC ) ← KeyGenS (par)← AO (par, pkS , pkV )(pkS , pkC,S ) ← AO (par, pkC )P K ← (pkS , pkC , pkC,S , pkV )z ← CKeyValid(par, pkS , pkC , pkC,S )z ←2 {AO (st) ↔ VC (par, P K, m, σ)}if (pkS , pkC,S , ∗) ∈ LCSetup ∧z  ← TkVer(par, pkS , pkC , pkC,S , m, σ, tkσ )z = true
output 1
if (pkC , pkC,S , m, σ) ∈ LSign ∧(z = accept ∨ z  = accept)
else output 0
output 1
else output 0(1k )Expnon-rep
S,Apar ← Setup(1k )(pkV , skV ) ← KeyGenV (par)(pkS , pkC , pkC,S , m, st) ← AO (par, pkV )P K ← (pkS , pkC , pkC,S , pkV )(st , (σ, z1 )) ← {AO (st) ↔ Receive(par, P K, m)}z2 ←2 {AO (st ) ↔ VD (par, P K, m, σ)}if z1 = z2 = accept output 1
else output 0

Fig. 1. Unforgeability, key unforgeability and non-repudiation security experiments– ODis : given the same input as OCon , this oracle returns ⊥ to A if there isno tuple (pkS , pkC,S , skC,S ) in LCSetup . Otherwise, the oracle interacts with
A by running Disavow with common input (par, pkS , pkC , pkC,S , pkV , m, σ)and secret input skC,S .
Definition 2. An ONS scheme N is said to be key unforgeable if no PPT
key-uf k
algorithm A with non-negligible advantage Advkey-uf
N,A (k) = Pr[ExpN,A (1 ) = 1]
exists.
Non-repudiation. Informally, non-repudiation requires that, even if a malicious
signer and conﬁrmer collude, it is not possible for the signer to make an honest veriﬁer accept a message/signature pair as valid in the sign protocol, while
the conﬁrmer is able to disavow the validity of the message/signature pair. Ourdeﬁnition of non-repudiation is slightly weaker than the deﬁnition given in [13]in that we allow the adversary a negligible success probability whereas [13] requires the success probability to be zero. However, we highlight that [13] makes
use of a non-interactive disavow protocol which is both oﬀ-line and on-line transferable which allows the slightly stronger non-repudiation property, whereas ourconstructions will rely on interactive non-transferable protocols with negligible
soundness error. We deﬁne non-repudiation of an ONS scheme N via the exper(1k ) shown in Figure 1. In the experiment, A has access to theiment Expnon-rep
N,Aoracles O = {OSimSign , OSimCon , OSimDis } which are deﬁned as above.

On-line Non-transferable Signatures Revisited

377

(1k )
Expsnd-sign
N,Apar ← Setup(1k ); (pkC , skC ) ← KeyGenC (par)(pkV , skV ) ← KeyGenV (par)(pkS , m, st) ← AO (par, pkC , skC , pkV )(pkC,S , skC,S ) ← CSetup(par, pkS , skC )P K ← (pkS , pkC , pkC,S , pkV )(σ, z1 ) ←2 {AO (st, pkC,S , skC,S ) ↔ Receive(par, P K, m)}z2 ← Valid(par, pkS , pkC , pkC,S , m, σ, skC,S )if z1 = accept ∧ z2 = reject output 1
else output 0(1k )Expsnd-confN,Apar ← Setup(1k ); (pkV , skV ) ← KeyGenV (par)(pkS , pkC , pkC,S , m, σ, tkσ , st) ← AO (par, pkV )P K ← (pkS , pkC , pkC,S , pkV )z1 ←2 {AO (st) ↔ VD (par, P K, m, σ)}z2 ←2 {AO (st) ↔ VC (par, P K, m, σ)}z3 ← TkVerify(par, pkS , pkC , pkC,S , m, σ, tkσ )if z1 = accept ∧ (z2 = accept ∨ z3 = accept) output 1
else output 0
Fig. 2. Soundness security experiments

Definition 3. An ONS scheme N is said to provide non-repudiation if no PPT
non-rep
non-rep
algorithm A with non-negligible advantage AdvN,A (k) = Pr[ExpN,A (1k ) = 1]
exists.
Soundness. We consider two soundness notions – signer soundness and conﬁrmer
soundness. The ﬁrst notion, signer soundness, guarantees that a signer cannot
make a veriﬁer accept a message/signature pair as valid through the sign protocol
without the conﬁrmer being able to conﬁrm the validity of this pair as well as
compute a veriﬁcation token showing validity. Our deﬁnition guarantees signer
soundness even if the conﬁrmer is corrupted since the adversary is allowed toaccess the private conﬁrmer key, and implies the soundness notion by Liskov
and Micali which only grants the adversary access to the public conﬁrmer key.
Formally, we deﬁne signer soundness of an ONS scheme N via the experimentsnd-sign
ExpN,A (1k ) shown in Figure 2. In the experiment, A will have access to theoracles O = {OSimSign , OSimCon , OSimDis } deﬁned as above.
Definition 4. An ONS scheme N is said to provide signer soundness if no PPT(k) = Pr[Expsnd-sign(1k ) =
algorithm A with non-negligible advantage Advsnd-sign
N,A
N,A
1] exists.
The second notion, conﬁrmer soundness, guarantees that even if both signer andconﬁrmer key is maliciously generated, a conﬁrmer cannot produce a message/
signature pair which he can successfully disavow by completing the disavow protocol, while still being able to conﬁrm validity of this pair, either by completingthe conﬁrm protocol or by producing a token that will make TkVerify output
accept. Since Liskov and Micali do not consider the conﬁrmer’s ability to conﬁrm

378

J.C.N. Schuldt and K. Matsuura

a signature, an equivalent security notion is not deﬁned in [13]. We deﬁne conﬁrmer soundness of an ONS scheme N via the experiment Expsnd-conf(1k ) shown
N,A
in Figure 2. In the experiment, A has access to the oracles O = {OSimSign ,OSimCon , OSimDis } deﬁned as above.
Definition 5. An ONS scheme is said to provide conﬁrmer soundness if nosnd-conf
snd-conf
PPT algorithm A with non-negligible advantage AdvN,A (k) = Pr[ExpN,A(1k ) = 1] exists.
On-line Non-transferability. Intuitively, on-line non-transferability of a protocol
requires that an adversary cannot distinguish between a real execution of the
protocol and a simulated execution by the veriﬁer. Note that since we are considering the on-line non-transferability of both the sign, conﬁrm and disavow
protocols, a veriﬁer must be able to provide a consistent response, even if theadversary ﬁrst obtains a signature through the (simulated) sign protocol andlater try to re-conﬁrm the validity through the (simulated) conﬁrm protocol. We
deﬁne a single non-transferability notion covering the non-transferability of all
three interactive protocols. More speciﬁcally, we require that an adversary cannot distinguish between a scenario in which he obtains a valid signature throughthe sign protocol, conﬁrms the validity through the conﬁrm protocol, and theninteracts in the simulated disavow protocol, and a scenario in which he obtains
a signature through the simulated sign protocol, conﬁrms the validity throughthe simulated conﬁrm protocol, and then interacts in the disavow protocol. Our
non-transferability notion implies a similar type of non-transferability of the sign
protocol as deﬁned by Liskov and Micali, but does not involve fake signature
generation. Formally, we deﬁne on-line non-transferability of a ONS scheme N(1k ) shown in Figure 3. In the experiment, A has
via the experiment Expnon-transN,A
Expnon-trans
(1k )
N,A
LV KeyReg ← {}; par ← Setup(1k ); (pkS , skS ) ← KeyGenS (par)(pkC , skC ) ← KeyGenC (par); (pkC,S , skC,S ) ← CSetup(par, pkS , skC )(pkV , skV ) ← KeyGenV (par); P K ← (pkS , pkC , pkC,S , pkV )(m, st) ← AO (par, P K, skV )b ← {0, 1}
if b = 0(σ, st ) ← {Sign(par, P K, m, skS ) ↔ A(st)}st ←2 {Confirm(par, P K, m, σ ∗ , skC,S ) ↔ A(st )}st ←2 {SimDis(par, P K, m, σ, skV ) ↔ A(st )}else (b = 1)(σ ∗ , st ) ← {SimSign(par, P K, m, skV ) ↔ A(st)}st ←2 {SimCon(par, P K, m, σ, skV ) ↔ A(st )}st ←2 {Disavow(par, P K, m, σ, skC,S ) ↔ A(st )}b ← AO (st )if b = b output 1
else output 0
Fig. 3. On-line non-transferability security experimentOn-line Non-transferable Signatures Revisited379

access to the oracles O = {OV KeyReg , OCSetup , OSign , OConvert , OCon , ODis } deﬁned as in the unforgeability and the key unforgeability experiments. The oraclesO are deﬁned exactly as O, except that OConvert will not respond to the query
consisting of the challenge (pkS , pkC,S ), m∗ and σ ∗ , and OCon and ODis will
not respond to queries on the challenge (pkS , pkC,S ), m∗ , σ ∗ and any pkV . Notethat OSign allows the adversary to obtain signatures under any conﬁrmer key,
and that OConvert , OCon and ODis accepts any signer key. This ensures security
in a scenario where multiple conﬁrmers service multiple signers. Note also thatthe adversary is given the private key of the veriﬁer. This will ensure that even
if the veriﬁer is compromised, the non-transferability is still maintained.
Definition 6. An ONS scheme N is said to be on-line non-transferable if no(k) = | Pr[Expnon-trans
PPT algorithm A with non-negligible advantage Advnon-trans
N,AN,A(1k ) = 1] − 12 | exits .

4Construction of an ONS Scheme

In this section we will present a construction of an ONS scheme based on four
simpler building blocks: a standard signature scheme, a core conﬁrmer signaturescheme, sigma protocols, and a trapdoor commitment scheme with an enhanced
binding property. In the following, we will formally deﬁne a core conﬁrmer signature scheme as well as the needed security requirements, motivate and deﬁne
the enhanced binding property of a trapdoor commitment scheme, and ﬁnallyshow how the above mentioned primitives can be combined into a secure ONS
scheme. Formal deﬁnitions of standard signatures, sigma protocols and trapdoor
commitments can be found in the full version.
4.1

Core Confirmer Signature Scheme

A core conﬁrmer signature scheme is essentially an ONS scheme without any of
the interactive algorithms. More speciﬁcally, a core conﬁrmer signature scheme
is deﬁned by CS = {CS.Setup, CS.KeyGenS , CS.KeyGenC , CS.Sign, CS.Convert,
CS.TkVerify} where the algorithms CS.Setup, CS.KeyGenS , and CS.KeyGenC aredeﬁned as in a full ONS scheme, and the CS.Sign, CS.Convert and CS.TkVerify
algorithms are deﬁned as follows:– CS.Sign: given par, pkC , m, and skS , this algorithm returns a signature σ.
– CS.Convert: given par, pkS , m, σ and skC , this algorithm returns a veriﬁcation token tkσ .
– CS.TkVerify: given par, pkS , pkC , m, σ and tkσ , this algorithm returns
either accept or reject.
Both CS.Convert and CS.TkVerify are assumed to be deterministic. Note that
all algorithms are non-interactive and that no speciﬁc conﬁrmer keys pkC,S or
veriﬁer keys pkV are required. Like for an ONS scheme, we deﬁne an algorithm
CS.Valid as

380

J.C.N. Schuldt and K. Matsuura– CS.Valid: given par, pkS , pkC , m, σ and skC , this algorithms computes theveriﬁcation token tkσ ← CS.Convert(par, pkS , m, σ, skC ) and returns theoutput of CS.TkVerify(par, pkS , pkC , m, σ, tkσ ).
We require that a scheme is correct i.e. for all par ← CS.Setup(1k ), (pkS , skS ) ←CS.KeyGenS (par), (pkC , skC ) ← CS.KeyGenV (par), all messages m and all σ ←CS.Sign(par, pkC , m, skS ), we require that z ← CS.Valid(par, pkS , pkC , m, σ, skC )yields z = accept. Furthermore, we require that a core conﬁrmer signaturescheme has unique private conﬁrmer keys i.e. for any pkC , there exists at mostone skC such that (pkC , skC ) ∈ {CS.KeyGenC (par)} where {CS.KeyGenC (par)}denotes the set of all possible conﬁrmer key pairs generated by CS.KeyGenC 5 .
Security Requirements. For a core conﬁrmer signature scheme to be secure, we
require that the scheme provides unforgeability, invisibility and token soundness.
However, due to the reduced functionality of a core conﬁrmer signature scheme,
these deﬁnitions will be much simpler compared to the security deﬁnitions of afull ONS scheme.
We deﬁne unforgeability of a core conﬁrmer signature scheme CS via the(1k ) shown in Figure 4. In the experiment, A has accessexperiment Expcs-uf-cma
CS,A
to the oracle OSign deﬁned as follows:– OSign : given pkC , and m, this oracle computes σ ← CS.Sign(par, pkC , m, skS ),adds (pkC , m, σ) to LCSSign , and returns σ.
Definition 7. A core conﬁrmer signature scheme CS is said to be unforgecs-uf-cma
able if no PPT algorithm A with non-negligible advantage AdvCS,A (k) =cs-uf-cma k
Pr[ExpCS,A (1 ) = 1] exists.
Invisibility of a core conﬁrmer signature scheme CS, which captures the property that valid signatures cannot be distinguished from random elements of thesignature space, is deﬁned via the experiment Expcs-inv-cma
shown in Figure 4. In
CS,A
the experiment, S denotes the signature space of the scheme, and A has accessto the oracles O = {OSign , OConvert } where OSign is deﬁned as in the above
unforgeability experiment, and OConvert is deﬁned as follows:– OConvert : given m and σ, this oracle returns the veriﬁcation token tkσ ←CS.Convert(par, pkS , pkC , m, σ, skC ).
Note that OConvert will only convert signatures from the signer pkS and is not
required to work for maliciously generated public signer keys for which the adversary might know the corresponding private key. Hence, intuitively, this security
requirement only requires the scheme to be secure in a “single user” settingin which a conﬁrmer only services a single signer. This weaker requirement isimportant for the security proof of our concrete construction.
Definition 8. A core conﬁrmer signature scheme CS is said to be invisible if(k) =there exists no PPT algorithm A with non-negligible advantage Advcs-inv-cma
CS,A
1
k
(1
)
=
1]
−
|
exists.
| Pr[Expcs-inv-cma
CS,A
2
5

This property is needed to prove conﬁrmer soundness (Theorem 15) of theconstruction presented in Section 4.3.

On-line Non-transferable Signatures Revisited

381

(1k )
Expcs-inv-cma
CS,Apar ← CS.Setup(1k )LCSSign ← {}(pkS , skS ) ← CS.KeyGenS (par)(pkC , skC ) ← CS.KeyGenC (par)par ← CS.Setup(1k )(pkS , skS ) ← CS.KeyGenS (par)(m∗ , st) ← AO (par, pkS , pkC )
∗
∗
∗
∗
O
b ← {0, 1}(pkC , m , σ , tkσ ) ← A (par, pkS )∗if b = 0 σ ∗ ← S, σ ∗ , m∗ , tkσ∗ )z ← CS.TkVerify(par, pkS , pkC∗
else σ ∗ ← CS.Sign(par, pkC , m, skS ), m∗ , σ ∗ ) ∈ LCSSign ∧ z = accept
if (pkC
output 1b ← AO (st, σ ∗ )if b = b output 1
else output 0
else output 0(1k )Expcs-tk-snd
CS,Apar ← CS.Setup(1k )
∗
∗
, skC
, m∗ , σ ∗ , tkσ∗ ) ← A(par)(pkS∗ , pkC∗, σ ∗ , m∗ , tkσ∗ )z1 ← CS.TkVerify(par, pkS∗ , pkC
∗
∗
∗
∗
)
z2 ← CS.Valid(par, pkS , pkC , σ , m∗ , skC∗∗
if (pkC , skC ) ∈ {CS.KeyGen C (par)} ∧ z1 = accept ∧ z2 = reject
output 1
else output 0(1k )Expcs-uf-cma
CS,A

Fig. 4. Unforgeability, invisibility and token soundness experiments for a core conﬁrmer
signature scheme

Lastly, we consider token soundness which intuitively captures the property
that an accepting veriﬁcation token cannot be constructed for an invalid signature. Formally, we deﬁne token soundness of a scheme CS via the experimentshown in Figure 4. In the ﬁgure, {CS.KeyGenC (par)} denotes the set
Expcs-tk-snd
CS,Aof all possible key pairs generated by CS.KeyGenC .
Definition 9. A core conﬁrmer signature scheme CS is said to provide token
soundness if there exists no PPT algorithm A with non-negligible advantage
Advcs-tk-snd(k) = Pr[Expcs-tk-snd(1k ) = 1].
CS,A
CS,A
Compatible Sigma Protocols. In our full ONS scheme, we will base the construction of on-line non-transferable protocols on sigma protocols. For this purpose,
we require that a set of sigma protocols compatible with the core conﬁrmer signature scheme exists. More speciﬁcally, we say that a triple of sigma protocols,ΣS , ΣC and Σ C , and a core conﬁrmer signature scheme CS are compatible if
the sigma protocols are deﬁned for the common input x = (par, pkS , pkC , m, σ)
and the following relations.
ΣS {(x, (skS , r)) : (pkS , skS ) ∈ {CS.KeyGenS (par)}∧σ = CS.Sign(par, pkC , m, skS ; r)}
ΣC {(x, skC ) : (pkC , skC ) ∈ {CS.KeyGenC (par)}∧
CS.Valid(par, pkS , pkC , m, σ, skC ) = accept}

382

J.C.N. Schuldt and K. MatsuuraΣ C {(x, skC ) : (pkC , skC ) ∈ {CS.KeyGenC (par)}∧
CS.Valid(par, pkS , pkC , m, σ, skC ) = false}
In the above, we use the notation Σ{(x, w) : R(x, w) = 1} to denote the sigma
protocol Σ for relation R with common input x and witness w. For simplicity,
we assume that the challenge space of ΣS , ΣC and Σ C are of the same size.
4.2

On-line Non-transferable Protocols

Our construction of on-line non-transferable protocols is based on a simple andintuitive approach inspired by the construction of designated veriﬁer proofs by
Jakobsson et al. [10] and is furthermore closely related to the construction ofeﬃcient zero-knowledge proofs in the auxiliary string model [6]. More speciﬁcally,
we modify the compatible sigma protocols using a trapdoor commitment scheme,
and let a prover and a veriﬁer interact as follows:
1. The prover computes the ﬁrst message a of the sigma protocol and the commitment com ← Comm(ck, a, r) for random r, and sends com to the veriﬁer.
2. The veriﬁer then sends a random challenge c to the prover.
3. The prover computes the last message z of the sigma protocol and sends
the opening (a, r) together with z to the veriﬁer. The veriﬁer checks thatcom = Comm(ck, a, r), and accepts if (a, c, z) is an accepting transcript of thesigma protocol.
The commitment key and trapdoor (ck, td) will be used as the public/private
key pair (pkV , skV ) of the veriﬁer. Hence, using skV , the veriﬁer will be able toopen com to any message a of his choice, and can therefor postpone generatinga until after the challenge c is revealed which allows him to simulate the proof
interactively. We use the notation NT(ck)-Σ to denote the non-transferable protocol obtained by modifying the sigma protocol Σ as described above using thecommitment key ck.
However, the above approach is not suﬃcient for proving our constructions
secure. Essentially the problem is that an adversary can request to interact with
SimSign, SimCon and SimDis in many of the security notions deﬁned in Section
3, choosing any message or message/signature pair (valid or invalid) as input.
This type of query can be diﬃcult to handle for a simulator not knowing the
trapdoor of the commitment scheme, whereas a simulator knowing the trapdoor
might not gain suﬃcient information from an adversary breaking the securityof the scheme. To address this problem, we introduce a commitment schemewith a stronger binding property. Speciﬁcally, we consider the advantage of an
adversary A against a scheme T deﬁned byk 
Oc ,Oo(ck) :
AdvbindT,A (k) = Pr[(ck, td) ← G(1 ); (w, r, w , r ) ← A

w = w ∧ Comm(ck, w, r) = Comm(ck, w , r )]where A has access to a commit and an open oracle, Oc and Oo , which behave
as follows: upon request, Oc computes (com, aux) ← TdComm, stores aux andOn-line Non-transferable Signatures Revisited383

returns com to A. Given a commitment com returned by Oc and a value w,
Oo retrieves the corresponding aux and returns r ← TdOpen(aux, w, td) suchthat com = Comm(ck, w, r). The adversary is only allowed to query Oo with acommitment com obtained from Oc , and is not allowed to make more than one
query to Oo for a given commitment com.
Definition 10. A trapdoor commitment scheme T is said to be binding underselective trapdoor openings if no PPT algorithm A with non-negligible advantage
AdvbindT,A (k) exists.
Pedersen’s commitment scheme [16] can be shown to be binding under selective
trapdoor openings assuming the one more discrete logarithm problem is hard.
However, to obtain a commitment scheme which can be shown secure only assuming the ordinary discrete logarithm problem is hard, we can make use of
the “double trapdoor” extension also used to strengthen the security of ordinary
signatures [18]. In the full version, we recall this scheme and prove it binding
under selective trapdoor openings.
4.3

Combined Scheme

We now show how to combine the above mentioned primitives into a full ONS
scheme. More speciﬁcally, let CS = {CS.Setup, CS.KeyGenS , CS.KeyGenC , CS.Sign,
CS.Convert, CS.TkVerify} be a core conﬁrmer signature scheme with compatible
sigma protocols ΣS , ΣC and Σ C , let T = {T.G, T.Comm, T.TdComm, T.TdOpen} be a
trapdoor commitment scheme, and let S = {S.Setup, S.KeyGen, S.Sign, S.Verify}
be an ordinary signature scheme. We construct an ONS scheme N as follows:– Setup(1k ): Compute parS ← S.Setup(1k ) and parCS ← CS.Setup(1k ), andreturn the parameters par ← (parS , parCS ). It is assumed that parCS include
a description of the randomness space R used by the CS.Sign algorithm.
– KeyGenS (par): Return (pkS , skS ) ← CS.KeyGenS (parCS ).
– KeyGenC (par): Return (pkC , skC ) ← S.KeyGen(parS ).
– KeyGenV (par): Return (pkV , skV ) ← T.G(1k ).


, skC
) ← CS.KeyGenC– CSetup(par, pkS , skC ): Compute the key pair (pkC(parCS ) and the signature δ ← S.Sign(parS , “pkS ||pkC ”, skC ), and return, δ) and skC,S ← skC.
pkC,S ← (pkC
– CKeyValid(par, pkS , pkC , pkC,S ) Let pkC,S = (pkC, δ) and return the result
of the veriﬁcation S.Verify(parS , pkC , “pkS ||pkC”, δ).
– (Sign, Receive): The common input is (par, pkS , pkC , pkC,S , pkV , m) where
pkC,S = (pkC, δ) and the signer is given skS as private input. The signer
, skS , pkC ||pkC,S ||m; r).
picks r ∈ R and computes σ ← CS.Sign(parCS , pkC
Then the signer sends σ to the veriﬁer, and interacts with the veriﬁer inthe protocol NT(pkV )-ΣS using (par, pkS , pkC, pkC ||pkC,S ||m, σ) as common
6
input and (skS , r) as secret input .
6

Note that this construction of the sign protocol is slightly more ﬂexible than requiredby the deﬁnition in Section 2 in that a signer is able to re-conﬁrm a signature byrunning NT(pkV )-ΣS . This, however, requires the signer to remember the randomness
used to construct the signature.

384

J.C.N. Schuldt and K. Matsuura– Convert(par, pkS , m, σ, skC,S ): Return the core conﬁrmer signature veriﬁcation token tkσ ← CS.Convert(parCS , pkS , m, σ, skC,S ).
– TkVerify(par, pkS , pkC , pkC,S , m, σ, tkσ ): Firstly, verify the validity of pkC,S
by computing z ← CKeyValid(par, pkS , pkC , pkC,S ), and return reject if
z = reject. Otherwise, let pkC,S = (pkC, δ) and return the output of
CS.TkVerify(parCS , pkS , pkC , pkC ||pkC,S ||m, σ, tkσ ).
– (Confirm, VC ): The common input is given by (par, pkS , pkC , pkC,S , pkV ,m, σ) where pkC,S = (pkC, δ) and the signer is given skC,S as private input.
Firstly, the veriﬁer checks validity of pkC,S by running CKeyValid(par, pkS ,pkC , pkC,S ), and aborts if the output is reject. The conﬁrmer then interacts
with the veriﬁer in the protocol NT(pkV )-ΣC with private input skC,S and
, pkC ||pkC,S ||m, σ).
common input (parS , pkS , pkC– (Disavow, VD ): Having the same input as in (Confirm, VC ), the veriﬁer ﬁrstly
checks if CKeyValid(par, pkS , pkC , pkC,S ) = accept, and aborts if this is not
the case. The veriﬁer and signer then interact in the protocol NT(pkV )-Σ Cwith common input (parS , pkS , pkC, pkC ||pkC,S ||m, σ) and private input skC,S
to the conﬁrmer.
Security. We will now state the theorems showing that the above constructed
ONS scheme satisﬁes the security deﬁnitions given in Section 3 assuming theunderlying primitives are secure. Due to space limitation, the proofs are notincluded here, but can be found in the full version.
Theorem 11. Assume that CS is unforgeable, that ΣS is honest veriﬁer zeroknowledge and has special soundness, and that T is perfectly hiding and binding
under selective trapdoor openings. Then the above ONS scheme N is unforgeable.
Theorem 12. Assume that S is strongly unforgeable. Then the above ONS
scheme N has key unforgeability.
Theorem 13. Assume that ΣS and Σ C have special soundness, and that T
is binding under selective trapdoor openings. Then the above ONS scheme N
provides non-repudiation.
Theorem 14. Assume that ΣS have special soundness, and that T is binding
under selective trapdoor openings. Then the above ONS scheme N provides signer
soundness.
Theorem 15. Assume that CS has unique private conﬁrmer keys and provides
token soundness, that ΣC and Σ C have special soundness, and that T is binding under selective trapdoor openings. Then the above ONS scheme N provides
conﬁrmer soundness.
Theorem 16. Assume that CS is invisible, that ΣS , ΣC and Σ C are honest
veriﬁer zero-knowledge, and that T provides a perfect trapdoor property. Thenthe above ONS scheme N provides on-line non-transferability.

On-line Non-transferable Signatures Revisited

4.4

385

Concrete Instantiation

To instantiate the above construction, we can use the strongly unforgeable
signature scheme by Boneh et al. [1] and the double trapdoor Pedersen commitment scheme mentioned above. In the full version, we deﬁne and provesecure a core conﬁrmer signature scheme and compatible sigma protocols tocomplete the instantiation. The scheme is essentially based on a linear encryption of the ﬁrst component of a Waters signature [19] combined with thetechnique of Boneh et al. [1] to obtain a strongly unforgeable scheme. Morespeciﬁcally, the public/private key pairs of the signer and conﬁrmer is givenby (pkS , skS ) = ((g α , g2 , h, F ), α) and (pkC , skC ) = ((u, v), (x, y)) where F isa Waters hash function and ux = v y = g, and a signature is of the form σ =(ua , v b , g a+b+r , g2α H(M )r , s) where M = g t hs , t = H(pkC ||ua ||v b ||g a+b+r ||m),and H is a collision resistant hash function. The scheme is invisible assuming
the decisional linear problem is hard, and is strongly unforgeable assume thediscrete logarithm problem is hard, H is collision resistant and Waters signatures are (weakly) unforgeable. Furthermore, the structure of the scheme allows
the compatible sigma protocols to be implemented using well-know techniques
for proving equality and inequality of discrete logarithms. We refer the reader
to the full version for the details.

5

Comparison

The generic construction by Liskov and Micali [13] provides many instantiation
options due to their use of standard primitives, whereas our approach relies on
special building blocks. However, our concrete instantiation has several advantages compared to any instantiation of the scheme by Liskov and Micali, bothin terms of functionality, eﬃciency and security. More speciﬁcally, our scheme
allows a conﬁrmer to both conﬁrm and disavow signatures, provides short signatures compared to the O(k) size signatures of [13] which furthermore allows amore eﬃcient sign protocol, and lastly, all interactive protocols are on-line nontransferable, security is guaranteed when multiple (potentially malicious) conﬁrmers are used, and the signer is not required to engage in any “fake” signing
protocols to maintain security. As mentioned in the introduction, these security
properties are not enjoyed by [13]. We note, however, that our scheme requires
large public keys whereas [13] can be instantiated to provide compact publickeys, and that the non-interactive disavow protocol of [13] allows perfect nonrepudiation whereas our scheme only achieves computational non-repudiation.

References
1. Boneh, D., Shen, E., Waters, B.: Strongly Unforgeable Signatures Based on Computational Diﬃe-Hellman. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.)
PKC 2006. LNCS, vol. 3958, pp. 229–240. Springer, Heidelberg (2006)

386

J.C.N. Schuldt and K. Matsuura

2. Camenisch, J., Michels, M.: Conﬁrmer signature schemes secure against adaptive
adversaries. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 243–
258. Springer, Heidelberg (2000)
3. Chaum, D.: Zero-knowledge undeniable signatures. In: Damgård, I.B. (ed.)
EUROCRYPT 1990. LNCS, vol. 473, pp. 458–464. Springer, Heidelberg (1991)
4. Chaum, D.: Designated Conﬁrmer Signatures. In: De Santis, A. (ed.)
EUROCRYPT 1994. LNCS, vol. 950, pp. 86–91. Springer, Heidelberg (1995)
5. Chaum, D., van Antwerpen, H.: Undeniable Signatures. In: Brassard, G. (ed.)
CRYPTO 1989. LNCS, vol. 435, pp. 212–216. Springer, Heidelberg (1990)
6. Damgård, I.: Eﬃcient Concurrent Zero-Knowledge in the Auxiliary String Model.
In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 418–430. Springer,
Heidelberg (2000)
7. Galbraith, S.D., Mao, W., Paterson, K.G.: RSA-Based Undeniable Signatures for
General Moduli. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 200–217.
Springer, Heidelberg (2002)
8. Gentry, C., Molnar, D., Ramzan, Z.: Eﬃcient Designated Conﬁrmer Signatures
Without Random Oracles or General Zero-Knowledge Proofs. In: Roy, B. (ed.)
ASIACRYPT 2005. LNCS, vol. 3788, pp. 662–681. Springer, Heidelberg (2005)
9. Huang, X., Mu, Y., Susilo, W., Wu, W.: Provably Secure Pairing-Based Convertible
Undeniable Signature with Short Signature Length. In: Takagi, T., Okamoto, T.,Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 367–391.
Springer, Heidelberg (2007)
10. Jakobsson, M., Sako, K., Impagliazzo, R.: Designated Veriﬁer Proofs and Their
Applications. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp.
143–154. Springer, Heidelberg (1996)
11. Kudla, C., Paterson, K.G.: Non-interactive Designated Veriﬁer Proofs and Undeniable Signatures. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS,
vol. 3796, pp. 136–154. Springer, Heidelberg (2005)
12. Kurosawa, K., Heng, S.-H.: 3-Move Undeniable Signature Scheme. In: Cramer,R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 181–197. Springer, Heidelberg(2005)
13. Liskov, M., Micali, S.: Online-Untransferable Signatures. In: Cramer, R. (ed.)
PKC 2008. LNCS, vol. 4939, pp. 248–267. Springer, Heidelberg (2008)
14. Michels, M., Stadler, M.: Generic Constructions for Secure and Eﬃcient Conﬁrmer
Signature Schemes. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp.
406–421. Springer, Heidelberg (1998)
15. Monnerat, J., Vaudenay, S.: Short 2-Move Undeniable Signatures. In: Nguyên, P.Q.
(ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 19–36. Springer, Heidelberg (2006)
16. Pedersen, T.P.: Non-interactive and information-theoretic secure veriﬁable secretsharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140.
Springer, Heidelberg (1992)
17. Steinfeld, R., Bull, L., Wang, H., Pieprzyk, J.: Universal Designated-Veriﬁer Signatures. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 523–542.
Springer, Heidelberg (2003)
18. Teranishi, I., Oyama, T., Ogata, W.: General Conversion for Obtaining
Strongly Existentially Unforgeable Signatures. In: Barua, R., Lange, T. (eds.)
INDOCRYPT 2006. LNCS, vol. 4329, pp. 191–205. Springer, Heidelberg (2006)
19. Waters, B.: Eﬃcient Identity-Based Encryption Without Random Oracles. In:
Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer,
Heidelberg (2005)