Chapter status: in progress

TODO:

• modify advantage notation to display the scheme

Games, Models, and Assumptions

This section presents how security assumptions and security properties of cryptographic schemes are formalized. It also gives a list of cryptographic assumptions relevant for this book (see also the ECRYPT II MAYA report).

Contents

• Big-O Notation and Negligible Functions
• Cryptographic Games
  • Game: Tentative Definition
  • Notation and Conventions for Writing Games
  • Advantage
  • Reductions
• Idealized Models
  • The Random Oracle Model
  • The Generic Group Model
  • The Algebraic Group Model
• Assumptions
  • Group Setup Algorithms
  • Assumptions in Standard Groups
    • Discrete Logarithm (DL)
    • Computational Diffie-Hellman (CDH)
    • Decisional Diffie-Hellman (DDH)
    • $q$-Discrete Logarithm ($q$-DL)
  • Assumptions in Product Groups
    • $(q_1,q_2)$-co-Discrete Logarithm ($(q_1,q_2)$-co-DL)
    • Computational co-Diffie-Hellman (co-CDH)
    • Computational co-Diffie-Hellman* (co-CDH*)
    • Computational $\psi$-co-Diffie-Hellman ($\psi$-co-CDH)
    • $(q_1,q_2)$-Strong Diffie-Hellman ($(q_1,q_2)$-SDH)
  • Assumptions in Pairing Groups
    • $(q_1,q_2)$-Bilinear Diffie-Hellman Inversion ($(q_1,q_2)$-BDHI)
    • $(q_1,q_2)$-Bilinear Strong Diffie-Hellman ($(q_1,q_2)$-BSDH)

Big-O Notation and Negligible Functions

In all the following, we consider functions from $\mathbb{N}$ to ${\mathbb{R}}^{+}=\{x\in \mathbb{R}\mid x\ge 0\}$ and we let $\lambda$ denote the variable.

A function $f$ is said to be negligible if $f\in {\lambda }^{-\omega (1)}$ or equivalently if $$\forall k\in \mathbb{N},\exists n\in \mathbb{N},\forall \lambda \ge n,f(\lambda )\le {\lambda }^{-c}.$$

In words, $f$ is negligible if it approaches zero faster than the inverse of any polynomial.

The set of all negligible functions is denoted $\mathrm{negl}.$ We often write $f(\lambda )=\mathrm{negl}(\lambda )$ in place of $f\in \mathrm{negl}.$

Cryptographic Games

Game: Tentative Definition

A game consists of a main algorithm $\mathrm{GAME}$ and a (potentially empty) finite tuple of oracle algorithms ${\text{O}}_1,\dots ,{\text{O}}_n.$ Then main algorithm (to which we simply refer as the game from here) takes as input $1^{\lambda }$ where $\lambda \in \mathbb{N}$ is an integer called security parameter and runs in three phases:

• initialization: the game initializes variables and generates some input $inp;$
• attack: the game invokes an algorithm $\mathsf{A}$ called adversary on input $inp;$ the adversary has oracle access to ${\text{O}}_1,\dots ,{\text{O}}_n;$
• finalization: when the adversary halts and returns some output $out,$ the game evaluates a predicate of $out$ and all variables and returns the truth value of this predicate.

To make this definition rigorous, the programming language used to write the game should be completely specified. Here, we will content ourselves with specifying games in pseudocode.

A very simple game called ADD drawing two random $\lambda$-bit integers and returning $\mathbf{true}$ if the adversary successfully adds them would look like this:

$$\boxed{\begin{array}{l}\text{Game ADD(1λ):}\\ a,b{\leftarrow }_{\$}\{2^{\lambda -1},\dots ,2^{\lambda }-1\}\\ c\leftarrow \mathsf{A}(a,b)\\ \mathbf{return}(c=a+b)\end{array}}$$

Notation and Conventions for Writing Games

• Given a predicate $A,$ we use $\mathbf{assert}A$ as a shorthand for $\mathbf{if}\neg A\mathbf{then}\mathbf{return}\mathbf{false}$
• Games return $\mathbf{true}$ by default, meaning if the end of the game code is reached and the game has not returned yet, then it returns $\mathbf{true}.$ Finalization often consists in returning the truth vale of $A\wedge B\wedge C\wedge \cdots .$ Under this convention, the following finalization code $$\mathbf{return}A\wedge B\wedge C$$ is equivalent to $$\begin{array}{rl}& \mathbf{assert}A\\ & \mathbf{assert}B\\ & \mathbf{assert}C\end{array}$$

Advantage

For each security parameter $\lambda ,$ a game together with an adversary define a finite probability space specified by all random choices made by the game and the random coins of the adversary. This allows to define the probability of various events related to the execution of the game with a specific adversary.

In particular, given a game $\mathrm{GAME}$ and an adversary $\mathsf{A},$ we write ${\mathrm{GAME}}^{\mathsf{A}}(1^{\lambda })\Rightarrow b,$ or simply $\mathrm{GAME}\Rightarrow b$ when the context is clear, for the event that an execution of $\mathrm{GAME}$ with adversary $\mathsf{A}$ for security parameter $\lambda$ returns $b.$ When the game returns $\mathbf{true}$ we also say that the adversary "wins".

A game can be computational or decisional depending on how a quantity called advantage, measuring how well an adversary performs at winning the game, is defined.

The advantage of an adversary $\mathsf{A}$ against a game $\mathrm{GAME}$ is a function of the security parameter $\lambda \in {\mathbb{N}}^{\ast }$ into $[0,1]$ defined as $${\mathbf{Adv}}_{\mathsf{A}}^{\text{game}}(\lambda ):=\mathrm{Pr}\left[\mathrm{GAME}\Rightarrow \mathbf{true}\right]$$ if the game is computational and $${\mathbf{Adv}}_{\mathsf{A}}^{\text{game}}(\lambda ):=\left|2\mathrm{Pr}\left[\mathrm{GAME}\Rightarrow \mathbf{true}\right]-1\right|$$ if the game is decisional. (We write the name of the game in small caps in the advantage superscript to lighten notation.)

We say that a game $\mathrm{GAME}$ is computationally hard if for every probabilistic polynomial-time (ppt) algorithm $\mathsf{A},$ $${\mathbf{Adv}}_{\mathsf{A}}^{\text{game}}(\lambda )=\mathrm{negl}(\lambda ).$$ We say that a game $\mathrm{GAME}$ is statistically hard (or information-theoretically hard or unconditionally hard) if for every algorithm $\mathsf{A}$ (not necessarily polynomial-time), $${\mathbf{Adv}}_{\mathsf{A}}^{\text{game}}(\lambda )=\mathrm{negl}(\lambda ).$$ In the special case where the advantage of any algorithm is zero, one says that the game is perfectly hard (for example, a commitment scheme that can be perfectly hiding or perfectly binding).

When we simply say that a game is hard, it usually means computationally hard (but this should always be clear from the context).

Hence, for a computationally, resp. statistically hard game, every ppt, resp. unbounded adversary "wins" with probability negligible close to 0 for a computational game and with probability negligibly close to $1/2$ for a decisional game.

Reductions

Given two games $X$ and $Y,$ we say that $X$ reduces to $Y,$ denoted $X\leqq Y,$ if there exists a probabilistic polynomial-time algorithm $\mathsf{B}$ (called reduction) with access to an oracle such that for every algorithm $\mathsf{A}$ solving $Y$ with non-negligible advantage, ${\mathsf{B}}^{\mathsf{A}}$ solves $X$ with non-negligible advantage.

If $X$ reduces to $Y$ and $Y$ reduces to $X,$ we say that $X$ and $Y$ are equivalent, denoted $X\equiv Y.$

Proposition 13.1. Assume that $X$ reduces to $Y.$ Then $X$ being hard implies $Y$ being hard.

Proof

Contraposing, assume that $Y$ is not hard, which by definition means that there exists a ppt algorithm $\mathsf{A}$ such that $${\mathbf{Adv}}_{\mathsf{A}}^{\text{Y}}(\lambda )\ne \mathrm{negl}(\lambda ).$$ Consider the reduction $\mathsf{B}$ from $X$ to $Y.$ Since $\mathsf{A}$ and $\mathsf{B}$ both run in polynomial time, ${\mathsf{B}}^{\mathsf{A}}$ runs in polynomial time as well. Moreover, by definition of a reduction, $${\mathbf{Adv}}_{{\mathsf{B}}^{\mathsf{A}}}^{\text{X}}(\lambda )\ne \mathrm{negl}(\lambda ).$$ Hence, $X$ is not hard.

Thus, $X\leqq Y$ can be read as "$X$ is not harder than $Y$" or $Y$ is at least as hard as $X$".

In cryptography, we are constantly making assumptions of the form "X is hard". Proposition 13.1 can be used to compare the strength of various assumptions. Indeed, assuming we proved that $X\leqq Y,$ then the assumption that $X$ is hard implies that $Y$ is hard too. If, in addition, there are some indications that $Y\leqq X$ does not hold, then the assumption that $X$ is hard is stronger than the assumption that $Y$ is hard. Indeed, if $X\leqq Y$ but $Y\leqq X$ is not known to hold, then it might be that $Y$ is hard yet $X$ is easy.

For example, consider the discrete logarithm (DL) problem on one hand (given a group $\mathbb{G}$ and group elements $G$ and $X=xG,$ compute $x)$ and the Computational Diffie-Hellman (CDH) problem on the other hand (given a group $\mathbb{G}$ and group elements $G,$ $X=xG,$ and $Y,$ compute $xY).$ One can easily prove that CDH $\leqq$ DL (CDH reduces to DL) by constructing a reduction from CDH to DL: given an algorithm solving DL, one can solve CDH by first computing the discrete logarithm $x$ of $X$ and then computing $xY.$ However, there is no proof that DL $\leqq$ CDH (except in very specific situations). Hence, the assumption that CDH is hard is (for most groups) stronger than the assumption that DL is hard.

Another way Proposition 13.1 is often used in cryptography is for security proofs. Here, $X$ is some hardness assumption such as DL and $Y$ is a security game, say unforgeability (in the precise sense of EUF-CMA security in the random oracle model) of Schnorr signatures. Then, a security proof for Schnorr signatures consists in proving that $X$ reduces to $Y,$ i.e., the DL problem reduces to the EUF-CMA security of Schnorr signatures in the ROM. By Proposition 13.1, if DL is hard, then Schnorr signatures are EUF-CMA secure in the ROM.

Idealized Models

The Random Oracle Model

The Generic Group Model

The Algebraic Group Model

Assumptions

Group Setup Algorithms

A standard group setup algorithm is an algorithm $\mathsf{GroupSetup}$ which on input the security parameter $1^{\lambda }$ returns a pair $(\mathbb{G},p)$ where $p$ is a $2\lambda$-bit prime and $\mathbb{G}$ is a cyclic group of order $p.$

A pairing group setup algorithm is an algorithm $\mathsf{PairingSetup}$ which on input the security parameter $1^{\lambda }$ returns a tuple $({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)$ where $r$ is a $2\lambda$-bit prime, ${\mathbb{G}}_1,$ ${\mathbb{G}}_2,$ and ${\mathbb{G}}_t$ are cyclic groups of order $r,$ and $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_t$ is an efficiently computable pairing.

We adopt the convention that group/pairing setup algorithms do not return generators of the groups. They will be explicitly sampled in the games.

One usually distinguishes three types of pairing group setup algorithms [GPS08]:

• a type-1 pairing group setup algorithm (also called symmetric pairing setup algorithm) is such that ${\mathbb{G}}_1={\mathbb{G}}_2;$
• a type-2 pairing group setup algorithm is such that ${\mathbb{G}}_1\ne {\mathbb{G}}_2$ and there exists an efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1;$
• a type-3 pairing group setup algorithm is such that ${\mathbb{G}}_1\ne {\mathbb{G}}_2$ an no efficiently computable isomorphism $\psi :{\mathbb{G}}_2\to {\mathbb{G}}_1$ is known.

Type-2 and type-3 pairing group setup algorithms are called asymmetric.

In all the following, we simply talk about "type-1/2/3 pairings" rather than "type-1/2/3 pairing group setup algorithms".

Assumptions in Standard Groups

Discrete Logarithm (DL)

• type: computational
• interactive: no
• falsifiable: yes
• references:
• notes:

$$\boxed{\begin{array}{l}\text{Game DL:}\\ par\leftarrow \mathsf{GroupSetup}(1^{\lambda })\\ (\mathbb{G},p)\twoheadleftarrow par\\ G{\leftarrow }_{\$}\mathbb{G}\setminus \{0\}\\ X{\leftarrow }_{\$}\mathbb{G}\\ x\leftarrow \mathsf{A}(par,G,X)\\ \mathbf{assert}(X=xG)\end{array}}$$

Computational Diffie-Hellman (CDH)

• type: computational
• interactive: no
• falsifiable: yes
• references:
• notes: CDH $\leqq$ DL

$$\boxed{\begin{array}{l}\text{Game CDH:}\\ par\leftarrow \mathsf{GroupSetup}(1^{\lambda })\\ (\mathbb{G},p)\twoheadleftarrow par\\ G{\leftarrow }_{\$}\mathbb{G}\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_p;X:=xG\\ Y{\leftarrow }_{\$}\mathbb{G}\\ Z\leftarrow \mathsf{A}(par,G,X,Y)\\ \mathbf{assert}(Z=xY)\end{array}}$$

Decisional Diffie-Hellman (DDH)

• type: decisional
• interactive: no
• falsifiable: yes
• references:
• notes: DDH $\leqq$ CDH

$$\boxed{\begin{array}{l}\text{Game DDH:}\\ par\leftarrow \mathsf{GroupSetup}(1^{\lambda })\\ (\mathbb{G},p)\twoheadleftarrow par\\ b{\leftarrow }_{\$}\{0,1\}\\ G{\leftarrow }_{\$}\mathbb{G}\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_p;X:=xG\\ Y{\leftarrow }_{\$}\mathbb{G}\\ Z_0:=xY;Z_1{\leftarrow }_{\$}\mathbb{G}\\ b^{\prime }\leftarrow \mathsf{A}(par,G,X,Y,Z_b)\\ \mathbf{assert}(b=b^{\prime })\end{array}}$$

$q$-Discrete Logarithm ($q$-DL)

• type: computational
• interactive: no
• falsifiable: yes
• references: [Che10, Lip10, FKL18, Rot22]
• notes:
  • sometimes called $q$-strong DL or DL with $q$ auxiliary inputs
  • 1-Dl = DL
  • $(q+1)$-DL $\leqq$ $q$-DL

$$\boxed{\begin{array}{l}\text{Game q-DL:}\\ par\leftarrow \mathsf{GroupSetup}(1^{\lambda })\\ (\mathbb{G},p)\twoheadleftarrow par\\ G{\leftarrow }_{\$}\mathbb{G}\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_p\\ x^{\prime }\leftarrow \mathsf{A}(par,G,xG,x^{2}G,\dots ,x^{q}G)\\ \mathbf{assert}(x=x^{\prime })\end{array}}$$

Assumptions in Product Groups

The assumptions listed in this section are defined for a pair of groups $({\mathbb{G}}_1,{\mathbb{G}}_2)$ of equal order $r.$ They are usually applied to groups returned by a pairing group setup algorithm $\mathsf{PairingSetup}$ but don't make use of the group ${\mathbb{G}}_t$ nor the pairing $e.$ For this reason, we simply write $({\mathbb{G}}_1,{\mathbb{G}}_2,r)\twoheadleftarrow par$ when parsing the parameters $par$ returned by $\mathsf{PairingSetup}.$

$(q_1,q_2)$-co-Discrete Logarithm ($(q_1,q_2)$-co-DL)

• type: computational
• interactive: no
• falsifiable: yes
• references: [Che10, Lip10, FKL18, Rot22]
• notes:

$$\boxed{\begin{array}{l}\text{Game (q1,q2)-co-DL:}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,r)\twoheadleftarrow par\\ G_1{\leftarrow }_{\$}{\mathbb{G}}_1\setminus \{0\}\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r\\ x^{\prime }\leftarrow \mathsf{A}(par,G_1,x{G}_1,\dots ,x^{q_1}{G}_1,G_2,x{G}_2,\dots ,x^{q_2}{G}_2)\\ \mathbf{assert}(x=x^{\prime })\end{array}}$$

Computational co-Diffie-Hellman (co-CDH)

• type: computational
• interactive: no
• falsifiable: yes
• references: [BLS04]
• notes:
  • co-CDH $\leqq$ DL in ${\mathbb{G}}_2$
  • co-CDH $\equiv$ CDH in ${\mathbb{G}}_1={\mathbb{G}}_2$ for type-1 pairings
  • co-CDH $\leqq$ CDH in ${\mathbb{G}}_1$ for type-2 pairings (see Proposition 17.3)

$$\boxed{\begin{array}{l}\text{Game co-CDH:}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,r)\twoheadleftarrow par\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r;X:=x{G}_2\\ Y{\leftarrow }_{\$}{\mathbb{G}}_1\\ Z\leftarrow \mathsf{A}(par,G_2,X,Y)\\ \mathbf{assert}(Z=xY)\end{array}}$$

Computational co-Diffie-Hellman* (co-CDH*)

• type: computational
• interactive: no
• falsifiable: yes
• references: [CHKM10]
• notes:
  • sometimes simply called (confusingly) co-CDH (e.g. [BDN18])
  • co-CDH${}^{\ast }$ $\leqq$ CDH in ${\mathbb{G}}_1$
  • co-CDH${}^{\ast }$ $\leqq$ DL in ${\mathbb{G}}_2$
  • co-CDH${}^{\ast }$ $\leqq$ co-CDH
  • co-CDH${}^{\ast }$ $\equiv$ CDH in ${\mathbb{G}}_1={\mathbb{G}}_2$ for type-1 pairings (see Proposition 17.1)
  • co-CDH${}^{\ast }$ $\equiv$ co-CDH for type-2 pairings (see Proposition 17.2)

$$\boxed{\begin{array}{l}\text{Game co-CDH∗:}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,r)\twoheadleftarrow par\\ G_1{\leftarrow }_{\$}{\mathbb{G}}_1\setminus \{0\}\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r;X_1:=x{G}_1;X_2:=x{G}_2\\ Y{\leftarrow }_{\$}{\mathbb{G}}_1\\ Z\leftarrow \mathsf{A}(par,G_1,X_1,G_2,X_2,Y)\\ \mathbf{assert}(Z=xY)\end{array}}$$

Computational $\psi$-co-Diffie-Hellman ($\psi$-co-CDH)

• type: computational
• interactive: yes
• falsifiable: no (for type-3 pairings)
• references: [SV07, BDN18]
• notes:
  • $\psi$-co-CDH $\leqq$ CDH in ${\mathbb{G}}_1$
  • $\psi$-co-CDH $\leqq$ DL in ${\mathbb{G}}_2$
  • $\psi$-co-CDH $\leqq$ co-CDH${}^{\ast }$ $\leqq$ co-CDH
  • $\psi$-co-CDH $\equiv$ co-CDH for type-2 pairings (the isomorphism $\psi$ enables to compute $\text{SolveCoCDH}(U)$ efficiently as $\psi (U),$ assuming $\psi (G_2)=G_1)$

$$\boxed{\begin{array}{ll}\text{Game ψ-co-CDH:}& \text{Oracle SolveCoCDH(U):}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })& //\text{solves co-CDH for (G2,U,G1)}\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,r)\twoheadleftarrow par& \mathbf{assert}U\in {\mathbb{G}}_2\\ G_1{\leftarrow }_{\$}{\mathbb{G}}_1\setminus \{0\}& \mathbf{for}u\in {\mathbb{Z}}_r\mathbf{do}\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}& \mathbf{if}u{G}_2=U\mathbf{then}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r;X_1:=x{G}_1;X_2:=x{G}_2& \mathbf{return}u{G}_1\\ Y{\leftarrow }_{\$}{\mathbb{G}}_1& \\ Z\leftarrow {\mathsf{A}}^{\text{SolveCoCDH}}(par,G_1,X_1,G_2,X_2,Y)& \\ \mathbf{assert}(Z=xY)& \end{array}}$$

$(q_1,q_2)$-Strong Diffie-Hellman ($(q_1,q_2)$-SDH)

• type: computational
• interactive: no
• falsifiable: yes
• references: [BB08]
• notes:
  • $(q,1)$-SDH usually called $q$-SDH
  • not to be confused with another assumption named SDH introduced in [ABR01]
  • $(q_1+1,q_2)$-SDH $\leqq$ $(q_1,q_2)$-SDH
  • $(q_1,q_2+1)$-SDH $\leqq$ $(q_1,q_2)$-SDH

$$\boxed{\begin{array}{l}\text{Game (q1,q2)-SDH:}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,r)\twoheadleftarrow par\\ G_1{\leftarrow }_{\$}{\mathbb{G}}_1\setminus \{0\}\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r\\ (a,Y)\leftarrow \mathsf{A}(par,G_1,x{G}_1,\dots ,x^{q_1}{G}_1,G_2,x{G}_2,\dots ,x^{q_2}{G}_2)\\ \mathbf{assert}(Y=\frac{1}{x+a}{G}_1)\end{array}}$$

Assumptions in Pairing Groups

$(q_1,q_2)$-Bilinear Diffie-Hellman Inversion ($(q_1,q_2)$-BDHI)

• type: computational
• interactive: no
• falsifiable: yes
• references: [BB04]
• notes:
  • $(q_1+1,q_2)$-BDHI $\leqq$ $(q_1,q_2)$-BDHI
  • $(q_1,q_2+1)$-BDHI $\leqq$ $(q_1,q_2)$-BDHI

$$\boxed{\begin{array}{l}\text{Game (q1,q2)-BSDH:}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)\twoheadleftarrow par\\ G_1{\leftarrow }_{\$}{\mathbb{G}}_1\setminus \{0\}\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r\\ Y\leftarrow \mathsf{A}(par,G_1,x{G}_1,\dots ,x^{q_1}{G}_1,G_2,x{G}_2,\dots ,x^{q_2}{G}_2)\\ \mathbf{assert}(Y=e(G_1,G_2{)}^{\frac{1}{x}})\end{array}}$$

$(q_1,q_2)$-Bilinear Strong Diffie-Hellman ($(q_1,q_2)$-BSDH)

• type: computational
• interactive: no
• falsifiable: yes
• references: [KZG10a]
• notes:
  • $(q,1)$-BSDH is usually simply called $q$-BSDH
  • $(q_1+1,q_2)$-BSDH $\leqq$ $(q_1,q_2)$-BSDH
  • $(q_1,q_2+1)$-BSDH $\leqq$ $(q_1,q_2)$-BSDH
  • $(q_1,q_2)$-BSDH $\leqq$ $(q_1,q_2)$-SDH
  • $(q_1,q_2)$-BSDH $\leqq$ $(q_1,q_2)$-BDHI

$$\boxed{\begin{array}{l}\text{Game (q1,q2)-BSDH:}\\ par\leftarrow \mathsf{PairingSetup}(1^{\lambda })\\ ({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,r,e)\twoheadleftarrow par\\ G_1{\leftarrow }_{\$}{\mathbb{G}}_1\setminus \{0\}\\ G_2{\leftarrow }_{\$}{\mathbb{G}}_2\setminus \{0\}\\ x{\leftarrow }_{\$}{\mathbb{Z}}_r\\ (a,Y)\leftarrow \mathsf{A}(par,G_1,x{G}_1,\dots ,x^{q_1}{G}_1,G_2,x{G}_2,\dots ,x^{q_2}{G}_2)\\ \mathbf{assert}(Y=e(G_1,G_2{)}^{\frac{1}{x+a}})\end{array}}$$