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

 IBMS RSA Authors Ali Bagherzandi[@: 1], and Stanislaw Jarecki[@: 2] Published 2010 г. Licence ? Web site ? Status ? Download оригинал

Abstract.

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.

## Introduction

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 ${\displaystyle n~\,\!}$ signatures from ${\displaystyle O(n)~\,\!}$ to ${\displaystyle O(1)~\,\!}$, but the verifiers still need the public keys of ${\displaystyle n~\,\!}$ 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 ${\displaystyle n~\,\!}$ 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 ${\displaystyle O(1)~\,\!}$ 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 ${\displaystyle O(1)~\,\!}$ 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 ${\displaystyle {\text{Underlying Problem}}^{(1)}}$ Restrictions ${\displaystyle ^{(2)}}$ Number of Rounds Verification Time ${\displaystyle ^{(3)}}$ Signing Time ${\displaystyle ^{(3)}}$ Signature Length ${\displaystyle ^{(4)}}$ [7]-IBAS GapDH Stateful 1 3P+nM 5M ${\displaystyle 2|G_{1}|+k}$ [8] GapDH Sequential 1 6P+nM 7M ${\displaystyle 3|G|}$ OUR IBAS RSA - 2 nE 2E ${\displaystyle |Z_{n}^{*}|+2k+\log l\,}$ [7]-IBMS GapDH - 1 3P 3M ${\displaystyle 2|G_{1}|}$ [1] RSA - 3 1E 2E ${\displaystyle |Z_{n}^{*}|+k}$ OUR IBMS RSA - 2 1E 2E ${\displaystyle |Z_{n}^{*}|+2k+\log l\,}$

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, ${\displaystyle P~}$ is the cost of one pairing operation, ${\displaystyle M}$ is the cost of scalar multiplication on an elliptic curve, and ${\displaystyle E~}$ is the cost of (multi-)exponentiation in ${\displaystyle Z_{n}^{*}~}$ (with about 80-bit exponents);
• (4) Signature length is measured in bits where ${\displaystyle k}$ is the security parameter, ${\displaystyle n~}$ is an RSA modulus, ${\displaystyle l~}$ is an upper bound on the number of players, ${\displaystyle ~G1}$ and ${\displaystyle ~G2}$ are two groups of elliptic curve points with an asymmetric bilinear map, ${\displaystyle ~G}$ is a group of elliptic curve points with a symmetric bilinear map, and ${\displaystyle ~|A|}$ stands for the bitsize of representation of elements in group ${\displaystyle ~A}$ . Typical values for these parameters are ${\displaystyle k=160}$ , ${\displaystyle ~|G_{1}|=160}$ , ${\displaystyle ~|G|=512}$, ${\displaystyle ~\log l=20}$, and ${\displaystyle ~|Z_{n}^{*}|=1024}$ or ${\displaystyle 2048}$.

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 ${\displaystyle ~\Sigma }$-equivocable commitments and we show that ${\displaystyle ~\Sigma }$-equivocable commitments suffice to compile a class of ${\displaystyle ~\Sigma }$-protocols which includes an RSA-based identification protocol, a proof of knowledge of ${\displaystyle ~e}$-th root, to straight-line simulatable structured-instance ZK. In Section 5 we show homomorphic ${\displaystyle ~\Sigma }$-equivocable commitments secure under RSA. By the results from Section 4 this implies an aggragatable structured-instance ZK proof of knowledge of ${\displaystyle ~e}$-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 ${\displaystyle e}$-th root modulo ${\displaystyle n}$(in ROM). Let ${\displaystyle {y=H(ID)}\,}$ be an element in ${\displaystyle Z_{n}^{*}}$and let ${\displaystyle {x}}$ be the ${\displaystyle e}$ -th root of ${\displaystyle y}$, a private key corresponding to identity ID. (Such private key can be computed the PKG who knows the factorization of ${\displaystyle n}$.) To sign message ${\displaystyle m}$, the signer with identity ${\displaystyle Id}$ follows the ROM-based NIZK PK of${\displaystyle e}$ -th root of ${\displaystyle y}$: It computes the first proof message ${\displaystyle a=k^{e}}$ for random ${\displaystyle k}$ in ${\displaystyle ~Z_{n}^{*}}$, gets challenge ${\displaystyle c}$ by querying ${\displaystyle (m,a)}$ to a hash function (modeled as random oracle), and computes response ${\displaystyle z}$ to this challenge as ${\displaystyle z=kx^{c}}$. The signature is ${\displaystyle (a,z)}$ verified by checking if ${\displaystyle z^{e}=ay^{c}}$ for ${\displaystyle c=H(m,a)}$. Due to homomorphic property of exponentiation one might hope to obtain an IBAS/IBMS scheme by aggregating such ROM-based NIZK PK’s of${\displaystyle e}$ -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 ${\displaystyle a_{i}}$. All players obtain a common challenge ${\displaystyle c}$ by querying the hash function on input including ${\displaystyle a=a_{i}}$ and the message being signed. Finally each player broadcasts its response ${\displaystyle z_{i}}$ to this challenge. The multi-signature is ${\displaystyle (a,z)}$ where ${\displaystyle z=\prod {z_{i}}}$. Note that if ${\displaystyle z_{i}^{e}=a_{i}y_{i}^{c}}$ for each ${\displaystyle i}$ then ${\displaystyle (a,z)}$ satisfies the verification equation ${\displaystyle z^{e}=a(\prod {y_{i}})^{c}}$ where ${\displaystyle y_{i}=H(ID_{i})}$. 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 ${\displaystyle e}$ -th root picks a random challenge ${\displaystyle c}$ and a random ${\displaystyle z}$ in ${\displaystyle ~Z_{n}^{*}}$, computes prover’s first message as ${\displaystyle a=z^{e}y^{-c}}$ and defines the hash of ${\displaystyle (a,m)}$ as ${\displaystyle c}$ because it controls the hash function ${\displaystyle H}$. Note that since the Adversary has no information about ${\displaystyle a}$, there is only a negligible chance that it queries ${\displaystyle H}$ on the same ${\displaystyle (a,m)}$ before the simulator attempts to define its value as ${\displaystyle c}$ , 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 ${\displaystyle a_{i}}$ on the basis of ${\displaystyle a_{i}}$’s broadcasted by the honest cosigners. Consequently, the simulator can only guess the resulting ${\displaystyle a}$ value with probability ${\displaystyle {\frac {1}{g_{h}}}}$ where ${\displaystyle q_{h}}$ is the number of hash queries the Adversary makes. This gives rise to a simulation procedure which rewinds the Adversary expected ${\displaystyle q_{h}}$ 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 ${\displaystyle a_{i}}$ contribution by broadcasting a hash ${\displaystyle H(a_{i})}$. By controlling the hash function ${\displaystyle H}$ the simulator can learn the ${\displaystyle a_{i}}$’s committed by the Adversary and then decide on the${\displaystyle a_{i}}$'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 ${\displaystyle ~\Sigma }$-protocol using an equivocable commitment scheme, but we introduce an interesting twist: In Damgard’s scheme a signer commits to its ${\displaystyle a_{i}}$ value using an equivocable commitment scheme, and the simulator, on any challenge ${\displaystyle c}$ can open this commitments to the value ${\displaystyle a_{i}=z_{i}^{e}y_{i}^{-c}}$ 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 ${\displaystyle ~Z_{n}^{*}}$and satisfies a restricted form of equivocability which we call ${\displaystyle ~\Sigma }$-equivocability, and which suffices for straight- line simulation of ${\displaystyle ~\Sigma }$-protocol compiled as above. For example, ${\displaystyle ~\Sigma }$-equivocable commitment for relation ${\displaystyle R=\{(x,y)|y=xe\}~\,\!}$ allows for equivocation of commitments to messages of the form zey-c for any ${\displaystyle c}$ and ${\displaystyle z}$, 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 ${\displaystyle q_{H}}$, 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 ${\displaystyle ~\Sigma }$-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 ${\displaystyle ~\Sigma }$-protocol for proving knowledge of preimage of function ${\displaystyle f(x)=x^{e}}$ are instances of the form ${\displaystyle y={\dot {y}}f(\delta )}$ where ${\displaystyle {\dot {y}}}$ is the simulator’s challenge. In this way the simulator can embed its challenge into any number of identities, picking random ${\displaystyle \delta }$ 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 ${\displaystyle ~\Sigma }$-equivocability and apply it to a compilation from ${\displaystyle ~\Sigma }$-protocols to straight-line simulatable structured-instance ZKPK (Section 4). Secondly, we construct a multiplicatively homomorphic and ${\displaystyle ~\Sigma }$-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 ${\displaystyle s.t.}$

• ${\displaystyle (mpk,msk)\leftarrow {\text{Setup}}(1^{k})}$, run by a trusted party, on input the security parameter ${\displaystyle k}$, generates master public key ${\displaystyle mpk}$ and corresponding master secret key ${\displaystyle msk}$.
• ${\displaystyle sk_{Id}\leftarrow {\text{KeyDer}}(msk,Id)}$, run by a trusted party, on input master secret key ${\displaystyle msk}$ and an identity ${\displaystyle Id\in {0,1}^{*}}$ provides a secret key ${\displaystyle sk_{Id}}$ to the user with identity ${\displaystyle Id}$.
• MSign is a multisignature protocol run by a group of players who intend to sign the same message ${\displaystyle m}$. Player with identity ${\displaystyle Id}$ executes this protocol on public inputs${\displaystyle mpk}$and message ${\displaystyle m}$ and private input${\displaystyle sk_{Id}}$which is his own secret key. The local output of the protocol for every participant is a multisignature denoted ${\displaystyle \sigma }$.
• ${\displaystyle {0,1}\leftarrow {\text{Vrfy}}(mpk,m,IdSet,\sigma )}$ verifies whether ${\displaystyle \sigma }$ is a valid multisignature on message ${\displaystyle m}$ on behalf of the set of the identities ${\displaystyle IdSet}$.

In the random oracle model (ROM), KeyDer, MSign and Vrfy procedures additionally have access to a random oracle ${\displaystyle H(\cdot ):\{0,1\}\rightarrow D}$, where ${\displaystyle D}$ depends on the scheme. This set of procedures must satisfy the following completeness properties: For any integer ${\displaystyle n}$, any message ${\displaystyle m}$ , and any ${\displaystyle (mpk,msk)}$ output by ${\displaystyle {\text{Setup}}(1^{k})}$, if for ${\displaystyle i=1..n}$, one obtains ${\displaystyle sk_{{Id}_{i}}\leftarrow {\text{KeyDer}}(msk,{Id}_{i})}$ and correctly follows MSign on input ${\displaystyle m}$ using secret keys${\displaystyle sk_{{Id}_{i}}}$, then assuming all messages are delivered between players, each player outputs the same string ${\displaystyle \sigma }$ which satisfies ${\displaystyle {\text{Vrfy}}(mpk,m,{{Id}_{1},...,{Id}_{n}},\sigma )=1}$.

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 ${\displaystyle Id}$ to the key derivation oracle and receiving its secret key ${\displaystyle sk_{Id}}$. In a signature query the Adversary specifies the message ${\displaystyle m}$ and the identity ${\displaystyle Id}$ that it wants to interact with; and the signing oracle performs MSign protocol on message ${\displaystyle m}$ on behalf of ${\displaystyle Id}$. The Adversary wins the game if it eventually outputs a message ${\displaystyle m}$, a multisignature ${\displaystyle \sigma }$ and a set of identities ${\displaystyle IdSets.t.{\text{Vrfy}}(mpk,m,IdSet,\sigma )=1}$ and there exists an identity ${\displaystyle Ids.t.}$, the Adversary never queried the key derivation oracle on ${\displaystyle Id}$ and never queried the signing oracle on ${\displaystyle (m,Id)}$. More formally we define the Adversarial Advantage of ${\displaystyle {\mathcal {A}}}$ against IBMS = (Setup,KeyDer,MSign,Vrfy) as a probability that experiment ${\displaystyle Exp_{IBMS}^{uu-cma}({\mathcal {A}})}$ described in Figure 2 outputs 1 i.e.

${\displaystyle Adv_{IBMS}^{uu-cma({\mathcal {A}})}={\text{Pr}}[Exp_{IBMS}^{uu-cma({\mathcal {A}})}=1]}$

where the probability goes over the random coins of the Adversary and all the randomness used in the experiment. We call an IBMS scheme ${\displaystyle (t,\epsilon ,n,q_{K},q_{S})}$- secure if ${\displaystyle Adv_{IBMS}^{uu-cma({\mathcal {A}})}\leqslant \epsilon }$ for every Adversary ${\displaystyle {\mathcal {A}}}$ that runs in time at most ${\displaystyle t}$,makes at most ${\displaystyle q_{K}}$ key derivation queries and at most ${\displaystyle q_{S}}$ signature queries, and produces a forgery on behalf of at most ${\displaystyle n}$ parties. In the random oracle model we extend this notion to ${\displaystyle (t,\epsilon ,n,q_{K},q_{S},q_{H})}$-security, where ${\displaystyle {\mathcal {A}}}$ is additionally restricted to at most ${\displaystyle q_{H}}$ hash queries and the probability in the experiment ${\displaystyle {\text{Exp}}^{uu-cma({\mathcal {A}})}}$ goes also over random choice of a hash function.￼

Experiment ${\displaystyle Exp_{IBMS}^{uu-cma({\mathcal {A}})}}$ :
• ${\displaystyle (mpk,msk)\leftarrow {\text{Setup}}(1^{k});{\text{MIdLst}}\leftarrow \varnothing ;{\text{CIdLst}}\leftarrow \varnothing ;}$
• Run ${\displaystyle {\mathcal {A}}(mpk)}$, and handle ${\displaystyle {\mathcal {A}}}$’s key derivation and signature queries as follows:
• On a key derivation query on identity ${\displaystyle Id}$, add ${\displaystyle Id}$ to CIdLst, run KeyDer on input ${\displaystyle (msk,Id)}$ and return ${\displaystyle sk_{Id}}$ to ${\displaystyle {\mathcal {A}}}$.
• On a signing query on pair ${\displaystyle (m,Id)}$, add ${\displaystyle (m,Id)}$ to MIdLst, run MSign protocol on behalf of identity ${\displaystyle Id}$ on message ${\displaystyle m}$ forwarding messages to and from ${\displaystyle {\mathcal {A}}}$.
• When ${\displaystyle {\mathcal {A}}}$ halts, parse its output as ${\displaystyle (m,IdSet,\sigma )}$.
• If ${\displaystyle ({\text{Vrfy}}(mpk,m,{\text{IdSet}},\sigma )=1)\land (\exists Id\in {\text{IdSet}}s.t.(Id\notin CIdLst)\land ((m,Id)\notin MIdLst))}$
then return 1, otherwise return 0 } Fig. 2. Chosen Message Attack against an Identity-Based Multisignature Scheme

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

Homomorphic ${\displaystyle ~\Sigma }$-Protocols: ${\displaystyle ~\Sigma }$-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 ${\displaystyle R=\{(x,y)\}}$ be a relation whose membership can be verified in polynomial time. We consider a special case where ${\displaystyle X}$ and ${\displaystyle Y}$ are algebraic groups (for notational simplicity we use multiplicative notation for both), and ${\displaystyle R=\{(x,f(x))|x\in X\}}$ where ${\displaystyle f:X\rightarrow Y}$ is a homomorphic one-way function. We consider a proof of knowledge system for relation ${\displaystyle R}$ which we call homomorphic ${\displaystyle ~\Sigma }$-protocol (for ${\displaystyle R}$): The prover, on input ${\displaystyle x\in X,}$ sends ${\displaystyle a=f(k)}$ where ${\displaystyle k{\xleftarrow {r}}X}$. The verifier, on input ${\displaystyle y\in Y}$ , creates a challenge ${\displaystyle c}$ as a random ${\displaystyle k}$-bit string, and the prover responds with ${\displaystyle z=kx^{c}}$. The verifier accepts if ${\displaystyle f(z)=ay^{c}}$. This is a form of several ${\displaystyle ~\Sigma }$- protocols for known homomorphic one-way functions, e.g. Guillou-Quisquater identification scheme [13] for a power function ${\displaystyle f_{e,n}(x)=x^{e}modn}$ and Schnorr’s scheme [17] for exponentiation ${\displaystyle f_{g,p}(x)=g^{x}modp}$. The special HVZK property of a ${\displaystyle ~\Sigma }$-protocol says that there exists an efficient simulator which on input ${\displaystyle y}$ computes pair ${\displaystyle (a,z)}$ for any ${\displaystyle c}$ with the distribution matching that of the prover. The special strong soundness says that there exists an efficient extractor which computes witness ${\displaystyle xs.t.(x,y)\in R}$ for any ${\displaystyle y}$ from any pair of accepting conversations ${\displaystyle (a,c,z)}$ and ${\displaystyle (a,c',z')s.t.c\neq c'}$.

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 ${\displaystyle s.t.}$

• (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 ${\displaystyle R}$ introduced above is an intermediary notion: The simulator is given a “core statement” ${\displaystyle {\dot {y}}\in Y}$ before it sets the CRS string, and then it can simulate the proof for statement ${\displaystyle y={\dot {y}}\cdot f(\delta )}$ for any ${\displaystyle \delta \in X}$. Here is the formal definition:

Definition 1. Let ${\displaystyle X}$ and ${\displaystyle Y}$ be algebraic groups and ${\displaystyle f:X\rightarrow Y}$ be a surjective homomorphic one-way function, all indexed by a public parameter par. Let ${\displaystyle \Pi =(G,P,V)}$ be a proof system in CRS model for relation ${\displaystyle R=\{(x,y)\in X\times Y|y=f(x)\}}$ where ${\displaystyle G}$ is an algorithm that outputs the common reference string. We say that ${\displaystyle \Pi }$ is straight-line ${\displaystyle \epsilon }$-structured-instance zero-knowledge if there exist efficient algorithms ${\displaystyle S1,S2s.t.S1}$ on input par and a core instance ${\displaystyle {\dot {y}}\in Y}$, outputs the CRS string ${\displaystyle \sigma }$ and trapdoor ${\displaystyle td}$, while ${\displaystyle S2}$ on input ${\displaystyle td}$ and a “witness-shift” ${\displaystyle \delta \in X}$ outputs a simulated proof ${\displaystyle {\tilde {\pi }}}$ for instance ${\displaystyle y={\dot {y}}f(\delta )}$, and for all ${\displaystyle ({\dot {x}},{\dot {y}})\in X\times Ys.t.f({\dot {x}})={\dot {y}}}$ the following two properties hold:

• 1. Statistical difference between the following two distributions is at most ${\displaystyle \epsilon :\{\sigma |(\sigma ,td)\leftarrow S1(par,{\dot {y}})\}\{\sigma |\sigma \leftarrow G(par)\}}$
• 2. ${\displaystyle \forall }$ verifier ${\displaystyle V^{*}}$ and ${\displaystyle \forall \delta \in X}$, the following two distributions are identical:

${\displaystyle \{{\tilde {\pi }}|{\tilde {\pi }}\leftarrow V^{*}(y,\sigma )^{S_{2}(td,\delta ,\sigma )};(td,\sigma )\leftarrow S_{1}(par,{\dot {y}});y\leftarrow {\dot {y}}f(\delta )\}}$

${\displaystyle \{\pi |\pi \leftarrow V^{*}(y,\sigma )^{{\mathcal {P}}(x,y,\sigma )};\sigma \leftarrow {\mathcal {G}}(par);y\leftarrow {\dot {y}}f(\delta );x\leftarrow {\dot {x}}\delta \}}$

Commitment Schemes: A commitment scheme ${\displaystyle C}$ in the CRS model consists of probabilistic poly-time algorithms CSetup, CKG, Com and Open. CSetup on input the security parameter ${\displaystyle k}$, generates public parameters cpar, which also determine the commitment message space ${\displaystyle {\mathcal {M}}}$. CKG(cpar) generates the commitment key ${\displaystyle K}$ , ${\displaystyle {\text{Com}}_{K}(m)}$ generates the commitment ${\displaystyle C}$ and the decommitment ${\displaystyle D}$ on message ${\displaystyle m\in {\mathcal {M}}}$, and finally ${\displaystyle {\text{Open}}_{K}(C,D,m)}$ determines if ${\displaystyle D}$ is a valid decommitment of commitment ${\displaystyle C}$ to message ${\displaystyle m}$. A commitment scheme must satisfy that if ${\displaystyle {\text{cpar}}\leftarrow {\text{CSetup}}(1^{k})}$, ${\displaystyle K\leftarrow {\text{CKG(cpar)}}}$, and ${\displaystyle (C,D)\leftarrow {\text{Com}}_{K}(m)}$, then ${\displaystyle {\text{Open}}_{K}(C,D,m)=1}$. Below we define statistical hiding and computational binding properties of commitments because these will be variants of these notions which our scheme satisfies.

${\displaystyle \epsilon }$-Hiding: For all ${\displaystyle {\text{cpar}}\leftarrow {\text{CSetup}}(1^{k}),m0,m1\in {\mathcal {M}},}$ and ${\displaystyle K\leftarrow {\text{CKG}}(cpar)}$, there is less than ${\displaystyle \epsilon }$ statistical difference between the distribution of ${\displaystyle C}$’s output by ${\displaystyle {\text{Com}}_{K}(m_{0})}$ and the distribution of ${\displaystyle C}$’s output by ${\displaystyle {\text{Com}}_{K}(m_{1})}$. A commitment scheme is perfectly hiding if ${\displaystyle \epsilon =0}$. ${\displaystyle (t,\epsilon )}$-Binding: For any algorithm ${\displaystyle {\mathcal {A}}}$ running in time ${\displaystyle t}$ and any cpar output by ${\displaystyle {\text{CSetup}}(1^{k})}$, the probability of ${\displaystyle {\text{Open}}_{K}(C,D_{0},m_{0})={\text{Open}}_{K}(C,D_{1},m_{1})=1}$ and ${\displaystyle m_{0}\neq m_{1}}$ is less than ${\displaystyle \epsilon {\text{where}}(C,D_{0},D_{1},m_{0},m_{1})}$ is outputted by ${\displaystyle {\mathcal {A}}}$ on input ${\displaystyle K}$ and ${\displaystyle K\leftarrow {\text{CKG(cpar)}}}$ and probability is over the coins of CKG and ${\displaystyle {\mathcal {A}}}$. 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 ${\displaystyle {\mathcal {R}}}$ and the Com procedure picks decommitment ${\displaystyle D{\xleftarrow {r}}{\mathcal {R}}}$ and computes the commitment ${\displaystyle C}$ as the deterministic function of ${\displaystyle m}$ and ${\displaystyle D}$.

${\displaystyle ~\Sigma }$-Equivocable Commitments: A commitment scheme is equivocable if there exists an efficient simulator that generates commitment key ${\displaystyle K}$, indistinguishable from real key, together with a trapdoor ${\displaystyle {\text{td}}}$. 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 ${\displaystyle ~\Sigma }$-protocol to a multi-instance ZK proof system with straight-line simulation [15]. Here we define a rather restrictive form of equivocability called ${\displaystyle ~\Sigma }$-equivocability and we show that it is sufficient for compiling ${\displaystyle ~\Sigma }$-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 ${\displaystyle X}$ and ${\displaystyle Y}$ be algebraic groups and let ${\displaystyle f:X\rightarrow Y}$ be a homomorphic one-way function, all indexed by a commitment parameter cpar. We call a commitment scheme ${\displaystyle \epsilon -~\Sigma -}$ equivocable for ${\displaystyle f}$ if there exist probabilistic polytime algorithms tdCKG, tdCom, and RstEquiv, where ${\displaystyle (K,td)\leftarrow {\text{tdCKG}}({\text{cpar}},{\dot {y}}),({\tilde {C}},st)\leftarrow {\text{tdCom}}_{K}(td),}$ and ${\displaystyle ({\tilde {D}},z)\leftarrow {\text{RstEquiv}}_{K}(td,st,c,\delta ),s.t.}$ for any cpar output by CSetup and any ${\displaystyle {\dot {y}}\in Y}$ the following properties hold:

• 1. There is at most ${\displaystyle \epsilon }$ statistical difference between the distribution of ${\displaystyle K}$ ’s output by CKG(cpar) and ${\displaystyle K}$ ’s output by ${\displaystyle {\text{tdCKG}}({\text{cpar}},{\dot {y}})}$.
• 2. For all ${\displaystyle (K,td)\leftarrow {\text{tdCKG}}({\text{cpar}},{\dot {y}}),\delta \in X,andC\in \{0,1\}^{k},if({\tilde {C}},st)}$ is output by ${\displaystyle {\text{tdCom}}_{K}(td)and({\tilde {D}},z)}$ is output by ${\displaystyle {\text{RstEquiv}}_{K}(td,st,c,\delta )}$ then ${\displaystyle {\tilde {D}}}$ is distributed as random decommitment in ${\displaystyle R}$ and ${\displaystyle {\text{Open}}_{K}({\tilde {C}},{\tilde {D}},f(z)({\dot {y}}f(\delta ))^{-c})=1}$.

Intuitively definition 2 says that the equivocation procedure, given ${\displaystyle ({\dot {y}},c,\delta )}$, can open a fake commitment to a message of the form ${\displaystyle a=f(z)({\dot {y}}f(\delta ))^{-c}}$ for some ${\displaystyle z}$. This is useful in straight-line simulation of a proof of knowledge for relation ${\displaystyle R=\{(x,y)\in X\times Y|y=f(x)\}}$.For example, let ${\displaystyle f:QR_{n}\rightarrow QR_{n}}$ where ${\displaystyle f(z)=z^{e}(modn)}$. Consider the HVZK simulator of the ${\displaystyle ~\Sigma }$-protocol for proving knowledge of${\displaystyle e}$ -th root: This simulator picks random ${\displaystyle c}$ and ${\displaystyle z}$ and computes prover’s first message ${\displaystyle a=z^{e}y^{-c}}$. Below we show that Damgard’s compilation [15] (see Figure 3 below) transforms such ${\displaystyle ~\Sigma }$-protocol to structured-instance zero-knowledge using only such ${\displaystyle ~\Sigma }$-equivocable commitments, because the simu- lator can output a fake commitment and then open it to what the ${\displaystyle ~\Sigma }$-protocol simulator would output as the prover’s first message i.e. ${\displaystyle a=z^{e}y^{-c}}$. 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 = ${\displaystyle {\dot {y}}\delta e}$ where ${\displaystyle {\dot {y}}}$ 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 ${\displaystyle \times and\oplus s.t.}$ if ${\displaystyle {\text{Open}}_{K}(C_{1},D_{1},m_{1})=1}$ and ${\displaystyle {\text{Open}}_{K}(C_{2},D_{2},m_{2})=1,}$ then ${\displaystyle {\text{Open}}_{K}(C,D,m)=1}$ for ${\displaystyle C=C1\times C2,D=D1\oplus D2,andm=m_{1}m_{2}}$. Accordingly, a commitment scheme is ${\displaystyle l}$-restricted multiplicatively homomorphic if the homomorphic operation can be applied on only ${\displaystyle l}$ commitment-decommitment pairs generated by Com procedure. Our construction is ${\displaystyle l}$-restricted multiplicatively homomorphic.

￼Common Reference String:

Commitment Key ${\displaystyle K}$ of ${\displaystyle ~\Sigma }$-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 ${\displaystyle ~\Sigma }$-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 ${\displaystyle ~\Sigma }$-protocol and ${\displaystyle ~\Sigma }$-equivocable commitment. This is an identical construction to Damgard’s compiler from ${\displaystyle ~\Sigma }$-protocol to ZKPK proof [15]. Below we show that using only ${\displaystyle ~\Sigma }$-equivocable commitments the same compilation produces structured-instance zero-knowledge proof given homomorphic ${\displaystyle ~\Sigma }$-protocol. As in [15] the resulting protocol is an argument of knowledge, subject to the binding property of the commitment scheme.

Theorem 1. Let ${\displaystyle X}$ and ${\displaystyle Y}$ be algebraic groups, ${\displaystyle f:X\leftarrow Y}$ a homomorphic one-way function, ${\displaystyle c}$ a ${\displaystyle ~\Sigma }$-equivocable commitment over message space ${\displaystyle {\mathcal {M}}\in Y}$ . Then the protocol in figure 3 is a straight-line simulatable structured-instance zero-knowledge proof of knowledge of pre-image of ${\displaystyle f}$ in the CRS model.

Proof. The straight-line simulator ${\displaystyle S=(S1,S2)}$, for structured-instance zero-knowledge proof acts as follows: In the first phase, given cpar and ${\displaystyle {\dot {y}}\in Y,S1{\text{runs}}{\text{tdCKG}}({\text{cpar}},{\dot {y}})}$ to obtain ${\displaystyle (td,K)}$ and sets the common reference string ${\displaystyle \sigma }$ as ${\displaystyle K}$ . In the second phase, given td and witness shift ${\displaystyle \delta \in X,S2{\text{runs}}{\text{tdCom}}_{K}(td)}$ to obtain the fake commitment ${\displaystyle {\tilde {C}}}$ and state ${\displaystyle st}$ and sends ${\displaystyle {\tilde {C}}}$ to the verifier. Upon receiving the challenge ${\displaystyle C}$ from the verifier, ${\displaystyle S2{\text{runs}}{\text{RstEquiv}}_{K}(td,st,{\dot {y}},\delta )}$ to get the response ${\displaystyle z}$ and fake commitment ${\displaystyle {\tilde {D}}}$. According to ${\displaystyle ~\Sigma }$-equivocability property (definition 2) it immediately follows that ${\displaystyle S}$ satisfies conditions in definition 4.

## Aggregatable Zero-Knowledge Proof of Knowledge of ${\displaystyle e}$-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 ${\displaystyle n}$ but use two different public exponents ${\displaystyle e}$ and ${\displaystyle e'}$, it is convenient for us to use the following notation for RSA instance generation: We call an algorithm ${\displaystyle KG_{sRSA}}$ a safe RSA generator if on input security parameter ${\displaystyle k}$ and a prime ${\displaystyle es.t.2k\leqslant e\leqslant 22k,KG_{sRSA}}$ generates a pair ${\displaystyle (n,d){\text{where}}(1)n=pqs.t.p=2p'+1,q=2q'+1}$ and ${\displaystyle p,q,p'}$ and ${\displaystyle q'}$ are all prime numbers ${\displaystyle s.t.|p'|=|q'|}$ and ${\displaystyle p',q'>22k}$ and ${\displaystyle (2)d=e^{-1}mod\phi (n)}$. For later use we define ${\displaystyle n'=p'q'}$. The Advantage of an algorithm ${\displaystyle {\mathcal {A}}}$ in breaking the RSA(e) problem is defined as

${\displaystyle {\text{Adv}}_{KG_{sRSA},{\mathcal {A}},e}^{ow_{R}SA}(\kappa )={\text{Pr}}[x^{e}\equiv ny|(n,d){\xleftarrow {r}}KG(k,e);y{\xleftarrow {r}}Z*;x{\xleftarrow {r}}A(n,e,y)](1)sRSAn}$

￼We say algorithm ${\displaystyle A}$, ${\displaystyle (t,\epsilon )}$-breaks the ${\displaystyle {\text{RSA}}(e)}$ problem on security parameter ${\displaystyle \kappa }$ if ${\displaystyle {\mathcal {A}}}$ runs in time at most ${\displaystyle t}$ and ${\displaystyle {\text{Adv}}_{KG_{sRSA},{\mathcal {A}},e}^{ow_{R}SA}(\kappa )\geqslant \epsilon }$. We say that the ${\displaystyle {\text{RSA}}(e)}$ problem is ${\displaystyle (t,\epsilon )}$-hard (for security parameter ${\displaystyle \kappa }$) if no algorithm ${\displaystyle {\mathcal {A}},(t,\epsilon )}$-breaks it. We note that the requirement that ${\displaystyle p',q'>2^{2k}}$ is just a lower-bound we introduce to enable any party to choose “secondary” public exponent ${\displaystyle e's.t.{\text{gcd}}(e',\phi (n))=1}$ and ${\displaystyle e'>le}$ where ${\displaystyle l}$ is a maximum number of participants in any single instance of the multi-signature scheme.

RSA-based Multiplicatively Homomorphic ${\displaystyle ~\Sigma }$-Equivocable Commitment

Let ${\displaystyle e}$ and ${\displaystyle e'}$ be two prime numbers ${\displaystyle s.t.2^{k}\leqslant e,e'\leqslant 2^{2k}}$ and ${\displaystyle e\leqslant e'/l}$ for some integer ${\displaystyle l}$ and let ${\displaystyle (n,d)}$ be output by ${\displaystyle KG_{sRSA}(k,e)}$. This assures that both ${\displaystyle (n,e)}$ and ${\displaystyle (n,e')}$ are safe RSA instances. We describe an efficient commitment scheme, which is computationally binding under the ${\displaystyle {\text{RSA}}(e')}$ assumption, has ${\displaystyle l-}$ restricted multiplicatively homomorphic property on message space ${\displaystyle {\mathcal {M}}=QR_{n}}$, and is ${\displaystyle ~\Sigma }$-equivocable for ${\displaystyle f(x)=x^{e}(modn)}$. 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 ${\displaystyle e}$ -th root, standard hiding property is not necessary, and ${\displaystyle ~\Sigma }$-equivocability property for the above function is sufficient.

${\displaystyle {\text{CSetup}}(\kappa )}$: Pick prime numbers ${\displaystyle e}$ and ${\displaystyle e's.t.2^{k}\leqslant e,e'\leqslant 2^{2k}}$ and ${\displaystyle e\leqslant e'/l.}$ Run KG_{sRSA} on input ${\displaystyle (k,e)}$ to obtain ${\displaystyle (n,d)}$. Set ${\displaystyle {\text{cpar}}\leftarrow (n,e,e')}$.

${\displaystyle {\text{CKG}}(n,e,e')}$: Pick ${\displaystyle h{\xleftarrow {r}}QR_{n}{\text{and set}}K\leftarrow (n,e,e',h)}$. Note that it is easy to sample random elements in ${\displaystyle QR_{n}}$ by squaring a random element in ${\displaystyle Z_{n}^{*}}$.

${\displaystyle {\text{Com}}_{K}(m)}$:Pick ${\displaystyle r{\xleftarrow {r}}Z_{e}}$ and set ${\displaystyle C\leftarrow h^{r}m^{e'}}$ and ${\displaystyle D\leftarrow r}$. (Hence the decommitment space is ${\displaystyle Z_{e}}$.)

${\displaystyle {\text{Open}}_{K}(C,r,m)}$: Accept iff ${\displaystyle C=h^{r}m^{e'}}$ and ${\displaystyle 0\leqslant r.

${\displaystyle {\text{tdCKG}}((n,e,e'),{\dot {y}})}$: Pick \gamma \xleftarrow{r} [n] [/itex], and set ${\displaystyle h\leftarrow ({\dot {y}})^{\gamma e'},K\leftarrow (n,e,e',h)}$, and ${\displaystyle td\leftarrow (\gamma ,{\dot {y}})}$.

${\displaystyle {\text{tdCom}}_{K}(td)}$ :Picks ${\displaystyle {\xleftarrow {r}}Z_{e}}$ and return ${\displaystyle ({\tilde {C}},st)}$ where ${\displaystyle {\tilde {C}}=({\dot {y}})^{e's}}$ and ${\displaystyle st=s}$.

${\displaystyle {\text{RstEquiv}}_{K}(td,st,c,\delta )}$: Compute ${\displaystyle r=(s+c)\gamma ^{-1}(mode)}$ and ${\displaystyle i=(s+c-\gamma r)/e}$ (over integers) and return ${\displaystyle (r,z)}$ where ${\displaystyle z=({\dot {y}})^{i}(\delta )^{c}}$.

Statistical Hiding: This commitment scheme is ${\displaystyle \epsilon }$-hiding for the messages picked from ${\displaystyle {\tilde {\mathcal {M}}}\in QR_{n}}$ where ${\displaystyle {\tilde {\mathcal {M}}}=\{h^{i(e')^{-1}}|i\in [\epsilon _{E}/2]\}}$ and ${\displaystyle h}$ is determined by the commitment key. To argue this note that the maximum statistical difference between the distributions of the commitments to ${\displaystyle m_{0},m_{1}\in {\tilde {\mathcal {m}}}}$ happens when they correspond to ${\displaystyle i=0}$ and ${\displaystyle i=\epsilon _{E}/2}$ respectively. This way the distributions of the commitments would be ${\displaystyle \{h^{r}\}_{r{\xleftarrow {r}}[e]}}$ and ${\displaystyle \{h^{r+\epsilon e/2}\}_{r{\xleftarrow {r}}[e]}}$ respectively which has a statistical difference equal to ${\displaystyle \epsilon }$.

Computational Binding: This commitment scheme is ${\displaystyle (t,\epsilon )}$-binding if RSA(${\displaystyle e'}$) problem is ${\displaystyle (t,\epsilon )}$-hard. Indeed given the challenge ${\displaystyle (n,e',h)}$, one can use the attacker on binding to find the ${\displaystyle e'}$-th root of ${\displaystyle h}$. The reduction runs the binding attacker to obtain ${\displaystyle (C,r,m,r',m')s.t.{\text{Open}}_{K}(C,r,m)={\text{Open}}_{K}(C,r',m')=1}$ and ${\displaystyle m\neq m'}$. Since ${\displaystyle C=h^{r}m^{e'}=h^{r'}m'^{e'}}$ it follows that ${\displaystyle h^{r-r'}=(m'/m)^{e'}}$. Now since ${\displaystyle r,r', then ${\displaystyle gcd(e',r-r')=1}$ and using extended Euclidian algorithm one can compute ${\displaystyle \alpha ,\beta s.t.\alpha (r-r')+\beta e'=1}$. Thus ${\displaystyle h=h^{\alpha (r-r')+\beta e'}=((m'/m)^{\alpha }h^{\beta })e'}$ and ${\displaystyle e'}$-th root of ${\displaystyle h}$ can be computed as ${\displaystyle (m'/m)^{\alpha }h^{\beta }}$.

l-Restricted Multiplicative Homomorphism: This commitment scheme is multiplicatively homomorphic on ${\displaystyle QR_{n}}$ in the sense that up to ${\displaystyle l\leqslant \lfloor e'/e\rfloor }$ messages can be combined: If ${\displaystyle {(C_{i},r_{i})}_{i=1..l}}$ are commitment-decommitment pairs for messages ${\displaystyle m_{1},...,m_{l}\in QR_{n}}$ each computed by the commitment procedure, then ${\displaystyle r=\sum _{i=1}^{l}{r_{i}}}$ (over integers) is a valid decommitment for commitment ${\displaystyle C=\prod _{i=1}^{l}{C_{i}}}$ for message ${\displaystyle m=\sum _{i=1}^{l}{m_{i}}}$. Note that by setting ${\displaystyle e'\geqslant e2^{k}}$, homomorphism can be used on any feasible set of messages.

${\displaystyle ~\Sigma }$-Equivocability: This commitment scheme is ${\displaystyle 2^{-2k}-~\Sigma }$-equivocable for function (family) ${\displaystyle f(n,e)(x)=x^{e}(modn)}$. First note that for every ${\displaystyle (n,e,e')}$ output by CSetup and every ${\displaystyle {\dot {y}}\in QR_{n}s.t.{\dot {y}}}$ is a generator of ${\displaystyle QR_{n}}$, the distributions of keys generated by ${\displaystyle {\text{CKG}}(n,e,e')}$ and ${\displaystyle {\text{tdCKG}}((n,e,e'),{\dot {y}})}$ are at most ${\displaystyle 2^{-2k}}$ apart, because CKG chooses the key ${\displaystyle h}$ as a random element in ${\displaystyle QR_{n}}$ while tdCKG picks ${\displaystyle h=({\dot {y}})^{e'\gamma }}$ for ${\displaystyle e's.t.gcd(e',\phi (n))=1}$ and ${\displaystyle \gamma }$ chosen at random in ${\displaystyle [n]}$. Moreover the statistical difference between ${\displaystyle [n]}$ and ${\displaystyle [4n']}$ is equal to ${\displaystyle 1-4n'/n<2^{2k}}$. Secondly, if ${\displaystyle {\dot {y}}}$ is a generator of ${\displaystyle QR_{n}}$ then for every ${\displaystyle \gamma \in [n]}$, every ${\displaystyle \delta \in QR_{n}}$ and every ${\displaystyle c\in \{0,1\}^{k}}$, according to the code of tdCom and RstEquiv , ${\displaystyle r,z}$ satisfy ${\displaystyle s+c=\gamma r+ie}$ and ${\displaystyle z=({\dot {y}})^{i}(\delta )^{c}}$, therefore for ${\displaystyle m=z^{e}({\dot {y}}(\delta )^{e})^{-c}}$ we have ${\displaystyle {\tilde {C}}=h^{r}m^{e'}}$ , and hence ${\displaystyle {\text{Open}}({\tilde {C}},r,m)=1}$. Moreover the distribution of the decommitments in the equivocation process i.e. ${\displaystyle \{{\tilde {r}}|s{\xleftarrow {r}}Z_{e};{\tilde {r}}\leftarrow (s+c)\gamma ^{-1}(mode)\}}$ is identical to uniform distribution over ${\displaystyle Z_{e}}$.

Corollary 1. Consider prime number ${\displaystyle 2^{k}\leqslant e\leqslant 2^{2k}}$ and let ${\displaystyle n}$ be a safe RSA modulus output by ${\displaystyle KG_{sRSA}}$ on input ${\displaystyle e}$ and security parameter ${\displaystyle k}$. Consider compilation shown in figure 3 and let the function (family) ${\displaystyle f}$ be ${\displaystyle f(n,e):QR_{n}\rightarrow QR_{n}s.t.f(n,e)(x)=x^{e}(modn)}$ 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 ${\displaystyle e}$ -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 ${\displaystyle ~\Sigma }$-protocol for proving knowledge of ${\displaystyle e}$ -th root. Each party simply executes the aggregatable zero-knowledge proof of ${\displaystyle e}$ -th root of its (hashed) identity string, using the straight-line simulatable aggregatable ZKPK of ${\displaystyle e}$ -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 ${\displaystyle (z,C,D)}$ where ${\displaystyle z\in Z_{n}^{*}}$ and ${\displaystyle (C,D)\in Z_{n}^{*}\times Z_{e}}$ is a commitment-decommitment pair on message ${\displaystyle a=z^{e}({\dot {y}})^{-c}}$. However this commitment can be computed as a deterministic function of the committed message ${\displaystyle a}$ and the decommitment ${\displaystyle D}$ (see Section 4). Therefore ${\displaystyle C}$ can be computed given ${\displaystyle (z,c,D)}$, and hence one can use ${\displaystyle (z,c,D)}$ as the final multi-signature, which reduces the multi-signature size to ${\displaystyle |Z_{n}^{*}|+|Z_{e}|+\kappa <|n|+2k+\log l}$.

Theorem 2. If ${\displaystyle RSA(e)}$ and ${\displaystyle RSA(e')}$ problems are ${\displaystyle (t',\epsilon ')}$-hard, and the IBMS scheme in figure 4 is instantiated with commitment scheme in section 5, which is ${\displaystyle (t_{B},\epsilon _{B})}$-binding and ${\displaystyle \epsilon _{E}-~\Sigma }$-equivocable for function ${\displaystyle f(n,e)(x)=x^{e}(modn)}$, then the resulting IBMS scheme is ${\displaystyle (t,\epsilon ,n,q_{k},q_{s},q_{h})}$-secure in random oracle model where

${\displaystyle t\geqslant 1/2\min(t',t_{B})-(3q_{s}+q_{h})t_{exp}}$

􏰷${\displaystyle \epsilon \leqslant 4q_{k}{\sqrt {(\epsilon '+\epsilon _{B}+\epsilon _{E})q_{h}}}+(q_{h}/{2^{k+1}})^{2}+q_{k}q_{h}/{2^{k-1}}+\epsilon _{E}}$ ${\displaystyle \epsilon \leqslant 4q_{k}{\sqrt {(\epsilon '+\epsilon _{B}+\epsilon _{E})q_{h}}}}$

and ${\displaystyle t_{exp}}$ is the time of one exponentiation in ${\displaystyle Z_{n}^{*}}$.

￼￼￼ ￼￼￼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${\displaystyle mpk}$= (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 ${\displaystyle Id}$ as${\displaystyle sk_{Id}}$\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,${\displaystyle sk_{{Id}_{i}}}$), performs the following steps: 3.1 Pick ki \xleftarrow{r} QRn, ${\displaystyle a_{i}}$ \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 ${\displaystyle c}$ \leftarrow Pj\inP Cj; Set ${\displaystyle c}$ \leftarrow H2(C, IdSet, m); Compute zi \leftarrow ki(xIdi )c and broadcast (zi, Di); 3.3 Output multisignature ${\displaystyle \sigma }$ = (z, C, D), where z = zj and D = Dj . Pj \inP Pj \inP 4. Vrfy(mpk,m,IdSet,\sigma): Parse ${\displaystyle \sigma }$ as (z,C,D) and${\displaystyle mpk}$as (n,e,e',K); Set ${\displaystyle c}$ \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 ${\displaystyle C=({\text{CKG,Com,Open,tdCKG,tdCom,RstEquiv}})}$ be a commitment scheme for public parameters ${\displaystyle \textstyle {cpar}=(n,e,e')}$ and the message space ${\displaystyle {\mathcal {M}}}$ equal to ${\displaystyle QR_{n}}$. Assume ${\displaystyle C}$ is ${\displaystyle l}$-restricted multiplicatively homomorphic, ${\displaystyle (t_{B},\epsilon _{B})}$-binding and ${\displaystyle \epsilon _{E}-~\Sigma }$-equivocable for ${\displaystyle f(e,n)(x)=x^{e}(modn)}$. Given a ${\displaystyle (t,\epsilon ,n,q_{k},q_{s},q_{h})}$ -forger ${\displaystyle {\mathcal {F}}}$, consider two simulators ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$ that simulate the role of the honest player as in the experiment ${\displaystyle {\text{Exp}}_{\text{IBMS}}^{uu-cma}}$ interacting with the forger ${\displaystyle {\mathcal {F}}}$. ${\displaystyle {\mathcal {B}}_{0}}$ takes as an input a set ${\displaystyle \{c_{1},c_{2},...,c_{q_{h}}\}}$ where ${\displaystyle c_{i}'s}$ are in ${\displaystyle \{0,1\}^{k}}$ and runs Setup procedure to obtain ${\displaystyle (mpk,msk)}$ and follows the real protocol i.e. answers to forger’s key derivation queries and signing queries using procedures KeyDer and MSign respectively. Additionally, ${\displaystyle {\mathcal {B}}_{0}}$ answers the forger’s hash queries and performs an extra finalization process by following the procedures SimHash and Finalize in Figure 5. The simulator ${\displaystyle {\mathcal {B}}_{1}}$, on the other hand, takes as an input an RSA challenge ${\displaystyle (n,e,{\dot {y}})}$ and a set ${\displaystyle \{c_{1},c_{2},...,c_{q_{h}}\}}$ where ${\displaystyle c_{i}}$'s are in ${\displaystyle \{0,1\}^{k}}$ 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 ${\displaystyle {\mathcal {B}}_{1}}$ uses Coron’s technique [18] to embed the RSA challenge in the hashes of the ID’s of the players with some biased probability ${\displaystyle 1-\rho }$ hoping that the forgery be based upon the ${\displaystyle Id}$ of the player for which the RSA challenge is indeed embed-ded. This way ${\displaystyle {\mathcal {B}}_{1}}$ passes the signing queries on behalf of identity ${\displaystyle Id}$ just like real protocol using the procedure MSign if the RSA challenge is not embedded in the hash of ${\displaystyle Id}$ and otherwise ${\displaystyle {\mathcal {B}}_{1}}$ uses the straight-line structured-instance zero-knowledge simulator for proof of knowledge of ${\displaystyle e}$ -th root (see corollary 1) to simulate the signature protocol on behalf of the identity ${\displaystyle Id}$. Both ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$, after receiving a valid forgery from ${\displaystyle {\mathcal {F}}}$, 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 ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$ return ${\displaystyle (j,(m,IdSet,\sigma ))s.t.{\text{Vrfy}}(mpk,m,IdSet,\sigma )=1}$ and there exists at least one uncorrupted ${\displaystyle Ids.t.(m,Id)}$ is never queried for signing. The simulators ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$ set up empty tables ${\displaystyle H_{1}}$ and ${\displaystyle H_{2}}$ to simulate the hash functions ${\displaystyle {\mathcal {H}}_{1}}$ and ${\displaystyle {\mathcal {H}}_{2}}$ respectively and use the set ${\displaystyle \{c_{1},c_{2},...,c_{q_{h}}\}}$ to answer to the hash queries to ${\displaystyle {\mathcal {h}}_{2}}$ which enables the utilization of forking lemma (as formulated e.g. in [5][6]).

Now for ${\displaystyle I\in \{0,1\}}$ let’s lower-bound ${\displaystyle acc_{{\mathcal {B}}_{I}}}$ the probability that ${\displaystyle {\mathcal {B}}_{I}}$ generates a “useful” output i.e. an output other than ${\displaystyle (0,\lambda )}$. This happens when ${\displaystyle {\mathcal {B}}_{I}}$ does not abort in any of the key derivation queries or finalization procedure. Therefore ${\displaystyle acc_{{\mathcal {B}}_{I}}\geqslant \rho ^{q_{K}}(1-\rho )}$. This function reaches its maximum when ${\displaystyle \rho =q_{K}/(q_{K}+1)}$. Substituting this value of ${\displaystyle \rho }$ yields:

􏰌${\displaystyle acc_{{\mathcal {B}}_{I}}\geqslant \left({\frac {q_{K}}{q_{K}+1}}\right)^{q_{K}}\left(1-{\frac {q_{K}}{q_{K}+1}}\right)\geqslant {\frac {1}{q_{K}}}\left({\frac {q_{K}}{q_{K}+1}}\right)^{q_{K}+1}\geqslant {\frac {1}{4q_{K}}}}$

For ${\displaystyle I\in \{0,1\}}$, consider ${\displaystyle {\mathcal {F}}_{{\mathcal {B}}_{I}}}$ -the forking algorithm associated with ${\displaystyle {\mathcal {B}}_{I}}$ . The success event of ${\displaystyle {\mathcal {F}}_{{\mathcal {B}}_{I}}}$ denoted by ${\displaystyle E^{{\mathcal {B}}_{I}}}$ is that the algorithm ${\displaystyle {\mathcal {B}}_{I}}$ outputs two tuples ${\displaystyle (c_{j},(x,n_{1},m,IdSet,\sigma ))}$ and ${\displaystyle ({\tilde {c}},({\tilde {x}},{\tilde {n_{1}}},{\tilde {m}},{\tilde {IdSet}},{\tilde {\sigma }}))s.t.c_{j}\neq {\tilde {c_{j}}}}$ where j is the index of the hash responses upon which the forged multisignature is based. Since the random coins of the algorithm ${\displaystyle {\mathcal {B}}_{I}}$ and the hash responses of the algorithm ${\displaystyle {\mathcal {B}}_{I}}$ previous to ${\displaystyle j^{\textstyle th}}$ 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 ${\displaystyle {\mathcal {H}}_{2}}$ before ${\displaystyle j^{\textstyle th}}$ query must be the same, too. Thus the occurrence of ${\displaystyle E^{{\mathcal {B}}_{I}}}$ implies ${\displaystyle IdSet={\tilde {IdSet}}}$, ${\displaystyle C={\tilde {C}}}$ and ${\displaystyle m={\tilde {m}}}$. Note that ${\displaystyle IdSet={\tilde {IdSet}}}$ also implies ${\displaystyle y={\tilde {y}}}$. This is because ${\displaystyle y=\prod _{Id_{i}\in IdSet}{({\mathcal {H}}_{1}(Id_{i}))^{2}},{\tilde {y}}=\prod _{Id_{i}\in {\tilde {IdSet}}}{({\mathcal {H}}_{1}(Id_{i}))^{2}}}$ and the values for ${\displaystyle {\mathcal {H}}_{1}(Id_{i})}$ for all ${\displaystyle Id_{i}\in IdSet}$ is fixed before the fork. The success event ${\displaystyle E^{{\mathcal {B}}_{I}}}$ can be partitioned into two cases (1) event ${\displaystyle E_{1}^{{\mathcal {B}}_{I}}}$ in which ${\displaystyle E^{{\mathcal {B}}_{I}}}$ happens and ${\displaystyle z^{e}y^{-c}={\tilde {z}}^{e}{\tilde {y}}^{-c}}$ (2) event E_2^{\mathcal{B}_I} in which ${\displaystyle E^{{\mathcal {B}}_{I}}}$ happens an ${\displaystyle z^{e}y^{-c}\neq {\tilde {z}}^{e}{\tilde {y}}^{-c}}$. Obviously ${\displaystyle E^{{\mathcal {B}}_{I}}=E_{1}^{{\mathcal {B}}_{I}}\cup E_{2}^{{\mathcal {B}}_{I}}}$ and hence ${\displaystyle {\text{Pr}}[E^{{\mathcal {B}}_{I}}]\leqslant {\text{Pr}}[E_{1}^{{\mathcal {B}}_{I}}]+{\text{Pr}}[E_{2}^{{\mathcal {B}}_{I}}]}$. On the other hand, according to the forking lemma, ${\displaystyle E^{{\mathcal {B}}_{I}}}$ can be lower bounded by ${\displaystyle \epsilon _{{\mathcal {B}}_{I}}}$ , the success probability of the simulator ${\displaystyle {\mathcal {B}}_{I}}$:

${\displaystyle acc_{{\mathcal {B}}_{I}}\cdot \left({\frac {acc_{{\mathcal {B}}_{I}}}{q_{h}}}-{\frac {1}{2^{k}}}\right)\leqslant {\text{Pr}}[E^{{\mathcal {B}}_{I}}]\leqslant {\text{Pr}}[E_{1}^{{\mathcal {B}}_{I}}]+{\text{Pr}}[E_{2}^{{\mathcal {B}}_{I}}](2)}$

If ${\displaystyle c_{i}}$’s are uniformly distributed in ${\displaystyle \{0,1\}^{k}}$ then ${\displaystyle {\mathcal {F}}}$’s view in interaction with ${\displaystyle {\mathcal {B}}_{0}}$ is identical to the real execution of the protocol. As for ${\displaystyle {\mathcal {B}}_{1}}$, since ${\displaystyle C}$ is ${\displaystyle \epsilon _{E}-~\Sigma }$ -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 ${\displaystyle \epsilon _{E}}$ apart and secondly the distribution of the tuples ${\displaystyle (C_{1},D_{1},z_{1})}$ generated in each signature instance in the interaction between ${\displaystyle {\mathcal {F}}}$ and ${\displaystyle {\mathcal {B}}_{1}}$ is identical the distributions of the same variables in the real execution. Thus, since our simulation is straight line, total distance between ${\displaystyle {\mathcal {F}}}$’s view in interaction with ${\displaystyle {\mathcal {B}}_{1}}$ and in real execution is at most ${\displaystyle \epsilon _{E}}$. This implies in particular that ${\displaystyle \epsilon _{{\mathcal {B}}_{0}}=\epsilon ,|\epsilon _{{\mathcal {B}}_{0}1}-\epsilon |\leqslant \epsilon _{E}}$ and ${\displaystyle |{\text{Pr}}[E_{2}^{{\mathcal {B}}_{0}}]-{\text{Pr}}[E_{2}^{{\mathcal {B}}_{1}}]|\leqslant \epsilon _{E}}$. So ${\displaystyle \epsilon /4q_{k}\leqslant acc_{{\mathcal {B}}_{0}}}$ and ${\displaystyle (\epsilon -\epsilon _{E})/4q_{k}\leqslant acc_{{\mathcal {B}}_{0}}}$. Thus equation (2) becomes:

${\displaystyle {\frac {\epsilon -\epsilon _{E}}{4q_{k}}}\left({\frac {\epsilon -\epsilon _{E}}{4q_{k}q_{h}}}-{\frac {1}{2^{k}}}\right)\leqslant {\text{Pr}}[E_{1}^{{\mathcal {B}}_{1}}]+{\text{Pr}}[E_{2}^{{\mathcal {B}}_{0}}]+\epsilon _{E}(3)}$

The actual reduction algorithm ${\displaystyle {\mathcal {R}}}$, runs both ${\displaystyle {\mathcal {F}}_{{\mathcal {B}}_{0}}and{\mathcal {F}}_{{\mathcal {B}}_{1}}}$. If ${\displaystyle E_{1}^{{\mathcal {B}}_{1}}}$ happens, then ${\displaystyle z^{e}y^{(}-c_{j})={\tilde {z}}^{e}{\tilde {y}}^{(}-c_{j})}$. Substituting ${\displaystyle y={\tilde {y}}=({\dot {y}})^{2n_{1}}x^{2e}}$ where ${\displaystyle n_{1}}$ is the number of players for whom the reduction has embedded the challenge (see figure 5) yields

${\displaystyle \left((z/{\tilde {z}}x^{2(c_{j}-{\tilde {c}}_{j})})\right)^{e}=({\dot {y}})^{2n_{1}(c_{j}-{\tilde {c}}_{j})}(4)}$

￼￼￼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), set${\displaystyle mpk}$as (n,e,e',K) and run F on input mpk; SimKeyDer(I d): Query H1 on ${\displaystyle Id}$ 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 ${\displaystyle Id}$ 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 ${\displaystyle \sigma }$ 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; ${\displaystyle c}$ \leftarrow ${\displaystyle c}$ \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 ${\displaystyle \sigma }$ = (z, C, D); Dj; x \leftarrow return (j, (x, n1, m, IdSet, \sigma)) where j is the index of ${\displaystyle c}$ in the hash table H2. ￼Fig. 5. The procedures SimHash and Finalize that ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$ use and the procedures Init, SimKeyDer, and SimMSign that ${\displaystyle {\mathcal {B}}_{1}}$ uses.

Now since ${\displaystyle l2^{k+1}, therefore ${\displaystyle gcd(e,n_{1}(c_{j}-{\tilde {c}}_{j}))=1}$ and one can easily compute the ${\displaystyle e}$ -th root of ${\displaystyle {\dot {y}}}$ using the extended Euclidean algorithm.

If ${\displaystyle E_{2}^{{\mathcal {B}}_{0}}}$ happens, then ${\displaystyle {\mathcal {R}}}$ immediately translates it into an attack against binding property of commitment scheme ${\displaystyle C}$ by returning ${\displaystyle (c,D,{\tilde {D}},z^{e}y^{-c_{j}},{\tilde {z}}^{e}{\tilde {y}}^{-c_{j}})}$. To see this note that as argued before, ${\displaystyle y={\tilde {y}},C={\tilde {C}}}$ and since ${\displaystyle E_{2}^{{\mathcal {b}}_{0}}}$ is occurred, thus ${\displaystyle z^{e}y^{-c_{j}}\neq {\tilde {z}}^{e}{\tilde {y}}^{-c_{j}}}$ and due to validity of the forgeries we have ${\displaystyle {\text{Open}}_{K}(C,D,z^{e}y^{-c_{j}})={\text{Open}}_{K}(C,D,{\tilde {z}}^{e}{\tilde {y}}^{-c_{j}})=1}$. Moreover the commitment key ${\displaystyle K}$ is outputted by CKG in the execution of ${\displaystyle {\mathcal {B}}_{0}}$. Thus ${\displaystyle {\text{Pr}}[E_{1}^{{\mathcal {B}}_{1}}]\leqslant \epsilon '}$ and ${\displaystyle {\text{Pr}}[E_{2}^{{\mathcal {B}}_{0}}]\leqslant \epsilon _{B}}$ and hence equation (3) becomes

${\displaystyle {\frac {\epsilon -\epsilon _{E}}{4q_{k}}}\left({\frac {\epsilon -\epsilon _{E}}{4q_{k}q_{h}}}-{\frac {1}{2^{k}}}\right)\leqslant \epsilon '+\epsilon _{B}+\epsilon _{E}(5)}$

￼￼￼The running time ${\displaystyle t_{R}}$ of the reduction algorithm ${\displaystyle {\mathcal {R}}}$ is twice the maximum of running time of the algorithms ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$. But the running time of ${\displaystyle {\mathcal {B}}_{0}}$ and ${\displaystyle {\mathcal {B}}_{1}}$ is dominated by the running time of the forger ${\displaystyle {\mathcal {F}}}$ plus the time spent by the simulators to answer the hash, signing and key derivation queries. Thus ${\displaystyle t_{R}\leqslant 2(t+(3q_{s}+q_{h})t_{exp})}$ where ${\displaystyle t_{exp}}$ is the time required for exponentiation in ${\displaystyle Z_{n}^{*}}$. On the other hand since ${\displaystyle {\mathcal {R}}}$ either answers the RSA challenge or returns an attack against the binding property of the commitment ${\displaystyle C}$, it must be true that ${\displaystyle \min(t',t_{B})\leqslant t_{R}}$. Thus:

${\displaystyle t\leqslant {\frac {1}{2}}\min(t',t_{B})-(3q_{s}+q_{h})t_{exp}}$

## 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 ${\displaystyle {\mathcal {H}}_{2}}$ 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 ${\displaystyle \sigma }$ as ${\displaystyle (z,C,D)}$ and ${\displaystyle mpk}$ as ${\displaystyle (n,e,e',K)}$; Compute ${\displaystyle R\leftarrow z^{e}\prod _{Id_{i}\in IdSet}{({\mathcal {H}}_{1}(Id_{i}))^{2c_{i}}}}$ where ${\displaystyle c_{i}}$ is output of ${\displaystyle {\mathcal {H}}_{2}}$ on input ${\displaystyle (C,IdSet,m_{i})}$ and check whether ${\displaystyle {\text{Open}}_{K}(C,D,R)=1}$. 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 ${\displaystyle E_{2}}$ in the previous proof) or to find ${\displaystyle e}$-th root of the challenge (event ${\displaystyle E_{1}}$ 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${\displaystyle e}$-th root of the challenge we have the following equation instead of equation 4 in the previous proof:

${\displaystyle ({\dot {y}})^{2\sum _{Id_{i}\in IdSet_{1}}({\tilde {c}}_{i}-c_{i})}=\left((z/{\tilde {z}})\prod _{Id_{i}\in IdSet}x_{i}^{2({\tilde {c}}_{i}-c_{i})}\right)^{e}}$

Therefore to be able to compute ${\displaystyle e}$-th root of ${\displaystyle {\dot {y}}}$, we need ${\displaystyle gcd(e,2\sum _{Id_{i}\in IdSet_{1}}{({\tilde {c}}_{i}-c_{i})})=1}$. In particular, the reduction succeeds as long as ${\displaystyle \sum _{Id_{i}\in IdSet_{1}}({\tilde {c}}_{i}-c_{i}))\neq 0\mod e}$, i.e. unless the challenges in the two branches of the forking algorithm sum up to the same value mod ${\displaystyle e}$, which happens with only negligible probability.

## References:

1. 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. 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. 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. 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. Craig Gentry and Zulfikar Ramzan. Identity-based aggregate signatures. In Public Key Cryptography, pages 257–273, 2006.
8. 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. 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. Louis C. Guillou and Jean-Jacques Quisquater. A ”paradoxical” indentity- based signature scheme resulting from zero-knowledge. In CRYPTO, pages 216–231, 1988.
14. 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. 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 zandi@ics.uci.edu
2. Department of Computer Science, University of California, Irvine stasio@ics.uci.edu