By correctness of the punctured PRF keys, we have that
$\mathsf{PKeyGen}^{\prime}_{K\\{id^{*}\\},ipk^{*},id^{*}}$ and
$\mathsf{PKeyGen}_{K}$ have the same functionality. The result follows by the
security of $i\mathcal{O}$. ∎

######  Claim 2.

$\mathsf{Hyb}_{1}\approx\mathsf{Hyb}_{2}$.

###### Proof.

Observe that in $\mathsf{Hyb}_{1}$, the adversary has only access to
(efficient functions of) PRF evaluations at points other than $id^{*}$ and the
punctured PRF key $K\\{id^{*}\\}$, rather than the full key $K$. Therefore,
the result follows from the puncturable PRF security (Definition 1). ∎

By above, we get that $\mathcal{A}$ wins in $\mathsf{Hyb}_{2}$ with non-
negligible probability. We claim that the adversary $\mathcal{A}^{\prime}$
described below wins the public-key encryption security game (LABEL:defn:pke)
against $\mathsf{PKE}$ with non-negligible probability.

$\mathcal{A}^{\prime}$ runs $\mathcal{A}$ to obtain $id^{*}$. Then, it samples
a PRF key $K$ for $F$ and computes $K\\{id^{*}\\}\leftarrow
F.\mathsf{Punc}(K,id^{*})$. When it receives the public key $pk$ from the
challenger, $\mathcal{A}^{\prime}$ computes $\mathsf{OPKeyGen}\leftarrow
i\mathcal{O}(\mathsf{PKeyGen}_{K\\{id^{*}\\},pk,id^{*}},1^{\lambda})$, where
$\mathsf{PKeyGen}_{K\\{id^{*}\\},pk,id^{*}}$ is the following program.

$\underline{\mathsf{PKeyGen}^{\prime}_{K\\{id^{*}\\},pk,id^{*}}(id)}$
Hardcoded: $K\\{id^{*}\\},{pk,id^{*}}$ 1. If $id=id^{*}$, output $pk$ and
terminate. 2. Sample
$ipk,isk\leftarrow\mathsf{PKE.KeyGen}(1^{\lambda};F(K,id))$. 3. Output $ipk$.

Then, $\mathcal{A}^{\prime}$ runs $\mathcal{A}$ on $\mathsf{OPKeyGen}$ and
$K\\{id^{*}\\}$ to obtain $m_{0},m_{1}$, which it submits to the challenger.
Finally, when $\mathcal{A}^{\prime}$ obtains the challenge ciphertext from the
challenger, it runs $\mathcal{A}$ on it to obtain the guess $b^{\prime}$,
which it submits to the challenger.

It is easy to see that $\mathcal{A}^{\prime}$ wins the public-key encryption
security game with the same probability as $\mathcal{A}$ wins in
$\mathsf{Hyb}_{2}$, which is non-negligible. This is a contradiction to the
security of $\mathsf{PKE}$.

###  5.4 Puncturable Functional Encryption Construction

As an application of our puncturable IBE scheme and as a warm-up to our copy-
protected functional encryption scheme, we show how to construct puncturable
functional encryption. In our copy-protected functional encryption scheme
(Section 7), we use a punctured master secret key in a non-black-box way to
remove interaction from the post-challenge-ciphertext phase of the security
game.

Now we move onto our construction, which will be similar to the delegatable
functional encryption scheme of [CGJS15]. Assume the existence of following
schemes and we will construct a puncturable functional encryption for the
class of functions $\mathfrak{F}$ defined as all circuits that are of size at
most $Q(\lambda)$, where $Q(\lambda)$ is a fixed polynomial.

  * •

$i\mathcal{O}$, $2^{-\lambda-Q(\lambda)}$-secure indistinguishability
obfuscation scheme,

  * •

$\mathsf{IBE}$, a $2^{-\lambda-Q(\lambda)}$-secure public-key identity-based
encryption scheme for identity space $\\{0,1\\}^{Q(\lambda)}$ with puncturable
master secret keys (Definition 14) and deterministic identity key generation
satisfying strong punctured key correctness (Definition 13)

  * •

$F$, a a $2^{-\lambda-Q(\lambda)}$-secure puncturable PRF family with input
space $\\{0,1\\}^{Q(\lambda)}$ and output length same as the size of the
randomness used by $\mathsf{IBE.Enc}$,

##### $\underline{\mathsf{FE.Setup}(1^{\lambda})}$

  1. 1.

Sample $pk,imsk\leftarrow\mathsf{IBE.Setup}(1^{\lambda})$.

  2. 2.

Output $pk,(imsk,\mathsf{FULL-KEY})$.

##### $\underline{\mathsf{FE.KeyGen}(msk^{\prime},f)}$

  1. 1.

Parse $(msk^{\prime\prime},\mathsf{TYPE})=msk^{\prime}$.

  2. 2.

If $\mathsf{TYPE}=\mathsf{PUNC-KEY}$, output $msk^{\prime\prime}(f)$ and
terminate.

  3. 3.

Sample $sk\leftarrow\mathsf{IBE.KeyGen}(msk^{\prime\prime},f)$.

  4. 4.

Output $(sk,f)$.

##### $\underline{\mathsf{FE.Punc}(msk,m_{0},m_{1})}$

  1. 1.

Parse $(imsk,\mathsf{TYPE})=msk$. Terminate if $\mathsf{TYPE}\neq\mathsf{FULL-
KEY}$.

  2. 2.

Sample $\mathsf{OPKey}\leftarrow
i\mathcal{O}(1^{\lambda},\mathsf{PKey}_{imsk,m_{0},m_{1}})$ where
$\mathsf{PKey}_{imsk,m_{0},m_{1}}$ is the following program.

$\underline{\mathsf{PKey}_{imsk,m_{0},m_{1}}(f)}$ Hardcoded:
$imsk,m_{0},m_{1}$ 1. If $f(m_{0})\neq f(m_{1})$, output $\perp$ and
terminate. 2. Compute $sk=\mathsf{IBE.KeyGen}(imsk,f)$. 3. Output $(sk,f)$.

  3. 3.

Output $\mathsf{OPKey}$.

##### $\underline{\mathsf{FE.Enc}(pk,m)}$

  1. 1.

Sample $K\leftarrow F.\mathsf{Setup}(1^{\lambda}).$

  2. 2.

Sample $\mathsf{OPCt}\leftarrow i\mathcal{O}(\mathsf{PCt}_{m,pk,K})$ where
$\mathsf{PCt}_{m,pk,K}$ is the following program.
$\underline{\mathsf{PCt}_{m,pk,K}(f)}$ Hardcoded: $m,pk,K$ 1. Compute
$a=f(m)$. 2. Compute $ct=\mathsf{IBE.Enc}(pk,f,a;F(K,f))$. 3. Output $ct$.

  3. 3.

Output $\mathsf{OPCt}$.

##### $\underline{\mathsf{FE.Dec}(sk,ct)}$

  1. 1.

Parse $(sk^{\prime},f)=sk$.

  2. 2.

Parse $\mathsf{OPCt}=ct$.

  3. 3.

$ct^{\prime}=\mathsf{OPCt}(f)$.

  4. 4.

Output $\mathsf{IBE.Dec}(sk^{\prime},ct^{\prime})$.

######  Theorem 23.

$\mathsf{FE}$ satisfies both correctness (Definition 16) and strong punctured
master secret key correctness (Definition 17).

###### Proof.

Follows in a straightforward manner from the correctness of the underlying
primitives and the fact that $\mathsf{IBE.KeyGen}$ is deterministic. ∎

######  Theorem 24.

$\mathsf{FE}$ satisfies puncturable master secret key security (Definition
17).

Since we construct in Section 5.2 a puncturable IBE with the properties
required by $\mathsf{FE}$ based on $i\mathcal{O}$ and one-way functions, we
get the following corollary.

######  Corollary 3.

Assuming the existence of subexponentially secure indistinguishability
obfuscation and one-way functions, there exist a puncturable functional
encryption scheme.

###  5.5 Proof of Security for Puncturable Functional Encryption

In this section, we prove Theorem 24. Our proof will be similar to security
proof of the delegatable functional encryption scheme in [CGJS15]. Throughout
the proof, we will interpret the functions $f\in\mathfrak{F}$, which are
represented by circuits of size $Q(\lambda)$, as numbers in
$\\{0,1,\dots,2^{Q}\\}$.

Suppose for a contradiction there exists a QPT adversary $\mathcal{A}$ that
wins the puncturable functional encryption game with non-negligible advantage,
that is, $\Pr[\mathsf{PUN-FE-IND}(\lambda,\mathcal{A})=1]\geq
1/2+1/p(\lambda)$ for some polynomial $p(\cdot)$ and for infinitely many
values of $\lambda>0$. We will prove security through a series of hybrids,
each of which is obtained by modifying the previous one, starting with
$\mathsf{Hyb}_{0}$.

We define $\mathsf{Hyb}_{0}$ to be the same as the original security game
$\mathsf{PUN-FE-IND}(\lambda,\mathcal{A})$.

#####  $\mathsf{Hyb}_{t}$ for $t\in\\{0,1,\dots,2^{Q}\\}$:

We now compute the challenge ciphertext (encryption of $m_{b}$) as
$\mathsf{OPCt}\leftarrow i\mathcal{O}(\mathsf{PCt}^{(t)})$.
$\underline{\mathsf{PCt}^{(t)}(f)}$ Hardcoded:
${\color[rgb]{1,0,0}m_{0},m_{1},b},pk,K$ 1. If $f<t$, set $a=f(m_{1-b})$.
Otherwise, set $a=f(m_{b})$. 2. Compute $ct=\mathsf{IBE.Enc}(pk,f,a;F(K,f))$.
3. Output $ct$.

Define the event $E_{t}$ to be the event that the pair of challenge messages
$m_{0},m_{1}$ output by the adversary $\mathcal{A}$ are such that
$t(m_{0})=t(m_{1})$.

######  Lemma 3.

$|(\mathsf{Hyb}_{t})_{|E_{t}}-(\mathsf{Hyb}_{t})_{|E_{t}}|<2^{-\lambda-Q(\lambda)}$.

###### Proof.

Observe the programs $\mathsf{PCt}^{(t)}$ and $\mathsf{PCt}^{(t+1)}$ only on
input $f=t$, in which case the first program compute $a=t(m_{b})$ whereas the
second program computes $a=t(m_{1-b})$. However, conditioned on $E_{t}$, we
have $t(m_{b})=t(m_{1-b})$. Hence, the programs have the same functionality
and the result follows from the security of $i\mathcal{O}$. ∎

We will also prove
$|(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}|<2^{-\lambda/2-Q(\lambda)}$.
This combined with the above lemma gives
$|\mathsf{Hyb}_{t}-\mathsf{Hyb}_{t+1}|<{2^{-\lambda/2-Q(\lambda)}}$ through
triangle inequality. Crucially, note that the probability of the event $E_{t}$
is the same in both hybrids since we only change the way we compute the
challenge ciphertext (which the adversary sees after choosing $m_{0},m_{1}$).

To prove
$|(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}|<2^{-\lambda/2-Q(\lambda)}$,
we define a sequence of intermediary hybrids.

#####  $\mathsf{Hyb}_{t,1}$ for $t\in\\{0,1,\dots,2^{Q}\\}$:

We first compute $ct^{*}\leftarrow\mathsf{IBE.Enc}(pk,t,f(m_{b});F(K,t))$ and
$K\\{t\\}\leftarrow F.\mathsf{Punc}(K,t)$. Then, we now compute the challenge
ciphertext as $\mathsf{OPCt}\leftarrow i\mathcal{O}(\mathsf{PCt}^{(t,1)})$.
$\underline{\mathsf{PCt}^{(t,1)}(f)}$ Hardcoded:
${\color[rgb]{1,0,0}ct^{*},K\\{t\\}},m_{0},m_{1},b,pk$ 1. If $f=t$, output
$ct^{*}$ and terminate. 2. If $f<t$, set $a=f(m_{1-b})$. Otherwise, set
$a=f(m_{b})$. 3. Compute
$ct=\mathsf{IBE.Enc}(pk,f,a;F({\color[rgb]{1,0,0}K\\{t\\}},f))$. 4. Output
$ct$.

#####  $\mathsf{Hyb}_{t,2}$ for $t\in\\{0,1,\dots,2^{Q}\\}$:

We now sample $ct^{*}\leftarrow\mathsf{IBE.Enc}(pk,t,f(m_{b});z)$ where $z$ is
sampled uniformly at random from the output space of $F$.

##### $\mathsf{Hyb}_{t,3}$ for $t\in\\{0,1,\dots,2^{Q}\\}$

: We now change the way we sample punctured master secret key as follows. At
the beginning of the game, we compute
$imsk^{\prime}\leftarrow\mathsf{IBE.Punc}(imsk,t)$. We now output
$\mathsf{OPKey}\leftarrow\mathsf{PKey}^{(t)}$.

$\underline{\mathsf{PKey}^{(t)}(f)}$ Hardcoded:
${\color[rgb]{1,0,0}imsk^{\prime}},m_{0},m_{1}$ 1. If $f(m_{0})\neq f(m_{1})$,
output $\perp$ and terminate. 2. Compute
$sk=\mathsf{IBE.KeyGen}({\color[rgb]{1,0,0}imsk^{\prime}},f)$. 3. Output
$(sk,f)$.

##### $\mathsf{Hyb}_{t,4}$ for $t\in\\{0,1,\dots,2^{Q}\\}$

: Same as $\mathsf{Hyb}_{t,3}$ but we now compute $ct^{*}$ as
$ct^{*}\leftarrow\mathsf{IBE.Enc}(pk,t,{\color[rgb]{1,0,0}f(m_{1-b})};z)$.

##### $\mathsf{Hyb}_{t,5}$ for $t\in\\{0,1,\dots,2^{Q}\\}$

: Same as ${\color[rgb]{0,0,1}\mathsf{Hyb}_{t,2}}$ but we compute $ct^{*}$ as
$ct^{*}\leftarrow\mathsf{IBE.Enc}(pk,t,{\color[rgb]{1,0,0}f(m_{1-b})};F(K,t))$.

##### $\mathsf{Hyb}_{t,6}$ for $t\in\\{0,1,\dots,2^{Q}\\}$

: Same as ${\color[rgb]{0,0,1}\mathsf{Hyb}_{t,1}}$ but we compute $ct^{*}$ as
$ct^{*}\leftarrow\mathsf{IBE.Enc}(pk,t,{\color[rgb]{1,0,0}f(m_{1-b})};F(K,t))$.

######  Lemma 4.

$|(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t,1})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

By the punctured key correctness of $F$, the programs $\mathsf{PCt}^{(t)}$ and
$\mathsf{PCt}^{(t,1)}$ have the same functionality. The results follows by the
security of $i\mathcal{O}$. ∎

######  Lemma 5.

$|(\mathsf{Hyb}_{t,1})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t,2})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

Observe that the adversary only has the punctured key $K\\{t\\}$. The resut
follows by the security of the puncturable PRF $F$. ∎

######  Lemma 6.

$|(\mathsf{Hyb}_{t,2})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t,3})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}\cdot\textnormal{poly}(\lambda)$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

Since we are conditioned on the event $\overline{E_{t}}$, we have
$t(m_{0})\neq t(m_{1})$. Hence, by strong punctured key correctness of
$\mathsf{IBE}$, all the programs $\mathsf{PKey}_{P}$ in these hybrids have the
same functionality. Result follows from the security of $i\mathcal{O}$. ∎

######  Lemma 7.

$|(\mathsf{Hyb}_{t,3})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t,4})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

Since we are conditioned on the event $\overline{E_{t}}$, we have
$t(m_{0})\neq t(m_{1})$. Further, to win, for any function $f\in\mathfrak{F}$,
if $f$ is queried by the adversary, then $f(m_{0})=f(m_{1})$. Combining these,
we get that $t$ was never queried by the adversary. Therefore, the adversary
never gets a secret key for the identity $t$. In particular, all the identity
secret keys obtained by the adversary (as a result of functional key queries)
can instead be obtained using $imsk^{\prime}$, the IBE master secret key
punctured at $t$, due to the strong punctured key correctness of IBE. Further,
the punctured IBE master secret key obtained by the adversary (which is inside
the punctured FE master secret key) is also punctured at $t$. Finally, observe
that $ct^{*}$ is an IBE encryption (sampled using true randomness $z$) under
the identity $t$. Hence, the result follows by puncturable IBE security
(Definition 14). ∎

######  Lemma 8.

$|(\mathsf{Hyb}_{t,4})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t,5})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}\cdot\textnormal{poly}(\lambda)$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

Same argument as Lemma 6. ∎

######  Lemma 9.

$|(\mathsf{Hyb}_{t,5})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t,6})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

Same argument as Lemma 5. ∎

######  Lemma 10.

$|(\mathsf{Hyb}_{t,6})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t+1})_{|\overline{E_{t}}}|<2^{-\lambda-Q(\lambda)}$
for all $t\in\\{0,1,\dots,2^{Q}\\}$.

###### Proof.

Same argument as Lemma 4. ∎

Combining the above lemmata, we get
$|(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}-(\mathsf{Hyb}_{t})_{|\overline{E_{t}}}|<2^{-\lambda/2-Q(\lambda)}$.
Then, as argued before, this gives
$|\mathsf{Hyb}_{t}-\mathsf{Hyb}_{t+1}|<2^{2^{-\lambda/2-Q(\lambda)}}$, finally
yielding $|\mathsf{Hyb}_{0}-\mathsf{Hyb}_{2^{Q}}|<{2^{-\lambda/2}}$. Hence,
$\Pr[\mathsf{Hyb}_{0}=1]\geq 1/2+1/p(\lambda)$ by assumption and therefore
$\Pr[\mathsf{Hyb}_{2^{Q}}=1]\geq 1/2+1/(2\cdot p(\lambda))$. However, this is
clearly a contradiction, since the challenge messages in these hybrids are
$m_{b}$ and $m_{1-b}$ respectively (while we still compare the adversary’s
guess to $b$).

##  6 Public-Key Encryption with Copy-Protected Secret Keys

In this section, we define public-key encryption with copy-protected secret
keys. Then, we give our construction based on coset states and prove it
secure.

###  6.1 Definitions

######  Definition 18 (Public-key Encryption with Copy-Protected Secret Keys).

A public-key encryption scheme with copy-protected secret keys consists of the
following efficient algorithms.

  * •

$\mathsf{KeyGen}(1^{\lambda})$: Takes in the security parameter, output a
classical secret key $sk$ and a public key $pk$.

  * •

$\mathsf{QKeyGen}(sk)$: Takes as input the classical secret key and outputs a
quantum secret key.

  * •

$\mathsf{Enc}(pk,m)$: Takes in the public key and a message $m\in\mathcal{M}$,
outputs and encryption of $m$.

  * •

$\mathsf{Dec}(R_{\mathsf{dec}},ct)$: Takes in a quantum secret key and a
ciphertext, outputs a message or $\perp$.

We require correctness and _CPA security_.

##### Correctness

For all messages $m\in\mathcal{M}$,

$\Pr[\mathsf{Dec}(R_{\mathsf{dec}},ct)=m:\begin{array}[]{c}pk,sk\leftarrow\mathsf{Setup}(1^{\lambda})\\\
R_{\mathsf{dec}}\leftarrow\mathsf{QKeyGen}(sk)\\\
ct\leftarrow\mathsf{Enc}(pk,m)\end{array}]=1.$

##### CPA Security

For any stateful QPT adversary $\mathcal{A}$,

$\Pr[\mathcal{A}(ct)=b:\begin{array}[]{c}pk,sk\leftarrow\mathsf{Setup}(1^{\lambda})\\\
m_{0},m_{1}\leftarrow\mathcal{A}(pk,1^{\lambda})\\\ b\leftarrow\\{0,1\\}\\\
ct\leftarrow\mathsf{Enc}(pk,m_{b})\end{array}]\leq\frac{1}{2}+\mathsf{negl}(\lambda).$

As observed by [CLLZ21], correctness of the scheme along with Lemma 1 means
that we can implement decryption in a way such that the quantum secret key is
not disturbed. Thus, we can reuse the key to decrypt any number of times.

Following prior work, we will use two different security notions, regular
anti-piracy and strong anti-piracy. The former will be the natural security
notion while the latter definition is easier to work with when proving
security. Both definitions follow [CLLZ21, LLQZ22], with the strengthening
that we allow unbounded111111Still polynomial since the adversary is QPT.
number of key queries and we also allow the adversary to choose different
challenge messages for each freeloader.

Below, we write $\mathsf{U}_{quantum}$ to denote the quantum universal circuit
$\mathsf{U}_{quantum}((\mathcal{B},\rho),x)$ that takes in the description of
a quantum circuit $\mathcal{B}$ with a hardwired state $\rho$ and simulates it
on input $x$. That is, it computes $\mathcal{B}(\rho,x)$.

######  Definition 19 (CPA-Style Regular $\gamma$-Anti-Piracy Security).

Let $\mathsf{PKE}$ be a public key encryption scheme with copy-protected
secret keys. Consider the following game between the challenger and an
adversary $\mathcal{A}$.

##### $\underline{\mathsf{PKEAntiPiracy}(\lambda,\mathcal{A})}$

  1. 1.

The challenger runs $sk,pk\leftarrow\mathsf{PKE}.\mathsf{Setup}(1^{\lambda})$
and submits $pk$ to the adversary.

  2. 2.

For multiple rounds, $\mathcal{A}$ makes quantum key queries. For each query,
the challenger generates a key as
$R\leftarrow\mathsf{PKE}.\mathsf{QKeyGen}(sk)$ and submits $R$ to the
adversary.

  3. 3.

$\mathcal{A}$ outputs a $(k+1)$-partite register $R_{\mathsf{adv}}$ and
challenge messages $m_{\ell}^{0},m_{\ell}^{1}$ for $\ell\in[k+1]$, where $k$
is the number of queries it made.

  4. 4.

The challenger executes the following for each $\ell\in[k+1]$.

    1. 4.1.

$b_{\ell}\leftarrow\\{0,1\\}$.

    2. 4.2.

$ct_{\ell}\leftarrow\mathsf{PKE}.\mathsf{Enc}(pk,m^{b_{\ell}}_{\ell})$.

    3. 4.3.

$b^{\prime}_{\ell}\leftarrow\mathsf{U}_{quantum}(R_{\mathsf{adv}}[\ell],ct_{\ell})$.

    4. 4.4.

Check if $b^{\prime}_{\ell}=b_{\ell}$.

  5. 5.

The challenger outputs 1 if and only if all the checks pass.

We say that $\mathsf{PKE}$ satisfies $\gamma$-anti-piracy security if for any
QPT adversary $\mathcal{A}$,

$\Pr[\mathsf{PKEAntiPiracy}(\lambda,\mathcal{A})=1]\leq\frac{1}{2}+\gamma(\lambda)+\mathsf{negl}(\lambda).$

We ignore writing $\gamma$ when $\gamma=0$.

Before moving onto the stronger definition, we need the following notation.

######  Definition 20 (Decryptor Testing).

In the anti-piracy game between the challenger and an adversary, fix
$\ell\in[k+1]$, some values $m_{\ell}^{0},m_{\ell}^{1}$ of the challenge
messages and some value $st$ of a classical state maintained by the challenger
(which will be defined later). Let $\mathcal{D}$ be an efficient ciphertext
distribution that can depend on $st$. That is, $\mathcal{D}^{st}(m;r)$ is an
efficient classical algorithm where $m\in\mathcal{M}$, $r\in\mathcal{R}$ and
$\mathcal{R}$ is a random coin set.

Consider the following mixture $\mathcal{P}$ of binary _projective_
121212While the measurement $\mathsf{U}$ described as-is is a general
measurement, we will implicitly consider it as a measurement on input plus
some ancilla in the state $\ket{0}^{n}$, since in its implementation we apply
the unitary part of it on the input plus ancilla and finally make a
measurement in the standard computational basis. In this case, the measurement
is indeed projective, indexed by the output space of the challenge ciphertext
distribution. _measurements_ , induced by $\mathcal{D}$ and
$m_{\ell}^{0},m_{\ell}^{1},st$, applied on a state $\rho$.

  1. 1.

Sample $b\leftarrow\\{0,1\\}$.

  2. 2.

Sample $r\leftarrow\mathcal{R}$.

  3. 3.

Run $ct\leftarrow\mathcal{D}^{st}(m^{b}_{\ell};r)$.

  4. 4.

Run the universal circuit $\mathsf{U}_{quantum}$ on $(\rho,ct)$, let
$b^{\prime}$ be the output.

  5. 5.

Output 1 if $b^{\prime}=b$. Otherwise, output $0$.

Observe that we can efficiently execute the above measurement131313More
formally, we are actually talking about the measurement where $r,b$ are fixed
for arbitrary given superpositions of $r$ and $b$ values. Therefore, by
Section 3.7, there exists both exact and approximated projective and threshold
implementations for $\mathcal{P}$. We write $\mathsf{PI}_{\ell,\mathcal{D}}$
and $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}}$ to denote the
projective implementation and approximate projective implementation of
$\mathcal{P}$, respectively. Similarly, let
$\mathsf{TI}_{\ell,\mathcal{D},\eta}$ and
$\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},\eta}$ denote the
threshold and efficient approximate threshold implementations of $\mathcal{P}$
for a threshold value $\eta$.

While the fixed values $m_{\ell}^{0},m_{\ell}^{1},st$ are omitted from the
notation, they will be clear from the context. Unless otherwise specified, we
will write $\mathcal{D}$ to denote the ciphertext distribution where we
encrypt $m$ as

$ct\leftarrow\mathsf{PKE.Enc}(pk,m)$

where $pk$ is part of $st$.

######  Definition 21 (CPA-Style Strong $\gamma$-Anti-Piracy).

Let $\mathsf{PKE}$ be a public key encryption scheme with copy-protected
secret keys. Consider the following game between the challenger and an
adversary $\mathcal{A}$.

#####
$\underline{\mathsf{PKEStrongAntiPiracy}(\lambda,\gamma(\lambda),\mathcal{A})}$

  1. 1.

The challenger runs $sk,pk\leftarrow\mathsf{PKE}.\mathsf{Setup}(1^{\lambda})$
and submits $pk$ to the adversary.

  2. 2.

For multiple rounds, $\mathcal{A}$ makes quantum key queries. For each query,
the challenger generates a key as
$R\leftarrow\mathsf{PKE}.\mathsf{QKeyGen}(sk)$ and submits $R$ to the
adversary.

  3. 3.

$\mathcal{A}$ outputs a $(k+1)$-partite register $R_{\mathsf{adv}}$ and
challenge messages $m_{\ell}^{0},m_{\ell}^{1}$ for $\ell\in[k+1]$, where $k$
is the number of queries it made.

  4. 4.

The challenger applies the test

$\bigotimes_{\ell\in[k+1]}\mathsf{TI}_{\ell,\mathcal{D},1/2+\gamma}$

to $R_{\mathsf{adv}}$ and outputs $1$ if and only if the measurement result is
all $1$.

We say that $\mathsf{PKE}$ satisfies strong $\gamma$-anti-piracy security if
for any QPT adversary $\mathcal{A}$,

$\Pr[\mathsf{PKEStrongAntiPiracy}(\lambda,\gamma(\lambda),\mathcal{A})]\leq\mathsf{negl}(\lambda).$

We also have the following relationship between the various security
definitions for public-key encryption.

######  Theorem 25 ([CLLZ21]).

Suppose a public key encryption scheme with copy-protected keys satisfies CPA-
style strong $\gamma$-anti-piracy (Definition 21). Then, it also satisfies
CPA-style regular $\gamma$-anti-piracy (Definition 19).

While [CLLZ21] proves the above for only $1\to 2$ anti-piracy security, it can
be generalized to unbounded collusion setting - see proof of Theorem 29.

######  Theorem 26 ([CLLZ21]).

Suppose a public key encryption scheme with copy-protected keys satisfies CPA-
style regular $\gamma$-anti-piracy (Definition 19) for any inverse polynomial
$\gamma$. Then, it also satisfies regular CPA security and regular
$\gamma$-anti-piracy for $\gamma=0$.

This is simply due to the definition of $\mathsf{negl}(\lambda)$ and
$\gamma$-anti-piracy.

###  6.2 Construction

In this section, we present our construction. Assume the existence of
following primitives where we set $\nu(\lambda)=2^{-6\lambda}\cdot
2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

  * •

$i\mathcal{O}$, indistinguishability obfuscation scheme that is
$\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$\mathsf{IBE}$, identity-based encryption scheme for the identity space
$\mathcal{ID}=\\{0,1\\}^{\lambda}$ (Definition 10) that is
$\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$F_{1}$, puncturable PRF family with input length $\lambda$ and output length
same as the size of the randomness used by $\mathsf{CosetGen}$ that is
$\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$F_{2}$, puncturable PRF family with input length $\lambda$ and output length
same as the size of the randomness used by $\mathsf{IBE.Enc}$ that is
$\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$\mathsf{CCObf}$, compute-and-compare obfuscation for
$2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$-unpredictable distributions
that is $2^{-2\lambda-1}\cdot 2^{-2\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-secure
against $2^{3\lambda}\cdot 2^{2\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time
adversaries,

While we assume exponential security of the above primitives for specific
exponents, these assumptions can be based solely on subexponential hardness
for any exponent, since we can always scale the security parameter by a
polynomial factor when instantiating in the underlying primitives.

Set $L(\lambda)=\lambda$ and therefore $c_{L}(\lambda)=24\cdot\lambda^{3}$
(see Theorem 19). We also assume that all obfuscated programs in the
construction and in the proof are appropriately padded.

We now give our construction for public-key encryption with copy-protected
secret keys.

##### $\underline{\mathsf{PKE.Setup}(1^{\lambda})}$

  1. 1.

Sample a PRF key $K_{1}\leftarrow F_{1}.\mathsf{KeyGen}(1^{\lambda})$.

  2. 2.

Sample $cpk,csmk\leftarrow\mathsf{IBE.Setup}(1^{\lambda})$.

  3. 3.

Sample $\mathsf{OPMem}\leftarrow i\mathcal{O}(\mathsf{PMem}_{K_{1}})$, where
$\mathsf{PMem}_{K_{1}}$ is the following program.

$\underline{\mathsf{PMem}_{K_{1}}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)}$
Hardcoded: $K_{1}$ 1.
$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}\leftarrow\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1},id))$.
2. For each $i\in[c_{L}(\lambda)]$, check if $u_{i}\in A_{i}+s_{i}$ if
$(r)_{i}=0$ and check if $u_{i}\in A^{\perp}_{i}+s^{\prime}_{i}$ if
$(r)_{i}=1$. If any of the checks fail, output $0$ and terminate. 3. Output
$1$.

  4. 4.

Set $pk=(cpk,\mathsf{OPMem})$ and $sk=(cmsk,K_{1})$.

  5. 5.

Output $(pk,sk)$.

##### $\underline{\mathsf{PKE.QKeyGen}(sk)}$

  1. 1.

Parse $(cmsk,K_{1})=sk$.

  2. 2.

Sample $id\leftarrow\\{0,1\\}^{\lambda}$.

  3. 3.

$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}=\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1},id))$.

  4. 4.

$ck\leftarrow\mathsf{IBE.KeyGen}(cmsk,id)$.

  5. 5.

Output
$\mathopen{}\mathclose{{}\left(\ket{A_{i,s_{i},s^{\prime}_{i}}}}\right)_{i\in[c_{L}(\lambda)]},ck,id$.

##### $\underline{\mathsf{PKE.Enc}(pk,m)}$

  1. 1.

Parse $(cpk,\mathsf{OPMem})=pk$.

  2. 2.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

  3. 3.

Sample a PRF key $K_{2}$ for $F_{2}$ as $K_{2}\leftarrow
F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  4. 4.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}(\mathsf{PCt}_{\mathsf{OPMem},cpk,K_{2},r,m})$, where
$\mathsf{PCt}_{\mathsf{OPMem},cpk,K_{2},r,m}$ is the following program.
$\underline{\mathsf{PCt}_{\mathsf{OPMem},cpk,K_{2},r,m}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded: $\mathsf{OPMem},cpk,K_{2},r,m$ 1. Run
$\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. 2. Output
$\mathsf{IBE.Enc}(cpk,id,m;F_{2}(K_{2},id))$.

  5. 5.

Output $(\mathsf{OPCt},r)$.

##### $\underline{\mathsf{PKE.Dec}(R_{\mathsf{key}},ct)}$

  1. 1.

Parse $((R_{i})_{i\in[c_{L}(\lambda)]},ck,id)=R_{\mathsf{key}}$ and
$(\mathsf{OPCt},r)=ct$.

  2. 2.

For indices $i\in[c_{L}(\lambda)]$ such that $(r)_{i}=1$, apply
$H^{\otimes\kappa(L(\lambda)+\lambda)}$ to $R_{i}$.

  3. 3.

Run the program $\mathsf{OPCt}$ coherently on $id$ and
$(R_{i})_{i\in[c_{L}(\lambda)]}$.

  4. 4.

Measure the output register and denote the outcome by $cct$.

  5. 5.

Output $\mathsf{IBE.Dec}(ck,cct)$.

Correctness with probability $1$ follows in a straightforward manner from the
correctness of the underlying schemes. We claim that the construction is also
secure.

######  Theorem 27.

$\mathsf{PKE}$ satisfies strong $\gamma$-anti-piracy for any inverse
polynomial $\gamma$.

When we instantiate the assumed building blocks with known constructions, we
get the following corollary.

######  Corollary 4.

Assuming subexponentially secure $i\mathcal{O}$, one-way functions and LWE,
there exists a public-key encryption scheme that satisfies anti-piracy
security against unbounded collusion.

###### Proof.

$\mathsf{IBE}$ can be constructed based on $i\mathcal{O}$ and one-way
functions (Corollary 2). $F_{1}$ and $F_{2}$ can be constructed based on one-
way functions (Theorem 4). $\mathsf{CCObf}$ can be constructed based on
$i\mathcal{O}$ and LWE (Theorem 8). ∎

###  6.3 Proof of Strong Anti-Piracy

In this section, we will prove Theorem 27. Throughout the proof, we will
interpret identity strings for $\mathsf{IBE}$, which are $\lambda$-bit
strings, as integers in the set $\\{0,1,\dots,2^{\lambda}\\}$. Without loss of
generality, we assume that $\mathsf{IBE}$ can also encrypt the symbol $\top$,
which is outside the message space $\mathcal{M}$ for $\mathsf{PKE}$.

Fix any inverse polynomial $\gamma(\lambda)$ and suppose for a contradiction
that there exists an efficient adversary $\mathcal{A}$ that wins the strong
$\gamma$-anti-piracy game with non-negligible probability. Let $k$ denote the
number of keys obtained by the adversary. Define $\mathsf{Hyb}_{0}$ to be the
original security game
$\mathsf{PKEStrongAntiPiracy}(\lambda,\gamma(\lambda),\mathcal{A})$.

#### Making Key Identities Unique

Define $\mathsf{Hyb}_{1}$ by modifying $\mathsf{Hyb}_{0}$ by changing the way
we sample the identity strings (in $\mathsf{PKE.QKeyGen}$) during each quantum
key query as follows. Let the challenger record each sampled identity when
answering each query, and when answering a new query, it samples uniformly at
random an identity value from the set $\\{1,\dots,2^{\lambda}-1\\}$ _that has
not appeared before_ 141414Note that this can be done on-the-go in polynomial
time, with overwhelming probability, e.g. through rejection sampling. That is,
we sample unique identity strings for each quantum key. Also, we define the
following notation. Let $id_{\alpha(i)}$ be the $i^{th}$ value sampled where
$\alpha(\cdot)$ is the permutation $[k]\to[k]$ such that
$0<id_{1}<\dots<id_{k}<2^{\lambda}$. That is, $id_{\alpha(i)}$ is the identity
string that is sampling during the $i^{th}$ query of the adversary. For
simplicity of notation, we also set $id_{0}=0$ and $id_{k+1}=2^{\lambda}$.

######  Claim 3.

$|\mathsf{Hyb}_{0}-\mathsf{Hyb}_{1}|<\exp(-\lambda)$.

###### Proof.

An easy calculation shows that uniformly and independently sampling from
$\\{0,1,\dots,2^{\lambda}-1\\}$ $k$ times gives $k$ unique values from the set
$\\{1,\dots,2^{\lambda}-1\\}$ with probability at least

$1-\frac{k^{2}(\lambda)}{2^{\lambda}}.$

The result follows since $k(\cdot)$ is a polynomial. ∎

#### Making the Challenger Efficient

Define $\mathsf{Hyb}_{2}$ by modifying $\mathsf{Hyb}_{1}$ as follows. At the
end of the game, instead of using threshold implementations
$\mathsf{TI}_{\ell,\mathcal{D},1/2+\gamma}$, the challenger uses approximate
threshold implementations
$\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},1/2+\frac{31\gamma}{32}}$
with $\varepsilon=\frac{\gamma}{32k}$ and $\delta=2^{-10\lambda}\cdot
2^{-10\lambda^{C_{\mathsf{MoE.Coll}}}}$. It outputs $1$ if and only if all
$\mathsf{ATI}$ output $1$.

######  Claim 4.

$\Pr[\mathsf{Hyb}_{2}=1]>\Pr[\mathsf{Hyb}_{1}=1]-{\exp(-\lambda)}$.

###### Proof.

Let $\sigma$ be the $(k+1)$-partite state output by the adversary. By Theorem
14, we get

$\Tr[\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k+1]}\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},1/2+\frac{31\gamma}{32}}}\right)\sigma]\geq\Tr[\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k+1]}\mathsf{TI}_{\ell,\mathcal{D},1/2+\gamma}}\right)\sigma]-(k(\lambda)+1)\cdot\exp(-\lambda).$

Observe that the trace expressions on the left-hand side and the right-hand
side are the winning probabilities in $\mathsf{Hyb}_{2}$ and
$\mathsf{Hyb}_{1}$ respectively. The result follows since $k(\lambda)$ is a
polynomial. ∎

Therefore, $\mathcal{A}$ wins in $\mathsf{Hyb}_{2}$ with probability
$\frac{1}{p(\cdot)}$ for some polynomial $p(\cdot)$ and infinitely many values
of $\lambda>0$. Note that in $\mathsf{Hyb}_{2}$, now the challenger is also
efficient by Theorem 13 and our choice of $\varepsilon,\delta$.

The rest of the proof will be devoted to showing that using $\mathcal{A}$, we
can construct an adversary that breaks the monogamy-of-entanglement game
$\mathsf{MoE-Coll}$ (Theorem 19). We will use projective and threshold
implementations for various mixtures of measurements. The public key $pk$, the
identity strings $id_{1},\dots,id_{k}$ and the permutation $\alpha$ will be
part of the classical state $st$ of the challenger, in the sense of Definition
20. The particular distribution on the collection of projective measurements
(induced by a challenge ciphertext distribution) will vary, and it will be
denoted explicitly.

######  Notation.

For all $j\in[k]$, let
$(A_{i}^{j},s_{i}^{j},s_{i}^{{}^{\prime}j})_{{i\in[c_{L}(\lambda)]}}$ denote
the tuple of subspaces and vectors sampled during the sampling of the
$(\alpha^{-1}(j))$-th key. That is, it is the coset tuple associated with
$id_{j}$.

#### A Monogamy-of-Entanglement Type Game

First, we define the following monogamy-of-entanglement type game
$\mathcal{G}$ for a tuple of adversaries
$(\mathcal{A}^{\prime}_{0},\mathcal{A}^{\prime}_{1},\mathcal{A}^{\prime}_{2})$.
Observe that it will be straightforward to reduce the above game $\mathcal{G}$
to $\mathsf{MoE-Coll}$ with no loss of security, since the former is the same
as the latter except that it includes an independent $\mathsf{IBE}$ instance
that does not affect the game.

#####
$\underline{\mathcal{G}(\lambda,(\mathcal{A}^{\prime}_{0},\mathcal{A}^{\prime}_{1},\mathcal{A}^{\prime}_{2}))}$

  1. 1.

The challenger executes $pk,sk\leftarrow\mathsf{PKE.Setup}(1^{\lambda})$ and
submits $pk$ to $\mathcal{A}^{\prime}_{0}$.

  2. 2.

For multiple rounds, $\mathcal{A}^{\prime}$ makes quantum key queries. For
each query, the challenger samples a quantum key as in $\mathsf{PKE.QKeyGen}$,
but by sampling the identity $id$ in a collusion-free way (as in
$\mathsf{Hyb}_{1}$), and submits it to $\mathcal{A}_{0}^{\prime}$.

  3. 3.

The adversary outputs a _bipartite_ register $R_{\mathsf{bip}}$ and an index
$j^{*}\in[k]$, where $k$ is the number of queries it made.

  4. 4.

For $\ell\in\\{1,2\\}$, the challenger does the following.

    1. 4.1.

Sample $r_{\ell}\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 4.2.

Run $\mathcal{A}^{\prime}_{\ell}$ on $R_{\mathsf{bip}}[\ell]$,
$(A^{j^{*}}_{i})_{i\in[c_{L}(\lambda)]}$ and $r_{\ell}$ to obtain a tuple of
vectors $(v_{\ell,i})_{i\in[{c_{L}(\lambda)}]}$.

    3. 4.3.

For all $i\in[c_{L}(\lambda)]$, check if $v_{\ell,i}\in
A^{j^{*}}_{i}+s^{j^{*}}_{i}$ if $(r_{\ell})_{i}=0$ and check if
$v_{\ell,i}\in{(A^{j^{*}})}^{\perp}_{i}+s^{{}^{\prime}{j^{*}}}_{i}$ if
$(r_{\ell})_{i}=1$.

If all the checks pass, the challenger outputs $1$. Otherwise, it outputs $0$.

Now, we construct a tuple of adversaries
$(\mathcal{A}^{\prime}_{0},\mathcal{A}^{\prime}_{1},\mathcal{A}^{\prime}_{2})$
for $\mathcal{G}$, starting with $\mathcal{A}^{\prime}_{0}$. Let
$\mathcal{D}_{j}$ for $j\in\\{0,\dots,k+1\\}$ be efficient ciphertext
distributions, which we will define later.
$\underline{\mathcal{A}_{0}^{\prime}(pk)}$ 1. Simulate $\mathcal{A}$ on $pk$
by making a quantum secret key query to the challenger whenever $\mathcal{A}$
makes a query, and forwarding the obtained key to it. Let $R_{\mathsf{adv}}$
be the $(k+1)$-partite register (with state $\sigma$) and
$(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]}$ be the challenge messages output
by $\mathcal{A}$ at the end of the query phase. 2. Uniformly at random sample
$x,y,j^{*}$ such that $1\leq x<y\leq k+1$ and $j^{*}\in\\{1,\dots,k\\}$. 3.
Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{0}}$ to all
registers $R_{\mathsf{adv}}[\ell]$ for $\ell\in[k+1]$, let $b_{\ell,0}$ be the
measurement outcomes. 4. Apply
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in succession for
$i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[x]$, let $b_{x,i}$ be the measurement
outcomes. 5. Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$
in succession for $i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[y]$, let $b_{y,i}$ be
the measurement outcomes. 6. Output $\displaystyle($
$\displaystyle(R_{\mathsf{adv}}[x],j^{*},x,y,(b_{\ell,0})_{\ell\in[k+1]},(b_{x,i})_{i\in[j^{*}]},(b_{y,i})_{i\in[j^{*}]}),$
$\displaystyle(R_{\mathsf{adv}}[y],j^{*},x,y,(b_{\ell,0})_{\ell\in[k+1]},(b_{x,i})_{i\in[j^{*}]},(b_{y,i})_{i\in[j^{*}]},),$
$\displaystyle j^{*}).$

For $j\in\\{1,\dots,k\\}$, define $\mathcal{D}_{j}$ to be the challenge
ciphertext distribution where an encryption of a message $m$ is computed as
follows.

  1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

  2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  3. 3.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\color[rgb]{1,0,0}\mathsf{PCt}^{(j)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}}})$
$\underline{\mathsf{PCt}^{(j)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded: $\mathsf{OPMem},cpk,K_{2},r,m,{\color[rgb]{1,0,0}id_{j}}$ 1. Run
$\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. 2. If $id<id_{j}$, set $a=\top$. Otherwise, set
$a=m$. 3. Output
$\mathsf{IBE.Enc}(cpk,id,{\color[rgb]{1,0,0}a};F_{2}(K_{2},id))$.

  4. 4.

Output $(\mathsf{OPCt},r)$.

We define $\mathcal{D}_{0}$ to be the honest ciphertext distribution
$\mathcal{D}$ and we define $\mathcal{D}_{k+1}$ as follows.

  1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

  2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  3. 3.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\color[rgb]{1,0,0}\mathsf{PCt}^{(k+1)}_{\mathsf{OPMem},cpk,K_{2},r}})$
$\underline{\mathsf{PCt}^{(k+1)}_{\mathsf{OPMem},cpk,K_{2},r}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded: $\mathsf{OPMem},cpk,K_{2},r$ 1. Run
$\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. 2. Output
$\mathsf{IBE.Enc}(cpk,id,{\color[rgb]{1,0,0}\top};F_{2}(K_{2},id))$.

  4. 4.

Output $(\mathsf{OPCt},r)$.

Note that this distribution does not actually use the message $m$.

Observe that $\mathcal{A}_{0}^{\prime}$ can indeed execute
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$. The identity
strings $id_{j}$ are part of the quantum secret keys. Further, the adversary
can record the order in which the identity strings are received and also their
sorted version, so it can index them as $id_{j}$.

######  Notation.

Let ${\mathsf{Exp}}_{{\mathcal{C}},{\ell}}$ denote the outcome of the
following experiment where $\mathcal{C}$ is a ciphertext distribution that can
depend on $pp$.

  1. 1.

Execute $pk,sk\leftarrow\mathsf{PKE.Setup}(1^{\lambda})$.

  2. 2.

Simulate the first two steps of $\mathcal{A}^{\prime}_{0}$ and the challenger
of $\mathcal{G}$:

    1. 2.1.

Simulate $\mathcal{A}$ on $pk$ by sampling a quantum secret key (as in
$\mathsf{Hyb}_{1}$) whenever $\mathcal{A}$ makes a query, and submitting the
key to it. Let $R_{\mathsf{adv}},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]}$
be the output of $\mathcal{A}$.

    2. 2.2.

Uniformly at random sample $x,y,j^{*}$ such that $1\leq x<y\leq k+1$ and
$j^{*}\in\\{1,\dots,k\\}$.

  3. 3.

Set
$pp=(x,y,j^{*},(id_{j})_{j\in[k+1]},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]},pk)$.

  4. 4.

Sample $b\leftarrow\\{0,1\\}$.

  5. 5.

Sample $ct\leftarrow\mathcal{C}(pp,m_{\ell}^{b})$.

  6. 6.

Output $R_{\mathsf{adv}},(b,ct),pp$.

We will write
${\mathsf{Exp}}_{{\mathcal{C}},{\ell}}\approx_{\nu}^{c}{\mathsf{Exp}}_{{\mathcal{C}^{\prime}},{\ell}}$
to denote that the advantage of any computational adversary in distinguishing
the outcomes of these experiments is $\nu$.

We will obtain efficient $\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime}$
using Definition 5 such that
$(\mathcal{A}^{\prime}_{0},\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime})$
wins $\mathcal{G}$ with probability

$\frac{1}{2^{0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$

#### Finding a Simultaneous Jump

In the claim below, we will formalize the following fact. Observe the
adversary only obtains $k$ different identity keys for $\mathsf{IBE}$.
Therefore, informally, by pigeonhole principle, two of the $k+1$ freeloaders
must be using $\mathsf{IBE}$ encryptions of their challenge message under the
same identity $id_{j}$ to decode their challenge ciphertext. This will in turn
mean that they must be using the same coset state tuple, which is a
contradiction by the monogamy-of-entanglement property.

######  Claim 5.

Let $\tau$ be the state of the bipartite register $R_{\mathsf{adv}}[x,y]$
output by $\mathcal{A}^{\prime}_{0}$ in $\mathcal{G}$, and also consider the
classical values $j^{*},x,y,\\{b_{\ell,i}\\}_{\ell,i}$ contained in the output
of $\mathcal{A}^{\prime}_{0}$.

Suppose we apply the measurement
$\mathsf{API}^{\varepsilon,\delta}_{x,\mathcal{D}_{j^{*}+1}}\otimes\mathsf{API}^{\varepsilon,\delta}_{y,\mathcal{D}_{j^{*}+1}}$
to $\tau$ and let $b_{x,j^{*}+1},b_{y,j^{*}+1}$ denote the measurement
outcomes we obtain. Then,

$\Pr[b_{x,j^{*}}-b_{x,j^{*}+1}>\frac{29\gamma}{32k}\wedge
b_{y,j^{*}}-b_{y,j^{*}+1}>\frac{29\gamma}{32k}]>\frac{1}{4p(\lambda)\cdot
k^{3}(\lambda)}$

where the probability is taken over the randomness of the challenger, the
adversary $\mathcal{A}_{0}^{\prime}$ and the measurement outcomes.

###### Proof.

Consider instead the following modified version of $\mathcal{A}_{0}^{\prime}$.
We run $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in
succession from $i=0$ to $i=k+1$ on all registers $\ell\in[k+1]$ of
$R_{\mathsf{adv}}$, to obtain values $b^{\prime}_{\ell,i}$. While the ordering
of execution between the registers does not matter, since local operations on
disjoint registers commute, for convenience, assume that we run
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ on all registers
before moving onto
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i+1}}$. Let $\rho_{i}$
denote the post-measurement state after having run
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ on all sub-
registers.

First, we claim that

$\Pr[\forall\ell\in[k+1]~{}~{}b^{\prime}_{\ell,{k+1}}<1/2+\frac{2\gamma}{32}\bigg{|}\forall\ell\in[k+1]\forall
i\in\\{0,\dots,k\\}~{}~{}b^{\prime}_{\ell,i}=b^{\prime\prime}_{\ell,i}]\geq
1-(k(\lambda)+1)\cdot\exp(-\lambda).$ (1)

for any fixed tuple of values
$(b^{\prime\prime}_{\ell,i})_{\ell\in[k+1],i\in\\{0,\dots,k\\}}$ in the joint
support of $(b^{\prime}_{\ell,i})_{\ell\in[k+1],i\in\\{0,\dots,k\\}}$. To
prove this, we will instead prove the more general statement that for any
quantum state $\xi$ of appropriate dimension, we have

$\Pr[\forall\ell\in[k+1]~{}x_{\ell}<\frac{1}{2}+\frac{2\gamma}{32}]\geq
1-(k(\lambda)+1)\cdot\exp(-\lambda).$

where
$(x_{\ell})_{\ell\in[k+1]}\leftarrow\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k+1]}\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{k+1}}}\right)\cdot\xi$.

Let $\iota$ be any quantum state of appropriate dimension. By Theorem 13, we
have for all $\ell\in[k+1]$

$\displaystyle\Pr[\mathopen{}\mathclose{{}\left(\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{k+1}}}\right)\cdot\iota\geq\frac{1}{2}+\frac{2\gamma}{32}]$
$\displaystyle\leq$
$\displaystyle\Pr[\mathopen{}\mathclose{{}\left(\mathsf{PI}_{\ell,\mathcal{D}_{k+1}}}\right)\cdot\iota\geq\frac{1}{2}+\frac{\gamma}{32}]+\exp(-\lambda).$

Then, by Theorem 9, we have that if the outcome of
$\mathsf{PI}_{\ell,\mathcal{D}_{k+1}}$ is $p^{\prime}$, then the post-
measurement state has success probability $p^{\prime}$ for the distribution
$\mathcal{D}_{k+1}$. However, the challenge ciphertext sampled according to
$\mathcal{D}_{k+1}$ is independent of the challenge bit $b$, hence we always
have $p^{\prime}\leq 1/2$. Hence,

$\Pr[\mathopen{}\mathclose{{}\left(\mathsf{PI}_{\ell,\mathcal{D}_{k+1}}}\right)\cdot\iota\geq\frac{1}{2}+\frac{\gamma}{32}]=0.$

Therefore,
$\Pr[\mathopen{}\mathclose{{}\left(\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{k+1}}}\right)\cdot\iota\geq\frac{1}{2}+\frac{2\gamma}{32}]\leq\exp(-\lambda)$.
Now, if we apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{k+1}}$
to each part $\xi[i]$, even conditioned on some outcome obtained for the other
parts, we get that the result will be $\geq 1/2+2\gamma/32$ with probability
at most $\exp(-\lambda)$, since we showed the result above for any state
$\iota$. Hence, probability of obtaining an outcome $\geq 1/2+2\gamma/32$ for
at least one part is at most $(k(\lambda)+1)\cdot\exp(-\lambda)$. This gives
the desired result (Equation 1).

Now, we claim that we have
$b^{\prime}_{\ell,1}\geq\frac{1}{2}+\frac{31\gamma}{32}$ for all
$\ell\in[k+1]$ with probability $1/(2p(\lambda))$. First, by assumption we
have

$\Pr[\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k+1]}\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},1/2+\frac{31\gamma}{32}}}\right)\sigma]\geq
1/p(\lambda).$

since this is exactly the winning condition in $\mathsf{Hyb}_{2}$. While we
later apply other measurements, they do not change the marginal distribution
of the initial measurement since we cannot signal backwards in time.

Assume for now that
${\mathsf{Exp}}_{{\mathcal{D}},{\ell}}\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}_{1}},{\ell}}$
for all $\ell\in[k+1]$ and we will prove it later (26). Then, by Theorem 12
and by above we get

$\displaystyle\Pr[\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k+1]}\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{1},1/2+\frac{31\gamma}{32}}}\right)\sigma]$
(2) $\displaystyle\geq$
$\displaystyle\Pr[\mathopen{}\mathclose{{}\left(\bigotimes_{\ell\in[k+1]}\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},1/2+\frac{31\gamma}{32}}}\right)\sigma]-\mathsf{negl}(\lambda)>1/(2\cdot
p(\lambda)).$ (3)

In Theorem 12, it is easy to see ${\mathsf{Exp}}_{{\mathcal{D}},{\ell}}$
corresponds to $(\mathcal{S},\mathcal{D})$ and
${\mathsf{Exp}}_{{\mathcal{D}_{1}},{\ell}}$ corresponds to
$(\mathcal{S},\mathcal{D}_{1})$; while the measurement results
$\vec{p_{0}},\vec{p_{1}}$ correspond to
$\bigotimes_{\ell\in[k+1]}\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}}\sigma$
and
$\bigotimes_{\ell\in[k+1]}\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{1}}\sigma$
when we define our collection of measurements as in Definition 20. That is,
our measurement is executing the given state as a decryptor using
$\mathsf{U}_{quantum}$ and comparing the outcome to $b$.

Finally, by combining Equation 1 and Equation 2, we get that with probability
at least $1/(4\cdot p(\lambda))$, we have that
$\frac{1}{2}+\frac{31\gamma}{32}\leq b^{\prime}_{\ell,1}$ and
$b^{\prime}_{\ell,k+1}<\frac{1}{2}+\frac{2\gamma}{32}$ for all $\ell\in[k+1]$.
Hence, we see that with probability at least $\frac{1}{4p(\lambda)}$; for all
$\ell\in[k+1]$ there is $i_{\ell}\in\\{1,\dots,k\\}$ such that
$b^{\prime}_{\ell,i_{\ell}}-b^{\prime}_{\ell,i_{\ell}+1}>\frac{29\gamma}{32k}$.
Then, by pigeonhole principle, there is $\ell\neq\ell^{\prime}$ such that
$i_{\ell}=i_{\ell^{\prime}}$.

We claim that for any fixed $x<y\in[k+1]$ and $j^{*}\in[k]$, the marginal
distribution (i.e., the reduced density matrix) of
$\rho_{j^{*}}[x,y],(b^{\prime}_{\ell,0})_{\ell\in[k+1]},(b^{\prime}_{x,i})_{i\in[j^{*}+1]},(b^{\prime}_{y,i})_{i\in[j^{*}+1]}$
in the above experiment is the same as the distribution of
$\tau,(b_{\ell,0})_{\ell\in[k+1]},(b_{x,i})_{i\in[j^{*}+1]},(b_{y,i})_{i\in[j^{*}+1]}$
conditioned on the fixed values of $x,y,j^{*}$. This follows from two
arguments. First, no-signalling between disjoint registers gives that whether
or not we apply measurements on the other registers does not change the
marginal distributions of measurement outcomes and post-measurement states on
registers $x,y$. Similarly, by the time we are applying measurements for
$\mathcal{D}_{i}$ for $i\geq j^{*}+1$, the measurement outcomes for
$\mathcal{D}_{j^{*}}$ are already determined. Since it is not possible to
signal backwards in time, the marginal distributions for measurement outcomes
$b_{\ell,j^{*}}$ is not affected by whether or not we apply the measurements
for $\mathcal{D}_{i}$ for $i\geq j^{*}+1$.

We have already shown that with probability $1/(4p(\lambda))$, there is
guaranteed to be a _jump_ in measurement results. Since $x,y,j^{*}$ are
sampled independently by $\mathcal{A}^{\prime}_{0}$, they hit the correct
indices $\ell,\ell^{\prime}$ satisfying $i_{\ell}=i_{\ell^{\prime}}$ with
probability $1/k{k+1\choose 2}$ and $j^{*}$ hits $i_{\ell}=i_{\ell^{\prime}}$
with probability $1/k$. Therefore, we finally have

$\Pr[b_{x,j^{*}}-b_{x,j^{*}+1}>\frac{29\gamma}{32k}\wedge
b_{y,j^{*}}-b_{y,j^{*}+1}>\frac{29\gamma}{32k}]>\frac{1}{4\cdot
p(\lambda)\cdot k^{3}(\lambda)}.$

∎

Now, we define some intermediary challenge ciphertext distributions. Define
the following for all $j\in\\{0,1,\dots,k\\}$ and
$\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$. For notational convenience, also
define $\mathcal{D}_{j}^{id_{j+1}-id_{j},0}$ to be $\mathcal{D}_{j+1}^{(0,0)}$
for all $j\in\\{0,1,\dots,k\\}$. Also note that $\mathcal{D}_{j}^{(0,0)}$ is
exactly the same as $\mathcal{D}_{j}$ for $j\in[k]$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,0)}(m)}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,0)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}+\Delta}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,0)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}+\Delta}}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded: ${\mathsf{OPMem},cpk,K_{2},r,m,{\color[rgb]{1,0,0}id_{j}+\Delta}}$
(a) Run $\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs
$0$, output $\perp$ and terminate. (b) If $id<id_{j}+\Delta$, set $a=\top$.
Otherwise, set $a=m$. (c) Output
$\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    4. 4.

Output $(\mathsf{OPCt},r)$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,1)}(m)}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,m;F_{2}(K_{2},id_{j}+\Delta)).$

    4. 4.

$K_{2}\\{id_{j}+\Delta\\}\leftarrow F_{2}.\mathsf{Punc}(K_{2},id_{j}+\Delta)$.

    5. 5.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,1)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,1)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,{\color[rgb]{1,0,0}K_{2}\\{id_{j}+\Delta\\}},r,m,id_{j}+\Delta,{\color[rgb]{1,0,0}ct^{*}}}$
(a) Run $\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs
$0$, output $\perp$ and terminate. (b) If $id=id_{j}+\Delta$, output $ct^{*}$
and terminate. (c) If $id<id_{j}+\Delta+1$, set $a=\top$. Otherwise, set
$a=m$. (d) Output $\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    6. 6.

Output $(\mathsf{OPCt},r)$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,2)}(m)}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

Sample $z^{*}$ uniformly at random from the output space of $F_{2}$.

    4. 4.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,m;z^{*}).$

    5. 5.

$K_{2}\\{id_{j}+\Delta\\}\leftarrow F_{2}.\mathsf{Punc}(K_{2},id_{j}+\Delta)$.

    6. 6.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,2)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,2)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,{K_{2}\\{id_{j}+\Delta\\}},r,m,id_{j}+\Delta,{ct^{*}}}$
(a) Run $\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs
$0$, output $\perp$ and terminate. (b) If $id=id_{j}+\Delta$, output $ct^{*}$
and terminate. (c) If $id<id_{j}+\Delta+1$, set $a=\top$. Otherwise, set
$a=m$. (d) Output $\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    7. 7.

Output $(\mathsf{OPCt},r)$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,3)}(m)}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

Sample $z^{*}$ uniformly at random from the output space of $F_{2}$.

    4. 4.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,m;z^{*}).$

    5. 5.

$K_{2}\\{id_{j}+\Delta\\}\leftarrow F_{2}.\mathsf{Punc}(K_{2},id_{j}+\Delta)$.

    6. 6.

Compute
$(A^{*}_{i},s_{i}^{*},s_{i}^{{}^{\prime}{*}})=F_{1}(K_{1},id_{j}+\Delta).$

    7. 7.

For $i\in[c_{L}(\lambda)]$, set $g_{i}=\mathsf{Can}_{A^{*}_{i}}$ if
$(r)_{i}=0$ and set $g_{i}=\mathsf{Can}_{(A^{*}_{i})^{\perp}}$ if $(r)_{i}=1$.

    8. 8.

For $i\in[c_{L}(\lambda)]$, compute $y_{i}=g_{i}(s_{i}^{*})$ if $(r)_{i}=0$
and $y_{i}=g_{i}(s_{i}^{{}^{\prime}{*}})$ if $(r)_{i}=1$.

    9. 9.

Set $g$ to be the function
$g(v_{1},\dots,v_{c_{L}(\lambda)})=(g_{1}(v_{1})||\dots||g_{c_{L}(\lambda)}(v_{c_{L}(\lambda)}))$.

    10. 10.

Set $y=y_{1}||\dots||y_{c_{L}(\lambda)}$.

    11. 11.

$\mathsf{OCC}\leftarrow\mathsf{CCObf.Obf}(g,y,ct^{*})$.

    12. 12.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,3)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}\\},r,m,id_{j}+\Delta,\mathsf{OCC}}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,3)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,\mathsf{OCC}}}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,{K_{2}\\{id_{j}+\Delta\\}},r,m,id_{j}+\Delta,{\color[rgb]{1,0,0}\mathsf{OCC}}}$
(a) If $id=id_{j}+\Delta$, output the output of
$\mathsf{OCC}(u_{1},\dots,u_{c_{L}(\lambda)})$ and terminate. (b) Run
$\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. (c) If $id<id_{j}+\Delta+1$, set $a=\top$.
Otherwise, set $a=m$. (d) Output
$\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    13. 13.

Output $(\mathsf{OPCt},r)$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,4)}(m)}$: Same as
$\mathcal{D}_{j}^{(\Delta,3)}$ except for the following. Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,m;z^{*})$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,{\color[rgb]{1,0,0}\top};z^{*}).$

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,5)}(m)}$: Same as
$\mathcal{D}_{j}^{(\Delta,2)}$ except for the following. Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,m;z^{*})$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,{\color[rgb]{1,0,0}\top};z^{*}).$

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,6)}(m)}:$ Same as
${\mathcal{D}_{j}^{(\Delta,1)}}$ except for the following. Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,m;F_{2}(K_{2},id_{j}+\Delta))$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}+\Delta,{\color[rgb]{1,0,0}\top};F_{2}(K_{2},id_{j}+\Delta)).$

Now, we show that these distributions _collapse_ around $\Delta=0$ for each
$j$. Below, all our indistinguishability claims are for $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries and we set
$\nu(\lambda)=2^{-6\lambda}\cdot 2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

######  Claim 6.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,0)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,1)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Observe that by punctured key correctness of $F_{2}$ (Definition 1), the
different obfuscated programs
${\mathsf{PCt}^{(j,\Delta,0)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}+\Delta}}$
and
${\mathsf{PCt}^{(j,\Delta,1)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}$
in these hybrids have the same functionality. The result follows by security
of $i\mathcal{O}$ and by our choice of parameters. ∎

######  Claim 7.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,1)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,2)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

The result follows by selective puncturing security of $F_{2}$ (Definition 1)
and our choice of parameters. ∎

######  Claim 8.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,2)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Observe that the obfuscated ciphertext programs $\mathsf{PCt}$ in these
hybrids have the same functionality by correctness of $\mathsf{CCObf}$, since
a vector $w$ is in $A_{i}^{*}+s_{i}^{*}$ if and only if
$\mathsf{Can}_{A_{i}^{*}}(w)=\mathsf{Can}_{A_{i}^{*}}(s_{i}^{*})$ and
similarly for $(A^{*})_{i}^{\perp}+s^{{}^{\prime}*}_{i}$. Then, the claim
follows by the security of $i\mathcal{O}$. ∎

######  Claim 9.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4)}}},{\ell}}$
if

  * •

$j\in\\{1,\dots,k\\}$ and $\Delta\in\\{1,\dots,id_{j+1}-id_{j}-1\\}$, or

  * •

$j=0$ and $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$

and for all $\ell\in[k+1]$.

###### Proof.

Observe that in these hybrids, the randomness used to invoke
$\mathsf{IBE.Enc}$ to compute $ct^{*}$ is uniformly and independently sampled.
Further, the adversary only has the $\mathsf{IBE}$ keys for the identities
$id_{1},id_{2},\dots,id_{k}$, all of which are different from the identity
$id_{j}+\Delta$ under which $ct^{*}$ is encrypted. Hence, by IBE security
(Definition 10), the result follows. ∎

######  Claim 10.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,5)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Essentially the same argument as in 21 yields the result. ∎

######  Claim 11.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,5)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,6)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Essentially the same argument as in 20 yields the result. ∎

######  Claim 12.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,6)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta+1,0)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Essentially the same argument as in 19 yields the result. ∎

######  Claim 13.

For all $\ell\in[k+1]$, we have

  * •

${\mathsf{Exp}}_{{\mathcal{D}_{0}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{\mathcal{D}_{1}},{\ell}}$

  * •

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(0,4)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{\mathcal{D}_{j+1}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$

  * •

${\mathsf{Exp}}_{{\mathcal{D}_{j}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(0,3)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$

where $\nu(\lambda)=2^{-5\lambda}\cdot
2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

###### Proof.

It is easy to see that
$\mathcal{D}_{0}\approx^{c}_{\nu(\lambda)}\mathcal{D}_{0}^{(0,0)}$ and
$\mathcal{D}_{k+1}\approx^{c}_{\nu(\lambda)}\mathcal{D}_{k+1}^{(0,0)}$ by the
security of $i\mathcal{O}$.

Rest follows by a simple calculation using the above results. ∎

######  Notation.

We will write $\mathcal{D}^{\prime}$ to denote $\mathcal{D}_{j^{*}}^{(0,3)}$
and $\mathcal{D}^{\prime\prime}$ to denote $\mathcal{D}_{j^{*}}^{(0,4)}$ where
$j^{*}$ is as output by $\mathcal{A}_{0}^{\prime}$.

######  Claim 14.

Let $\tau$ be the bipartite state output by $\mathcal{A}^{\prime}_{0}$ in
$\mathcal{G}$. Let $p^{\prime}_{x},p^{\prime}_{y}$ be the outcome of applying
$\mathsf{PI}_{x,\mathcal{D}^{\prime}}\otimes\mathsf{PI}_{y,\mathcal{D}^{\prime}}$
to $\tau$. Similarly, let $p^{\prime\prime}_{x},p^{\prime\prime}_{y}$ be the
outcome of applying
$\mathsf{PI}_{x,\mathcal{D}^{\prime\prime}}\otimes\mathsf{PI}_{y,\mathcal{D}^{\prime\prime}}$
to $\tau$. Then,

  * •

$\Pr[p^{\prime}_{x}>b_{x,j^{*}}-\frac{3\gamma}{32k}\wedge
p^{\prime}_{y}>b_{y,j^{*}}-\frac{3\gamma}{32k}]\geq 1-2^{-2\lambda}\cdot
2^{-4\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

  * •

$\Pr[b_{x,j^{*}}-p^{\prime\prime}_{x}>\frac{28\gamma}{32k}\wedge
b_{y,j^{*}}-p^{\prime\prime}_{y}>\frac{28\gamma}{32k}]>\frac{1}{q(\lambda)}$
for some polynomial $q(\cdot)$.

###### Proof.

Let $(a^{\prime}_{x},a^{\prime}_{y})$ be the outcome of applying
$\mathsf{API}^{\varepsilon,\delta}_{x,\mathcal{D}_{j^{*}}}\otimes\mathsf{API}^{\varepsilon,\delta}_{y,\mathcal{D}_{j^{*}}}$
to $\tau$. Then, by Theorem 15, Theorem 14 and by definition of
$b_{x,j^{*}},b_{y,j^{*}}$, we have

$\Pr[a^{\prime}_{x}>b_{x,j^{*}}-\frac{3\gamma}{32k}\wedge
a^{\prime}_{y}>b_{y,j^{*}}-\frac{3\gamma}{32k}]\geq
1-\textnormal{poly}(\lambda)\cdot\delta(\lambda).$

Then, since
${\mathsf{Exp}}_{{\mathcal{D}_{j^{*}}},{\ell}}\approx^{c}_{\nu}{\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{\ell}}$
against $2^{5\lambda}\cdot 2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time
adversaries where $\nu(\lambda)=2^{-5\lambda}\cdot
2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$, we get

$\Pr[p^{\prime}_{x}>b_{x,j^{*}}-\frac{3\gamma}{32k}\wedge
p^{\prime}_{y}>b_{y,j^{*}}-\frac{3\gamma}{32k}]\geq 1-2^{-2\lambda}\cdot
2^{-4\lambda^{0.3C_{\mathsf{MoE.Coll}}}}.$

by Theorem 12.

See the proof of 5 for a remark on how to invoke Theorem 12. Note that here,
we are applying the measurements to $\tau$ rather than to the state $\sigma$.
However, since the procedure that gives $\tau$ from $\sigma$ is an efficient
procedure that only uses $pp$, the indistinguishability between
$\mathcal{D}_{j^{*}}$ and $\mathcal{D}^{\prime}$ given $\sigma$ still applies
when we are instead given $\tau$, hence Theorem 12 indeed applies.

We now move onto the second claim. By 5, we have that

$\Pr[b_{x,j^{*}}-b_{x,j^{*}+1}>\frac{29\gamma}{32k}\wedge
b_{y,j^{*}}-b_{y,j^{*}+1}>\frac{29\gamma}{32k}]$

is non-negligible. Further, we have
${\mathsf{Exp}}_{{\mathcal{D}_{j^{*}+1}},{\ell}}\approx{\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{\ell}}$.
By Theorem 12 and Theorem 16, we get that

$\Pr[b_{x,j^{*}}-p^{\prime\prime}_{x}>\frac{28\gamma}{32k}\wedge
b_{y,j^{*}}-p^{\prime\prime}_{y}>\frac{28\gamma}{32k}]$

is non-negligible. Similar to above, the indistinguishability of
$\mathcal{D}_{j^{*}+1}$ and $\mathcal{D}^{\prime\prime}$ given $\sigma$ still
applies when we are given the state $\tau$ instead. Therefore, Theorem 12
indeed applies. ∎

#### Extracting MoE Vectors

######  Claim 15.

There exist efficient $\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime}$ such
that
$(\mathcal{A}^{\prime}_{0},\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime})$
wins $\mathcal{G}$ with probability
$\frac{1}{2^{0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$

###### Proof.

For a challenge ciphertext distribution $\mathcal{C}$, let
${\mathsf{Exp}}_{{\mathcal{C}},{x}}^{\prime}$ denote the outcome of the
following experiment.

  1. 1.

Execute $pk,sk\leftarrow\mathsf{PKE.Setup}(1^{\lambda})$.

  2. 2.

Simulate $\mathcal{A}^{\prime}_{0}$ and the challenger of $\mathcal{G}$:

    1. 2.1.

Simulate $\mathcal{A}$ on $pk$ by sampling a quantum secret key (as in
$\mathsf{Hyb}_{1}$) whenever $\mathcal{A}$ makes a query, and submitting the
key to it. Let $R_{\mathsf{adv}},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]}$
be the output of $\mathcal{A}$.

    2. 2.2.

Uniformly at random sample $x,y,j^{*}$ such that $1\leq x<y\leq k+1$ and
$j^{*}\in\\{1,\dots,k\\}$.

    3. 2.3.

Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{0}}$ to all
registers $R_{\mathsf{adv}}[\ell]$ for $\ell\in[k+1]$, let $b_{\ell,0}$ be the
measurement outcomes.

    4. 2.4.

Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in succession
for $i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[x]$, let $b_{x,i}$ be the
measurement outcomes.

    5. 2.5.

Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in succession
for $i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[y]$, let $b_{y,i}$ be the
measurement outcomes.

  3. 3.

Set
$pp=(x,y,j^{*},(id_{j})_{j\in[k+1]},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]},pk)$.

  4. 4.

Sample $b\leftarrow\\{0,1\\}$.

  5. 5.

Sample $ct\leftarrow\mathcal{C}(pp,m_{\ell}^{b})$.

  6. 6.

Output $R_{\mathsf{adv}}[x],(b,ct),pp$.

It is easy to see that
${\mathsf{Exp}}_{{\mathcal{C}_{0}},{\ell}}\approx_{\nu}^{c}{\mathsf{Exp}}_{{\mathcal{C}_{1}},{\ell}}$
implies
${\mathsf{Exp}}_{{\mathcal{C}_{0}},{x}}^{\prime}\approx_{\nu}^{c}{\mathsf{Exp}}_{{\mathcal{C}_{1}},{x}}^{\prime}$
since they only differ in their auxiliary states and we can efficiently obtain
the auxiliary state of the former using the auxiliary state of the latter.

By 14, we have

  1. 1.

$\Pr[\mathsf{PI}_{x,\mathcal{D}^{\prime}}\cdot\tau[1]\leq
b_{x,j^{*}}-\frac{3\gamma}{32k}]\leq 2^{-2\lambda}\cdot
2^{-4\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$, and

  2. 2.

$\Pr[\mathsf{PI}_{x,\mathcal{D}^{\prime\prime}}\cdot\tau[1]<b_{x,j^{*}}-\frac{28\gamma}{32k}]$
is non-negligible.

Suppose for a contradiction that
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}}^{\prime}\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{x}}^{\prime}$.
Then, by Theorem 13 and Theorem 12, Item 2 implies that

$\Pr[\mathsf{PI}_{x,\mathcal{D}^{\prime}}\cdot\tau[1]<b_{x,j^{*}}-\frac{26\gamma}{32k}]$

is non-negligible. This is a contradiction to Item 1, therefore,
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}}^{\prime}\not\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{x}}^{\prime}$.
We define the distribution $\mathcal{D}_{sim}$ by modifying
$\mathcal{D}^{\prime}$ as follows: We replace the line

$\mathsf{OCC}\leftarrow\mathsf{CCObf.Obf}(g,y,ct^{*})$

with

$\mathsf{OCC}\leftarrow\mathsf{CCObf.Sim}(1^{\lambda},|g|,|y|,|ct^{*}|).$

Since
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}}^{\prime}\not\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{x}}^{\prime}$,
we have either
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}}^{\prime}\not\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}_{sim}},{x}}^{\prime}$
or
${\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{x}}^{\prime}\not\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}_{sim}},{x}}^{\prime}$.
We will only discuss the first case but the second case follows from the same
argument.

Now, we will give a distribution $\mathcal{B}$ over compute-and-compare
programs (with quantum auxiliary information) and an adversary
$\mathcal{A}_{CC}$ that breaks the security of $\mathsf{CCObf}$ for this
distribution. This in turn will mean by Definition 5 that there is an
adversary that can predict the _target_ value of these programs, given the
description of the compute part of the program and the auxiliary information.

We first define the distribution $\mathcal{B}$.

##### $\underline{\mathcal{B}(1^{\lambda})}$

  1. 1.

Execute $pk,sk\leftarrow\mathsf{PKE.Setup}(1^{\lambda})$.

  2. 2.

Simulate $\mathcal{A}^{\prime}_{0}$ and the challenger of $\mathcal{G}$:

    1. 2.1.

Simulate $\mathcal{A}$ on $pk$ by sampling a quantum secret key (as in
$\mathsf{Hyb}_{1}$) whenever $\mathcal{A}$ makes a query, and submitting the
key to it. Let $R_{\mathsf{adv}},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]}$
be the output of $\mathcal{A}$.

    2. 2.2.

Uniformly at random sample $x,y,j^{*}$ such that $1\leq x<y\leq k+1$ and
$j^{*}\in\\{1,\dots,k\\}$.

    3. 2.3.

Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{0}}$ to all
registers $R_{\mathsf{adv}}[\ell]$ for $\ell\in[k+1]$, let $b_{\ell,0}$ be the
measurement outcomes.

    4. 2.4.

Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in succession
for $i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[x]$, let $b_{x,i}$ be the
measurement outcomes.

    5. 2.5.

Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in succession
for $i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[y]$, let $b_{y,i}$ be the
measurement outcomes.

  3. 3.

Set
$pp=(x,y,j^{*},(id_{j})_{j\in[k+1]},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]},pk)$.

  4. 4.

Sample $b\leftarrow\\{0,1\\}$.

  5. 5.

Simulate the first steps of $\mathcal{D}^{\prime}$ on $m_{x}^{b}$:

    1. 5.1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 5.2.

Sample $z^{*}$ uniformly at random the output space of $F_{2}$.

    3. 5.3.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j},m^{b}_{x};z^{*}).$

    4. 5.4.

Compute
$(A^{*}_{i},s_{i}^{*},s_{i}^{{}^{\prime}{*}})=F_{1}(K_{1},id_{j^{*}}).$

    5. 5.5.

For $i\in[c_{L}(\lambda)]$, set $g_{i}=\mathsf{Can}_{A^{*}_{i}}$ if
$(r)_{i}=0$ and set $g_{i}=\mathsf{Can}_{(A^{*}_{i})^{\perp}}$ if $(r)_{i}=1$.

    6. 5.6.

For $i\in[c_{L}(\lambda)]$, compute $y_{i}=g_{i}(s_{i}^{*})$ if $(r)_{i}=0$
and $y_{i}=g_{i}(s_{i}^{{}^{\prime}{*}})$ if $(r)_{i}=1$.

    7. 5.7.

Set $g$ to be the function
$g(v_{1},\dots,v_{c_{L}(\lambda)})=(g_{1}(v_{1})||\dots||g_{c_{L}(\lambda)}(v_{c_{L}(\lambda)}))$.

    8. 5.8.

Set $y=y_{1}||\dots||y_{c_{L}(\lambda)}$.

  6. 6.

Output $(g,y,ct^{*})$ as the compute-and-compare program and

$(R_{\mathsf{adv}}[x],pp,r,m^{b}_{x},id_{j^{*}},b)$

as the auxiliary information.

We define the adversary $\mathcal{A}_{CC}$ as follows. Let
$\mathcal{A}_{dist}$ be an adversary that distinguishes
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}}\not\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}_{sim}},{x}}$.

##### $\underline{\mathcal{A}_{CC}(P,R_{\mathsf{aux}})}$

  1. 1.

Parse $(R_{\mathsf{}},pp,r,m^{b}_{x},id_{j^{*}},b)=R_{\mathsf{aux}}$.

  2. 2.

Parse
$(x,y,j^{*},(id_{j})_{j\in[k+1]},(m_{\ell}^{0},m_{\ell}^{1})_{\ell\in[k+1]},pk)=pp$.

  3. 3.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  4. 4.

Sample $K_{2}\\{id_{j^{*}}\\}\leftarrow
F_{2}.\mathsf{Punc}(K_{2},id_{j^{*}})$.

  5. 5.

Sample $\mathsf{OPCt}\leftarrow i\mathcal{O}(\mathsf{PCt}).$
$\underline{\mathsf{PCt}(id,u_{1},\dots,u_{c_{L}(\lambda)})}$ Hardcoded:
${\mathsf{OPMem},cpk,{K_{2}\\{id_{j^{*}}\\}},r,m^{b}_{x},id_{j^{*}},P}$ (a) If
$id=id_{j^{*}}$, output the output of $P(u_{1},\dots,u_{c_{L}(\lambda)})$ and
terminate. (b) Run $\mathsf{OPMem}(id,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If
it outputs $0$, output $\perp$ and terminate. (c) If $id<id_{j^{*}}+1$, set
$a=\top$. Otherwise, set $a=m^{b}_{x}$. (d) Output
$\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

  6. 6.

Set $ct=(\mathsf{OPCt},r)$.

  7. 7.

Output $\mathcal{A}_{dist}(R_{\mathsf{}},(ct,b),pp)$.

It is easy to see that
$\mathcal{A}_{CC}(\mathsf{CCObf.Obf}(g,y,ct^{*}),R_{\mathsf{aux}})$
corresponds to
$\mathcal{A}_{dist}({\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}})$ while
$\mathcal{A}_{CC}(\allowdisplaybreaks\mathsf{CCObf.Sim}(1^{\lambda},|g|,|y|,|ct^{*}|),R_{\mathsf{aux}}))$
corresponds to $\mathcal{A}_{dist}({\mathsf{Exp}}_{{\mathcal{D}_{sim}},{x}})$
where $(g,y,ct^{*})\leftarrow\mathcal{B}(1^{\lambda})$. Hence, since
$\mathcal{A}_{dist}$ distinguishes
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{x}}\not\approx^{c}{\mathsf{Exp}}_{{\mathcal{D}_{sim}},{x}}$,
by Theorem 8 there exists an adversary $\mathcal{M}_{1}$ that can extract
vectors $u_{i}$ such that $g((u_{i}))=y$, using the quantum auxiliary
information defined above and the description of $g$. Note that $g$ can be
computed efficiently given $r$ and
$(A^{*}_{i},s^{*}_{i},s^{{}^{\prime}{*}}_{i})_{i\in[c_{L}(\lambda)]}$, which
are indeed provided to $\mathcal{A}^{\prime}_{1}$ in $\mathcal{G}$. Similarly,
$\mathcal{A}_{1}^{\prime}$ can compute $R_{\mathsf{aux}}$ from its input
provided by $\mathcal{A}_{0}^{\prime}$. Therefore, we set
$\mathcal{A}^{\prime}_{1}=\mathcal{M}_{1}$ and it is easy to see that
$\mathcal{A}^{\prime}_{1}$ outputs correct vectors in the game $\mathcal{G}$
with probability at least $2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$,
since $\mathsf{CCObf}$ is a compute-and-compare obfuscation scheme for
$2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$-unpredictable distributions.

Now, we will argue that we can simultaneously extract MoE vectors from the
second register, that is, we can extract even conditioned on a successful
extraction from the first register. Let $\xi$ denote the post-measurement
state of the input state of $\mathcal{A}^{\prime}_{2}$, conditioned on
$\mathcal{A}^{\prime}_{1}$ succeeding. First, define
${\mathsf{Exp}}_{{\mathcal{C}},{y}}^{\prime\prime}$ as follows.

  1. 1.

Simulate $\mathcal{B}(1^{\lambda})$.

  2. 2.

Run $\mathcal{A}^{\prime}_{1}$ on
$(R_{\mathsf{adv}}[x],pp,r,m^{b}_{x},id_{j^{*}},b)$ and $g$ to obtain vectors
$(u_{i})_{i\in c_{L}(\lambda)}$.

  3. 3.

Check if $\mathsf{OPMem}(id_{j^{*}},u_{1},\dots,u_{c_{L}(\lambda)},r)$. If the
output is $0$, output $\perp$ and terminate.

  4. 4.

Sample $b\leftarrow\\{0,1\\}$.

  5. 5.

Sample $ct\leftarrow\mathcal{C}(pp,m_{\ell}^{b})$.

  6. 6.

Output $R_{\mathsf{adv}}[y],(b,ct),pp$.

Observe that the state of the register $R_{\mathsf{adv}}[y]$ output above is
$\xi$ (when the experiment outcome is not $\perp$). We claim that $\xi$
satisfies

  1. 1.

$\Pr[\mathsf{PI}_{y,\mathcal{D}^{\prime}}\cdot\xi\leq
b_{y,j^{*}}-\frac{3\gamma}{32k}]\leq\sqrt{2^{-2\lambda}\cdot
2^{-4\lambda^{0.3C_{\mathsf{MoE.Coll}}}}}\cdot
2^{\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}.$

  2. 2.

$\Pr[\mathsf{PI}_{y,\mathcal{D}_{{}^{\prime\prime}}}\cdot\xi<b_{y,j^{*}}-\frac{28\gamma}{32k}]\geq
2^{-\lambda^{0.3\cdot{C_{\mathsf{MoE.Coll}}}}}.$

This first claim follows from 14, Theorem 6, and the fact that extraction on
the first register succeeds with probability $\geq
2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$. We argue the second claim as
follows. Let $E$ denote the event of successful extraction on the first
register, and let $G$ denote the event that applying
$\mathsf{PI}_{y,\mathcal{D}_{{}^{\prime\prime}}}$ on the second register
yields a value $<b_{y,j^{*}}-\frac{28\gamma}{32k}$. The probability above
corresponds to $\Pr[G|E]$, which equals
$\frac{\Pr[E|G]\cdot\Pr[G]}{\Pr[E]}\geq\Pr[E|G]\cdot\Pr[G]\geq\Pr[E|G]\cdot\frac{1}{\textnormal{poly}(\lambda)}$.
However, observe that we can first apply the measurement
$\mathsf{PI}_{y,\mathcal{D}_{{}^{\prime\prime}}}$ on the second register, and
then try to extract on the first register. Observe that a _gap_ still exists
on the first register after this measurement on the second register and
conditioning on the outcome $G$, by 14 and Theorem 6, since
$\Pr[G]>1/\textnormal{poly}(\lambda)$. Hence, similar to the extraction
argument above, we get that
$\Pr[E|G]>2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$, which proves our
claim.

Now, suppose for a contradiction that
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{y}}^{\prime\prime}\approx^{c}_{\nu}{\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{y}}^{\prime\prime}$
against $2^{3\lambda}\cdot 2^{2\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time
adversaries where $\nu=2^{-2\lambda-1}\cdot
2^{-2\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$. Then, by Theorem 12, we get that
Item 1 implies

$\Pr[\mathsf{PI}_{y,\mathcal{D}_{{}^{\prime\prime}}}\cdot\xi\leq
b_{y,j^{*}}-\frac{3\gamma}{32k}]\leq 2\cdot 2^{-\lambda}\cdot
2^{-\lambda^{0.3\cdot{C_{\mathsf{MoE.Coll}}}}}.$

which is a contradiction to Item 2. Hence,
${\mathsf{Exp}}_{{\mathcal{D}^{\prime}},{y}}^{\prime\prime}\not\approx^{c}_{\nu}{\mathsf{Exp}}_{{\mathcal{D}^{\prime\prime}},{y}}^{\prime\prime}$.
Then, using the same extraction we used for the first register, by the
security of $\mathsf{CCObf}$, we get that there exists an adversary
$\mathcal{A}_{2}^{\prime}$ such that it outputs the correct coset vectors with
probability at least $2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$
_conditioned on $\mathcal{A}^{\prime}_{1}$ outputting correct coset vectors_.
This shows that
$(\mathcal{A}^{\prime}_{0},\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime})$
wins $\mathcal{G}$ with probability
${2^{-0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$ ∎

We have shown that there is an adversary
$(\mathcal{A}_{0}^{\prime},\mathcal{A}_{1}^{\prime},\mathcal{A}_{2}^{\prime})$
that wins the game $\mathcal{G}$ with probability

${1}/{2^{0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$

Finally, we show that we can construct an adversary
$(\mathcal{A}_{0}^{\prime\prime},\mathcal{A}_{1}^{\prime\prime},\mathcal{A}_{2}^{\prime\prime})$
that can win $\mathsf{MoE-Coll}$.

######  Claim 16.

There exists efficient
$\mathcal{A}^{\prime\prime}=(\mathcal{A}_{0}^{\prime\prime},\mathcal{A}_{1}^{\prime\prime},\mathcal{A}_{2}^{\prime\prime})$
such that

$\Pr[\mathsf{MoE-
Coll}(\lambda,L(\lambda),\mathcal{A}^{\prime\prime})=1]\geq{2^{-0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}.$

###### Proof.

$\mathcal{A}_{0}^{\prime\prime}$ simulates both the challenger of
$\mathcal{G}$ and the adversary $\mathcal{A}^{\prime}_{0}$ as follows. It
first samples $cpk,csmk\leftarrow\mathsf{IBE.Setup}(1^{\lambda})$. Then, it
sets $pk=(cpk,\mathsf{OPMem})$ where it obtains $\mathsf{OPMem}$ from its
challenger. Then, whenever $\mathcal{A}^{\prime}_{0}$ makes a key query, it
samples an identity string $id$ in a collusion-free way as in $\mathcal{G}$
and queries its own challenger for the coset state associated with $id$. It
also samples $ck$ as in $\mathsf{PKE.QKeyGen}$ using $cmsk$, and submits the
coset state, $id$ and $ck$ to $\mathcal{A}_{0}^{\prime}$. Finally, when
$\mathcal{A}^{\prime}_{0}$ yields a bipartite register and an index $j^{*}$,
$\mathcal{A}_{0}^{\prime\prime}$ outputs both.

We define $\mathcal{A}_{1}^{\prime\prime}$ to simulate
$\mathcal{A}_{1}^{\prime}$ and make no queries during the second query phase.
$\mathcal{A}_{2}^{\prime\prime}$ is defined similarly for
$\mathcal{A}_{2}^{\prime}$.

It is easy to see that $\mathcal{A}^{\prime\prime}$ playing $\mathsf{MoE-
Coll}$ perfectly simulates $\mathcal{G}$ as played by $\mathcal{A}^{\prime}$,
hence $\mathcal{A}^{\prime\prime}$ wins with probability
${2^{-0.4\cdot\lambda^{C_{\mathsf{MoE.Coll}}}}}$. ∎

This completes the security proof, since the above is a contradiction to
Theorem 19.

##  7 Public-Key Functional Encryption with Copy-Protected Functional Keys

In this section, we formally define functional encryption with copy-protected
functional keys. Then, we give a construction based on coset states and prove
it secure.

We note that Kitagawa and Nishimaki [KN22] define a simpler model of
functional encryption with copy-protected functional keys and give a secure
construction in this model. In their model, the adversary can query for any
number of functional keys, but only one can be in copy-protected mode. In
turn, the adversary only outputs two freeloaders. Further, the freeloader
adversaries are not allowed to query for more keys after getting their
challenge ciphertexts.

###  7.1 Definitions

An informal overview of our security model is as follows. The piracy adversary
will be allowed to adaptively query for classical (i.e., not copy-protected)
and copy-protected functional keys. At the end of this first query phase, the
adversary will produce a pair of challenge messages $m^{0},m^{1}$ and $k+1$
registers (freeloaders) where $k$ is the number of copy-protected keys
obtained by it. After this split, the challenger presents them each with a
challenge ciphertext. Finally, after receiving the challenge ciphertexts,
freeloaders can query for more keys, and they output their guess at the end.

For the challenge message pair $m^{0},m^{1}$, we will require that the pirate
can obtain a _classical_ key for a function $f$ only if it satisfies
$f(m^{0})=f(m^{1})$. Similarly, the freeloader can obtain a key for $f$ only
under this condition. However, we will not require anything for functional
keys that were only obtained in copy-protected mode by the pirate adversary
before the split. Thus, our security guarantee will allow $k$ out of the $k+1$
freeloaders to possibly use these copy-protected functional keys to decrypt
their challenge ciphertexts. However, it should not be possible for all $k+1$
registers to use these copy-protected keys simultaneously.

We also define our model so that copy-protected functional keys are generated
given only a classical functional key. Therefore, we do not need to separately
require that a copy-protected key for $f$ allows no more than evaluation of
the encrypted message under $f$, which is already implied by the regular
functional encryption security.

######  Definition 22 (Public-key Functional Encryption with Copy-Protected
Secret Keys).

A public-key functional encryption scheme with copy-protected secret keys is a
public-key functional encryption scheme (Definition 3) with the following
additional algorithm and guarantee.

  * •

$\mathsf{QKeyGen}(fk)$: Takes as input a classical functional key, outputs a
quantum secret key.

##### Correctness

For all messages $m\in\mathcal{M}$,

$\Pr[\mathsf{Dec}(R_{\mathsf{dec}},ct)=f(m):\begin{array}[]{c}pk,msk\leftarrow\mathsf{Setup}(1^{\lambda})\\\
sk_{f}\leftarrow\mathsf{KeyGen}(msk,f)\\\
R_{f}\leftarrow\mathsf{QKeyGen}(sk_{f})\\\
ct\leftarrow\mathsf{Enc}(pk,m)\end{array}]=1.$

As discussed in Section 6, correctness of the scheme along with Lemma 1 means
that we can implement decryption in a way such that the quantum functional key
is not disturbed. Thus, we can reuse the key to decrypt any number of times.

Similar to public-key encryption, we give a CPA-style anti-piracy security
definition.

Let $\mathfrak{F}=\\{\mathfrak{F}_{\lambda}\\}_{\lambda}$ be a family of
functions. We define anti-piracy security for $\mathfrak{F}$ as follows.

######  Definition 23 (CPA-Style Regular Anti-Piracy Security for Functional
Encryption).

Consider the following game between the challenger and an adversary
$\mathcal{A}$.

##### $\underline{\mathsf{FEAntiPiracy}(\lambda,\mathcal{A})}$

  1. 1.

The challenger runs $msk,pk\leftarrow\mathsf{FE}.\mathsf{Setup}(1^{\lambda})$
and submits $pk$ to the adversary. It also initializes the set
$\mathcal{F}_{clas}=\emptyset$.

  2. 2.

Query Phase 1: For multiple rounds, the adversary adaptively submits a
function $f\in\mathfrak{F}$ and a query type, either $\mathsf{CLASSICAL}$ or
$\mathsf{PROTECTED}$. For each $f$, the challenger does the following. It
first computes $sk_{f}\leftarrow\mathsf{FE}.\mathsf{KeyGen}(msk,f)$.

Then, if the query type is $\mathsf{CLASSICAL}$, it adds $f$ to
$\mathcal{F}_{clas}$ and submits $sk_{f}$ to the adversary.

Otherwise, it computes $R_{f}\leftarrow\mathsf{FE}.\mathsf{QKeyGen}(sk_{f})$
and submits $R_{f}$ to the adversary.

  3. 3.

The adversary outputs a pair of challenge messages $m^{0},m^{1}$ and a
$(k+1)$-partite register $R_{\mathsf{adv}}$ (where $k$ is the number of
queries of the type $\mathsf{PROTECTED}$), each part of the register being an
interactive freeloader adversary that will be executed using a universal
circuit. The challenger checks if $f(m^{0})=f(m^{1})$ for all
$f\in\mathcal{F}_{clas}$. If not, it outputs $0$ and terminates.

  4. 4.

Challenge Phase: For each $\ell\in[k+1]$, the challenger samples
$b_{\ell}\leftarrow\\{0,1\\}$, then computes
$ct_{\ell}\leftarrow\mathsf{FE}.\mathsf{Enc}(pk,m^{b_{\ell}})$ and sends
$ct_{\ell}$ to the $\ell$-th freeloader.

  5. 5.

Query Phase 2: The challenger interacts with each of the $k+1$ freeloaders,
using a universal circuit, for multiple rounds as follows. The freeloader
$\ell\in[k+1]$ adaptively submits a function $f\in\mathfrak{F}$ and a query
type, either $\mathsf{CLASSICAL}$ or $\mathsf{PROTECTED}$. For each $f$, the
challenger does the following. It first computes
$sk_{f}\leftarrow\mathsf{FE}.\mathsf{KeyGen}(msk,f)$. Then, it adds $f$ to
$\mathcal{F}_{\ell}$.

If the query type is $\mathsf{CLASSICAL}$, the challenger submits $sk_{f}$ to
the adversary $\ell$. If the query type is $\mathsf{PROTECTED}$, the
challenger computes $R_{f}\leftarrow\mathsf{FE}.\mathsf{QKeyGen}(sk_{f})$ and
submits $R_{f}$ to the adversary.

  6. 6.

For $\ell\in[k+1]$, the challenger submits $ct_{\ell}$ to the $\ell$-th
freeloader to obtain a guess $b^{\prime}_{\ell}$. Then, it checks if
$b^{\prime}_{\ell}=b_{\ell}$ and if $f(m^{0})=f(m^{1})$ for all
$f\in\mathcal{F}_{\ell}$. It outputs $1$ if and only if all the check pass.

We say that a public key functional encryption scheme $\mathsf{FE}$ with copy-
protected secret keys satisfies $\gamma$-anti-piracy security if for any QPT
adversary $\mathcal{A}$,

$\Pr[\mathsf{FEAntiPiracy}(\lambda,\mathcal{A})=1]\leq\frac{1}{2}+\gamma(\lambda)+\mathsf{negl}(\lambda).$

We omit indicating $\gamma$ explicitly when $\gamma=0$.

We make some remarks about this definition. First, notice that if a
construction satisfies $\gamma$-anti-piracy for any inverse polynomial
$\gamma$, then it also satisfies it for $\gamma=0$, simply because of the
added $\mathsf{negl}(\lambda)$ term above. Second, note that
($\gamma=0-$)anti-piracy security trivially implies regular functional
encryption security: an adversary for the latter corresponds to an adversary
for the former that only makes queries of the type $\mathsf{CLASSICAL}$.

Finally, note that as opposed to our public-key encryption definition, the
piracy adversary is not allowed to choose different challenge message pairs
for each freeloader. Looking ahead, this is partially an artifact of our proof
technique. In our proof, we will need to remove Query Phase 2 from the game,
since our techniques are restricted to non-interactive freeloaders. To achieve
this without weakening our security model, we will instead define a scheme
where the freeloader adversaries receive a punctured key $pmsk$ that allows
them to obtain secret keys for functions $f$ that satisfy $f(m^{0})=f(m^{1})$.
If we allowed different challenge messages for each freeloader, then their
punctured keys would also be different. While they are not allowed to
communicate, this situation might possibly allow them to use these punctured
keys to decrypt their ciphertexts, since entanglement provides advantage over
classical strategies in non-local games (e.g CHSH game [CHSH69]). We leave it
as an open question to construct schemes where the freeloaders are allowed to
have different challenge message pairs.

###  7.2 Construction

In section, we give our construction of a functional encryption scheme with
copy-protected keys for the class of functions $\mathfrak{F}$ defined as all
circuits that are of size at most $Q(\lambda)$, where $Q(\lambda)$ is any
fixed polynomial. The construction is highly similar to our public-key
encryption construction. The main difference is that a functional key for a
function $f$ will consist of an $\mathsf{IBE}$ key for $id||f$ where $id$ is a
random string.

Assume the existence of following primitives where we set
$\nu(\lambda)=2^{-5\lambda-Q(\lambda)}\cdot
2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

  * •

$i\mathcal{O}$, indistinguishability obfuscation scheme that is
$\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$\mathsf{IBE}$, identity-based encryption scheme with puncturable master
secret keys (Definition 14) and deterministic $\mathsf{KeyGen}$ that satisfies
strong punctured key correctness (Definition 13), for the identity space
$\mathcal{ID}=\\{0,1\\}^{Q(\lambda)+\lambda}$ that is $\nu(\lambda)$-secure
against $2^{5\lambda}\cdot 2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time
adversaries,

  * •

$F_{1}$, puncturable PRF family with input length $Q(\lambda)+\lambda$ and
output length same as the size of the randomness used by $\mathsf{CosetGen}$
that is $\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$F_{2}$, puncturable PRF family with input length $Q(\lambda)+\lambda$ and
output length same as the size of the randomness used by $\mathsf{IBE.Enc}$
that is $\nu(\lambda)$-secure against $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries,

  * •

$\mathsf{CCObf}$, compute-and-compare obfuscation for
$2^{-\lambda^{0.2\cdot{C_{\mathsf{MoE.Coll}}}}}$-unpredictable distributions
that is $2^{-2\lambda-1}\cdot 2^{-2\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-secure
against $2^{3\lambda}\cdot 2^{2\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time
adversaries,

While we assume exponential security of the above primitives for specific
exponents, these assumptions can be based only on subexponential hardness for
some exponent, since we can always scale the security parameter by a
polynomial factor.

Also, set $L(\lambda)=Q(\lambda)+\lambda$ and hence
$c_{L}(\lambda)=3\cdot(Q(\lambda)+2\lambda)^{3}$.

We now give our construction. Below, assume that all programs that are
obfuscated are appropriately padded.

##### $\underline{\mathsf{FE.Setup}(1^{\lambda})}$

  1. 1.

Sample a PRF key $K_{1}\leftarrow F_{1}.\mathsf{KeyGen}(1^{\lambda})$.

  2. 2.

Sample $cpk,csmk\leftarrow\mathsf{IBE.Setup}(1^{\lambda})$.

  3. 3.

Sample $\mathsf{OPMem}\leftarrow i\mathcal{O}(\mathsf{PMem}_{K_{1}})$, where
$\mathsf{PMem}_{K_{1}}$ is the following program.

$\underline{\mathsf{PMem}_{K_{1}}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)}$
Hardcoded: $K_{1}$ 1.
$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}\leftarrow\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1},id||f))$.
2. For each $i\in[c_{L}(\lambda)]$, check if $u_{i}\in A_{i}+s_{i}$ if
$(r)_{i}=0$ and check if $u_{i}\in A^{\perp}_{i}+s^{\prime}_{i}$ if
$(r)_{i}=1$. If any of the checks fail, output $0$ and terminate. 3. Output
$1$.

  4. 4.

Set $pk=(cpk,\mathsf{OPMem})$, $msk=(cmsk,K_{1})$.

  5. 5.

Output $(pk,msk)$.

##### $\underline{\mathsf{FE.KeyGen}(msk,f)}$

  1. 1.

Parse $(cmsk,K_{1})=msk$.

  2. 2.

Sample $id\leftarrow\\{0,1\\}^{\lambda}$.

  3. 3.

Sample $ck\leftarrow\mathsf{IBE.KeyGen}(cmsk,id||f)$.

  4. 4.

$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}=\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1},id||f))$.

  5. 5.

Output $(ck,id,f,(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]})$.

##### $\underline{\mathsf{FE.QKeyGen}(fk)}$

  1. 1.

Parse $(ck,id,f,(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]})=fk$.

  2. 2.

Output
$\mathopen{}\mathclose{{}\left(\ket{A_{i,s_{i},s^{\prime}_{i}}}}\right)_{i\in[c_{L}(\lambda)]},ck,id,f$.

##### $\underline{\mathsf{FE.Enc}(pk,m)}$

  1. 1.

Parse $(cpk,\mathsf{OPMem})=pk$.

  2. 2.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

  3. 3.

Sample a PRF key $K_{2}$ for $F_{2}$ as $K_{2}\leftarrow
F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  4. 4.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}(\mathsf{PCt}_{\mathsf{OPMem},cpk,K_{2},r,m})$, where
$\mathsf{PCt}_{\mathsf{OPMem},cpk,K_{2},r,m}$ is the following program.
$\underline{\mathsf{PCt}_{\mathsf{OPMem},cpk,K_{2},r,m}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded: $\mathsf{OPMem},cpk,K_{2},r,m$ 1. Run
$\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. 2. Output
$\mathsf{IBE.Enc}(cpk,id||f,f(m);F_{2}(K_{2},id||f))$.

  5. 5.

Output $(\mathsf{OPCt},r)$.

##### $\underline{\mathsf{FE.Dec}(R_{\mathsf{key}},ct)}$

  1. 1.

Parse $((R_{i})_{i\in[c_{L}(\lambda)]},ck,id,f)=R_{\mathsf{key}}$ and
$(\mathsf{OPCt},r)=ct$.

  2. 2.

For indices $i\in[c_{L}(\lambda)]$ such that $(r)_{i}=1$, apply
$H^{\otimes\kappa(L(\lambda)+\lambda)}$ to $R_{i}$.

  3. 3.

Run the program $\mathsf{OPCt}$ coherently on $id,f$ and
$(R_{i})_{i\in[c_{L}(\lambda)]}$.

  4. 4.

Measure the output register and denote the outcome by $cct$.

  5. 5.

Output $\mathsf{IBE.Dec}(ck,cct)$.

Correctness with probability $1$ follows in a straightforward manner from the
correctness of the underlying schemes. We claim that the construction is also
secure.

######  Theorem 28.

$\mathsf{FE}$ satisfies $\gamma$-anti-piracy (Definition 23) for any inverse
polynomial $\gamma$.

When we instantiate the assumed primitives with known constructions, we get
the following corollary.

######  Corollary 5.

Assuming subexponentially secure $i\mathcal{O}$, one-way functions and LWE,
there exists a public-key functional encryption scheme that satisfies anti-
piracy security against unbounded collusion.

###  7.3 Proof of Anti-Piracy

Proof will closely follow the strong anti-piracy security proof for our
public-key encryption construction in Section 6.3, which crucially relies on
projective implementations to simultaneously extract vectors from all
registers to reduce to the monogamy-of-entanglement game. However, since the
freeloaders in the functional encryption security game are interactive as
opposed to the ones in regular public-key encryption, we cannot use projective
implementations directly. Therefore, we first make the post-challenge-
ciphertext steps non-interactive by providing the freeloaders with a punctured
master secret key $pmsk$ that lets them issue their own functional keys, as
long as $f(m^{0})=f(m^{1})$.

We give the following two definitions, specific to our construction
$\mathsf{FE}$. Recall that we also assume that $\mathsf{IBE.KeyGen}$ is
deterministic, which is true for the construction we give in Section 5.2.

######  Definition 24 (CPA-Style Post-Challenge-Ciphertext-Non-interactive
Anti-Piracy Security for $\mathsf{FE}$).

Consider the following game between the challenger and an adversary
$\mathcal{A}$.

##### $\underline{\mathsf{FEAntiPiracyNI}(\lambda,\mathcal{A})}$

  1. 1.

The challenger runs $msk,pk\leftarrow\mathsf{FE}.\mathsf{Setup}(1^{\lambda})$
and submits $pk$ to the adversary. It also initializes the set
$\mathcal{F}_{clas}$. It parses $(cmsk,K_{1})=msk$.

  2. 2.

Query Phase 1: For multiple rounds, the adversary adaptively submits a
function $f\in\mathfrak{F}$ and a query type, either $\mathsf{CLASSICAL}$ or
$\mathsf{PROTECTED}$. For each $f$, the challenger does the following. It
first computes $sk_{f}\leftarrow\mathsf{FE}.\mathsf{KeyGen}(msk,f)$.

Then, if the query type is $\mathsf{CLASSICAL}$, it adds $f$ to
$\mathcal{F}_{clas}$ and submits $sk_{f}$ to the adversary.

Otherwise, it computes $R_{f}\leftarrow\mathsf{FE}.\mathsf{QKeyGen}(sk_{f})$
and submits $R_{f}$ to the adversary.

  3. 3.

The adversary outputs a pair of challenge messages $m^{0},m^{1}$ and a
$(k+1)$-partite register $R_{\mathsf{adv}}$ (where $k$ is the number of
queries of the type $\mathsf{PROTECTED}$), each part of the register being a
freeloader adversary that will be executed using a universal circuit.

  4. 4.

The challenger checks if $f(m^{0})=f(m^{1})$ for all $f\in\mathcal{F}_{clas}$.
If not, it outputs $0$ and terminates.

Otherwise, the challenger computes $pmsk\leftarrow
i\mathcal{O}(\mathsf{PKey}_{cmsk,K_{1}})$.

$\underline{\mathsf{PKey}_{cmsk,K_{1}}(id||f)}$ Hardcoded:
$cmsk,K_{1},m^{0},m^{1}$ 1. Check if $f(m^{0})=f(m^{1})$. If not, output
$\perp$ and terminate. 2. Compute $ck=\mathsf{IBE.KeyGen}(cmsk,id||f)$. 3.
$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}=\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1},id||f))$.
4. Output $(ck,id,f,(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]})$.

  5. 5.

For $\ell\in[k+1]$, the challenger submits $ct_{\ell},pmsk$ to the $\ell$-th
freeloader to obtain a guess $b^{\prime}_{\ell}$. Then, it checks if
$b^{\prime}_{\ell}=b_{\ell}$ and if $f(m^{0})=f(m^{1})$ for all
$f\in\mathcal{F}_{\ell}$. It outputs $1$ if and only if all the check pass.

We say $\mathsf{FE}$ satisfies post-challenge-ciphertext non-interactive
$\gamma$-anti-piracy security if for any QPT adversary,

$\Pr[\mathsf{FEAntiPiracyNI}(\lambda,\gamma(\lambda),\mathcal{A})=1]\leq\frac{1}{2}+\gamma(\lambda)+\mathsf{negl}(\lambda).$

######  Definition 25 (Functional Encryption Decryptor Testing).

In the anti-piracy game between the challenger and an adversary, fix
$\ell\in[k+1]$, some values $m^{0},m^{1}$ of the challenge messages and some
value $st$ of a classical state of the challenger (which will be defined
later). Let $\mathcal{D}$ be an efficient ciphertext and punctured master
secret key distribution that can depend on $st$. That is,
$\mathcal{D}^{st}(m;r)$ is an efficient classical algorithm where
$m\in\mathcal{M}$, $r\in\mathcal{R}$ and $\mathcal{R}$ is a random coin set.

Consider the following mixture of binary _projective measurements_
$\mathcal{P}$, induced by $\mathcal{D}$ and $m^{0},m^{1},st$, applied on a
state $\rho$.

  1. 1.

Sample $b\leftarrow\\{0,1\\}$.

  2. 2.

Sample $r\leftarrow\mathcal{R}$.

  3. 3.

Run $ct,pmsk\leftarrow\mathcal{D}^{st}(m^{b};r)$.

  4. 4.

Run the universal circuit $\mathsf{U}_{quantum}$ on $(\rho,pmsk,ct)$, let
$b^{\prime}$ be the output.

  5. 5.

Output 1 if $b^{\prime}=b$. Otherwise, output $0$.

Observe that we can efficiently execute the above measurement for arbitrary
given superpositions of $r$ and $b$ values. Therefore, by Section 3.7, there
exists exact and efficient approximated projective and threshold
implementations for $\mathcal{P}$. We write $\mathsf{PI}_{\ell,\mathcal{D}}$
and $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}}$ to denote the
projective implementation and approximate projective implementation of
$\mathcal{P}$, respectively. Similarly, let
$\mathsf{TI}_{\ell,\mathcal{D},\eta}$ and
$\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},\eta}$ denote the
threshold and efficient approximate threshold implementations of $\mathcal{P}$
for a threshold value $\eta$.

The fixed values $m^{0},m^{1},st$, omitted in the notation, will be clear from
the context. Unless otherwise specified, we will write $\mathcal{D}$ to denote
the distribution where the ciphertext is sampled as

$ct\leftarrow\mathsf{FE}.\mathsf{Enc}(pk,m)$

and $pmsk$ is sampled as in Definition 24, where $pk$ is part of $st$.

######  Definition 26 (CPA-Style Strong Anti-Piracy Security for
$\mathsf{FE}$).

Consider the following game between the challenger and an adversary
$\mathcal{A}$.

##### $\underline{\mathsf{FEStrongAntiPiracy}(\lambda,\gamma,\mathcal{A})}$

  1. 1.

The challenger runs $msk,pk\leftarrow\mathsf{FE}.\mathsf{Setup}(1^{\lambda})$
and submits $pk$ to the adversary. It also initializes the set
$\mathcal{F}_{clas}$. It parses $(cmsk,K_{1})=msk$.

  2. 2.

Query Phase 1: For multiple rounds, the adversary adaptively submits a
function $f\in\mathfrak{F}$ and a query type, either $\mathsf{CLASSICAL}$ or
$\mathsf{PROTECTED}$. For each $f$, the challenger does the following. It
first computes $sk_{f}\leftarrow\mathsf{FE}.\mathsf{KeyGen}(msk,f)$.

Then, if the query type is $\mathsf{CLASSICAL}$, it adds $f$ to
$\mathcal{F}_{clas}$ and submits $sk_{f}$ to the adversary.

Otherwise, it computes $R_{f}\leftarrow\mathsf{FE}.\mathsf{QKeyGen}(sk_{f})$
and submits $R_{f}$ to the adversary.

  3. 3.

The adversary outputs a pair of challenge messages $m^{0},m^{1}$ and a
$(k+1)$-partite register $R_{\mathsf{adv}}$ (where $k$ is the number of
queries of the type $\mathsf{PROTECTED}$), each part of the register being a
freeloader adversary that will be executed using a universal circuit.

  4. 4.

The challenger checks if $f(m^{0})=f(m^{1})$ for all $f\in\mathcal{F}_{clas}$.
If not, it outputs $0$ and terminates.

  5. 5.

The challenger applies the test

$\bigotimes_{\ell\in[k+1]}\mathsf{TI}_{\ell,\mathcal{D},1/2+\gamma}$

to $R$ and outputs $1$ if and only if all the measurement results are $1$.

We say $\mathsf{FE}$ satisfies strong $\gamma$-anti-piracy security if for any
QPT adversary,

$\Pr[\mathsf{FEStrongAntiPiracy}(\lambda,\gamma(\lambda),\mathcal{A})=1]\leq\mathsf{negl}(\lambda).$

We first prove that the stronger definition implies the regular anti-piracy
security (Definition 23).

######  Theorem 29.

Suppose $\mathsf{FE}$ satisfies strong $\gamma$-anti-piracy security. Then, it
also satisfies regular $\gamma$-anti-piracy security.

###### Proof.

We first show that strong $\gamma$-anti-piracy security implies post-
challenge-ciphertext non-interactive $\gamma$-anti-piracy security, by
generalizing an argument made by [CLLZ21] for public-key encryption.

As discussed before, there exists a projective implementation for each
decryption test the challenger performs above for each register, where instead
of applying the universal circuit and comparing the output to
$b^{\prime}_{\ell}$, if we apply the projective implementation to obtain a
value $p_{\ell}$ and output a bit $a_{\ell}=1$ with probability $p_{\ell}$, we
get the correct output distribution for all registers simultaneously151515Note
that the joint distribution is still correct since the projective
implementations are correct for any input state, and hence we can consider the
post-measurement state of any register conditioned on measurement outcomes of
the other registers, and the projective implementation will still have the
correct output distribution.. Hence, we can equivalently execute the security
game $\mathsf{FEAntiPiracyNI}$ by applying these projective implementations,
obtaining some $a_{\ell}$, and outputting $1$ if and only if $a_{\ell}=1$ for
all $\ell\in[k+1]$.

Now, note that by construction of $\mathsf{TI}$ and by the assumption that
$\mathsf{FE}$ satisfies strong $\gamma$-anti-piracy security, we have

$\Pr[\forall\ell\in[k+1]~{}~{}p_{\ell}\geq\frac{1}{2}+\gamma(\lambda)]\leq\mathsf{negl}(\lambda).$

Then, by above,

$\displaystyle\Pr[\mathsf{FEAntiPiracyNI}(\lambda,\mathcal{A})=1]=$
$\displaystyle\mathds{E}[p_{1}\cdots p_{\ell}]$ $\displaystyle=$
$\displaystyle\Pr[\forall\ell\in[k+1]~{}~{}p_{\ell}\geq\frac{1}{2}+\gamma(\lambda)]\cdot\mathds{E}[p_{1}\cdots
p_{\ell}|\forall\ell\in[k+1]~{}~{}p_{\ell}\geq\frac{1}{2}+\gamma(\lambda)]+$
$\displaystyle\Pr[\exists\ell\in[k+1]~{}~{}p_{\ell}<\frac{1}{2}+\gamma(\lambda)]\cdot\mathds{E}[p_{1}\cdots
p_{\ell}|\exists\ell\in[k+1]~{}~{}p_{\ell}<\frac{1}{2}+\gamma(\lambda)]$
$\displaystyle\leq$ $\displaystyle\mathsf{negl}(\lambda)\cdot
1+1\cdot(\frac{1}{2}+\gamma(\lambda)).$

This completes the proof that strong $\gamma$-anti-piracy security implies
post-challenge-ciphertext non-interactive $\gamma$-anti-piracy security.

Now, we show that the latter implies regular $\gamma$-anti-piracy security. A
freeloader adversary $\mathcal{B}^{\prime}$ for $\mathsf{FEAntiPiracyNI}$ can
simulate a freeloader adversary $\mathcal{B}$ for the regular $\gamma$-anti-
piracy as follows. Whenever $\mathcal{B}$ makes a query for a function $f$ in
Query Phase 2, $\mathcal{B}^{\prime}$ samples a random identity $id$ and
evaluates $pmsk$ on $id,f$. Since $f$ satisfies $f(m^{0})=f(m^{1})$, by
correctness of $i\mathcal{O}$, it will be able to obtain the correct key. If
query is of type $\mathsf{CLASSICAL}$, then $\mathcal{B}^{\prime}$ submits the
obtained classical key $fk$ to $\mathcal{B}$. Otherwise, it runs
$\mathsf{FE.QKeyGen}$ on $fk$ and then submits the resulting quantum key. This
perfectly simulates the regular anti-piracy game, hence post-challenge-
ciphertext non-interactive $\gamma$-anti-piracy security implies regular anti-
piracy security. ∎

#### Reducing to Monogamy-of-Entanglement

######  Lemma 11.

$\mathsf{FE}$ satisfies strong $\gamma$-anti-piracy security for any inverse
polynomial $\gamma$.

Proof of this lemma is almost identical to the proof of security of our
public-key encryption scheme. Therefore, we will omit the proofs of some
claims.

Throughout the proof, we will interpret identity strings for $\mathsf{IBE}$,
which are $Q(\lambda)+\lambda$-bit strings, as integers in the set
$\\{0,1,\dots,2^{Q(\lambda)+\lambda}\\}$.

Fix any inverse polynomial $\gamma(\lambda)$ and suppose for a contradiction
that there exists an efficient adversary $\mathcal{A}$ that wins the strong
$\gamma$-anti-piracy game with non-negligible probability. Let $k$ denote the
number of keys obtained by the adversary. Define $\mathsf{Hyb}_{0}$ to be the
original security game
$\mathsf{FEStrongAntiPiracy}(\lambda,\gamma(\lambda),\mathcal{A})$.

Define $\mathsf{Hyb}_{1}$ by modifying $\mathsf{Hyb}_{0}$ as follows. When
generating functional keys, we sample the identity strings in a collusion-free
way. Further, at the end of the game, the challenger instead applies the test
$\bigotimes_{\ell\in[k+1]}\mathsf{ATI}^{\varepsilon,\delta}_{\ell,\mathcal{D},1/2+\frac{31\gamma}{32}}$
instead of $\mathsf{TI}$ where we set $\varepsilon=\frac{\gamma}{32k}$ and
$\delta=2^{-10\lambda}\cdot 2^{-10\lambda^{C_{\mathsf{MoE.Coll}}}}$.

######  Claim 17.

$\Pr[\mathsf{Hyb}_{2}=1]>1/p(\lambda)$ for some polynomial $p(\cdot)$ and
infinitely many values of $\lambda>0$

###### Proof.

Follows from the same argument as in Section 6.3. ∎

######  Notation.

For all $j\in[k]$, let $id_{j}||f_{j}$ denote the identity string and let
$(A_{i}^{j},s_{i}^{j},s_{i}^{{}^{\prime}j})_{{i\in[c_{L}(\lambda)]}}$ denote
the tuple of cosets sampled during the sampling of the functional key for the
$(\alpha^{-1}(j))$-th query of type $\mathsf{PROTECTED}$. That is, it is the
coset tuple associated with $id_{j}||f_{j}$.

We now define a monogamy-of-entanglement type game $\mathcal{G}$, similar to
the game defined in the PKE proof.

#####
$\underline{\mathcal{G}(\lambda,(\mathcal{A}^{\prime}_{0},\mathcal{A}^{\prime}_{1},\mathcal{A}^{\prime}_{2}))}$

  1. 1.

The challenger runs $msk,pk\leftarrow\mathsf{FE}.\mathsf{Setup}(1^{\lambda})$
and submits $pk$ to the adversary. It also initializes the set
$\mathcal{F}_{clas}$. It parses $(cmsk,K_{1})=msk$.

  2. 2.

Query Phase 1: For multiple rounds, the adversary adaptively submits a
function $f\in\mathfrak{F}$ and a query type, either $\mathsf{CLASSICAL}$ or
$\mathsf{PROTECTED}$. For each $f$, the challenger does the following. It
first computes $sk_{f}\leftarrow\mathsf{FE}.\mathsf{KeyGen}(msk,f)$.

Then, if the query type is $\mathsf{CLASSICAL}$, it adds $f$ to
$\mathcal{F}_{clas}$ and submits $sk_{f}$ to the adversary.

Otherwise, it computes $R_{f}\leftarrow\mathsf{FE}.\mathsf{QKeyGen}(sk_{f})$
and submits $R_{f}$ to the adversary.

  3. 3.

The adversary outputs a pair of challenge messages $m^{0},m^{1}$ and an index
$j^{*}\in[k]$ where $k$ is the number of queries it made of type
$\mathsf{PROTECTED}$.

  4. 4.

The challenger checks if $f(m^{0})=f(m^{1})$ for all $f\in\mathcal{F}_{clas}$.
If not, it outputs $0$ and terminates.

Otherwise, the challenger computes $K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}\leftarrow
F_{1}.\mathsf{Punc}(K_{1},id_{j^{*}}||f_{j^{*}})$ and submits it to the
adversary.

  5. 5.

The challenger outputs a _bipartite_ register $R_{\mathsf{bip}}$.

  6. 6.

For $\ell\in\\{1,2\\}$, the challenger does the following.

    1. 6.1.

Sample $r_{\ell}\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 6.2.

Run $\mathcal{A}^{\prime}_{\ell}$ on $R_{\mathsf{bip}}[\ell]$,
$(A^{j^{*}}_{i})_{i\in[c_{L}(\lambda)]}$ and $r_{\ell}$ to obtain a tuple of
vectors $(v_{\ell,i})_{i\in[{c_{L}(\lambda)}]}$.

    3. 6.3.

For all $i\in[c_{L}(\lambda)]$, check if $v_{\ell,i}\in
A^{j^{*}}_{i}+s^{j^{*}}_{i}$ if $(r_{\ell})_{i}=0$ and check if
$v_{\ell,i}\in{(A^{j^{*}})}^{\perp}_{i}+s^{{}^{\prime}{j^{*}}}_{i}$ if
$(r_{\ell})_{i}=1$.

If all the checks pass, the challenger outputs $1$. Otherwise, it outputs $0$.

It is straightforward to reduce this game to the collusion-resistant MoE game.
We construct our adversary for $\mathcal{G}$ as follows, where we will define
challenge ciphertext-punctured master secret key distributions
$\mathcal{D}_{j}$ later. Without loss of generality161616In the general case,
the adversary would simply sample $j^{*}$ from $[k^{\prime}]$ where
$k^{\prime}$ is the number of queries made by the adversary $\mathcal{A}$ of
type $\mathsf{PROTECTED}$ that do satisfy $f(m_{0})\neq f(m_{1})$., we will
assume that all queries made by the adversary $\mathcal{A}$ of type
$\mathsf{PROTECTED}$ satisfy $f(m_{0})\neq f(m_{1})$.
$\underline{\mathcal{A}_{0}^{\prime}(pk)}$ 1. Simulate $\mathcal{A}$ on $pk$
by making a functional key query to the challenger whenever $\mathcal{A}$
makes a query, and forwarding the obtained key to it. Let $R_{\mathsf{adv}}$
be the $(k+1)$-partite register (with state $\sigma$) and $(m^{0},m^{1})$ be
the challenge messages output by $\mathcal{A}$ at the end of the query phase.
2. Uniformly at random sample $x,y,j^{*}$ such that $1\leq x<y\leq k+1$ and
$j^{*}\in\\{1,\dots,k\\}$. 3. Output $j^{*}$ to the challenger and obtain
$K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}$. 4. Apply
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{0}}$ to all registers
$R_{\mathsf{adv}}[\ell]$ for $\ell\in[k+1]$, let $b_{\ell,0}$ be the
measurement outcomes. 5. Apply
$\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$ in succession for
$i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[x]$, let $b_{x,i}$ be the measurement
outcomes. 6. Apply $\mathsf{API}^{\varepsilon,\delta}_{\ell,\mathcal{D}_{i}}$
in succession for $i=1$ to $j^{*}$ to $R_{\mathsf{adv}}[y]$, let $b_{y,i}$ be
the measurement outcomes. 7. Output $\displaystyle($
$\displaystyle(R_{\mathsf{adv}}[x],j^{*},x,y,(b_{\ell,0})_{\ell\in[k+1]},(b_{x,i})_{i\in[j^{*}]},(b_{y,i})_{i\in[j^{*}]}),$
$\displaystyle(R_{\mathsf{adv}}[y],j^{*},x,y,(b_{\ell,0})_{\ell\in[k+1]},(b_{x,i})_{i\in[j^{*}]},(b_{y,i})_{i\in[j^{*}]},),$
$\displaystyle j^{*}).$ For $j\in\\{1,\dots,k\\}$, define $\mathcal{D}_{j}$ to
be the following challenge ciphertext-punctured master secret key
distribution.

  1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

  2. 2.

Sample a PRF key $K_{2}$ for $F_{2}$ as $K_{2}\leftarrow
F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  3. 3.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\color[rgb]{1,0,0}\mathsf{PCt}^{(j)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}||f_{j}}})$
$\underline{\mathsf{PCt}^{(j)}_{\mathsf{OPMem},cpk,K_{2},r,m^{b},m_{1-b},id_{j}||f_{j}}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
$\mathsf{OPMem},cpk,K_{2},r,m^{b},m^{1-b},{\color[rgb]{1,0,0}id_{j}||f_{j}}$
1. Run $\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs
$0$, output $\perp$ and terminate. 2. If $id||f<id_{j}||f_{j}$, set
$a=f(m^{1-b})$. Otherwise, set $a=f(m^{b})$. 3. Output
$\mathsf{IBE.Enc}(cpk,id,{\color[rgb]{1,0,0}a};F_{2}(K_{2},id))$.

  4. 4.

Sample $pmsk\leftarrow
i\mathcal{O}(\mathsf{PKey}_{cmsk,K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}})$.

$\underline{\mathsf{PKey}_{cmsk,K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}}(id||f)}$
Hardcoded: $cmsk,K_{1}\\{id_{j^{*}}||f_{j^{*}}\\},m^{0},m^{1}$ 1. Check if
$f(m^{0})=f(m^{1})$. If not, output $\perp$ and terminate. 2. Compute
$ck=\mathsf{IBE.KeyGen}(cmsk,id||f)$. 3.
$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}=\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1}\\{id_{j^{*}}||f_{j^{*}}\\},id||f))$.
4. Output $(ck,id,f,(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]})$.

  5. 5.

Output $(\mathsf{OPCt},r),pmsk$.

We define $\mathcal{D}_{0}$ to be the distribution where ciphertext is
computed honestly and $pmsk$ is computed as in Definition 24. We define
$\mathcal{D}_{k+1}$ as follows.

  1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

  2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

  3. 3.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\color[rgb]{1,0,0}\mathsf{PCt}^{(k+1)}_{\mathsf{OPMem},cpk,K_{2},r}})$
$\underline{\mathsf{PCt}^{(k+1)}_{\mathsf{OPMem},cpk,K_{2},r,m^{0},m^{1},b}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded: $\mathsf{OPMem},cpk,K_{2},r,m^{1-b}$ 1. Run
$\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. 2. Output
$\mathsf{IBE.Enc}(cpk,id,{\color[rgb]{1,0,0}f(m^{1-b})};F_{2}(K_{2},id))$.

  4. 4.

Sample $pmsk$ as in $\mathcal{D}_{j}$.

  5. 5.

Output $(\mathsf{OPCt},r),pmsk$.

######  Notation.

Let ${\mathsf{Exp}}_{{\mathcal{C}},{\ell}}$ denote the outcome of the
following experiment where $\mathcal{C}$ is a challenge ciphertext-punctured
master secret key distribution that can depend on $pp$.

  1. 1.

Execute $pk,sk\leftarrow\mathsf{PKE.Setup}(1^{\lambda})$.

  2. 2.

Simulate the first steps of $\mathcal{A}^{\prime}_{0}$ and the challenger of
$\mathcal{G}$:

    1. 2.1.

Simulate $\mathcal{A}$ on $pk$ by making a functional key query to the
challenger whenever $\mathcal{A}$ makes a query, and forwarding the obtained
key to it. Let $R_{\mathsf{adv}}$ be the $(k+1)$-partite register (with state
$\sigma$) and $(m^{0},m^{1})$ be the challenge messages output by
$\mathcal{A}$ at the end of the query phase.

    2. 2.2.

Uniformly at random sample $x,y,j^{*}$ such that $1\leq x<y\leq k+1$ and
$j^{*}\in\\{1,\dots,k\\}$.

    3. 2.3.

Compute $K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}\leftarrow
F_{1}.\mathsf{Punc}(K_{1},id_{j^{*}}||f_{j^{*}})$.

  3. 3.

Set $pp=(x,y,j^{*},(id_{j}||f_{j})_{j\in[k+1]},m_{0},m_{1},pk)$.

  4. 4.

Sample $b\leftarrow\\{0,1\\}$.

  5. 5.

Sample $ct,pmsk\leftarrow\mathcal{C}(pp,m^{b})$.

  6. 6.

Output $R_{\mathsf{adv}},(b,ct,pmsk),pp$.

We will write
${\mathsf{Exp}}_{{\mathcal{C}},{\ell}}\approx_{\nu}^{c}{\mathsf{Exp}}_{{\mathcal{C}^{\prime}},{\ell}}$
to denote that the advantage of any computational adversary in distinguishing
the outcomes of these experiments is $\nu$.

######  Claim 18.

Let $\tau$ be the state of the bipartite register $R_{\mathsf{adv}}[x,y]$
output by $\mathcal{A}^{\prime}_{0}$ in $\mathcal{G}$, and also consider the
classical values $j^{*},x,y,\\{b_{\ell,i}\\}_{\ell,i}$ contained in the output
of $\mathcal{A}^{\prime}_{0}$.

Suppose we apply the measurement
$\mathsf{API}^{\varepsilon,\delta}_{x,\mathcal{D}_{j^{*}+1}}\otimes\mathsf{API}^{\varepsilon,\delta}_{y,\mathcal{D}_{j^{*}+1}}$
to $\tau$ and let $b_{x,j^{*}+1},b_{y,j^{*}+1}$ denote the measurement
outcomes we obtain. Then,

$\Pr[b_{x,j^{*}}-b_{x,j^{*}+1}>\frac{29\gamma}{32k}\wedge
b_{y,j^{*}}-b_{y,j^{*}+1}>\frac{29\gamma}{32k}]>\frac{1}{4p(\lambda)\cdot
k^{3}(\lambda)}$

where the probability is taken over the randomness of the challenger, the
adversary $\mathcal{A}_{0}^{\prime}$ and the measurement outcomes.

###### Proof.

Follows from the same argument as 5. Only caveat is that we need to prove that
the success probability of the freeloaders with respect to the challenge
ciphertext distribution $\mathcal{D}_{k+1}$ is $\leq 1/2$. However, this is
indeed true, since $\mathcal{D}_{k+1}$ is encoding $m^{1-b}$ while the
challenge bit is $b$. ∎

######  Notation.

When we refer to $(id||f+\Delta)$ as a function, we will mean the function
$f^{\prime}$ which the function whose description is the last $Q(\lambda)$
bits of $(id||f+\Delta)$.

Now, we define some intermediary distributions. Define the following for all
$j\in\\{0,1,\dots,k\\}$ and
$\Delta\in\\{0,1,\dots,id_{j+1}||f_{j+1}-id_{j}||f_{j}-1\\}$. For notational
convenience, also define $\mathcal{D}_{j}^{id_{j+1}||f_{j+1}-id_{j}||f_{j},0}$
to be $\mathcal{D}_{j+1}^{(0,0)}$ for all $j\in\\{0,1,\dots,k\\}$. Also note
that $\mathcal{D}_{j}^{(0,0)}$ is exactly the same as $\mathcal{D}_{j}$ for
$j\in[k]$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,0)}}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,0)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}+\Delta}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,0)}_{\mathsf{OPMem},cpk,K_{2},r,m^{b},m^{1-b},id_{j}||f_{j}+\Delta}}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,K_{2},r,m^{b},m^{1-b},{\color[rgb]{1,0,0}id_{j}||f_{j}+\Delta}}$
(a) Run $\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it
outputs $0$, output $\perp$ and terminate. (b) If
$id||f<id_{j}||f_{j}+\Delta$, set $a=f(m^{1-b})$. Otherwise, set $a=f(m^{b})$.
(c) Output $\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    4. 4.

Sample $pmsk$ as in $\mathcal{D}_{j}$.

    5. 5.

Output $(\mathsf{OPCt},r),pmsk$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,1)}}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});F_{2}(K_{2},id_{j}||f_{j}+\Delta)).$

    4. 4.

$K_{2}\\{id_{j}||f_{j}+\Delta\\}\leftarrow
F_{2}.\mathsf{Punc}(K_{2},id_{j}||f_{j}+\Delta)$.

    5. 5.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,1)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,1)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,{\color[rgb]{1,0,0}K_{2}\\{id_{j}||f_{j}+\Delta\\}},r,m^{b},m^{1-b},id_{j}||f_{j}+\Delta,{\color[rgb]{1,0,0}ct^{*}}}$
(a) Run $\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it
outputs $0$, output $\perp$ and terminate. (b) If
$id||f=id_{j}||f_{j}+\Delta$, output $ct^{*}$ and terminate. (c) If
$id<id_{j}||f_{j}+\Delta+1$, set $a=f(m^{1-b})$. Otherwise, set $a=f(m)$. (d)
Output $\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    6. 6.

Sample $pmsk$ as in $\mathcal{D}_{j}$.

    7. 7.

Output $(\mathsf{OPCt},r),pmsk$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,2)}}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

Sample $z^{*}$ uniformly at random from the output space of $F_{2}$.

    4. 4.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});z^{*}).$

    5. 5.

$K_{2}\\{id_{j}||f_{j}+\Delta\\}\leftarrow
F_{2}.\mathsf{Punc}(K_{2},id_{j}||f_{j}+\Delta)$.

    6. 6.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,2)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,2)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}||f_{j}+\Delta\\},r,m^{b},m^{1-b},id_{j}||f_{j}+\Delta,ct^{*}}}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,{K_{2}\\{id_{j}+\Delta\\}},r,m^{b},m^{1-b},id_{j}||f_{j}+\Delta,{ct^{*}}}$
(a) Run $\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it
outputs $0$, output $\perp$ and terminate. (b) If
$id||f=id_{j}||f_{j}+\Delta$, output $ct^{*}$ and terminate. (c) If
$id<id_{j}||f_{j}+\Delta+1$, set $a=f(m^{1-b})$. Otherwise, set $a=f(m)$. (d)
Output $\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    7. 7.

Sample $pmsk$ as in $\mathcal{D}_{j}$.

    8. 8.

Output $(\mathsf{OPCt},r),pmsk$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,3)}}$:

    1. 1.

Sample $r\leftarrow\\{0,1\\}^{c_{L}(\lambda)}$.

    2. 2.

Sample a PRF key $K_{2}$ for $F_{2}.\mathsf{KeyGen}(1^{\lambda})$.

    3. 3.

Sample $z^{*}$ uniformly at random from the output space of $F_{2}$.

    4. 4.

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});z^{*}).$

    5. 5.

$K_{2}\\{id_{j}||f_{j}+\Delta\\}\leftarrow
F_{2}.\mathsf{Punc}(K_{2},id_{j}||f_{j}+\Delta)$.

    6. 6.

Compute
$(A^{*}_{i},s_{i}^{*},s_{i}^{{}^{\prime}{*}})=F_{1}(K_{1},id_{j}||f_{j}+\Delta).$

    7. 7.

For $i\in[c_{L}(\lambda)]$, set $g_{i}=\mathsf{Can}_{A^{*}_{i}}$ if
$(r)_{i}=0$ and set $g_{i}=\mathsf{Can}_{(A^{*}_{i})^{\perp}}$ if $(r)_{i}=1$.

    8. 8.

For $i\in[c_{L}(\lambda)]$, compute $y_{i}=g_{i}(s_{i}^{*})$ if $(r)_{i}=0$
and $y_{i}=g_{i}(s_{i}^{{}^{\prime}{*}})$ if $(r)_{i}=1$.

    9. 9.

Set $g$ to be the function
$g(v_{1},\dots,v_{c_{L}(\lambda)})=(g_{1}(v_{1})||\dots||g_{c_{L}(\lambda)}(v_{c_{L}(\lambda)}))$.

    10. 10.

Set $y=y_{1}||\dots||y_{c_{L}(\lambda)}$.

    11. 11.

$\mathsf{OCC}\leftarrow\mathsf{CCObf.Obf}(g,y,ct^{*})$.

    12. 12.

Sample $\mathsf{OPCt}\leftarrow
i\mathcal{O}({\mathsf{PCt}^{(j,\Delta,3)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}\\},r,m,id_{j}+\Delta,\mathsf{OCC}}}).$
$\underline{{\mathsf{PCt}^{(j,\Delta,3)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}||f_{j}+\Delta,\mathsf{OCC}}}(id||f,u_{1},\dots,u_{c_{L}(\lambda)})}$
Hardcoded:
${\mathsf{OPMem},cpk,{K_{2}\\{id_{j}+\Delta\\}},r,m^{b},m^{1-b},id_{j}||f_{j}+\Delta,{\color[rgb]{1,0,0}\mathsf{OCC}}}$
(a) If $id||f=id_{j}||f_{j}+\Delta$, output the output of
$\mathsf{OCC}(u_{1},\dots,u_{c_{L}(\lambda)})$ and terminate. (b) Run
$\mathsf{OPMem}(id||f,u_{1},\dots,u_{c_{L}(\lambda)},r)$. If it outputs $0$,
output $\perp$ and terminate. (c) If $id<id_{j}||f_{j}+\Delta+1$, set
$a=f(m^{1-b})$. Otherwise, set $a=f(m)$. (d) Output
$\mathsf{IBE.Enc}(cpk,id,{a};F_{2}(K_{2},id))$.

    13. 13.

Sample $pmsk$ as in $\mathcal{D}_{j}$.

    14. 14.

Output $(\mathsf{OPCt},r),pmsk$.

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,4)}}$: Same as
$\mathcal{D}_{j}^{(\Delta,3)}$ except for the following. Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});z^{*})$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,{\color[rgb]{1,0,0}(id_{j}||f_{j}+\Delta)(m^{1-b})};z^{*}).$

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,5)}}$: Same as
$\mathcal{D}_{j}^{(\Delta,2)}$ except for the following. Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});z^{*})$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,{\color[rgb]{1,0,0}(id_{j}||f_{j}+\Delta)(m^{1-b})};z^{*}).$

  * •

$\underline{\mathcal{D}_{j}^{(\Delta,6)}}:$ Same as
${\mathcal{D}_{j}^{(\Delta,1)}}$ except for the following. Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});F_{2}(K_{2},id_{j}||f_{j}+\Delta))$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,{\color[rgb]{1,0,0}(id_{j}||f_{j}+\Delta)(m^{1-b})};F_{2}(K_{2},id_{j}||f_{j}+\Delta)).$

Now, we show that these distributions _collapse_ around $\Delta=0$ for each
$j$. Below, all our indistinguishability claims are for $2^{5\lambda}\cdot
2^{8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$-time adversaries and we set
$\nu(\lambda)=2^{-5\lambda-Q(\lambda)}\cdot
2^{-8\lambda^{0.3C_{\mathsf{MoE.Coll}}}}$.

######  Claim 19.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,0)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,1)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Observe that by punctured key correctness of $F_{2}$ (Definition 1), the
different obfuscated programs
${\mathsf{PCt}^{(j,\Delta,0)}_{\mathsf{OPMem},cpk,K_{2},r,m,id_{j}+\Delta}}$
and
${\mathsf{PCt}^{(j,\Delta,1)}_{\mathsf{OPMem},cpk,K_{2}\\{id_{j}+\Delta\\},r,m,id_{j}+\Delta,ct^{*}}}$
in these hybrids have the same functionality. The result follows by security
of $i\mathcal{O}$ and by our choice of parameters. ∎

######  Claim 20.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,1)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,2)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

The result follows by selective puncturing security of $F_{2}$ (Definition 1)
and our choice of parameters. ∎

######  Claim 21.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,2)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Observe that the obfuscated ciphertext programs $\mathsf{PCt}$ in these
hybrids have the same functionality by correctness of $\mathsf{CCObf}$, since
a vector $w$ is in $A_{i}^{*}+s_{i}^{*}$ if and only if
$\mathsf{Can}_{A_{i}^{*}}(w)=\mathsf{Can}_{A_{i}^{*}}(s_{i}^{*})$ and
similarly for $(A^{*})_{i}^{\perp}+s^{{}^{\prime}*}_{i}$. Then, the claim
follows by the security of $i\mathcal{O}$. ∎

######  Claim 22.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4)}}},{\ell}}$
if

  * •

$j\in\\{1,\dots,k\\}$ and $\Delta\in\\{1,\dots,id_{j+1}-id_{j}-1\\}$, or

  * •

$j=0$ and $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$

and for all $\ell\in[k+1]$.

###### Proof.

We have two cases. First, assume that
$(id_{j}||f_{j}+\Delta)(m_{0})=(id_{j}||f_{j}+\Delta)(m_{1})$. Then, the
result easily follows.

Otherwise, define the intermediary distributions
$\mathcal{D}_{j}^{(\Delta,3^{\prime})},\mathcal{D}_{j}^{(\Delta,4^{\prime})}$
as follows.

#####  $\underline{\mathcal{D}_{j}^{(\Delta,3^{\prime})}}$

  1. 1.

Sample $(\mathsf{OPCt},r)$ as in $\mathcal{D}_{j}^{(\Delta,3)}$.

  2. 2.

Sample $cmsk^{\prime}\leftarrow\mathsf{IBE.Punc}(cmsk,id_{j}||f_{j}+\Delta)$.

  3. 3.

Sample $pmsk\leftarrow
i\mathcal{O}(\mathsf{PKey}_{cmsk^{\prime},K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}})$.

$\underline{\mathsf{PKey}_{cmsk^{\prime},K_{1}\\{id_{j^{*}}||f_{j^{*}}\\}}(id||f)}$
Hardcoded: $cmsk^{\prime},K_{1}\\{id_{j^{*}}||f_{j^{*}}\\},m^{0},m^{1}$ 1.
Check if $f(m^{0})=f(m^{1})$. If not, output $\perp$ and terminate. 2. Compute
$ck=\mathsf{IBE.KeyGen}(cmsk^{\prime},id||f)$. 3.
$(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]}=\mathsf{CosetGen}(1^{L(\lambda)+\lambda};F_{1}(K_{1}\\{id_{j^{*}}||f_{j^{*}}\\},id||f))$.
4. Output $(ck,id,f,(A_{i},s_{i},s_{i}^{\prime})_{i\in[c_{L}(\lambda)]})$.

#####  $\underline{\mathcal{D}_{j}^{(\Delta,4^{\prime})}}$

Same as $\mathcal{D}_{j}^{(\Delta,3^{\prime})}$ except for the following.
Replace the line

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,(id_{j}||f_{j}+\Delta)(m^{b});z^{*})$

with

$ct^{*}=\mathsf{IBE.Enc}(cpk,id_{j}||f_{j}+\Delta,{\color[rgb]{1,0,0}(id_{j}||f_{j}+\Delta)(m^{1-b})};z^{*}).$

First, we claim
${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3^{\prime})}}},{\ell}}$
and
${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4^{\prime})}}},{\ell}}$.
We will only argue the first one and the second one follows similarly. Observe
that by strong punctured key correctness of deterministic
$\mathsf{IBE.KeyGen}$, the obfuscated programs $\mathsf{PKey}$ in these
hybrids can behave differently only on input $(id_{j}||f_{j}+\Delta)(m_{0}).$.
However, since we are considering the case
$(id_{j}||f_{j}+\Delta)(m_{0})\neq(id_{j}||f_{j}+\Delta)(m_{1})$, the programs
will not go past the first line and will have the exact same functionality.
Then, the claim follows by security of $i\mathcal{O}$.

Now, we claim
${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,3^{\prime})}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4^{\prime})}}},{\ell}}$.
Observe that in these hybrids, the randomness used to invoke
$\mathsf{IBE.Enc}$ to compute $ct^{*}$ is uniformly and independently sampled.
Further, the adversary only has the $\mathsf{IBE}$ keys for the identities
$id_{1}||f_{1},id_{2}||f_{2},\dots,id_{k}||f_{k}$, all of which are different
from the identity $id_{j}||f_{j}+\Delta$ under which $ct^{*}$ is encrypted.
Finally, the master secret key $cmsk^{\prime}$ obtained by the adversary is
punctured at $id_{j}||f_{j}+\Delta$. Hence, the result follows from the
punctured master secret key security of $\mathsf{IBE}$. ∎

######  Claim 23.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,4)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,5)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.

Essentially the same argument as in 21 yields the result. ∎

######  Claim 24.

${\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,5)}}},{\ell}}\approx^{c}_{\nu(\lambda)}{\mathsf{Exp}}_{{{\mathcal{D}_{j}^{(\Delta,6)}}},{\ell}}$
for all $j\in\\{0,1,\dots,k\\}$, $\Delta\in\\{0,1,\dots,id_{j+1}-id_{j}-1\\}$
and $\ell\in[k+1]$.

###### Proof.