Benoît Libert
email: benoit.libert@gmail.com

Joye Marc
email: marc.joye@technicolor.com

Moti Yung

Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively-Secure Threshold Signatures with Short Shares

Keywords: Threshold signatures, fully distributed schemes, non-interactivity, adaptive security, efficiency, availability, fault tolerance, distributed key generation, erasure-freeness

Threshold cryptography is a fundamental distributed computational paradigm for enhancing the availability and the security of cryptographic public-key schemes. It does it by dividing private keys into n shares handed out to distinct servers. In threshold signature schemes, a set of at least t + 1 ≤ n servers is needed to produce a valid digital signature. Availability is assured by the fact that any subset of t + 1 servers can produce a signature when authorized. At the same time, the scheme should remain robust (in the fault tolerance sense) and unforgeable (cryptographically) against up to t corrupted servers; i.e., it adds quorum control to traditional cryptographic services and introduces redundancy. Originally, most practical threshold signatures have a number of demerits: They have been analyzed in a static corruption model (where the set of corrupted servers is fixed at the very beginning of the attack); they require interaction; they assume a trusted dealer in the key generation phase (so that the system is not fully distributed); or they suffer from certain overheads in terms of storage (large share sizes). In this paper, we construct practical fully distributed (the private key is born distributed), non-interactive schemes -where the servers can compute their partial signatures without communication with other servers-with adaptive security (i.e., the adversary corrupts servers dynamically based on its full view of the history of the system). Our schemes are very efficient in terms of computation, communication, and scalable storage (with private key shares of size O(1), where certain solutions incur O(n) storage costs at each server). Unlike other adaptively secure schemes, our schemes are erasure-free (reliable erasure is hard to assure and hard to administer properly in actual systems). To the best of our knowledge, such a fully distributed highly constrained scheme has been an open problem in the area. In particular, and of special interest, is the fact that Pedersen's traditional distributed key generation (DKG) protocol can be safely employed in the initial key generation phase when the system is born -although it is well-known not to ensure uniformly distributed public keys. An advantage of this is that this protocol only takes one round optimistically (in the absence of faulty player).

Introduction

Threshold cryptography [START_REF] Desmedt | Society and group oriented cryptography: A new concept[END_REF][START_REF] Desmedt | Threshold cryptosystems[END_REF][START_REF] Boyd | Digital Multisignatures[END_REF][START_REF] Santis | How to share a function securely[END_REF] is a paradigm where cryptographic keys are divided into n > 1 shares to be stored by distinct servers, which increases the system's availability and resilience to failures. In (t, n)-threshold cryptosystems, private-key operations require the cooperation of at least t +1 out of n servers (any subset is good). By doing so, the system remains secure against adversaries that break into up to t servers. (The mechanism can be viewed as extending Shamir's secret sharing of one value [START_REF] Shamir | How to share a secret[END_REF] to sharing of the capability to apply cryptographic function efficiently.) The public-key portion of the function (e.g., signature verification key) does not change from its usual format.

Threshold primitives are widely used in distributed protocols. Threshold homomorphic encryption schemes are utilized in voting systems (see, e.g., [START_REF] Cramer | Multi-autority secret-ballot elections with linear work[END_REF][START_REF] Cramer | A secure and optimally efficient multi-authority election scheme[END_REF]) and multiparty computation protocols [START_REF] Cramer | Multiparty computation from threshold homomorphic encryption[END_REF]. Threshold signatures enhance the security of highly sensitive private keys, like those of certification authorities (e.g., [18]). They can also serve as tools for distributed storage systems [START_REF] Kubiatowicz | OceanStore: An architecture for global-scale persistent storage[END_REF][START_REF] Rhea | Pond: The OceanStore prototype[END_REF]. RSA and Elgamal-type constructions have been at the core of many threshold protocols the last two decades (see, e.g., [START_REF] Santis | How to share a function securely[END_REF][START_REF] Gennaro | Robust threshold DSS signatures[END_REF][START_REF] Gennaro | Robust and efficient sharing of RSA functions[END_REF][START_REF] Herzberg | Proactive public key and signature systems[END_REF]). A fully distributed public-key system is one where the public (and the distributed private) keys are jointly generated by the same servers which end up holding the private key's shares (e.g., via a threshold secret sharing [START_REF] Shamir | How to share a secret[END_REF]). Efficient distributed key generation (DKG) protocols were put forth for both RSA [START_REF] Boneh | Efficient Generation of shared RSA keys[END_REF][START_REF] Frankel | Robust efficient distributed RSA-key generation[END_REF][START_REF] Fouque | Fully Distributed Threshold RSA under standard assumptions[END_REF][START_REF] Damgård | Efficient, robust and constant-round distributed RSA key generation[END_REF] and discrete-logarithm-based systems [START_REF] Pedersen | A threshold cryptosystem without a trusted party[END_REF][START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF][START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Canetti | Adaptive security for threshold cryptosystems[END_REF][START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF].

Non-Interactive Threshold Signatures. For a long time, RSA-based threshold signatures have been the only solutions to enable non-interactive distributed signature generation. By "noninteractive", we mean that each server can compute its own partial signature without any online conversation with other servers: each server should send a single message to an entity, called combiner, which gathers the signature shares so as to obtain a full signature. Unlike threshold versions of Schnorr and DSA signatures [START_REF] Gennaro | Secure applications of Pedersen's distributed key generation protocol[END_REF][START_REF] Gennaro | Robust threshold DSS signatures[END_REF], threshold RSA signatures are well-suited to non-interactive signing protocols as they are deterministic. Hence, they do not require the servers to jointly generate a randomized signature component in a first round before starting a second round. Practical robust noninteractive threshold signatures were described by Shoup [START_REF] Shoup | Practical threshold signatures[END_REF] under the RSA assumption and by Katz and Yung [START_REF] Katz | Threshold cryptosystems based on factoring[END_REF] assuming the hardness of factoring. Boldyreva [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF] showed a threshold version of Boneh-Lynn-Shacham signatures [START_REF] Boneh | Short signatures from the Weil pairing[END_REF], which provided an alternative non-interactive scheme with robustness and short signatures. The latter construction [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF] was subsequently generalized by Wee [START_REF] Wee | Threshold and revocation cryptosystems via extractable hash proofs[END_REF]. These solutions are only known to resist static attacks, where the set of corrupted servers is chosen by the adversary at the very beginning of the attack, before even seeing the public key.

Adaptive Corruptions. More realistically than the static model, the adaptive corruption model allows adversaries to choose whom to corrupt at any time, based on their entire view so far. Adaptive adversaries are known to be strictly (see, e.g., [START_REF] Cramer | Efficient multi-party computations secure against an adaptive adversary[END_REF]) stronger. The first adaptively secure threshold signatures were independently described in 1999 by Canetti et al. [START_REF] Canetti | Adaptive security for threshold cryptosystems[END_REF] and by Frankel et al. [START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Frankel | Adaptively-secure optimal-resilience proactive RSA[END_REF]. These constructions rely on a technique, called "single inconsistent player" (SIP), which inherently requires interaction. The SIP technique basically consists in converting a t-out-of-n secret sharing into a t-out-of-t secret sharing in such a way that, in the latter case, there is only one server whose internal state cannot be consistently revealed to the adversary. Since this player is chosen at random by the simulator among the n severs, it is only corrupted with probability less than 1/2 and, upon this undesirable event, the simulator can simply rewind the adversary back to one of its previous states. After this backtracking operation, the simulator uses different random coins to simulate the view of the adversary, hoping that the inconsistent player will not be corrupted again (and the expected number of rewinding-s is bounded by 2).

Jarecki and Lysyanskaya [START_REF] Jarecki | Adaptively secure threshold cryptography: Introducing concurrency, removing erasures[END_REF] extended the SIP technique in order to eliminate the need for servers to reliably erase intermediate computation results. However, their adaptively secure version of the Canetti-Goldwasser threshold cryptosystem [START_REF] Canetti | An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack[END_REF] requires a substantial amount of interaction at each private-key operation. The same holds for the adaptively secure threshold signatures of Lysyanskaya and Peikert [START_REF] Lysyanskaya | Adaptive security in the threshold setting: From cryptosystems to signature schemes[END_REF] and the universally composable protocols of Abe and Fehr [START_REF] Abe | Adaptively secure Feldman VSS and applications to universally-composable threshold cryptography[END_REF].

In 2006, Almansa, Damgård and Nielsen [START_REF] Almansa | Simplified threshold RSA with adaptive and proactive security[END_REF] showed a variant of Rabin's threshold RSA signatures [START_REF] Rabin | A simplified approach to threshold and proactive RSA[END_REF] and proved them adaptively secure using the SIP technique and ideas from [START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Frankel | Adaptively-secure optimal-resilience proactive RSA[END_REF]. Similar techniques were used in [START_REF] Wang | Adaptively secure threshold signature scheme in the standard model[END_REF] to construct adaptively secure threshold Waters signatures [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF]. While the SIP technique provides adaptively secure threshold signatures based on RSA or the Diffie-Hellman assumption, these fall short of minimizing the amount of interaction. The constructions of [START_REF] Frankel | Adaptively-secure distributed public-key systems[END_REF][START_REF] Frankel | Adaptively-secure optimal-resilience proactive RSA[END_REF] proceed by turning a (t, n) polynomial secret sharing into a (t, t) additive secret sharing by first selecting a pool of at least t participants. However, if only one of these fails to provide a valid contribution to the signing process, the whole protocol must be restarted from scratch. The protocol of Almansa et al. [START_REF] Almansa | Simplified threshold RSA with adaptive and proactive security[END_REF] is slightly different in that; like [START_REF] Rabin | A simplified approach to threshold and proactive RSA[END_REF], it proceeds by sharing an RSA private key in an additive (n, n) fashion (i.e., the private RSA exponent d is split into shares d 1 , . . . , d n such that d = n i=1 d i ). In turn, each additive share d i is shared in a (t, n) fashion using a polynomial verifiable secret sharing and each share d i,j of d i is distributed to another server j. This is done in such a way that, if one participant fails to provide a valid RSA signature share H(M ) d i , the missing signature share can be re-constructed by running the reconstruction algorithm of the verifiable secret sharing scheme that was used to share d i . The first drawback of this approach is that it is only non-interactive when all players are honest as a second round is needed to reconstruct missing multiplicative signature shares H(M ) d i . Another disadvantage is that players have to store Θ(n) values, where n is the number of servers, as each player has to store a polynomial share of other players' additive share. Ideally, we would like a solution where each player only stores O(1) elements, regardless of the number of players.

Recently, Libert and Yung [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF][START_REF] Libert | Non-interactive CCA2-secure threshold cryptosystems with adaptive security: New framework and constructions[END_REF] gave several constructions of adaptively secure threshold encryption schemes with chosen-ciphertext security. They also suggested an adaptively secure and non-interactive threshold variant [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF] of a signature scheme due to Lewko and Waters [START_REF] Lewko | New techniques for dual system encryption and fully secure HIBE with short ciphertexts[END_REF]. The use of bilinear maps in composite order groups makes the scheme of [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF] expensive when it comes to verifying signatures: as discussed by Freeman [START_REF] Freeman | Converting pairing-based cryptosystems from composite-order groups to prime-order groups[END_REF], computing a bilinear map in composite order groups is at least 50 times slower than evaluating the same bilinear map in prime-order groups at the 80-bit security level (things can only get worse at higher security levels). The techniques of Lewko [START_REF] Lewko | Tools for simulating features of composite order bilinear groups in the prime order setting[END_REF] can be used to adapt the construction of [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF] to the setting of prime-order groups. In the resulting construction, each signature consists of 6 group elements. The use of asymmetric bilinear maps (see [START_REF] Chen | Shorter IBE and signatures via asymmetric pairings[END_REF]) allows reducing the signature size to 4 group elements. Unfortunately, the techniques of [START_REF] Lewko | Tools for simulating features of composite order bilinear groups in the prime order setting[END_REF][START_REF] Chen | Shorter IBE and signatures via asymmetric pairings[END_REF] assume a trusted dealer and, if implemented in a distributed manner, their key generation phase is likely to be communication-expensive (resorting to generic multiparty secure computations). In particular, they seem hardly compatible with a round-optimal DKG protocol. The reason is that [START_REF] Chen | Shorter IBE and signatures via asymmetric pairings[END_REF] requires to generate public keys containing pairs of matrices of the form g A ∈ G n×n and g A -1 ∈ G n×n , for some matrix A ∈ Z n×n p , and it is not clear how these non-linear operations can be achieved in a round-optimal distributed manner (let alone with adaptive security). Finally, the solutions of [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF] require reliable erasures due to the use of the dual system encryption technique [START_REF] Waters | Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions[END_REF][START_REF] Lewko | New techniques for dual system encryption and fully secure HIBE with short ciphertexts[END_REF] and the existence of several distributions of partial signatures.

Our Contributions. We consider the problem of devising a fully distributed, non-interactive, robust, and adaptively secure construction which is as efficient as the centralized schemes obtained from [START_REF] Libert | Adaptively secure non-interactive threshold cryptosystems[END_REF][START_REF] Chen | Shorter IBE and signatures via asymmetric pairings[END_REF] and does not rely on erasures. In particular, we want to retain private-key shares of O(1) size, no matter how many players are involved in the protocol. Here, "fully distributed" implies that the public key is jointly generated by all players -so that no trusted dealer is needed-while guaranteeing the security of the scheme against an adaptive adversary. As mentioned above, we wish to avoid the costly and hard-to-control use of reliable erasures. This means that, whenever the adversary corrupts a player, it learns the entire history of that player.

At the same time, the distributed key generation phase should be as communication-efficient as possible. Ideally, a single communication round should be needed when the players follow the protocol. Finally, we would like to avoid interaction during the distributed signing process. To the best of our knowledge, no existing solution combines all the aforementioned highly constraining properties. We thus provide the first candidates.

Our constructions are derived from linearly homomorphic structure-preserving signatures (LH-SPS). As defined by Abe et al. [START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF][START_REF] Abe | Signing on elements in bilinear groups for modular protocol design[END_REF], structure-preserving signatures (SPS) are signature schemes where messages and public keys live in an abelian group over which a bilinear map is efficiently computable. Recently, Libert et al. [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF] considered SPS schemes with additive homomorphic properties: given signatures on linearly independent vectors of group elements, anyone can publicly compute a signature on any linear combination of these vectors. In order to sign a message M ∈ {0, 1} * in a distributed manner, our idea is to hash M onto a vector of group elements which is signed using the LHSPS scheme of [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF]. In the random oracle model, we prove that the resulting system is a secure digital signature even if the underlying LHSPS scheme satisfies a weak security definition. Since the LHSPS signing algorithm is deterministic and further presents certain homomorphic properties over the key space, the resulting signature is also amenable for non-interactive distributed signature generation. In the threshold setting, we take advantage of specific properties of the LHSPS scheme of [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF] to prove that the scheme provides security against adaptive corruptions in the absence of secure erasures.

More surprisingly, we prove that the scheme remains adaptively secure if the public key is generated using Pedersen's DKG protocol [START_REF] Pedersen | A threshold cryptosystem without a trusted party[END_REF]. The latter basically consists in having all players verifiably share a random value using Feldman's verifiable secret sharing (VSS) [START_REF] Feldman | A practical scheme for non-interactive verifiable secret sharing[END_REF] before computing the shared secret as the sum of all well-behaved players' contributions. While very efficient (as only one round is needed in the absence of faulty players), this protocol is known [START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF] not to guarantee the uniformity of the resulting public key. Indeed, even a static adversary can bias the distribution by corrupting only two players. Nonetheless, the adversary does not have much control on the distribution of the public key and Pedersen's protocol can still be safely used in some applications, as noted by Gennaro et al. [START_REF] Gennaro | Secure applications of Pedersen's distributed key generation protocol[END_REF][START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF]. For example, it was recently utilized by Cortier et al. [START_REF] Cortier | Distributed ElGamal à la Pedersen: Application to Helios[END_REF] in the context of voting protocols. However, these safe uses of Pedersen's protocol were in the static corruption setting and our scheme turns out to be its first application in an adaptive corruption model. To our knowledge, it is also the first adaptively secure threshold signature where the DKG phase takes only one round when all players follow the specifications.

As an extension of our first scheme, we describe a variant supporting signature aggregation: as suggested by Boneh et al. [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF], a set of n signatures for distinct public keys PK 1 , . . . , PK s on messages M 1 , . . . , M s can be aggregated into a single signature σ which convinces a verifier that, for each i, M i was signed by the private key underlying PK i . In the threshold setting, this property allows for de-centralized certification authorities while enabling the compression of certification chains.

As a final contribution, we give a non-interactive adaptively secure threshold signature scheme in the standard model that retains all the useful properties (including the erasure-freeness) of our first realization. In particular, Pedersen's protocol can still be used in the key generation phase if a set of uniformly random common parameters -which can be shared by many public keys-is set up beforehand. As is natural for standard-model constructions, this scheme is somewhat less efficient than its random-oracle-based counterpart but it remains sufficiently efficient for practical applications.

Like Gennaro et al. [START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF] and Cortier et al. [START_REF] Cortier | Distributed ElGamal à la Pedersen: Application to Helios[END_REF], we prove security via a direct reduction from the underlying number-theoretic assumption instead of reducing the security of our schemes to that of their centralized version. We emphasize that our proof technique is different from those of [START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF][START_REF] Cortier | Distributed ElGamal à la Pedersen: Application to Helios[END_REF], where the reduction runs Pedersen's DKG protocol on behalf of honest players and embeds a discrete logarithm instance in the contribution of honest players to the public key, using a proper simulation of Feldman's verifiable secret sharing. In the adaptive corruption setting, this would at least require an adaptively secure variant of Feldman's VSS, such as [START_REF] Abe | Adaptively secure Feldman VSS and applications to universally-composable threshold cryptography[END_REF], and thus extra communications. Instead, our reduction always faithfully runs the protocol on behalf of honest players, and thus always knows their internal state so as to perfectly answer corruption queries. Yet, we can use the adversary's forgery to break the underlying hardness assumption by taking advantage of key homomorphic properties of the scheme, which allow us to turn a forgery for the jointly generated public key -of possibly skewed distribution-into a forgery for some uniformly random key.

Background

Definitions for Threshold Signatures

A non-interactive (t, n)-threshold signature scheme consists of a tuple Σ = (Dist-Keygen, Share-Sign, Share-Verify, Verify, Combine) of efficient algorithms or protocols such that:

Dist-Keygen(params, λ, t, n): This is an interactive protocol involving n players P 1 , . . . , P n , which all take as input common public parameters params, a security parameter λ ∈ N as well as a pair of integers t, n ∈ poly(λ) such that 1 ≤ t ≤ n. The outcome of the protocol is the generation of a public key PK , a vector of private key shares SK = (SK 1 , . . . , SK n ) where P i only obtains SK i for each i ∈ {1, . . . , n}, and a public vector of verification keys VK = (VK 1 , . . . , VK n ). Share-Sign(SK i , M ): is a possibly randomized algorithm that takes in a message M and a private key share SK i . It outputs a signature share σ i . Share-Verify(PK , VK, M, (i, σ i )): is a deterministic algorithm that takes as input a message M , the public key PK , the verification key VK and a pair (i, σ i ) consisting of an index i ∈ {1, . . . , n} and signature share σ i . It outputs 1 or 0 depending on whether σ i is deemed as a valid signature share or not. Combine(PK , VK, M, {(i, σ i )} i∈S ): takes as input a public key PK , a message M and a subset S ⊂ {1, . . . , n} of size |S| = t + 1 with pairs {(i, σ i )} i∈S such that i ∈ {1, . . . , n} and σ i is a signature share. This algorithm outputs either a full signature σ or ⊥ if {(i, σ i )} i∈S contains ill-formed partial signatures. Verify(PK , M, σ): is a deterministic algorithm that takes as input a message M , the public key PK and a signature σ. It outputs 1 or 0 depending on whether σ is deemed valid share or not.

We shall use the same communication model as in, e.g., [START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF][START_REF] Gennaro | Secure applications of Pedersen's distributed key generation protocol[END_REF][START_REF] Gennaro | Secure distributed key generation for discrete-log based cryptosystems[END_REF], which is partially synchronous. Namely, communications proceed in synchronized rounds and sent messages are always received within some time bound in the same round. All players have access to a public broadcast channel, which the adversary can use as a sender and a receiver. However, the adversary cannot modify messages sent over this channel, nor prevent their delivery. In addition, we assume private and authenticated channels between all pairs of players.

In the adaptive corruption setting, the security of non-interactive threshold signatures can be defined as follows.

Definition 1. A non-interactive threshold signature scheme Σ is adaptively secure against chosenmessage attacks if no PPT adversary A has non-negligible advantage in the game hereunder. At any time, we denote by C ⊂ {1, . . . , n} and G := {1, . . . , n} \ C the dynamically evolving subsets of corrupted and honest players, respectively. Initially, we set C = ∅.

1. The game begins with an execution of the DKG protocol Dist-Keygen(params, λ, t, N ) during which the challenger plays the role of honest players P i and the adversary A is allowed to corrupt players at any time. When A chooses to corrupt a player P i , the challenger sets G = G \ {i}, C = C ∪ {i} and returns the internal state of P i . Moreover, A is allowed to act on behalf of P i from this point forward. The protocol ends with the generation of a public key PK , a vector of private key shares SK = (SK 1 , . . . , SK n ) and the corresponding verification keys VK = (VK 1 , . . . , VK n ). At the end of this phase, the public key PK and {SK i } i∈C are available to the adversary A. 2. On polynomially many occasions, A adaptively interleaves two kinds of queries.

-Corruption query: At any time, A can choose to corrupt a server. To this end, A chooses i ∈ {1, . . . , n} and the challenge returns SK i before setting G = G \ {i} and C = C ∪ {i}. -Signing query: For any i ∈ G, A can also submit a pair (i, M ) and ask for a signature share on an arbitrary message M on behalf of player P i . The challenger responds by computing σ i ← Share-Sign(SK i , M ) and returning σ to A. 3. A outputs a message M and a signature σ . We define V = C ∪ S, where S ⊂ {1, . . . , n} is the subset of players for which A made a signing query of the form (i, M ). The adversary wins if the following conditions hold: (i)

|V| < t + 1; (ii) Verify(PK , M , σ ) = 1.
A's advantage is defined as its probability of success, taken over all coin tosses.

Since we focus on non-interactive schemes, Definition 1 allows the adversary to individually query each partial signing oracle whereas usual definitions only provide the adversary with an oracle that runs the distributed signing protocol on behalf of all honest players. We also remark that Definition 1 allows the adversary to obtain some partial signatures on the forgery message M as long as its output remains a non-trivial forgery. In a weaker (but still compelling) definition, partial signing queries for M would be completely disallowed. In the following, we will stick to the stronger definition.

Hardness Assumptions

We first recall the definition of the Decision Diffie-Hellman problem.

Definition 2. In a cyclic group G of prime order p, the Decision Diffie-Hellman Problem (DDH) in G, is to distinguish the distributions (g, g a , g b , g ab ) and (g, g a , g b , g c ), with a, b, c R ← Z p . The Decision Diffie-Hellman assumption is the intractability of DDH for any PPT distinguisher.

We use bilinear maps e : G × Ĝ → G T over groups of prime order p. We will work in asymmetric pairings, where we have G = Ĝ so as to allow the DDH assumption to hold in G (see, e.g., [START_REF] Scott | Authenticated ID-based key exchange and remote log-in with simple token and PIN number[END_REF]). In certain asymmetric pairing configurations, DDH is even believed to hold in both G and Ĝ. This assumption is called Symmetric eXternal Diffie-Hellman (SXDH) assumption and it implies that no isomorphism between Ĝ and G be efficiently computable.

For convenience, we also use the following problem in asymmetric pairing configurations.

Definition 3 ([3]). The Double Pairing problem (DP) in (G, Ĝ, G T ) is, given ( ĝz , ĝr ) ∈ R Ĝ2 , to find a pair (z, r) ∈ G 2 \ {(1 G , 1 G )} that satisfies e(z, ĝz ) • e(r, ĝr ) = 1 G T .
The Double Pairing assumption asserts that the DP problem is infeasible for any PPT algorithm.

The DP problem is known [START_REF] Abe | Signing on elements in bilinear groups for modular protocol design[END_REF] to be at least as hard as DDH in Ĝ. Given ( ĝz , ĝr , ĝz θ 1 , ĝr θ 2 ), a solution (z, r) allows deciding whether θ 1 = θ 2 or not by testing if the equality e(z, ĝz θ 1 ) • e(r, ĝr θ 2 ) = 1 G T holds.

Linearly Homomorphic Structure-Preserving Signatures

Structure-preserving signatures [START_REF] Abe | Structure-preserving signatures and commitments to group elements[END_REF][START_REF] Abe | Signing on elements in bilinear groups for modular protocol design[END_REF] are signature schemes that allow signing elements of an abelian group while preserving their algebraic structure, without hashing them first. In [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF], Libert et al. described structure-preserving signatures with linearly homomorphic properties. Given signatures on several vectors M 1 , . . . , M n of group elements, anyone can publicly derive a signature on any linear combination of M 1 , . . . , M n . They suggested the following scheme, which is a one-time LHSPS (namely, it only allows signing one linear subspace) based on the DP assumption.

Keygen(λ, N ): Given a security parameter λ and the dimension N ∈ N of the subspace to be signed, choose bilinear group (G, Ĝ, G T ) of prime order p > 2 λ . Then, choose ĝz , ĝr

R ← Ĝ. For k = 1 to N , pick χ k , γ k R ← Z p and compute ĝk = ĝz χ k ĝr γ k . The private key is sk = {χ k , γ k } N i=1 while the public key consists of pk = ĝz , ĝr , { ĝk } N k=1 . Sign(sk, (M 1 , . . . , M N )): To sign a vector (M 1 , . . . , M N ) ∈ G N using sk = {χ k , γ k } N k=1 , compute and output σ = (z, r) ∈ G 2 , where z = N k=1 M -χ k k and r = N k=1 M -γ k k . SignDerive(pk, {(ω i , σ (i) )} i=1 ):
Given the public key pk and tuples (ω i , σ (i) ), parse σ (i) as σ (i) = z i , r i ∈ G 3 for i = 1 to . Then, compute and return σ = (z, r), where z = i=1 z ω i i and r = i=1 r ω i i . Verify(pk, σ, (M 1 , . . . , M N )): Given a purported signature σ = (z, r) ∈ G 2 and a vector (M 1 , . . . , M N ), return 1 if and only if (M 1 , . . . , M N ) = (1 G , . . . , 1 G ) and (z, r) satisfies 1 G T = e(z, ĝz ) • e(r, ĝr ) • N k=1 e(M k , ĝk ). A useful property of the scheme is that, if the DP assumption holds, it is computationally hard to come up with two distinct signatures on the same vector, even if the private key is available.

A Practical Adaptively Secure Non-Interactive Threshold Signature

The construction notably relies on the observation that, as shown in Appendix C.1, any one-time linearly homomorphic SPS can be turned into a fully secure ordinary signature by introducing a random oracle. The public key is simply that of a linearly homomorphic SPS for vectors of dimension n > 1. Messages are signed by hashing them to a vector H ∈ G n and generating a one-time homomorphic signature on H. The security reduction programs the random oracle in such a way that all signed messages are hashed into a proper subspace of G n whereas, with some probability, the adversary forges a signature on a message which is hashed outside this subspace. Hence, a forgery for this message translates into an attack against the underlying linearly homomorphic SPS.

In the threshold setting, our system can be seen as an adaptively secure variant of Boldyreva's threshold signature [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF], which builds on the short signatures of Boneh, Lynn, and Shacham [START_REF] Boneh | Short signatures from the Weil pairing[END_REF].

The DKG phase uses Pedersen's protocol [START_REF] Pedersen | A threshold cryptosystem without a trusted party[END_REF] (or, more precisely, a variant with two generators). Each player verifiably shares a random secret using Pedersen's verifiable secret sharing [START_REF] Pedersen | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF] -where verification is enabled by having all parties broadcast commitments to their secret polynomialsand the final secret key is obtained by summing up the shares of non-disqualified players. When all parties follow the protocol, a single communication round is needed. Moreover, we do not need to rely on zero-knowledge proofs or reliable erasures at any time.

In order to sign a message using his private key share, each player first hashes the message M to obtain a vector (H 1 , H 2 ) ∈ G 2 of two group elements, which can be signed using the linearly homomorphic structure-preserving signature of Section 2.3. We actually build on the observation that any one-time linearly homomorphic SPS implies a fully secure digital signature in the random oracle model. In the threshold setting, we take advantage of two specific properties in the underlying homomorphic signature. First, it is also key homomorphic 4 and thus amenable for non-interactively distributing the signing process. Second, in the security proof of [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF], the reduction always knows the private key, which allows consistently answering adaptive corruption queries.

Description

In the description below, we assume that all players agree on public parameters params consisting of asymmetric bilinear groups (G, Ĝ, G T ) of prime order p > 2 λ with generators ĝz , ĝr ∈ R Ĝ and a hash function H : {0, 1} * → G 2 that ranges over G × G. This hash function is modeled as a random oracle in the security analysis. While no party should know log ĝz ( ĝr ), we do not need an extra round to generate ĝr in a distributed manner as it can simply be derived from a random oracle.

Dist-Keygen(params, λ, t, n): Given common public parameters params = {(G, Ĝ, G T ), ĝz , ĝr , H}, a security parameter λ and integers t, n ∈ N such that n ≥ 2t + 1, each player P i conducts the following steps. 1. Each player P i shares two pairs {(a ik0 , b ik0 )} 2 k=1 . To this end, he does the following:

(a) For each k ∈ {1, 2}, choose random polynomials A ik [X] = a ik0 + a ik1 X + • • • + a ikt X t , B ik [X] = b ik0 + b ik1 X + • • • + b ikt X t ∈ Z p [X] of degree t and broadcast Ŵik = ĝz a ik ĝr b ik ∀ ∈ {0, . . . , t} . (b) For j = 1 to n, send {(A ik (j), B ik (j))} 2 k=1 to P j . 2. For each set of shares {(A jk (i), B jk (i))} 2
k=1 received from another player P j , P i verifies that ĝA jk (i)

z ĝB jk (i) r = t =0 Ŵ i jk for k = 1, 2 . (1)
If these equalities do not both hold, P i broadcasts a complaint against the faulty sender P j .

3. Any player who received strictly more than t complaints is immediately disqualified. Each player P i who received a complaint from another player P j responds by returning the correct shares {(A ik (j), B ik (j))} 2 k=1 . If any of these new shares does not satisfy (1), P i is disqualified. Let Q ⊂ {1, . . . , n} be the set of non-disqualified players at the end of step 3.

The public key is obtained as

PK = {ĝ k } 2 k=1
, where ĝk = i∈Q Ŵik0 = ĝ i∈Q a ik0 z ĝ i∈Q b ik0 r . Each P i locally defines his private key share

SK i = {(A k (i), B k (i))} 2 k=1 = { j∈Q A jk (i), j∈Q B jk (i) } 2 k=1
and anyone can publicly compute his verification key VK i = V1,i , V2,i as

VK i = ĝz A 1 (i) ĝr B 1 (i) , ĝz A 2 (i) ĝr B 2 (i) = j∈Q t =0 Ŵ i j1 , j∈Q t =0 Ŵ i j2 .
For any disqualified player i ∈ {1, . . . , n} \ Q, the i-th private key share is implicitly set as

SK i = {(0, 0)} 2 k=1
and the corresponding verification key is

VK i = (1 Ĝ, 1 Ĝ).
This completes the generation of the private key shares SK = (SK 1 , . . . , SK n ), the vector of verification keys VK = (VK 1 , . . . , VK n ) and the public key, which consists of PK = params, ĝ1 , ĝ2 .

When the protocol ends, the obtained private key shares

{A k (i)} 2 k=1 and {B k (i)} 2 k=1 lie on t-degree polynomials A k [X] = j∈Q A jk [X] and B k [X] = j∈Q B jk [X]. Each player also holds an addi- tive share {(a ik0 , b ik0 )} 2 k=1 of the secret key {(A k (0), B k (0)) = ( i∈Q a ik0 , i∈Q b ik0 )} 2
k=1 but these shares will not be used in the scheme.

Share-Sign(i, SK i , M ): To generate a partial signature on a message M ∈ {0, 1} * using his private key share

SK i = {(A k (i), B k (i))} 2 k=1 , P i first computes the hash value (H 1 , H 2 ) = H(M ) ∈ G×G and generates the partial signature σ i = (z i , r i ) ∈ G 2 as z i = 2 k=1 H -A k (i) k , r i = 2 k=1 H -B k (i) k . Share-Verify PK , VK, M, (i, σ i ) : Given a candidate partial signature σ i = (z i , r i ) ∈ G 2 and the verification key VK i = V1,i , V2,i , the partial verification algorithm first computes (H 1 , H 2 ) = H(M ) ∈ G 2 . It returns 1 if the equality e(z i , ĝz ) • e(r i , ĝr ) • 2 k=1 e(H k , Vk,i ) = 1 G T holds and 0 otherwise. Combine(PK , VK, M, {(i, σ i )} i∈S ): Given a (t + 1)-set with valid shares {(i, σ i )} i∈S , parse the signa- ture share σ i as z i , r i ∈ G 2 for each i ∈ S. Then, compute (z, r) = i∈S z ∆ i,S (0) i , i∈S r ∆ i,S (0) i by Lagrange interpolation in the exponent. Return the pair (z, r) ∈ G 2 . Verify PK , M, σ : Given a purported signature σ = (z, r) ∈ G 2 , compute (H 1 , H 2 ) = H(M ) ∈ G × G
and return 1 if and only if the following equality holds:

e(z, ĝz ) • e(r, ĝr ) • e(H 1 , ĝ1 ) • e(H 2 , ĝ2 ) = 1 G T .
If the scheme is instantiated using Barreto-Naehrig curves [START_REF] Barreto | Pairing-friendly elliptic curves of prime order[END_REF] at the 128-bit security level, each signature consists of 512 bits. For the same security level, RSA-based threshold signatures like [START_REF] Shoup | Practical threshold signatures[END_REF][START_REF] Almansa | Simplified threshold RSA with adaptive and proactive security[END_REF] require 3076 bits. The scheme is also very efficient from a computational standpoint. Each server only has to compute two multi-exponentiations with two base elements and two "hash-on-curve" operations. The verifier has to compute a product of four pairings.

At the end of the key generation phase, each player only needs to store a private key share

SK i = {(A k (i), B k (i))} 2
k=1 of constant-size -whereas solutions like [START_REF] Almansa | Simplified threshold RSA with adaptive and proactive security[END_REF] incur the storage of O(n) elements at each player-and can erase all intermediate values, including the polynomials A ik [X] and B ik [X]. However, we insist that the security analysis does not require reliable erasures. When a player is corrupted, we assume that the adversary learns the entire history of this player.

Security

Although the public key is not guaranteed to be uniform due to the use of Pedersen's DKG protocol, the key homomorphic property allows the reduction to turn the adversary's forgery into a valid signature with respect to some uniformly random public key obtained by multiplying honest users' contributions to the public key. This is sufficient for solving a given Double Pairing instance.

The security proof proceeds with a sequence of games which can be outlined as follows. The first game is the real game where the challenger assumes the role of all honest players in the distributed key generation phase. Since it controls a majority of players, the challenger knows the polynomials {A jk [X], B jk [X]} j∈Q,k∈{1,2} and the private key shares {SK j } j∈Q of all non-disqualified playerseither because it obtained at least t + 1 polynomial shares {(A jk (i), B jk (i))} i∈G,k∈{1,2} for each j ∈ Q or because it chose the polynomials itself -at the end of the Dist-Keygen protocol.

In subsequent games, the challenger applies Coron's proof technique for Full Domain Hash signatures [START_REF] Coron | On the exact security of full domain hash[END_REF]. At each random oracle query H(M ), it flips a coin ϑ M ∈ {0, 1} that takes the value 0 with probability 1/q s and the value 1 with probability 1/(q s + 1), where q s is the number of signing queries. If ϑ M = 1, the challenger defines H(M ) to be a random vector of G 2 . If ϑ M = 0, the message M is hashed to a subspace of dimension 1. We prove that, although H does no longer behave as an actual random oracle, this change should not affect the adversary's view if the DDH assumption holds in G. Coron's analysis [START_REF] Coron | On the exact security of full domain hash[END_REF] shows that, with probability Ω(1/q s ), the following conditions are fulfilled: (i) The adversary only obtains partial signatures on messages M 1 , . . . , M qs that are hashed in a one-dimensional subspace; (ii) The adversary's forgery involves a message M such that (H 1 , H 2 ) = H(M ) is linearly independent of the vectors {(H 1,i , H 2,i ) = H(M i )} qs i=1 . Condition (i) ensures that the adversary obtains little information about the private key shares {SK i } i∈G and the additive shares {a ik0 , b ik0 } i∈G,k∈{1,2} of honest players. Hence, if the challenger computes the additive contribution of honest players to a signature on the vector (H 1 , H 2 ) = H(M ), this contribution is completely unpredictable by the adversary due to condition (ii). With overwhelming probability, this contribution does not coincide with the one that can be extracted (using the additive shares {a jk0 , b jk0 } j∈Q\G, k∈{1,2} that the reduction knows from the key generation phase) from the adversary's forgery (z , r ) using the key homomorphic property of the scheme. The challenger thus obtains two distinct linearly homomorphic signatures on the vector (H 1 , H 2 ), which allows solving an instance of the Double Pairing problem. Theorem 1. The scheme provides adaptive security under the SXDH assumption in the random oracle model. Namely, for any PPT adversary A, there exist DDH distinguishers B 1 and B 2 with comparable running time in the groups G and Ĝ, respectively.

Proof. The proof proceeds with a sequence of three games. The latter begins with Game 0, which is the real game, and ends with Game 2, where any PPT adversary is shown to contradict the Double Pairing assumption. For each j ∈ {0, 1, 2}, S j denotes the event that the adversary wins in Game j.

We assume w.l.o.g. that the adversary A always queries the random oracle H before any signing query for the same message M . The challenger can always enforce this by making random oracle queries for itself. We also assume that random oracle queries are distinct.

Game 0: This is the real game. Namely, the challenger runs the Dist-Keygen protocol on behalf of all uncorrupted players. Whenever the adversary A decides to corrupt a player P i , the challenger sets C = C ∪ {i}, G = G\{i} and faithfully reveals the internal state of P i , which includes P i 's private key share

SK i = {(A k (i), B k (i))} 2 k=1 and his polynomials {A ik [X], B ik [X]} 2 k=1
if the corruption query occurs after step 1.a of Dist-Keygen. Whenever a player P i is corrupted, A receives full control over P i and may cause him to arbitrarily deviate from the protocol. Queries to the random oracle H are answered by returning uniformly random group elements in G 2 . Partial signature queries (i, M ) are answered by returning the values (z i , r

i ) = 2 k=1 H -A k (i) k , 2 k=1 H -B k (i) k
. At the end of the game, A outputs a message-signature pair σ = (z , r ), M . We assume that the adversary queries H(M ) before producing its forgery. We denote by S 0 the event that σ = (z , r ) is a valid signature.

In the following, we define

A k [X] = i∈Q A ik [X] and B k [X] = i∈Q B ik [X]
as well as (a k0 , b k0 ) = ( i∈Q a ik0 , i∈Q b ik0 ) for each k ∈ {1, 2}. We remark that, at the end of the Dist-Keygen protocol, the challenger knows the polynomials

{A jk [X], B jk [X]} 2
k=1 and the additive shares {(a jk0 , b jk0 )} 2 k=1 of all non-disqualified players j ∈ Q. Indeed, for each j ∈ Q ∩ C such that P j was corrupted before step 1.a of the distributed key generation phase, it obtained at least t + 1 shares

{A jk (i), B jk (i)} 2 k=1 , which is sufficient for reconstructing {A jk [X], B jk [X]} 2 k=1 .
As for other players P j such that j ∈ Q, the challenger honestly chose their sharing polynomials at step 1.a of Dist-Keygen.

Game 1: This game is identical to Game 0 with the following difference. For each random oracle query H(M ), the challenger B flips a biased coin ϑ M ∈ {0, 1} that takes the value 1 with probability 1/(q s + 1) and the value 0 with probability q s /(q s + 1). When the game ends, B considers the event E that either of the following conditions holds:

-For the message M , the coin ϑ M ∈ {0, 1} flipped for the hash query H(M ) was ϑ M = 0.

-There exists signing query (i, M ) with M = M for which ϑ M = 1.

If event E occurs (which B can detect at the end of the game), B halts and declares failure. The same analysis as that of Coron [START_REF] Coron | On the exact security of full domain hash[END_REF] shows that Pr[¬E] = 1/e(q s + 1), where e is the base for the natural logarithm. The transition from Game 0 to Game 1 is thus a transition based on a failure event of large probability [START_REF] Dent | A Note On Game-Hopping Proofs[END_REF] and we thus have Pr[S 1 ] = Pr[S 0 ] • Pr[¬E] = Pr[S 0 ]/e(q s + 1).

Game 2: We modify the distribution of random oracle outputs. Specifically, the challenger B chooses generators g, h R ← G at the beginning of the game and uses them to answer random oracle queries. The treatment of each hash query H(M ) depends on the random coin ϑ M ∈ {0, 1}.

-If ϑ M = 0, the challenger B chooses a random α M R ← Z p , and programs the random oracle so as to have H(M ) = (g α M , h α M ). Note that the resulting hash value H(M ) ∈ G 2 is no longer uniform in G 2 as it now lives in the one-dimensional space spanned by the vector (g, h)

∈ G 2 . -If ϑ M = 1, B chooses a uniformly random pair (g M , h M ) ∈ G 2 and programs H(M ) so as to have H(M ) = (g M , h M ).
Lemma 1 below shows that Game 2 and Game 1 are computationally indistinguishable if the DDH assumption holds in the group G.

It follows that | Pr[S 2 ] -Pr[S 1 ]| ≤ Adv DDH 1 (B).
In Game 2, we claim that Pr[S 2 ] ≤ Adv(B) DP (λ) + 1/p as B can be turned into an algorithm solving the DP problem. Indeed, with probability 1/e(q s +1), the hash value H(M ) = (H 1 , H 2 ) ∈ G 2 is uniformly random for the message M involved in the forgery (z , r ) whereas, for each signed message M such that M = M , H(M ) = (H 1 , H 2 ) lives in the one-dimensional subspace spanned by (g, h). We also note that, while the adversary is allowed to submit queries of the form (i, M ) to the partial signing oracle, these queries do not reveal any more information than if the challenger were simply handing over the corresponding private share SK i . We thus treat these partial signing queries for M as corruption queries. When A halts, the challenger determines which players have generated a partial signature on M and moves them from G to C. Note that, for these updated sets G and C, it still knows the

polynomials {(A jk [X], B jk [X])} 2
k=1 for all j ∈ C. Let us define the aggregated additive shares

a k,G = j∈G a jk0 b k,G = j∈G b jk0 k ∈ {1, 2}. a k,Q∩C = j∈Q∩C a jk0 b k,Q∩C = j∈Q∩C b jk0
We remark that all pairs {(a k,G , b k,G )} 2 k=1 are uniformly distributed in Z 2 p since they are obtained by summing additive shares that were honestly chosen by the challenger.

We also argue that a 2,G is independent of A's view. To see this, let us consider what an unbounded A can learn during the game. Corruption queries reveal {A j2 (i)} j∈G,i∈C , which is insufficient to infer anything about a 2,G = j∈G A j2 (0) since |C| ≤ t. For each M = M , signing queries are answered by returning

(z i , r i ) = H -A 1 (i) 1 H -A 2 (i) 2 , H -B 1 (i) 1 H -B 2 (i) 2 = (g -A 1 (i) • h -A 2 (i) ) α M , (g -B 1 (i) • h -B 2 (i) ) α M .
Note that the information supplied by r i is redundant since, for a given pair (H 1 , H 2 ) and a given z i ∈ G, there is only one

r i ∈ G satisfying e(z i , ĝz ) • e(r i , ĝr ) • 2 k=1 e(H k , Vk,i ) = 1 G T . Since A knows {(A jk [X], B jk [X])} 2 k=1 for each j ∈ Q ∩ C, it can obtain z i,G = g -j∈G A j1 (i) • h -j∈G A j2 (i) α M , (2)
However, these partial signatures (z i , r i ) on M = M only provide A with redundant information about j∈G A j1 (i), j∈G A j2 (i), j∈G B j1 (i), j∈G B j2 (i) . The only thing that A really learns from ( 2) is the value

j∈G (A j1 (i) + ω • A j2 (i))
, where ω = log g (h). In addition, during step 2 of the Dist-Keygen protocol, relation (1) also provides the adversary with ĝz A jk (i) ĝr B jk (i) for each i ∈ {1, . . . , n}, j ∈ G and k ∈ {1, 2}. Still, the only way to leverage these pieces of information is to interpolate them and get a 1,G + ω • a 2,G as well as

{a k,G + ρ • b k,G } 2 k=1
, where ρ = log ĝz ( ĝr ), which leaves A with a system of 3 equations in 4 unknowns {(a k,G , b k,G )} 2 k=1 . As a consequence, a 2,G remains completely undetermined in A's view as long as |C| ≤ t.

The lack of adversarial information about a 2,G allows solving the DP problem as follows. For the target message M , we can write (H 1 , H 2 ) = (g α M , h α M +γ ), for some random α M , γ ∈ R Z p . This implies that, if the challenger computes a product (z † , r † ) of its own partial signatures on the message M using the sum (a 1,G , a 2,G , b 1,G , b 2,G ) of its additive shares, this product can be written as

(z † , r † ) = H 1 -a 1,G • H 2 -a 2,G , H 1 -b 1,G • H 2 -b 2,G = (g a 1,G • h a 2,G ) -α M • h -γ•a 2,G , (g b 1,G • h b 2,G ) -α M • h -γ•b 2,G , (3)
where z † is completely unpredictable by A. Indeed, in the right-hand-side member of (3), A can information-theoretically determine the term (g a 1,G •h a 1,G ) α M by interpolating the discrete logarithms j∈G (A j,1 (i) + ωA j,2 (i)) obtained from (2) (note that, although (g, h) are not explicitly given to A, they can be inferred, in the same way as exponents α M and α M , by observing hash values). However, the uniformly random term h -γ•a 2,G remains completely independent of A's view. Now, the challenger can use the adversary's forgery (z , r ) to compute

(z , r ) = z • H 1 a 1,Q∩C • H 2 a 2,Q∩C , r • H 1 b 1,Q∩C • H 2 b 2,Q∩C , which, if we define ĝ1,G = ĝz a 1,G • ĝr b 1,G and ĝ2,G = ĝz a 2,G • ĝr b 2,G , is easily seen to satisfy e(z , ĝz ) • e(r , ĝz ) • e(H 1 , ĝ1,G ) • e(H 2 , ĝ2,G ) = 1 G T since ĝ1 = ĝ1,G • ĝz a 1,Q∩C • ĝr b 1,Q∩C and ĝ2 = ĝ2,G • ĝz a 2,Q∩C • ĝr b 2,Q∩C . From (3), we see that (z † , r † ) also satisfies e(z † , ĝz ) • e(r † , ĝz ) • e(H 1 , ĝ1,G ) • e(H 2 , ĝ2,G ) = 1 G T by construction.
Given that z † is independent of A's view, the quotient (z † /z , r † /r ) forms a non-trivial solution to the DP instance ( ĝz , ĝr ) with probability 1 -1/p. Such a solution easily allows building a distinguisher for the DDH problem in Ĝ. We thus find the upper bound

Adv(A) ≤ e • (q s + 1) • Adv DDH 1 (B) + Adv DDH 2 (B) + 1 p , (4)
where q s is the number of signing queries and e is the base for the natural logarithm.

We remark that the proof of Theorem 1 goes through if, during the key generation phase, each player Ŵi10 ) • e(g, Ŵi20 ) = 1 G T and thus forms a LHSPS on (g, h) for the public key { Ŵik0 } 2 k=1 . Indeed, if we consider the information that each player initially reveals about its local additive shares (a i10 , a i20 , b i10 , b i20 ) ∈ Z 4 p , it amounts to the discrete logarithms of ( Ŵi10 , Ŵi20 , Z i0 ). The only extra information revealed by Z i0 is thus a i10 +ω •a i20 , where ω = log g (h), which leaves a i20 undetermined. While an unbounded adversary can compute the sum a 1,G +ω •a 2,G in Game 2, it still has no information about a 2,G = j∈G a j20 . In Appendix F, we use this observation to show a simple modification of the scheme that supports signature aggregation.

P i additionally publicizes (Z i0 , R i0 ) = g -a i10 h -a i20 , g -b i10 h -b i20 , for public g, h ∈ G, which satisfies e(Z i0 , ĝz ) • e(R i0 , ĝr ) • e(h,

Adding Proactive Security

The scheme readily extends to provide proactive security [START_REF] Ostrovksy | How to withstand mobile virus attacks[END_REF][START_REF] Herzberg | Proactive public key and signature systems[END_REF][START_REF] Frankel | Optimal resilience proactive public-key cryptosystems[END_REF] against mobile adversaries that can potentially corrupt all the players at some point as long as it never controls more than t players at any time. By having the players refreshing all shares (without changing the secret) at discrete time intervals, the scheme remains secure against an adversary corrupting up to t players during the same period. This is achieved by having all players run a new instance of Pedersen's DKG protocol where the shared secret is {(0, 0)} 2 k=1 and locally add the resulting shares to their local shares before updating {VK i } n i=1 accordingly. The techniques of [START_REF] Herzberg | Proactive secret sharing Or: How to cope with perpetual leakage[END_REF]Section 4] can also be applied to detect parties holding a corrupted share (due to a crash during an update phase or an adversarial behavior) and restore the correct share.

A Construction in the Standard Model

This section gives a round-optimal construction in the standard model. We remark that, under the Decision Linear assumption [START_REF] Boneh | Short group signatures[END_REF], any one-time LHSPS in symmetric bilinear groups can be turned into a full-fledged digital signature, as shown in the full version of the paper. In the threshold setting, we need to rely on specific properties of the underlying LHSPS in order to achieve adaptive security without relying on a trusted dealer.

The scheme relies on the Groth-Sahai non-interactive witness indistinguishable (NIWI) proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], which are recalled in Appendix A. In its centralized version, a signature consists of a NIWI proof of knowledge -somewhat in the spirit of Okamoto's signature scheme [START_REF] Okamoto | Provably secure and practical identification schemes and corresponding signature schemes[END_REF]-of a one-time linearly homomorphic signature on a fixed vector g ∈ G of dimension n = 1. To generate this proof, the signer forms a Groth-Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] common reference string (CRS) (f , f M ) using the bits of the message M , according to a technique suggested by Malkin et al. [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF]. Due to the witness indistinguishability property of Groth-Sahai proofs, no information leaks about the private key of the underlying one-time homomorphic signature. For this reason, when the adversary creates a fake signature, the reduction is able to extract a different homomorphic signature than the one it can compute. Hence, it obtains two distinct signatures on the same vector, which allows solving an instance of the DP problem.

The scheme can also be seen as a threshold version of (a variant of) the signature presented in [START_REF] Malkin | Signatures resilient to continual leakage on memory and computation[END_REF]. In order to distribute the signing process, we take advantage of the homomorphic properties of Groth-Sahai proofs. More precisely, we use the fact that linear pairing product equations and their proofs can be linearly combined in order to obtain a valid proof for the desired statement when performing a Lagrange interpolation in the exponent. In order to avoid interaction during the signing process, we leverage the property that the centralized signature scheme is key homomorphic.

However, we have to prove that the scheme remains adaptively secure when the DKG phase uses Pedersen's protocol [START_REF] Pedersen | A threshold cryptosystem without a trusted party[END_REF]. To this end, we take further advantage of the key homomorphic property. In the security proof, we show that, if the adversary can forge a signature for a non-uniform public key PK , we can turn this forgery into one for another public key PK , which is uniformly distributed.

In the following notations, for each h ∈ G and any vector g = (g 1 , g 2 ) ∈ G 2 , we denote by E(g, ĥ) the vector (e(g 1 , ĥ), e(g 2 , ĝ)) ∈ G 2

T . Here, we assume public parameters params made of asymmetric bilinear groups (G, Ĝ, G T ) of prime order p > 2 λ with generators

g ∈ R G, ĝz , ĝr ∈ R Ĝ and vectors f = (f, h) ∈ G 2 and f i = (f i , h i ) R ← G 2 for i = 0 to L, where L ∈ poly(λ).
Dist-Keygen(params, λ, t, n): This protocol proceeds as in the scheme of Section 3. Namely, given common parameters params = {(G, Ĝ, G T ), g, ĝz , ĝr , f , {f i } L i=0 }, a security parameter λ and integers t, n ∈ N such that n ≥ 2t + 1, each player P i conducts the following steps. 1. Each player P i shares a random pair (a i0 , b i0 ) according to the following step:

(a) Pick random polynomials

A i [X] = a i0 + a i1 X + • • • + a it X t , B i [X] = b i0 + b i1 X + • • • + b it X t
of degree t and broadcast Ŵi = ĝz a i ĝr b i for all ∈ {0, . . . , t}. (b) For j = 1 to n, send (A i (j), B i (j)) to P j . 2. For each received shares (A j (i), B j (i)), player P i verifies that ĝA j (i)

z ĝB j (i) r = t =0 Ŵ i j .
(

) 5
If the latter equality does not hold, P i broadcasts a complaint against P j . 3. Any player receiving more than t complaints is disqualified. Each player P i who received a complaint from another player P j responds by returning the correct shares (A i (j), B i (j)). If any of these new shares fails to satisfy (5), the faulty P i is expelled. Let Q ⊂ {1, . . . , n} be the set of non-disqualified players at the end of step 3. 4. The public key PK is obtained as PK = ĝ1 , where ĝ1 = i∈Q Ŵi0 = ĝ i∈Q a i0 z ĝ i∈Q b i0 r . Each P i locally defines his private key share as SK i = (A(i), B(i)) = j∈Q A j (i), j∈Q B j (i) and anyone can publicly compute his verification key as

VK i = Vi = ĝz A(i) ĝr B(i) = j∈Q t =0
Ŵ i j . Any disqualified player i ∈ {1, . . . , n} \ Q is implicitly assigned the share SK i = (0, 0) and the matching verification key VK i = 1 Ĝ. The vector of private key shares is SK = (SK 1 , . . . , SK n ) and the corresponding vector of verification keys VK = (VK 1 , . . . , VK n ). The public key consists of PK = params, ĝ1 . Share-Sign(SK i , M ): To generate a partial signature on a L-bit message

M = M [1] . . . M [L] ∈ {0, 1} L using SK i = (A(i), B(i)), define (z i , r i ) = (g -A(i) , g -B(i) ). 1. Using the bits M [1] . . . M [L] of M ∈ {0, 1} L , define the vector f M = f 0 • L i=1 f M [i] i so as to assemble a Groth-Sahai CRS f M = (f , f M ). 2. Using the CRS f M = (f , f M ), compute Groth-Sahai commitments C z,i = (1 G , z i ) • f ν z,1 1 • f ν z,2 M and C r,i = (1 G , r i )•f ν r,1,i •f ν r,2,i M
to the group elements z i and r i , respectively. Then, generate a NIWI proof πi = (π 1,i , π2,i ) ∈ Ĝ2 that committed elements (z i , r i ) ∈ G 2 satisfy the verification equation 1 G T = e(z i , ĝz ) • e(r i , ĝr ) • e(g, Vi ). This proof is obtained as

πi = (π 1,i , π2,i ) = ĝz -ν z,1,i • ĝr -ν r,1,i , ĝz -ν z,2,i • ĝr -ν r,2,i Return σ i = (C z,i , C r,i , πi ) ∈ G 4 × Ĝ2 . Share-Verify(PK , VK, M, (i, σ i )): Given M ∈ {0, 1} L and a candidate σ i , parse σ i as σ i = (C z,i , C r,i , πi ). Define f M = f 0 • L i=1 f M [i] i
and return 1 if πi = (π 1,i , π2,i ) satisfies

E (1 G , g), Vi -1 = E C z,i , ĝz • E C r,i , ĝr • E(f , π1,i ) • E(f M , π2,i )
and 0 otherwise. Combine(PK , VK, M, {(i, σ i )} i∈S ): Given a (t + 1)-set with valid shares {(i, σ i )} i∈S , parse each signature share σ i as (C z,i , C r,i , πi ) ∈ G 4 × Ĝ2 , where πi = (π 1,i , π2,i ), for all i ∈ S. Then, compute

(C z , C r , π 1 , π 2 ) as i∈S C ∆ i,S (0) z,i , i∈S C ∆ i,S (0) r,i , i∈S π∆ i,S (0) 1,i , i∈S π∆ i,S (0)
2,i by Lagrange interpolation in the exponent. Finally, re-randomize (C z , C r , π 1 , π 2 ) and output the resulting re-randomized full signature σ = (C z , C r , π1 , π2 ). Verify(PK , M, σ): Given a message M ∈ {0, 1} L and a purported signature σ, parse σ as

(C z , C r , π) ∈ G 4 × Ĝ2 . Define f M = f 0 • L i=1 f M [i] i
and return 1 if and only if π = (π 1 , π2 ) satisfies

E (1 G , g), ĝ1 -1 = E C z , ĝz • E C r , ĝr • E(f , π1 ) • E(f M , π2 ) .
The scheme can be simplified by having each player set his private key share as SK i = (g -A(i) , g -B(i) ) so as to spare two exponentiations in the signing phase. In the description, we defined SK i as (A(i), B(i)) to insist that no reliable erasures are needed. At each corruption query, the adversary obtains (A(i), B(i)) and, not only (g -A(i) , g -B(i) ). In any case, each player only needs to store two elements of Z p .

At the 128-bit security level, if each element of G (resp. Ĝ) has a 256-bit (resp. 512 bit) representation on Barreto-Naehrig curves [START_REF] Barreto | Pairing-friendly elliptic curves of prime order[END_REF], we only need 2048 bits per signature. Theorem 2. The scheme provides adaptive security under the SXDH assumption in the standard model. Namely, for any PPT adversary A, there exist DDH distinguishers B 1 and B 2 with comparable running time in the groups G and Ĝ, respectively.

Proof. The proof uses a sequence of three games that begins with Game 0, which is the real game, and ends with Game 2, where even any PPT adversary A allows breaking the Double Pairing assumption. For each j ∈ {0, 1, 2}, we denote by S j the event that the adversary wins in Game j.

Game 0: This is the actual game. Specifically, the challenger assumes the role of all uncorrupted players during the Dist-Keygen protocol. When A chooses to corrupt a player P i , the challenger sets C = C ∪ {i}, G = G\{i} and reveals the internal state of P i , which includes P i 's private key share SK i = (A(i), B(i)) and the polynomials A i [X], B i [X] if the corruption occurs after step 1.a of Dist-Keygen. When a player P i is corrupted, it may arbitrarily deviate from the protocol. Partial signature queries (i, M ) are answered by honestly running the partial signing algorithm. At the end of the game, A outputs a message-signature pair σ = (C z , C r , π ), M . We denote by S 0 the event that σ = (C z , C r , π ) is a valid forgery. We define

A[X] = i∈Q A i [X], B[X] = i∈Q B i [X] and (a 0 , b 0 ) = ( i∈Q a i0 , i∈Q b i0 )
. At the end of the Dist-Keygen protocol, the challenger knows the polynomials A j [X], B j [X] and the additive shares (a j0 , b j0 ) of all non-disqualified players j ∈ Q. Indeed, since there is always a majority of honest players, the challenger receives at least t + 1 shares (A j (i), B j (i)) for each j ∈ Q ∩ C. As for the remaining players P j such that j ∈ G ⊂ Q, their polynomials were honestly chosen by the challenger at step 1.a of Dist-Keygen.

Game 1: In this game, we modify the generation of the public parameters. Namely, the vectors (f , {f i } L i=0 ) are chosen as f = (f, h) and {f i } L i=0 , where Game 2: In this game, we raise an event F 2 and let the simulator B abort if it occurs. Let M 1 , . . . , M q be the messages submitted to the partial signing oracle during the game. For each message

f 0 = f ξ 0,1 • (1, h) ξ 0,2 • (1, h) µ•ζ-ρ 0 (6)
f i = f ξ i,1 • (1, h) ξ i,2 • (1, h) -ρ i , i ∈ {1, . . . , L} with µ R ← {0, . . . , L}, ξ 0,1 , ξ 1,1 , . . . , ξ L,1 R ← Z p , ξ 0,2 , ξ 1,2 , . . . , ξ L,2
M = M [1] . . . M [L] ∈ {0, 1} L , we consider the function J(M ) = µ • ζ -ρ 0 -L i=1 ρ i • M [i]
. We define F 2 to be the event that either -J(M ) = 0 -There exists a message M j ∈ {M 1 , . . . , M q }\{M } such that J(M j ) = 0.

We remark that ρ 0 , ρ 1 , . . . , ρ L are chosen independently of A's view. In fact, the challenger could equivalently define {f i } L i=0 at the beginning of the game and only choose {ρ i } L i=0 -along with values {ξ 2,i } L i=0 that are consistent with {f i } L i=0 -at the very end of the game, when M , M 1 , . . . , M q have been defined. The same analysis as [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF][START_REF] Bellare | Simulation without the artificial abort: Simplified proof and improved concrete security for Waters' IBE scheme[END_REF]

shows that Pr[S 2 ∧ ¬F 2 ] ≥ Pr[S 1 ] 2 /(27 • q • (L + 1)).
This follows from the fact that, for any set of queries, a lower bound on the probability of event ¬F 2 is 1/(2q(L + 1)).

Game 3: We modify the distribution of public parameters. Namely, f = (f, h) is chosen as before but, instead of generating {f i } L i=0 as in Game 2, we choose them as

f 0 = f ξ 0,1 • (1, h) µ•ζ-ρ 0 ( 7
)
f i = f ξ i,1 • (1, h) -ρ i , i ∈ {1, . . . , L}
which amounts to setting ξ 0,2 = ξ 1,2 = . . . = ξ L,2 = 0. If the DDH assumption holds in G, the above modification should have no noticeable impact on A's behavior. More precisely, if events S 2 ∧ ¬F 2 and S 3 ∧ ¬F 2 occur with noticeably different probabilities in Game 2 and Game 3, we can build a DDH distinguisher B. The latter takes as input a DDH instance (f, h, f α , Z), where α R ← Z p and Z = h α or Z ∈ R G. Using the random self-reducibility of DDH, we can create L + 1 DDH instances (by extending a technique used in [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF]) -which are all Diffie-Hellman tuples or random tuples depending whether Z = h δ or not -and embed them in

{f i } L i=0 in such a way that {f i } L i=0 is distributed as in Game 2 (resp. Game 3) if Z ∈ R G (resp. Z = h δ ). For this reason, we can write | Pr[S 3 ∧ ¬F 2 ] -Pr[S 2 ∧ ¬F 2 ]| ≤ Adv DDH 1 (B).
In Game 3, we can show that Pr[S 3 ∧ ¬F 2 ] ≤ Adv(B) DP (λ) + 1/p as the challenger B can be turned into an algorithm solving the DP problem.

Indeed, if ¬F 2 occurs, the adversary's forgery σ = (C z , C r , π ) is a NIWI proof generated for a perfectly binding Groth-Sahai CRS (f , f M ), which means that B can use log f (h) to extract a pair (z , r ) satisfying e(z , ĝz ) • e(r , ĝr ) = e(g, ĝ1 ) -1 from the commitments C z , C r . At the same time, for each signed message M = M , the NIWI proof (C z , C r , π) is generated for a perfectly hiding CRS (f , f M ), so that no information about (z i , r i ) -and thus the private key shares (A(i), B(i))leaks for these queries. Also, while A is allowed queries of the form (i, M ) to the partial signing oracle, these do not reveal any more information than the corresponding private share SK i = (A(i), B(i)) itself. We thus consider partial signing queries for M as if they were corruption queries. Namely, at the end of the game, B determines which players have generated a partial signature for M and moves them from G to C. For these updated sets G and C, however, B still has the polynomials (A j [X], B j [X]) at disposal for all j ∈ C. Let us consider the aggregated additive shares

a G = j∈G a j0 b G = j∈G b j0 , a Q∩C = j∈Q∩C a j0 b Q∩C = j∈Q∩C b j0 ,
which are the contribution of good and corrupted players to the shared private key. We remark that the pair (a G , b G ) is uniformly distributed in Z 2 p since it is the sum of uniformly random additive shares chosen by the challenger.

It is easy to see that, conditionally on ¬F 2 , the term a G is independent of A's view as long as |C| ≤ t. This follows from the following facts: (i) Partial signing queries for M = M reveal nothing about a G due to the perfect WI property of the proof system; (ii) A obtains at most t -1 shares of each pair (a j0 , b j0 ), for j ∈ G; (iii) During step 2 of the Dist-Keygen protocol, while relation [START_REF] Barreto | Pairing-friendly elliptic curves of prime order[END_REF] provides the adversary with ĝz A j (i) ĝr B j (i) for each j ∈ G and i ∈ {1, . . . , n}, the only extractable useful information is a G + log ĝz ( ĝr ) • b G . As a consequence, a G remains independent of A's view as long as |C| ≤ t.

It comes that B can solve the DP problem as follows. If we define ĝ1,G = ĝz a G ĝr b G , the challenger can use the sum (a G , b G ) of its additive shares to compute a pair

(z † , r † ) = g -a G , g -b G ,
where z † is completely unpredictable by A, such that e(z † , ĝz ) • e(r † , ĝr ) = e(g, ĝ1,G ) -1 .

Moreover, B can also use the group elements (z , r ) extracted from A's forgery to compute

(z , r ) = z • g a Q∩C , r • g b Q∩C ,
which, since ĝ1 = ĝ1,G • ĝz a Q∩C • ĝr b Q∩C , is easily seen to also satisfy e(z , ĝz ) • e(r , ĝz ) = e(g, ĝ1,G ) -1 .

Since z † is independent of A's view, the pair (z † /z , r † /r ) forms a non-trivial solution to the DP instance ( ĝz , ĝr ) with probability 1 -1/p. Since the DP assumption implies the DDH assumption in Ĝ, we can upper bound the adversary's advantage as

Adv(A) ≤ 27 • q • (L + 1) • Adv DDH 1 (B) + Adv DDH 2 (B) + 1 p 1/2
, which proves the announced result.

A Groth-Sahai Non-Interactive Proof Systems

In [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], Groth and Sahai described efficient non-interactive witness indistinguishable (NIWI) proof systems of which one instantiation relies on the SXDH assumption. This instantiation uses prime order groups and a common reference string containing three vectors

f 1 , f 2 ∈ G 2 , where f 1 = (g, f 1 ), f 2 = (h, f 2 ), for some g, h, f 1 , f 2 ∈ G.
To commit to a group element X ∈ G, the prover chooses r, s

R ← Z p and computes C = (1, X) • f 1 r • f 2 s
. On a perfectly sound common reference string, we have f 2 = f 1 ξ , for some ξ ∈ Z p . Commitments C = (g r+ξs , f r+ξs 1

• X) are extractable as their distribution coincides with that of an Elgamal ciphertexts [START_REF] Gamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] and the committed X can be extracted using β = log g (f 1 ). In the witness indistinguishability (WI) setting, the vector f 2 is chosen so that (f 1 , f 2 ) are linearly independent vectors and C is a perfectly hiding commitment. Under the DDH assumption in G, the two kinds of CRS can be exchanged for one another without the adversary noticing.

To convince the verifier that committed variables satisfy a set of relations, the prover computes one commitment per variable and one proof element per equation. Such NIWI proofs can be efficiently generated for linear pairing-product equations, which are relations of the type

n i=1 e(X i , A i ) = t T , (8)
for variables X 1 , . . . , X n ∈ G and constants A 1 , . . . ,

A n ∈ Ĝ, t T ∈ G T , a ij ∈ Z p , for i, j ∈ {1, . . . , n}.
Under the SXDH assumption, proving an an equation like ( 8) requires two elements of Ĝ.

In [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF], Belenkiy et al. showed that Groth-Sahai proofs are perfectly randomizable. Given commitments {C X i } n i=1 and a NIWI proof π PPE that committed {X } n i=1 satisfy ( 8), anyone can publicly compute re-randomized commitments {C X i } n i=1 and a re-randomized proof π PPE of the same statement. Moreover, {C X i } n i=1 and π PPE are distributed as freshly generated commitments and proof.

B Definition and Template of Linearly Homomorphic Structure-Preserving Signatures

Let (G, Ĝ, G T ) be groups of prime order p such that a bilinear map e : G × Ĝ → G T can be efficiently computed.

A signature scheme is structure-preserving [START_REF] Abe | Signing on elements in bilinear groups for modular protocol design[END_REF] if messages, signatures and public keys live in the groups G or Ĝ. In linearly homomorphic structure-preserving signatures, the message space M consists of pairs M := T × G N , for some N ∈ N, where T is a tag space. Definition 4. A linearly homomorphic structure-preserving signature scheme over (G, Ĝ, G T ) is a tuple of efficient algorithms Σ = (Keygen, Sign, SignDerive, Verify) for which the message space consists of M := T × G N , for some integer n ∈ poly(λ) and some set T , and with the following specifications.

Keygen(λ, N ): is a randomized algorithm that takes in a security parameter λ ∈ N and an integer N ∈ poly(λ) denoting the dimension of vectors to be signed. It outputs a key pair (pk, sk), where pk includes the description of a tag space T , where each tag serves as a file identifier. Sign(sk, τ, M ): is a possibly randomized algorithm that takes as input a private key sk, a file identifier τ ∈ T and a vector M = (M 1 , . . . , M N ) ∈ G N . It outputs a signature σ ∈ G ns , for some n s ∈ poly(λ). SignDerive(pk, τ, {(ω i , σ (i) )} i=1 ): is a (possibly randomized) derivation algorithm. It inputs a public key pk, a file identifier τ as well as pairs (ω i , σ (i) ), each of which consists of a coefficient ω i ∈ Z p and a signature σ (i) ∈ G ns . It outputs a signature σ ∈ G ns on the vector M = i=1 M ω i i , where σ (i) is a signature on M i .

Verify(pk, τ, M , σ): is a deterministic verification algorithm that takes as input a public key pk, a file identifier τ ∈ T , a signature σ and a vector M = (M 1 , . . . , M N ). It outputs 0 or 1 depending on whether σ is deemed valid or not.

In a one-time linearly homomorphic SPS, the tag τ can be omitted in the specification as a given key pair (pk, sk) only allows signing one linear subspace.

As in all linearly homomorphic signatures, the security requirement is that the adversary be unable to create a valid triple (τ , M , σ ) for a new file identifier τ or, if τ is recycled from one or more honestly generated signatures, for a vector M outside the linear span of the vectors that have been legitimately signed for the tag τ .

An important property is that the SignDerive algorithm must operate on vectors that are all labeled with the same tag.

Template of One-Time LHSPS. In [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF], it was observed that any linearly homomorphic structurepreserving signature satisfies a certain template. In the case of one-time LHSPS, this template can be simplified as follows in bilinear groups (G, Ĝ, G T ).

Keygen(λ, N ): given λ and the dimension N ∈ N of the vectors to be signed, choose constants n z , m. Among these, n s will determine the signature length while m will be the number of verification equations. Then, choose { Fj,µ } j∈{1,...,m},µ∈{1,...,ns} , { Ĝj,k } k∈{1,...,N }, j∈{j,...,m} in the group Ĝ. The public key is pk = { Fj,µ } j∈{1,...,m},µ∈{1,...,ns} , { Ĝj,k } k∈{1,...,N }, j∈{j,...,m} while sk contains information about the representation of public elements w.r.t. specific bases.

Sign(sk, (M 1 , . . . , M N )): A vector (M 1 , . . . , M N ) ∈ G N is signed by outputting a tuple of the form σ = Z 1 , . . . , Z ns ∈ G ns . SignDerive(pk, {(ω i , σ (i) )} i=1 ): parses each σ (i) as Z (i) 1 , . . . , Z (i)
ns and computes

Z µ = i=1 Z (i) µ ω i µ ∈ {1, . . . , n s }.
After a possible extra re-randomization step, it outputs Z 1 , . . . , Z ns . Verify(pk, σ, (M 1 , . . . , M N )): given a signature σ = Z 1 , . . . , Z ns ∈ G ns and (M 1 , . . . , M N ), return 0 if (M 1 , . . . , M N ) = (1 G , . . . , 1 G ). Otherwise, return 1 if and only if the following equalities hold for j = 1 to m:

1 G T = ns µ=1 e(Z µ , Fj,µ ) • N k=1 e(M k , Ĝj,k ) j ∈ {1, . . . , m}. (9)
C Generic Signatures from One-Time Linearly Homomorphic Signature

This section shows that any one-time LHSPS can be used to build fully secure signatures in the random oracle model and in the standard model.

C.1 Generic Construction in the Random Oracle Model from the K-Linear Assumption

Let us first recall the following assumption which is a generalization of the DDH and Decision Linear assumptions.

Definition 5. For K > 0, the K-Linear assumption states that, given (g, g 1 , . . . , g K , g a 1 1 , . . . ,

g a K K , η) ∈ G 2K+2 , no PPT algorithm can decide if η = g a 1 +•••+a K or η ∈ R G.
For K = 1 (resp. K = 2), the K-linear assumption coincides with the DDH (resp. DLIN) assumption.

Given any one-time linearly homomorphic signature Π = (Keygen, Sign, SignDerive, Verify) with homomorphic key generation that works over possibly asymmetric bilinear groups (G, Ĝ, G T ), we can use a random oracle to build the following fully secure signature scheme under the K-Linear assumption.

Keygen(λ): Given a security parameter λ, the system is set up by conducting the following steps.

1. Generate a LHSPS key pair (pk, sk) ← Π.Keygen(λ, K +1) for vectors of dimension N = K +1.

Parse pk as pk = (G, Ĝ, G T ), { Fi,j,µ } j∈{1,...,m},µ∈{1,...,ns} , { Ĝi,j,k } j∈{j,...,m},k∈{1,...,K+1} . 2. Choose a hash function H : {0, 1} * → G K+1 , which will be modeled as a random oracle in the security analysis. Return the public key

P K = pk = { Fj,µ } j∈{1,...,m},µ∈{1,...,ns} , { Ĝj,k } j∈{j,...,m},k∈{1,...,K+1}
and the private key SK = sk.

Sign(SK, M

): To sign a message M ∈ {0, 1} * using SK = sk, conduct the following steps.

1. Compute (H 1 , . . . , H K+1 ) = H(M ) ∈ G K+1 . 2. Using sk, compute and output σ = (Z 1 , . . . , Z ns ) ← Π.Sign(sk, (H 1 , . . . , H K+1 )) ∈ G ns .
Verify(P K, M, σ): Given M ∈ {0, 1} L and a purported signature σ i , parse σ as (Z 1 , . . . , Z ns ) ∈ G ns and return 1 if Π.Verify(pk, (H 1 , . . . , H K+1 ),

σ i ) = 1, where (H 1 , . . . , H K+1 ) = H(M ) ∈ G K+1 .
Otherwise, it returns 0.

It is immediate that the construction is correct. We prove that it is fully secure in the random oracle model if the underlying LHSPS is one-time secure. Theorem 3. The scheme provides existential unforgeability under chosen-message attacks in the random oracle model assuming that: (i) Π is a secure one-time LHSPS; (ii) The k-Linear assumption holds in G.

Proof. The proof proceeds with a sequence of games.

Game 0: This is the real attack game. The challenger generates a public key P K which is given to the adversary A. After a series of adaptive signing queries, A produces a forgery σ on a message M that has never been submitted to the signing oracle. We define S 0 as the event that (σ , M ) is a valid forgery.

Game 1: This game is like Game 0 but we modify the treatment of random oracle queries. For each hash query H(M ), the challenger B flips a coin ϑ M ∈ {0, 1} that yields the value 1 with probability 1/(q s + 1) and 0 with probability q s /(q s + 1). At the end of the game, B considers the event E that either of the following conditions holds:

-For the target message M , the coin ϑ M ∈ {0, 1} flipped for the hash query H(M ) was ϑ M = 0. -There was a partial signing query (i, M ) for which ϑ M = 1.

If event E occurs, B halts and fails. Coron's analysis [START_REF] Coron | On the exact security of full domain hash[END_REF] shows that Pr[¬E] = 1/e(q s + 1), which implies Pr[S 1 ] = Pr[S 0 ] • Pr[¬E] = Pr[S 0 ]/e(q s + 1).

Sign(SK, M ): To generate a signature on a message M = M [START_REF] Abe | Adaptively secure Feldman VSS and applications to universally-composable threshold cryptography[END_REF] . . . M [L] ∈ {0, 1} L using the private key SK = sk, do the following.

1. Generate (Z 1 , . . . , Z ns ) ← Π.Sign(sk, g) as a one-time homomorphic signature on the onedimensional vector g ∈ G.

Using the bits M

[1] . . . M [L] of M ∈ {0, 1} L , define the vector f M = f 0 • L i=1 f M [i] i so as to assemble a Groth-Sahai CRS f M = (g 1 , g 2 , f M ). 3. Using f M = (f , f M ), compute Groth-Sahai commitments C Z,µ = (1 G , Z µ ) • g ν 1,µ 1 • g ν 2,µ 2 • f ν 3,µ M
to {Z µ } ns µ=1 for µ ∈ {1, . . . , n s }. Then, generate NIZK proofs π j ∈ G 6 that (Z 1 , . . . , Z ns ) satisfy the verification equations

1 G T = e(g, G j ) • ns µ=1
e(Z µ , F j,µ ) j ∈ {1, . . . , m}.

These NIZK proofs are obtained by proving that

1 G T = e(g, Θ j ) • ns µ=1 e(Z µ , F j,µ ) j ∈ {1, . . . , m} (10)
1 G T = e(g, Θ j ) • (g, G -1 j ) (11)
using extra variables Θ j = G j and their commitments

C Θ j = (1 G , Θ j ) • g θ 1,j 1 • g θ 2,j 2 • f θ 3,j
M . as

π j = (π j,1 , π i,2 , π j,3 , π j,4 , π j,5 , π j,6 ) = g -θ 1,j • ns µ=1 F -ν 1,µ j,µ , g -θ 2,j • ns µ=1 F -ν 2,µ j,µ , g -θ 3,j • ns µ=1 F -ν 3,µ j,µ
, g -θ 1,j , g -τ 2,j , g -θ 3,j

Return the partial signature σ i = (C Z,1 , . . . , C Z,ns , C Θ 1 , . . . , C Θm , π 1 , . . . , π m ) ∈ G 3ns+9m .

Verify(P K, M, σ): Given a L-bit message M ∈ {0, 1} L and a purported signature σ, parse σ as (C Z,1 , . . . , C Z,ns , C Θ 1 , . . . , C Θm , π 1 , . . . , π m ) ∈ G 3ns+9m , where π j = (π j,1 , π j,2 , π j,3 , π j,4 , π j,5 , π j,6 ) for each j ∈ {1, . . . , m}. Return 1 if it satisfies

1 G T = E g, C Θ j • ns µ=1 E F µ , C Z,µ • E(g 1 , π j,1 ) • E(g 2 , π j,2 ) • E(f M , π j,3 ) 1 G T = E g, C Θ j • E g -1 , (1 G , 1 G , G j ) • E(g 1 , π j,4 ) • E(g 2 , π j,5 ) • E(f M , π j,6 ),
where

f M = f 0 • L i=1 f M [i] i .
The proof of security proceeds in the same way as the proof of Theorem 2. The main change is that we need NIZK proofs for pairing product equations here. Theorem 4. The scheme provides existential unforgeability assuming that Π is a secure one-time LHSPS and that the DLIN assumption holds in G.

Proof. The proof proceeds with a sequence of games.

Game 0: This is the actual game. We call S 0 the event that the adversary A wins.

Game 1: We modify the generation of the public key. Namely, the vectors (g 1 , g 2 , {f i } L i=0 ) are chosen as g 1 = (g 1 , 1, g), g 2 = (1, g 2 , g) and {f i } L i=0 , where

f 0 = g ξ 0,1 1 • g ξ 0,2 1 • (1, 1, g) ξ 0,3 • (1, 1, g) µ•ζ-ρ 0 (12)
f i = g ξ i,1 1 • g ξ i,2 2 • (1, 1, g) ξ i,3 • (1, g) -ρ i , i ∈ {1, . . . , L} with µ R ← {0, . . . , L}, ξ 0,1 , ξ 1,1 , . . . , ξ L,1 R ← Z p , ξ 0,2 , ξ 1,2 , . . . , ξ L,2 R ← Z p , ξ 0,3 , ξ 1,3 , . . . , ξ L,3 R
← Z p and ρ 0 , ρ 1 , . . . , ρ L R ← {0, . . . , ζ -1}, with ζ = 2q and where q is the number of partial signature queries. We note that {f i } L i=0 have the same distribution as in Game 0, so that Pr[S 1 ] = Pr[S 0 ]. Game 2: We raise an event F 2 and let the simulator B abort if it occurs. Let M 1 , . . . , M q be the messages submitted by the adversary to the partial signing oracle during the game. For each message

M = M [1] . . . M [L] ∈ {0, 1} L , we define the function J(M ) = µ • ζ -ρ 0 -L i=1 ρ i • M [i]
and define F 2 to be the event that either -J(M ) = 0 -There exists a message M j ∈ {M 1 , . . . , M q } such that J(M j ) = 0. We remark that ρ 0 , ρ 1 , . . . , ρ L are completely independent of A's view. The same analysis as [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF][START_REF] Bellare | Simulation without the artificial abort: Simplified proof and improved concrete security for Waters' IBE scheme[END_REF] shows that Pr[S 2 ∧ ¬F 2 ] ≥ Pr[S 1 ] 2 /(27 • q • (L + 1)). Game 3: We change the distribution of public parameters. Namely, g 1 and g 2 are chosen as before but, instead of generating {f i } L i=0 as in Game 2, they are generated as

f 0 = g ξ 0,1 1 • g ξ 0,2 2 • (1, 1, g) µ•ζ-ρ 0 ( 13
)
f i = g ξ i,1 1 • g ξ i,2 1 • (1, 1, g) -ρ i , i ∈
f M = f 0 • L i=1 f M [i] i = g K 1 (M ) 1 • g K 2 (M ) 2 • (1, 1, g) J(M ) ,
where

K 1 (M ) = ξ 0,1 + L i=1 ξ i,1 , K 2 (M ) = ξ 0,2 + L i=1 ξ i,2 .
Using the trapdoor information (K 1 (M ), K 2 (M ), J(M )), the challenger generates a simulated NIZK proof π i,j .

To generate a proof for equation [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF], B uses the assignment Θ j = 1 G and Z µ = 1 G for µ ∈ {1, . . . , n s }, j ∈ {1, . . . , m}, which allows honestly generating a proof for [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF]. As for equation [START_REF] Boneh | Short group signatures[END_REF], the challenger can use (K 1 (M ), K 2 (M ), J(M )) to generate a fake proof that Θ j = G j by trapdoor opening the commitment to

C Θ j = g θ 1,j 1 • g θ 2,j 2 • f θ 3,j
M which was computed as a commitment to 1 G . Namely, it can compute

π j,4 = g θ 1,j • G K 1 (M ) J(M ) j , π j,5 = g θ 2,j • G K 2 (M ) J(M ) j , π j,6 = g θ 3,j • G -1 J(M ) j ,
which forms a valid proof for equation [START_REF] Boneh | Short group signatures[END_REF] and is always computable when J(M ) = 0. Given that simulated NIZK proofs are perfectly indistinguishable from real proofs on a witness indistinguishable CRS, A's view is the same as in Game 3, so that Pr

[S 4 ∧ ¬F 2 ] = Pr[S 3 ∧ ¬F 2 ].
In Game 4, we claim that B can be turned into a LHSPS forger running in about the same time as A and for which Pr[S 4 ∧ ¬F 2 ] ≤ Adv LHSPS (B).

To break the security of Π, B interacts with its own challenger that provides it with a public key pk = {F j,µ } j∈{1,...,m},µ∈{1,...,ns} , {G j } j∈{j,...,m} for Π. Then, B generates (g 1 , g 2 , {f i } L i=0 ) as in Game 4 so as to form P K, which is given to A.

The adversary's signing queries are answered by simulating NIZK proofs as in Game 4 in such a way that B never has to invoke its own signing oracle. When the adversary outputs a forgery (σ , M ), we know that (g 1 , g 2 , f M ) is an extractable Groth-Sahai CRS if event ¬F 2 occurs. Using the discrete logarithms (log g (g 1 ), log g (g 2 )), B can thus extract a valid LHSPS from the Groth-Sahai commitments contained in σ .

D Deferred Proofs for Theorem 1

Lemma 1. Under the DDH assumption in G, Game 2 is computationally indistinguishable from Game 1.

Proof. The proof is by contradiction and builds a straightforward DDH distinguisher B from an adversary A that has noticeably different behaviors in Game 1 and Game 2.

The reduction B receives as input a pair (g, g x , g y , T ) and has to decide whether T = g xy or T ∈ R G. To this end, algorithm B begins by generating P K, SK and VK in the same way as in the real scheme. In addition, it defines h = g y . Throughout the game, B always answers partial signing queries and corruption queries faithfully. However, the treatment of random oracle queries H(M ) depends on the value of the biased coin δ M ∈ {0, 1}. Namely, when δ M = 0, B uses the random self-reducibility of DDH and builds many DDH instances out of one.

-

If δ M = 0, B chooses α M , β M R ← Z p , computes (g M , h M ) = ((g x ) α M • g β M , T α M • (g y ) β M )
and programs the random oracle so as to have H(M ) = (H 1 , H 2 ) = (g M , h M ). Observe that, if T = g xy , the pair (H 1 , H 2 ) = (g M , h M ) has the same distribution as in Game 2 as it can be written

(H 1 , H 2 ) = (g z M , h z M ) with z M = x • α M + β M . In contrast, if T ∈ R G, we can write T = g xy+z for some random z ∈ R Z p . In this case, we have (H 1 , H 2 ) = (g z M , h z M +x•α M ), so that (H 1 , H 2 ) ∈ R G 2 . -If δ M = 1, B draws g M , h M R ← G 2 and defines H(M ) = (g M , h M ).
When A terminates, B outputs a random bit if event E has come about during the game. Otherwise, B outputs 1 if b = b and 0 otherwise.

Clearly, if T = g xy , A's view is exactly the same as in Game 2. In contrast, if T is uniform in G, B is rather playing Game 1 with the adversary.

E A Construction Based on the DLIN Assumption

This section shows a variant of our first construction based on the Decision Linear assumption [START_REF] Boneh | Short group signatures[END_REF], which is believed to be strictly weaker than SXDH. The scheme retains adaptive security in the random oracle model even in groups (G, Ĝ, G T ) endowed with efficiently computable isomorphisms between G and Ĝ. Definition 6 ( [START_REF] Boneh | Short group signatures[END_REF]). The Decision Linear Problem (DLIN) in G, is to distinguish the distributions (g a , g b , g ac , g bd , g c+d ) and (g a , g b , g ac , g bd , g z ), with a, b, c, d

R ← Z p , z R ← Z p .
For convenience, we also consider the following assumption. Any algorithm solving the SDP problem immediately yields a DLIN distinguisher in the group Ĝ. From a DLIN 2 instance (ĝ, ĝa , ĝac , ĝb , ĝbd , η), we create an SDP instance (ĝ ac , ĝa , ĝbd , ĝb ). If the SDP solver finds (z, r, u) such that e(z, ĝac ) • e(r, ĝa ) = 1 G T and e(z, ĝbd ) • e(u, ĝb ) = 1 G T , we know that r = z -c and u = z -d . To decide if η = ĝc+d , it is sufficient to check whether e(r • u, ĝ) • e(z, η) = 1 G T .

Here, we need public parameters params consisting of four generators ĝz , ĝr , ĥz , ĥu ∈ R Ĝ. Again, ĝr , ĥz , ĥu can be derived from a random oracle so as to avoid the need to generate them in a in a distributed manner while still making sure that no party knows their discrete logarithms. λ, t, n): given params = {(G, Ĝ, G T ), ĝz , ĝr , ĥz , ĥu , , H}, a security parameter λ and integers t, n ∈ N such that n ≥ 2t + 1, the player P 1 , . . . , P n proceed as follows. 1. Each player P i shares random triples {(a ik0 , b ik0 , c ik0 )} 3 k=1 . To this end, he does the following:

a. For each k ∈ {1, 2, 3}, choose random polynomials A ik [X] = a ik0 + a ik1 X + • • • + a ikt X t , B ik [X] = b ik0 + b ik1 X + • • • + b ikt X t and C ik [X] = c ik0 + c ik1 X + • • • + c ikt X t ∈ Z p [X] of degree t and broadcast Vik = ĝz a ik ĝr b ik Ŵik = ĥz a ik ĥu c ik ∀ ∈ {0, . . . , t} b. For j = 1 to n, send {(A ik (j), B ik (j), C ik (j))} 3 k=1 to P j . 2. For each received shares {(A jk (i), B jk (i), C jk (i))} 3 k=1 , player P i verifies that ĝA jk (i) z ĝB jk (i) r = t =0 V i jk ĥA jk (i) z ĥC jk (i) u = t =0 Ŵ i jk ∀k ∈ {1, 2, 3}. (14)
If these equalities do not both hold, P i broadcasts a complaint against P j . 3. Any player who receives strictly more than t complaints is disqualified. Each player P i who received a complaint from another player P j responds by returning the correct shares {(A ik (j), B ik (j), C ik (j))} 3 k=1 . If any of these new shares does not satisfy ( 14), P i is disqualified. Let Q ⊂ {1, . . . , n} be the set of players who are not disqualified at the end of step 3. 4. The public key is obtained as P K = {ĝ k , ĥk } 3 k=1 , where ĝk = i∈Q Vik0 = ĝ i∈Q a ik0 z ĝ i∈Q b ik0 r and ĥk = i∈Q Ŵik0 = ĥ i∈Q a ik0 z ĥ i∈Q c ik0 u . Each P i locally defines his private key share

SK i = {(A k (i), B k (i), C k (i))} 3 k=1 = { j∈Q A jk (i), j∈Q B jk (i), j∈Q C jk (i) } 3 k=1
and anyone can publicly compute his verification key

V K i = { Ûk,i = ĝz A k (i) ĝr B k (i) } 3 k=1 , { Ẑk,i = ĥz A k (i) ĥu C k (i) } 3 k=1 . as ( Ûk,i , Ẑk,i ) = j∈Q t =0 V i jk , j∈Q t =0 Ŵ i jk
for each i ∈ Q and k ∈ {1, 2, 3}. For any disqualified player i ∈ {1, . . . , n}\Q, the i-th private key share is implicitly set as SK i = {(0, 0, 0)} 3 k=1 and the corresponding verification key is V K i = {1 Ĝ, 1 Ĝ} 3 k=1 . The vector of private key shares is SK = (SK 1 , . . . , SK n ) while the corresponding vector of verification keys VK = (V K 1 , . . . , V K n ) and the public key, which consists of

P K = params, { ĝk , ĥk } 3 k=1 .
Share-Sign(i, SK i , M ): to generate a partial signature on a message M ∈ {0, 1} * using its private key share

SK i = {(A k (i), B k (i), C k (i))} 3 k=1
, the i-th server first computes the hash value (H 1 , H 2 , H 3 ) = H(M ) ∈ G 3 and generates the partial signature as

z i = 3 k=1 H -A k (i) k r i = 3 k=1 H -B k (i) k u i = 3 k=1 H -C k (i) k
The partial signature consists of σ i = (z i , r i , u i ) ∈ G 3 . Share-Verify P K, V K i , M, (i, σ i ) : given the partial signature σ i = (z i , r i , u i ) ∈ G 3 and the verification key

V K i = { Ûk,i , Ẑk,i } 3 k=1 , compute (H 1 , H 2 , H 3 ) = H(M ) ∈ G 3 and return 1 iff e(z i , ĝz ) • e(r i , ĝr ) • 3 k=1 e(H k , Ûk,i ) = 1 G T e(z i , ĥz ) • e(u i , ĥu ) • 3 k=1 e(H k , Ẑk,i ) = 1 G T Combine(P K, VK, M, {(i, σ i )} i∈S ): given a (t + 1)-set with valid shares {(i, σ i )} i∈S , parse the sig- nature share σ i as z i , r i , u i ∈ G 3 for each i ∈ S. Then, compute (z, r, u) = i∈S z ∆ i,S (0) i , i∈S r ∆ i,S (0) i , i∈S u ∆ i,S (0)
σ = (z, r, u) ∈ G 3 , compute (H 1 , H 2 , H 3 ) = H(M ) ∈ G 3 and return 1 if
and only if (z, r, u) satisfy the equalities e(z, ĝz ) • e(r, ĝr )

• 3 k=1 e(H k , ĝk ) = 1 G T e(z, ĥz ) • e(u, ĥu ) • 3 k=1 e(H k , ĥk ) = 1 G T .
The scheme can be proved adaptively secure under the DLIN assumption. The proof is, mutatis mutandis, identical to the proof of Theorem 1 and omitted here. Theorem 5. The scheme provides adaptive security in the random oracle model if the DLIN assumption holds in both G and Ĝ. Concretely, for any PPT adversary A, there exist efficient DLIN distinguishers B 1 and B 2 in the groups G and Ĝ, respectively, such that

Adv(A) ≤ e • (q s + 1) • Adv DLIN 1 (B 1 ) + Adv DLIN 2 (B 2 ) + 1 p ,
where q s is the number of signing queries and e is the base for the natural logarithm.

F A Construction Supporting Signature Aggregation

In this section, we show how to extend the scheme of Section 3 so as to enable unrestricted signature aggregation. We consider non-interactive distributed aggregate signatures which are threshold signatures augmented with two additional algorithms named Aggregate and Aggregate-Verify. The former takes as input a set of public keys {P K j } j=1 with the corresponding message-signature pairs {(M j , σ (j) )} j=1 and returns a constant-size aggregate signature σ. The corresponding aggregate verification algorithm inputs an aggregate signature σ and a set of pairs {(P K j , M j )} j=1 and returns 1 if and only if it accepts σ as convincing evidence that signer j indeed signed M j . The security of an aggregate threshold signature is defined via a game which is identical to the game of Definition 1 except that, instead of outputting a single message-signature pair in stage 3, the adversary outputs an aggregate signature σ and a list of pairs {(P K j , M j )} j=1 . Formally, the adversary is given public parameters params and interacts with the challenger during the generation of the challenge public key P K . In the second phase, the adversary is granted access to an adaptive corruption oracle as well as a partial signing oracle for all servers that hold a share SK i of the matching private key SK . Eventually, the adversary outputs σ and {(P K j , M j )} j=1 . It wins under the following conditions: (i) Aggregate-Verify({(P K j , M j )} j=1 , σ ) = 1; (ii) The set {(P K j , M j )} j=1 contains at least one pair (P K j , M j ) such that P K j = P K and, if S ⊂ {1, . . . , n} denotes the set of players for which A obtained a partial signature on M j , then |S ∪ C| ≤ t.

Here, we assume public parameters params containing two extra generators g, h ∈ R G in addition to those of the scheme in Section 3. The distributed key generation phase is as in Section 3, with the difference that the players jointly generate a one-time linearly homomorphic signature on the vector (g, h) ∈ G 2 and incorporate this signature in the public key. In the aggregate verification process, the verifier performs a sanity check on public keys and only accepts aggregate signatures where all involved public keys contain a linearly homomorphic signature on (g, h).

Looking ahead, these homomorphic signatures will be useful in the security proof when it comes to extract an ordinary signature from the adversary's fake aggregate signature. More specifically, they allow the reduction to recover the contribution of adversarially generated keys to the aggregate signature in order to remove it from the aggregate. To this end, another solution would have been to assume registered public keys (as done in Boldyreva's multi-signatures [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme[END_REF]) and force the adversary to reveal the underlying private key whenever it generates a public key for itself. We found it more natural to introduce a built-in proof of validity in each public key.

Dist-Keygen(params, λ, t, n): Given params = {(G, Ĝ, G T ), g, h, ĝz , ĝr , H}, a security parameter λ and integers t, n ∈ N with n ≥ 2t + 1, the players proceed as follows. Then, broadcast values

Z i0 = g -a i10 h -a i20 R i0 = g -b i10 h -b i20 ,
which form a homomorphic signature on the vector (g, h) for the public key ( Ŵi10 , Ŵi20 ). b. For j = 1 to n, send {(A ik (j), B ik (j))} 2 k=1 to P j . 2. For each received shares {(A jk (i), B jk (i))} 2 k=1 , player P i verifies that ĝA jk (i)

z ĝB jk (i) r = t =0 Ŵ i jk for k = 1, 2. ( 15
)
and e(Z j0 , ĝz ) • e(R j0 , ĝr ) • e(g, Ŵj10 ) • e(h, Ŵj20 ) = 1 G T . If equalities (15) do not both hold, P i broadcasts a complaint against P j . 3. Any player P i who sent incorrect verification values (Z i0 , R i0 ) or received more than t complaints is immediately disqualified. Each player P i who received a complaint from another player P j responds by returning the correct shares {(A ik (j), B ik (j))} 2 k=1 . If any of these new shares fail to satisfy [START_REF] Boyd | Digital Multisignatures[END_REF], P i is disqualified. Let Q ⊂ {1, . . . , n} be the set of non-disqualified players at the end of step 3. its BLS challenger when P K = P K BLS and handles the query itself when P K = P K BLS . In the threshold setting, this approach is problematic because random oracle queries may occur during the distributed key generation protocol, before the challenge public key P K is defined. Since P K is not necessarily uniform due to the use of Pedersen's protocol, we cannot trivially rule out hash queries of the form H(P K , M ) during the key generation phase. While Gennaro et al. [START_REF] Gennaro | Secure applications of Pedersen's distributed key generation protocol[END_REF] properly addressed a similar problem in the static corruption setting, we found it simpler to give a direct proof under the underlying number theoretic assumptions here.

Theorem 6. The above threshold aggregate signature is secure under adaptive corruptions in the random oracle under the SXDH assumption in (G, ĜT ). Concretely, any PPT adversary A implies DDH distinguishers B 1 and B 2 with comparable running times in the groups G and Ĝ, respectively.

Proof. In order to prove the result, we consider a sequence of games which is similar to that in the proof of Theorem 1. For each i ∈ {0, 1}, we call S i the event that the adversary wins game i.

Game 0: This game the actual attack game during which all random oracle queries are answered by returning uniformly random group elements in G 2 . We assume that all hash queries are distinct. At the beginning, the challenger B assumes the role of all uncorrupted players when executing the Dist-Keygen protocol in interaction with the adversary A. When A chooses to corrupt a player P i , the challenger sets C = C ∪ {i}, G = G\{i} and reveals the internal state of P i . From this point forward, A has full control over P i and may cause him to deviate from the protocol. The distributed key generation phase thus ends with the generation of a challenge public key P K = { ĝk , ĥk } 2 k=1 , Z , R . At this point, the aggregate adversary A has also obtained the vector of verification keys VK = (V K 1 , . . . , V K n ), as well as the private key shares SK i of all corrupted players i ∈ C so far and their internal state, including their polynomials A ik [X] and B ik [X]. In the next phase, partial signature queries (i, M ) are answered by faithfully computing the pair (z i , r i ) = . When A terminates, it outputs a purported aggregate signature σ together with a list of pairs {(P K j , M j )} j=1 . We assume that the adversary queries all hash values {H(P K j , M j )} j=1 before outputting its forgery. We denote by S 0 the event that σ = (z , r ) is a valid forgery. Recall that S 0 implies that {(P K j , M j )} j=1 contains at least one pair (P K j , M j ) such that P K j = P K and |C ∪ S| ≤ t, where S ⊂ {1, . . . , n} denotes the subset of players that have generated a partial signature on M j . If {(P K j , M j )} j=1 contains several pairs satisfying the latter condition, we define (P K j , M j ) to be the first one in lexicographical order.

At the end of the game, we define the set L as the union of {(P K j , M j )} j=1 \{(P K , M j )} and the set {(P K , M )} qs j=1 of pairs (P K , M ) such that M = M j and A obtained a partial signature on M . Clearly, the size of L is at most |L| ≤ q s + n max -1.

Game 1: This game is like Game 0 with one difference. For each hash query M = (P K||M ), the challenger B flips a coin ϑ M ∈ {0, 1} that takes the value 1 with probability 1/(q s + n max ) and the value 0 with probability 1 -1/(q s + n max ). At the end of the game, B considers the event E that at least one of the following conditions holds:

-For the message M = (P K , M j ), the coin ϑ M ∈ {0, 1} associated with the random oracle query H(P K , M j ) was ϑ M = 0. -The list L contains an entry (P K, M ) for which ϑ (P K||M ) = 1.

Note that B can recognize event E at the end of the game. If it occurs, B halts and reports failure. Coron's analysis [START_REF] Coron | On the exact security of full domain hash[END_REF] shows that Pr[¬E] = 1/e(q s + n max ), where e is the base for the natural logarithm, so that we have Pr[S 1 ] = Pr[S 0 ] • Pr[¬E] = Pr[S 0 ]/e(q s + n max ).

Game 2: We modify the input-output behavior of the random oracle and let the treatment of each hash query H(P K||M ) depend on the random coin ϑ M ∈ {0, 1}.

R←

  Z p and ρ 0 , ρ 1 , . . . , ρ L R ← {0, . . . , ζ -1}, with ζ = 2q and where q is the number of partial signature queries. This change is only conceptual since {f i } L i=0 have the same distribution as in Game 0. We thus have Pr[S 1 ] = Pr[S 0 ].

  {1, . . . , L} which amounts to setting ξ 0,3 = ξ 1,3 = . . . = ξ L,3 = 0. Under the DLIN assumption in G, this change should not noticeable modify the probability of event S 2 ∧ ¬F 2 . Concretely, if events S 2 ∧¬F 2 and S 3 ∧¬F 2 occur with significantly different probabilities in Game 2 and Game 3, we can construct a DLIN distinguisher B. The latter takes as input a DLIN instance (g, g 1 , g 2 , g a 1 , g b 2 , Z), where a, b R ← Z p and Z = g a+b or Z ∈ R G. Using the random self-reducibility of DLIN, we can create L + 1 DLIN instances -which are all linear tuples (resp. random tuples) if Z = g a+b (resp. Z ∈ R G) -and embed them in {f i } L i=0 in such a way that {f i } L i=0 is distributed as in Game 2 (resp. Game 3) if Z ∈ R G (resp. Z = g a+b ). For this reason, we obtain the inequality | Pr[S 3 ∧ ¬F 2 ] -Pr[S 2 ∧ ¬F 2 ]| ≤ Adv DLIN (B). Game 4: We modify the signature generation oracle. Namely, at each signing query on a message M = M [1] . . . M [L], the challenger assembles the Groth-Sahai CRS (g 1 , g 2 , f M ), where

Definition 7 .

 7 The Simultaneous Double Pairing problem (SDP) in (G, Ĝ, G T ) is, given a tuple ( ĝz , ĝr , ĥz , ĥu ) ∈ Ĝ4 , to find a non-trivial triple (z, r, u) ∈ G 3 \{(1 G , 1 G , 1 G )} such that the equalities e(z, ĝz ) • e(r, ĝr ) = 1 G T and e(z, ĥz ) • e(u, ĥu ) = 1 G T are satisfied.

  i by Lagrange interpolation in the exponent. Return the pair (z, r, u) ∈ G 3 . Verify P K, M, σ : given

1 .

 1 Each player P i does the following:a. For each k ∈ {1, 2}, choose random polynomials A ik [X] = a ik0 + a ik1 X + • • • + a ikt X t , B ik [X] = b ik0 + b ik1 X + • • • + b ikt X t ∈ Z p [X]of degree t and broadcast Ŵik = ĝz a ik ĝr b ik ∀ ∈ {0, . . . , t}.

4 .

 4 The public key P K is obtained asP K = {ĝ k } 2 k=1 , Z, R , where ĝk = i∈Q Ŵik0 = ĝ i∈Q a ik0 z ĝ i∈Q b ik0 r

Namely, the private key space forms an additive group such that, for any message M , given any two signatures σ1 ← Sign(sk1, M ) and σ2 ← Sign(sk2, M ), anyone can compute a valid signature on M for the private key sk1 + sk2.

Game 2: This game is identical to Game 1 except for one difference. At the outset of the game, B picks g, g 1 , . . . , g K R ← G, a 1 , . . . , a K R ← Z p and defines vectors g 1 = (g a 1 1 , 1, . . . 1, g) ∈ G K+1 , g 2 = (1, g a 2 2 , 1, . . . 1, g) ∈ G K+1 , . . . , g K = (1, . . . , 1, g a K K , g) ∈ G K+1 . Then, the distribution of random oracle outputs is modified as follow depending on the random coin ϑ M ∈ {0, 1}.

-If ϑ M = 0, the challenger B defines H(M ) ∈ G K+1 to be a random linear combination

where α 1 , . . . , α K R ← Z p . Note that H(M ) lives in a proper subspace of G K+1 . -If ϑ M = 1, B defines H(M ) as a random vector of G K+1 .

Clearly, although H is no longer a true random oracle, it still looks like one in A's view if the K-Linear assumption holds. We have

In Game 2, A can be used by the challenger B to break the one-time security of Π. Specifically, B takes as input a public key pk for Π, which is also given as a challenge public key to A.

Before starting its interaction with A, our LHSPS adversary B invokes its own challenger to obtain linearly homomorphic signatures σ1 , . . . , σK on the vectors g 1 , . . . , g K ∈ G K+1 . If event ¬E occurs, we know that A only obtains signatures on messages M such that H(M ) lives in the linear subspace spanned by (g 1 , . . . , g K ). In this case, B is always able to answer signing queries on its own. Indeed, it can use the coefficients α 1 , . . . , α K ∈ Z p such that H(M ) = K i=1 g α i i in order to obtain and return a signature σ ← Π.SignDerive(pk, {(α i , σi )} K i=1 ) on M without any further help from its own signing oracle.

When the adversary outputs a valid forgery (σ , M ), we know that, if event ¬E occurs, the vector H(M ) = (H 1 , . . . , H K+1 ) lands outside span(g 1 , . . . , g k ), which means that (σ , H(M )) is a valid forgery for Π.

C.2 Construction in the Standard model from any One-Time LHSPS

This section shows how to use the DLIN-based instantiation of Groth-Sahai proofs to build a fully secure digital signature from any one-time LHSPS in symmetric bilinear groups (i.e., where G = Ĝ).

In the standard model, the generic construction uses the same design principle as the scheme of Section 4 in that it proceeds by generating a non-interactive proof of knowledge of a one-time homomorphic signature on a fixed vector. The difference is that, while NIWI proofs for pairing product equations were sufficient in the scheme of Section 4, we need NIZK proofs here. Fortunately, although pairing product equations are not known to always admit efficient NIZK simulators, they can be realized while keeping constant-size signatures.

Given any one-time linearly homomorphic signature Π = (Keygen, Sign, SignDerive, Verify) in symmetric bilinear groups, we can construct a fully secure signature as follows.

Keygen(λ):

The system is set up by conducting the following steps.

1. Generate a LHSPS key pair (pk, sk) ← Π.Keygen(λ, 1) for vectors of dimension N = 1. Parse pk as pk = (G, G T ), {F i,j,µ } j∈{1,...,m},µ∈{1,...,ns} , {G i,j } j∈{j,...,m} .

Choose generators

Return the public key

), pk = {F j,µ } j∈{1,...,m},µ∈{1,...,ns} , {G j } j∈{j,...,m} and the secret key SK = sk.

Each P i locally defines his private key share

and anyone can publicly compute his verification key V K i = V1,i , V2,i as

Any disqualified player i ∈ {1, . . . , n}\Q has his private key share (resp. its verification key) implicitly set as

The public key finally consists of

Share-Sign(i, SK i , M ): To create a partial signature on a message M ∈ {0, 1} * using his private key share

As we can see, Share-Sign is as in Section 3 with the sole difference that the public key is appended to the message which is actually being signed. Algorithms Share-Verify and Combine are identical to those of Section 3. We thus focus on the signature aggregation and verification algorithms. For convenience, we define the standard verification algorithm as a special case of the Aggregate-Verify algorithm when = 1.

Aggregate({(P K j , σ (j) , M j )} j=1 ): Given a set of triples (P K j , σ (j) , M j ), parse each public key P K j as P K j = (params, ĝ1 (j) , ĝ2 (j) , Z (j) , R (j) ) and return ⊥ if it does not parse properly. Then, parse each signature σ (j) as (z (j) , r (j) ) and return ⊥ if there exists j ∈ {1, . . . , } such that Verify(P K j , M j , σ (j) ) = 0. Otherwise, compute and return (z, r) = j=1 z (j) , j=1 r (j) . Aggregate-Verify {(P K j , M j )} j=1 , σ : Given a candidate aggregate signature σ = (z, r) ∈ G 2 , compute (H

2 ) = H(P K j ||M j ) ∈ G × G for each j ∈ {1, . . . , } and return 1 if and only if the following equality holds e(z, ĝz ) • e(r, ĝr )

and, for each j ∈ {1, . . . , }, P K j = params, ĝ1 (j) , ĝ2 (j) , Z (j) , R (j) satisfies the sanity check below e(Z (j) , ĝz ) • e(R (j) , ĝr ) • e(g, ĝ(j)

Like Bellare et al. [START_REF] Bellare | Unrestricted aggregate signatures[END_REF], we consider a security model where aggregate signatures may involve multiple messages from the same signer. The proof of Theorem 6 combines the proof of Theorem 1 and ideas of [START_REF] Bellare | Unrestricted aggregate signatures[END_REF].

However, while Bellare et al. [START_REF] Bellare | Unrestricted aggregate signatures[END_REF] prove the security of their unrestricted BGLS aggregate signatures via a reduction from the security of BLS signatures [START_REF] Boneh | Short signatures from the Weil pairing[END_REF], we need a direct proof under the SXDH assumption. The reason is that, in the proof of [START_REF] Bellare | Unrestricted aggregate signatures[END_REF]Lemma 3.3], the reduction interacts with a BLS challenger on input of a public key P K BLS while emulating the aggregate adversary's challenger. Whenever the latter makes a random oracle query H(P K||M ), the reduction forwards the query to

and defines H(P K||M ) = (g α M , h α M ). Note that the resulting hash value H(P K||M ) ∈ G 2 now lives in the linear subspace spanned by (g, h) ∈ G 2 .

-If ϑ M = 1, B chooses a uniformly random pair (g M , h M ) ∈ G 2 and sets H(P K||M ) = (g M , h M ). The same argument as in the proof of Lemma 1 shows that Game 2 and Game 1 are computationally indistinguishable if the DDH assumption holds in the group G. It follows that

In Game 2, we can prove that Pr[S 2 ] ≤ Adv(B) DP (λ) + 1/p as B can be turned into an algorithm solving the DP problem, as in the proof of Theorem 1. We actually show that B can use the fake aggregate signature (z , r ) -which involves a message M j on behalf of P K although the sets C and S are such that |C ∪ S| ≤ t -produced by the adversary to extract a valid ordinary signature (z , r ) on M j with respect to the challenger public key P K . In turn, this forgery (M j , (z , r )) can be used to break the DP assumption in the same way as in the proof of Theorem 1.

To extract, an ordinary signature (z , r ) from (z , r ), B proceeds in the same way as in the proof of [START_REF] Bellare | Unrestricted aggregate signatures[END_REF]Lemma 3.3]. If ¬E occurs, if we define the subset W := {(P K j , M j )} j=1 \{(P K , M j )} ⊂ L, then all pairs (P K, M ) ∈ W have been assigned the bit ϑ (P K||M ) = 0, which means that H(P K||M ) was defined as (g α M , h α M ) for some random α M ∈ R Z p chosen by B. It implies that, as long as

) is a valid signature on M w.r.t. P K since (Z, R) is a homomorphic signature on (g, h) (this follows from the linearly homomorphic property of the scheme in Section 2.3). For all pairs M = (P K, M ) ∈ W, B can thus compute a valid signature (z M , r M ) and divide it from the aggregate forgery (z , r ). If τ ∈ {1, . . . , } denotes the number of occurrences of (P K , M j ) in

which is a valid ordinary signature on M j by construction.

We also know that, conditionally on event ¬E, for all messages M = M j , the queried hash value H(P K ||M ) falls in the subspace spanned by (g, h). This guarantees that B has not leaked too much information about the private key shares of honest players, which allows applying the same arguments as in the proof of Theorem 1 when it comes to argue that the DP problem can be solved with non-negligible probability in Game 2.

When putting the above altogether, the adversary's advantage can be bounded by

where q s is the number of signing queries, e is the base for the natural logarithm and n max denotes the maximal number of message-public-key pairs in an aggregate.