Identity-Based Aggregate and Multi-Signature Schemes Based on RSA

From Bauman National Library
This page was last modified on 12 December 2015, at 16:25.

Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG
Authors Ali Bagherzandi[@: 1],
and Stanislaw Jarecki[@: 2]
Published 2010 г.
Licence  ?
Web site  ?
Status  ?
Download оригинал


We propose new identity-based multi-signature (IBMS) and aggregate signature (IBAS) schemes, secure under RSA assumption. Our schemes reduce round complexity of previous RSA-based IBMS scheme of Bellare and Neven [1] from three to two rounds. Surprisingly, this improvement comes at virtually no cost, as the computational efficiency and exact security of the new scheme are almost identical to those of [1]. The new scheme is enabled by a technical tool of independent interest, a class of zero-knowledge proofs of knowledge of preimages of one-way functions which is straight-line simulatable, enabling concur- rency and good exact security, and aggregatable, enabling aggregation of parallel instances of such proofs into short multi/aggregate signatures.


A multisignature protocol allows a group of players to sign the same message by generating a short string, called a multisignature, which can be verified against the set of the public keys of these players. Aggregate signature is a generaliza- tion of this notion to the case where each player signs a potentially different message. Such schemes reduce the bandwidth needed to transmit signatures, the space needed to store them, and the time needed to verify them, from linear in the number of the cosigners to a constant. Reducing bandwidth is especially important for low-energy devices, such as RFID chips and sensors, which com- municate over energy-consuming wireless channels where data transmision con- sumes several orders of magnitude more energy than arithmetic operations (see e.g. [2]). Standard multi-/aggregate signatures reduce the space taken by signatures from to , but the verifiers still need the public keys of signers. Therefore in applications where bandwidth is a bottleneck it can be useful to consider identity-based multi-/aggregate signatures where verifiers only need unique identifiers of signers, e.g. 32-bit IP addresses, instead of public keys.

Identity-Based (Multi-/Aggregate) Signatures. Identity-based cryptog- raphy [3] simplifies public key management by replacing users’ public keys with their identity e.g. their names, e-mails or IP addresses. In identity-based scheme a trusted party, a Private Key Generator (PKG), generates a private key corresponding to each user’s identity, and messages signed using such keys can be then verified using the signer’s identity and the PKG’s master public key. In the case of identity-based multi-/aggregate signatures, if all signers have their private keys issued by the same PKG then the verifier needs only the PKG’s master public key and the identities of all signers. Note that in many applica- tions the identities of signers are often present in the protocol messages, e.g. the usernames or IP addresses in packet headers, in which case an identity-based multi-/aggregate signature adds only a constant bandwidth overhead over un- authenticated messages.

Current State of the Art. Standard signatures imply identity-based signa- tures following the “certification paradigm”, e.g. [4], i.e. by simply at- taching signer’s public key and certificate to each signature. However, it is not clear how to apply this idea to convert standard multi-/aggregate signatures, e.g. [5],[6], into identity-based ones, because it is not clear how to aggregate separate public keys and certificates, even if all certificates are signed by the same CA. (Standard aggregate signatures can be used to eliminate the overhead of CA’s signatures on the certificates, but this would not eliminate the overhead due to the public keys.) The first efficient IBAS/IBMS schemes designed from scratch are due to Gen- try and Ramzan [7]. Their schemes employ a group with a bilinear map, their security relies, in the Random Oracle Model (ROM), on the hardness of GapDH problem, the schemes are non-interactive, and both the signing and veri- fication times take exponentiations and bilinear map operations. However, the IBAS scheme of [7] requires all cosigners to share a common token for every set of signatures they want to aggregate, and each cosigner must ensure that this token has not been previously used in signing a different message, hence in some applications this scheme will need an extra communication round for the participants to agree on a fresh common token. In subsequent work, Boldyreva et. al [8] (correcting a previous version of this paper) proposed an IBAS scheme which does not need these unique tokens but it requires sequential com- munication pattern, and it is based on a more complex bilinear map assumption. Note that while sequential communication is perfectly suited to some applica- tions, e.g. secure route discovery [9], it introduces unnecessary overhead for players connected e.g. by a broadcast channel or a tree topology. Without bilinear maps, Bellare and Neven [1] gave an IBMS scheme which relies on the RSA assumption in ROM. Their scheme also has fast multi- signature generation and verification, requiring exponentiations, but it takes three rounds of interaction. Note that any 3-round IBMS implies a 4- round IBAS if all cosigners’ messages are broadcast and the IBMS scheme is run on their concatenation. (Moreover, in the IBMS scheme of [1] this broadcast can be piggybacked on the first protocol round, giving a 3-round IBAS scheme.) However, such broadcast of all messages to all co-signers imposes bandwidth usage which might not be otherwise required, and so apart from this generic transformation it is interesting to consider IBAS schemes which do not require such broadcast. (As a side remark, we believe that the 3-round IBMS scheme of [1] can be modified to a 3-round IBAS scheme without such broadcast, e.g. using ideas similar to our IBAS scheme [10].)

IBAS/IBMS Schemes Restrictions Number of Rounds Verification Time Signing Time Signature Length
[7]-IBAS GapDH Stateful 1 3P+nM 5M
[8] GapDH Sequential 1 6P+nM 7M
[7]-IBMS GapDH - 1 3P 3M
[1] RSA - 3 1E 2E

Fig. 1.

  • (1) All schemes have been given security proofs only in the ROM model;
  • (2) The IBAS scheme of [7] assumes that the players share a unique and common token for every instance of the IBAS scheme. This requirement can be avoided at the cost of an additional round of interaction, while the scheme of [8] requires sequential aggregation;
  • (3) Signing time is measured per player. In both signing and verification costs, is the cost of one pairing operation, is the cost of scalar multiplication on an elliptic curve, and is the cost of (multi-)exponentiation in (with about 80-bit exponents);
  • (4) Signature length is measured in bits where is the security parameter, is an RSA modulus, is an upper bound on the number of players, and are two groups of elliptic curve points with an asymmetric bilinear map, is a group of elliptic curve points with a symmetric bilinear map, and stands for the bitsize of representation of elements in group . Typical values for these parameters are , , , , and or .

Our Contributions. We propose IBMS and IBAS schemes secure under RSA assumption in ROM which require only two rounds of communication. This provides alternatives to IBMS/IBAS schemes based on bilinear maps especially in applications which intrinsically take two communication rounds, such as authenticated route discovery or aggregation of broadcast acknowledgements. Since bilinear map operations are still more expensive than RSA exponentiation, our computational costs are slightly lower in signing and significantly lower in verification, compared to e.g. [7], although our signatures are longer. A summary of these comparisons is in Figure 1.

Further Related Work. Gregory Neven introduced two primitives, sequential aggregate signed data and multisigned data, corresponding to aggregate signatures and multisignatures respectively, whose goal is to minimize the total bandwidth consumed by signatures and messages incurred in transmission of authenticated data originated by multiple sources [11]. His constructions use message recovery techniques to squeeze message bits into a (multi/aggregate) signature. Comparing his work to ours, we note that

  • (1) his schemes support only sequential aggregation when signing different messages;
  • (2) bandwidth savings depend on message sizes (for small messages the bandwidth can be worse than with standard signatures);
  • (3) these schemes do not address the overhead due to public keys, which raises an interesting question whether total bandwidth due to signatures and messages can be further reduced, perhaps using message-recovery techniques, with identity-based multi/aggregate signatures. In other related work Herranz and Galindo et. al [12],[4] show identity-based signatures which can be aggregated if they originate from the same signer.

Organization/Roadmap. Section 2 contains a technical overview of our constructions. In Section 3 we define IBMS schemes. (We relegate a formal description of IBAS schemes to [10].) In Section 4 we develop our tools, namely we introduce structured-instance zero-knowledge (ZK) proofs and -equivocable commitments and we show that -equivocable commitments suffice to compile a class of -protocols which includes an RSA-based identification protocol, a proof of knowledge of -th root, to straight-line simulatable structured-instance ZK. In Section 5 we show homomorphic -equivocable commitments secure under RSA. By the results from Section 4 this implies an aggragatable structured-instance ZK proof of knowledge of -th root, which leads to an IBMS scheme construction, described in Section 6, and an IBAS scheme sketched in Section 7.

Technical Overview

Our IBAS/IBMS scheme is a multi-prover version of Guillou-Quisquater signature [13]. The ID-based version of GQ signature is a non-interactive zero- knowledge (NIZK) proof of knowledge (PK) of -th root modulo (in ROM). Let be an element in and let be the -th root of , a private key corresponding to identity ID. (Such private key can be computed the PKG who knows the factorization of .) To sign message , the signer with identity follows the ROM-based NIZK PK of -th root of : It computes the first proof message for random in , gets challenge by querying to a hash function (modeled as random oracle), and computes response to this challenge as . The signature is verified by checking if for . Due to homomorphic property of exponentiation one might hope to obtain an IBAS/IBMS scheme by aggregating such ROM-based NIZK PK’s of -th root made by several cosigners. For instance, consider the two-round protocol built along the lines of the DL-based multisignature scheme of [14]: In the first round each player broadcasts its first message . All players obtain a common challenge by querying the hash function on input including and the message being signed. Finally each player broadcasts its response to this challenge. The multi-signature is where . Note that if for each then satisfies the verification equation where . We believe that an adaptation of the security proof of [14] would show security of this scheme, but the resulting security argument would have several limitations:

  • (1) The reduction would be only from expected-time hardness of RSA problem;
  • (2) It would encounter substantial se- curity degradation due to extensive use of rewindings;
  • (3) It would therefore not extend to concurrent executions of multiple instances of this scheme.

To explain how we overcome these limitations we need to first explain why they appear in the above draft scheme. The simulator for the NIZK PK of -th root picks a random challenge and a random in , computes prover’s first message as and defines the hash of as because it controls the hash function . Note that since the Adversary has no information about , there is only a negligible chance that it queries on the same before the simulator attempts to define its value as , and hence the simulator passes with overwhelming probability. The fundamental difference between this simulation and the simulation for aggregated proof in the draft scheme above is that in the aggregated proof corrupt cosigners can choose their contributions on the basis of ’s broadcasted by the honest cosigners. Consequently, the simulator can only guess the resulting value with probability where is the number of hash queries the Adversary makes. This gives rise to a simulation procedure which rewinds the Adversary expected times in each signature instance, which causes all the limitations listed above: reduction to expected-time hardness, loose security reduction, and no argument for security of concurrent protocol instances. Bellare and Neven [1] showed how to overcome all these issues in the ROM model by adding an extra communication round in which each player first commits to its contribution by broadcasting a hash . By controlling the hash function the simulator can learn the ’s committed by the Adversary and then decide on the's published on behalf of the honest players. This way the simulator passes without rewinding with overwhelming probability, similarly to the NIZK simulation sketched above. The main technical challenge we handle in this work is how to achieve such straight-line simulation without introducing such extra communication round, i.e. with only two rounds of interaction. Our technique is a variant of Damgard’s HVZK-to-ZK compilation [15] which constructs a straight-line simulatable zero-knowledge proof from any -protocol using an equivocable commitment scheme, but we introduce an interesting twist: In Damgard’s scheme a signer commits to its value using an equivocable commitment scheme, and the simulator, on any challenge can open this commitments to the value needed for the proof to verify (where i response zi is chosen at random, to match the response distribution in the real proof). However, to create an IBMS/IBAS scheme by aggregating such proofs we need this commitment scheme to be multiplicatively homomorphic, and to the best of our knowledge no efficient commitment scheme is both equivoca- ble and multiplicatively homomorphic. Instead, we show a commitment scheme which is multiplicatively homomorphic over and satisfies a restricted form of equivocability which we call -equivocability, and which suffices for straight- line simulation of -protocol compiled as above. For example, -equivocable commitment for relation allows for equivocation of commitments to messages of the form zey-c for any and , and this is exactly the form of message a which the simulator needs in the above proof. The idea to use commitments with similarly restricted equivocability appeared before in [6], where it was used to construct a straight-line simulatable and aggregatable proof of DL knowledge, and a DL-based multi-signature scheme. However, the equivocability notion (and the construction) of [6] gives rise to only single-instance zero-knowledge proofs. Intuitively, this suffices for security of multi-signatures (as opposed to identity-based multi-signatures) because in multi-signatures the Adversary w.l.o.g. corrupts all players except of one, so the simulator needs to embed its challenge problem in just one public key, and needs to simulate multi-signature protocol on behalf of only that one player. Using this form of equivocation in security argument for identity-based schemes would introduce security degradation by factor of , the number of hash function queries, because the simulator would have to guess the single identity into which to embed its challenge. Here we define a more general notion of -equivocability which allows for straight-line simulatable “structured instance” zero-knowledge proofs in the CRS model: In structured-instance zero-knowledge proofs, formalized in this paper, the simulator can simulate on any statement in a class of related instances, in contrast to a single statement in single-instance ZK and any instance in (standard) multi-instance ZK. The class of instances which is particularly useful in showing a security reduction for an IBMS/IBAS scheme based on -protocol for proving knowledge of preimage of function are instances of the form where is the simulator’s challenge. In this way the simulator can embed its challenge into any number of identities, picking random for each identity, and yet straight-line simulate the proofs performed on behalf of all these entities in parallel. Thus our main technical contribution is two-fold: First, we formalize the notion of -equivocability and apply it to a compilation from -protocols to straight-line simulatable structured-instance ZKPK (Section 4). Secondly, we construct a multiplicatively homomorphic and -equivocable commitment scheme based on the RSA problem (Section 5). Together, these two parts immediately imply the IBMS and IBAS schemes we present in this paper (Section 6 and Section 7).

Identity-Based Multi-/Aggregate Signature Schemes

We define the notion of identity-based multisignature scheme (IBMS) building on the definitions given by [14],[5],[7], [1]. (Due to lack of space, we relegate the extension of our definitions to IBAS schemes to the full version of the paper [10]). Our notion is more flexible than that of [BN07,MOR01,BN06] because we do not require the set of participants’ identities as input to the multi-/aggregate signature protocol. The participating players must be aware of each other in the protocol execution, but this is needed only to ensure proper communication, and the participant identities are not required as inputs to the cryptographic protocol. The schemes secure in this setting provide flexibility to applications of multi-/aggregate signatures because sometimes signers might care only about the message they are signing and not about the identities of the cosigners. Otherwise the list of cosigners can always be attached to the message being signed.

Syntax of an IBAS Scheme . We define an identity-based multisignature as IBMS = (Setup,KeyDer,MSign,Vrfy) where Setup, KeyDer and Vrfy are probabilistic poly-time algorithms, and MSign is a distributed protocol executed by a set of parties

  • , run by a trusted party, on input the security parameter , generates master public key and corresponding master secret key .
  • , run by a trusted party, on input master secret key and an identity provides a secret key to the user with identity .
  • MSign is a multisignature protocol run by a group of players who intend to sign the same message . Player with identity executes this protocol on public inputsand message and private inputwhich is his own secret key. The local output of the protocol for every participant is a multisignature denoted .
  • verifies whether is a valid multisignature on message on behalf of the set of the identities .

In the random oracle model (ROM), KeyDer, MSign and Vrfy procedures additionally have access to a random oracle , where depends on the scheme. This set of procedures must satisfy the following completeness properties: For any integer , any message , and any output by , if for , one obtains and correctly follows MSign on input using secret keys, then assuming all messages are delivered between players, each player outputs the same string which satisfies .

Security Notion of an IBMS Scheme. We model the security as existential unforgeability under an adaptive chosen message and adaptive chosen identity attack: The Adversary participates in a game in which it issues a number of key derivation and signature queries. In a key derivation query, the Adversary corrupts a player by submitting its identity to the key derivation oracle and receiving its secret key . In a signature query the Adversary specifies the message and the identity that it wants to interact with; and the signing oracle performs MSign protocol on message on behalf of . The Adversary wins the game if it eventually outputs a message , a multisignature and a set of identities and there exists an identity , the Adversary never queried the key derivation oracle on and never queried the signing oracle on . More formally we define the Adversarial Advantage of against IBMS = (Setup,KeyDer,MSign,Vrfy) as a probability that experiment described in Figure 2 outputs 1 i.e.

where the probability goes over the random coins of the Adversary and all the randomness used in the experiment. We call an IBMS scheme - secure if for every Adversary that runs in time at most ,makes at most key derivation queries and at most signature queries, and produces a forgery on behalf of at most parties. In the random oracle model we extend this notion to -security, where is additionally restricted to at most hash queries and the probability in the experiment goes also over random choice of a hash function.

Experiment  :
  • Run , and handle ’s key derivation and signature queries as follows:
  • On a key derivation query on identity , add to CIdLst, run KeyDer on input and return to .
  • On a signing query on pair , add to MIdLst, run MSign protocol on behalf of identity on message forwarding messages to and from .
  • When halts, parse its output as .
  • If
then return 1, otherwise return 0 } Fig. 2. Chosen Message Attack against an Identity-Based Multisignature Scheme

-Equivocable Commitments and Structured-Instance Zero-KnowledgeΣ {\displaystyle \Sigma } -Equivocable Commitments and Structured-Instance Zero-Knowledge

Homomorphic -Protocols: -protocol, a notion introduced by Cramer, Damgard and Schoenmakers [16], is a three-move proof system with special honest-verifier zero-knowledge (HVZK) and strong soundness properties. Let be a relation whose membership can be verified in polynomial time. We consider a special case where and are algebraic groups (for notational simplicity we use multiplicative notation for both), and where is a homomorphic one-way function. We consider a proof of knowledge system for relation which we call homomorphic -protocol (for ): The prover, on input sends where . The verifier, on input , creates a challenge as a random -bit string, and the prover responds with . The verifier accepts if . This is a form of several - protocols for known homomorphic one-way functions, e.g. Guillou-Quisquater identification scheme [13] for a power function and Schnorr’s scheme [17] for exponentiation . The special HVZK property of a -protocol says that there exists an efficient simulator which on input computes pair for any with the distribution matching that of the prover. The special strong soundness says that there exists an efficient extractor which computes witness for any from any pair of accepting conversations and .

Structured-Instance Zero-Knowledge. Multi-instance zero-knowledge (ZK) (a.k.a. multi-theorem ZK) in common reference string (CRS) model requires a two-phase probabilistic poly-time simulator

  • (1) in the first phase, given public parameters, the simulator outputs the CRS string together with some trapdoor information;
  • (2) In the second phase, given a statement and the trapdoor, simulator outputs the simulated proof for that statement.

In the single-instance ZK, the simulator knows the statement beforehand and can set the CRS string as a function of this particular statement. Structured instance zero-knowledge proof for relation introduced above is an intermediary notion: The simulator is given a “core statement” before it sets the CRS string, and then it can simulate the proof for statement for any . Here is the formal definition:

Definition 1. Let and be algebraic groups and be a surjective homomorphic one-way function, all indexed by a public parameter par. Let be a proof system in CRS model for relation where is an algorithm that outputs the common reference string. We say that is straight-line -structured-instance zero-knowledge if there exist efficient algorithms on input par and a core instance , outputs the CRS string and trapdoor , while on input and a “witness-shift” outputs a simulated proof for instance , and for all the following two properties hold:

  • 1. Statistical difference between the following two distributions is at most
  • 2. verifier and , the following two distributions are identical:

Commitment Schemes: A commitment scheme in the CRS model consists of probabilistic poly-time algorithms CSetup, CKG, Com and Open. CSetup on input the security parameter , generates public parameters cpar, which also determine the commitment message space . CKG(cpar) generates the commitment key , generates the commitment and the decommitment on message , and finally determines if is a valid decommitment of commitment to message . A commitment scheme must satisfy that if , , and , then . Below we define statistical hiding and computational binding properties of commitments because these will be variants of these notions which our scheme satisfies.

-Hiding: For all and , there is less than statistical difference between the distribution of ’s output by and the distribution of ’s output by . A commitment scheme is perfectly hiding if . -Binding: For any algorithm running in time and any cpar output by , the probability of and is less than is outputted by on input and and probability is over the coins of CKG and . Notation: In this paper we only deal with the commitment schemes in which the commitment is a deterministic function of the message and the decommitment. Therefore we assume there exist a decommitment space denoted as and the Com procedure picks decommitment and computes the commitment as the deterministic function of and .

-Equivocable Commitments: A commitment scheme is equivocable if there exists an efficient simulator that generates commitment key , indistinguishable from real key, together with a trapdoor . The trapdoor allows simulator to create fake commitments indistinguishable from real ones, and later decommit them to any message. Using equivocable commitments, one can compile a -protocol to a multi-instance ZK proof system with straight-line simulation [15]. Here we define a rather restrictive form of equivocability called -equivocability and we show that it is sufficient for compiling -protocols into structured-instance ZK proofs with straight-line simulation. It turns out that structured-instance ZK is sufficient for our application of ZK proofs to multi-/aggregate signatures and multi-instance ZK is not required. Moreover the straight-line simulatability of this system allows us to have multi-/aggregate schemes with concurrency, better exact security and with improved round complexity.

Definition 2. Let and be algebraic groups and let be a homomorphic one-way function, all indexed by a commitment parameter cpar. We call a commitment scheme equivocable for if there exist probabilistic polytime algorithms tdCKG, tdCom, and RstEquiv, where and for any cpar output by CSetup and any the following properties hold:

  • 1. There is at most statistical difference between the distribution of ’s output by CKG(cpar) and ’s output by .
  • 2. For all is output by is output by then is distributed as random decommitment in and .

Intuitively definition 2 says that the equivocation procedure, given , can open a fake commitment to a message of the form for some . This is useful in straight-line simulation of a proof of knowledge for relation .For example, let where . Consider the HVZK simulator of the -protocol for proving knowledge of -th root: This simulator picks random and and computes prover’s first message . Below we show that Damgard’s compilation [15] (see Figure 3 below) transforms such -protocol to structured-instance zero-knowledge using only such -equivocable commitments, because the simu- lator can output a fake commitment and then open it to what the -protocol simulator would output as the prover’s first message i.e. . Definition 2 implies that a fake commitment can be opened to a = ze( \dot{y}\deltae)-c for any \delta and c. Hence the structured-instance zero-knowledge simulator can use this property to simulate a proof for any instance y = where is set before the simulator creates the CRS string (see theorem 1).

Homomorphic Commitments: We call a commitment scheme multiplicatively homomorphic if there are efficiently computable operations if and then for . Accordingly, a commitment scheme is -restricted multiplicatively homomorphic if the homomorphic operation can be applied on only commitment-decommitment pairs generated by Com procedure. Our construction is -restricted multiplicatively homomorphic.

Common Reference String:

Commitment Key of -Equivocable Commitment Scheme

Prover P(x) s.t. x \in X, f(x) = y k\xleftarrow{r} X,a\leftarrowf(k) (C, D) \leftarrow ComK (a) oo z\leftarrowkxc C c z ,D // Verifier V (y) s.t. y \in Y c \xleftarrow{r} { 0 , 1 } k acciffOpenK(C,D,f(z)y-c)=1 // Fig. 3. Straight-line simulatable structured-instance ZKPK of pre-image of f

Structured-Instance Zero-Knowledge from Homomorphic -Protocol: Figure 3 shows a construction of a straight-line simulatable structured-instance zero-knowledge proof of knowledge system, in the CRS model, from homomorphic -protocol and -equivocable commitment. This is an identical construction to Damgard’s compiler from -protocol to ZKPK proof [15]. Below we show that using only -equivocable commitments the same compilation produces structured-instance zero-knowledge proof given homomorphic -protocol. As in [15] the resulting protocol is an argument of knowledge, subject to the binding property of the commitment scheme.

Theorem 1. Let and be algebraic groups, a homomorphic one-way function, a -equivocable commitment over message space . Then the protocol in figure 3 is a straight-line simulatable structured-instance zero-knowledge proof of knowledge of pre-image of in the CRS model.

Proof. The straight-line simulator , for structured-instance zero-knowledge proof acts as follows: In the first phase, given cpar and to obtain and sets the common reference string as . In the second phase, given td and witness shift to obtain the fake commitment and state and sends to the verifier. Upon receiving the challenge from the verifier, to get the response and fake commitment . According to -equivocability property (definition 2) it immediately follows that satisfies conditions in definition 4.

Aggregatable Zero-Knowledge Proof of Knowledge of -th RootAggregatable Zero-Knowledge Proof of Knowledge of e {\displaystyle e} -th Root

Safe RSA Assumption: Since our construction relies on two related instances of RSA cryptosystems which share same RSA modulus but use two different public exponents and , it is convenient for us to use the following notation for RSA instance generation: We call an algorithm a safe RSA generator if on input security parameter and a prime generates a pair and and are all prime numbers and and . For later use we define . The Advantage of an algorithm in breaking the RSA(e) problem is defined as

We say algorithm , -breaks the problem on security parameter if runs in time at most and . We say that the problem is -hard (for security parameter ) if no algorithm -breaks it. We note that the requirement that is just a lower-bound we introduce to enable any party to choose “secondary” public exponent and where is a maximum number of participants in any single instance of the multi-signature scheme.

RSA-based Multiplicatively Homomorphic -Equivocable Commitment

Let and be two prime numbers and for some integer and let be output by . This assures that both and are safe RSA instances. We describe an efficient commitment scheme, which is computationally binding under the assumption, has restricted multiplicatively homomorphic property on message space , and is -equivocable for . Curiously, this commitment is statistically hiding only for the messages picked from a specific subset of the message space, but in our application of this commitment scheme to straight line simulatable ZKPK of -th root, standard hiding property is not necessary, and -equivocability property for the above function is sufficient.

: Pick prime numbers and and Run KG_{sRSA} on input to obtain . Set .

: Pick . Note that it is easy to sample random elements in by squaring a random element in .

:Pick and set and . (Hence the decommitment space is .)

: Accept iff and .

: Pick \gamma \xleftarrow{r} [n] </math>, and set , and .

 :Picks and return where and .

: Compute and (over integers) and return where .

Statistical Hiding: This commitment scheme is -hiding for the messages picked from where and is determined by the commitment key. To argue this note that the maximum statistical difference between the distributions of the commitments to happens when they correspond to and respectively. This way the distributions of the commitments would be and respectively which has a statistical difference equal to .

Computational Binding: This commitment scheme is -binding if RSA() problem is -hard. Indeed given the challenge , one can use the attacker on binding to find the -th root of . The reduction runs the binding attacker to obtain and . Since it follows that . Now since , then and using extended Euclidian algorithm one can compute . Thus and -th root of can be computed as .

l-Restricted Multiplicative Homomorphism: This commitment scheme is multiplicatively homomorphic on in the sense that up to messages can be combined: If are commitment-decommitment pairs for messages each computed by the commitment procedure, then (over integers) is a valid decommitment for commitment for message . Note that by setting , homomorphism can be used on any feasible set of messages.

-Equivocability: This commitment scheme is -equivocable for function (family) . First note that for every output by CSetup and every is a generator of , the distributions of keys generated by and are at most apart, because CKG chooses the key as a random element in while tdCKG picks for and chosen at random in . Moreover the statistical difference between and is equal to . Secondly, if is a generator of then for every , every and every , according to the code of tdCom and RstEquiv , satisfy and , therefore for we have , and hence . Moreover the distribution of the decommitments in the equivocation process i.e. is identical to uniform distribution over .

Corollary 1. Consider prime number and let be a safe RSA modulus output by on input and security parameter . Consider compilation shown in figure 3 and let the function (family) be and let the compilation be instantiated with the commitment scheme described in this section. Then from theorem 1, it immediately follows that the resulting scheme is a straight-line structured-instance zero-knowledge proof of knowledge of -th root.

Identity-Based Multisignature Scheme Based on RSA

We describe our IBMS scheme based on the RSA assumption. The scheme takes two communication rounds, requires two double-exponentiations per party for signing and one triple-exponentiation for verification. The scheme is based on the GQ ID-based identification protocol [13], which is the -protocol for proving knowledge of -th root. Each party simply executes the aggregatable zero-knowledge proof of -th root of its (hashed) identity string, using the straight-line simulatable aggregatable ZKPK of -th root described in Section 5. Figure 4 contains the Setup, KeyDer, MSign and Vrfy algorithms for this IBMS scheme.

Note on multi-signature length: In Figure 4 the final multi-signature is a tuple where and is a commitment-decommitment pair on message . However this commitment can be computed as a deterministic function of the committed message and the decommitment (see Section 4). Therefore can be computed given , and hence one can use as the final multi-signature, which reduces the multi-signature size to .

Theorem 2. If and problems are -hard, and the IBMS scheme in figure 4 is instantiated with commitment scheme in section 5, which is -binding and -equivocable for function , then the resulting IBMS scheme is -secure in random oracle model where


and is the time of one exponentiation in .

 1. Setup(1k): Let l be the maximum number of players in the IBMS scheme. Pick prime numbers eande' s.t.2k \leqslante,e' \leqslant22k and2k+1l < e < e'/l.RunKG_{sRSA} oninput(k,e)to obtain (n, d). Note that gcd(e', φ(n)) = 1 because φ(n) = 4p'q' where p', q' > 22k. Run CKG(n, e, e') to obtain the commitment key K . Set= (n, e, e', K ) and msk = d. Assume H1 : {0,1}* → QRn and H2 : QRn \times{0,1}* \timesQRn → {0,1}k are random oracles that every other algorithm in the protocol has access to them. 2. KeyDer(msk,Id): The PKG computes xId \leftarrow (H1(Id))2d(mod n), sets the private key of the user with identity as\leftarrow xId and sends it back to him via a secure and authenticated channel. 3. MSign: Let P be the set of players participating in the protocol. Each player determines P after the first step of MSign. Player with identity Idi on input (mpk, m,), performs the following steps: 3.1 Pick ki \xleftarrow{r} QRn, \leftarrow kie; Set (Ci, Di) \xleftarrow{r} ComK (ai) and broadcast (Idi, Ci); N 3.2 Upon receiving (Idj,Cj) ∀Pj\in P, Set IdSet \leftarrow {Idj}Pj\inP and \leftarrow Pj\inP Cj; Set \leftarrow H2(C, IdSet, m); Compute zi \leftarrow ki(xIdi )c and broadcast (zi, Di); 3.3 Output multisignature = (z, C, D), where z = zj and D = Dj . Pj \inP Pj \inP 4. Vrfy(mpk,m,IdSet,\sigma): Parse as (z,C,D) andas (n,e,e',K); Set \leftarrow H2(C,IdSet,m); y \leftarrow Q H1(Idi)2; If Open (C, D, zey-c) = 1 then accept otherwise reject. Idi\inIdSet K QL Fig. 4. Identity-based multisignature scheme based on RSA

Proof. Let be a commitment scheme for public parameters and the message space equal to . Assume is -restricted multiplicatively homomorphic, -binding and -equivocable for . Given a -forger , consider two simulators and that simulate the role of the honest player as in the experiment interacting with the forger . takes as an input a set where are in and runs Setup procedure to obtain and follows the real protocol i.e. answers to forger’s key derivation queries and signing queries using procedures KeyDer and MSign respectively. Additionally, answers the forger’s hash queries and performs an extra finalization process by following the procedures SimHash and Finalize in Figure 5. The simulator , on the other hand, takes as an input an RSA challenge and a set where 's are in and follows the Init, SimKeyDer, SimMSign, SimHash and Finalize procedures detailed in Figure 5 to perform the initialization, answering to key derivation, signing and hash queries and finalization processes,respectively. Intuitively, the simulator uses Coron’s technique [18] to embed the RSA challenge in the hashes of the ID’s of the players with some biased probability hoping that the forgery be based upon the of the player for which the RSA challenge is indeed embed-ded. This way passes the signing queries on behalf of identity just like real protocol using the procedure MSign if the RSA challenge is not embedded in the hash of and otherwise uses the straight-line structured-instance zero-knowledge simulator for proof of knowledge of -th root (see corollary 1) to simulate the signature protocol on behalf of the identity . Both and , after receiving a valid forgery from , perform a finalization phase in which the forged multisignature is returned together with the index of the hash responses upon which they are based. Namely both and return and there exists at least one uncorrupted is never queried for signing. The simulators and set up empty tables and to simulate the hash functions and respectively and use the set to answer to the hash queries to which enables the utilization of forking lemma (as formulated e.g. in [5][6]).

Now for let’s lower-bound the probability that generates a “useful” output i.e. an output other than . This happens when does not abort in any of the key derivation queries or finalization procedure. Therefore . This function reaches its maximum when . Substituting this value of yields:


For , consider -the forking algorithm associated with . The success event of denoted by is that the algorithm outputs two tuples and where j is the index of the hash responses upon which the forged multisignature is based. Since the random coins of the algorithm and the hash responses of the algorithm previous to query are the same in the first and second executions, all the computations and communications and in particular the queries submitted to the hash function before query must be the same, too. Thus the occurrence of implies , and . Note that also implies . This is because and the values for for all is fixed before the fork. The success event can be partitioned into two cases (1) event in which happens and (2) event E_2^{\mathcal{B}_I} in which happens an . Obviously and hence . On the other hand, according to the forking lemma, can be lower bounded by , the success probability of the simulator :

If ’s are uniformly distributed in then ’s view in interaction with is identical to the real execution of the protocol. As for , since is -equivocable, by straight-line structured-instance simulatability of ZKPK of e-th root, firstly the distributions of the commitment keys in the simulation and in the real protocol are at most apart and secondly the distribution of the tuples generated in each signature instance in the interaction between and is identical the distributions of the same variables in the real execution. Thus, since our simulation is straight line, total distance between ’s view in interaction with and in real execution is at most . This implies in particular that and . So and . Thus equation (2) becomes:

The actual reduction algorithm , runs both . If happens, then . Substituting where is the number of players for whom the reduction has embedded the challenge (see figure 5) yields

Init(n, e, \dot{y}): Pick prime e' where el \leqslant e' \leqslant 22k and run tdCKG((n,e,e'), \dot{y}) to get (td,K), setas (n,e,e',K) and run F on input mpk; SimKeyDer(I d): Query H1 on and look up H1[Id] to get (b,\delta,y). If b = 0, return \delta other- wise abort the simulation with failure outputting (0, λ). SimMSign(m, I d): Query H1 on and look up H1[Id] to get (b,\delta,y). If (b = 0) then run MSign(m,Id); otherwise: -(C ̃, st)\leftarrowtdComK (td); Send (Id,C ̃) to F; -Upon receiving (Idj,Cj) for Pj \in P, N SimHash: H1 (I d): If I d is not previously queried, pick \delta uniformly at random from QRn, tossabiasedcoinbsothatb=0with probability \rho and b = 1 with probability 1-\rho.Ifb=0,sety\leftarrow\deltae otherwise set y \leftarrow \dot{y}\deltae. Store (b, \delta, y) to H1[Id]. Return H1 [I d]. H2(C, IdSet, m): If (C, IdSet, m) is an ith distinct query of F to H2, then query H1(Idi) for every Idi \in IdSet and set H2[(C, IdSet, m)] \leftarrow ci; Return H2[(C, IdSet, m)]; Finalize: Upon receiving a valid forgery (m, IdSet, \sigma) from F, parse as (z,C,D)andqueryH2 on(C,IdSet,m). Let IdSet0 = {Idi|bi = 0} and IdSet1 = {Idi|bi = 1}. If IdSet1 = \varnothing then abort the simulation with fail- IdSet \leftarrow {Idj}Pj\inP; \leftarrow \leftarrow H2(C, IdSet, m); Pj\inP Cj; (D ̃ , z ̃) \leftarrow RstEquivK (td, st, c, \delta); ure outputting (0, λ). Otherwise set Q Send (z ̃,D ̃) to F; -z\leftarrowQ zj; D\leftarrowL Idi\inIdSet(xi), n1 = |IdSet1| and Pj \inP Pj \inP Output = (z, C, D); Dj; x \leftarrow return (j, (x, n1, m, IdSet, \sigma)) where j is the index of in the hash table H2. Fig. 5. The procedures SimHash and Finalize that and use and the procedures Init, SimKeyDer, and SimMSign that uses.

Now since , therefore and one can easily compute the -th root of using the extended Euclidean algorithm.

If happens, then immediately translates it into an attack against binding property of commitment scheme by returning . To see this note that as argued before, and since is occurred, thus and due to validity of the forgeries we have . Moreover the commitment key is outputted by CKG in the execution of . Thus and and hence equation (3) becomes

The running time of the reduction algorithm is twice the maximum of running time of the algorithms and . But the running time of and is dominated by the running time of the forger plus the time spent by the simulators to answer the hash, signing and key derivation queries. Thus where is the time required for exponentiation in . On the other hand since either answers the RSA challenge or returns an attack against the binding property of the commitment , it must be true that . Thus:

Identity-Based Aggregate Signature Scheme

The construction in the previous section can be easily modified to obtain a 2-round identity based aggregate signature (IBAS) scheme provably secure under RSA assumption. For this purpose, one needs to modify the verification algorithm to support the case where different challenges are acquired in step 4.2 of the protocol due to querying on different messages. More precisely, the resulting IBAS scheme is exactly the same as the scheme described in figure 4 except that its verification algorithm would be as follows: Parse as and as ; Compute where is output of on input and check whether . The security proof for this IBAS scheme is similar to the proof given in the previous section. Namely the reduction runs two simulators; in one simulator the challenge is embedded in the commitment key and in the other it is embedded in hashes of IDs. Therefore with high probability, if the forgery happens the reduc- tion translates it either to either attack the binding property of the commitment scheme (event in the previous proof) or to find -th root of the challenge (event in the previous proof). The security proof of the IBAS scheme is similar to the security proof of IBMS scheme described in the previous section. The most important difference is that in order to find the-th root of the challenge we have the following equation instead of equation 4 in the previous proof:

Therefore to be able to compute -th root of , we need . In particular, the reduction succeeds as long as , i.e. unless the challenges in the two branches of the forking algorithm sum up to the same value mod , which happens with only negligible probability.


  1. 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Bellare, M., Neven, G.: Identity-based multi-signatures from rsa. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 145–162. Springer, Heidelberg (2006)
  2. Barr, K., Asanovic, K.: Energy aware lossless data compression. In:MobiSys (2003)
  3. Shamir, A.: Identity-based cryptosystems and signature schemes. In:Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
  4. 4.0 4.1 Galindo, D., Herranz, J., Kiltz, E.: On the generic construction of identitybased signatures with additional properties. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 178–193. Springer, Heidelberg (2006)
  5. 5.0 5.1 5.2 Mihir Bellare and Gregory Neven. Mult-signatures in the plain public- key model and a general forking lemma. In Conference on Computer and Communications Security, CCS’06, pages 390– 399, 2006.
  6. 6.0 6.1 6.2 6.3 Ali Bagherzandi, Jung Hee Cheon, and Stanislaw Jarecki. Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In ACM Conference on Computer and Communications Security, pages 449–458, 2008.
  7. 7.0 7.1 7.2 7.3 7.4 7.5 7.6 Craig Gentry and Zulfikar Ramzan. Identity-based aggregate signatures. In Public Key Cryptography, pages 257–273, 2006.
  8. 8.0 8.1 8.2 Alexandra Boldyreva, Craig Gentry, Adam O’Neill, and Dae Hyun Yum. Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In Cryptology ePrint Archive, Report 2007/438, Revised 21/02/2010, 2010.
  9. Jihye Kim and Gene Tsudik. Srdp: Securing route discovery in dsr. In MobiQuitous, pages 247–260, 2005.
  10. 10.0 10.1 10.2 Ali Bagherzandi and Stanislaw Jarecki. Identity-based aggregate and multi- signature schemes based on RSA. (full version), 2010.
  11. Gregory Neven. E
  12. Javier Herranz. Deterministic identity-based signatures for partial aggrega- tion. Comput. J., 49(3):322–330, 2006.
  13. 13.0 13.1 13.2 Louis C. Guillou and Jean-Jacques Quisquater. A ”paradoxical” indentity- based signature scheme resulting from zero-knowledge. In CRYPTO, pages 216–231, 1988.
  14. 14.0 14.1 14.2 Silvio Micali, Kazuo Ohta, and Leonid Reyzin. Accountable-subgroup mul- tisignatures. In ACM Conference on Computer and Communications Secu- rity, CCS’01, October 2001.
  15. 15.0 15.1 15.2 15.3 15.4 Ivan Damg ̊ard. E
  16. Ronald Cramer, Ivan Damg ̊ard, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In CRYPTO, pages 174–187, 1994.
  17. Claus-Peter Schnorr. E
  18. Jean-S ́ebastienCoron.Ontheexactsecurityoffulldomainhash.In CRYPTO, pages 229–235, 2000.

  1. Department of Computer Science, University of California, Irvine
  2. Department of Computer Science, University of California, Irvine