Tight Security for BBS Signatures

Tight Security for BBS Signatures ‹ Rutchathon Chairattana-Apirom1‹‹ , Dennis Hofheinz2 , and Stefano Tessaro1

arXiv:2608.06724v1 [cs.CR] 7 Aug 2026

1

Paul G. Allen School of Computer Science & Engineering University of Washington, Seattle, US {rchairat,tessaro}@cs.washington.edu 2 Department of Computer Science ETH Zurich, Switzerland hofheinz@inf.ethz.ch

Abstract. This paper studies the concrete security of BBS signatures (Boneh, Boyen, Shacham, CRYPTO ’04; Camenisch and Lysyanskaya, CRYPTO ’04), a popular algebraic construction of digital signatures which underlies practical privacy-preserving authentication systems and is undergoing standardization by the W3C and IRTF. Schäge (Journal of Cryptology ’15) gave a tight standard-model security proof under the q-SDH assumption for a less efficient variant of the scheme, called BBS+—here, q is the number of issued signatures. In contrast, the security proof for BBS (Tessaro and Zhu, EUROCRYPT ’23), also under the q-SDH assumption, is not tight. Nonetheless, this recent proof shifted both standardization and industry adoption towards the more efficient BBS, instead of BBS+, and for this reason, it is important to understand whether this tightness gap is inherent. Recent cryptanalysis by Chairattana-Apirom and Tessaro (ASIACRYPT ’25) also shows that a tight reduction to q-SDH is the best we can hope for. This paper closes this gap in two different ways. On the positive end, we show a novel tight reduction for BBS in the case where each message is signed at most once–this case covers in particular the common practical use case which derandomizes signing. On the negative end, we use a meta-reduction argument to prove that if we allow generating multiple signatures for the same message, then no algebraic reduction to q-SDH (and its variants) can be tight.

1

Introduction

Many privacy-preserving authentication protocols benefit from digital signature schemes that are fully algebraic, i.e., all operations performed during signing are within the group (for example, signing does not involve the evaluation of a cryptographic primitive such as a hash function). Such signatures typically enable efficient zero-knowledge proofs of knowledge of valid message-signature pairs, possibly additionally ensuring the message satisfies a certain predicate. Typical applications include anonymous credentials [CL04, TAKS07], direct anonymous attestation [Che10, BL10, CDL16], and k-time anonymous authentication [ASMC13]. There are multiple examples of such signatures, such as structure preserving [AFG` 10] or PointchevalSanders [PS16] signatures. In this work, we focus on BBS signatures [BBS04, ASMC13, CDL16, TZ23], which have been favored in real-world deployment, especially in the space of anonymous credentials. In particular, BBS signatures are implemented in industry [mat, mic] and covered by standardization efforts by the W3C Verifiable Credentials working group [w3c] and by the Decentralized Identity Foundation, the latter leading to an RFC draft by the IRTF [LKWL26]. Due to widespread interest in adoption, it is also crucial to gain a complete understanding of their concrete security, but recent works on security proofs [TZ23] and cryptanalysis [CAT26] highlight important gaps between upper and lower bounds on the concrete security of BBS. As the main contribution of this work, we complete the picture of our understanding of the concrete security of BBS signatures. We give a new tight proof for the most common use case of BBS signatures (which covers in particular its standardized version), along with an impossibility result showing that a more general tightness result is not possible. A preliminary version of this paper appears in the proceedings of EUROCRYPT 2026. This is the full version. © IACR 2026. ‹‹ A portion of this work is done while visiting ETH Zurich. ‹

BBS and its security. BBS signatures were first put forward by Camenisch and Lysyanskaya [CL04] as a standalone signature scheme, taking inspiration from the concurrent work by Boneh, Boyen, and Shacham [BBS04], which used a similar construction to add exculpability to the well-known BBS group signature scheme. (Hence, the rather confusing naming.) BBS can sign any message vectors m ⃗ P Zℓp , and produce a signature σ “ pA, eq consisting of a group element A P G1 and a scalar e P Zp such that 1 A“ x´e

˜ G1 `

ℓ ÿ

¸ ⃗ mris ⃗ Hris

,

i“1

⃗ ⃗ where x is the secret key and G1 , Hr1s, . . . , Hrℓs are generators of G1 . It is not hard to see that the signature can be verified, given the verification key X2 “ xG2 P G2 , using a bilinear pairing. Neither work [CL04, BBS04], however, gave a proof of security. Au, Susilo, and Mu [ASMC13] later proved the security of a less efficient variant of BBS, which is typically referred to as BBS+. One can think of BBS+ as a variant of BBS where the first message coordinate mr1s ⃗ is set to a random scalar s, which is then included as a part of the signature σ “ pA, e, sq. Their security proof is based on the q-SDH assumption in type-2 pairings with q denoting the number of signing queries. Later on, Camenisch, Drijvers, and Lehmann [CDL16] adapted the proof to the more efficient type-3 pairings. These proofs are not tight, due to an extra multiplicative advantage loss of q. Schäge [Sch15] gave an alternative tight reduction to q-SDH for a scheme essentially equivalent to BBS+. Hofheinz and Kiltz [HK12], with a non-tight proof, showed existential unforgeability security for a signature scheme equivalent to BBS but with bit-vector messages m ⃗ P t0, 1uℓ . Tessaro and Zhu [TZ23] more recently showed that the original BBS signature scheme (i.e., without using the random scalar s) can also be proved secure based on the q-SDH assumption. This led to the RFC draft [LKWL26] transitioning to BBS signatures instead of BBS+. However, unlike the case of BBS+, their proof is non-tight, whereas the tight proof [Sch15] inherently relies on the extra randomization via the scalar s, and does not apply to BBS. They were only able to give a tight security proof in the Algebraic Group Model (AGM) [FKL18]. This leads to the following natural question: Can we give a tight security reduction for BBS signatures without resorting to the Algebraic Group Model? We note that these works are complemented by recent cryptanalysis work by Chairattana-Apirom and Tessaro [CAT26] which shows that any q-SDH attack can be turned into an attack against all variants of BBS/BBS+ with equal advantage (and roughly equal running time). This means that a tight reduction to q-SDH is the best we can hope for any of these schemes, and the question remains open on whether such a reduction exists for BBS. Why does it matter? Ascertaining whether a multiplicative q loss is inherent has important consequences on choosing parameters that guarantee a certain security level. To this end, we would typically plug into our bound the generic advantage upper bound Opqt2 {pq for breaking q-SDH by a t-time adversary, where p is the order of the group. This q-SDH bound is tight for many choices of q due to the attacks by Cheon [Che06] and Brown-Gallant [BG04]. A non-tight reduction would then give a concrete security advantage upper bound of Opq2 t2 {pq. For a typical parameter choice such as p « 2256 and q “ 264 , such a proof would only guarantee 64-bit security (t “ 264 ). In contrast, a tight reduction would ensure 96-bit security, essentially matching the cryptanalysis of [CAT26]. Result I: Tightness for distinct messages. For our first main contribution, we give an affirmative answer to the above question for the case of signing distinct messages. This special case is the most relevant to practice. While BBS indeed allows signing a message multiple times, picking distinct values of e, in practice one would derandomize this choice (using a pseudorandom function applied to the message), and this is the construction covered by the IRTF draft [LKWL26]. Accordingly, our result effects the parameter choices for the standardization by reinforcing that the version considered by the draft does not admit any better generic attack than that of [CAT26]. 2

Our reduction only shares very basic elements from prior work, but is otherwise entirely novel. As in prior work, the main barrier is handling the case where the adversary produces a forgery σ ˚ “ pA˚ , e˚ q for a value e˚ which has been used by one of the signatures that the adversary has previously obtained. The reduction is given a q-SDH instance consisting of xG1 , x2 G1 , . . . , xq G1 to simulate the ℓ ` 1 generators used by the scheme, hoping that a forgery of the above type will allow us to extract x using a well-known trick by Boneh-Boyen [BB08]. In particular, one can think without loss of generality of such a strategy as assigning specific polynomials in x to the simulated generator, i.e., for ℓ “ 1, we may set G1 “ f pxqG1 and H “ gpxqG1 , for known polynomials f and g, and unknown x. Our strategy differs substantially from prior works in how we pick these polynomials, and how we generate the values e used by each signature. In particular, verifying that our strategy produces the right distribution is non-trivial, and requires a fairly involved probabilistic analysis using the H-coefficient technique from symmetric cryptography. (This technique was also used in [TZ23] as well as more recently in [BDLR25].) One caveat is that we require the d-SDH assumption with d “ Θpqq instead of q-SDH, but still with a small constant (i.e., d « 10q). Note that this still implies the same asymptotic generic upper bound as q-SDH. We give further details below in our technical overview. Result II: Non-tightness for general messages. This still leaves open whether such tight reductions exist when messages may repeat. On that note, we show via a meta-reduction argument that a tight reduction in the standard model is in fact not possible. Concretely, no algebraic and straight-line reduction to d-SDH (for any integer d) can achieve less than Θpqq factor loss, matching the reduction in [TZ23]. (Here, algebraic reductions can explain their group element outputs with algebraic representations based on previously obtained elements.) This indeed covers most reductions for group-based signatures and all existing reductions for BBS. We stress that the reductions in our impossibility results are in the standard model, while our meta-reductions work in the AGM [FKL18]. We also extend the impossibility to rewinding reductions: concretely, any reduction that runs the adversary r times will incur at least a Θpq{r2 q factor loss. Broader picture: Tight signatures. Generally, the quest for tight security reductions has a long history, starting with concrete security [BDJR97], and tight security reductions for public-key encryption [BBM00, HJ12, BJLS16], digital signatures [CJ07, HJ12, BKP14], and other cryptographic primitives (e.g., key exchange [BHJ` 15, BJLS16, HHK18] or identity-based encryption [CW13, BKP14]). The motivation for these works is both understanding the exact security guarantees given by a particular construction, and optimizing parameter choices (as explained above). In the case of digital signatures, we do have tightly secure constructions from standard complexity assumptions, even for schemes with additional properties (like structure-preserving [AHN` 17] or multisignatures [BW24]). However, those constructions are less efficient than “ordinary” (i.e., not known to be tightly secure) signature schemes. Little is known about the tight security of practical and popular signature schemes (such as BBS signatures), although of course it is particularly important to be able to give concrete security guarantees for such schemes. We remark that our work does not consider the multi-user settings, where the adversary can (adaptively) corrupt multiple signers. Indeed, the lower bound by [BJLS16] rules out tight reductions for multi-user security with adaptive corruptions of any standard model signature scheme. Thus, we cannot hope to prove BBS tight in this setting.

2

Technical Overview

2.1

Prior Non-Tight Reductions

We start by reviewing prior security reductions for BBS/BBS+ signatures for message length ℓ “ 1 (extending to any ℓ ą 1 is quite simple). Recall that a BBS signature on message m P Zp for a verification key X2,1 P G2 1 and secret key x P Zp is of the form pA, eq where A “ x´e pG1 ` mHq and e Ð$ Zp (G1 , H are the public parameters). For simplicity, we will call e the tag. The BBS security proof (for ℓ “ 1) considers two cases for the forgery pA˚ , e˚ q with respect to the previously obtained signatures pσi “ pAi , ei qqiPrqs : (a) e˚ R tei uiPrqs (which already has a tight reduction), and (b) e˚ P tei uiPrqs (which is our focus throughout this paper). In 3

both cases, the reduction taking as input a q-SDH instance pG1 , pX1,i “ xi G1 qiPrqs , G2 , X2,1 “ xG2 q follows a common template: Set up the public parameters: The reduction sets the verification key as X2,1 and the public parameters as G1 “ f pxqG1 , H “ gpxqG1 depending on some polynomials f, g P Zďq p rXs. These can be efficiently computed from the q-SDH instance. (At this stage, some tags ei may not be determined.) Simulate signing queries: On query mi P Zp , select ei such that pX ´ ei q ‌ f pXq ` mi gpXq. Indeed, i gpxq this divisibility condition is necessary for the reduction to compute Ai “ f pxq`m G1 from its SDH x´ei instance. Extract SDH solution: On the forgery pm˚ , σ ˚ “ pA˚ , e˚ qq, if pX´e˚ q ffl f pXq`m˚ gpXq, the reduction can 1 extract an SDH solution pe˚ , Z “ x´e ˚ G1 q via the by-now well-known technique by Boneh-Boyen [BB08] (see Remark 3.1). Importantly, the chosen ei ’s should still look uniformly random. For Case (b), if the messages m1 , . . . , mq are known to the reduction beforehand, the reduction can sample e1 , . . . , eq Ð$ Zp and find f and g such that for each i P rqs, pX ´ ei q ‌ f pXq ` mi gpXq (allowing simulation) but pX ´ ei q ffl f pXq ` m1 gpXq (allowing extraction if e˚ “ ei ) for m1 ‰ mi via polynomial interpolation. This is the key insight behind the tight proof for BBS+ signatures (not BBS) given in [Sch15]. However, this only gives a tight reduction for non-adaptively chosen queries. ˚ With adaptive queries, the proof given by ś Tessaro and Zhu [TZ23] first ś guesses an index i P rqs such 1 ˚ that e “ ei˚ , and set f pXq “ αpX ´ ei˚ q i‰i˚ pX ´ ei q and gpXq “ β i‰i˚ pX ´ ei q. This allows them to simulate the i˚ -th query for any mi˚ using ei˚ “ αe1i˚ ` mi˚ and still extract a solution from a forgery pm˚ ‰ mi˚ , A˚ , e˚ “ ei˚ q. However, the guessing results in a q factor loss. 2.2

Our Tight Reduction

We now give a high-level overview of our tight reduction against adversaries who make distinct signing queries m1 , . . . , mq P Zp . This implies that derandomized BBS signatures (which is the version specified in the IRTF draft [LKWL26]) is actually tightly secure from the d-SDH assumption for d “ Θpqq. Reduction idea. One property of Tessaro and Zhu’s reduction is that for the i˚ -th signing query, ei˚ (not e1i˚ ) can only be used to simulate a specific message mi˚ and a signature pA˚ , ei˚ q for any m˚ ‰ mi˚ can be used to extract a SDH solution. Our hope is to achieve this property for a large number of tags used in the signing queries (a constant fraction suffices) while still being able to simulate without knowing the messages in advance. At a high level, we will set up G1 , H so that (1) on query mi , attempt to find such good ei to simulate the signing, and (2) if we cannot, we use the tags from a “stash”, denoted er1 , . . . erq , prepared in advance; note that the tags from the stash will not allow us to extract an SDH solution. More precisely, our reduction strategy is as follows: Setting up G1 , H: Sample a random monic polynomial f of degree d, β Ð$ Z˚p , and the stash er1 , . . . erq Ð$ Zp . Then, we set ś ś G1 “ f pxq iPrqs px ´ eri qG1 , H “ β iPrqs px ´ eri qG1 . Simulation: On the i-th signing query mi P Zp , check if f pXq ` mi β has a “unique” zero in Zp , denoted ś pf pxq`mi βq

px´r ei q

iPrqs e. If so, set ei Ð e; otherwise, set ei Ð eri . Then, compute Ai “ x´ei ś G1 as a linear combination of the SDH instance. This is possible because pX ´ ei q ‌ pf pXq ` mi βq iPrqs pX ´ eri q. Extraction: On the forgery pm˚ , pA˚ , e˚ qq such that e˚ “ ei˚ for some i˚ P rqs, if i˚ is the index where we use the stash, abort. Otherwise, since m˚ ‰ mi˚ (by freshness of the forgery), f pXq ` m˚ β does not have ei˚ as a zero. Thus, pX ´ ei˚ q ffl pf pXq ` m˚ βq, allowing us to extract a SDH solution. The success of our reduction hinges on whether the index i˚ (defined by the forgery) is such that ei˚ is not from the stash. More precisely, this is the event i˚ R S Ď rqs where we define S :“ ti P rqs : |f ´1 p´mi βq| “ 1u, as the set of indices i where ei is a zero of f pXq`mi β. Note that the set of preimages of a, f ´1 paq, is equivalent to the set of zeros of f pXq´a. To show why our reduction is tight, we analyze the distribution of the transcript between the reduction and the adversary augmented with the set S, i.e., pG1 , H, G2 , X2 , pmi , ei qiPrqs , Sq. The

4

formal analysis of the distribution relies on the H-coefficient technique, but essentially, the distribution of the transcript satisfies the following properties: (1) The tags ei ’s are indistinguishable from uniformly random. (2) The distribution of S is (almost) independent of the rest of the transcript. (3) For any i˚ P rqs, the probability that a sampled S contains i˚ is at least e´1 . 3 Assuming that the above are true, we will now see why our reduction is tight. Due to (1), the view of the adversary within the reduction will be indistinguishable from its view in the unforgeability game. Thus, it still wins within the reduction with probability close to in the game. Accordingly, we know that the reduction wins given that i˚ is in S. Hence, by (2) and (3), the reduction’s loss is only e´1 . We refer to Section 4 for the concrete security statement, with the advantage and running time of our reduction, and Section 6 for the formal proof. Case study: one-query adversary. We give an intuition why the properties (1)–(3) are satisfied by examining the simpler case of q “ 1. Specifically in this overview, we will consider a simplified transcript that omits the generators and the verification key4 and is of the form pm P Zp , e P Zp , S Ď t1uq . This is generated by (a) sampling f Ð$ Zdp rXs, β Ð$ Z˚p and er Ð$ Zp , (b) running the adversary who picks m, (c) selecting the tag e by finding the number of zeros of f pXq ` mβ as in the reduction, and (d) setting S as H if e is set to er and t1u otherwise. We will now show (1) and (2) by considering the probability of each possible transcript being generated for two main cases: S “ t1u and S “ H. First, consider the transcript of the form pm, e, S “ t1uq5 for any m, e P Zp . The corresponding event over the randomness f, β, er is “f pXq ` mβ has only e as its zero” (so that S “ t1u), or equivalently f ´1 p´mβq “ teu. Then, we calculate the probability of this event over the randomness as: (following a similar analysis from [Leo06] counting monic degree-d polynomials with no zeros in Zp ) ” ı Ť Prf,β,re rf ´1 p´mβq “ teus “ Pr pf peq “ ´mβq X ␣ e1 PZp zteu pf pe1 q “ ´mβq ” ı Ť “ Prrf peq “ ´mβs ´ Pr pf peq “ ´mβq X e1 PZp zteu pf pe1 q “ ´mβq ”Ť ı 1 “ p´1 ´ Pr e1 PZp zteu pf pe q “ f peq “ ´mβq ÿ “ ‰ “ p´1 ´ p´1q|T |´1 Pr @e1 P T Y teu : f pe1 q “ ´mβ H‰T ĎZp zteu

Ť The first equality follows from pf ´1 p´mβq “ teuq being equivalent to pf peq “ ´mβq X ␣ e1 PZp zteu pf pe1 q “ ´mβq (ruling out other preimages e1 ‰ e). The second to last equality follows because f is uniformly random. The last equality follows from the inclusion-exclusion principle. ś Here, the event @e1 P T Y teu : f pe1 q “ ´mβ is equivalent to writing f pXq ` mβ “ e1 PT Yteu pX ´ e1 q ¨ gpXq where g P Zp rXs is monic and deg g “ d ´ |T | ´ 1. Therefore, we have that # “ ‰ Pr @e1 P T Y teu : f pe1 q “ ´mβ “

3

p´|T |´1 0

|T | ď d ´ 1 . otherwise

We overload e with the tags ei P Zp and the real number e P R when clear from the context. Our formal proof analyzes the full transcript, which makes things slightly more complex. Here, we only present the core difficulties in the analysis of the distribution. 5 The notation p¨q denotes an actual value, and not a random variable. 4

5

Hence, we continue the calculation as ÿ ‰ “ p´1 ´ p´1q|T |´1 Pr @e1 P T Y teu : f pe1 q “ ´mβ H‰T ĎZp zteu d´1 ÿ

˙ p ´ 1 ´i´1 “p ´ p´1q p ; Counting subsets T Ď Zp zteu of size i i i“1 ˜ ¸ ˆ ˙ d´1 ÿ ´1 i p´1 ´i´1 “ lopomoon ¨ . p´1q p i i“0 Prre“es loooooooooooooooomoooooooooooooooon ´1

ˆ

i´1

PrrS“t1us

This clearly shows properties (1) and (2) with the two terms attributing to the probabilities of getting e and S “ t1u. Next, for transcripts of the form pm, e, S “ Hq, the corresponding event over the randomness is “|f ´1 p´mβq| ‰ 1 and er “ e.” Since f and er are independently sampled, we can write Prrr e “ es ¨ loooooooooooomoooooooooooon Prr|f ´1 p´mβq| ‰ 1s . Prf,β,re r|f ´1 p´mβq| ‰ 1 X er “ es “ loooomoooon Prre“es“p´1

PrrS“Hs

From the above analysis of both cases, properties (1) and (2) are satisfied. Finally, we show property (3), i.e., S “ t1u with probability roughly e´1 . In particular, the term PrrS “ t1us derived above can be estimated as ˆ ˙ ˆ ˙ ˆ ˙p´1 p´1 d´1 ÿ ÿ p ´ 1 ´i´1 p ´ 1 ´i´1 1 p´1qi p « p´1qi p “ 1´ « e´1 . i i p i“0 i“0 The first approximation follows when d is large enough, making the truncated terms relatively small. The equality follows from binomial expansion. The last approximation follows if p is large. This completes the 1-query case analysis. Generalizing to q queries. To extend our analysis to q-query adversaries, we make a crucial observation from the analysis above. In particular, we observe that the approximated value p1 ´ p1 qp´1 is exactly the probability of sampling a random function f : Zp Ñ Zp and for a fixed z P Zp , |f ´1 pzq| “ 1. This follows by counting the number of such f as follows: (1) pick the unique preimage e of z (p possible ways), (2) for e1 ‰ e, pick the image f pe1 q ‰ z (pp ´ 1qp´1 ways). For q-query adversaries, we can consider a simplified transcript of the form ppmi , ei qiPrqs , S Ď rqsq. For the probability of getting a particular transcript ppmi , ei qiPrqs , Sq, the corresponding event over the randomness ei qiPrqs is: f, β, pr ` ˘ ` ˘ @i P S : f ´1 p´mi βq “ tei u X @i R S : |f ´1 p´mi βq| ‰ 1 X eri “ ei . Our analysis then relies on the observed similarities between random polynomials and random functions Zp Ñ Zp on events regarding the number of preimages for any distinct elements z1 , . . . , zq (setting zi “ ´mi β in the analysis). Essentially, we show that for d “ Θpqq, any distinct z1 , . . . , zq and distinct e1 , . . . , eq ˇ „ ȷ ȷ „ @i P S : |f ´1 pzi q| “ 1 ˇˇ @i P S : |f ´1 pzi q| “ 1 @i P S : f pei q “ zi « Pr Pr . ´1 @i R S : |f ´1 pzi q| ‰ 1 ˇ pzi q| ‰ 1 f :Zp ÑZp @i R S : |f f Ð$ Zd p rXs This says that the extra conditioning on which preimage ei is used does not influence the distribution much. We abstract out the calculation of these probabilities and give our reduction with formal analysis in Sections 5 and 6, respectively. Finally, we remark that our strategy applies only when the messages m1 , . . . , mq are distinct; otherwise, two queries mi “ mj can be answered with the same ei “ ej with very high probability (and distinguishable from the original game). This limitation turns out to be inherent, and no tight reduction exists for the general case. We explain in the next section why such a loss cannot be avoided. 6

2.3

Impossibility of Tight Reductions for General Messages

For our impossibility results, let us consider the supposed “worst-case scenario” where all the signing queries are identical, and the adversary outputs a forgery with a tag e˚ “ ei for some i P rqs. From the sketched proof structure in Section 2.1, the reduction can be viewed as committing to polynomials f and g through the group elements G1 and H. Moreover, the tags e1 , . . . , eq should satisfy that pX ´ ei q divides f ` mi g. We can then categorize the tag ei as “useful” for a message mi when pX ´ ei q only divides f ` mi g but not f ` m1 g for any m1 ‰ mi ; such tags allow extracting the SDH solution. If an adversary can force only a small portion (say Op1q) of the tags to be useful and later forge using a uniformly random tag from e1 , . . . , eq , then the reduction can reliably extract the SDH solution only with Op1{qq probability, leading to a Opqq loss. Our key observation is that for any fixed polynomials f and g, no tag e can be useful for two messages m ‰ m1 (i.e., if pX ´ eq divides f ` mg but not f ` m1 g for m1 ‰ m, e cannot be useful for m1 ). Hence, for a uniformly random message m Ð$ Zp , there exists at most one useful tag on average. Therefore, if an adversary makes q identical signing queries on a random m and forges using a tag ei for a random i Ð$ rqs, the reduction can only find a SDH solution with 1{q probability. Otherwise, the reduction has to output a tag ei such that pX ´ ei q ffl f ` mg, in which case it inherently breaks the SDH assumption. In Section 7, we formalize the sketched intuition as a meta-reduction against any algebraic reductions (i.e., it outputs group elements along with their algebraic representations). We also extend the impossibility to: (a) reductions to variants of the SDH assumption, (b) general verification key vk (this overview assumes vk “ X2,1 taken from the SDH instance), (c) rewinding reductions (a reduction running the adversary r times incurs at least Θpq{r2 q factor loss), and (d) fine-grained adversaries making queries on at least k ă q distinct messages.

3

Preliminaries

Notations. Let rn..ms “ tn, n ` 1, . . . , mu for any n, m P Z where n ď m and rns “ r1..ns for any n ě 1. We ⃗ use λ as the security parameter, denote vectors with the arrow symbols ¯ (e.g., ⃗v , H), write ⃗vS for the subvector śl´1 ´ pp´aq! pvi qiPS of ⃗v . We define an error factor Erpa, l; pq :“ k“0 1 ´ a`k “ p´l ¨ pp´a´lq! (used repeatedly in our p proofs) for integers p ě a, l ě 0. For boolean-or and boolean-and, we use the operators Y and X, respectively. Polynomials. We denote formal variables with sans-serif letters (e.g., X, Y). For any prime modulus p, let řd Zp rXs (and Zdp rXs) denote the ring of (monic degree-d) polynomials gpXq “ i“0 ai Xi with coefficients in Zp and deg g “ d as the degree of gpXq. We often refer to gpXq using the shorthand g. Denote rootpf q :“ tα P Zp : f pαq “ 0u as the set (not a multiset) of zeros of f P Zp rXs. We refer to the notation as a set and not a multiset; accordingly, if pX ´ aq2 |f pXq, we still count α as one zero. Bilinear pairing groups. For any group G with prime-order p, we write 0G as the identity element, G˚ as the set of generators of G, and group elements and scalars with upper- and lower- case letters, respectively. We adopt additive notations. For G P G˚ and H P G, we use DLG pHq P Zp as the discrete logarithm of H base G. A bilinear group parameter generator is a probabilistic algorithm GGen with input 1λ and output pp, G1 , G2 , GT , eq. Here, G1 , G2 and GT are groups of λ-bit prime order p, and e : G1 ˆ G2 Ñ GT is a bilinear map satisfying (1) bilinearity, i.e., for any A P G1 , B P G2 and x, y P Zp , e pxA, yBq “ pxyq ¨ e pA, Bq, and (2) non-triviality, i.e., for any G1 P G˚1 , G2 P G˚2 , e pG1 , G2 q P G˚T . Signature schemes. A digital signature scheme SS is a tuple of algorithms pSS.Setup, SS.KG, SS.Sign, SS.Verq with the following syntax: λ ‚ The setup algorithm SS.Setupp1 q generates public parameters par which are implicit inputs to all other algorithms and also define the message space SS.M “ SS.Mpparq. The key generation algorithm SS.KGpq outputs the signing and verification keys psk, vkq. ‚ The (possibly randomized) signing algorithm SS.Signpsk, mq takes as inputs, the signing key sk and a message m P SS.M, and outputs a signature σ. ‚ The deterministic verification algorithm outputs a bit SS.Verpvk, m, σq. 7

Game SUFA SS pλq:

Oracle Spmq: λ

Sigs Ð H ; par Ð$ SS.Setupp1 q

σ Ð$ SS.Signpsk, mq

psk, vkq Ð$ SS.KGpq

if σ ‰ K then

˚

˚

Sigs Ð Sigs Y tpm, σqu

S

pm , σ q Ð$ A ppar, vkq ˚

˚

˚

˚

return pm , σ q R Sigs X SS.Verpvk, m , σ q “ 1

return σ

Fig. 1. Strong unforgeability game Game pd1 , d2 q-SDHA GGen pλq:

Game pd1 , d2 q-DLA GGen pλq: λ

λ

par “ pp, G1 , G2 , GT , eq Ð$ GGenp1 q

par “ pp, G1 , G2 , GT , eq Ð$ GGenp1 q

˚ ˚ G1 Ð$ G1 ; G2 Ð$ G2 ; x Ð$ Zp

˚ ˚ G1 Ð$ G1 ; G2 Ð$ G2 ; x Ð$ Zp

i

i

1

i

i

pe, Zq Ð$ Appar, G1 , px G1 qiPrd1 s , G2 , px G2 qiPrd2 s q x Ð$ Appar, G1 , px G1 qiPrd1 s , G2 , px G2 qiPrd2 s q ¯ ´ 1 1 return px “ x q return Z “ x`e G1

Fig. 2. Games pd1 , d2 q-SDH and pd1 , d2 q-DL

Correctness says that for any public parameters par and key pair psk, vkq generated from the setup and key generation algorithms and any message m P M, the signature σ Ð$ SS.Signpsk, mq always satisfies SS.Verpvk, m, σq “ 1. We consider strong unforgeability security, defined by the game SUFA SS pλq (given in Figure 1), and for any adversary A, its advantage is A Advsuf SS pA, λq :“ PrrSUFSS pλq “ 1s .

Security assumptions. We use the pd1 , d2 q-Strong Diffie-Hellman (pd1 , d2 q-SDH) assumption in a format supporting type-3 pairings. This generalizes the q-SDH assumption defined by Boneh and Boyen [BB08], obtained by setting d1 “ q and d2 “ 1. We also consider the pd1 , d2 q–Discrete Logarithm (pd1 , d2 q-DL) [Lip12] assumption, which is implied by the pd1 , d2 q-SDH assumption. We simply refer to p1, 1q-DL as the Discrete Logarithm (DL) assumption. The corresponding games pd1 , d2 q-pSDH{DLq are formalized in Figure 2, and the corresponding advantages for any adversary A are pd ,d q-psdh{dlq

1 2 AdvGGen

pA, λq “ Prrpd1 , d2 q-pSDH{DLqA GGen pλq “ 1s .

Remark 3.1. Our security proofs will rely on the observation (due to Boneh and Boyen [BB08]) that, given pxq group elements pxi G1 qiPr0,ds and A “ fx´e G1 for any f P Zp rXs of degree at most d and a scalar e ‰ x, 1 if f peq ‰ 0, one can efficiently compute a d-SDH solution p´e, x´e G1 q. Due to the polynomial remainder r qG1 . theorem, we can write f pXq “ gpXqpX´eq`r where r “ f peq ‰ 0 and deg g ď d´1. Thus, A “ pgpxq` x´e Then, the solution 1 A ´ gpxqG1 G1 “ , x´e r is efficiently computable, as gpxqG1 can be computed from the given inputs. Algebraic group model (AGM). Our impossibility results on tightness require the AGM. We assume that the reductions are algebraic [FKL18], i.e., when outputting a group element, it also provides the representation as a linear combination of previously seen group elements to the meta-reduction. Useful inequalities. We recall several useful inequalities. The first one, which is used throughout the paper, is due to Bonferroni’s giving upper and lower bounds for probability of union of sets/events through the inclusion-exclusion principle. The second is a lower bound on factorials due to Sterling’s approximation. The third lemma follows from calculus and implies the fourth lemma. 8

Algorithm BBS.Setupp1λ q :

Algorithm BBS.Signpsk “ x, m ⃗ P Zℓp q : ´ ¯ ř 1 ⃗ e Ð$ Zp ; A Ð x´e G1 ` ℓi“1 mris ⃗ Hris

λ

pp, G1 , G2 , GT , eq Ð$ GGenp1 q ˚ ˚ ⃗ Ð$ Gℓ G1 Ð$ G1 ; G2 Ð$ G2 ; H 1

return pA, eq ⃗ G2 , G1 , G2 , GT , eq Algorithm BBS.Verpvk, m, return par Ð pp, G1 , H, ⃗ σ “ pA, eqq :

Algorithm BBS.KGpq : C Ð G1 `

⃗

řℓ

⃗ Hris i“1 mris

return e pA, vk ´ eG2 q “ e pC, G2 q

x Ð$ Zp return psk Ð x, vk Ð xG2 q

Fig. 3. Signature scheme BBS “ BBSrGGen, ℓs.

Lemma 3.2. For subsets A1 , . . . , An Ď U of some universe U, let 1 ď K ď n be an even integer and Pr denotes Pru Ð$ U . Then, » fi « ff « ff ÿ č ď ÿ č |B|´1 |B|´1 p´1q Pr Ai ď Pr – Ai fl “ p´1q Pr Ai iPB

BĎrns: 1ď|B|ďK

iPrns

iPB

H‰BĎrns

« ÿ ď

|B|´1

p´1q

Ai

.

iPB

BĎrns: 1ď|B|ďK`1

Lemma 3.3. For positive integer k, k! ě

Pr

ff č

` k ˘k e

x Lemma 3.4. For any real x, 1 ` x ď ex . For any x ą ´1, lnp1 ` xq ě 1`x .

Proof. The second inequality follows by substituting x “ ´ lnp1 ` xq (which is well-defined for x ą ´1) into the first inequality, giving x 1 ðñ lnp1 ` xq ě . 1`x 1`x ´ ¯p´k p´k Lemma 3.5. For real numbers 0 ă l, k ă p, 1 ´ pl ě e´l¨ p´l . 1 ´ lnp1 ` xq ď

\ [

Proof. By setting x “ ´ pl in Lemma 3.4, we have ˆ

l 1´ p

˙p´k

´l{p

l

p´k

“ epp´kq¨lnp1´ p q ě epp´kq¨ln 1´l{p “ e´l¨ p´l .

\ [

BBS signatures. The signature scheme BBS “ BBSrGGen, ℓs in Figure 3 is parameterized by a group parameter generatorGGen and the message length ℓ ě 1. We make a syntactical change replacing px ` eq with px ´ eq. This is for readability since we can write e as zero of some polynomial f if pX ´ eq|f instead of ´e. When x ´ e “ 0, we denote 1{0 “ 0, following the notations in [TZ23]. We also consider derandomized BBS, denoted DBBS “ DBBSrGGen, ℓ, PRFs where e is derived by evaluating the pseudorandom function PRF on m ⃗ and the PRF key that is sampled at key generation.

4

Tight Security Proofs of BBS Signatures

In this section, we state our tight security guarantees for BBS signatures against adversaries with distinct signing queries in Section 4.1 and discuss our reduction running time in Section 4.2. 9

Game SUF1 A BBS pλq:

Oracle Spm ⃗ P Zℓp q: λ

Sigs, Tags Ð H ; par Ð$ BBS.Setupp1 q

σ “ pA, eq Ð$ BBS.Signpsk, mq ⃗

psk, vkq Ð$ BBS.KGpq

Sigs Ð Sigs Y tpm, ⃗ σqu

˚

pm ⃗ ,σ

˚

˚

˚

S

“ pA , e qq Ð$ A ppar, vkq

Tags Ð Tags Y teu

˚ ˚ ˚ ˚ return pm ⃗ , σ q R Sigs X e˚ P Tags X BBS.Verpvk, m ⃗ , σ q “ 1 return σ

Fig. 4. Game SUF1 for BBS “ BBSrGGen, ℓs.

4.1

Tight Concrete Security of BBS Signatures

The following theorem establishes the tight SUF security of BBS signatures under the d-SDH assumption (with d “ Θpq ` λq) against adversaries making q distinct signing queries. It also implies tight security for DBBS “ DBBSrGGen, ℓ, PRFs by additionally assuming the security of PRF. Theorem 4.1. Let GGen be a group parameter generator outputting bilinear groups of prime-order p “ ppλq, ℓ “ ℓpλq, BBS “ BBSrGGen, ℓs, and TG “ TG pλq, Tp “ Tp pλq be the running time for group exponentiation and field operation in Zp , respectively. For any SUF adversary A making at most q “ qpλq distinct signing queries with running time tA “ tA pλq, there exist adversaries B1 , B2 , B3 , BBadQ , and BColl such that for d1 “ rpe2 ` 2qq ` 2 log2 ps ` 1, 1

d -sdh dl dl Advsuf BBS pA, λq ď e ¨ AdvGGen pB1 , λq ` AdvGGen pBColl , λq ` AdvGGen pBBadQ , λq q-sdh ` Advdl GGen pB2 , λq ` AdvGGen pB3 , λq `

p4e ` 1qq2 ` p8e ` 2qq ` 2e ` 6 . 2p

Also, B1 and B3 run in time roughly tA ` Opq2 plog2 q log2 p ` TG ` Tp qq and tA ` Opq2 pTG ` Tp qq, respectively; B2 , BBadQ and BColl run in time roughly tA . We concretely specify the additive term in the reduction’s running time in contrast to the prior works giving security proofs for BBS signatures [ASMC13, Sch15, CDL16, TZ23] and note that the additive running time of Opq2 plog2 q log p ` TG ` Tp qq might not lead to a totally tight reduction. For example, an adversary A may only ask queries, so that tA « q ¨ polypλq ! q2 ¨ polypλq. However realistically, the concrete number of signing queries, which are online interactions, are relatively small compared to offline computations done r 2 q. More importantly, similar additive by the adversary. As a result, we can mildly assume that tA ě Ωpq 2 terms depending on q also appear in prior works [Gen06, ASMC13, CDL16, Sch15, TZ23] on tight security reductions to q-type assumptions, and especially for BBS/BBS+ signatures. We further discuss why such terms appear in Section 4.2. The following lemma shows that the SUF security of BBS is implied tightly by the SUF1 security of BBS formalized in Figure 4. The SUF1 security is a special case for the security analysis of BBS in [TZ23] where the forgery contains e˚ which is already output by the signing oracle. We do not give a proof of Lemma 4.2 as it immediately follows from the proof of [TZ23, Theorem 1] by abstracting out the specific case where the previous reduction incurs a q factor in security loss. Lemma 4.2. Let GGen, p, TG , Tp , BBS be as in Theorem 4.1. For any SUF adversary A making q “ qpλq signing queries with running time tA “ tA pλq, there exist adversaries B1 , B2 , B3 such that 1

q-SDH suf dl Advsuf BBS pA, λq ď AdvBBS pB1 , λq ` AdvGGen pB2 , λq ` AdvGGen pB3 q `

q2 ` 2q ` 4 . 2p

Also, B1 runs in time roughly tA and makes at most q queries to its signing oracle; B2 and B3 runs in time roughly tA and tA ` Opq2 pTG ` Tp qq, respectively. 10

We now establish the tight SUF1 security of BBS against adversaries making distinct signing queries via the two following lemmas, which combined with the above imply Theorem 4.1. Lemma 4.3 tightly reduces SUF1 security for arbitrary length ℓ ě 1 messages to SUF1 security for length-1. Lemma 4.4 is our core technical lemma establishing the tight security of SUF1 for length-1 messages. Lemma 4.3. Let GGen, p, TG , Tp , BBS be as in Theorem 4.1, and BBS1 “ BBSrGGen, 1s. For any adversary A making at most q “ qpλq distinct signing queries with running time tA “ tA pλq, there exist adversaries B 1 and BColl running in time roughly tA such that 1

1

suf dl 1 Advsuf BBS pA, λq ď AdvBBS1 pB , λq ` AdvGGen pBColl , λq .

Moreover, B 1 makes at most q distinct signing queries. ⃗ The proof in Section A simply sets up the public parameters Hrjs Ð αj H 1 for αj Ð$ Zp (the reduction řℓ 1 ⃗ receives H and outputs Hrjs) and convert a length ℓ message m ⃗ to m “ j“1 αj mrjs. ⃗ Additionally, we rule řℓ 1 out the event where two messages m ⃗ ‰m ⃗ maps to the same message via the map m ⃗ ÞÑ j“1 αj mrjs, ⃗ which řℓ řℓ 1 ⃗ ⃗ implies a collision mrjs ⃗ Hrjs “ m ⃗ rjsHrjs breaking DL. j“1

j“1

Lemma 4.4. Let GGen, p, TG , Tp , BBS1 be as in Lemma 4.3. For any adversary A making at most q “ qpλq distinct signing queries with running time tA “ tA pλq, there exist adversaries B1 and BBadQ such that, 1

1

dl d -sdh Advsuf BBS1 pA, λq ď e ¨ AdvGGen pB1 , λq ` AdvGGen pBBadQ , λq `

e ¨ p2q2 ` 4q ` 1q , p

where d1 “ rpe2 ` 2qq ` 2 log2 ps ` 1. Moreover, B1 runs in time roughly tA ` Opq2 plog2 q log2 p ` TG ` Tp qq, and BBadQ runs in time roughly tA . The proof in Section 6 will rely heavily on the toolkit on statistical properties of random functions and random polynomials established in Section 5. 4.2

Discussion on the Reduction’s Running Time

r 2 q additive loss in our reduction’s runtime also appears in prior works. The As mentioned earlier, the Opq security reduction to q-ABDHE assumption of Gentry’s IBE [Gen06] requires additional Opq2 ¨ TG q where TG “ TG pλq denotes running time for group exponentiation to compute group elements for the challenge queries. Similarly, the prior tight reductions for BBS/BBS+ [ASMC13, CDL16, Sch15, TZ23] also has Opq2 ¨ pTG ` Tp qq additive term arising from computing for each signing query, the group element Ai from the SDH instance and the underlying polynomial that represents Ai . Possible optimization. Only for certain bilinear groups (e.g., ones where p ´ 1 is divisible by a large enough power-of-two d), there exists an algorithm, due to [GHO20, FK23] to precompute openings for KZG polynomial commitments [KZG10] in Opd log2 d ¨ TG q at ď d points where d is the degree of the committed polynomial and d|pp ´ 1q. This particular algorithm can be adapted to the reductions for BBS to precompute the group elements Ai in the signatures faster than Opq2 q time. In particular, we can view the two group elements G1 and H that the reduction outputs as KZG polynomial commitments to two polynomials f and g. (Recall the reduction structure in Section 2.) Then, the reduction can do the following: ‚ Setup f, g and G1 Ð f pxqG1 , H Ð gpxqG1 . ‚ Assuming that the tags e1 , . . . , eq are known beforehand, the reduction uses the mentioned algorithm to precompute the KZG openings Bi for the evaluation f pei q and Bi1 for the evaluation gpei q. For all i P rqs, the following equations are then satisfied by the precomputed values ` ˘ e G1 ´ f pei qG1 , G2 “ e pBi , X2,1 ´ ei G2 q , ` ˘ ` ˘ e H ´ gpei qG1 , G2 “ e Bi1 , X2,1 ´ ei G2 11

‚

Since it is ensured that f pei q ` mi gpei q “ 0 by how the reduction is structured, we have that Ai “ Bi ` mi Bi1 satisfies ` ˘ e pAi , X2,1 ´ ei G2 q “ e Bi ` mi Bi1 , X2,1 ´ ei G2 ˘ ` “ e G1 ` mi H ´ pf pei q ` mi gpei qqG1 , G2 ˘ ` “ e G1 ` mi H, G2 .

It is easy to see that the above sketched algorithm’s runtime is dominated by the second step. This optimization directly applies to all prior reductions due to the tags being known beforehand. In the case of the standard model reduction in [TZ23], q ´ 1 of the tags ei are already known beforehand (meaning the precomputation can be done for those tags). For the only query where ei is not known beforehand, naively computing Ai incurs only additive OpqpTG ` Tp qq running time and does not change the asymptotic runtime. This optimization, unfortunately, does not apply to our tight reduction as it does not know most of the ei ’s in advance. In particular, we can precompute the Ai ’s for when ei “ eri , but not for ei ’s derived from the unique zero. More importantly, because our analysis shows that the number of indices i such that ei ‰ eri is on average « q{e, this optimization does not quite apply. Still, we stress again that this optimization only works for certain classes of bilinear groups.

5

Probability Toolkit for the Tight Reductions

In this section, we introduce a toolkit for statistical properties that are heavily used by the analysis of our tight reduction in Section 6. In particular, we consider certain properties regarding number of preimages for arbitrarily fixed elements of random functions (in Section 5.1) and relate them to similar properties of random high-degree polynomials (in Section 5.2). We suggest that the readers first go through the proof in Section 6 to see how these derived properties are relevant to the analysis and refer back to this section when they are invoked. 5.1

Probability Toolkit from Random Functions

In this section, we consider the distribution of a certain set S sampled with respect to certain properties of a random function f : Zp Ñ Zp . Looking ahead in Section 6, we will augment the SUF1 game’s transcript with the set S independently sampled from this distribution. Then, we show that the distribution of this augmented transcript is indistinguishable from the transcript between our reduction and the adversary. There, S is defined according to the reduction strategy using a random polynomial, of which the relevant probabilities are considered in Section 5.2. Importantly, our security proof will not explicitly consider random functions but only refer to the properties of S derived in this section. For any distinct values z0 , z1 , . . . , zq P Zp and x P Zp , we will consider the distribution of the set S Ď rqs defined by the following experiment: 1. Sample a random function f : Zp Ñ Zp conditioned on f pxq “ z0 . 2. Set S :“ ti P rqs : |f ´1 pzi q| “ 1u. Here, the extra conditioning comes from the fact that our reduction will embed f pxq in one of the generators with x being the discrete logarithm of the SDH instance. This further constrains the distribution of S defined in the reduction. The following lemma, proved in Section 5.3, describes the probability density function of S, denoted η. Lemma 5.1. Let F be the family of all functions Zp Ñ Zp , z0 , z1 , . . . , zq P Zp be any distinct values and x P Zp . For any S Ď rqs, define ηpSq :“ Prf Ð$ F rp@i P S : |f ´1 pzi q| “ 1q X p@i R S : |f ´1 pzi q| ‰ 1q | f pxq “ z0 s . ř Accordingly, SĎrqs ηpSq “ 1 and ηpSq ě 0 for all S Ď rqs. Moreover, ηpSq “

q´|S| ÿ i“0

ˆ p´1qi

˙ ˆ ˙p´|S|´i´1 q ´ |S| |S| ` i Erp1, |S| ` i; pq 1 ´ . i p 12

(1)

We write the probability as ηpSq since its value is independence of the choices of z0 , z1 , . . . , zq and x. This means that for any z0 , z1 , . . . , zq distinct and x, if one sample the set S according to the above experiment, the distribution of S is independent of the choices of zi ’s and x. The proof given in Section 5.3 is roughly as follows: (1) observe that @i R S : |f ´1 pzi q| ‰ 1 is the negation of Di R S : |f ´1 pzi q| “ 1, (2) break the probability calculation down via the inclusion-exclusion principle, and (3) this finally boils down to computing the probability for some T Ď rqs that @i P T : |f ´1 pzi q| “ 1. Next, the following corollaries establish lower bounds on specific probabilities regarding a sampled set S. The first corollary will be used to show that our reduction has a constant factor loss of e in security. The second corollary will be used in Section 5.5 to relate the distribution of S defined with respect to random polynomials as in our reduction to the distribution of S sampled according to η. Corollary 5.2. For any i˚ P rqs, PrS Ð$ η ri˚ P Ss ě e´1 . Proof. Let z0 , z1 , . . . , zq P Zp be distinct and x P Zp as in Lemma 5.1. Consider ˆ PrS Ð$ η ri˚ P Ss “ Prr|f ´1 pzi˚ q| “ 1 | f pxq “ z0 s “

1´

1 p

˙p´1 ě e´1 .

The first equality follows from definition of S as the set of indices i P rqs where zi has only one preimage. The second follows from a counting argument: (1) pick a preimage of zi˚ that is not x and (2) pick images of other elements in the domain. The last inequality follows from Lemma 3.5 setting k “ l “ 1. [ \ ´ ¯p´|S|´1 ¨ Erp1, |S|; pq. Corollary 5.3. For any S Ď rqs, ηpSq ě 1 ´ pq Proof. First, we recall the definition of η ηpSq :“ Prf Ð$ F rp@i P S : |f ´1 pzi q| “ 1q X p@i R S : |f ´1 pzi q| ‰ 1q | f pxq “ z0 s ě Prrp@i P S : |f ´1 pzi q| “ 1q X p@i R S : |f ´1 pzi q| “ 0q | f pxq “ z0 s ˙p´|S|´1 ˆ q “ 1´ ¨ Erp1, |S|; pq . p The first inequality follows from |f ´1 pzi q| “ 0 implying |f ´1 pzi q| ‰ 1. The last equality follows from the following counting argument and dividing by pp´1 (i.e., the number of f P F such that f pxq “ z0 ): ‚ Count number of ways to assign unique preimages of zi : For each i P S, we can assign distinct ei ‰ x such that f pei q “ zi . In particular, this corresponds to selecting a vector pei qiPS with distinct elements, i.e., there are pp ´ 1q!{pp ´ |S| ´ 1q! such vectors. ‚ Count number of ways to assign images to the non-selected elements in Zp : For each e P Zp zptxuYtei uiPS q, we select f peq to be any value in Zp except for tzi uiPrqs , since we already fixed all the preimages of these values. Hence, there are exactly pp ´ qqp´|S|´1 ways to assign these images. [ \ 5.2

Probability Toolkit from Random Polynomials

In this section, we consider the distribution of the set S Ď rqs sampled according to our reduction strategy in Section 6 based on a random polynomial of large enough degree d. The following lemma, which is proved in Section 5.5 and is the key to our reduction’s analysis, establishes the probability that a random monic polynomial f of degree d “ Θpqq satisfies the following constraints for any distinct z0 , z1 , . . . , zq , a set S Ď rqs, and distinct x, pei qiPS : (a) for i R S, the number of preimages of zi with respect to the function f is not 1, and (b) for i P S, zi has ei as its only preimage. Note that f ´1 pzq “ rootpf pXq ´ zq, of which the notation is used throughout the paper. As a connection to Section 5.1, the lemma shows the probability lower bound of sampling an f that leads to a particular set S with extra constraints on specific preimages of zi for i P S (hence, the p´|S| factor). This relates the probability of sampling a specific transcript based on the reduction’s simulation and the transcript in the SUF1 game. 13

Lemma 5.4. Let d “ rpe2 ` 1qq ` 2 log2 ps ` 1, p ě 2q2 , S Ď rqs, z0 , z1 , . . . , zq P Zp be distinct values, and 2 |S| x P Zp , pei qiPS P Zp also be distinct values. Then, with ε “ e´pe ´3qq´log2 p`1 ă p´1 , „ Prf Ð$ Zdp rXs

ȷ f pxq “ z0 X @i R S : |f ´1 pzi q| ‰ 1 ě p1 ´ εq ¨ p´1´|S| ηpSq . X @i P S : f ´1 pzi q “ tei u

We stress that the lemma does not immediately follow from the fact that a random degree-d polynomial f is a d-wise independent function (i.e., for d distinct points, the evaluations of f is uniformly random). Indeed, the particular event we consider is global, in that reasoning about the (size of) set of preimages introduce constraints to all values in the domain. For example, fixing f to have only e P Zp mapping to z P Zp means that for all e1 ‰ e, we require f pe1 q ‰ z. If f is a uniformly random function Zp Ñ Zp instead of degree-d polynomials, the corresponding probability as defined in the lemma is exactly p´|S|´1 ¨ Erp1, |S|; pq´1 ηpSq.6 For random degree-d polynomial f , we can also show that the probability is within p1 ˘ εq factor of this mentioned value, but we only state the relevant lower bound required by our security proof later on.

5.3

Proof of Lemma 5.1

As an overview, we will simplify the calculation of the probability by defining placeholder events and apply the inclusion-exclusion principle so that the events Ş can be easily analyzed. For readability, we first define the events Bi :“ |f ´1 pzi q| “ 1 for i P rqs, and A :“ iPS Bi . Then, we can write the the event defining ηpSq as: ¨ p@i P S : |f ´1 pzi q| “ 1q X p@i R S : |f ´1 pzi q| ‰ 1q “ A X ˝

˛ č

¨

␣Bi ‚ “ A X ␣ ˝

iPrqszS

˛ ď

Bi ‚ .

iPrqszS

The first equality follows from ␣Bi “ |f ´1 pzi q| ‰ 1. Hence, we have that ¨ » ˛ˇ fi ˇ ď ˇ Bi ‚ ˇˇ f pxq “ z0 fl ηpSq “ Prf Ð$ F –A X ␣ ˝ ˇ iPrqszS ¨ » ˛ˇ fi ˇ ď ˇ “ PrrA | f pxq “ z0 s ´ Pr –A X ˝ Bi ‚ ˇˇ f pxq “ z0 fl ˇ iPrqszS ˇ » fi ˇ ď ˇ “ PrrA | f pxq “ z0 s ´ Pr – pA X Bi q ˇˇ f pxq “ z0 fl . ˇ iPrqszS Ť Next, by inclusion-exclusion principle, we can compute the probability of the event iPrqszS pA X Bi q, as the following alternating sum ˇ » fi ˇ « ff ˇ ˇ ď ÿ č ˇ ˇ |T |´1 Pr – pA X Bi q ˇˇ f pxq “ z0 fl “ p´1q Pr pA X Bi q ˇ f pxq “ z0 ˇ ˇ iPT iPrqszS H‰T ĎrqszS ˇ « ff ˇ ÿ č ˇ |T |´1 “ p´1q Pr A X Bi ˇ f pxq “ z0 . ˇ iPT H‰T ĎrqszS

6

The error term stems from the additional constraints f pei q “ zi for all i P S.

14

Note that A “ A X

Ş

iPH Bi , meaning we can also write ηpSq as

ˇ ˇ ff « ff ˇ ˇ ÿ č ˇ ˇ Bi ˇ f pxq “ z0 ηpSq “ Pr A X Bi ˇ f pxq “ z0 ´ p´1q|T |´1 Pr A X ˇ ˇ iPT iPH H‰T ĎrqszS ˇ « ff ˇ ÿ č ˇ Bi ˇ f pxq “ z0 . “ p´1q|T | Pr A X ˇ iPT «

č

T ĎrqszS

|T |´1 The second equality follows from “ p´1q|T | . Now, we state the following lemma which determines Ş ´p´1q the exact probability of A X iPT Bi . The proof is in Section 5.4.

Lemma 5.5. For any distinct z0 , z1 , . . . , zq P Zp , x P Zp , and S 1 Ď rqs, let l “ |S 1 | ď q, then ˆ ˇ “ ‰ Prf Ð$ F @i P S 1 : |f ´1 pzi q| “ 1 ˇ f pxq “ z0 “

1´

l p

˙p´l´1 ¨ Erp1, l; pq .

By substituting in the terms and setting S 1 “ S Y T to the lemma statement, we have that ˇ « ff ˇ č ˇ Pr A X Bi ˇ f pxq “ z0 “ Prr@i P S Y T : |f ´1 pzi q| “ 1 | f pxq “ z0 s ˇ iPT ˙p´|S|´|T |´1 ˆ |S| ` |T | ¨ Erp1, |S| ` |T |; pq . “ 1´ p Then, notice that PrrA X

(2)

Ş

iPT Bi | f pxq “ z0 s only depends the size of S and T , meaning we can write

ˇ ff ˇ ˇ Pr A X Bi ˇ f pxq “ z0 ˇ iPT «

ÿ

ηpSq “

|T |

p´1q T ĎrqszS

č

ˆ ÿ “

|T |

p´1q T ĎrqszS q´|S| ÿ

“ i“0

ˆ p´1qi

|S| ` |T | 1´ p

˙p´|S|´|T |´1 ¨ Erp1, |S| ` |T |; pq

˙ˆ ˙p´|S|´i´1 |S| ` i q ´ |S| 1´ Erp1, |S| ` i; pq . i p

The second equality follows from Equation (2). The third equality follows by replacing each size |T | with i and counting all subsets T Ď rqszS of size i ě 1. [ \ 5.4

Proof of Lemma 5.5

We note first that there are exactly pp´1 functions f P F such that f pxq “ z0 . Then, we will now count the number of functions f P F such that for all i P S 1 , |f ´1 pzi q| “ 1, which is done in the following steps: 1. Count number of ways to assign unique preimages of zi : For each i P S 1 , we can assign distinct ei ‰ x such that f pei q “ zi . In particular, this correspond to selecting a vector pei qiPS 1 of length l “ |S 1 | with distinct elements, i.e., there are pp ´ 1q!{pp ´ l ´ 1q! such vectors. 2. Count number of ways to assign images to the non-selected elements in Zp : For each e P Zp zptxu Y tei uiPS 1 q, we can select f peq to be any value in Zp except for tzi uiPS 1 , since we constrained the number of preimages for these values to 1. Hence, there are exactly pp ´ lqp´l´1 ways to assign these images. 15

Combining the two steps and dividing by pp´1 , we have that pp ´ 1q! ¨ pp ´ lqp´l´1 pp ´ l ´ 1q! ˆ ˙p´l´1 l ¨ Erp1, l; pq . “ 1´ p

ˇ “ ‰ Prf Ð$ F @i P S 1 : |f ´1 pzi q| “ 1 ˇ f pxq “ z0 “ p´p`1 ¨

pp´1q! The equality follows from the definition of Erp1, l; pq “ p´l ¨ pp´l´1q! .

5.5

[ \

Proof of Lemma 5.4

Let pz0 , ⃗z, S, x, pei qiPS q be as in the lemma statement with S Ď rqs, z0 , . . . , zq distinct, and x, pei qiPS distinct. To prove the lemma and for readability, we first define for each i P rqs, the events D and Ei as D :“ f pxq “ z0 X p@i P S : f ´1 pzi q “ tei uq; ,

Ei :“ |f ´1 pzi q| “ 1 .

Then, we rewrite our desired probability (which we will denote as F ) as „ ȷ f pxq “ z0 X @i R S : |f ´1 pzi q| ‰ 1 F :“ Prf Ð$ Zdp rXs X @i P S : f ´1 pzi q “ tei u fi » J ď Ei fl “ Pr –D jPrqszS

» “ Pr –D

fi J ď

pD X Ej qfl

jPrqszS

»

fi ď

“ PrrDs ´ Pr –

pD X Ei qfl .

jPrqszS

Next, we apply the principle of inclusion-exclusion (Lemma 3.2)to compute the probability of Ei q as ”Ť ı ř ”Ş ı |T |`1 Pr Pr jPrqszS pD X Ei q “ jPT pD X Ej q . H‰T ĎrqszS p´1q Ş Also, notice that D “ jPH pD X Ej q, meaning « F “

ÿ

|T |

p´1q

Pr

č

pD X Ej q “ D X

č

We now compute PrrD X

Ş

jPT

GT,pe1i qiPT

jPrqszS pD X

ff č

pD X Ej q

.

(3)

jPT

T ĎrqszS

Note that by definition, we can write the event

Ť

Ş

jPT pD

X Ej q as

` ˘ Ej “ f pxq “ z0 X @j P T : |f ´1 pzj q| “ 1 X @j P S : f ´1 pzj q “ tej u .

jPT jPT Ej s. We observe that this event can be partitioned into p

|T |

disjoint events,

|T | for pe1i qiPT P Zp defined as

` ˘ GT,pe1i qiPT :“ f pxq “ z0 X @j P T : f ´1 pzj q “ te1j u X @j P S : f ´1 pzj q “ tej u . Ş 1 Note that the event GT,pe all GT,pe1i qiPT is a subset Ş Ş i qiPT partitions D X jPT Ej because (1) by definition, of (i.e., implies) D X jPT Ej , (2) the union of all GT,pe1i qiPT contains D X jPT Ej since each of the sets 16

explains what the only zero of f pXq ´ zj “ 0 could be, and (3) GT,pe1i qiPT and GT,pe2i qiPT for pe1i qiPT ‰ pe2i qiPT are disjoint as no function can have two “unique preimages”–i.e., f ´1 pzj q “ te1j u “ te2j u for e1j ‰ e2j for some j P T , which is clearly a contradiction. Also, for pe1i P Zp qiPT , PrrGT,pe1i qiPT s “ 0 if one of the following is true: (a) For some i P T, j P S, e1i “ ej or (b) For some i P T, x “ e1i , or (c) For some i ‰ j P T , e1i “ e1j . The reasoning is as follows. If (a) occurs, zi “ f pe1i q “ f pej q “ zj , a contradiction as zi ‰ zj . If (b) occurs, z0 “ f pxq “ f pe1i q “ zi , also a contradiction since zi ‰ z0 . If (c) occurs, zi “ zj , which is again a contradiction. Hence, we can write « ff ÿ č PrrGT,pe1i qiPT s . Pr pD X Ej q “ pe1i qiPT distinct and not overlap with tei uiPS Ytxu

jPT

We will now bound the probability of the event GT,pe1i qiPT via the following lemma, proved in Section 5.6. In particular, it is a special case of Lemma 5.4 where we do not consider the constraints that for i R S, the ´ ¯p´|S|´1 number of preimages of zi is not 1. We note that the term p´|S|´1 1 ´ |S| is exactly the probability p over a random function f such that f pxq “ z0 and for each j P S, zj has only one preimage being ej — drawing comparison to Lemma 5.5 (with extra constraints on which elements are the preimages). The proof ´ ¯p´|S|´1 idea is that in the binomial expansion of 1 ´ |S| , the terms after a large enough d will be very p small relative to the overall value; hence, the multiplicative error ε. The formal proof follows similar (but more complex) counting argument as in Section 2 relying on the inclusion-exclusion principle. Lemma 5.6. Let d “ rpe2 ` 1qq ` 2 log2 ps ` 1, S Ď rqs, x, pei qiPS be distinct values, and z0 , z1 , . . . , zq be 2 distinct values. Then, with ε “ e´pe ´1qq´log2 p , ˆ ˙p´|S|´1 “ ‰ |S| Prf Ð$ Zdp rXs f pxq “ z0 X @j P S : f ´1 pzj q “ tej u P r1 ˘ εs ¨ p´|S|´1 1 ´ . p By substituting S “ S Y T , ei “ ei for i P S and ei “ e1i for i P T , we have that ˆ ˙p´|S|´|T |´1 |S| ` |T | ´|S|´|T |´1 1 1´ PrrGT,pei qiPT s P r1 ˘ εs ¨ p . p Hence, we bound « ff ˆ ˙p´|S|´|T |´1 č |S| ` |T | |T | ´|S|´|T |´1 1´ Pr pD X Ej q P r1 ˘ εs ¨ Erp|S| ` 1, |T |; pqp ¨ p p jPT ˆ ˙p´|S|´|T |´1 |S| ` |T | “ r1 ˘ εs ¨ Erp|S| ` 1, |T |; pq ¨ p´|S|´1 1 ´ , p pp´|S|´1q! 1 where the multiplicative term Erp|S| ` 1, |T |; pq ¨ p|T | “ pp´|S|´|T |´1q! is the number of distinct pei qiPT P

pZp zptxu Y tei uiPT qq|T | . We emphasize that this probability only depends on the size of S and T (ignoring for the error term). Therefore, we can (upper and lower) bound F by substituting into Equation (3) the derived bound as ˆ ˙p´|S|´|T |´1 ÿ |S| ` |T | |T | ´|S|´1 F P p´1q r1 ˘ εs ¨ Erp|S| ` 1, |T |; pqp 1´ p T ĎrqszS

´|S|´1

“p

q´|S| ÿ

˙ ˆ ˙p´|S|´i´1 q ´ |S| |S| ` i p´1q r1 ˘ εs Erp|S| ` 1, i; pq 1 ´ . i p i“0 ˆ

i

17

The second equality follows from setting i “ |T | and factoring out p´|S|´1 . Now, we lower bound p|S|`1 F by taking the worst case of ˘ε in the alternating sum: p|S|`1 F ě

q´|S| ÿ

˙ ˆ ˙p´|S|´i´1 q ´ |S| |S| ` i Erp|S| ` 1, i; pq ¨ 1 ´ i p i“0 ˆ ˙ ˆ ˙p´|S|´i´1 q´|S| ÿ q ´ |S| |S| ` i . ´ε Erp|S| ` 1, i; pq ¨ 1 ´ i p i“0 ˆ

p´1qi

(4)

(5)

We first see that the right-hand side of (4) is q´|S| ÿ

ˆ ˆ ˙ ˙p´|S|´i´1 |S| ` i q ´ |S| p´1q Erp|S| ` 1, i; pq ¨ 1 ´ i p i“0 ˆ ˙ ˆ ˙p´|S|´i´1 q´|S| ÿ |S| ` i i q ´ |S| ´1 p´1q Erp1, |S| ` i; pq ¨ 1 ´ “ Erp1, |S|; pq ¨ i p i“0 i

“ Erp1, |S|; pq´1 ¨ ηpSq

(6)

The first equality follows from Erp|S| ` 1, i; pq “ Erp1, |S|; pq´1 Erp1, |S| ` i; pq. The second equality follows from Lemma 5.1. Finally, we upper bound the term in (5), so that ultimately, we can lower bound p|S|`1 ¨F with p1´ε1 q¨ηpSq 2 for ε1 “ e´pe ´3qq´log2 p`1 . q´|S| ÿ ˆ

˙p´|S|´i´1 ˆ ˙ |S| ` i q ´ |S| ε¨ Erp|S| ` 1, i; pq ¨ 1 ´ p i i“0 q´|S| ÿ ˆq ´ |S|˙ ďε i i“0 “ ε2q´|S| 2

2

ď e´pe ´1qq´log2 p ¨ eq “ e´pe ´3qq´log2 p`1 e´q´1 ˙p´|S|´1 ˆ q ´pe2 ´3qq´log2 p`1 ďe 1´ p ď ε1 ¨ Erp1, |S|; pq´1 ¨ ηpSq .

(7)

The first inequality follows simply from p1 ´ xq ď 1. The second equality follows from the binomial sum. The third inequality is subtituting ε and that 2q´|S| ď eq . The second to last inequality follows from Lemma 3.5 ´ ¯p´|S|´1 p´|S|´1 with l “ q and k “ |S| ` 1 ď q ` 1, giving 1 ´ pq ě e´q p´q ě e´q´qpq´|S|´1q{pp´qq ě e´q´1 (last step follows from p ě 2q2 ). The last inequality follows from Corollary 5.3. Therefore, we have that from Equations (6) and (7) p|S|`1 ¨ F ě p1 ´ ε1 qErp1, |S|; pq´1 ¨ ηpSq ě p1 ´ ε1 qηpSq . The final inequality follows from Erp1, |S|; pq ď 1. This concludes the proof. 5.6

\ [

Proof of Lemma 5.6

Fix distinct z0 , z1 , . . . , zq and x, pej qjPS as in the lemma statement. We will first simplify the probability calculation by defining placeholder events and apply the inclusion-exclusion principle (more precisely using 18

the bounds in Lemma 3.2) so that the events can be easily analyzed. This proof will then crucially relies on the fact that d is relatively large. Denote the event in the lemma statement as W :“ pf pxq “ z0 X @j P S : f ´1 pzj q “ tej uq First, we will define the following sets/events containing polynomials with specific evaluation constraints: ` ˘ V :“ f pxq “ z0 X @j P S : f pej q “ zj Ui,α :“ f pαq “ zi ; for i P S, α P Zp . Note that W Ď V by definition, and Ui,α are sets of polynomials which maps α to zi . We then claim the following: Ť Claim. W “ V z iPS,αPZp zpte ujPS Ytxuq Ui,α j

Ť Proof (of Claim). We first prove that W Ď V z iPS,αPZp zpte ujPS Ytxuq Ui,α . Consider f P W . Since W Ď V , j Ť f P V . Hence, we only need to show that f R iPS,αPZp zpte ujPS Ytxuq Ui,α , i.e., for all i P S and α R tej ujPS Y j

´1 txu, f pαq ‰ zi . This is implied Ť by the fact that f pzi q “ tei u for all i P S. Now, we consider f P V z iPS,αPZp zpte ujPS Ytxuq Ui,α and will show that f P W . To do so, we consider for j

each i P S, the set f ´1 pzi q. Note that by definition of V , f pei q “ zi and that for any α R txu Y tej ujPS , α R f ´1 pzi q. Hence, we only need to consider α P txu Y tej ujPS which is not ei . However, since we know that z0 , z1 , . . . , zq are distinct, it cannot be the case that f pαq “ zi and f pαq “ zj for j ‰ i. Therefore, we have that f ´1 pzi q “ tei u, meaning f P W , proving the claim. [ \ With the claim, we can write PrrW s as » — PrrW s “ PrrV s ´ Pr — –V X

ď iPS, αPZp zptej ujPS Ytxuq

fi

fi

»

ffi — — Ui,α ffi fl “ PrrV s ´ Pr –

ď iPS, αPZp zptej ujPS Ytxuq

ffi pV X Ui,α qffi fl .

We also make the following observation. Lemma 5.7. Let V and Ui,α be as defined before. 1. For i ‰ j and any α P Zp , PrrUi,α X Uj,α s “ 0. 2. For any subset B Ď S ˆ Zp zptej ujPS Y txuq such that |B| ď d ´ |S| ´ 1 and each pi, αq P B has distinct Ş α (crucially, the i’s can be the same), we have that Prr pi,αqPB pV X Ui,α qs “ p´|S|´1´|B| . Proof. The first point is true simply because Ş zi ‰ zj , so it cannot be that f pαq “ zi ‰ zj “ f pαq. The second point follows from the fact that the event pi,αqPB pV X Ui,α q can be written as follows č

pV X Ui,α q “ f pxq “ z0 X p@j P S : f pej q “ zj q X p@pi, αq P B : f pαq “ zi q.

pi,αqPB

In particular, the set contains polynomials satisfying |S|`1`|B| evaluation constraints on f , since pi, αq P B contains all distinct α and α R tej ujPS Y txu. This boils down to |S| ` 1 ` |B| linearly independent constraints on the coefficients of the possible monic polynomials f of degree d. Therefore, with f uniformly random with Ş degree d and |S| ` 1 ` |B| ď d, we have that the probability is Prr pi,αqPB pV X Ui,α qs “ p´|S|´1´|B| \ [ The above lemma gives PrrV s “ p´|S|´1 from setting B “ H. We also consider the probability of the union of pV X Ui,α q. In particular, by the upper and lower bounds in Lemma 3.2, we have that for an even integer 19

K, which we pick to be such that K ` 1 ď d ´ |S| ´ 1 we can bound (we mark the slight differences of the upper and lower bounds with blue) » fi — Pr — –

ď iPS, αPZp zptej ujPS Ytxuq

ffi pV X Ui,α qffi fl »

ÿ

fi č

p´1q|B|´1 Pr –

ě BĎSˆpZp ztei uiPS Ytxuq: 1ď|B|ďK

pV X Ui,α qfl

pi,αqPB

p´1q|B|´1 p´|S|´|B|´1 1rB contains pj, αq with distinct αs

ÿ “

BĎSˆpZp ztei uiPS Ytxuq: 1ď|B|ďK K ÿ

“

ˆ i´1

p´1q i“1

˙ p ´ |S| ´ 1 |S|i p´|S|´i´1 . i

Ş The second equality for the lower bound follows from the probability of the event pi,αqPB pV X Ui,α q for |B| ď K `1 ď d´|S|´1 as established in Lemma 5.7 (the indicator refers to the conditions from the lemma). The third equality for the lower bound follows by counting the number of subsets B of i satisfying the˘ ` ˘ size `p´|S|´1 i indicator (i.e., containing pj, αq with distinct α). The total count for each i is p´|S|´1 |S| , where i i is the number of ways to choose i distinct α values from Zp ztei uiPS Y txu, and |S|i is the number of ways to assign an index j P S to each α. Similarly, we also have the upper bound derived from similar steps. » fi fi » č ď ÿ — ffi pV X Ui,α qfl Pr — p´1q|B|´1 Pr – pV X Ui,α qffi – flď iPS, αPZp zptej ujPS Ytxuq

BĎSˆpZp ztei uiPS Ytxuq: 1ď|B|ďK`1 K`1 ÿ

“

ˆ p´1qi´1

i“1

pi,αqPB

˙ p ´ |S| ´ 1 |S|i pd´|S|´i´1 , i

From the above bounds, we can lower and upper bound PrrW s as ˙ ˆ ˙ ˆ ˙i K ÿ p ´ |S| ´ 1 p ´ |S| ´ 1 |S| |S|i p´|S|´i´1 “ p´|S|´1 p´1qi i i p i“1 i“0 ˙i ˆ ˙ ˆ ˙ ˆ K`1 K`1 ÿ ÿ |S| ´|S|´1 i´1 p ´ |S| ´ 1 i ´|S|´i´1 ´|S|´1 i p ´ |S| ´ 1 PrrW s ě p ´ p´1q |S| p “p p´1q . p i i i“1 i“0 PrrW s ď p´|S|´1 ´

K ÿ

ˆ

p´1qi´1

The equalities for both the upper and lower bounds follow from ´p´1qi´1 “ p´1qi and that p´|S|´1 “ `p´|S|´1˘ 0 ´|S|´0´1 |S| p . 0 ` ˘ ´ |S| ¯i řK Now, we observe that the term i“0 p´1qi p´|S|´1 without the factor p´|S|´1 is simply a truncated i p ´ ¯p´|S|´1 sum of the binomial expansion of 1 ´ |S| . In particular, we have p ˆ ˙ ˆ ˙i ˆ ˙p´|S|´1 p´|S|´1 ˆ ˙ ˆ ˙i ÿ p ´ |S| ´ 1 |S| |S| |S| i´1 p ´ |S| ´ 1 p´1q “ 1´ ` p´1q i i p p p i“0 i“K`1 K ÿ

i

20

Choosing K “ e2 q ` 2 log2 p – this can be done by choosing d ě pe2 ` 1qq ` 2 log2 p ` 1. Each of the term in the summation on the RHS with i ą K can be upper bounded as ˆ ˙ ˆ ˙i pp ´ |S| ´ 1q!|S|i |S|i p ´ |S| ´ 1 |S| “ ď i p i!pp ´ |S| ´ 1 ´ iq!pi i! ˙i ˆ e|S| ď i ´ eq ¯i ď i 2 ď e´i ď e´pe q`2 log2 pq . (8) The first equality follows from expanding the binomial coefficient. The second inequality follows from pp´|S|´1q! pp´|S|´1´iq!pi ď 1. The third inequality follows from Lemma 3.3. The fourth inequality follows from |S| ď q. The last two inequalities follows from i ą K ě e2 q ` 2 log2 p. Hence, we have that p´|S|´1 ÿ

ˆ i´1

p´1q i“K`1

p ´ |S| ´ 1 i

˙ˆ

|S| p

˙i 2

ď pe´pe q`2 log2 pq 2

ď e´pe q`log2 pq ˆ ˙p´|S|´1 2 |S| ď e´pe ´1qq´log2 p 1 ´ . p

(9)

The first inequality follows from the prior bound and that the number of terms in the sum is at most ¯p´|S|´1 ´ ě p. The second inequality follows from p ď elog2 p . The third inequality follows from 1 ´ |S| p ´ ¯p´|S| 1 ´ |S| ě e´|S| ě e´q (the second step is via Lemma 3.5 with l “ k “ |S|). Thus, we have that for p 2

ε “ e´pe ´1qq´log2 p ˆ

|S| PrrW s ď p1 ` εq 1 ´ p

˙p´|S|´1 ¨ p´|S|´1 .

Next, for the lower bound of PrrW s, we can similarly see that ˙ ˆ ˙i ˆ ˙p´|S|´1 p´|S|´1 ˆ ˙ ˆ ˙i ÿ |S| |S| p ´ |S| ´ 1 |S| i p ´ |S| ´ 1 p´1q “ 1´ ´ p´1q i p p i p i“0 i“K`2 ˙p´|S|´1 ˆ 2 |S| ´ p ¨ e´pe q`2 log2 pq ě 1´ p ˆ ˙p´|S|´1 |S| ě p1 ´ εq 1 ´ p ´ ¯p´|S|´1 The first equality follows from expanding 1 ´ |S| . The second and third inequalities follow from p K`1 ÿ

ˆ

i

Equations (8) and (9), respectively. Therefore, we can similarly lower bound PrrW s as ˆ ˙p´|S|´1 |S| PrrW s ě p1 ´ εq 1 ´ ¨ p´|S|´1 . p This proves the lemma.

6

\ [

Our Tight Reductions for Distinct Messages

In this section, we give our tight reductions in Section 6.1 with the analysis in the following subsections. 21

Algorithm B1 pG1 , pX1,i qiPrd1 s , G2 , X2,1 q:

Oracle Spmi P Zp q: d

˚

Sigs, S Ð H ; ẽ1 , . . . , ẽq Ð$ Zp ; β Ð$ Zp ; f Ð$ Zp rXs ś ś G1 Ð f pxq qi“1 px ´ ẽi qG1 ; ; H Ð β qi“1 px ´ ẽi qG1 ˚

pm , σ i

˚

˚

˚

˚

˚

“ ei u

if |rootpf pXq ` mi βq| “ 1 then ei Ð rootpf pXq ` mi βq S Ð S Y tiu

S

“ pA , e qq Ð$ A pG1 , H, G2 , X2,1 q

Ð minti : e

:

else ei Ð eri pf pxq`mi βq

ś

ri q iPrqs px´e

Ai Ð G1 ˚ ˚ ˚ x´ei R S Y e P tr ei uiPrqs Y pm , σ q P Sigs Y ¯ ¯ ´ ´ Sigs Ð Sigs Y tpm , pA , e qqu i i i ˚ ˚ ˚ e A , X2,1 ` e G2 ‰ e G1 ` m H, G2 then return K return pAi , ei q ˚ ˚ ´1 return pe , px ´ e q G1 q // Computed via Remark 3.1 if i

˚

˚

“K Y i

Fig. 5. Adversary B1 running A. We assume that all algorithms implicitly take as input the group description, and B1 implicitly counts the signing queries. d1 “ d ` q “ rpe2 ` 2qq ` 2 log2 ps ` 1. We use rootp¨q as a Zp -scalar instead if its size is 1. :: Our analysis does not require monic f , but we use it for consistency with the technical overview and readability as there are exactly d coefficients, rather than d ` 1. ; : At this point, it is not obvious that G1 is uniformly random. We will formally show this in our analysis but intuitively this is due to the degree d of f being relatively large.

6.1

Proof of Lemma 4.4

For simplicity, assume that all algorithms implicitly take as input the group description pp, G1 , G2 , GT , eq. We consider an SUF1 adversary A making exactly q distinct signing queries (since q is the upper bound we assume this without loss of generality). The adversary receives at the start of the game the tuple of public parameters and verification key pG1 , H, G2 , X2,1 q. For each i P rqs, we denote mi P Zp as the query and σi “ pAi , ei q as the resulting signature. At the end of the game, A outputs a forgery pm˚ , σ ˚ “ pA˚ , e˚ qq. We consider the event where A wins in SUF1 game, denoted Forge1 adopting the name from [TZ23]. We also consider an additional bad event BadQ where the adversary A makes a signing query mi such that G1 ` mi H “ 0G1 . We denote the event pForge1 X ␣BadQq as Forge11 . Here, we have that 1

1 Advsuf BBS1 pA, λq “ PrrForge1 s ď PrrForge1 s ` PrrBadQs .

Bounding PrrBadQs. We construct a reduction BBadQ playing the DLOG game such that PrrBadQs ď Advdl GGen pBBadQ , λq . In particular, BBadQ takes as input G1 P G˚1 , Z1,1 P G1 , G2 P G˚2 . The reduction samples x Ð$ Zp and set X2,1 “ xG2 and run the adversary with the input pG1 , H “ Z1,1 , G2 , X2,1 q. For each signing query mi , the ´1 iH $ reduction returns pAi “ G`m x´ei , ei Ð Zp q. If BadQ occurs, the reduction returns mi . Note that if BadQ occurs, mi ‰ 0 and is invertible, since G1 is a generator. Thus, the above inequality is justified. Bounding PrrForge11 s. We additionally assume that A does not make signing queries that trigger BadQ and consider the event Forge11 . To bound PrrForge11 s, we consider the reduction B1 , given in Figure 5, following the sketch in Section 2.2, and playing the d1 -SDH game where d1 “ rpe2 ` 2qq ` 2 log2 ps ` 1 “ Θpq ` λq. We note that the running time of B1 is dominated by (1) the running time of A (roughly tA ) and (2) the signing simulation which consists of (2.1) checking if f pXq`mi β has exactly 1 root in Zp and (2.2) computing the group element Ai from the d-SDH instance. Step (2.1) can be done by computing gcdpf pXq`mi β, Xp ´Xq and checking if the result is of degree 1 or not. More precisely, we can first compute Xp ´X pmod f pXq`mi βq via repeated squaring and polynomial division taking Opq log q log2 pq time (see [Y` 00, Lecture 1]), and then computing the GCD, via the Half-GCD algorithm (see [Y` 00, Lecture 2] and [AH74, Theorem 8.19]), takes Opq log2 q log pq per query with d “ Θpq ` λq.7 Step (2.2) can be done by computing the polynomial 7

We do not need to fully factor out the polynomial f pXq ` mi β nor need to know all available zeros. This helps immensely in reducing the running time of our reduction.

22

śq

i“1 pX´ẽi qpf pXq`mi βq

and compute Ai as a linear combination of G1 , X1,1 , . . . , X1,d , taking OpqpTG ` Tp qq X´ei per query. The reduction B1 wins in the d1 -SDH game if the following occurs: (1) A returns a “fresh” forgery `m˚ H pm˚ , pA˚ , e˚ qq such that Ai˚ ‰ A˚ and ei˚ “ e˚ for some i˚ P rqs and A˚ “ G1x´e , (2) x and e1 , . . . , eq ˚ ei uiPS “ H. This is because if tei uiPrqs X tr ei uiPS “ H and i˚ P S, are distinct, (3) i˚śP S, and (4) tei uiPrqs X tr q then pX ´ ei˚ q ∤ i“1 pX ´ ẽi q. Moreover, the forgery being fresh and i˚ P S implies that m˚ ‰ mi˚ , so pX ´ ei˚ q ∤ pf ` m˚ βq (in order to apply Remark 3.1); otherwise, f pei˚ q “ ´m˚ β ‰ ´mi˚ β “ f pei˚ q, which is a contradiction. With that said, we claim the following lemma which concludes the proof. Lemma 6.1. For a prime p, an integer q where p ě 2q2 , and d1 “ rpe2 ` 2qq ` 2 log2 ps ` 1 ă p, ˆ ˙ 2q2 ` 4q ` 1 1 d1 -sdh . PrrForge1 s ď e ¨ AdvGGen pB1 , λq ` p 6.2

Proof of Lemma 6.1

We assume A to be deterministic without loss of generality. For our formal analysis, we will use shorthand Pr0 r¨s and Pr1 r¨s to denote probabilities in Experiment 0, which is the SUF game running the adversary A, and Experiment 1, which is the simulation by B1 to A, respectively. However, we augment the transcripts in both experiments with the set S further explained below. In particular, we denote the transcript in experiment b P t0, 1u as Tb , which are of the form T0 “ pa, b, c, x, pm1 , e1 q, . . . , pmq , eq q, Sq , T1 “ pa, b, c, x, pm1 , e1 q, . . . , pmq , eq q, Sq . The values b, b and c denote the discrete logarithms with respect to some fixed generator of H, H and G2 , respectively. In T0 , a denotes the discrete logarithm of G1 with respect to some fixed generator, and the set S Ď rqs is sampled independently of the rest of the transcript with the probability density function η : 2rqs Ñ r0, 1s as defined in Lemma 5.1. In particular, let z0 , . . . , zq P Zp be distinct and any x0 P Zp , we can sample S as follows: (1) sample a random function f : Zp Ñ Zp such that f px0 q “ z0 and (2) set S as the set of indices i P rqs such that |f ´1 pzi q| “ 1, i.e., there is exactly one preimage of i. Note that the distribution of S is independent of the choice of images z0 , . . . , zq and the fixed x0 . In T1 , a denotes the discrete logarithm of G1 with respect to some fixed generator, and the rest of the transcript is sampled as in the reduction. The set S Ď rqs is defined as follows: given the messages m1 , . . . , mq sent by A, the sampled f , x, and β, S :“ ti P rqs : |f ´1 p´mi βq| “ 1u. We excluded the elements G1 , H, G2 , and Ai , since they are already determined by the transcript. For each i˚ P rqs, we define the event Forge11,i˚ as the event that Forge11 occurs and the value e˚ “ ei˚ . We note that since the adversary is deterministic, this event is well-defined for both transcripts T0 , T1 (as the forgery is determined by the transcript). Also, denote GoodE as the event that x, e1 , . . . , eq are distinct. Then, according to the winning condition of B1 , we have that “ ` ˘ ‰ 1 -sdh AdvdGGen pB1 , λq ě Pr1 GoodE X Di˚ P rqs : Forge11,i˚ X i˚ P S X ptei uiPrqs X tr ei uiPS “ Hq “ ` ˘‰ ě Pr1 GoodE X Di˚ P rqs : Forge11,i˚ X i˚ P S ´ Pr1 rtei uiPrqs X tr ei uiPS ‰ Hs 2 “ ` ˘‰ q ě Pr1 GoodE X Di˚ P rqs : Forge11,i˚ X i˚ P S ´ . p 2

ei uiPS ‰ Hs ď qp . This is because either (1) there is no The last inequality follows from Pr1 rtei uiPrqs X tr element in S (the event is not triggered), or (2) for i P S, eri is uniformly random and hidden from the view of the adversary (the transcript hides eri for i P S), so each collides with tei uiPrqs with probability at most pq . Then, the following lemma, proved in Section 6.3, upper bounds the total variation distance between the two transcripts given that d1 is large enough. 23

Lemma 6.2. For a prime p, an integer q where p ě 2q2 , and d1 “ rpe2 ` 2qq ` 2 log2 ps ` 1, SDpT0 , T1 q ď

pq ` 1q2 ` 4q . 2p

Using Lemma 6.2, we have that ‰ q2 “ Pr1 GoodE X Di˚ P rqs : pForge11,i˚ X i˚ P Sq ´ p “ ‰ pq ` 1q2 ` 4q q2 ě Pr0 GoodE X Di˚ P rqs : pForge11,i˚ X i˚ P Sq ´ ´ 2p p q 2 ÿ “ ‰ 3q ` 6q ` 1 Pr0 GoodE X Forge11,i˚ X i˚ P S ´ “ 2p ˚ i “1 q ÿ

“

‰ “ 3q2 ` 6q ` 1 Pr0 GoodE X Forge11,i˚ Pr0 ri˚ P Ss ´ 2p

i˚ “1 q ÿ

ě

1 e ˚

i “1

‰ 3q2 ` 6q ` 1 “ Pr0 GoodE X Forge11,i˚ ´ 2p

3q2 ` 6q ` 1 1 Pr0 rGoodE X Forge11 s ´ e 2p 1 1 3q2 ` 6q ` 1 ě Pr0 rForge11 s ´ Pr0 r␣GoodEs ´ e e 2p 2 2q ` 4q ` 1 1 ě Pr0 rForge11 s ´ . e p

“

The first inequality follows from the lemma. The second equality follows from the events Forge11,i˚ X i˚ P S being disjoint for all i˚ P rqs when GoodE is true. The third equality follows from S sampled independently from the rest of the transcript in T0 (note that i˚ is a fixed value). Then, the fourth inequality follows from Corollary 5.2. The fifth equality is obtained by summing over the probability of disjoint events Forge11,i˚ . The ` ˘1 last inequality follows from Prr␣GoodEs ď q`1 \ [ 2 p . Rearranging the terms finally concludes the proof. 6.3

Proof of Lemma 6.2

H-coefficient technique. Our goal is to bound the total variation distance SDpT0 , T1 q defined as SDpT0 , T1 q :“

ÿ 1ÿ |PrrT0 “ τ s ´ PrrT1 “ τ s| “ maxt0, PrrT0 “ τ s ´ PrrT1 “ τ su . 2 τ τ

The sum is over all transcripts τ . We will employ Patarin’s H-Coefficient technique [Pat08], but using the formalism of [HT16], which we now introduce. First, we denote any transcript τ to be of the form τ “ pa, b, c, x, pm1 , e1 q, . . . , pmq , eq q, Sq . Note the distinction of a fixed value (denoted with p¨q) and random variables (without). Let T denote the set of transcripts τ such that PrrT0 “ τ s ą 0. Also, we let p0 pτ q and p1 pτ q denote the interpolation probability, i.e., the probability that we pick the random coins in the respective experiment and result in the transcript τ if the queries m1 , . . . , mq are fixed ahead of time. Note that for any transcript τ , we have Prb rTb “ τ s P t0, pb pτ qu, since A is deterministic. Then, ÿ SDpT0 , T1 q “ maxt0, p0 pτ q ´ p1 pτ qu . τ PT

24

The key idea for the H-coefficient technique is to consider a subset set of good transcripts Good Ď T such that for τ P Good, p1 pτ q ďδ 1´ p0 pτ q for some δ P r0, 8q. Then, we can bound SDpT0 , T1 q as " * ÿ p1 pτ q SDpT0 , T1 q ď p0 pτ q max 0, 1 ´ ` Pr0 r␣Goods ď δ ` Pr0 r␣Goods . p0 pτ q τ PGood Here, the event ␣Good in T0 is independent of the queries of the adversary A. This lets us circumvent the adaptive nature of the distinguisher when analyzing the statistical distance, as considering ␣Good in T1 can be quite complicated. Interpolation probability. Recall first that we only consider transcripts where mi ‰ ´a{b (otherwise, G1 ` mi H “ 0G1 which is ruled out by the event BadQ) and the queries mi ’s are distinct (this is assumed at the beginning). Now, we define Good to be the set of transcripts τ such that (1) x and e1 , . . . , eq are 2

distinct, and (2) a and b are non-zero. Note here that Pr0 r␣Goods ď pq`1q ` p1 via the union bound over 2p the negation of (1) and (2). Now, fix a transcript τ P Good, we will compute the interpolation probabilities pτ q p0 pτ q and p1 pτ q and lower bound pp01 pτ q to ultimately bound SDpT0 , T1 q via the above inequality. For p0 pτ q, we consider the distribution of T0 . First, b, x, e1 , . . . , eq are uniformly random over Zp and a, c are uniformly random in Z˚p . Also, S is sampled independently with respect to the PDF η. Hence we have that the interpolation probability of the sampled transcript being exactly τ is p0 pτ q “

1 1 1 1 1 ¨ ¨ ¨ ¨ ¨ηpSq q p ´ 1 p p ´ 1 p p loomoon loomoon loomoon loomoon loomoon a

“

b

c

x

pei qiPrqs

1 1 1 1 1 ηpSq . ¨ ¨ ¨ q´|S| ¨ p p ´ 1 p p pp ´ 1qp|S| loomoon loomoon loomoon loomoon loooooooomoooooooon b

c

x

pei qiRS

pa,pei qiPS ,Sq

The first equality follows because each value in the transcript is sampled uniformly at random according to their domain. (Note: we write the factors in the order of the transcript τ and annotate the random variable each factor corresponds to.) The second equality follows by simply rearranging the terms. The corresponding annotated values will assist in comparing the quantity with p1 . Now, we consider the more complex p1 pτ q. To reiterate, the transcript is defined by the randomness px P Zp , pẽi P Zp qiPrqs , f P Zdp rXs, β P Z˚p , c P Z˚p q sampled by the reduction. This means p1 pτ q can be written as follows: » fi x“x Xś c“cX — a “ f pxq q px ´ ẽi q X ffi ÿ — ffi ś i“1 1 1 1 1 1 — b “ β q px ´ ẽi q X ffi . p1 pτ q “ ¨ ¨ ¨ ¨ 1 i“1 — ffi d q p p ´ 1 p ´ 1 p p ´1 loomoon loomoon loomoon loomoon loomoon f,x,pẽi qiPrqs ,β,c – @i R S : |f p´mi βq| ‰ 1 X eri “ ei X fl c x f β ei qiPrqs pr @i P S : f ´1 p´mi βq “ tei u The sum counts all possible randomness that results in the transcript τ . Note that the indicator is 1 only if x “ x, c “ c, eri “ ei for all i R S, and eri ‰ x for all i P rqs. The last condition arises from considering τ P Good where a, b ‰ 0 and all ei ‰ x. By constraining to these particular values, we rewrite the sum as ś ś » fi f pxq “ a iRS px ´ ei q´1 iPS px ´ ẽi q´1 X ś ś ´1 ´1 ÿ ÿÿ —β “ b ffi 1 1 1 1 1 X iPS px ´ ẽi q iRS px ´ ei q ffi . ¨ ¨ ¨ q´|S| ¨ |S| d 1— ´1 – fl pomo ´ o1n lo pomo ´ o1n loomo p on loomoon @i R S : |f p´mi βq| ‰ 1 X p p p pẽ q ‰x β f lo i iPS ´1 @i P S : f p´mi βq “ tei u c x b pei qiRS loooooooooooooooooooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooooooooooooooooooon pa,pei qiPS ,Sq

25

Now, and pẽi qiPS “ ś pei qiPS , β is fixed as β “ ś if we fix each ś tuple pẽi qiPrqs such that ẽi ‰ x for i P rqsś b iRS px ´ ei q´1 iPS px ´ ẽi q´1 ‰ 0, and f pxq is fixed as a1 “ a iRS px ´ ei q´1 iPS px ´ ẽi q´1 ‰ 0. Then, for these fixed values, we want to count the number of f such that the following constraint is true f pxq “ a1 X p@i R S : |f ´1 p´mi βq| ‰ 1q X p@i P S : f ´1 p´mi βq “ tei uq . This coincides with the event considered in Lemma 5.4in Section 5.2, by setting z0 “ a1 , zi “ ´mi β, and ei “ ei for i P rqs. Note that z0 , z1 , . . . , zq are distinct, since τ P Good and ´mi ‰ a{b. Applying Lemma 5.4, we have that „ ȷ „ ȷ 1 ÿ f pxq “ a1 X @i R S : |f ´1 p´mi βq| ‰ 1 f pxq “ z0 X @i R S : |f ´1 p´mi βq| ‰ 1 1 ¨ “ Pr d f Ð$ Zp rXs X @i P S : f ´1 p´mi βq “ tei u X @i P S : f ´1 p´mi βq “ tei u pd f

ě p1 ´ εq ¨ p´1´|S| ηpSq , 2

where ε “ e´pe ´3qq´log2 p`1 . Finally, we can lower bound p1 pτ q as ś ś » fi f pxq “ a iRS px ´ ei q´1 iPS px ´ ẽi q´1 X ś ś ´1 ´1 ÿ ÿÿ —β “ b ffi 1 1 1 1 1 X iRS px ´ ei q iPS px ´ ẽi q ffi p1 pτ q “ ¨ ¨ ¨ q´|S| ¨ |S| d 1— ´1 – fl p´1 p´1 p p @i R S : |f p´mi βq| ‰ 1 X p p pẽ q ‰x β f i iPS ´1 @i P S : f p´mi βq “ tei u ÿ 1 1 1 1 1 1 ě ¨ ¨ ¨ ¨ p1 ´ εq 1`|S| ηpSq p ´ 1 p ´ 1 p pq´|S| p|S| p pẽ q ‰x i iPS

1 pp ´ 1q|S| 1 1 1 1 “ ¨ p1 ´ εq 1`|S| ηpSq ¨ ¨ ¨ q´|S| ¨ |S| p´1 p´1 p p p p ˆ ˙|S| 1 “ p1 ´ εq 1 ´ ¨ pp ´ 1q´1 ¨ pp ´ 1q´1 ¨ p´1 ¨ p´q`|S| ¨ p´1´|S| ηpSq . loooooooooooooooooooooooooooooooomoooooooooooooooooooooooooooooooon p p0 pτ q

The second inequality follows from the inequality derived above and because there is only one β that makes the indicator 1. The second to last equality follows from counting the number of pr ei qiPS where eri ‰ x. The last equality follows by rearranging the terms. We also mark the modified terms with blue . Therefore, ˆ ˙|S| p1 pτ q 1 |S| q`1 ě p1 ´ εq 1 ´ ě1´ε´ ě1´ . p0 pτ q p p p ś ř The second inequality follows from i p1 ´ xi q ě 1 ´ i xi for 0 ď xi ď 1. The last one follows from ε ď 1{p and |S| ď q. Hence, we have that pq ` 1q2 ` 4q SDpT0 , T1 q ď .[ \ 2p

7

Impossibility of Tight Reductions for General Messages

In this section, we consider the tightness of security reductions againsts adversaries that makes arbitrary (i.e., not necessarily distinct) signing queries. In particular, Sections 7.1 and 7.2 give lower bounds on the reduction loss for straight-line and rewinding “algebraic” reductions, respectively. 7.1

Impossibility of Tight Straight-Line Algebraic Reductions

The following theorem shows that for any straight-line algebraic reduction R, with black-box access to an adversary A that makes at most q identical signing queries, cannot achieve an advantage in breaking 26

1

the pd1 , d2 q-SDH assumption greater than Opq´1 q ¨ Advsuf BBS pA, λq. Otherwise, there exists an adversary M breaking pd1 , d2 q-DL with non-negligible advantage. Accordingly, any straight-line algebraic reductions must incur at least a Θpqq factor loss in the advantage. Here, it suffices for us to show impossibility of tight SUF1 security with message length ℓ “ 1, since it is tightly (and trivially) implied by SUF security for any ℓ ą 1. We also stress that the reduction R does not obtain the algebraic representation of the group elements output by the adversary. (Note that there exists a tight reduction in the AGM [TZ23].) Finally, Corollary 7.3 extends this impossibility result to adversaries A with fine-grained query patterns: making q{k queries each on k distinct messages. In that case, the loss is at least Θpq{kq. Theorem 7.1. Let GGen be a group parameter generator outputting bilinear groups of prime-order p “ ppλq, d1 “ d1 pλq, d2 “ d2 pλq be integers, and BBS1 “ BBSrGGen, 1s. There exists an unbounded adversary A 1 q2 making q “ qpλq identical signing queries with Advsuf BBS1 pA, λq ě 1 ´ p . For any straight-line algebraic reduction R in the pd1 , d2 q-SDH game with running time tR “ tR pλq and running the adversary only once, there exists a meta-reduction M (in the AGM) against the pd1 , d2 q-DL assumption running in time roughly tR such that 2 pd1 ,d2 q-dl pd1 ,d2 q-sdh AdvGGen pM, λq ě AdvGGen pRA , λq ´ . q Proof. We will discuss the reduction’s output and representation in the AGM, describe the unbounded adversary A and the meta-reduction M in Figure 6, and analyze them. For simplicity, assume that all algorithms implicitly takes as input the group description pp, G1 , G2 , GT , eq. Reduction R. Note that we are working in Type-3 pairing groups and assuming the AGM [FKL18]. In particular, the reduction takes as input the group elements pG1 P G˚1 , pX1,i P G1 qiPrd1 s , G2 P G˚2 , pX2,i P G2 qiPrd2 s q. It then outputs the following group elements along with their algebraic representation: ‚ Public parameters and key: The group elements G1 , H, G2 , X 2,1 are given along with their representation f⃗, ⃗g P Zdp1 `1 , ⃗a, ⃗b P Zdp2 `1 such that G1 “ f0 G1 `

d1 ÿ

fi X1,i , H “ g0 G1 `

i“1

G2 “ a0 G2 `

d2 ÿ

d1 ÿ

gi X1,i ,

(10)

i“1

ai X2,i , X 2,1 “ b0 G2 `

i“1

d2 ÿ

bi X2,i .

(11)

i“1

In particular, f⃗, ⃗g define polynomials f, g of degree at most d1 and similarly ⃗a, ⃗b define polynomials a, b8 of degree at most d2 . We will refer to them as polynomials throughout the proof. ‚ Signing queries: As a part of the output of the i-th signing query, the group element Ai can be described with α ⃗ piq P Zdp1 `1 or equivalently a polynomial αpiq of degree at most d1 such that piq

Ai “ α0 G1 `

d1 ÿ

piq

αj X1,i “ αpiq pxqG1 .

j“1

‚

The pd1 , d2 q-SDH solution: The SDH solution pe1 , Z ˚ q is described with ζ⃗ P Zd`2 where p Z ˚ “ ζ0 G1 `

d1 ÿ

ζi X1,i ` ζd1 `2 A˚ ,

i“1

with A˚ being the forgery that the adversary returns to the reduction. 8

These extend from Section 2.3 on how the reduction can choose the verification key.

27

Algorithm BS pG1 , H, G2 , X 2,1 , f⃗, ⃗ g, ⃗ a, ⃗bq:

Algorithm Mpinpq: pG1 , pX1,i qiPrd1 s , G2 , pX2,i qiPrd2 s q Ð inp 1

B

˚

⃗ Ð$ R pinpq pe , Z , ζq řd1 ˚ ζi X1,i ` ζd1 `2 A˚ // Z “ ζ0 G1 ` i“1

// f⃗, ⃗ g, ⃗ a, ⃗b satisfy (10,11) , f⃗, ⃗ a ‰⃗ 0 if G1 “ 0G1 Y G2 “ 0G2 then return K m Ð$ Zp ; i

˚

˚

Ð$ rqs ; m

Ðm`1 piq

1

⃗ q Ð$ Spmq return x s.t. xG1 “ X1,1 X ζpxqpx ´ e q “ 1 for i P rqs : pσi “ pAi , ei q, α řd1 S piq piq Algorithm A pG1 , H, G2 , X 2,1 q: // Ai “ α0 G1 ` j“1 αj X1,i “ αpiq pxqG1 if G1 “ 0G1 Y G2 “ 0G2 then return K m Ð$ Zp x Ð dlogG pX 2,1 q 2

if pDi P rqs : BBS.VerppG1 , H, G2 q, X 2,1 , m, σi q “ 0q Y pDi ‰ j P rqs : ei “ ej q then return K if Di P rqs : pb ´ ei aq ffl pf ` mgqa then

for i P rqs : pσi “ pAi , ei qq Ð$ Spmq if pDi P rqs : BBS.VerpX 2,1 , m, σi q “ 0q Y pDi ‰ j P rqs : ei “ ej q then return K i

˚

˚

Ð$ rqs ; m

Ðm`1

˚

return pm , pA˚ “

// BadRep

M abort and return x where xG1 “ X1,1 X piq

α

pxqpbpxq ´ ei apxqq “ pf pxq ` mgpxqqapxq

if pb ´ ei˚ aq ‌ f a X pb ´ ei˚ aq ‌ ga X degpb ´ ei˚ aq “ maxtdeg a, deg bu then

G1 `m˚ H , ei˚ qq x´e ˚ i

f pxq`m˚ gpxq apxq ¨ apxqG1 , ei˚ qq i˚

return pm˚ , pA˚ “ bpxq´e else M abort

// BadIdx

Fig. 6. Meta-reduction M, unbounded adversary A, and simulated adversary B. As discussed in the body, all rep⃗ we write ζ as the corresponding polynomial). resentation vectors can be parsed as a polynomial (i.e., for a vector ζ, We distinguish between the meta-reductionM and the simulated adversaryB aborting with abort and return K, respectively.

Unbounded adversary A. The adversary A in Figure 6 finds the discrete logarithm x “ dlogG2 X 2,1 , makes q signing queries on a uniformly random message m, and forges on m ` 1 using x and a tag ei˚ with i˚ Ð$ rqs. Here, A wins in the SUF1 game unless it aborts when signatures are invalid or the tags ei ’s collide 1 2 (occurs with probability at most q2 {p). Hence, Advsuf BBS1 pA, λq ě 1 ´ q {p. Meta-reduction M: The meta-reduction M, given in Figure 6, forwards its inputs to R and has access to R’s algebraic representations. It simulates A by making q queries on a random message m and trying to forge using a tag from a random query. We note that there are two bad events defined where M aborts: ‚ BadRep: There exists some i P rqs where pb ´ ei aq ffl pf ` m ¨ gqa. If this occurs, M can find the ` ˘ ` ˘ discrete logarithm x of X2,1 . In particular, when pAi , ei q verifies, e Ai , X 2,1 ´ ei G2 “ e G1 ` mH, G2 . Therefore, αpiq pxq ¨ pbpxq ´ ei apxqq “ apxqpf pxq ` mgpxqq . Since pb ´ ei aq ffl pf ` mgqa, we have that x is one of the zeros of the non-zero polynomial hpXq “ αpiq pXqpbpXq ´ ei apXqq ´ pf pXq ` mgpXqqapXq, which M can find efficiently. ˚ ‚ BadIdx: The sampled index i is such that pb ´ ei˚ aq does not divide f a or ga, or degpb ´ ei˚ aq ă pXq`m˚ gpXq maxtdeg a, deg bu. If this does not occur, M can compute A˚ “ α˚ pxqG1 where α˚ pXq “ fbpXq´e apXq ˚ apXq i

˚

f pXq`m gpXq “ bpXq{apXq´e . With the degree constraint, we have deg α˚ “ degpf ` m˚ gq ` deg a ´ degpb ´ ei˚ aq ď i˚ degpf ` m˚ gq ď d1 , so A˚ can be computed from the pd1 , d2 q-DL instance. If BadIdx does not occur, the view of R is identical to when it is running A since M outputs a valid forgery. With A˚ “ α˚ pxqG1 , the representation ζ⃗ of Z ˚ can be viewed as a polynomial ζpXq with deg ζ ď d1 . Hence, M succeeds in the pd1 , d2 q-DL game, if R succeeds in the pd1 , d2 q-SDH game and BadIdx does not occur. Also, if BadRep occurs, M also succeeds as discussed above. Also, it is easy to see that the running time of M depends on tR , the time for finding the zeros of ζpXqpX ´ e1 q ´ 1, and the time for checking if b ´ ei˚ a divides f and g. These are dominated by tR . Finally, we bound the advantage of M and conclude the proof via the following lemma. pd ,d q-dl

1 2 AdvGGen

pd ,d q-sdh

1 2 pM, λq ě AdvGGen

pRA , λq ´ PrrBadIdx X ␣BadReps .

Lemma 7.2. PrrBadIdx X ␣BadReps ď 2q . 28

[ \

Proof (of Lemma 7.2). We fix any input and random tape of R, which fixes the polynomials f, g, a, b. Then, we show that for any such fixed polynomials, the probability that BadIdx X ␣BadRep occurs is at most 2{q. By definition, BadIdx X ␣BadRep implies (1) degpb ´ ei˚ aq ă maxtdeg a, deg bu, or (2) pb´ei˚ a ‌ pf `mgqaq X pb´ei˚ a ffl f a Y b´ei˚ a ffl gaq. Our approach is to upper bound the number of e’s that can lead to such event, which bounds the probability over i˚ Ð$ rqs, and take the expectation over m Ð Zp . For part (1) of the event, it is clear that only one e can decrease the degree, i.e., by canceling out the leading coefficient. Thus, for fixed f, g, a, b and distinct e1 , . . . , eq , Pri˚ Ð$ rqs rdegpb´ei˚ aq ă maxtdeg a, deg bus ď 1{q. For part (2) of the event, define for fixed f ‰ 0, g, a ‰ 0, b and m P Zp φf,g,a,b pmq :“ te P Zp : pb ´ eaq ‌ pf ` mgqa X ppb ´ eaq ffl f a Y pb ´ eaq ffl gaqu . Then, for m ‰ m1 P Zp , φf,g,a,b pmq X φf,g,a,b pm1 q “ H. This is because if there exists e P φf,g,a,b pmq X 1 φf,g,a,b pm1 q, we have that ř pb ´ eaq ‌ pf ` mgqa and pb ´ eaq ‌ pf ` m gqa, so b ´ ea divides both f a and ga (a contradiction). Hence, mPZp |φf,g,a,b pmq| ď p. Accordingly, for any fixed f ‰ 0, g, a ‰ 0, b P Zp rXs, m P Zp , and distinct e1 , . . . , eq P Zp (otherwise, A aborts), we have ȷ „ |φf,g,a,b pmq| pb ´ ei˚ aq ‌ pf ` mgqa X ď Pri˚ Ð$ rqs . ppb ´ ei˚ aq ffl f a Y pb ´ ei˚ aq ffl gaq q Taking expectation over all messages m P Zp results in the 1{q bound, and we conclude by applying the union bound. \ [ Corollary 7.3 (Generalized query patterns). Let GGen be a group parameter generator, producing groups of order p “ ppλq, d1 “ d1 pλq, d2 “ d2 pλq be integers, and BBS1 “ BBSrGGen, 1s. There exists an unbounded adversary A making in total q “ qpλq queries on at least k “ kpλq distinct messages with q{k 1 q2 queries per message, such that Advsuf BBS1 pA, λq ě 1 ´ p . For any straight-line algebraic reduction R playing the pd1 , d2 q-SDH game with running time tR “ tR pλq and running the adversary only once, there exists a meta-reduction M against the pd1 , d2 q-DL assumption running in time roughly tR such that pd ,d q-dl

1 2 AdvGGen

pd ,d q-sdh

1 2 pM, λq ě AdvGGen

pRA , λq ´

k`1 . q

Proof. We only sketch the changes to the proof of Theorem 7.1 as follows: ‚ Unbounded adversary A and meta-reduction M: Both now sample uniformly random distinct messages pµ1 , . . . , µk q Ð$ Zkp and make q{k queries each, i.e., the queries are m ⃗ Ð pµ 1 , . . . , µ1 , . . . , µ k , . . . , µk q. loooomoooon loooomoooon q{k times

q{k times

They both forge on the minimum element m˚ in Zp ztµ1 , . . . , µk u. The overall strategies for both are unchanged. ‚ Events BadIdx and BadRep. The two events are now defined as: (BadRep) There exists i P rqs such that pb ´ ei aq ffl pf ` mi gqa, and (BadIdx) For i˚ Ð$ rqs, b ´ ei˚ a does not divide f a or ga or degpb ´ ei˚ aq “ maxtdeg a, deg bu. The bound in Lemma 7.2 changes to pk ` 1q{q instead of 2{q. Intuitively, the term k{q appears because with k distinct messages, there are now k times more chances (by linearity of expectation) for the reduction to choose ei where b ` ei a does not divide f a or ga but divides pf ` mi gqa. \ [ 7.2

Impossibility of Tight Rewinding Algebraic Reductions

In this section, we extend our impossibility results to rewinding algebraic reductions that run the adversary at most r times with the same random tape, with the ability to interleave these executions. The following theorem establishes that any such reduction incurs at least a Θpq{r2 q factor loss in their advantage. (For fine-grained query patterns, this scales linearly with 1{k as in Corollary 7.3.) Otherwise, the meta-reduction breaks the pd1 , d2 q-DL assumption. This result also encompasses those from the previous section, which we presented separately to illustrate our main ideas with simpler proofs before progressing to the more complex proof in Section 7.3. 29

Theorem 7.4. Let GGen, p, d1 , d2 , and BBS1 be as in Theorem 7.1. There exists an unbounded adversary A making in total q “ qpλq queries on at least k “ kpλq distinct messages with q{k queries per message, 1 q2 such that Advsuf BBS1 pA, λq ě 1 ´ p . Moreover, for any algebraic reduction R playing the pd1 , d2 q-SDH game, running in time tR “ tR pλq, and running the adversary at most r “ rpλq times (possibly interleaving the executions), there exist meta-reductions M and M1 (both in the AGM) against the pd1 , d2 q-DL assumption running in time roughly tR such that pd ,d q-dl

1 2 AdvGGen

pd ,d q-sdh

1 2 pM, λq ě AdvGGen

pRA , λq ´

r2 ¨ pk ` 1q pd1 ,d2 q-dl ´ AdvGGen pM1 , λq . q

Proof (Sketch). We give a proof sketch here for the simpler case of k “ 1 and prove the general case in Section 7.3, following a similar argument from the straight-line reduction case. Similar to before, the (algebraic) reduction R and unbounded adversary A interact in the following steps in one run of A: (1) R sends G1 , H, G2 , X2,1 committing to polynomials f, g, a, b, respectively. (2) A replies with a random message m Ð$ Zp , requesting q signatures. (3) R sends valid signatures pAi , ei qiPrqs such that pa ´ ei bq ‌ pf ` mgqa. (4) A forges a signature on the tag ei˚ where i˚ Ð$ rqs. However in this case, R can rewind A and give group different elements G1 , H, G2 , X2,1 at Step (1) or different signatures pAi , ei qiPrqs at Step (3).9 Our meta-reduction would also replicate the adversary A except that it can only forge when ei˚ is such that pa ´ ei˚ bq divides both f a and ga in each run. As we will formally prove, the optimal strategy for the reduction is to rewind to Step (1) Oprq times and Step (3) Oprq times. In essence, the rewindings to Step (1) allow the reduction to find the tuple pf pXq, gpXq, apXq, bpXq, m P Zp q such that there are many tags e P Zp for which pa ´ ebq divides pf ` mgqa but does not divide f a or ga. We show that after r rewindings to Step (1), the largest number of such tags e over the r rewound runs is at most r in expectation. Then, r additional rewindings to Step (3) of the run that produces the best tuple pf, g, a, b, mq boost the failure probability of the meta-reduction by a factor of r, resulting in the r2 factor in the bound.

7.3

Proof of Theorem 7.4

For simplicity, assume that all algorithms implicitly takes as input the group description pp, G1 , G2 , GT , eq and that k ‌ q. First and similarly to the proof of Theorem 7.1, we discuss the group elements output by the reduction R and their representations. Then, we describe the unbounded adversary A and the meta-reduction M, also given in Figures 7 and 8. Note that by now, we assume that the readers are familiar with the notations and underlying ideas of the proof of Theorem 7.1, as we will refer back to these ideas. We also without loss of generality assume that for each run of A, the reduction receives a forgery σ p˚,jq “ pAp˚,jq , ep˚,jq q—in the case that A or the reduction aborts that run, we let Ap˚,jq “ 0G1 . Also, throughout this proof, we will denote the values defined in the j-th rewinding of A with the superscript pjq. Reduction R. The reduction takes as input the SDH instance pG1 , pX1,i qiPrd1 s , G2 , pX2,i qiPrd2 s q and runs A at most r times with the ability to interleave the executions. Then, for the j-th run (j P rrs) of the adversary, the settings of the reduction R is as follows: pjq

‚

9

pjq

pjq

pjq

Public parameters and key: These are the group elements G1 , H , G2 , X 2,1 output along with their algebraic descriptions f⃗pjq , ⃗g pjq P Zdp1 `r`1 , ⃗apjq , ⃗bpjq P Zdp2 `1 . The representations describe these elements with respect to the group elements the reduction has previously seen including the SDH instance and the forgeries from previously completed runs denoted Ap˚,nq for the forgery in the n-th run. We note

Sending the same elements over rewound runs does not increase the reduction’s success probability, as A can pick its outputs by evaluating a random function (defined by its random-tape) on its view so far. The meta-reduction can efficiently simulate this via lazy-sampling.

30

pjq

that if the n-th run (n P rrs) is still incomplete (so Ap˚,nq is undefined), we let fd1 `n “ 0 for simplicity. Then, the representations satisfy the following equations pjq

pjq

G1 “ f0 G1 `

d1 ÿ

r ÿ

fnpjq X1,n `

n“1

H

pjq

pjq

“ g0 G1 `

d1 ÿ

pjq

pjq

d2 ÿ

pjq

(12)

pjq

(13)

n“1 r ÿ

gnpjq X1,n `

n“1

G2 “ a0 G2 `

fd1 `n Ap˚,nq , gd1 `n Ap˚,nq ,

n“1

apjq n X2,n ,

pjq

pjq

X 2,1 “ b0 G2 `

n“1

d2 ÿ

bpjq n X2,n .

(14)

n“1

Also, if for all completed run n, Ap˚,nq is computed as a linear combination of G1 , X1,1 , . . . , X1,d1 , we pjq

pjq

pjq

pjq

can still describe G1 , H with polynomials f pjq , g pjq of degree at most d1 . Moreover, G2 , X 2,1 can always be described with polynomials apjq , bpjq of degree at most d2 . Throughout the proof, we will refer to f pjq , g pjq , apjq , bpjq as polynomials instead. pjq ‚ Signing queries: As the output of the i-th signing query, the group element A can be described with i α ⃗ pi,jq P Zdp1 `r`1 such that pjq

Ai

pi,jq

“ α0

G1 `

d1 ÿ

αnpi,jq X1,n `

n“1

r ÿ

pi,jq

αd1 `n Ap˚,nq ,

n“1

pi,jq

Similar to the above, we let αd1 `n “ 0 if Ap˚,nq is not yet defined. Also, if Ap˚,nq ’s are computed as a pjq

linear combination of G1 , X1,1 , . . . , X1,d1 , we can write Ai degree at most d1 .

“ αpi,jq pxqG1 for some polynomial αpi,jq of

The pd1 , d2 q-SDH solution: Finally, R returns the SDH solution pe1 , Z ˚ q which can be described with ζ⃗ P Zdp1 `r`1 where d1 r ÿ ÿ Z ˚ “ ζ0 G1 ` ζn X1,n ` ζd1 `j Ap˚,jq . n“1

j“1

Unbounded adversary A. The adversary A, given in Figure 7, is similar to the one in the non-rewinding proof. However, its random coins are now two (exponentially large) random functions F1 : G21 ˆG22 Ñ Zkp , F2 : G21 ˆ G22 ˆ pZ2p ˆ G1 qq Ñ rqs. These in particular are used to control randomnesses for different rewound runs of itself (without knowing that it has been rewound). The key steps to A are as follows: Processing the public parameters and the verification key: Compute x “ dlogG2 X 2,1 . The adversary A aborts if G1 “ 0G1 or G2 “ 0G2 . (This does not occur in the real SUF1 game.) ‚ Selecting signing query: Compute pµl qlPrks Ð F1 pG1 , H, G2 , X 2,1 q and setup m ⃗ Ð pµ 1 , . . . , µ1 , . . . , loooomoooon ‚

q{k times 1 µ k , . . . , µk q. Then, request q signing queries pAi , ei q Ð Spmi q. If ei “ ei1 for i ‰ i P rqs or the signatures loooomoooon q{k times

do not verify or µi “ µi1 for some i ‰ i1 P rks, A aborts. ˚ ‚ Forgery: Compute i Ð F2 pG1 , H, G2 , X 2,1 , tpmi , ei , Ai quiPrqs q10 , set m˚ Ð minpZp ztml ulPrks q, i.e., the ˚

`m H minimum element not used as queries, e˚ “ ei˚ and A˚ “ G1x´e . ˚

It is easy to see that A wins in the SUF1 game unless it aborts (when ei ’s or mi ’s contain duplicates—this `˘ ` ˘ 1 2 occurs with probability at most p 2q ` k2 q{p ď q2 {p). Hence, Advsuf BBS1 pA, λq ě 1 ´ q {p. 10

The tuples of messages and signatures are sorted before evaluating F2 . This is to avoid the reduction gaining advantage by simply reordering the oracle replies over several runs.

31

Algorithm AS pG1 , H, G2 , X 2,1 q: if G1 “ 0G1 Y G2 “ 0G2 then return K 2

2

k

2

2

2

F1 Ð$ tf : G1 ˆ G2 Ñ Zp u

// Random functions q

F2 Ð$ tf : G1 ˆ G2 ˆ pZp ˆ G1 q Ñ rqsu pµl qlPrks Ð F1 pG1 , H, G2 , X 2,1 q ; x Ð dlogG pX 2,1 q 2

m ⃗ Ð pµ µk , . . . , µk q 1 , . . . , µ1 , . . . , loooooomoooooon loooooomoooooon q{k times

q{k times

for i P rqs : pσi “ pAi , ei qq Ð$ Spmi q if pDi P rqs : BBS.VerppG1 , H, G2 q, X 2,1 , mi , σi q “ 0q Y 1

pDi ‰ i P rqs : ei “ ei1 Y Di ‰ i1 P rks : µi “ µi1 q then return K i

˚

Ð$ F2 pG1 , H, G2 , X 2,1 , tpmi , ei , Ai quiPrqs q // The message-signature tuples are sorted.

m˚ Ð min pZp ztµl ulPrks q ˆ ˆ ˙˙ G `m˚ H return m˚ , A˚ “ 1x´e , ei˚ i˚

Fig. 7. Unbounded adversary A. The integers k and q are defined as in the lemma statement. The code in dashed boxes indicates the difference from the case k “ 1.

Meta-reduction M: Now, we describe the meta-reduction (also given in Figure 8) playing the pd1 , d2 q-DL game and running the reduction R as follows: pd1 , d2 q-SDH instance for R: This is simply forwarding its pd1 , d2 q-DL instance G1 , X1,1 , . . . , X1,d1 , G2 , X2,1 , . . . , X2,d2 . ‚ Simulating random functions F1 and F2 : Since the meta-reduction is not unbounded, it needs to simulate the random functions F1 and F2 to be consistent over all simulated runs. This is done by lazysampling, i.e., when computing F1 p¨q, F2 p¨q on a new input, it samples a uniformly random element from the co-domain of the functions and records the input-output pair in a table. To compute the function on an input for the second time, the meta-reduction looks up the table for the recorded value. In the pseudocode, we model these as random oracles that M simulates. ‚ For each run of A: Denoted with the simulated adversary B which the reduction is given access to. The runs are indexed by j P rrs.

‚

pjq

´ The reduction R returns the group elements G1 , H pjq

pjq

pjq

pjq

, G2 , X 2,1 . Here, M aborts this particular

pjq

run if G1 and G2 are not generators. Note that these elements come with their algebraic representations which defines the polynomials f pjq , g pjq , apjq , bpjq (assuming that all the forgeries Ap˚,jq returned by M are constructed as linear combinations of X1,i ). We may assume without loss of generality that these are consistent over all runs for the same group elements; otherwise, the meta-reduction can stick to the first representation. pjq

pjq

pjq

pjq

pjq

´ Selecting the signing query: Compute pµl qlPrks Ð$ F1 pG1 , H , G2 , X 2,1 q (with F1 simulated as described above). Then, structure the message queries m ⃗ pjq exactly as A does. ´ Processing the signatures: This is done after all the queries have been made. The meta-reduction replicates the aborts in a particular run of A if one of the following occurs: pjq

pjq

pjq

(a) There exists i P rqs such that the signature pAi , ei q is not valid for mi . pjq pjq (b) There exists i ‰ i1 P rqs such that ei “ ei1 . pjq pjq (c) There exists i ‰ i1 P rks such that µi “ µi1 . 32

Algorithm Mpinpq:

Oracle F1 pstrq:

pG1 , pX1,i qiPrd1 s , G2 , pX2,i qiPrd2 s q Ð inp Mapping F1 : t0, 1u

k

˚

Ñ Zp ; F2 : t0, 1u

// str “ pG1 , H, G2 , X 2,1 q

˚

if F1 rstrs “ K then

Ñ rqs

k

F1 rstrs Ð$ Zp

// For simulating oracles F1 , F2

return F1 rstrs

Mapping cmpt-ord : rrs Ñ rrs // Keep track of completed run ordering

Oracle F2 pstrq:

started, completed Ð 0 // str “ pG1 , H, G2 , X 2,1 , tpmi , σi quiPrqs q

// Count number of started & completed runs 1

˚

⃗ Ð$ R pe , Z , ζq

ÂF1 ,F2

// Z ˚ “ ζ0 G1 `

if F2 rstrs “ K then pinpq

F2 rstrs Ð$ rqs

řd1

i“1 ζi X1,i `

řr

p˚,jq j“1 ζd1 `j A

return F2 rstrs

1

return x s.t. xG1 “ X1,1 X ζpxqpx ´ e q “ 1 pjq

Algorithm pBF1 ,F2 qS pG1 , H

pjq

pjq

pjq

, G2 , X 2,1 , f⃗pjq , ⃗ g pjq , ⃗ apjq , ⃗bpjq q:

pjq pjq pjq pjq // f⃗ , ⃗ g ,⃗ a , ⃗b satisfy (12–14), and j P rrs denotes the run’s numbering

if G1 “ 0G1 Y G2 “ 0G2 then return K started Ð started ` 1

pjq

,a

pjq

‰0

// Note that started “ j pjq

pjq

// f

pµl qlPrks Ð F1 pG1 , H pjq

pjq

pjq

pjq

, G2 , X 2,1 q

pjq

pjq

pjq

m ⃗ pjq Ð pµ 1 , . . . , µ1 , . . . , µ k , . . . , µk q loooooooomoooooooon loooooooomoooooooon q{k times

q{k times

pjq pjq pjq pjq pi,jq for i P rqs : pσi “ pAi , ei q, α ⃗ q Ð$ Spmi q pjq

// Ai

pi,jq

“ α0

G1 `

řd1

ř pi,jq pi,jq X1,i ` rn“1 αd `n Ap˚,nq n“1 αn 1

pjq

pjq

pjq

pjq

if pDi P rqs : BBS.VerpX 2,1 , mi , σi q “ 0q Y pDi ‰ i1 P rqs : ei pjq

pjq

Y pDi ‰ i1 P rks : µi i

pjq

m

pjq

Ð F2 pG1 , H

p˚,jq

pjq

pjq

“ ei1 q

“ µi1 q then return K

pjq

pjq

pjq

pjq

pjq

, G2 , X 2,1 , tpmi , ei , Ai quiPrqs q pjq

Ð minpZp ztµl ulPrks q

completed Ð completed ` 1 ; cmpt-ordrcompleteds Ð j // Register the ordering of the completed runs with cmpt-ord. pjq

if Di P rqs : pb if pb

pjq

pjq

pjq pjq pjq pjq pjq pjq ´ ei a q ffl pf ` mi g qa then M abort

pjq

´ e pjq a i

degpb

pjq

q‌f

pjq

´ e pjq a i

αp˚,jq pXq Ð

pjq pjq

pjq

a

X pb

pjq

pjq

i

pjq

q “ maxtdeg a

f pjq pXq`mp˚,jq g pjq pXq bpjq pXq´e

pjq

´ e pjq a

pjq apjq pXq ipjq

, deg b

q‌g

pjq

pjq pjq

a

// BadRepcompleted

X

u then

apjq pXq pjq

return pmp˚,jq , pAp˚,jq “ αp˚,jq pxqG1 , e pjq qq i

else M abort

// BadIdxcompleted

Fig. 8. Meta-reduction M and simulated adversary B which shares global states with M. The integers k, r and q are defined as in the lemma statement. As discussed in the body, all representation vectors can be parsed as a polynomial. ⃗ we write ζ as the corresponding polynomial.) We distinguish between the meta-reductionM and the (For vector ζ, simulated adversaryB aborting with abort and return K, respectively. The code in dashed boxes indicates the difference from the case k “ 1.

33

pjq

pjq

Moreover, if for some i P rqs, pbpjq ´ ei ¨ apjq q ffl pf pjq ` mi ¨ g pjq qapjq , the meta-reduction aborts its whole algorithm.11 We denote the event that this latter abort occurs in any of the runs as BadRep. pjq ´ Forging a signature: Select mp˚,jq to be the minimal element of the set Zp ztµl ulPrks (i.e., an pjq

unused message), and compute ipjq from F2 . If ipjq is such that pbpjq ` eipjq apjq q does not divide pjq

f pjq apjq or g pjq apjq , or the degree of bpjq ´ eipjq apjq is less than the maximum of deg bpjq and deg apjq , the meta-reduction aborts its whole algorithm. pjq If neither BadIdx nor BadRep occurs, we have that the polynomial pbpjq ` eipjq apjq q divides both pjq

f pjq apjq and g pjq apjq and the degree of bpjq ´ eipjq apjq is exactly the maximum of deg bpjq or deg apjq . Then, let f pjq pXq ` mp˚,jq g pjq pXq f pjq pXq ` mp˚,jq g pjq pXq pjq a pXq “ . αp˚,jq pXq “ pjq pjq bpjq pXq ´ eipjq apjq pXq bpjq pXq{apjq pXq ´ eipjq Similar to the prior proof, we can see that αp˚,jq is a polynomial of degree at most d1 from the fact pjq that the degree of bpjq ´ eipjq apjq does not decrease; i.e., ´ ¯ ´ ¯ pjq deg αp˚,jq “ deg f pjq ` mp˚,jq g pjq ´ deg bpjq ´ eipjq apjq ` deg apjq ď d1 loooooooooooooomoooooooooooooon looooooooooooooooooooomooooooooooooooooooooon ď0

ďd1

Hence, the meta-reduction can compute the forgery pjq

σ p˚,jq “ pAp˚,jq “ αp˚,jq pxqG1 , ep˚,jq “ eipjq q ,

‚

from its pd1 , d2 q-DL instance. Note that it is easy to verify the validity of σ p˚,jq . Computing pd1 , d2 q-DL solution: Unless the meta-reduction aborts, the SDH solution pe1 , Z ˚ q from the reduction R can be written as Z ˚ “ ζpxqG1 for a degree at most d1 polynomial ζ. This is simply because Ap˚,jq can be written as αp˚,jq pxqG1 with deg αp˚,jq ď d1 (assuming that neither BadIdx nor BadRep occurs). Now, since Z ˚ “ px ´ e1 q´1 G1 , we have that ζpxqpx ´ e1 q “ 1. Thus, the discrete logarithm x can be found by computing the zeros of the polynomial ζpXqpX ´ e1 q ´ 1 and returning the one satisfying xG1 “ X1,1

Note that if neither BadIdx nor BadRep occur, R’s view is identical to its interaction with A. Also, if R wins in the pd1 , d2 q-SDH game, M also wins in the pd1 , d2 q-DL game. Hence, d-sdh A Advd-dl GGen pM, λq ě AdvGGen pR , λq ´ PrrBadIdx Y BadReps .

To bound the probability of BadIdx Y BadRep, we first define for each j P rrs, the index cmpt-ordrjs P rrs as the run-index of the j-th completed run. We refer to Figure 8 for how it is defined within the meta reduction. As an example, if the reduction starts 5 runs of A, and complete these runs in the order p2, 3, 1, 5, 4q, we have that cmpt-ordr1s “ 2 , cmpt-ordr2s “ 3 , cmpt-ordr3s “ 1 , cmpt-ordr4s “ 5 , cmpt-ordr5s “ 4 . We note that this unusual definition is used only to deal with the ability of the reduction to concurrently run many executions of A (and thus further generalizing our result). If R runs each execution of A sequentially, cmpt-ord is simply an identity map. Moreover, we remark that the forgery containing Ap˚,jq will only be sent to the reduction if the j-th run is completed. We remark that we cannot simply bound PrrBadReps separately via another meta-reduction M1 . This is because it could be the case that BadRep occurs at some point after the event BadIdx already occurred; 11

We make note of the distinction of the meta-reduction aborting its whole algorithm and it aborting a particular rewound run. The former means aborting its whole interaction with R. However, the latter means simulating the same aborts that A would do, and R is still free to run more instances of A.

34

meaning such meta-reduction M1 would not be able to compute a forgery on that run. To this end and as an intermediate step, we will define a sequence of events BadIdxj and BadRepj for j P rrs which denotes events where BadIdx or BadRep are triggered in the j-th completed run (i.e., the cmpt-ordrjs-th run). Then, we will write the event BadIdx Y BadRep so that we can easily consider the two cases without the undesirable situation above. For the definition of BadIdxj and BadRepj , we will use J “ cmpt-ordrjs for readability and define them as follows: pJq

‚

BadIdxj : The random index ipJq leads to the meta-reduction aborting, i.e., the polynomial pbpJq ´eipJq apJq q does not divide f pJq or g pJq , or pJq

degpbpJq ´ eipJq apJq q ă maxtdeg bpJq , deg apJq u . pJq

‚

pJq

BadRepj : There exists i P rqs such that bpJq ´ ei apJq ffl pf pJq ` mi g pJq qapJq .

Next, we can rewrite the event BadIdx Y BadRep as follows BadIdx Y BadRep “

r ď

pBadIdxj Y BadRepj q

j“1 r ď

˜ j´1 č

j“1

n“1

r ď

˜ j´1 č

j“1

n“1

“

“

¸ p␣BadIdxn X ␣BadRepn q X pBadIdxj Y BadRepj q ¸ p␣BadIdxn X ␣BadRepn q X pBadRepj Y p␣BadRepj X BadIdxj qq .

The second and third equalities follow from the fact that for boolean values x, y, x Y y “ x Y p␣x X yq (and inductively applying it). We additionally define two more events BadIdx1j , BadRep1j such that BadRep1j :“

j´1 č

p␣BadIdxn X ␣BadRepn q X BadRepj

n“1

BadIdx1j :“

j´1 č

p␣BadIdxn X ␣BadRepn q X ␣BadRepj X BadIdxj .

n“1

Intuitively, BadRep1j is the event that the meta-reduction has not aborted in the first j ´ 1 completed runs, and BadRepj occurs. On the other hand, BadIdx1j is the event that the meta-reduction has not aborted in pcmpt-ordrjsq

the first j ´ 1 completed runs and all the ei ’s does not trigger the BadRepj abort condition, but the sampled index ipcmpt-ordrjsq triggers BadIdxj . Now, we can write ¸ ˜ ¸ ˜ r r r ď ď ď 1 1 1 1 BadIdxj . BadRepj Y BadIdx Y BadRep “ pBadRepj Y BadIdxj q “ j“1

j“1

j“1

Thus, with the union bound, we will bound the following probability. « ff « ff r r ď ď PrrBadIdx Y BadReps ď Pr BadRep1j ` Pr BadIdx1j . j“1

j“1

Importantly, we stress that instead of bounding BadIdx and BadRep directly, we will bound the probability that these two events occur instead. This is because BadIdx does not necessarily guarantee that the given algebraic representation always leads to a well-defined polynomials, and BadRep does not necessarily guarantee that prior to the event triggering the meta-reduction can compute the forgeries for the prior runs. In contrast, with how BadRep1j and BadIdx1j are defined, these conditions are guaranteed. The two following lemmas then conclude the proof. \ [ 35

Lemma 7.5. Pr

ı r2 ¨ pk ` 1q 1 BadIdx . j ď j“1 q

”Ť r

Lemma 7.6.” There exists aı meta-reduction M1 playing the pd1 , d2 q-DL game running in time roughly tR Ťr pd1 ,d2 q-dl 1 such that Pr pM1 , λq. j“1 BadRepj ď AdvGGen Ťr Proof (of Lemma 7.6). We first consider the event j“1 BadRep1j . For simplicity and readability, we use the shorthand J “ cmpt-ordrjs to denote the run specified in the event BadRep1j throughout this proof. By the definition of BadRep1j , when the event is triggered, the meta-reduction M is able to forge on all prior completed runs as BadIdxn does not occur for n ă j. Hence, in all the runs the forgery Ap˚,Jq can be computed by the meta-reduction as a linear combination of G1 , X1,1 , . . . , X1,d1 . Thus, the representation pJq

pJq

pJq

pJq

pJq

of the group elements G1 , H , G2 , X 2,1 and Ai defines polynomials f pJq , g pJq , apJq , bpJq , and αpi,Jq , respectively. These polynomials are of degree at most d1 or d2 depending on which group it is in. Therefore, we can construct another meta-reduction M1 that simulates the adversary A in the same manner as M. However, when one of BadRep1j occurs, M1 will try to extract a DL solution. Let the i-th signing query of the j-th completed run (which corresponds to the J-th run) be the query which trigger the pJq pJq pJq pJq event. In particular, pbpJq ´ ei apJq q ffl pf pJq ` mi ¨ g pJq qapJq , and the signature pAi , ei q verifies, so we have that ¯ ´ pJq ¯ ´ pJq pJq pJq pJq pJq pJq pJq “ e G1 ` mi H , G2 e Ai , X 2,1 ´ ei G2 Accordingly, we have pJq

αpi,Jq pxq ¨ pbpJq pxq ´ ei apJq pxqq “ pf pJq pxq ` mpJq g pJq pxqq ¨ apJq pxq . Because of the indivisbility condition, the underlying polynomials on both sides are not identical, so x is one of the zeros of the non-zero polynomial pJq

pJq

hpXq “ αpi,Jq pXq ¨ pbpJq pXq ´ ei apJq pXqq ´ pf pJq pXq ` mi

¨ g pJq pXqq ¨ apJq pXq .

Thus, M1 simply factors h and checks which zero is actually a pd1 , d2 q-DL solution. The advantage bound follows via the success of this reduction. \ [ 7.4

Proof of Lemma 7.5

We first observe that the probability of the event can be bounded by the winning probability of any adversary C in the game Rewind (defined in Figure 9). The game models the behavior of the unbounded adversary A and the adversary B simulated by the meta-reduction into two phases: (1) Selecting signing queries (Chal1 ) and (2) Selecting index i˚ P rqs to forge on (Chal2 ). In particular, for any adversary C, its winning probability is C AdvRewind p,d1 ,d2 ,k,q,r pC, λq :“ PrrRewindp,d1 ,d2 ,k,q,r pλq “ 1s . Note that there exists an adversary C such that « ff r ď 1 Pr BadIdxj ď AdvRewind p,d1 ,d2 ,k,q,r pC, λq . j“1

This follows from how the unbounded adversary A and the meta-reduction M reply to R, and that the Ťr event j“1 BadIdx1j corresponds exactly to when win is set to true. Note that the abort conditions in the challenge oracle Chal2 exactly corresponds to how each event BadIdx1j is defined. Throughout this section, we will not use the notation cmpt-ordrjs for readability and refer to the run indices as j P rrs instead. We assume that C makes at most r queries to Chal1 and Chal2 . Moreover, we assume without loss of generality that for any C, there exists an adversary C 1 making r queries to Chal1 and “only 1 query to Chal2 ” such that Rewind 1 AdvRewind p,d1 ,d2 ,k,q,r pC, λq ď r ¨ Advp,d1 ,d2 ,k,q,r pC , λq . 36

Game RewindC p,d ,d ,k,q,r pλq:

Oracle Chal1 pf, g, a, bq:

Q1 , Q2 Ð 0 ; win Ð false

if deg f ą d1 Y deg g ą d1 Y

1

C

Chal1 ,Chal2

2

deg a ą d2 Y deg b ą d2 Y

λ

p1 q

f “ 0 Y a “ 0 then abort

return win X pQ1 ď rq X pQ2 ď rq

Q1 Ð Q 1 ` 1 µ ⃗

pQ1 q q

pQ1 q

pf m ⃗

“ pµl

pQ1 q

k lPrks Ð$ Zp

pQ q pQ q pQ q , g 1 , a 1 , b 1 q Ð pf, g, a, bq

pQ1 q pQ q pQ q pQ q pQ1 q Ð pµ , . . . , µ1 1 , . . . , looooooooooomooooooooooon µk 1 , . . . , µk 1 q 1 looooooooooomooooooooooon q{k times

q{k times

pQ q return pµl 1 qlPrks

Oracle Chal2 pj P rQ1 s, pei qiPrqs q pjq

if pDi P rqs : pb

Q2 Ð Q2 ` 1; i if pb

pjq

˚

pjq

´ ei˚ a

degpb

pjq

´ ei a

pjq

q ffl pf

pjq

pjq pjq

pjq

` mi g

qa

pjq

pjq

q Y pDi ‰ j P rqs : ei “ ej q then abort

Ð$ rqs q ffl f

pjq pjq

a

Y pb

´ ei˚ a

q ffl g

pjq pjq

a

Y

pjq pjq pjq pjq q ă maxtdeg a , deg b u then i

´e ˚a

win Ð true ˚

return i

Fig. 9. Rewinding game.

This follows simply from a guessing argument where C 1 guesses which query to Chal2 made by C lead to win Ð true being set. Accordingly, we can also assume that C 1 makes all the Chal1 queries before Chal2 , since the Chal1 queries made after the only Chal2 query does not influence the winning event. Hence, we will analyze the winning probability of C 1 making only 1 query to Chal2 after r queries to Chal1 instead. In particular, we assume without loss of generality that C 1 is deterministic and denote the sequence of Chal1 outputs as µ ⃗ “ p⃗ µp1q , . . . , µ ⃗ prq q (as random variables), we define the corresponding polynomial f, g, a, b in the j-th oracle query as a function p¨qpjq p⃗ µq of all the sampled messages µ ⃗ “ p⃗ µpjq “ pjq k pjq p1q pj´1q pµl qlPrks P Zp qjPrrs . Note that p¨q only depends on the first j ´ 1 elements µ ⃗ ,...,µ ⃗ of µ ⃗. We define the functions Xj,l p⃗ µq determined by the value of µ ⃗ for j P rrs, l P rks as ˇ$ ,ˇ pjq ˇ& bpjq p⃗ µq ` e ¨ apjq p⃗ µq ‌ pf pjq p⃗ µq ` µl ¨ g pjq p⃗ µqqapjq p⃗ µq X .ˇˇ ˇ ˇ Xj,l p⃗ µq :“ ˇˇ e P Zp : pbpjq p⃗ µq ` e ¨ apjq p⃗ µq ffl f pjq p⃗ µqapjq p⃗ µq Y -ˇˇ ˇ% pjq pjq pjq pjq b p⃗ µq ` e ¨ a p⃗ µq ffl g p⃗ µqa p⃗ µqq i.e., the number of bad e P Zp where the divisibility condition is not satisfied, meaning our meta-reduction will not be able to simulate the forgery. Then, we have that if C 1 řchooses run-index j P rrs for the query to Chal2 , its winning probability given that µ ⃗ “ ⃗µ is at most

mint

k µq,qu`1 l“1 Xj,l p⃗

q

. This is simply because of how the winning condition and Xj,l pjq

are defined. Here, we take into account the particular event where the degree degpbpjq ´ ei˚ apjq q decreases from the maximum of deg apjq and deg bpjq with the 1{q additive term. Note that this follows by a similar argument as in Lemma 7.2, because only one e P Zp can cause that by cancelling out the leading coefficient. Given that µ ⃗ “ ⃗µ, the optimal strategy for C 1 is to choose the index j P rrs with the maximum chance. mintmax

řk

Xj,l p⃗ µq,qu`1

jPrrs l“1 Therefore, the winning probability of C 1 is at most . q We can then say that ÿ ˇ “ ‰ 1 AdvRewind Prµ⃗ Ð$ pZkp qr r⃗ µ “ ⃗µs ¨ Pr C 1 wins ˇ µ ⃗ “ ⃗µ p,d1 ,d2 ,q,r pC , λq “

⃗ µ

37

˜ # + ¸ k ÿ 1ÿ µ “ ⃗µs min max ď Pr $ k r r⃗ Xj,l p⃗µq, q ` 1 q ⃗µ µ⃗ Ð pZp q jPrrs l“1 « # +ff k ÿ 1 1 “ Eµ⃗ min max Xj,l p⃗ µq, q ` . q q jPrrs l“1 The first equality follows from C 1 only depending on the outputs of the oracle Chal. The second inequality follows from the observation above. The last equality follows from definition of expectation over µ ⃗. Therefore, our goal is to compute the expectation of the maximum. !To do so, we prove the following claim ) řk lower bounding the probability that the random variable Y p⃗ µq “ min maxjPrrs l“1 Xj,l p⃗ µq, q (where the randomness comes from µ ⃗ ) is upper bounded by some integer t ě 1. We now prove the following identity on the expectation of a non-negative discrete random variable. Claim. For a discrete random variable X P r0, N s, ErXs “

řN

t“1 PrrX ě ts.

Proof (of Claim). Consider N ÿ

t ¨ PrrX “ ts “

ErXs “ t“1

q ÿ t ÿ

PrrX “ ts “

t“1 k“1

q ÿ q ÿ

PrrX “ ts “

k“1 t“k

q ÿ

PrrX ě ks .

k“1

řt The second equality follows from expanding t “ k“1 1. The third equality follows from swapping the order of the sum (since k starts from 1 to t, t starts from k to q). The last equality follows from X only taking positive integer values and is bounded by N . \ [ The claim then gives us Eµ⃗ rY p⃗ µqs “

řq

µq ě ts. Next, we observe that for each t P rqs, ⃗ rY p⃗ t“1 Prµ

ff « q ff « k k r ď ÿ ÿ ÿ Xj,l p⃗ µq ě t . PrrY p⃗ µq ě ts “ Prµ⃗ Ð$ pZkp qr p Xj,l p⃗ µq ě tq ď Prµ⃗ Ð$ pZkp qr j“1 l“1

j“1

l“1

The first equality follows by definition, and the second inequality follows from the union bound. Hence, µqs ď Eµ⃗ rY p⃗

q ÿ r ÿ

« Prµ⃗ Ð$ pZkp qr

t“1 j“1

“

k ÿ

Eµ⃗ j“1

ff Xj,l p⃗ µq ě t “

ff Xj,l p⃗ µq “

l“1

q r ÿ ÿ

« Prµ⃗ Ð$ pZkp qr

j“1 t“1

l“1

«

r ÿ

k ÿ

r ÿ k ÿ

k ÿ

ff Xj,l p⃗ µq ě t

l“1

Eµ⃗ rXj,l p⃗ µqs

j“1 l“1

The second equality follows by swapping the summation order. The second to last equality follows again from the above claim. The last equality follows from linearity of expectation. Finally, we claim that Eµ⃗ rXj,l p⃗ µqs ď 1 for all j P rrs, l P rks, which concludes the proof as 1 AdvRewind p,d1 ,d2 ,q,r pC , λq ď

Eµ⃗ rY p⃗ µqs ` 1 r ¨ pk ` 1q ď . \ [ q q

Claim. For j P rrs, l P rks, Eµ⃗ rXj,l p⃗ µqs ď 1. pnq

Proof. Note that f pjq , g pjq , apjq , bpjq all depend only on the first j ´ 1 values in µ ⃗ “ p⃗ µpnq “ pµl qlPrks qnPrrs , given any ⃗µr1:j´1s “ p⃗ µpnq qnPrj´1s P pZkp qj´1 these polynomials are fixed. Then, we consider the conditioned 38

expectation Eµ⃗ pjq rXj,l p⃗µr1:j´1s }⃗ µj qs “ “

1 pk

ÿ

Xj,l p⃗µr1:j´1s }⃗µpjq q

⃗ µpjq PZk p

1 pk´1

ÿ pjq

1 p k´1

⃗ µrksztlu PZp

ď

1 pk´1

ÿ

ÿ

Xj,l p⃗µr1:j´1s }⃗µpjq }µpjq q rksztlu l

pjq

µl PZp

1“1

pjq ⃗ µrksztlu PZk´1 p

The second to last inequality follows from the same observation as in the proof of Lemma 7.2: in particular, for , the number of e P Zp that is counted towards Xj,l p⃗µr1:j´1s }⃗µpjq } any fixed ⃗µr1:j´1s P pZkp qj´1 and ⃗µpjq rksztlu rksztlu pjq

pjq

µl q over all values of µl P Zp is at most p. With this, we can the the expectation over µ ⃗ r1:j´1s and the claim follows.

\ [

Acknowledgements The authors wish to thank Kenneth Paterson for discussions at an earlier stage of the work and discussions on the running time of our reduction. Chairattana-Apirom and Tessaro’s research was partially supported by NSF grants CNS-2026774, CNS-2154174, CNS-2426905, a gift from Microsoft, and a Stellar Development Foundation Academic Research Award.

References AFG` 10. Masayuki Abe, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. Structurepreserving signatures and commitments to group elements. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 209–236. Springer, Berlin, Heidelberg, August 2010. AH74. Alfred V Aho and John E Hopcroft. The design and analysis of computer algorithms. Pearson Education India, 1974. AHN` 17. Masayuki Abe, Dennis Hofheinz, Ryo Nishimaki, Miyako Ohkubo, and Jiaxin Pan. Compact structurepreserving signatures with almost tight security. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 548–580. Springer, Cham, August 2017. ASMC13. Man Ho Au, Willy Susilo, Yi Mu, and Sherman S. M. Chow. Constant-size dynamic k-times anonymous authentication. IEEE Syst. J., 7(2):249–261, 2013. BB08. Dan Boneh and Xavier Boyen. Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology, 21(2):149–177, April 2008. BBM00. Mihir Bellare, Alexandra Boldyreva, and Silvio Micali. Public-key encryption in a multi-user setting: Security proofs and improvements. In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 259–274. Springer, Berlin, Heidelberg, May 2000. BBS04. Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 41–55. Springer, Berlin, Heidelberg, August 2004. BDJR97. Mihir Bellare, Anand Desai, Eric Jokipii, and Phillip Rogaway. A concrete security treatment of symmetric encryption. In 38th FOCS, pages 394–403. IEEE Computer Society Press, October 1997. BDLR25. Renas Bacho, Sourav Das, Julian Loss, and Ling Ren. Glacius: Threshold schnorr signatures from DDH with full adaptive security. In Serge Fehr and Pierre-Alain Fouque, editors, EUROCRYPT 2025, Part II, volume 15602 of LNCS, pages 304–334. Springer, Cham, May 2025. BG04. Daniel R. L. Brown and Robert P. Gallant. The static Diffie-Hellman problem. Cryptology ePrint Archive, Report 2004/306, 2004. BHJ` 15. Christoph Bader, Dennis Hofheinz, Tibor Jager, Eike Kiltz, and Yong Li. Tightly-secure authenticated key exchange. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part I, volume 9014 of LNCS, pages 629–658. Springer, Berlin, Heidelberg, March 2015.

39

BJLS16.

BKP14.

BL10. BW24.

CAT26.

CDL16.

Che06. Che10.

CJ07.

CL04.

CW13.

FK23. FKL18.

Gen06. GHO20.

HHK18.

HJ12.

HK12. HT16.

KZG10.

Leo06.

Christoph Bader, Tibor Jager, Yong Li, and Sven Schäge. On the impossibility of tight cryptographic reductions. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 273–304. Springer, Berlin, Heidelberg, May 2016. Olivier Blazy, Eike Kiltz, and Jiaxin Pan. (Hierarchical) identity-based encryption from affine message authentication. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 408–425. Springer, Berlin, Heidelberg, August 2014. Ernie Brickell and Jiangtao Li. A pairing-based daa scheme further reducing tpm resources. In International Conference on Trust and Trustworthy Computing, pages 181–195. Springer, 2010. Renas Bacho and Benedikt Wagner. Tightly secure non-interactive BLS multi-signatures. In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part II, volume 15485 of LNCS, pages 397–422. Springer, Singapore, December 2024. Rutchathon Chairattana-Apirom and Stefano Tessaro. On the concrete security of BBS/BBS+ signatures. In Goichiro Hanaoka and Bo-Yin Yang, editors, Advances in Cryptology – ASIACRYPT 2025, pages 402– 434, Singapore, 2026. Springer Nature Singapore. Jan Camenisch, Manu Drijvers, and Anja Lehmann. Anonymous attestation using the strong diffie hellman assumption revisited. In Trust and Trustworthy Computing: 9th International Conference, TRUST 2016, Vienna, Austria, August 29-30, 2016, Proceedings 9, pages 1–20. Springer, 2016. Jung Hee Cheon. Security analysis of the strong Diffie-Hellman problem. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 1–11. Springer, Berlin, Heidelberg, May / June 2006. Liqun Chen. A daa scheme requiring less tpm resources. In Information Security and Cryptology: 5th International Conference, Inscrypt 2009, Beijing, China, December 12-15, 2009. Revised Selected Papers 5, pages 350–365. Springer, 2010. Benoı̂t Chevallier-Mames and Marc Joye. A practical and tightly secure signature scheme without hash function. In Masayuki Abe, editor, CT-RSA 2007, volume 4377 of LNCS, pages 339–356. Springer, Berlin, Heidelberg, February 2007. Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 56–72. Springer, Berlin, Heidelberg, August 2004. Jie Chen and Hoeteck Wee. Fully, (almost) tightly secure IBE and dual system groups. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 435–460. Springer, Berlin, Heidelberg, August 2013. Dankrad Feist and Dmitry Khovratovich. Fast amortized KZG proofs. Cryptology ePrint Archive, Report 2023/033, 2023. Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 33–62. Springer, Cham, August 2018. Craig Gentry. Practical identity-based encryption without random oracles. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 445–464. Springer, Berlin, Heidelberg, May / June 2006. Sanjam Garg, Mohammad Hajiabadi, and Rafail Ostrovsky. Efficient range-trapdoor functions and applications: Rate-1 OT and more. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 of LNCS, pages 88–116. Springer, Cham, November 2020. Julia Hesse, Dennis Hofheinz, and Lisa Kohl. On tightly secure non-interactive key exchange. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 65–94. Springer, Cham, August 2018. Dennis Hofheinz and Tibor Jager. Tightly secure signatures and public-key encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 590–607. Springer, Berlin, Heidelberg, August 2012. Dennis Hofheinz and Eike Kiltz. Programmable hash functions and their applications. Journal of Cryptology, 25(3):484–527, July 2012. Viet Tung Hoang and Stefano Tessaro. Key-alternating ciphers and key-length extension: Exact bounds and multi-user security. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 3–32. Springer, Berlin, Heidelberg, August 2016. Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 177–194. Springer, Berlin, Heidelberg, December 2010. Vladimir Konstantinovich Leont’ev. Roots of random polynomials over a finite field. Mathematical Notes, 80, 2006.

40

Lip12.

Helger Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS, pages 169–189. Springer, Berlin, Heidelberg, March 2012. LKWL26. Tobias Looker, Vasilis Kalos, Andrew Whitehead, and Mike Lodder. The BBS Signature Scheme. InternetDraft irtf-cfrg-bbs-signatures-10, Internet Engineering Task Force, January 2026. Work in Progress. mat. BBS+ implementation. Accessed: 2024-09-29. mic. BBS implementation. Accessed: 2024-09-29. Pat08. Jacques Patarin. A proof of security in Op2n q for the Benes scheme. In Serge Vaudenay, editor, AFRICACRYPT 08, volume 5023 of LNCS, pages 209–220. Springer, Berlin, Heidelberg, June 2008. PS16. David Pointcheval and Olivier Sanders. Short randomizable signatures. In Kazue Sako, editor, CTRSA 2016, volume 9610 of LNCS, pages 111–126. Springer, Cham, February / March 2016. Sch15. Sven Schäge. Tight security for signature schemes without random oracles. Journal of Cryptology, 28(3):641–670, July 2015. TAKS07. Patrick P. Tsang, Man Ho Au, Apu Kapadia, and Sean W. Smith. Blacklistable anonymous credentials: blocking misbehaving users without ttps. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 72–81. ACM Press, October 2007. TZ23. Stefano Tessaro and Chenzhi Zhu. Revisiting BBS signatures. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, pages 691–721. Springer, Cham, April 2023. w3c. Data Integrity BBS Cryptosuites v1.0. Accessed: 2024-09-29. Y` 00. Chee-Keng Yap et al. Fundamental problems of algorithmic algebra, volume 49. Oxford University Press Oxford, 2000.

41

A

Proof of Lemma 4.3

For simplicity, assume that all algorithms implicitly takes as input the group description pp, G1 , G2 , GT , eq. ⃗ G2 , X2,1 , making q signing queries on Consider a SUF1 adversary A, taking as input the group elements G1 , H, 1 ℓ ˚ ˚ distinct messages m ⃗ 1, . . . , m ⃗ q P Zp and returning a forgery pm ⃗ , σ “ pA˚ , e˚ qq such that A˚ “ x´e ˚ pG. 1 ` řℓ ˚ ⃗ m ⃗ rjsHrjsq. We consider the following events: j“1

řℓ řℓ ⃗ ⃗ Coll: For some i ‰ i1 P rqs, j“1 m ⃗ i rjsHrjs “ j“1 m ⃗ i1 rjsHrjs, or for the forgery pm ⃗ ˚ , σ ˚ q, there exists řℓ ř ℓ ˚ ⃗ ⃗ an index i P rqs such that j“1 m ⃗ i rjsHrjs “ j“1 m ⃗ rjsHrjs. ‚ Forgeℓ : Coll does not occur and A wins in the game. ‚

Then, it is easy to see that 1

Advsuf BBS pA, λq ď PrrColls ` PrrForgeℓ s . The two following claims then conclude the proof.

[ \

Claim. There exists an adversary BColl running in time roughly that of A such that PrrColls ď Advdlog GGen pA, λq `

1 . p

Proof. Consider BColl defined as follows: ⃗ X2,1 Ð xG2 where α ⃗ Ð$ Zℓ ⃗ Ðα Takes as input the group elements G1 , Y P G1 , G2 . Set H ⃗ G1 ` βY, ⃗, β p and x Ð$ Zp . ⃗ ‚ Run A with input pG1 , H, G2 , X2,1 q 1 ‚ For each signing query m ⃗ i , computes the signature σi by sampling ei Ð$ Zp and Ai Ð x´e pG1 ` i řℓ ⃗ ⃗ i rjsHrjsq. j“1 m ⃗˚ , σ ˚ q is given, check if Coll occurs. If so, let m ‚ After the forgery pm ⃗ ‰m ⃗ 1 be the two messages triggering řℓ 1 ř pmrjs´ ⃗ m ⃗ rjsqαrjs ℓ the event. Then, the reduction returns ´ řj“1 if j“1 pmrjs ⃗ ´m ⃗ 1 rjsqβrjs ‰ 0. Otherwise, ℓ pmrjs´ ⃗ m ⃗ 1 rjsqβrjs ‚

j“1

abort. It is clear that the running time is roughly tA . The correctness of the reduction follows from the event Coll implying that 0G1 “

ℓ ÿ

⃗ pmrjs ⃗ ´m ⃗ 1 rjsqHrjs “

j“1

ℓ ÿ

pmrjs ⃗ ´m ⃗ 1 rjsq⃗ αrjsG `

j“1

ℓ ÿ

⃗ pmrjs ⃗ ´m ⃗ 1 rjsqβrjsY .

j“1

řℓ Also, note that since β⃗ is information theoretically hidden from the view of A, the abort from j“1 pmrjs ⃗ ´ m ⃗ 1 rjsqβrjs “ 0 can only occur with probability at most 1{p. Hence, this concludes the proof. [ \ Claim. There exists an adversary B 1 against SUF’ game of BBS1 “ BBSrGGen, 1s running in time roughly that of A and making q distinct signing queries such that 1

1 PrrForgeℓ s ď Advsuf BBS1 pB , λq .

Proof. Consider B 1 playing the SUF’ game of BBS1 defined as follows: Takes as input the group elements G1 , H, G2 , X2,1 . If H “ 0G1 , make a query on message m “ 0 to ⃗ Ðα receive σ “ pA, eq and return the forgery p1, σq. Otherwise, compute H ⃗ H where α ⃗ P Zℓp . ⃗ ‚ Run A with input pG1 , H, G2 , X2,1 q. řℓ ‚ For each signing query m ⃗ i , compute m1i Ð j“1 m ⃗ i rjsαrjs, make a signing query to its oracle on m1i to receive σi “ pAi , ei q, and return σi to A.

‚

42

‚

For the forgery pm ⃗ ˚ , σ ˚ q, compute µ˚ “

řℓ

⃗ ˚ rjsαrjs and return the forgery pµ˚ , σ ˚ q. j“1 m

⃗ is uniform in The running time of B 1 is roughly that of A. Note that the view of A remains the same as H ℓ G1 and the signatures from the oracles are valid with ei uniformly random. Moreover, if H “ 0G1 , we can see that the reduction trivially wins in the game. Now, we consider when A wins the game and Coll does not occur. Since Coll does not occur and by how ⃗ we have that we set up H, (a) The signing queries m1i made by Bsuf are distinct. (b) The message µ˚ in the forgery is distinct from all the signing queries. Therefore, if A wins in the game, σ ˚ “ pA˚ , e˚ q is such that e˚ P tei uiPrqs and 1 A˚ “ x ´ e˚

˜ G1 `

ℓ ÿ j“1

¸ ⃗ m ⃗ ˚ rjsHrjs

1 “ x ´ e˚

˜ G1 `

Hence, Bsuf also wins in the SUF’ game, concluding the proof.

43

ℓ ÿ j“1

¸ m ⃗ ˚ rjs⃗ αrjsH

“

G1 ` µ˚ H . x ´ e˚ \ [

Related documents

• CBOR Object Signing and Encryption (COSE): Hash Algorithms#502494
• Efficient signature generation by smart cards#6667
• Use of the HSS/LMS Hash-Based Signature Algorithm with CBOR Object Signing and Encryption (COSE)#502381
• The Use of RSA/SHA-1 Signatures within Encapsulating Security Payload (ESP) and Authentication Header (AH)#500608
• Authentication issues in low-cost RFID#163873