Fabien Laguillaumie

Damien Vergnaud

Time-Selective Convertible Undeniable Signatures with Short Conversion Receipts *

Keywords: Convertible undeniable signatures, bilinear maps, anonymity, exact security, timeselective conversion

Undeniable signatures were introduced in 1989 by Chaum and van Antwerpen to limit the selfauthenticating property of digital signatures. An extended concept -the convertible undeniable signatures -proposed by Boyar, Chaum, Damgård and Pedersen in 1991, allows the signer to convert undeniable signatures to ordinary digital signatures.

In this article, we present a new efficient convertible undeniable signature scheme based on bilinear maps. Its unforgeability is tightly related, in the random oracle model, to the computational Diffie-Hellman problem and its anonymity to a non-standard decisional assumption. The advantages of our scheme are the short length of the signatures, the low computational cost of the signature and the receipt generation. Moreover, a variant of our scheme permits the signer to universally convert signatures pertaining only to a specific time period. We formalize this new notion as the timeselective conversion. We also improve our original scheme from CT-RSA'05 by reducing the length of the generated receipts: their size is now logarithmic in the number of time periods.

Introduction

We present a new efficient convertible undeniable signature scheme based on bilinear maps. Its unforgeability is tightly related, in the random oracle model, to the computational Diffie-Hellman problem and its anonymity to a non-standard decisional assumption. The advantages of our scheme are the short length of the signatures, the low computational cost of the signature and the receipt generation. Moreover, a variant of our scheme permits the signer to universally convert signatures pertaining only to a specific time period. We formalize this new notion as the time-selective conversion. Contrary to the original scheme [START_REF] Laguillaumie | Time-Selective Convertible Undeniable Signatures[END_REF] where the size of the receipts grew linearly with the number of time periods, the size of the generated receipts in the scheme proposed in this longer version is only logarithmic in the number of time periods.

Previous work

Digital signatures aim at recover in silico the usual properties of the traditional in vivo signatures, namely authentication, integrity, non-repudiation of the signed document and universal verifiability of the signatures. However, unlike handwritten signatures, digital signatures can be copy-cloned and therefore authenticated confidential documents (e.g. software certificates, contracts, dishonourable bills) can easily be disseminated.

For privacy reasons, it is desirable, in many applications, that the verification of signatures be controlled or (at least) limited by the signer. This remark justifies the concept of undeniable signatures, introduced in 1989 by Chaum and van Antwerpen [START_REF] Chaum | Undeniable Signatures[END_REF]. In this setting, the verification of a signature requires the cooperation of the signer. The security of their protocol relies on the hardness of the computational Diffie-Hellman problem, but suffers from the fact that the interactive protocols are not zero-knowledge. One year later, Chaum improved significantly the initial proposal in [START_REF] Chaum | Zero-Knowledge Undeniable Signatures[END_REF] by providing a zero-knowledge version.

There exist documents whose authentication must be limited at first, but which will require ordinary digital signatures after some period of time. In 1991, the concept has been refined by giving the possibility to transform an undeniable signature into a self-authenticating signature. These convertible undeniable signatures, introduced in [START_REF] Boyar | Convertible undeniable signatures[END_REF] by Boyar, Chaum, Damgård and Pedersen, provide individual and universal conversions of the signatures. Unfortunately, the seminal Elgamal-like scheme has been broken in 1996 by Michels, Petersen, and Horster [START_REF] Michels | Breaking and Repairing a Convertible Undeniable Signature Scheme[END_REF] who proposed a repaired version with heuristic security 1 . Since then, many schemes have then been proposed, based upon classical signatures, such as Schnorr [START_REF] Michels | Efficient Convertible Undeniable Signature Schemes[END_REF], Elgamal [START_REF] Damgård | New Convertible Undeniable Signature Schemes[END_REF] and RSA [START_REF] Gennaro | RSA-Based Undeniable Signatures[END_REF][START_REF] Galbraith | RSA-based Undeniable Signatures for General Moduli[END_REF][START_REF] Galbraith | Invisibility and Anonymity of Undeniable and Confirmer Signatures[END_REF]. Convertible undeniable signatures have given rise to many applications in cryptography [START_REF] Boyar | Convertible undeniable signatures[END_REF][START_REF] Boyd | Off-line Fair Payment Protocols using Convertible Signatures[END_REF][START_REF] Chaum | Wallet Databases with Observers[END_REF].

In all these protocols, the universal conversion consists in revealing a part of the signer's secret key. This conversion makes all signatures, past as well as future, be universally verifiable. This property may be undesirable in some context and furthermore the corresponding keys cannot be used to generate undeniable signatures any more. As in a classical public key infrastructure the public key needs to be certified by an authority (as well as in any asymmetric cryptographic protocol), this approach leads to the registration of a large number of public/secret key pairs for the signer, and the need for the verifiers to check the validity of these certificates.

Our contributions

In this article, we propose a new convertible undeniable signature scheme, in the spirit of both the original paper of Chaum and van Antwerpen [START_REF] Chaum | Undeniable Signatures[END_REF] and the short signatures from bilinear maps proposed by Boneh, Lynn and Shacham [START_REF] Boneh | Short Signatures from the Weil Pairing[END_REF]. The amusing fact is that the idea underlying these two papers is actually the same. In both cases, a signature consists in an exponentiation of (a hash-value of) the message by the signer's secret key : h(m) s . In Chaum and van Antwerpen's scheme, the anonymity of signatures [START_REF] Galbraith | Invisibility and Anonymity of Undeniable and Confirmer Signatures[END_REF] comes from the difficulty of the decisional Diffie-Hellman problem in a prime order subgroup of the multiplicative group of a finite field, whereas the efficiency of Boneh et al. signatures comes from the ease of this problem on certain elliptic curves.

We combine the best of both worlds and, introducing Zhang-Safavi-Naini-Susilo and Boneh-Boyen's technique from [START_REF] Zhang | Efficient Verifiably Encrypted Signature and Partially Blind Signature from Bilinear Pairings[END_REF][START_REF]Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups[END_REF], we obtain a convertible undeniable signature protocol which is one of the most efficient. Moreover, to overcome the difficulty mentioned above, we introduce and formalize the timeselective convertible undeniable signatures which supports signers in gradually converting the undeniable signatures in a controlled fashion. A slight variant of our new scheme permits the signer to universally convert signatures pertaining only to a specific time period. The size of the receipt is only logarithmic in the number of time conversions (whereas in our previous proposal [START_REF] Laguillaumie | Time-Selective Convertible Undeniable Signatures[END_REF], this size was linear in the number of time periods).

The new convertible undeniable signature scheme is designed for devices with constrained computation capabilities or with low bandwidth. It can be embedded in smart cards for example, as the main computation for a signature is a scalar multiplication on an elliptic curve, and the signature is essentially one point (with some additional random salt). The unforgeability of our scheme is tightly related, in the random oracle model, to the computational Diffie-Hellman problem and its anonymity to a non-standard (non-interactive2 ) decisional assumption.

Subsequent work

In [START_REF] Aimani | Gradually Convertible Undeniable Signatures[END_REF], El Aimani and the second author provided a protocol for time-selective convertible undeniable signatures (based on [START_REF] Michels | Breaking and Repairing a Convertible Undeniable Signature Scheme[END_REF]) with an advanced feature which permits the signer to universally convert achronously all signatures pertaining to a specific time period. The security is proven in the generic group model assuming specific assumptions on the hash function. Unfortunately, the conversion properties is ensured by using pseudo-random functions and are therefore not publicly checkable.

The technique introduced in [START_REF] Laguillaumie | Time-Selective Convertible Undeniable Signatures[END_REF] has had other applications. For instance, Paillier and the authors designed a very efficient universally convertible directed signatures [START_REF] Laguillaumie | Universally Convertible Directed Signatures[END_REF] -such a construction had remained open since 1993.

Roadmap

The article is organised as follows: first we formally define the concept of time-selective convertible undeniable signature scheme and its security model in Section 2. Then, we recall in Section 3 standard techniques to (dis)prove the membership of group elements to some algebraic languages, we review the cryptographic properties of bilinear maps and we describe the problems upon which depend our schemes. In section 4, we describe our new scheme and its time-selective convertible variant. Eventually in Section 5 we prove their security in the random oracle model. In appendix, we present a time-selective convertible variant of Huang, Mu, Susilo and Wei's undeniable signature scheme from [START_REF] Huang | Provably secure pairing-based convertible undeniable signature with short signature length[END_REF], since its security holds under more classical assumptions.

2 Formal definition and security model

Notations

The set of n-bit strings is denoted by {0, 1} n and the set of all finite binary strings is denoted by {0, 1} * . The empty word is denoted by . Let A be a probabilistic Turing machine running in polynomial time (a PPTM, for short), and let x be an input for A. The probability space that assigns to a string σ the probability that A, on input x, outputs σ is denoted by A(x). The support of A(x) is denoted by A[x]. Given a probability space S, a PPTM that samples a random element according to S is denoted by x R ← -S. For a finite set X, x R ← -X denotes a PPTM that samples a random element uniformly at random from X.

Definition

In this subsection, we formalise the concept of time-selective convertible undeniable signatures.

Definition 1 (Time-selective convertible undeniable signature). Let T be a positive integer. A timeselective convertible undeniable signature scheme with T time periods Σ is a 9-tuple Σ = (Setup, SKeyGen, VKeyGen, Sign, Control, Confirm, Deny, Convert, Verify) such that:

• Σ.Setup, the common parameter generation algorithm, is a PPTM which takes an integer k as input.

The output are the public parameters P. The integer k is called the security parameter.

• Σ.SKeyGen, the signer key generation algorithm, is a PPTM which takes the public parameters as input. The output is a pair (sk s , pk s ) where sk s is called a signing secret key and pk s a signing public key.

• Σ.VKeyGen, the verifier key generation algorithm, is a PPTM which takes the public parameters as input. The output is a pair (sk v , pk v ) where sk v is called a verifying secret key and pk v a verifying public key.

• Σ.Sign, the signing algorithm, is a PPTM which takes the public parameters, a message, an integer in [[1, T ]] and a signing secret key as inputs and outputs a bit string.

• Σ.Control, the controlling algorithm, is a PPTM which takes the public parameters, a message m, a bit string σ, an integer p ∈ [[1, T ]] and a signing key pair (sk s , pk s ) as inputs and outputs a bit. If the bit output is 1 then the bit string σ is said to be a signature on m for pk s for the time period p.

• Σ.{Confirm.Deny}, the confirming/denying protocols (respectively), are two-party protocols (Prove, Verify) such that:

-Prove and Verify take as input the public parameters, a message m, an integer p ∈ [[1, T ]], a bit-string σ, a signing public key pk s and a verifying public key pk v and the public parameters; -Prove takes as input sk s the signing secret key corresponding to pk s ; -Verify takes as input sk v the verifying secret key corresponding to pk v ;

Confirm.Verify (resp Deny.Verify ) outputs an element in {⊥, 1} (resp {⊥, 0}).

• Σ.Convert, the conversion algorithm, is a PPTM which takes as input the public parameters, an integer in [[1, T ]], a signing key pair and a bit string Υ (either a pair message/signature or the empty string ) and outputs a bit string.

• Σ.Verify, the verifying algorithm for converted signature, is a PPTM which takes as input the public parameters, a message m, and a bit string σ, an integer p ∈ [[1, T ]], a signing public key pk s and a bit string Λ and outputs a bit. If the bit output is 1 then the bit string Λ is said to be a receipt of the validity of σ.

where the protocols Σ.Confirm and Σ.Deny are designated verifier proof of membership systems for the languages (respectively): 1. completeness and soundness: the confirming and denying protocols and the verifying algorithms are complete and sound, where completeness means that valid (invalid) signatures can always be proved valid (invalid), and soundness means that no valid (invalid) signature can be proved invalid (valid);

{(P, m, σ, p, (sk s , pk s )) ∈ Σ.Setup[k] × {0, 1} * 2 × [[1, T ]] × Σ.SKeyGen[P] such that Σ.Control[P, m, σ, p, (sk s , pk s )] = {1}} {(P, m, σ, p, (sk s , pk s )) ∈ Σ.Setup[k] × {0, 1} * 2 × [[1, T ]] × Σ.
2. non-transferability: a verifier participating in an execution of the confirming/denying protocols does not obtain information that could be used to convince a third party about the validity/invalidity of a signature.

Our definition generalises the definition of traditional convertible undeniable signature since:

Definition 2 (Convertible Undeniable Signature). A convertible undeniable signature scheme is a timeselective convertible undeniable signature scheme with one time period.

Security model

In this subsection, we define the quantitative notions of unforgeability and anonymity of a time-selective convertible undeniable signature scheme. The proofs of security are carried in the random oracle model proposed by Bellare and Rogaway [START_REF] Bellare | Random Oracles are Practical: A Paradigm for Designing Efficient Protocols[END_REF]. In this model, hash functions are idealised as oracles which output a random value for each new query.

Registered public key model.

In public key cryptography, the notion of anonymity is to be handled with great attention. For instance, in order to ensure anonymity, it is important that users register their public key by a certifying authority. Hence, in our security analysis, it is assumed that the users' keys have been already registered to an authority. The registration procedure would always contain a proof of knowledge of the associated private key. To further simplify the security analysis, we will assume that this procedure will be the direct registration of the keys3 .

Security against existential forgery under chosen message attack

The standard notion of security for digital signatures was defined by Goldwasser, Micali and Rivest [START_REF] Goldwasser | A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks[END_REF] as existential forgery against adaptive chosen message attacks (EF-CMA). In [START_REF] Laguillaumie | Time-Selective Convertible Undeniable Signatures[END_REF], the corresponding notion for time-selective convertible undeniable signatures is defined along the same lines. The definition of resistance to forgery for time-selective convertible undeniable signatures that we propose is similar. In fact, we suppose that the adversary has access to the universal receipts for every time period p ∈ [[1, T ]] and is allowed to query a converting oracle Cv, a confirming oracle C and a denying oracle D on any couple message/signature of its choice. As usual, in the adversary answer, there is the natural restriction that the returned message/signature has not been obtained from the signing oracle.

Definition 3 (Unforgeability -EF-CMA). Let T be a positive integer, let Σ = (Setup, SKeyGen, VKeyGen, Sign, Control, Confirm, Deny, Convert, Verify) be a time-selective convertible undeniable signature scheme with T time periods and let A be an PPTM. We consider the following random experiment, where k is a security parameter:

Experiment Exp ef-cma Σ,A (k)
P R ← -Σ.Setup(k), (sk s , pk s ) R ← -Σ.SKeyGen(P) for j = 1 to T do Λ j ← Σ.Convert(P, j, (sk s , pk s ), ) (m , σ , p ) R ← -A S,Cv,C,D (P, pk s , {Λ j } j∈[[1,T ]] ) S : (m, p) -→ Σ.Sign(P, m, p, sk s ) Cv : (m, p, σ) -→ Σ.Convert(P, p, (sk s , pk s ), (m, σ)) C : (m, p, σ, pk v ) -→ Σ.Confirm(P, m, p, σ, pk v , pk s ) D : (m, p, σ, pk v ) -→ Σ.
Deny(P, m, p, σ, pk v , pk s ) return 1 if and only if the following properties are satisfied:

-

Σ.Verify[P, pk s , m , σ , p , Λ p ] = {1} -σ was not obtained from S We define the success of A, via Succ ef-cma Σ,A (k) = Pr Exp ef-cma Σ,A (k) = 1 . Given (k, t) ∈ N 2 and ε ∈ [0, 1], the scheme Σ is said to be (k, t, ε)-EF-CMA secure, if no EF-CMA- adversary A running in time t has Succ ef-cma Σ,A (k) ≥ ε.
The scheme Σ is said to be EF-CMA secure if, for any security parameter k ∈ N, any polynomial function t : N → N, and any negligible function

ε : N → [0, 1], it is (k, t(k), ε(k))-EF-CMA secure.

Anonymity

We state the precise definition of anonymity under a chosen message attack (Ano-CMA) which captures the notion that an attacker cannot determine under which key a signature was performed [START_REF] Galbraith | Invisibility and Anonymity of Undeniable and Confirmer Signatures[END_REF]. We consider a Ano-CMA-adversary A that runs in two stages. In the find stage, it takes as input two signing public keys pk s0 and pk s1 and outputs a message m , a time period p together with some state information I. In the guess stage, A gets a challenge time-selective convertible undeniable signature σ formed by signing at random the message m under one of the two keys for the time period p and it must say which key was chosen. In both stages, the adversary has access to a signing oracle S for both signing key pairs, to a converting oracle Cv, to a confirming oracle C and to a denying oracle D. The attacker is also given the universal receipts of both potential signers for all time period p ∈ [ [1, p -1]]. The only restriction on A is that it cannot query the triple (m , σ , p ) on the converting and confirming/denying oracles.

Definition 4 (Anonymity -Ano-CMA). Let T be a positive integer, let Σ = (Setup, SKeyGen, VKeyGen, Sign, Control, Confirm, Deny, Convert, Verify) be a time-selective convertible undeniable signature scheme with T time periods and let A be an PPTM. We consider the following random experiments, for r ∈ {0, 1}, where k is a security parameter:

Experiment Exp ano-cma-r Σ,A (k) P R ← -Σ.Setup(k) (sk s0 , pk s0 ) R ← -Σ.SKeyGen(P) (sk s1 , pk s1 ) R ← -Σ.SKeyGen(P) (m , p , I) R ← -A S,Cv,C,D (find, P, pk s0 , pk s1 ) S : (m, p, i) -→ Σ.Sign(P, m, p, sk si ) Cv : (m, p, σ, i) -→ Σ.Convert(P, p, (sk si , pk si ), (m, σ)) C : (m, p, σ, pk v , i) -→ Σ.Confirm(P, m, p, σ, pk v , pk si ) D : (m, p, σ, pk v , i) -→ Σ.Deny(P, m, p, σ, pk v , pk si ) σ R ← -Σ.Sign(P, m, sk sr , p ) for j from 1 to p -1 do Λ 0 j ← Σ.Convert(P, j, pk s0 , sk s0 , ) Λ 1 j R ← -Σ.Convert(P, j, pk s1 , sk s1 , ) d ← A S,Cv,C,D (guess, I, {Λ 0 j , Λ 1 j } j∈[[1,p -1]] ) Return d
We define the advantage of A, via

Adv ano-cma Σ,A (k) = Pr Exp ano-cma-1 Σ,A (k) = 1 -Pr Exp ano-cma-0 Σ,A (k) = 1 . Given (k, t) ∈ N 2 and ε ∈ [0, 1], the scheme Σ is said to be (k, t, ε)-Ano-CMA secure, if no Ano-CMA- adversary A running in time t has Adv ano-cma Σ,A (k) ≥ ε.
The scheme Σ is said to be Ano-CMA secure if, for any security parameter k ∈ N, any polynomial function t : N → N, and any negligible function

ε : N → [0, 1], it is (k, t(k), ε(k))-Ano-CMA secure.
Remark 2. To obtain the security results, the executions of the confirming-denying protocols must be simulated in the random oracle model. In our scheme, these protocols are achieved by interactive zero-knowledge proofs of equality/inequality of (root of ) discrete logarithms. More precisely, we use designated-verifier proofs [START_REF] Jakobsson | Designated Verifier Proofs and Their Applications[END_REF]. By definition of these proofs, the adversary gains no information other than the validity/invalidity of the signature from its interaction with the signer. As the adversary can obtain this conviction by querying the receipt generating oracle, there is no loss of generality to suppose that it does not have access to the confirming/denying oracles.

Background

Proof of equality or inequality of two discrete logarithms

Let (G, +) and (H, •) be two groups of the same prime order q and let P and g be generators of G and H (respectively). To confirm or deny that a bit string is a signature in our undeniable signature scheme, it is necessary to prove that a given quadruple (U

1 , V 1 , u 2 , v 2 ) ∈ G 2 × H 2 is
a Diffie-Hellman quadruple (or not), i.e. belongs to the set

EDL(G, H) = {(U 1 , V 1 , u 2 , v 2 ) ∈ G 2 × H 2 , log U1 (V 1 ) = log u 2 (v 2 )}, (or to the set IDL(G, H) = (G 2 × H 2 ) \ EDL(G, H)).
We denote, as in [START_REF] Camenisch | Efficient Group Signature Schemes for Large Groups[END_REF], the zero-knowledge proof of equality of the discrete logarithm

(EDL) of V 1 ∈ G in base U 1 and the one of v 2 ∈ H in base u 2 by P K(x : V 1 = xU 1 ∧ v 2 = u x
2 ). We use the notation

P K(x : V 1 = xU 1 ∧ v 2 = u x 2 )
. for the proof of inequality of the discrete logarithms (IDL). We refer the reader to Chaum and Pedersen's paper [START_REF] Chaum | Wallet Databases with Observers[END_REF] for the proof of equality, and the one of Camenisch and Shoup [START_REF] Camenisch | Practical Verifiable Encryption and Decryption of Discrete Logarithms[END_REF] for the proof of inequality.

In the design of the time-selective convertible undeniable signature scheme, we also need zeroknowledge proofs of equality/inequality of a root of a discrete logarithm: given p ∈ N,

P K(x : V 1 = xU 1 ∧ v 2 = u 2 x p ) and P K(x : V 1 = xU 1 ∧ v 2 = u 2 x p ).
Techniques to design efficient protocol can be found in [START_REF] Camenisch | Efficient Group Signature Schemes for Large Groups[END_REF][START_REF] Bresson | Proofs of Knowledge for Non-Monotone Discrete-Log Formulae and Applications[END_REF].

To face blackmailing or man in the middle (or mafia) attacks against our undeniable signatures, we use interactive designated verifier proofs, as introduced in [START_REF] Jakobsson | Designated Verifier Proofs and Their Applications[END_REF] by Jakobsson, Sako, and Impagliazzo, in Chaum's proofs of equality and inequality of discrete logarithm of [START_REF] Camenisch | Practical Verifiable Encryption and Decryption of Discrete Logarithms[END_REF]. The idea is to replace the generic commitment scheme by a trapdoor commitment [START_REF] Jakobsson | Designated Verifier Proofs and Their Applications[END_REF] and using classical techniques, the proofs are readily seen to be complete, sound, and above all non-transferable. The protocols involve a point Y = yU 1 where y is the secret key of the verifier, and the prover must be convinced that Y is well-formed (in the registered public key model, the registration procedure is used to force the users to know the secret-key corresponding to their public key). Such a proof is naturally non-transferable since the designated-verifier could have produced a given proof. The previously mentioned proofs of equality/inequality of a root of a discrete logarithm can be found in [32, p. 262].

Eventually, Fig. 1 and 2 represent respectively a designated verifier proof of equality of two discrete logarithms and its simulation. Fig. 3 and4 represents respectively a designated verifier proof of inequality of two discrete logarithms and its simulation.

Bilinear maps

Admissible bilinear maps have allowed the opening up of new territories in cryptography, making possible the realisation of protocols that were previously unknown or impractical.

Definition 5 (Admissible bilinear map [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF]). Let (G, +) and (H, ×) be two groups of the same prime order q and let us denote by P a generator of G. An admissible bilinear map is a map e : G × G -→ H satisfying the following properties:

• bilinear: e(aQ, bR) = e(Q, R) ab for all (Q, R) ∈ G 2 and all (a, b) ∈ Z 2 ;

• non-degenerate: e(P, P ) = 1.

• computable: there exists a polynomial time algorithm to compute e.

Definition 6 (prime-order-BDH-parameter-generator [4]).

A prime-order-BDH-parameter-generator is a probabilistic algorithm which takes as input a security parameter k and outputs a 5-tuple (q, P, G, H, e) where q is a prime with 2 k < q < 2 k+1 , G and H are groups of order q, P generates G, and e : G 2 -→ H is an admissible bilinear map.

Usually G can be considered as a subgroup of points on a (hyper)elliptic curve over a finite field, H as a subgroup of the multiplicative group of a related finite field and e as the Weil or Tate pairing [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF].

EDL.Prove Prover Verifier (a, b, k) R ← -[[1, q -1]] 3 C 1 = kU 1 c 2 = u k 2 C 3 = aU 1 + bY C 1 , c 2 , C 3 -------------→ r ← ------------- r ∈ R [[1, q -1]] c = k -x(r + b) mod q a, b, c -------------→ C 1 ? = cU 1 + (r + b)V 1 c 2 ? = u c 2 • v r+b 2 C 3 ? = aU 1 + bY V 1 = xU 1 ∧ v 2 = u x 2
Verifier: (pk, sk) = (Y, y) with Y = yU 1 At first glance, this may seem very similar to the classical decisional Diffie-Hellman (DDH) problem (in fact, the associated computational problem is equivalent to the CDH problem). The DDH assumption, underlying the security of many cryptographic protocols does not hold in the bilinear setting. Even if it is easier than the DBDH problem [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF], the xyz-DDH problem seems intractable. Considering the xyz-DDH problem and assuming its difficulty (combined with the ease of the DDH problem), we are able to design cryptographic protocols achieving a trade-off between authenticity and privacy. The time-selective convertible undeniable signature scheme is based on the following observations:

• Assuming the computational intractability of the xyz-DDH problem, given (P, xP, yP, zP, Q) ∈ G5 , no one can efficiently decide whether Q = xyzP .

• Everyone can be convinced by someone knowing either x, y or z that Q = xyzP . This can be done thanks to the proofs of equality of two discrete logarithms mentioned above, and the equalities e(Q, P ) = e(yP, zP ) x = e(xP, zP ) y = e(xP, yP ) z .

• After the publication of xyP , everyone can decide whether Q = xyzP .

Our new protocol is designed according to this idea but relies on a stronger assumption.

A new decisional problem

Recently, Boneh and Boyen [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF] proposed an efficient digital signature scheme whose security (in the standard security model) relies on the so-called -Strong Diffie-Hellman problem ( -SDH). This computational problem is slightly weaker than the -CAA problem 5 introduced by Mitsunari, Sakai, Kasahara Let (G, +) be a group of prime order q, let x, y and z be in [[1, q -1]] and and T be in N.

EDL.Fake Prover Verifier (c, d, k) R ← -[[1, q -1]] 3 C 1 = cU 1 + dV 1 c 2 = u c 2 • v d 2 C 3 = kU 1 C 1 , c 2 , C 3 -------------→ r ← ------------- r ∈ R [[1, q -1]] b = d -r mod q a = k -by mod q a, b, c -------------→ C 1 ? = cU 1 + (r + b)V 1 c 2 ? = u c 2 • v r+b 2 C 3 ? = aU 1 + bY V 1 = xU 1 ∧ v 2 = u x 2 Verifier: (pk, sk) = (Y, y) with Y = yU 1
Input:

(x i P ) i∈[[0,2T -1]] , yP, zP, h, x T y x + h k P, h k k∈[[1, ]] in G 2T +2 × [[1, q -1]] × (G × [[1, q -1]]) , with h / ∈ {h 1 , . . . , h } Oracle: for a request t ∈ [[1, T ]], the oracle answers (x i yP ) i∈[[1,t -1]] , Q ∈ G t Output: decide whether (x + h)Q = x t yzP
The anonymity of our convertible undeniable signature scheme (i.e. with one time period) is related to the ( , 1)-xyz-DCAA problem. The link between this problem and the -CAA problem from [START_REF] Mitsunari | A New Traitor Tracing[END_REF] is analogous to the one between the xyz-DDH problem and the CDH problem. We want to stress that, though non-standard, these problems achieve generic security (as defined by Shoup [START_REF] Shoup | Lower Bounds for Discrete Logarithms and Related Problems[END_REF]). The proof is similar to the one of the generic security of -SDH [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF].

To conclude this section, we quantify the new algorithmic assumption.

Definition 7 (( , T )-xyz-DCAA assumption).

Let Gen be a prime-order-BDH-parameter-generator and let and T be two integers. Let D be an adversary that takes on input (q, P, G, H, e) a 5-tuple generated by Gen and

(X i ) i∈[[1,2T -1]] , Y, Z, h, (R j , h j ) j∈[[1, ]] ∈ G 2T +1 × [[1, q -1]] × (G × [[1, q -1]])
and returns a bit. We consider the following random experiments, where k is a security parameter, for r ∈ {0, 1}:

IDL.Prove Prover Verifier (a, b, k 0 , k 1 , k 2 ) R ← -[[1, q -1]] 5 c 0 = v k0 2 /u xk0 2 C 1 = k 1 U 1 -k 2 V 1 c 2 = u k1 2 /v k2 2 C 3 = aU 1 + bY c 0 , C 1 , c 2 , C 3 -------------→ r ← ------------- r ∈ R [[1, q -1]] c = k 1 -xk 0 (r + b) mod q d = k 2 -k 0 (r + b) mod q a, b, c, d -------------→ c 0 ? = 1 H C 1 ? = cU 1 -dV 1 c 2 ? = c 0 u c 2 /v r+b 2 C 3 ? = aU 1 + bY V 1 = xU 1 ∧ v 2 = u x 2
Verifier: (pk, sk) = (Y, y) with Y = yU 1

P = (q, P, G, H, e) R ← -Gen(k) x R ← -[[1, q -1]] For i from 1 to 2T -1 do X i ← x i P (y, z) R ← -[[1, q -1]] 2 , Y ← yP , Z ← zP h 1 , . . . , h , h R ← -[[1, q -1]] For j from 1 to do R j = x T y(x + h j ) -1 P t ← D(P, (X i ) i∈[[1,2T -1]] , Y, Z, h, (R j , h j ) j∈[[1, ]] ) For k from 1 to t -1 do Y k ← x k yP If r = 0 then Q ← x T yz(x + h) -1 P else Q R ← -G d ← D(P, t , (X i ) i∈[[1,2T -1]] , Y, Z, h, (R j , h j ) j∈[[1, ]] , (Y k ) k∈[[1,t -1]] , Q) Return d (k)
We define the corresponding advantage of D in solving the ( , T ) -xyz-DCAA problem via:

Adv ( ,T)-xyz-dcaa Gen,D (k) = Pr Exp ( ,T)-xyz-dcaa-0 Gen,D (k) = 1 -Pr Exp ( ,T)-xyz-dcaa-1 Gen,D (k) = 1 . Given (k, t) ∈ N 2 and ε ∈ [0, 1], Gen is said to be (k, t, ε)-( , T )-xyz-DCAA-secure if no adversary D running in time t has advantage Adv ( ,T)-xyz-dcaa Gen,D (k) ≥ ε.
The generator Gen is said to be ( , T )-xyz-DCAA-secure if, for any security parameter k ∈ N, any polynomial function t : N → N, and any negligible function ε : In this section, we describe the new convertible undeniable signature scheme CUSBM, based on bilinear map. It is designed as follows:

N → [0, 1], it is (k, t(k), ε(k))-( , T )-xyz- DCAA-secure. IDL.Fake Prover Verifier (c, d, k 1 , k 2 ) R ← -[[1, q -1]] 4 c 0 R ← -H \ {1 H } C 1 = cU 1 -dV 1 c 2 = c 0 u c 2 /v k1 2 C 3 = k 2 U 1 c 0 , C 1 , c 2 , C 3 -------------→ r ← ------------- r ∈ R [[1, q -1]] b = k 1 -r mod q a = b -k 2 y mod q a, b, c, d -------------→ c 0 ? = 1 H C 1 ? = cU 1 -dV 1 c 2 ? = c 0 u c 2 /v r+b 2 C 3 ? = aU 1 + bY V 1 = xU 1 ∧ v 2 = u x

Setup and Key Generation

Setup: Let k be a security parameter, Gen be a prime-order-BDH-parameter-generator and (q, P, G, H, e) some output of Gen(k). Let f r : N → N be a function. We denote n r = f r (k). Let [{0, 1} * × {0, 1} nr -→ G] be a hash function family, and H be a random member of this family. Let [{0, 1} * × {0, 1} nr -→ [[1, q -1]]] be a hash function family, and h be a random member of this family. The public parameters are [(q, P, G, H, e), H, h] SKeyGen: Alice picks randomly two integers a 1 , a 2 ∈ [[1, q -1]] and computes the points P 1 = a 1 P and P 2 = a 2 P . Alice's public key is the pair (P 1 , P 2 ) and her secret key is (a 1 , a 2 ).

VKeyGen: the verifier Bob picks randomly an integer y ∈ [[1, q -1]] and computes the point Y = yP . Bob's public key is Y and his secret key is y.

Signing and controlling algorithm

Sign: Given a message m ∈ {0, 1} * , Alice picks at random r ∈ {0, 1} nr and computes the point

σ = a 1 a 2 (a 2 + h(m||r))
H(m||r).

The convertible undeniable signature of the message m is (σ, r).

Control: Given a message m and a putative signature (σ, r), Alice checks that e(σ, P 2 + h(m||r)P ) = e(H(m||r), P 1 ) a2 .

Confirmation / Denial protocols

Confirm: Given a message m and a signature (σ, r), Alice can confirm (σ, r) with the following interactive proof of knowledge:

P K(a 2 : e(σ, P 2 + h(m||r)P ) = e(H(m||r), P 1 ) a2 ∧ P 2 = a 2 P ).

Deny: Given a message m and an invalid signature (σ, r), Alice can deny (σ, r) with the following interactive proof of knowledge:

P K(a 2 : e(σ, P 2 + h(m||r)P ) = e(H(m||r), P 1 ) a2 ∧ P 2 = a 2 P ).

Receipt generation and verification

Convert

-On input , Alice publishes the point I = a 1 a 2 P .

-Given a message m ∈ {0, 1} * and a putative signature (σ, r) on m, Alice checks the validity of the signature thanks to the Control algorithm and then computes the point σ = a 2 H(m||r) ∈ G. The individual receipt with respect to σ is σ.

Verify:

-The validity of the universal receipt I is decided by verifying that e(P 1 , P 2 ) = e(I, P ).

If it is valid, given a signature (σ, r) on a message m ∈ {0, 1} * and I, everyone checks the validity of this signature by verifying that e(σ, P 2 + h(m||r)P ) = e(H(m||r), I).

-Given a message m ∈ {0, 1} * , a putative signature (σ, r) on m and a putative individual receipt σ on (σ, r), the validity of the receipt is decided by checking whether e(σ, P ) = e(P 2 , H(m||r))

or not. If σ is valid, then the validity of (σ, r) is decided by checking whether e(σ, P 2 + h(m||r)P ) = e(σ, P 1 ) or not.

Remark 3. Note that the designated verifier interactive proofs used in the confirm/deny protocols can be made non-interactive using the Fiat-Shamir paradigm (at the expense of the use of another random oracle). In addition, the scheme will gain in efficiency since the overall communication complexity will be reduced.

Remark 4 (Efficiency considerations).

Comparing with previous convertible undeniable signature schemes, CUSBM has a number of advantages. The signature only consists in an element of G and some additional random salt. In practise, the size of an element of G can be reduced by a factor 2 with compression techniques and the random salt has size n r = 60. Therefore, the size of the signature is only 231 bits. Furthermore, a receipt (individual and universal) is also an element of G, and therefore has bit size 171. From an efficiency point of view, the signature generation and the individual and universal receipts generation algorithms require only one exponentiation as the most expensive operation. Unfortunately, it turns out that the signature verification is slightly more time consuming, as it requires 2 pairing evaluations.

A time-selective convertible undeniable signature scheme: TSCUSBM

TSCUSBM is a time-selective convertible undeniable signature scheme which is a variant of CUSBM.

Setup and Key Generation

TSCUSBM.Setup = CUSBM.Setup SKeyGen: Alice picks randomly two integers a 1 , a 2 ∈ [[1, q -1]], and computes the points P 1 = a 1 P and P 2 = a 2 P . She chooses a number of time periods T ∈ N. Alice's public key is the pair (P 1 , P 2 , T ) and her secret key is (a 1 , a 2 ). TSCUSBM.VKeyGen= CUSBM.VKeyGen

Signing and controlling algorithm

Sign: Given a message m ∈ {0, 1} * and a time period t, Alice picks at random r ∈ {0, 1} nr and computes the point σ = a 1 a t 2 (a 2 + h(m||r)) -1 H(m||r). The signature of the message m is (σ, r, t). Control: Given a message m and a putative signature (σ, r, t), Alice checks that e(σ, P 2 + h(m||r)P ) = e(H(m||r), P 1 ) a t 2 .

Confirmation / Denial protocols

Confirm: Given a message m and a signature (σ, r, t), Alice can confirm (σ, r, t) with the following interactive proof of knowledge:

P K(a 2 : e(σ, P 2 + h(m||r)P ) = e(H(m||r), P 1 ) a t 2 ∧ P 2 = a 2 P ).

Deny: Given a message m and an invalid signature (σ, r, t), Alice can deny (σ, r, t) with the following interactive proof of knowledge:

P K(a 2 : e(σ, P 2 + h(m||r)P ) = e(H(m||r), P 1 ) a t 2 ∧ P 2 = a 2 P ).

Receipt generation and verification

Convert:

-On input , and an integer t ∈ [[1, T ]], this protocol consists for Alice in publishing the t-tuple

I t = (a 1 a 2 P, a 1 a 2 2 P, . . . , a 1 a t 2 P ) ∈ G t .
-Given an integer t ∈ [[1, T ]], a message m ∈ {0, 1} * , a putative signature (σ, r) on m for the time period t, Alice checks the validity of the signature thanks to the Control algorithm and then computes the t-tuple σ = (a 2 H(m||r), a 2 2 H(m||r), . . . , a t 2 H(m||r)). The individual receipt with respect to σ is σ.

Verify

-Given an integer t ∈ [[1, T ]], the validity of the universal receipt I t = (I (1) , . . . , I (t) ) is decided by verifying that e(P 1 , P 2 ) = e(I (1) , P ) and e(I (i-1) , P 2 ) = e(I (i) , P

) for i ∈ [[2, t]].
If it is valid, given a signature (σ, r) on a message m ∈ {0, 1} * for a time period t ≤ t and I t , everyone checks the validity of this signature by verifying that e(σ, P 2 + h(m||r)P ) = e(H(m||r), I (t ) ).

-Given an integer t ∈ [[1, T ]], a message m ∈ {0, 1} * , a putative signature (σ, r) on m for the time period t and a putative individual receipt σ = (σ (1) , . . . , σ(t) ) on (σ, r), the validity of the receipt is decided by checking whether e(σ (1) , P ) = e(P 2 , H(m||r)) and e(σ (i) , P ) = e(P 2 , σ(i-1) ) for i ∈ [[2, t]] or not. If σ is valid, then the validity of (σ, r) is decided by checking whether e(σ, P 2 + h(m||r)P ) = e(σ (t) , P 1 )

or not.

Remark 5. In a sequential use of these signatures (i.e. signatures for the time period t are individually converted only after the publication of I t-1 ), the verification processes can be considerably improved (as in the CUSBM scheme). Otherwise, the signer's operations are still efficient, but the verifier has more computations to perform. The scheme remains nevertheless reasonable.

An improved scheme with logarithmic size of the receipts: TSCUSBM+

To reduce the size of the receipts, we adapt an idea of Bresson and Stern from [START_REF] Bresson | Proofs of Knowledge for Non-Monotone Discrete-Log Formulae and Applications[END_REF], and therefore we reach a logarithmic size of the receipts. The technique is essentially similar to a "double-and-add" algorithm and is described in the following figures. The whole TSCUSBM+ scheme is the same as TSCUSBM but the two following procedures which must be modified using the ReceiptGen and ReceiptVerif of the Fig. 5 and described below: TSCUSBM+.Convert:

-On input , and an integer t ∈ [[1, T ]], this protocol consists for Alice running ReceiptGen(P 1 , a 2 , t).

-Given an integer t ∈ [[1, T ]], a message m ∈ {0, 1} * , a putative signature (σ, r) on m for the time period t, Alice checks the validity of the signature thanks to the Control algorithm and then runs ReceiptGen(H(m||r), a 2 , t).

TSCUSBM+.Verify

-Given an integer t ∈ [[1, T ]], the validity of the universal receipt I t = (I (1) , . . . , I (t) ) is decided by running ReceiptVerif(P 1 , P 2 , t, I t ) and checking that e(σ, P 2 + h(m||r)P ) = e(H(m||r), I (t) ).

-Given an integer t ∈ [[1, T ]], a message m ∈ {0, 1} * , a putative signature (σ, r) on m for the time period t and a putative individual receipt σ = (σ (1) , . . . , σ(t) ) on (σ, r), the validity of the receipt is decided by running ReceiptVerif(H(m||r), P 2 , t, σ). If σ is valid, then the validity of (σ, r) is decided by checking whether e(σ, P 2 + h(m||r)P ) = e(σ (t) , P 1 )

or not.

5 Security results

Unforgeability

The theorem below states that TSCUSBM is EF-CMA secure assuming the intractability of the CDH problem in the random oracle model (we replace the hash function H by random oracle H; there is no need to do ideal assumptions on h).

Theorem 1 (Unforgeability of TSCUSBM). Let Gen be a prime-order-BDH-parameter-generator, let f r : N → N and let A be an EF-CMA-adversary against TSCUSBM in the random oracle model, that produces an existential forgery with probability ε = Succ ef-cma TSCUSBM,A , within time τ , making q H , q Σ and

ReceiptGen Input P, Q, v, t Output T [λ -1 , . . . , λ 0 ] ← BinaryExpansion(t) i ← -1 α ← 1 while i ≥ 0 do α ← α 2 mod q R i ← αQ if λ i = 1 then α ← α • v mod q S i ← αQ else S i ← ε i ← i -1 It ← [(R -1 , S -1 ), . . . , (R 0 , S 0 )] ReceiptVerif Input P, Q, V , t,
and [(R -1 , S -1 ), . . . , (R 0 , S q Υ queries to the random oracle, to the signing oracle and to the receipt generating oracle. Then there exist ε ∈ [0, 1] and τ ∈ N verifying

0 )] Output b [λ -1 , . . . , λ 0 ] ← BinaryExpansion(t) i ← -1 ; S 0 ← Q b ← Valid while i ≥ 0 do A ← e(R i , Q) if S i-1 = ε then B ← e(R i-1 , R i-1 ) else B ← e(S i-1 , S i-1 ) if A = B then b ← Invalid if λ i = 1 then A ← e(S i , Q) B ← e(R i , S 0 ) if A = B then b ← Invalid
ε ≥ ε - q Σ (q H + q Σ ) 2 nr τ ≤ τ + (q H + q Σ + O(1))T Exp-G + (q Σ + O(1))T Exp-q
such that CDH can be solved with probability ε , within time τ , and where T Exp-G (resp. T Exp-q ) denotes the time for an exponentiation in G (resp. modulo q) and n r = f r (k).

Proof: The proof is very similar to Boneh, Lynn and Shacham's unforgeability proof in [START_REF] Boneh | Short Signatures from the Weil Pairing[END_REF]. We define a sequence of games Game 0 , . . . , Game 3 starting from the actual EF-CMA adversary A and modify it step by step, until we reach a final game whose success probability has an upper bound related to solving CDH. All the games operate on the same underlying probability space: the public and private keys of the signature scheme, the coin tosses of the adversary A and the random oracle H. Let k be a security parameter, let (q, P, G, H, e) be a 5-tuple generated by Gen(k) and let (X, Y ) be a random instance of the CDH problem.

Game 0 We consider an EF-CMA-adversary A with success Succ ef-cma TSCUSBM,A , within time τ . The key generation algorithm is run and produces a pair of keys (pk, sk, T ). The universal receipt generation algorithm produces the information (I 1 , . . . , I T ). The adversary A is fed with pk and (I 1 , . . . , I T ) and, querying the random oracle H, the signing oracle Σ, and the receipt generating oracle Υ, outputs a couple (m , (σ , r , t )). We denote by q H , q Σ and q Υ the number of queries from the random oracle H, from the signing oracle Σ and from the receipt generating oracle Υ. The only requirement is that the output signature (σ , r , t ) has not been obtained from the signing oracle. For a signing query on a message m, we first ask an hash value of m with some additional random salt r and when the adversary outputs its forgery (m , (σ , r , t )), we ask a hash value of (m , r ). Therefore at most q H + q Σ + 1 queries are asked to the hash oracle during this game.

In any Game j , we denote by Forge j the event TSCUSBM.UVerify(m , (σ , r , t ), pk, I T ) = 1.

By definition, we have Pr[Forge 0 ] = Succ ef-cma TSCUSBM,A . Game 1 In this game, we pick an element a 2 ∈ [[1, q -1]] at random, and we modify the simulation by replacing pk by (X, a 2 P ) and the T -tuple (I 1 , . . . , I T ) by (a 2 X, a 2 2 X, . . . , a T 2 X). The distribution of pk is unchanged since (X, Y ) is a random instance of the CDH problem and a 2 is picked at random. From now on, thanks to the knowledge of a Game 3 In this game, we simulate the signing oracle Σ: for any message m, whose signature is queried for the time period t, we pick at random two elements r ∈ {0, 1} nr , v ∈ [[1, q -1]], and compute σ = a t 2 v(a 2 + h(m||r)) -1 X. If the H-List includes a quadruple (m, r, ?, ?) we abort the simulation, else we store (m, r, v, vP ) in the H-List and output σ as the signature. As we abort with probability at most (q H + q Σ )2 -nr , summing up the inequalities for all signature queries, we have

|Pr[Forge 3 ] -Pr[Forge 2 ]| ≤ q Σ (q H + q Σ )2 -nr .
When the game Game 3 terminates, outputting a valid pair message/signature (m , (σ , r , t )), by definition of existential forgery, the H-List includes a quadruple (m , r , u , Q ) with Q = (a 2 + h(m||r))u Y . By the simulation, we have e(σ , P 2 + h(m||r)P ) = e(Q , a t 2 P 1 ), and the point R = (u a t 2 ) -1 σ is a solution to our instance of the Computational Diffie-Hellman Problem. This concludes the proof. Remark 6. In order to shorten the public keys, we can modify the key generation of CUSBM as follows : the key generation algorithm produces a public/private pair of keys (aP, a). This variant of CUSBM (setting a 1 = a 2 = a) is unforgeable under the -CAA [START_REF] Mitsunari | A New Traitor Tracing[END_REF] assumption.

Anonymity

The next theorem claims TSCUSBM's anonymity against a chosen message attack under the ( , T )-xyz-DCAA assumption in the random oracle model (the hash functions h and H are replaced by random oracles h and H):

Theorem 2 (Anonymity of TSCUSBM). Let Gen be a prime-order-BDH-parameter-generator, let f r : N → N and let A be an Ano-CMA-adversary against TSCUSBM in the random oracle model, that breaks anonymity with advantage Adv ano-cma TSCUSBM,A , within time τ , making q H , q h , q Σ and q Υ queries to the random oracles, to the signing oracles and to the receipt generating oracles. Then there exist T

∈ N, ε ∈ [0, 1] and τ ∈ N verifying ε ≥ ε 2 - (q Σ + 1)(q H + q h ) 2 nr-1 - 1 2 k τ ≤ τ + (q H + 2q Σ + T q Υ + O(1))T Exp-G + (q Σ + T q Υ + O(1))T Exp-q
such that (q H , T )-xyz-DCAA can be solved with probability ε , within time τ , and where T Exp-G (resp. T Exp-q ) denotes the time for an exponentiation in G (resp. modulo q) and n r = f r (k).

Proof: Our method of proof is inspired by Shoup [START_REF]OAEP Reconsidered[END_REF]: we define a sequence of games Game 0 , . . . , Game 5 starting from the actual Ano-CMA adversary A and modify it step by step, until we reach a final game whose success probability has an upper bound related to solving the (q H , T )-xyz-DCAA problem. All the games operate on the same underlying probability space: the public and private keys of the signature scheme, the coin tosses of A and the random oracles.

Let k be a security parameter, T and be two integers and let (q, P, G, H, e) be a 5-tuple generated by Gen(k) and (

X i ) i∈[[1,2T -1]] , Y, Z, h), (R j , h j ) j∈[[1, ]] in G 2T +1 × [[1, q -1]] × (G × [[1, q - 1
]]) be a random instance of the (q H , T )-xyz-DCAA problem. We denote X 0 = P . We construct a simulation which solves this instance.

Game 0 We consider an Ano-CMA-adversary A with advantage Adv ano-cma TSCUSBM,A (k), within time τ . The key generation algorithm is run twice and produces the following pairs of keys (sk 0 , pk 0 , T 0 ), and (sk 1 , pk 1 , T 1 ). The adversary A is fed with pk 0 , pk 1 , T 0 and T 1 and, querying the random oracles H and h, the signing oracles Σ 0 and Σ 1 , and the receipt generating oracles Υ 0 and Υ 1 , outputs a message m and a time period t ∈ [[1, min(T 0 , T 1 )]]. A challenge signature is then produced by flipping a coin b ∈ {0, 1} and signing the message under the key sk b . The adversary is given this challenge signature (σ , r , t ), and outputs a bit b at the end of the guess stage.

We denote by q H , q h , q Σ , and q Υ the number of queries from the random oracles, from the signing oracles, and from the receipt generating oracles and we assume that T ≥ min(T 0 , T 1 ) and q Σ ≤ . The only requirement is that the challenge signature (σ , r , t ) cannot be queried to a receipt generating oracle.

In any game Game i , we denote by Guess i the event b = b. By definition, to the oracle H, we pick at random s ∈ [[1, q -1]], compute sP ∈ G, store (m, r, s, sP, T ) in the H-List and return sP as the answer to the oracle call; to the oracle h, we pick at random u ∈ [[1, q -1]], store (m, r, u) in the h-List and returns u as the answer to the oracle call.

|2 Pr[Guess 0 ] -1| = Adv ano-cma TSCUSBM,A (k). Game 1 First, we pick (α, β) ∈ [[1, q -1]]
In the random oracle model, this game is clearly identical to the previous one. Hence, we obtain If the query is to Σ 0 , the signature is (sR i , r, t), we refresh the h-List with (m, r, h i ), then we increment the counter. If the query is to Σ 1 the signature is (sα t-1 βR i , r, t), we refresh the h-List with (m, r, αh i ), then we increment the counter. This game perfectly simulates the signing oracle if we do not abort. As we abort with probability at most (q H + q h )2 Game 5 Finally, in this game, in the challenge generation: once the adversary A asks for a signature on a message m for a time period t , we query the problem challenger with t . It outputs (Y j ) j∈[[1,t -1]] ∈ G t -1 and Q ∈ G. We pick a bit b ∈ {0, 1} and r ∈ {0, 1} nr at random. If there exists a 5-tuple (m , r , ?, ?, ?) in the H-List or a triple (m , r , ?) in the h-List, we abort the simulation, else we update the H-List by storing (m , r , ⊥, Z, ⊥) and the h-List by storing (m, r, α b h). We output ((α t -1 β) b Q, r , t ) as the challenge signature and (Y j ) j∈[[1,t -1]] as the universal receipts for the challenge..

Control: Given a message m and a putative signature (σ, r), Alice checks that e(σ, P )e(H 1 (m, r), -P 1 ) = e(H 0 (m||r), P 1 ) a2 .

Confirmation / Denial protocols Confirm: Given a message m and a signature (σ, r), Alice can confirm (σ, r) with the following interactive proof of knowledge:

P K(a 2 : e(σ, P )e(H 1 (m, r), -P 1 ) = e(H 0 (m||r), P 1 ) a2 ∧ P 2 = a 2 P ).

Deny: Given a message m and an invalid signature (σ, r), Alice can deny (σ, r) with the following interactive proof of knowledge:

P K(a 2 : e(σ, P )e(H 1 (m, r), -P 1 ) = e(H 0 (m||r), P 1 ) a2 ∧ P 2 = a 2 P ).

Receipt generation and verification Convert

-On input , Alice publishes the point I = a 1 a 2 P .

-Given a message m ∈ {0, 1} * and a putative signature (σ, r) on m, Alice checks the validity of the signature thanks to the Control algorithm and then computes the point σ = a 2 H 0 (m||r) ∈ G. The individual receipt with respect to σ is σ.

Verify:

-The validity of the universal receipt I is decided by verifying that e(P 1 , P 2 ) = e(I, P ).

If it is valid, given a signature (σ, r) on a message m ∈ {0, 1} * and I, everyone checks the validity of this signature by verifying that e(σ, P )e(H 1 (m, r), -P 1 ) = e(H 0 (m||r), I).

-Given a message m ∈ {0, 1} * , a putative signature (σ, r) on m and a putative individual receipt σ on (σ, r), the validity of the receipt is decided by checking whether e(σ, P ) = e(P 2 , H 0 (m||r))

or not. If σ is valid, then the validity of (σ, r) is decided by checking whether e(σ, P )e(H 1 (m, r), -P 1 ) = e(σ, P 2 ) or not.

To obtain a logarithmic size of the time-selective receipts, the following procedures must be included: Sign: Given a message m ∈ {0, 1} * , and a time period t ∈ [ [1, T ]]. Alice picks at random r ∈ {0, 1} nr and computes the point σ = (a 1 a t 2 )H 0 (m||r) + a 1 H 1 (m||r). The convertible undeniable signature of the message m is (σ, r). Convert -On input , and an integer t ∈ [[1, T ]], this protocol consists for Alice running ReceiptGen(P 1 , a 2 , t).

-Given an integer t ∈ [[1, T ]], a message m ∈ {0, 1} * , a putative signature (σ, r) on m for the time period t, Alice checks the validity of the signature thanks to the Control algorithm and then runs ReceiptGen(H(m||r), a 2 , t).

Figure 1 :

 1 Figure 1: Designated verifier proof of membership in EDL(G, H) -Prove protocol

Figure 2 :

 2 Figure 2: Designated verifier proof of membership in EDL(G, H) -Fake protocol

Figure 3 :

 3 Figure 3: Designated verifier proof of membership in IDL(G, H) -Prove protocol

2 1 Figure 4 :

 14 Figure 4: Designated verifier proof of membership in IDL(G, H) -Fake protocol

Figure 5 :

 5 Figure 5: Description of ReceiptGen and ReceiptVerif

  Under the CDH assumption, the schemes CUSBM and TSCUSBM+ are EF-CMA secure in the random oracle model.

Pr[Guess 2 ]Game 3

 23 = Pr[Guess 1 ]. Now we simulate the signing oracles. We initialise a counter to i = 1, and for each new request m ∈ {0, 1} * , t ∈ [[1, T ]] we pick r ∈ {0, 1} nr at random. If there exists a triple (m, r, ?) in the h-List or a 5-tuple (m, r, ?, ?, ?) in the H-List, we abort the simulation. We pick at random s ∈ [[1, q -1]], compute sX T -t ∈ G and store (m, r, s, sX T -t , t) in the H-List.

  2 , we can simulate the receipt generating oracle Υ. We have Pr[Forge 1 ] = Pr[Forge 0 ]. Game 2 In this game, we simulate the random oracle H. For any fresh query (m, r) ∈ {0, 1} * × {0, 1} nr to the oracle H, we pick at random u ∈ [[1, q -1]] and compute Q = (a 2 + h(m||r))uY . We store (m, r, u, Q) in the H-List and return Q as the answer to the oracle call. In the random oracle model, this game is clearly identical to the previous one. Hence, we get Pr[Forge 2 ] = Pr[Forge 1 ].

  2 at random and modify the simulation by replacing pk 0 by (X 1 , Y 1 ) and pk 1 by (αX 1 , βY 1 ). The distributions of pk 0 and pk 1 are unchanged since we consider a random instance of the (q H , T )-xyz-DCAA problem. Therefore we havePr[Guess 1 ] = Pr[Guess 0 ].Game 2 In this game, we simulate the random oracles H and h and maintain appropriate lists, which we denote by H-List and h-List. For any fresh query (m, r) ∈ {0, 1} * × {0, 1} nr

  -nr , we have|Pr[Guess 3 ] -Pr[Guess 2 ]| ≤ q Σ (q H + q h ) 2 nrGame 4 We simulate the receipt generating oracles. When the adversary requests a couple message/putative signature (m, (σ, r, t)) on m to Υ 0 with t ∈ [[1, T ]], we look in the H-List for a 5-tuple (m, r, s, sX T -t , t ), then the answer is the t-tuple (sX T -t +1 , . . . , sX T -t +t ). If this request is on Υ 1 , we answer with (sα T -t +1 X T -t +1 , . . . , sα T -t +t X T -t +t ) This simulation is perfect, therefore we have Pr[Guess 4 ] = Pr[Guess 3 ].

The security of the scheme from[START_REF] Michels | Breaking and Repairing a Convertible Undeniable Signature Scheme[END_REF] has recently been established in the generic group model[START_REF] Aimani | Gradually Convertible Undeniable Signatures[END_REF].

In[START_REF] Laguillaumie | Time-Selective Convertible Undeniable Signatures[END_REF], the assumption underlying the anonymity property was interactive.

It is often necessary to require the security of the schemes even if the adversary is the key registration centre. In this case, one must replace the proof of knowledge associated to the key registration by a zero-knowledge one[START_REF] Ristenpart | The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks[END_REF].

a.k.a. the Triffie-Hellman problem

collusion attack algorithm with traitors

Acknowledgements We express our gratitude to Pascal Paillier for his helpful comments.

If Q = Q real = x T yz(x + h) -1 P , this game perfectly simulates the challenge generation if we do not abort (which happens with probability at most (q H + q h )2 -nr ). Therefore

If Q = Q random is a random element from G, the adversary gains no information on b, in an information theoretic sense, therefore

The last term accounts for the probability that Q random = Q real . By definition, the advantage in the Game 5 simulation in solving the (q H , T ) -xyz-DCAA problem is:

A simple computation gives the claimed bounds for ε and τ .

Remark 7. Using Boneh-Boyen's technique [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF], it is possible to avoid the ideal hypothesis of perfect randomness of the hash function h.

Corollary 2 (Anonymity of CUSBM and TSCUSBM+). Under the ( , 1)-xyz-DCAA assumption, the schemes CUSBM and TSCUSBM+ are Ano-CMA secure in the random oracle model.

Final remarks and conclusion

Time-selective convertible signatures are introduced to eliminate the burden of registration of new public keys after the universal receipt publication. We formalised the security notions of a time-selective convertible undeniable signature scheme and thanks to a new technique to design cryptographic protocols achieving a tradeoff between authenticity and privacy, we proposed the first scheme meeting this definition.

The new schemes offer the advantage of issuing short signatures. Moreover, the computational costs for the signer in the signature generation, the confirmation/denial protocols and the receipt generation algorithms, are the lowest of all known convertible undeniable signature schemes.

The xyz-trick might have other applications: the use of this trick to design distributed contract signing and verifiable signature sharing protocols seems to be an interesting topic for further research.

A Time-Selective Conversion for Huang et al.'s scheme

Let's first give a rough description of Huang, Mu, Susilo and Wei's scheme from [START_REF] Huang | Provably secure pairing-based convertible undeniable signature with short signature length[END_REF].

Setup and Key Generation

Setup: Let k be a security parameter, Gen be a prime-order-BDH-parameter-generator and (q, P, G, H, e) some output of Gen(k). Let f r : N → N be a function. We denote n r = f r (k). Let [{0, 1} * × {0, 1} nr -→ G] be a hash function family, and H 0 and H 1 be two random members of this family. The public parameters are [(q, P, G, H, e), H 0 , H 1 ] SKeyGen: Alice picks randomly two integers a 1 , a 2 ∈ [[1, q -1]] and computes the points P 1 = a 1 P and P 2 = a 2 P . Alice's public key is the pair (P 1 , P 2 ) and her secret key is (a 1 , a 2 ). VKeyGen: the verifier Bob picks randomly an integer y ∈ [[1, q -1]] and computes the point Y = yP . Bob's public key is Y and his secret key is y.

Signing and controlling algorithm

Sign: Given a message m ∈ {0, 1} * , Alice picks at random r ∈ {0, 1} nr and computes the point σ = (a 1 a 2 )H 0 (m||r) + a 1 H 1 (m||r).

The convertible undeniable signature of the message m is (σ, r).