$\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
to generate a state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems $R$ and aux.

  5. 5.

Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$ to obtain
$\mathbf{x}_{0}\in\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})$
or $\bot$. If the output is $\bot$, output $\mathsf{Invalid}$. Else, run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime},\rho_{\textsc{aux}})$
on the reduced state $\rho_{\mathbf{\textsc{aux}}}$ and then output
$b^{\prime}$.

$\mathsf{H}_{2}:$ This is the following distribution:

  1. 1.

Sample a random matrix
$\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}$.

  2. 2.

Sample
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$,
$\mathbf{e}\sim D_{\mathbb{Z}^{m},\alpha q}$ and $e^{\prime}\sim
D_{\mathbb{Z},\beta q}$.  Let
$\mathbf{u}=\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}$.

  3. 3.

Generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with parameter $\sigma>0$.

  4. 4.

Run
$\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
to generate a state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems $R$ and aux.

  5. 5.

Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$ to obtain
$\mathbf{x}_{0}\in\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})$
or $\bot$. If the output is $\bot$, output $\mathsf{Invalid}$. Else, run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\rho_{\textsc{aux}})$
on the reduced state $\rho_{\mathbf{\textsc{aux}}}$ and output $b^{\prime}$.

$\mathsf{H}_{3}$: This is the following distribution:

  1. 1.

Sample a random matrix
$\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}$.

  2. 2.

Sample
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$.

  3. 3.

Generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with parameter $\sigma>0$.

  4. 4.

Run
$\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
to generate a state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems $R$ and aux.

  5. 5.

Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$ to obtain
$\mathbf{x}_{0}\in\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})$
or $\bot$. If the output is $\bot$, output $\mathsf{Invalid}$. Else, run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\rho_{\textsc{aux}})$
on the reduced state $\rho_{\mathbf{\textsc{aux}}}$ amd output $b^{\prime}$.
Else, output $0$.

$\mathsf{H}_{4}$: This is the distribution $\widetilde{{\sf hyb}}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}$:

  1. 1.

Sample a random matrix
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.

  2. 2.

Sample
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$.

  3. 3.

Generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with parameter $\sigma>0$.

  4. 4.

Run
$\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
to generate a state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems $R$ and aux.

  5. 5.

Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$ to obtain
$\mathbf{x}_{0}\in\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})$
or $\bot$. If the output is $\bot$, output $0$. Else, run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\rho_{\textsc{aux}})$
on the reduced state $\rho_{\mathbf{\textsc{aux}}}$ and output $b^{\prime}$.
Else, output $0$.

We now show the following:

######  Claim 6.5.

Hybrids $\mathsf{H}_{0}$ and $\mathsf{H}_{1}$ are statistically
indistinguishable. In other words,

$\mathsf{H}_{0}\,\approx_{s}\,\mathsf{H}_{1}.$

###### Proof.

This follows from the correctness of $\mathsf{GenTrap}(1^{n},1^{m},q)$ in
Theorem 2.10. ∎

######  Claim 6.6.

Hybrids $\mathsf{H}_{1}$ and $\mathsf{H}_{2}$ are statistically
indistinguishable. In other words,

$\mathsf{H}_{1}\,\approx_{s}\,\mathsf{H}_{2}.$

###### Proof.

Here, we invoke the _noise flooding_ property in Lemma 2.6 to argue that
$\mathbf{e}^{\intercal}\mathbf{x}_{0}\ll e^{\prime}$ holds with overwhelming
probability for our choice of parameters. Therefore, the distributions in
$\mathsf{H}_{1}$ and $\mathsf{H}_{2}$ are computationally indistinguishable. ∎

######  Claim 6.7.

Assuming $\mathsf{LWE}_{n,q,\alpha q}^{m}$, the hybrids $\mathsf{H}_{2}$ and
$\mathsf{H}_{3}$ are computationally indistinguishable:

$\mathsf{H}_{2}\,\approx_{c}\,\mathsf{H}_{3}.$

###### Proof.

Here, we invoke the _non-uniform_ $\mathsf{LWE}_{n,q,\alpha q}^{m}$ assumption
with auiliary input $\nu_{\lambda}$, where $\nu_{\lambda}$ is independent of
$\mathbf{A}$. Consider the following distinguisher $\tilde{\mathcal{D}}$ which
on input $(\mathbf{A},\mathbf{u})$, where
$\mathbf{u}=\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}$ is either
an $\mathsf{LWE}$ sample or a random vector
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$,
does the following:

  1. 1.

Generate
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with parameter $\sigma>0$.

  2. 2.

Compute
$\rho_{R,\mathbf{\textsc{aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
with auxiliary input $\nu_{\lambda}$.

  3. 3.

Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$ to obtain
a short vector $\mathbf{x}_{0}\in\mathbb{Z}_{q}^{m}$.

  4. 4.

Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\rho_{\textsc{aux}})$
on the reduced state $\rho_{\mathbf{\textsc{aux}}}$ and output $b^{\prime}$.

Therefore, if we can distinguishing between the two hybrids $\mathsf{H}_{2}$
and $\mathsf{H}_{3}$, then the distinguisher $\tilde{\mathcal{D}}$ succeeds at
distinguishing between whether
$\mathbf{u}=\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}$ is an
$\mathsf{LWE}$ sample or a random vector
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
– thereby breaking $\mathsf{LWE}_{n,q,\alpha q}^{m}$. This proves the claim. ∎

######  Claim 6.8.

The hybrids $\mathsf{H}_{3}$ and $\mathsf{H}_{4}$ are statistically
indistinguishable. In other words,

$\mathsf{H}_{3}\,\approx_{s}\,\mathsf{H}_{4}.$

###### Proof.

This follows from the correctness of $\mathsf{GenTrap}(1^{n},1^{m},q)$ in
Theorem 2.10. ∎

The first hybrid corresponds to $\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})$ and the last hybrid corresponds
to $\widetilde{{\sf hyb}}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})$. Since we proved that the first
and last hybrids are computationally indistinguishable, it follows that
$\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})\approx_{c}\widetilde{{\sf
hyb}}_{0}.{\sf Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})$, and thus
$\delta_{1}\leq\mathsf{negl}(\lambda)$. This proves the claim. ∎

Plugging in the previous claim that
$\epsilon(\lambda)=\delta_{1}(\lambda)+\delta_{2}(\lambda)\geq
1/\mathrm{poly}(\lambda)$, we have $\delta_{2}(\lambda)\geq
1/\mathrm{poly}(\lambda)$. In other words, we have shown that

$\frac{1}{2}{\sf Pr}[1\leftarrow{\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[0\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]\geq\frac{1}{2}+1/\mathrm{poly}(\lambda).$

We now consider the following hybrid.

${\sf hyb}_{1}.{\sf Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$:
1. Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Sample
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$ 3. Sample $\mathbf{x}_{0}\sim
D_{\mathbb{Z}_{q}^{m},\frac{\sigma}{\sqrt{2}}}$ and let
$\mathbf{y}\leftarrow\mathbf{A}\cdot\mathbf{x}_{0}\ (\mathrm{mod}\ q)$ 4.
Generate
$\ket{\psi_{\mathbf{y}}}\leftarrow\textsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$
5. Generate
$\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
6. Run $\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)$
on system $R$. If it outputs $\top$, continue. Otherwise, output
$\mathsf{Invalid}$. 7. Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\cdot)$
on system Aux. Output $b^{\prime}$.
---
Figure 10: The distribution ${\sf hyb}_{1}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$.
$\tilde{\mathcal{D}}\big{(}\mathbf{A},\mathbf{y},\mathbf{u},v,\rho\big{)}$:
Input: $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$,
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$, $\mathbf{u}\in\mathbb{Z}_{q}^{n}$,
$v\in\mathbb{Z}_{q}$ and $\rho\in L(\mathcal{H}_{\mathbf{\textsc{Aux}}})$.
---
Output: A bit $b^{\prime}\in{\\{0,1\\}}$.
Procedure: 1. Sample $e^{\prime}\sim D_{\mathbb{Z},\beta q}$. 2. Output
$b^{\prime}\leftarrow\mathcal{D}\big{(}\mathbf{A},\mathbf{y},\mathbf{u},v+e^{\prime},\rho\big{)}$.
Figure 11: The distinguisher
$\tilde{\mathcal{D}}\big{(}\mathbf{A},\mathbf{y},\mathbf{u},v,\rho\big{)}$.

We now proceed to the final part of the proof which involves a Goldreich-Levin
reduction. Before we invoke the theorem, we make two observations that will be
relevant below. First, $r+e^{\prime}\ (\mathrm{mod}\ q)$ is uniform for
$r\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}$
and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$. Second, by the correctness of
$\mathsf{QSampGauss}$ in Theorem 3.2, its output is statistically close to
$\mathsf{GenGauss}(\mathbf{A},\sigma)$. This implies that

$\frac{1}{2}{\sf Pr}[1\leftarrow{\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[0\leftarrow{\sf hyb}_{1}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]\geq\frac{1}{2}+1/\mathrm{poly}(\lambda).$

Therefore, we can use the Goldreich-Levin Theorem161616Technically, we invoke
the 1-bit unpredictability variant of the quantum Goldreich-Levin Theorem in
Theorem 4.3, which is implied by the regular indistinguishability formulation.
in Theorem 4.3 to argue that we can convert $\tilde{\mathcal{D}}$ in Figure 11
into an extractor $\mathcal{E}$ that takes as input
$(\mathbf{A},\mathbf{A}\cdot\mathbf{x}_{0},\rho_{\mathbf{\textsc{aux}}})$ and
outputs $\mathbf{x}_{0}$ in time
$\mathrm{poly}\big{(}\lambda,m,\sigma,q,1/\varepsilon\big{)}$ with probability

$\displaystyle\Pr\left[\begin{subarray}{c}\left(\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)\otimes\mathcal{E}(\mathbf{A},\mathbf{y},\cdot)\right)(\rho_{R,\mathbf{\textsc{aux}}})\vspace{3mm}\\\
\vspace{2mm}=\\\
(\top,\mathbf{x}_{0})\end{subarray}\,\,\,:\,\,\,\begin{subarray}{c}(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)\\\
\mathbf{x}_{0}\sim
D_{\mathbb{Z}_{q}^{m},\frac{\sigma}{\sqrt{2}}},\,\mathbf{y}\leftarrow\mathbf{A}\cdot\mathbf{x}_{0}\
(\mathrm{mod}\ q)\\\
\ket{\psi_{\mathbf{y}}}\leftarrow\textsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)\\\
\rho_{R,\mathbf{\textsc{aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\end{subarray}\right]\geq\mathrm{poly}\big{(}1/\lambda,1/m,1/\sigma,1/q,\varepsilon\big{)}.$

Therefore, by the correctness of correctness of $\mathsf{QSampGauss}$ in
Theorem 3.2, there exists a quantum extractor $\mathcal{E}$ that takes as
input $\mathbf{A}$, $\mathbf{y}$ and system Aux of the state
$\rho_{R,\mathbf{\textsc{Aux}}}$ and outputs a short vector in the coset
$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})$ in time
$\mathrm{poly}(\lambda,m,\sigma,q,1/\varepsilon)$ such that

$\displaystyle\Pr\left[\begin{subarray}{c}\left(\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)\otimes\mathcal{E}(\mathbf{A},\mathbf{y},\cdot)\right)(\rho_{R,\mathbf{\textsc{aux}}})=(\top,\mathbf{x})\vspace{1mm}\\\
\bigwedge\vspace{0.1mm}\\\
{\mathbf{x}}\,\,\in\,\,\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})\end{subarray}\,\,:\,\,\begin{subarray}{c}(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)\\\
(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)\\\
\rho_{R,\mathbf{\textsc{aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\end{subarray}\right]\geq\mathrm{poly}\big{(}1/\lambda,1/m,1/\sigma,1/q,\varepsilon\big{)}.$

∎

###  6.3 Distinct Pair Extraction

The following lemma allows us to analyze the probability of simultaneously
extracting two distinct preimages in terms of the success probability of
revocation and the success probability of extracting a preimage from the
adversary’s state.

######  Lemma 6.9 (Projection onto Distinct Pairs).

Let $\rho\in\mathcal{D}({\mathcal{H}}_{X}\otimes{\mathcal{H}}_{Y})$ be an any
density matrix, for some Hilbert spaces ${\mathcal{H}}_{X}$ and
${\mathcal{H}}_{Y}$. Let
$\ket{\psi}=\sum_{x\in\mathcal{S}}\alpha_{x}\ket{x}\in{\mathcal{H}}_{X}$ be
any state supported on a subset ${\mathcal{S}}\subseteq\mathcal{X}$, and let
$\mathbf{\Pi}=\ket{\psi}\\!\bra{\psi}$ denote its associated projection. Let
$\mathbf{\Pi}_{\mathcal{S}}$ be the projector onto $\mathcal{S}$ with

$\mathbf{\Pi}_{\mathcal{S}}=\sum_{x\in\mathcal{S}}|x\rangle\langle x|.$

Let
$\mathcal{E}:\mathcal{L}(\mathcal{H}_{Y})\rightarrow\mathcal{L}(\mathcal{H}_{X^{\prime}})$
be any $\mathsf{CPTP}$ map of the form

$\mathcal{E}_{Y\rightarrow
X^{\prime}}(\sigma)=\mathrm{Tr}_{E}\left[V_{Y\rightarrow
X^{\prime}E}\,\sigma\,V_{Y\rightarrow
X^{\prime}E}^{\dagger}\right],\quad\forall\sigma\in\mathcal{D}(\mathcal{H}_{Y}),$

for some isometry $V_{Y\rightarrow X^{\prime}E}$. Consider the projector
$\mathbf{\Gamma}$ given by

$\mathbf{\Gamma}=\sum_{x,x^{\prime}\in{\mathcal{S}}:x\neq
x^{\prime}}\ket{x}\\!\bra{x}_{X}\otimes V_{Y\rightarrow
X^{\prime}E}^{\dagger}(\ket{x^{\prime}}\\!\bra{x^{\prime}}_{X^{\prime}}\otimes
I_{E})V_{Y\rightarrow X^{\prime}E}.$

Let $\rho_{X}=\mathrm{Tr}_{Y}[\rho_{XY}]$ denote the reduced state. Then, it
holds that

$\mathrm{Tr}[\mathbf{\Gamma}\rho]\,\geq\,\left(1-\max_{x\in{\mathcal{S}}}|\alpha_{x}|^{2}\right)\cdot\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\mathrm{Tr}\left[\mathbf{\Pi}_{\mathcal{S}}\,\mathcal{E}_{Y\rightarrow
X^{\prime}}(\sigma)\right],$

where $\sigma=\mathrm{Tr}[(\mathbf{\Pi}\otimes
I)\rho]^{-1}\cdot\mathrm{Tr}_{X}[(\mathbf{\Pi}\otimes I)\rho]$ is a reduced
state in system $Y$.

###### Proof.

First, note that the projectors $\mathbf{\Gamma}$ and $(\mathbf{\Pi}\otimes
I)$ commute, i.e.

$\mathbf{\Gamma}\left(\mathbf{\Pi}\otimes I\right)=\left(\mathbf{\Pi}\otimes
I\right)\mathbf{\Gamma}.$

Therefore, we have the trace inequality

$\displaystyle\mathrm{Tr}\left[\mathbf{\Gamma}\rho\right]\geq\mathrm{Tr}\left[\left(\mathbf{\Pi}\otimes
I\right)\mathbf{\Gamma}\rho\right]=\mathrm{Tr}\left[\mathbf{\Gamma}(\mathbf{\Pi}\otimes
I)\rho\right].$ (1)

Notice also that $(\mathbf{\Pi}\otimes I)\rho(\mathbf{\Pi}\otimes I)$ lies in
the image of $(\mathbf{\Pi}\otimes I)$ with
$\mathbf{\Pi}=\ket{\psi}\\!\bra{\psi}$, and thus

$\displaystyle(\mathbf{\Pi}\otimes I)\rho(\mathbf{\Pi}\otimes
I)=\mathrm{Tr}[(\mathbf{\Pi}\otimes
I)\rho]\cdot(\ket{\psi}\\!\bra{\psi}\otimes\sigma),$ (2)

for some $\sigma\in\mathcal{D}(\mathcal{H}_{Y})$. Putting everything together,
we get that

$\displaystyle\mathrm{Tr}\left[\mathbf{\Gamma}\rho\right]$ $\displaystyle\geq$
$\displaystyle\mathrm{Tr}\left[\left(\mathbf{\Pi}\otimes
I\right)\mathbf{\Gamma}\rho\right]\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\text{(using
inequality \eqref{ineq:gamma})}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}\left[\mathbf{\Gamma}(\mathbf{\Pi}\otimes
I)\rho\right]\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,\,\text{(since
$\mathbf{\Gamma}$ and $(\mathbf{\Pi}\otimes I)$ commute)}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}\left[\mathbf{\Gamma}(\mathbf{\Pi}\otimes
I)\rho(\mathbf{\Pi}\otimes
I)\mathbf{\Gamma}\right]\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\text{(since
$\mathbf{\Gamma}(\mathbf{\Pi}\otimes I)$ is a projector)}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}[(\mathbf{\Pi}\otimes
I)\rho]\cdot\mathrm{Tr}\left[\mathbf{\Gamma}\left(\ket{\psi}\\!\bra{\psi}\otimes\sigma\right)\mathbf{\Gamma}\right]\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\text{(using
equation \eqref{ineq:sigma})}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}[(\mathbf{\Pi}\otimes
I)\rho]\cdot\mathrm{Tr}\left[\mathbf{\Gamma}\left(\ket{\psi}\\!\bra{\psi}\otimes\sigma\right)\right]\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(since
$\mathbf{\Gamma}$ is a projector)}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\mathrm{Tr}\left[\sum_{x,x^{\prime}\in{\mathcal{S}}:x\neq
x^{\prime}}\ket{x}\\!\bra{x}_{X}\otimes V_{Y\rightarrow
X^{\prime}E}^{\dagger}\left(\ket{x^{\prime}}\\!\bra{x^{\prime}}_{X^{\prime}}\otimes
I_{E}\right)V_{Y\rightarrow
X^{\prime}E}\left(\ket{\psi}\\!\bra{\psi}\otimes\sigma\right)\right]$
$\displaystyle=$
$\displaystyle\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\sum_{x^{\prime}\in{\mathcal{S}}}\left(\sum_{x\in{\mathcal{S}}:x\neq
x^{\prime}}|\langle x|\psi\rangle|^{2}\right)\mathrm{Tr}\left[V_{Y\rightarrow
X^{\prime}E}^{\dagger}(\ket{x^{\prime}}\\!\bra{x^{\prime}}_{X^{\prime}}\otimes
I_{E})V_{Y\rightarrow X^{\prime}E}\,\sigma\right]$ $\displaystyle=$
$\displaystyle\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\sum_{x^{\prime}\in{\mathcal{S}}}\left(1-|\alpha_{x^{\prime}}|^{2}\right)\mathrm{Tr}\left[(\ket{x^{\prime}}\\!\bra{x^{\prime}}_{X^{\prime}}\otimes
I_{E})V_{Y\rightarrow X^{\prime}E}\,\sigma\,V_{Y\rightarrow
X^{\prime}E}^{\dagger}\right]$ $\displaystyle\geq$
$\displaystyle\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\left(1-\max_{x\in{\mathcal{S}}}|\alpha_{x}|^{2}\right)\cdot\sum_{x^{\prime}\in{\mathcal{S}}}\mathrm{Tr}\left[(\ket{x^{\prime}}\\!\bra{x^{\prime}}_{X^{\prime}}\otimes
I_{E})V_{Y\rightarrow X^{\prime}E}\,\sigma\,V_{Y\rightarrow
X^{\prime}E}^{\dagger}\right]$ $\displaystyle=$
$\displaystyle\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\left(1-\max_{x\in{\mathcal{S}}}|\alpha_{x}|^{2}\right)\cdot\sum_{x^{\prime}\in{\mathcal{S}}}\mathrm{Tr}\left[\ket{x^{\prime}}\\!\bra{x^{\prime}}_{X^{\prime}}\mathrm{Tr}_{E}\left[V_{Y\rightarrow
X^{\prime}E}\,\sigma\,V_{Y\rightarrow X^{\prime}E}^{\dagger}\right]\right]$
$\displaystyle=$
$\displaystyle\mathrm{Tr}[\mathbf{\Pi}\rho_{X}]\cdot\left(1-\max_{x\in{\mathcal{S}}}|\alpha_{x}|^{2}\right)\cdot\mathrm{Tr}\left[\mathbf{\Pi}_{\mathcal{S}}\,\mathcal{E}_{Y\rightarrow
X^{\prime}}(\sigma)\right].$

This proves the claim. ∎

###  6.4 Proof of Theorem 6.1

###### Proof.

Let $\mathcal{A}$ be a $\mathsf{QPT}$ adversary and suppose that

$\Pr\left[b\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]=\frac{1}{2}+\epsilon(\lambda),$

for some $\varepsilon(\lambda)$ with respect to
$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$ in Figure 12. We show that
$\varepsilon(\lambda)$ is negligible.

$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$: 1. The challenger samples
$(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$ and
generates |ψ_y⟩ = ∑_x ∈Z_q^mA x = y (mod q)ρ_σ(x) |x⟩, for some
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$, by running
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
The challenger lets $\mathsf{MSK}\leftarrow\mathsf{td}_{\mathbf{A}}$ and
$\mathsf{PK}\leftarrow(\mathbf{A},\mathbf{y})$ and sends
$\rho_{\mathsf{SK}}\leftarrow\ket{\psi_{\mathbf{y}}}$ to the adversary
$\mathcal{A}$. 2. $\mathcal{A}$ generates a (possibly entangled) bipartite
state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems
$\mathcal{H}_{R}\otimes\mathcal{H}_{\textsc{Aux}}$ with
$\mathcal{H}_{R}=\mathcal{H}_{q}^{m}$, returns system $R$ and holds onto the
auxiliary system Aux. 3. The challenger runs
$\mathsf{Revoke}(\mathsf{PK},\mathsf{MSK},\rho_{R})$, where $\rho_{R}$ is the
reduced state in system $R$. If the outcome is $\top$, the game continues.
Otherwise, output Invalid. 4. $\mathcal{A}$ submits a plaintext bit
$\mu\in{\\{0,1\\}}$. 5. The challenger does the following depending on
$b\in{\\{0,1\\}}$: • if $b=0$: the challenger samples a vector
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$
and errors $\mathbf{e}\sim D_{\mathbb{Z}^{m},\,\alpha q}$ and $e^{\prime}\sim
D_{\mathbb{Z},\,\beta q}$, and sends a Dual-Regev encryption of
$\mu\in{\\{0,1\\}}$ to $\mathcal{A}$: CT= (s^⊺A \+ e^⊺, s^⊺y \+ e’ + μ⋅⌊q2 ⌋)
∈Z_q^m ×Z_q.  • if $b=1$: the challenger samples
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and
$r\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}$
uniformly at random and sends the following pair to $\mathcal{A}$: (u,r)
∈Z_q^m ×Z_q.  6. $\mathcal{A}$ returns a bit $b^{\prime}\in{\\{0,1\\}}$.
---
Figure 12: The key-revocable security experiment according to Definition 5.3.

Suppose for the sake of contradiction that $\epsilon(\lambda)$ is non-
negligible. We show that we can use $\mathcal{A}$ to break the
$\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$ problem. Without loss of generality,
we assume that $\mathcal{A}$ submits the plaintext $x=0$. By the assumption
that $\epsilon(\lambda)\geq 1/\mathrm{poly}(\lambda)$, it follows from Theorem
6.3 that there exists a quantum Goldreich-Levin extractor $\mathcal{E}$ that
takes as input $\mathbf{A}$, $\mathbf{y}$ and system Aux of the state
$\rho_{R,\mathbf{\textsc{Aux}}}$ and outputs a short vector in the coset
$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})$ in time
$\mathrm{poly}(\lambda,m,\sigma,q,1/\varepsilon)$ such that

$\displaystyle\Pr\left[\begin{subarray}{c}\left(\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)\otimes\mathcal{E}(\mathbf{A},\mathbf{y},\cdot)\right)(\rho_{R,\mathbf{\textsc{Aux}}})=(\top,\mathbf{x})\vspace{1mm}\\\
\bigwedge\vspace{0.1mm}\\\
{\mathbf{x}}\,\,\in\,\,\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})\end{subarray}\,:\,\begin{subarray}{c}(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)\\\
(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)\\\
\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\end{subarray}\right]\geq\mathrm{poly}\big{(}1/\lambda,1/m,1/\sigma,1/q,\varepsilon\big{)}.$

Consider the following procedure in Algorithm 3.

Input: Matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$.

Output: Vector $\mathbf{x}\in\mathbb{Z}^{m}$.

1

2Generate a Gaussian state
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with
$\ket{\psi_{\mathbf{y}}}\,\,=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{x})\,\ket{\mathbf{x}}$ for some vector
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$.

3

4Run $\mathcal{A}$ to generate a bipartite state
$\rho_{R\,\mathbf{\textsc{Aux}}}$ in systems
$\mathcal{H}_{R}\otimes\mathcal{H}_{\textsc{aux}}$ with
$\mathcal{H}_{R}=\mathcal{H}_{q}^{m}$.

5

6Measure system $R$ in the computational basis, and let
$\mathbf{x}_{0}\in\mathbb{Z}_{q}^{n}$ denote the outcome.

7

8Run the quantum Goldreich-Levin extractor
$\mathcal{E}(\mathbf{A},\mathbf{y},\rho_{\mathbf{\textsc{aux}}})$ from Theorem
6.3, where $\rho_{\mathbf{\textsc{Aux}}}$ is the reduced state in system
$\mathcal{H}_{\textsc{Aux}}$, and let $\mathbf{x}_{1}\in\mathbb{Z}_{q}^{n}$
denote the outcome.

9

Output the vector $\mathbf{x}=\mathbf{x}_{1}-\mathbf{x}_{0}$.

Algorithm 3 $\mathsf{SIS\\_Solver}(\mathbf{A})$

To conclude the proof, we show that $\mathsf{SIS\\_Solver}(\mathbf{A})$ in
Algorithm 3 breaks the $\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$ problem
whenever $\varepsilon(\lambda)=1/\mathrm{poly}(\lambda)$. In order to
guarantee that $\mathsf{SIS\\_Solver}(\mathbf{A})$ is successful, we use the
distinct pair extraction result of Lemma 6.9. This allows us to analyze the
probability of simultaneously extracting two distinct short pre-images
$\mathbf{x}_{0}\neq\mathbf{x}_{1}$ such that
$\mathbf{A}\mathbf{x}_{0}=\mathbf{y}=\mathbf{A}\mathbf{x}_{1}\ (\mathrm{mod}\
q)$ – both in terms of the success probability of revocation and the success
probability of extracting a pre-image from the adversary’s state
$\rho_{\mathbf{\textsc{Aux}}}$ in system $\mathcal{H}_{\textsc{Aux}}$.
Assuming that $\mathbf{x}_{0},\mathbf{x}_{1}$ are distinct short pre-images
such that $\|\mathbf{x}_{0}\|\leq\sigma\sqrt{\frac{m}{2}}$ and
$\|\mathbf{x}_{1}\|\leq\sigma\sqrt{\frac{m}{2}}$, it then follows that the
vector $\mathbf{x}=\mathbf{x}_{1}-\mathbf{x}_{0}$ output by
$\mathsf{SIS\\_Solver}(\mathbf{A})$ has norm at most $\sigma\sqrt{2m}$, and
thus yields a solution to $\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$.

We remark that the state $\ket{\psi_{{\mathbf{y}}}}$ prepared by Algorithm 3
is not normalized for ease of notation. Note that the tail bound in Lemma 2.4
implies that (the normalized variant of) $\ket{\psi_{{\mathbf{y}}}}$ is within
negligible trace distance of the state with support
$\\{\mathbf{x}\in\mathbb{Z}_{q}^{m}:\|\mathbf{x}\|\leq\sigma\sqrt{\frac{m}{2}}\\}$.
Therefore, for the sake of Lemma 6.9, we can assume that
$\ket{\psi_{{\mathbf{y}}}}$ is a normalized state of the form

$\ket{\psi_{{\mathbf{y}}}}=\left(\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{\frac{m}{2}}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\frac{\sigma}{\sqrt{2}}}(\mathbf{z})\right)^{-\frac{1}{2}}\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\|\mathbf{x}\|\leq\sigma\sqrt{\frac{m}{2}}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}.$

Before we analyze Algorithm 3, we first make two technical remarks. First,
since $\sigma\geq\omega(\sqrt{\log m})$, it follows from Lemma 2.7 that, for
any full-rank $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and for any
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$, we have

$\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{\frac{m}{2}}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\left\\{\frac{\rho_{\frac{\sigma}{\sqrt{2}}}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{\frac{m}{2}}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\frac{\sigma}{\sqrt{2}}}(\mathbf{z})}\right\\}\,\,\leq\,\,2^{-\Omega(m)}.$

Second, we can replace the procedure
$\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\rho_{R})$ by
an (inefficient) projective measurement
$\\{|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|,I-|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\\}$,
since they produce statistically close outcomes. This follows from the fact
that
$\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\rho_{R})$
applies the procedure $\mathsf{QSampGauss}$ in Algorithm 2 as a subroutine,
which is correct with overwhelming probability acccording to Theorem 3.2.

Let us now analyze the success probability of Algorithm 3. Putting everything
together, we get

$\displaystyle{\sf Pr}\left[\begin{subarray}{c}\mathbf{x}\leftarrow{\sf
SIS}\\_{\sf Solver}(\mathbf{A})\vspace{1mm}\\\ \bigwedge\vspace{0.5mm}\\\
\mathbf{x}\neq\mathbf{0}\,\text{
s.t.}\,\,\|\mathbf{x}\|\leq\sigma\sqrt{2m}\end{subarray}\ \,:\,\
\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}\right]$
$\displaystyle\geq\left(1-\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{\frac{m}{2}}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\left\\{\frac{\rho_{\frac{\sigma}{\sqrt{2}}}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{\frac{m}{2}}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\frac{\sigma}{\sqrt{2}}}(\mathbf{z})}\right\\}\right)$
$\displaystyle\quad\cdot\Pr\left[{\sf
IneffRevoke}({\mathbf{A}},{\mathbf{y}},\rho_{R})=\top\,\,:\,\,\begin{subarray}{c}\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}\text{ s.t. }{\mathbf{A}}\text{ is full-rank}\\\
(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)\\\
\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\end{subarray}\right]$
$\displaystyle\quad\cdot\Pr\left[\mathcal{E}\big{(}\mathbf{A},\mathbf{y},\rho_{\mathbf{\textsc{Aux}}}\big{)}\,\,\in\,\,\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\cap\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{m/2})\,\,:\,\,\begin{subarray}{c}\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}\text{ s.t. }{\mathbf{A}}\text{ is full-rank}\\\
(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)\\\
\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\\\
\top\leftarrow{\sf
IneffRevoke}({\mathbf{A}},{\mathbf{y}},\rho_{R})\end{subarray}\right]$
$\displaystyle\geq\left(1-2^{-\Omega(m)}\right)\cdot\Pr\left[\begin{subarray}{c}\left({\sf
IneffRevoke}({\mathbf{A}},{\mathbf{y}},\cdot)\otimes\mathcal{E}(\mathbf{A},\mathbf{y},\cdot)\right)(\rho_{R\,\mathbf{\textsc{aux}}})=(\top,\mathbf{x}_{1})\vspace{2mm}\\\
\bigwedge\vspace{0.5mm}\\\ \ \\\
{\mathbf{x}_{1}}\in\,\,\in\,\,\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\cap\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})\end{subarray}\,:\,\begin{subarray}{c}\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}\\\ \text{ s.t. }{\mathbf{A}}\text{ is full-rank}\\\
(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)\\\
\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\end{subarray}\right]$
$\displaystyle\geq\left(1-2^{-\Omega(m)}\right)\cdot\big{(}\mathrm{poly}(1/q,\varepsilon)-q^{-n}\big{)}\quad\geq\quad\mathrm{poly}(1/q,\varepsilon).$

In other words, $\mathsf{SIS\\_Solver}(\mathbf{A})$ in Algorithm 3 runs in
time $\mathrm{poly}(q,1/\varepsilon)$ and solves
$\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$ whenever
$\varepsilon=1/\mathrm{poly}(\lambda)$. Therefore, we conclude that
$\varepsilon(\lambda)$ must be negligible. ∎

##  7 Key-Revocable Fully Homomorphic Encryption

In this section, we describe our key-revocable (leveled) fully homomorphic
encryption scheme from $\mathsf{LWE}$ which is based on the so-called
$\mathsf{DualGSW}$ scheme used by Mahadev [Mah18] which itself is a variant of
the homomorphic encryption scheme by Gentry, Sahai and Waters [GSW13].

Let $\lambda\in\mathbb{N}$ be the security parameter. Suppose we would like to
evaluate $L$-depth circuits consisting of $\mathsf{NAND}$ gates. We choose
$n(\lambda,L)\gg L$ and a prime $q=2^{o(n)}$. Then, for integer parameters
$m\geq 2n\log q$ and $N=(m+1)\cdot\lceil\log q\rceil$, we let $\mathbf{I}$ be
the $(m+1)\times(m+1)$ identity matrix and let
$\mathbf{G}=[\mathbf{I}\,\|\,2\mathbf{I}\,\|\,\dots\,\|\,2^{\lceil\log
q\rceil-1}\mathbf{I}]\in\mathbb{Z}_{q}^{(m+1)\times N}$ denote the so-called
_gadget matrix_ which converts a binary representation of a vector back to its
original vector representation over the field $\mathbb{Z}_{q}$. Note that the
associated (non-linear) inverse operation $\mathbf{G}^{-1}$ converts vectors
in $\mathbb{Z}_{q}^{m+1}$ to their binary representation in ${\\{0,1\\}}^{N}$.
In other words, we have that $\mathbf{G}\circ\mathbf{G}^{-1}$ acts as the
identity operator.

###  7.1 Construction

######  Construction 3 (Key-Revocable DualGSW encryption).

Let $\lambda\in\mathbb{N}$ be the security parameter. The scheme
$\mathsf{RevDualGSW}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Eval},\mathsf{Revoke})$
consists of the following $\mathsf{QPT}$ algorithms:

$\mathsf{KeyGen}(1^{\lambda},1^{L})\rightarrow(\mathsf{PK},\rho_{\mathsf{SK}}):$
sample a pair $(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$ and
generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with

$\ket{\psi_{\mathbf{y}}}\,\,=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\,\ket{\mathbf{x}},$

for some $\mathbf{y}\in\mathbb{Z}_{q}^{n}$. Output
$\mathsf{PK}=(\mathbf{A},\mathbf{y})$,
$\rho_{\mathsf{SK}}=\ket{\psi_{\mathbf{y}}}$ and
$\mathsf{MSK}=\mathsf{td}_{\mathbf{A}}$.

$\mathsf{Enc}(\mathsf{PK},\mu):$ to encrypt $\mu\in{\\{0,1\\}}$, parse
$(\mathbf{A},\mathbf{y})\leftarrow\mathsf{PK}$, sample a random matrix
$\mathbf{S}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
N}$ and $\mathbf{E}\sim D_{\mathbb{Z}^{m\times N},\,\alpha q}$ and row vector
$\mathbf{e}\sim D_{\mathbb{Z}^{N},\,\beta q}$, and output the ciphertext

$\mathsf{CT}=\left[\begin{subarray}{c}\mathbf{A}^{\intercal}\mathbf{S}+\mathbf{E}\vspace{1mm}\\\
\hline\cr\vspace{1mm}\\\
\mathbf{y}^{\intercal}\mathbf{S}+\mathbf{e}\end{subarray}\right]+\mu\cdot\mathbf{G}\
(\mathrm{mod}\ q)\in\mathbb{Z}_{q}^{(m+1)\times N}.$

$\mathsf{Eval}(\mathsf{CT}_{0},\mathsf{CT}_{1}):$ to apply a $\mathsf{NAND}$
gate on a ciphertext pair $\mathsf{CT}_{0}$ and $\mathsf{CT}_{1}$, output the
matrix

$\mathbf{G}-\mathsf{CT}_{0}\cdot\mathbf{G}^{-1}(\mathsf{CT}_{1})\
(\mathrm{mod}\ q)\in\mathbb{Z}_{q}^{(m+1)\times N}.$

$\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT})\rightarrow{\\{0,1\\}}:$ to
decrypt $\mathsf{CT}$, apply the unitary
$U:\ket{\mathbf{x}}\ket{0}\rightarrow\ket{\mathbf{x}}\ket{(-\mathbf{x},1)\cdot\mathsf{CT}_{N}}$
on input $\ket{\psi_{\mathbf{y}}}\leftarrow\rho_{\mathsf{SK}}$, where
$\mathsf{CT}_{N}\in\mathbb{Z}_{q}^{m+1}$ is the $N$-th column of
$\mathsf{CT}$, and measure the second register in the computational basis.
Output $0$, if the measurement outcome is closer to $0$ than to
$\lfloor\frac{q}{2}\rfloor$, and output $1$, otherwise.

$\mathsf{Revoke}(\mathsf{MSK},\mathsf{PK},\rho)\rightarrow\\{\top,\bot\\}$: on
input $\mathsf{td}_{\mathbf{A}}\leftarrow\mathsf{MSK}$ and
$(\mathbf{A},\mathbf{y})\leftarrow\mathsf{PK}$, apply the projective
measurement
$\\{\ket{\psi_{\mathbf{y}}}\\!\bra{\psi_{\mathbf{y}}},I-\ket{\psi_{\mathbf{y}}}\\!\bra{\psi_{\mathbf{y}}}\\}$
onto $\rho$ using
$\mathsf{SampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$ in
Algorithm 2. Output $\top$ if the measurement is successful, and output $\bot$
otherwise.

###  7.2 Proof of Theorem 7.1

$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$: 1. The challenger samples
$(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$ and
generates |ψ_y⟩ = ∑_x ∈Z_q^mA x = y (mod q)ρ_σ(x) |x⟩, for some
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$, by running
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
The challenger lets $\mathsf{MSK}\leftarrow\mathsf{td}_{\mathbf{A}}$ and
$\mathsf{PK}\leftarrow(\mathbf{A},\mathbf{y})$ and sends
$\rho_{\mathsf{SK}}\leftarrow\ket{\psi_{\mathbf{y}}}$ to the adversary
$\mathcal{A}$. 2. $\mathcal{A}$ generates a (possibly entangled) bipartite
state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems
$\mathcal{H}_{R}\otimes\mathcal{H}_{\textsc{Aux}}$ with
$\mathcal{H}_{R}=\mathcal{H}_{q}^{m}$, returns system $R$ and holds onto the
auxiliary system Aux. 3. The challenger runs
$\mathsf{Revoke}(\mathsf{MSK},\mathsf{PK},\rho_{R})$, where $\rho_{R}$ is the
reduced state in system $R$. If the outcome is $\top$, the game continues.
Otherwise, output Invalid. 4. $\mathcal{A}$ submits a plaintext bit
$\mu\in{\\{0,1\\}}$. 5. The challenger does the following depending on
$b\in{\\{0,1\\}}$: • if $b=0$: The challenger samples a random matrix
$\mathbf{S}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
N}$ and errors $\mathbf{E}\sim D_{\mathbb{Z}^{m\times N},\,\alpha q}$ and row
vector $\mathbf{e}\sim D_{\mathbb{Z}^{N},\,\beta q}$, and outputs the
ciphertext CT= [A^⊺S \+ Ey^⊺S \+ e ] + μ⋅G ∈Z_q^(m+1)×N.  • if $b=1$: the
challenger samples a matrix
$\mathbf{U}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m\times
N}$ and row vector
$r\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{N}$
uniformly at random, and sends the following to $\mathcal{A}$: [U r ]
∈Z_q^(m+1)×N.  6. $\mathcal{A}$ returns a bit $b^{\prime}\in{\\{0,1\\}}$.
---
Figure 13: The key-revocable security experiment according to Definition 5.3.

######  Theorem 7.1.

Let $L$ be an upper bound on the $\mathsf{NAND}$-depth of the circuit which is
to be evaluated. Let $n\in\mathbb{N}$ and $q$ be a prime modulus with
$n=n(\lambda,L)\gg L$, $q=2^{o(n)}$ and $m\geq 2n\log q$, each parameterized
by the security parameter $\lambda\in\mathbb{N}$. Let $N=(m+1)\cdot\lceil\log
q\rceil$ be an integer. Let $\sigma\in(\sqrt{2m},q/\sqrt{2m})$ and let
$\alpha,\beta\in(0,1)$ be parameters such that $\beta/\alpha=2^{o(n)}$ and
$1/\alpha=2^{o(n)}\cdot\sigma$. Then, assuming the subexponential hardness of
the $\mathsf{LWE}_{n,q,\alpha q}^{m}$ and
$\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$ problems, the scheme
$\mathsf{RevDualGSW}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Eval},\mathsf{Revoke})$
in 3 is a secure key-revocable (leveled) fully homomorphic encryption scheme
according to Definition 5.3.

###### Proof.

Let $\mathcal{A}$ be a $\mathsf{QPT}$ adversary and suppose that

$\Pr\left[b\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]=\frac{1}{2}+\epsilon(\lambda),$

for some $\varepsilon(\lambda)$ with respect to
$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$ in Figure 13. Note that the
RevDualGSW ciphertext can (up to an additive shift) be thought of as a column-
wise concatenation of $N$-many independent ciphertexts of our key-revocable
Dual-Regev scheme in 2. Therefore, we can invoke 5.8 and Theorem 6.1 in order
to argue that $\varepsilon(\lambda)$ is at most negligible.

∎

##  8 Revocable Pseudorandom Functions

In this section, we introduce the notion of _key-revocable_ pseudorandom
functions (or simply, called revocable) and present the first construction
from (quantum hardness of) learning with errors.

###  8.1 Definition

Let us first recall the traditional notion of $\mathsf{PRF}$ security [GGM86],
defined as follows.

######  Definition 8.1 (Pseudorandom Function).

Let $\lambda\in\mathbb{N}$ and $\kappa(\lambda),\ell(\lambda)$ and
$\ell^{\prime}(\lambda)$ be polynomials. A (post-quantum) pseudorandom
function $(\mathsf{pqPRF})$ is a pair $({\sf Gen},\mathsf{PRF})$ of
$\mathsf{PPT}$ algorithms given by

  * •

${\sf Gen}(1^{\lambda}):$ On input $1^{\lambda}$, it outputs a key
$k\in{\\{0,1\\}}^{\kappa}$.

  * •

$\mathsf{PRF}(k,x):$ On input $k\in{\\{0,1\\}}^{\kappa}$ and
$x\in{\\{0,1\\}}^{\ell}$, it outputs a value
$y\in{\\{0,1\\}}^{\ell^{\prime}}$.

with the property that, for any $\mathsf{QPT}$ distinguisher $\mathcal{D}$, we
have

$\displaystyle\vline\,\Pr\left[\mathcal{D}^{\mathsf{PRF}(k,\cdot)}(1^{\lambda})=1]\,:\,k\leftarrow{\sf
Gen}(1^{\lambda})\right]-\Pr\left[\mathcal{D}^{F(\cdot)}(1^{\lambda})=1]\,:\,F\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathcal{F}^{\ell,\ell^{\prime}}\right]\,\vline\,\leq\,\mathsf{negl}(\lambda),$

where $\mathcal{F}^{\ell,\ell^{\prime}}$ is the set of all functions with
domain ${\\{0,1\\}}^{\ell}$ and range ${\\{0,1\\}}^{\ell^{\prime}}$.

We now present a formal definition of revocable pseudorandom functions below.

######  Definition 8.2 (Revocable Pseudorandom Function).

Let $\lambda\in\mathbb{N}$ be the security parameter and let
$\kappa(\lambda),\ell(\lambda)$ and $\ell^{\prime}(\lambda)$ be polynomials. A
revocable pseudorandom function $(\mathsf{rPRF})$ is a scheme $({\sf Gen},{\sf
PRF},{\sf Eval},\mathsf{Revoke})$ consisting of the following efficient
algorithms:

  * •

${\sf Gen}(1^{\lambda})$: on input the security parameter
$\lambda\in\mathbb{N}$, it outputs a ${\sf PRF}$ key
$k\in{\\{0,1\\}}^{\kappa}$, a quantum state $\rho_{k}$ and a master secret key
$\mathsf{MSK}$.

  * •

${\sf PRF}(k,x)$: on input a key $k\in{\\{0,1\\}}^{\kappa}$ and an input
string $x\in\\{0,1\\}^{\ell}$, it outputs a value
$y\in\\{0,1\\}^{\ell^{\prime}}$. This is a deterministic algorithm.

  * •

${\sf Eval}(\rho_{k},x)$: on input a state $\rho_{k}$ and an input
$x\in\\{0,1\\}^{\ell}$, it outputs a value $y\in\\{0,1\\}^{\ell^{\prime}}$.

  * •

$\mathsf{Revoke}(\mathsf{MSK},\sigma)$: on input key $\mathsf{MSK}$ and a
state $\sigma$, it outputs $\mathsf{Valid}$ or $\mathsf{Invalid}$.

We additionally require that the following holds:

##### Correctness.

For each $(k,\rho_{k},\mathsf{MSK})$ in the support of ${\sf
Gen}(1^{\lambda})$ and for every $x\in\\{0,1\\}^{\ell}$:

  * •

(Correctness of evaluation:)

${\sf Pr}\left[{\sf PRF}(k,x)={\sf Eval}(\rho_{k},x)\right]\geq
1-\mathsf{negl}(\lambda).$

  * •

(Correctness of revocation:)

${\sf
Pr}\left[\mathsf{Valid}\leftarrow\mathsf{Revoke}(\mathsf{MSK},\rho_{k})\right]\geq
1-\mathsf{negl}(\lambda).$

###  8.2 Security

We define revocable ${\sf PRF}$ security below.

$\mathsf{Expt}^{\mathcal{A},\mu}(1^{\lambda},b)$: Initialization Phase: • The
challenger computes
$(k,\rho_{k},\mathsf{MSK})\leftarrow\mathsf{Gen}(1^{\lambda})$ and sends
$\rho_{k}$ to $\mathcal{A}$. Revocation Phase: • The challenger sends the
message REVOKE to $\mathcal{A}$. • The adversary $\mathcal{A}$ sends a state
$\sigma$ to the challenger. • The challenger aborts if
$\mathsf{Revoke}\left(\mathsf{MSK},\sigma\right)$ outputs $\mathsf{Invalid}$.
Guessing Phase: • The challenger samples bit $b\leftarrow\\{0,1\\}$. • The
challenger samples random inputs
$x_{1},\dots,x_{\mu}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}{\\{0,1\\}}^{\ell}$
and then sends the values $(x_{1},\dots,x_{\mu})$ and $(y_{1},\dots,y_{\mu})$
to $\mathcal{A}$, where: – If $b=0$, set
$y_{1}=\mathsf{PRF}(k,x_{1}),\,\dots,\,y_{\mu}=\mathsf{PRF}(k,x_{\mu})$ and, –
If $b=1$, set
$y_{1},\dots,y_{\mu}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\\{0,1\\}^{\ell^{\prime}}$.
• $\mathcal{A}$ outputs a bit $b^{\prime}$ and wins if $b^{\prime}=b$.
---
Figure 14: Revocable $\mathsf{PRF}$ security

######  Definition 8.3 (Revocable ${\sf PRF}$ Security).

A revocable pseudorandom function $(\mathsf{rPRF})$ satisfies revocable
$\mathsf{PRF}$ security if, for every QPT adversary $\mathcal{A}$ and every
polynomial $\mu=\mu(\lambda)\in\mathbb{N}$,

$\Pr\left[b\leftarrow\mathsf{Expt}^{\mathcal{A},\mu}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]\leq\frac{1}{2}+\mathsf{negl}(\lambda),$

where $\mathsf{Expt}^{\mathcal{A},\mu}$ is as defined in Figure 14. If the
above property holds for a fixed polynomial $\mu(\lambda)$, then we say that
$\mathsf{rPRF}$ satisfies $\mu$-revocable $\mathsf{PRF}$ security.

##### From one-query to multi-query security.

We show that proving security with respect to $\mu=1$ is sufficient. That is,
we show the following.

######  Claim 8.4.

Supoose an $\mathsf{rPRF}$ scheme $({\sf Gen},{\sf PRF},{\sf
Eval},\mathsf{Revoke})$ satisfies $1$-revocable $\mathsf{PRF}$ security. Then,
$\mathsf{rPRF}$ also satisfies the stronger notion of (multi-query) revocable
PRF security.

###### Proof.

We consider a sequence of hybrids defined as follows. Let $\mathcal{A}$ be a
QPT adversary participating in the revocable PRF security experiment and let
$(x_{1},y_{1}),\ldots,(x_{\mu},y_{\mu})$ denote the challenge input-output
pairs, for some polynomial $\mu=\mu(\lambda)$. We also denote by $k$ the
$\mathsf{PRF}$ key sampled using ${\sf Gen}$ by the challenger in Figure 14.

$\mathsf{H}_{i}$, for $i\in[\mu+1]$: In this hybrid, $y_{1},\ldots,y_{i-1}$
are sampled uniformly at random from $\\{0,1\\}^{\ell^{\prime}}$ and
$y_{i},\ldots,y_{\mu}$ are generated as follows: $y_{j}={\sf PRF}(k,x_{j})$
for $j\geq i$.

We claim that $\mathcal{A}$ can win the 1-bit unpredictability game between
hybrids $\mathsf{H}_{i}$ and $\mathsf{H}_{i+1}$, for all $i\in[\mu]$, with
probability $\frac{1}{2}+\mathsf{negl}(\lambda)$. That is, a bit $b$ is
sampled uniformly at random and if $b=0$ then $\mathcal{A}$ participates in
$\mathsf{H}_{i}$ and if $b=1$ then $\mathcal{A}$ participates in
$\mathsf{H}_{i+1}$. We claim that $\mathcal{A}$ can predict $b$ with
probability $\frac{1}{2}+\mathsf{negl}(\lambda)$. Once we show this, we can
then invoke the hybrid lemma for 1-bit unpredictability (Lemma 5.5) to
complete the proof.

Suppose the above claim is not true. Let the prediction probability of
$\mathcal{A}$ be $\frac{1}{2}+\varepsilon$, where $\varepsilon$ is inverse
polynomial. Then we use $\mathcal{A}$ to break 1-revocation security of
$\mathsf{rPRF}$. Specifically, we construct a reduction ${\mathcal{B}}$ that
does the following:

  * •

Get $\rho_{k}$ from the challenger.

  * •

Sample $x_{i+1},\ldots,x_{\mu}$ uniformly at random from $\\{0,1\\}^{\ell}$.
Denote $\rho_{k}^{(i+1)}=\rho_{k}$. Do the following for $j=i+1,\ldots,\mu$:
${\sf Eval}(\rho_{k}^{(j)},x_{j})$ to obtain $y_{j}$. Using Almost as good as
new lemma [Aar16], recover $\rho_{k}^{(j+1)}$, where $\rho_{k}^{(j+1)}$ is
negligibly171717Technically, this depends on the correctness error and we
start with a $\mathsf{rPRF}$ that is correct with probability negligibly close
to 1. close to $\rho_{k}$ in trace distance.

  * •

Forward $\rho_{k}^{(\mu+1)}$ to $\mathcal{A}$.

  * •

When the challenger sends the message REVOKE then forward this message to
$\mathcal{A}$.

  * •

If $\mathcal{A}$ sends $\sigma$. Forward this to the challenger.

  * •

If the revocation did not fail, the guessing phase begins. The challenger
sends $(x^{*},y^{*})$. Then, sample $x_{1},\ldots,x_{i-1}$ uniformly at random
from $\\{0,1\\}^{\ell}$ and $y_{1},\ldots,y_{i-1}$ uniformly at random from
$\\{0,1\\}^{\ell^{\prime}}$. Set $x_{i}=x^{*}$ and $y_{i}=y^{*}$. Send
$(x_{1},y_{1}),\ldots,(x_{\mu},y_{\mu})$ to $\mathcal{A}$.

  * •

Output $b$, where $b$ is the output of $\mathcal{A}$.

From the quantum union bound [Gao15], Almost as good as new lemma [Aar09] and
the correctness of $\mathsf{rPRF}$, it follows that
$\operatorname{TD}(\rho_{k},\rho_{k}^{(\mu+1)})\leq\mathsf{negl}(\lambda)$ and
thus, the success probability of $\mathcal{A}$ when given $\rho_{k}^{(\mu+1)}$
instead of $\rho_{k}$ is now at least
$\frac{1}{2}+\varepsilon-\mathsf{negl}(\lambda)$. Moreover, by the design of
${\mathcal{B}}$, it follows that the success probability of ${\mathcal{B}}$ in
breaking 1-revocation security of $\mathsf{rPRF}$ is exactly the same as the
success probability of $\mathcal{A}$ in breaking revocation security of
$\mathsf{rPRF}$. This contradicts the fact that $\mathsf{rPRF}$ satisfies
1-revocation security.

∎

######  Remark 8.5.

As in the case of key revocable public-key encryption, we could consider an
alternate definition defined with respect to computational
indistinguishability: instead of requiring the adversary (in the guessing
phase) to predict whether it receives a pseudorandom output or a string
sampled uniformly at random, we could instead require the adversary to
distinguish a pseudorandom sample from the uniform distribution. For a reason
similar to the revocable PKE case, these two definitions are incomparable. We
leave the investigation of the indistinguishability-based definition to the
future works.

######  Remark 8.6.

Our notion of revocable $\mathsf{PRF}$ security from Definition 8.3 does not
directly imply traditional notion of $\mathsf{pqPRF}$ security181818Although
any revocable $\mathsf{PRF}$ is a weak PRF. Recall that a weak PRF is one
where the adversary receives as input
$(x_{1},y_{1}),\ldots,(x_{\mu},y_{\mu})$, where $x_{i}$s are picked uniformly
at random. The goal of the adversary is to distinguish the two cases: all
$y_{i}$s are pseudorandom or all $y_{i}$s are picked uniformly at random. from
Definition 8.1. The reason is that the definition does not preclude the
possibility of there being an input $x$ (say an all zeroes string) on which,
$\mathsf{PRF}$ outputs $x$ itself (or the first bit of $x$ if the output of
$\mathsf{PRF}$ is a single bit).

Motivated by Remark 8.6, we now introduce the following notion of a _strong_
$\mathsf{rPRF}$.

######  Definition 8.7 (Strong $\mathsf{rPRF}$).

We say that a scheme $({\sf Gen},{\sf PRF},{\sf Eval},\mathsf{Revoke})$ is a
strong revocable pseudorandom function (or, strong $\mathsf{rPRF}$) if the
following two properties hold:

  1. 1.

$({\sf Gen},{\sf PRF},{\sf Eval},\mathsf{Revoke})$ satisfy revocable
$\mathsf{PRF}$ security according to Definition 8.3, and

  2. 2.

$({\sf Gen},\mathsf{PRF})$ satisfy $\mathsf{pqPRF}$ security according to
Definition 8.1.

######  Remark 8.8.

Instantiating pseudorandom functions in the textbook construction of private-
key encryption [Gol06] from revocable pseudorandom functions, we get a
private-key revocable encryption scheme.

We show that the issue raised in Remark 8.6 is not inherent. In fact, we give
a simple generic transformation that allows us to obtain strong
$\mathsf{rPRF}$s by making use of traditional $\mathsf{pqPRF}$s.

######  Claim 8.9 (Generic Transformation for Strong $\mathsf{rPRF}$s).

Let $({\sf Gen},{\sf PRF},{\sf Eval},\mathsf{Revoke})$ be an $\mathsf{rPRF}$
scheme which satisfies revocable $\mathsf{PRF}$ security, and let
$(\overline{{\sf Gen}},\overline{{\sf PRF}})$ be a $\mathsf{pqPRF}$. Then, the
scheme $(\widetilde{{\sf Gen}},\widetilde{{\sf PRF}},\widetilde{{\sf
Eval}},\widetilde{\mathsf{Revoke}})$ is a strong $\mathsf{rPRF}$ which
consists of the following algorithms:

  * •

$\widetilde{{\sf Gen}}(1^{\lambda})$: on input the security parameter
$1^{\lambda}$, first run $(k,\rho_{k},\mathsf{MSK})\leftarrow{\sf
Gen}(1^{\lambda})$ and then output $((K,k),(K,\rho_{k}),\mathsf{MSK})$, where
$K\leftarrow\overline{{\sf Gen}}(1^{\lambda})$ is a $\mathsf{pqPRF}$ key.

  * •

$\widetilde{{\sf PRF}}((K,k),x)$: on input a key $(K,k)$ and string
$x\in\\{0,1\\}^{\ell}$, output $\overline{{\sf
PRF}}(K,x)\oplus\mathsf{PRF}(k,x)$.

  * •

$\widetilde{{\sf Eval}}((K,\rho_{k}),x)$: on input $(K,\rho_{k})$ and
$x\in\\{0,1\\}^{\ell}$, output $\overline{{\sf
PRF}}(K,x)\oplus\mathsf{Eval}(\rho_{k},x)$.

  * •

$\widetilde{\mathsf{Revoke}}(\mathsf{MSK},(K,\sigma))$: on input a master
secret key $\mathsf{MSK}$ and a pair $(K,\rho_{k})$, first discard the key $K$
and then run $\mathsf{Revoke}(\mathsf{MSK},\sigma)$.

###### Proof.

Let us first show that the scheme $(\widetilde{{\sf Gen}},\widetilde{{\sf
PRF}},\widetilde{{\sf Eval}},\widetilde{\mathsf{Revoke}})$ maintains revocable
$\mathsf{PRF}$ security. Suppose that there exists a $\mathsf{QPT}$ adversary
$\mathcal{A}$ and a polynomial $\mu=\mu(\lambda)\in\mathbb{N}$ such that

$\Pr\left[b\leftarrow\mathsf{Expt}^{\mathcal{A},\mu}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]=\frac{1}{2}+\epsilon(\lambda),$

for some function $\epsilon(\lambda)=1/\mathrm{poly}(\lambda)$ and
$\mathsf{Expt}^{\mathcal{A},\mu}$ as defined in Figure 14. We show that this
implies the existence of a $\mathsf{QPT}$ distinguisher $\mathcal{D}$ that
breaks the revocable $\mathsf{PRF}$ security of the scheme $({\sf Gen},{\sf
PRF},{\sf Eval},\mathsf{Revoke})$. The distinguisher $\mathcal{D}$ proceeds as
follows:

  1. 1.

$\mathcal{D}$ receives as input a quantum state $\rho_{k}$, where
$(k,\rho_{k},\mathsf{MSK})\leftarrow{\sf Gen}(1^{\lambda})$ is generated by
the challenger. Then, $\mathcal{D}$ generates a $\mathsf{pqPRF}$ key
$K\leftarrow\overline{{\sf Gen}}(1^{\lambda})$ and sends $(K,\rho_{k})$ to
$\mathcal{A}$.

  2. 2.

When $\mathcal{A}$ returns a state $\rho$, $\mathcal{D}$ forwards it to the
challenger as part of the revocation phase.

  3. 3.

When $\mathcal{D}$ receives the challenge input $(x_{1},\dots,x_{\mu})$ and
$(y_{1},\dots,y_{\mu})$ from the challenger, $\mathcal{D}$ sends
$(x_{1},\dots,x_{\mu})$ and $(\overline{{\sf PRF}}(K,x_{1})\oplus
y_{1},\dots,\overline{{\sf PRF}}(K,x_{\mu})\oplus y_{\mu})$ to $\mathcal{A}$.

  4. 4.

When $\mathcal{A}$ outputs $b^{\prime}$, so does the distinguisher
$\mathcal{D}$.

Note that the simulated challenge distribution above precisely matches the
challenge distribution from the experiment $\mathsf{Expt}^{\mathcal{A},\mu}$
from Figure 14. Therefore, if $\mathcal{A}$ succeeds with inverse polynomial
advantage $\epsilon(\lambda)=1/\mathrm{poly}(\lambda)$, so does $\mathcal{D}$
– thereby breaking the revocable $\mathsf{PRF}$ security of the scheme $({\sf
Gen},{\sf PRF},{\sf Eval},\mathsf{Revoke})$. Consequently, $(\widetilde{{\sf
Gen}},\widetilde{{\sf PRF}},\widetilde{{\sf
Eval}},\widetilde{\mathsf{Revoke}})$ satisfies revocable $\mathsf{PRF}$
security.

To see why $(\widetilde{{\sf Gen}},\widetilde{\mathsf{PRF}})$ satisfy
$\mathsf{pqPRF}$ security according to Definition 8.1, we can follow a similar
argument as above to break the $\mathsf{pqPRF}$ security of $(\overline{{\sf
Gen}},\overline{{\sf PRF}})$. Here, we rely on the fact that the keys
$(k,\rho_{k},\mathsf{MSK})\leftarrow{\sf Gen}(1^{\lambda})$ and
$K\leftarrow\overline{{\sf Gen}}(1^{\lambda})$ are sampled independently from
another.

∎

######  Remark 8.10.

We note that previous works [CLLZ21, KNY21a] do not explicitly require in
their definitions that either secure software leasing or copy-protection of
pseudorandom functions to preserve the pseudorandomness property (although
their constructions could still satisfy the traditional pseudorandomness
property).

###  8.3 Construction

We construct a PRF satisfying 1-revocation security (Definition 8.3).

##### Shift-Hiding Construction.

We construct a _shift-hiding_ function which is loosely inspired by shift-
hiding shiftable functions introduced by Peikert and Shiehian [PS18].

Let $n,m\in\mathbb{N}$, $q\in\mathbb{N}$ be a modulus and let
$\ell=nm\lceil\log q\rceil$. In the following, we consider matrix-valued
functions $F:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$, where $F$
is one of the following functions:

  * •

${\mathcal{Z}}:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$ which,
on input $x\in{\\{0,1\\}}^{\ell}$, outputs an all zeroes matrix
$\mathbf{0}\in\mathbb{Z}_{q}^{n\times m}$, or:

  * •

$H_{r}:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$ which, on input
$x\in\\{0,1\\}^{\ell}$, outputs $\mathbf{M}\in\mathbb{Z}_{q}^{n\times m}$,
where $r\in\\{0,1\\}^{\ell}$ and $x=r\oplus{\sf bindecomp}(\mathbf{M})$, where
$\mathbf{M}\in\mathbb{Z}_{q}^{n\times m}$ and ${\sf bindecomp}(\cdot)$ takes
as input a matrix and outputs a binary string that is obtained by
concatenating the binary decompositions of all the elements in the matrix (in
some order).

We show that there exist $\mathsf{PPT}$ algorithms
$({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ (formally defined in 4) with the
following properties:

  * •

${\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},F)$: on input
$1^{n},1^{m}$, a modulus $q\in\mathbb{N}$, a matrix
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and a function
$F\in\\{\mathcal{Z}\\}\cup\\{H_{r}:r\in\\{0,1\\}^{\ell}\\}$, it outputs a pair
of keys $(pk_{F},sk_{F})$.

  * •

${\mathcal{E}}(pk_{F},x)$: on input $pk_{F}$, $x\in\\{0,1\\}^{\ell}$, it
outputs ${\bf S}_{x}\mathbf{A}+{\bf E}_{x}+F(x)$, where ${\bf
S}_{x}\in\mathbb{Z}_{q}^{n\times n}$ and ${\bf
E}_{x}\in\mathbb{Z}_{q}^{n\times m}$, where $||{\bf
E}_{x}||_{\infty}\leq\left(m\sigma\right)^{2}\cdot(nm\lceil\log(q)\rceil)$.
Moreover, there is an efficient algorithm that recovers ${\bf S}_{x}$ given
$sk_{F}$ and $x$.

We show that our construction of $({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$
satisfies a _shift-hiding property_ ; namely, for any $r\in\\{0,1\\}^{\ell}$,

$\\{pk_{{\mathcal{Z}}}\\}\approx_{c}\\{pk_{H_{r}}\\},$

for any $pk_{F}$ with
$(pk_{F},sk_{F})\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},F)$,
where $\mathbf{A}\xleftarrow{\$}\mathbb{Z}_{q}^{n\times m}$, and
$F\in\\{\mathcal{Z},H_{r}\\}$.

In the construction below, we consider a bijective function
$\phi:[n]\times[m]\times[\lceil\log(q)\rceil]\rightarrow[\ell]$.

######  Construction 4.

Consider the $\mathsf{PPT}$ algorithms
$({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ defined as follows:

  * •

${\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},F)$: on input
$1^{n},1^{m}$, a modulus $q\in\mathbb{N}$, a matrix
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and function
$F\in\\{\mathcal{Z}\\}\cup\\{H_{r}:r\in\\{0,1\\}^{\ell}\\}$, it outputs a pair
of keys $\kappa_{F}=(pk_{F},sk_{F})$ generated as follows:

    1. 1.

For every $i,j\in[n],\tau\in[\lceil\log(q)\rceil]$, define $\\{{\sf
M}_{b}^{(i,j,\tau)}\\}$ as follows:

       * –

If $F={\mathcal{Z}}$, then for every
$i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil]$, let ${\sf
M}_{b}^{(i,j,\tau)}=\mathbf{0}\in\mathbb{Z}_{q}^{n\times n}$,

       * –

If $F=H_{r}$, then for every $i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil]$,
let ${\sf M}_{b}^{(i,j,\tau)}=(b\oplus r_{\phi(i,j,\tau)})\cdot{\bf
I}_{n\times n}$.

    2. 2.

For every $i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil]$, $b\in\\{0,1\\}$,
compute:

$pk_{b}^{(i,j,\tau)}={\bf S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf
E}_{b}^{(i,j,\tau)}+{\sf M}_{b}^{(i,j,\tau)},$
$sk_{b}^{(i,j,\tau)}=\left(\left\\{{\bf S}_{b}^{(i,j,\tau)},{\bf
E}_{b}^{(i,j,\tau)}\right\\}\right),$

where for every $i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil]$,
$b\in\\{0,1\\}$:

       * –

${\bf S}_{b}^{(i,j,\tau)}\leftarrow D_{\mathbb{Z}_{q},\sigma}^{n\times n}$,

       * –

${\bf E}_{b}^{(i,j,\tau)}\leftarrow D_{\mathbb{Z}_{q},\sigma}^{n\times m}$

    3. 3.

Output
$pk_{F}=\left(\mathbf{A},\left\\{pk^{(i,j,\tau)}_{b}\right\\}_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}\end{subarray}}\right)$ and
$sk_{F}=\left\\{sk^{(i,j,\tau)}_{b}\right\\}_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}\end{subarray}}$.

  * •

${\mathcal{E}}(pk_{F},x)$: on input $pk_{F}$ and $x\in{\\{0,1\\}}^{\ell}$,
proceed as follows:

    1. 1.

Parse
$pk_{F}=\left(\mathbf{A}\left\\{pk_{b}^{(i,j,\tau)}\right\\}_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}\end{subarray}}\right)$

    2. 2.

Output $\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}pk_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}$.

######  Claim 8.11 (Correctness).

Let $({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ be the pair of $\mathsf{PPT}$
algorithms in 4. Let
$(pk_{F},sk_{F})\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},F)$
with $F\in\\{\mathcal{Z}\\}\cup\\{H_{r}:r\in\\{0,1\\}^{\ell}\\}$. Then, the
output of ${\mathcal{E}}(pk_{F},x)$ is of the form:

${\mathcal{E}}(pk_{F},x)={\bf S}_{x}\mathbf{A}+{\bf E}_{x}+F(x),$

where ${\bf S}_{x}\in\mathbb{Z}_{q}^{n\times n}$ and ${\bf
E}_{x}\in\mathbb{Z}_{q}^{n\times m}$ with $||{\bf
E}_{x}||_{\infty}\leq\left(m\sigma\right)^{2}\cdot(nm\lceil\log(q)\rceil)$.
Moreover, there is an efficient algorithm that recovers ${\bf S}_{x}$ given
$(pk_{F},sk_{F})$.

###### Proof.

Let
$(pk_{F},sk_{F})\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},F)$.
Parse
$pk_{F}=\left(\mathbf{A},\left\\{pk^{(i,j,\tau)}_{b}\right\\}_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}\end{subarray}}\right)$ and
$sk_{F}=\left\\{sk^{(i,j,\tau)}_{b}\right\\}_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}\end{subarray}}$, where:

$pk_{b}^{(i,j,\tau)}={\bf S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf
E}_{b}^{(i,j,\tau)}+{\sf M}_{b}^{(i,j,\tau)},$
$sk_{b}^{(i,j,\tau)}=\left(\\{{\bf S}_{b}^{(i,j,\tau)},{\bf
E}_{b}^{(i,j,\tau)}\\}\right)$

There are two cases to consider here:

Case 1. $F={\mathcal{Z}}$: in this case, ${\sf M}_{b}^{(i,j,\tau)}=\bf 0$, for
every $i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}$. Thus, the
following holds:

$\displaystyle\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}pk_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}$
$\displaystyle=$
$\displaystyle\underbrace{\left(\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}{\bf
S}_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}\right)}_{{\bf
S}_{x}}\mathbf{A}+\underbrace{\left(\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}{\bf
E}_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}\right)}_{{\bf
E}_{x}}+\left(\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}{\sf
M}_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}\right)$ $\displaystyle=$
$\displaystyle{\bf S}_{x}\mathbf{A}+{\bf E}_{x}+{\mathcal{Z}}(x)$

Moreover, $||{\bf E}_{b}^{(i,j,\tau)}||_{\infty}\leq\left(m\sigma\right)^{2}$
and thus, $||{\bf
E}_{x}||_{\infty}\leq\left(m\sigma\right)^{2}\cdot(nm\lceil\log(q)\rceil)$.

Case 2. $F={H}_{r}$:

$\displaystyle\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}pk_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}$
$\displaystyle=$ $\displaystyle{\bf S}_{x}\mathbf{A}+{\bf
E}_{x}+\left(\sum_{\begin{subarray}{c}i\in[n],j\in[m],\\\
\tau\in[\lceil\log(q)\rceil]\end{subarray}}{\sf
M}_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}\right)$ $\displaystyle=$
$\displaystyle{\bf S}_{x}\mathbf{A}+{\bf E}_{x}+H_{r}(x),$

where ${\bf S}_{x}$ and ${\bf E}_{x}$ are as defined above. The second
equality holds because of the fact that ${\sf
M}_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}$ has the value $(b\oplus
r_{\phi(i,j,\tau)})\cdot 2^{\tau}$ in the $(i,j)^{th}$ position and zero,
everywhere else. Thus, summing up all the ${\sf
M}_{x_{\phi(i,j,\tau)}}^{(i,j,\tau)}$ matrices results in the matrix ${\sf
M}$, where $x\oplus r$ is the binary decomposition of ${\sf M}$.

Finally, it is clear that ${\bf S}_{x}$ can be efficiently recovered from
$sk_{F}$ and $x$. ∎

######  Claim 8.12 (Shift-hiding property).

Assuming the quantum hardness of learning with errors, the pair
$({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ in 4 has the property that

$\\{pk_{{\mathcal{Z}}}\\}\approx_{c}\\{pk_{H_{r}}\\},$

for any $pk_{F}$ with
$(pk_{F},sk_{F})\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},F)$,
where $\mathbf{A}\xleftarrow{\$}\mathbb{Z}_{q}^{n\times m}$,
$r\in\\{0,1\\}^{\ell}$ and $F\in\\{\mathcal{Z},H_{r}\\}$.

###### Proof.

For every $i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil]$, $b\in\\{0,1\\}$, let
${\sf M}_{b}^{(i,j,\tau)}=(b\oplus r_{\phi(i,j,\tau)})\cdot{\bf I}_{n\times
n}$. Then from the quantum hardness of learning with errors, the following
holds for every $(i,j,\tau)$ and $b\in\\{0,1\\}$:

$\\{{\bf S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf
E}_{b}^{(i,j,\tau)}\\}\approx_{c}\\{{\bf S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf
E}_{b}^{(i,j,\tau)}+{\sf M}_{b}^{(i,j,\tau)}\\}$

Since $\\{{\bf S}_{b}^{(i,j,\tau)}\\}$ and $\\{{\bf E}_{b}^{(i,j,\tau)}\\}$
are sampled independently for every $(i,j,\tau)$ and $b\in\\{0,1\\}$, the
proof of the claim follows. ∎

######  Remark 8.13.

When consider the all-zeroes function ${\mathcal{Z}}$, we drop the notation
from the parameters. For instance, we denote $pk_{{\mathcal{Z}}}$ to be simply
$pk$.

##### Construction.

We consider the following parameters which are relevant to our ${\sf PRF}$
construction. Let $n,m\in\mathbb{N}$ and let $q\in\mathbb{N}$ be a modulus
with $q=2^{o(n)}$. Let $\ell=nm\lceil\log q\rceil$. Let
$\sigma\in(\sqrt{2m},q/\sqrt{2m})$ and let $p\ll q$ be a sufficiently large
rounding parameter with

$n\cdot m^{3.5}\sigma^{3}\lceil\log q\rceil=(q/p)\cdot 2^{-o(n)}.$

We describe our construction below.

######  Construction 5 (Revocable ${\sf PRF}$ scheme).

Let $n\in\mathbb{N}$ be the security parameter and $m\in\mathbb{N}$. Let
$q\geq 2$ be a prime and let $\sigma>0$ be a parameter. Let
$({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ be the procedure in 4. Our
revocable ${\sf PRF}$ scheme is defined as follows:

  * •

${\sf Gen}(1^{\lambda})$: This is the following key generation procedure:

    1. 1.

Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.

    2. 2.

Compute
$\kappa_{{\mathcal{Z}}}\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},{\mathcal{Z}})$,
where ${\mathcal{Z}}:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$ is
the such that ${\mathcal{Z}}(x)$ outputs an all zero matrix for every
$x\in\\{0,1\\}^{\ell}$. Parse $\kappa_{{\mathcal{Z}}}$ as $(pk,sk)$.

    3. 3.

Generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y}\in\mathbb{Z}_{q}^{n})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with

$\ket{\psi_{\mathbf{y}}}\,\,=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\,\ket{\mathbf{x}}.$

Output $k=(pk,sk,\mathbf{y})$, $\rho_{k}=(pk,\ket{\psi_{\mathbf{y}}})$ and
$\mathsf{MSK}=\mathsf{td}_{\mathbf{A}}$.

  * •

${\sf PRF}(k,x)$: this is the following procedure:

    1. 1.

Parse the key $k$ as a tuple $(pk,sk),\mathbf{y})$.

    2. 2.

Output $\lfloor{\bf S}_{x}\mathbf{y}\rceil_{p}$. Here, ${\bf
S}_{x}\in\mathbb{Z}_{q}^{n\times n}$ is a matrix that can be efficiently
recovered from $sk$ as stated in 8.11.

  * •

${\sf Eval}(\rho_{k},x)$: this is the following evaluation algorithm:

    1. 1.

Parse $\rho_{k}$ as $(pk,\rho)$.

    2. 2.

Compute ${\sf M}_{x}\leftarrow{\mathcal{E}}(pk,x)$.

    3. 3.

Measure the register ${\sf Aux}$ of the state $U(\rho\otimes|0\rangle\langle
0|_{\sf Aux})U^{\dagger}$. Denote the resulting outcome to be ${\bf z}$, where
$U$ is defined as follows:

$U\ket{\mathbf{t}}\ket{0}_{\sf Aux}\rightarrow\ket{\mathbf{t}}\ket{\lfloor{\sf
M}_{x}\cdot\mathbf{t}\rceil_{p}}_{\sf Aux}$

    4. 4.

Output ${\bf z}$.

  * •

$\mathsf{Revoke}(\mathsf{MSK},\rho)$: given as input the trapdoor
$\mathsf{td}_{\mathbf{A}}\leftarrow\mathsf{MSK}$, apply the projective
measurement
$\\{\ket{\psi_{\mathbf{y}}}\\!\bra{\psi_{\mathbf{y}}},I-\ket{\psi_{\mathbf{y}}}\\!\bra{\psi_{\mathbf{y}}}\\}$
onto the state $\rho$ using the procedure
$\mathsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$
in Algorithm 2. Output $\mathsf{Valid}$ if the measurement is successful, and
$\mathsf{Invalid}$ otherwise.

######  Lemma 8.14.

The above scheme satisfies correctness for our choice of parameters.

###### Proof.

The correctness of revocation follows immediately from the correctness of
$\mathsf{QSampGauss}$ in Algorithm 2, which we showed in Theorem 3.2. Next, we
show the correctness of evaluation. Let
$\kappa_{{\mathcal{Z}}}\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},{\mathcal{Z}})$
with $\kappa_{{\mathcal{Z}}}=(\mathsf{PK},\mathsf{SK})$. From 8.11, we have
for any $x\in{\\{0,1\\}}^{\ell}$:

${\mathcal{E}}(\mathsf{PK},x)={\bf S}_{x}\mathbf{A}+{\bf E}_{x}\
(\mathrm{mod}\ q),$

where ${\bf S}_{x}\in\mathbb{Z}_{q}^{n\times n}$ and ${\bf
E}_{x}\in\mathbb{Z}_{q}^{n\times m}$ with $||{\bf
E}_{x}||_{\infty}\leq\left(m\sigma\right)^{2}\cdot(nm\lceil\log(q)\rceil)$.
Recall that $\mathsf{GenGauss}(\mathbf{A},\sigma)$ outputs a state
$\ket{\psi_{\mathbf{y}}}$ that is overwhelmingly supported on vectors
$\mathbf{t}\in\mathbb{Z}_{q}^{m}$ such that
$\|\mathbf{t}\|\leq\sigma\sqrt{\frac{m}{2}}$ with
$\mathbf{A}\cdot\mathbf{t}=\mathbf{y}\ (\mathrm{mod}\ q)$. Therefore, we have
for any input $x\in{\\{0,1\\}}^{\ell}$:

$\left\lfloor{\mathcal{E}}(\mathsf{PK},x)\cdot\mathbf{t}\right\rceil_{p}=\left\lfloor{\bf
S}_{x}\mathbf{A}\cdot\mathbf{t}+{\bf
E}_{x}\cdot\mathbf{t}\right\rceil_{p}=\left\lfloor{\bf
S}_{x}\cdot\mathbf{y}+{\bf
E}_{x}\cdot\mathbf{t}\right\rceil_{p}=\left\lfloor{\bf
S}_{x}\cdot\mathbf{y}\right\rceil_{p},$

where the last equality follows from the fact that

$\|\mathbf{E}_{x}\cdot\mathbf{t}\|_{\infty}\leq\|\mathbf{E}_{x}\|_{\infty}\cdot\|\mathbf{t}\|_{\infty}\leq\left(m\sigma\right)^{2}\cdot(nm\lceil\log(q)\rceil)\cdot\sigma\sqrt{m/2}.$

and $n\cdot m^{3.5}\sigma^{3}\lceil\log q\rceil=(q/p)\cdot 2^{-o(n)}$ for our
choice of parameters. ∎

######  Theorem 8.15.

Let $n\in\mathbb{N}$ and $q$ be a prime modulus with $q=2^{o(n)}$ and $m\geq
2n\log q$, each parameterized by $\lambda\in\mathbb{N}$. Let
$\ell=nm\lceil\log q\rceil$. Let $\sigma\in(\sqrt{2m},q/\sqrt{2m})$ and
$\alpha\in(0,1)$ be any noise ratio with $1/\alpha=\sigma\cdot 2^{o(n)}$, and
let $p\ll q$ be a sufficiently large rounding parameter with

$n\cdot m^{3.5}\sigma^{3}\lceil\log q\rceil=(q/p)\cdot 2^{-o(n)}.$

Then, assuming the quantum subexponential hardness of
$\mathsf{LWE}_{n,q,\alpha q}^{m}$ and
$\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$, our revocable $\mathsf{PRF}$ scheme
$({\sf Gen},{\sf PRF},{\sf Eval},\mathsf{Revoke})$defined in 5 satisfies
1-revocation security according to Definition 8.3.

###### Proof.

Let $\mathcal{A}$ be a $\mathsf{QPT}$ adversary and suppose that

$\Pr\left[b\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]=\frac{1}{2}+\epsilon(\lambda),$

for some $\varepsilon(\lambda)$ with respect to experiment
$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$ in Figure 15. Let us now show
that $\varepsilon(\lambda)$ is negligible.

$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$: Initialization Phase: • The
challenger runs the procedure $\mathsf{Gen}(1^{\lambda})$: 1. Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Generate $\mathbf{A}_{N}\in\mathbb{Z}_{q}^{(n+m)\times m}$ with
$\overline{\mathbf{A}_{N}}\xleftarrow{\$}\mathbb{Z}_{q}^{m\times m}$ and
$\underline{\mathbf{A}_{N}}=\mathbf{A}$. 3. Compute
$\kappa_{{\mathcal{Z}}}\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},1^{q},\mathbf{A}_{N},{\mathcal{Z}})$,
where ${\mathcal{K}}{\mathcal{G}}$ is as defined in 4 and
${\mathcal{Z}}:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$ is such
that ${\mathcal{Z}}(x)$ outputs an all zero matrix for every
$x\in\\{0,1\\}^{\ell}$. Parse $\kappa_{{\mathcal{Z}}}$ as $(pk,sk)$. 4.
Generate
$(\ket{\psi_{\mathbf{y}}},\mathbf{y}\in\mathbb{Z}_{q}^{n})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with |ψ_y⟩ = ∑_x ∈Z_q^mAx = y (mod q)ρ_σ(x) |x⟩.  5. Let
$k=(pk,sk,\mathbf{y})$, $\rho_{k}=(pk,\ket{\psi_{\mathbf{y}}})$ and
$\mathsf{MSK}=\mathsf{td}_{\mathbf{A}}$. • The challenger sends
$\rho_{k}=(pk,\ket{\psi_{\mathbf{y}}})$ to $\mathcal{A}$. Revocation Phase: •
The challenger sends the message REVOKE to $\mathcal{A}$. • $\mathcal{A}$
generates a (possibly entangled) bipartite state
$\rho_{R,\mathbf{\textsc{aux}}}$ in systems
$\mathcal{H}_{R}\otimes\mathcal{H}_{\textsc{Aux}}$ with
$\mathcal{H}_{R}=\mathcal{H}_{q}^{m}$, returns system $R$ and holds onto the
auxiliary system Aux. • The challenger runs
$\mathsf{Revoke}(\mathsf{MSK},\rho_{R})$, where $\rho_{R}$ is the reduced
state in system $R$. If the outcome is $\mathsf{Invalid}$, the challenger
aborts. Guessing Phase: • The challenger samples
$x\leftarrow{\\{0,1\\}}^{\ell}$ and sends $(x,y)$ to $\mathcal{A}$, where – If
$b=0$: compute ${\bf S}_{x}$ from $sk$ as in 8.11. Set $y=\lfloor{\bf
S}_{x}\mathbf{y}\rceil_{p}$. – If $b=1$: sample $y\leftarrow\\{0,1\\}^{n}$. •
$\mathcal{A}$ outputs a string $b^{\prime}$ and wins if $b^{\prime}=b$.
---
Figure 15: The revocable ${\sf PRF}$ experiment
$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)$ for 5.

Suppose for the sake of contradition that
$\epsilon(\lambda)=1/\mathrm{poly}(\lambda)$. Let us now introduce a sequence
of hybrid experiments which will be relevant for the remainder of the proof.

Let
$\mathsf{RevDual}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke})$
be the $n$-bit key-revocable Dual-Regev scheme from 2. Fix $\mu=0^{n}$, where
$\mu$ is the challenge message in the dual-Regev encryption security.

$\mathsf{H}_{0}$: This is $\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},0)$ in
Figure 15.

$\mathsf{H}_{1}$: This is the same experiment as
$\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},0)$, except for the following
changes:

  * •

Sample a random string $r\leftarrow\\{0,1\\}^{\ell}$.

  * •

Run the procedure $\mathsf{RevDual}.\mathsf{KeyGen}(1^{\lambda})$ instead of
$\mathsf{GenTrap}(1^{n},1^{m},q)$ and $\mathsf{GenGauss}(\mathbf{A},\sigma)$
to obtain $(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathbf{y}\in\mathbb{Z}_{q}^{n},\mathsf{MSK},\rho_{\mathsf{SK}})$.

  * •

Compute
$(\mathsf{CT}_{1},\mathsf{CT}_{2})\leftarrow\mathsf{RevDual}.\mathsf{Enc}(\mathbf{A},\mathbf{y},\mu)$,
where $\mathsf{CT}_{1}\in\mathbb{Z}_{q}^{n\times m}$ and
$\mathsf{CT}_{2}\in\mathbb{Z}_{q}^{n}$.

  * •

Set $x=r\oplus{\sf bindecomp}(\mathsf{CT}_{1})$.

The rest of the hybrid is the same as before.

Note that Hybrids $\mathsf{H}_{0}$ and $\mathsf{H}_{1}$ are identically
distributed.

$\mathsf{H}_{2}$: This is the same experiment as before, except that the
challenger now uses an alternative key-generation algorithm:

  * •

As before, run the procedure $\mathsf{RevDual}.\mathsf{KeyGen}(1^{\lambda})$
instead of $\mathsf{GenTrap}(1^{n},1^{m},q)$ and
$\mathsf{GenGauss}(\mathbf{A},\sigma)$ to obtain
$(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathbf{y}\in\mathbb{Z}_{q}^{n},\mathsf{MSK},\rho_{\mathsf{SK}})$. Sample
$r\leftarrow\\{0,1\\}^{\ell}$.

  * •

Let $H_{r}:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$ be as
defined in the beginning of Section 8.3.

  * •

Run the alternate algorithm
$\kappa_{H}\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},1^{q},\mathbf{A},H_{r})$
instead of
$\kappa_{{\mathcal{Z}}}\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},1^{q},\mathbf{A},{\mathcal{Z}})$.

  * •

Compute the ciphertext
$(\mathsf{CT}^{*}_{1},\mathsf{CT}^{*}_{2})\leftarrow\mathsf{RevDual}.\mathsf{Enc}(\mathbf{A},\mathbf{y},\mu)$,
where $\mathsf{CT}^{*}_{1}\in\mathbb{Z}_{q}^{n\times m}$. Then, set
$x^{*}=r\oplus{\sf bindecomp}(\mathsf{CT}_{1}^{*})$. Send $x^{*}$ to the
adversary in the guessing phase.

$\mathsf{H}_{3}$: This is the same hybrid as before, except that we choose
$\mathsf{CT}_{1}^{*}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}$ and
$\mathsf{CT}_{2}^{*}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$.

$\mathsf{H}_{4}$: This is the $\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},1)$ in
Figure 15.

Note that hybrids $\mathsf{H}_{3}$ and $\mathsf{H}_{4}$ are identically
distributed.

Suppose that the following holds:

$\displaystyle\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{1}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{2}^{\mathcal{A}}(1^{\lambda})]$
$\displaystyle=\frac{1}{2}+\delta_{1}(\lambda),\,\,\,\text{ and }$
$\displaystyle\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{2}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{3}^{\mathcal{A}}(1^{\lambda})]$
$\displaystyle=\frac{1}{2}+\delta_{2}(\lambda)$

for some functions $\delta_{1}(\lambda)$ and $\delta_{2}(\lambda)$. We claim
that either $\delta_{1}(\lambda)\geq 1/\mathrm{poly}(\lambda)$ or
$\delta_{2}(\lambda)\geq 1/\mathrm{poly}(\lambda)$ must hold. This is easily
seen as follows. By taking the sum of the two expressions above, we get

$\displaystyle\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{1}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{2}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{2}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{3}^{\mathcal{A}}(1^{\lambda})]$
$\displaystyle=\frac{1}{2}+\delta_{1}(\lambda)+\frac{1}{2}+\delta_{2}(\lambda).$

Note that we have the identity ${\sf
Pr}[0\leftarrow\mathsf{H}_{2}^{\mathcal{A}}(1^{\lambda})]+{\sf
Pr}[1\leftarrow\mathsf{H}_{2}^{\mathcal{A}}(1^{\lambda})]=1$. Moreover,
because the hybrids $\mathsf{H}_{0}$ and $\mathsf{H}_{1}$, as well as hybrids
$\mathsf{H}_{3}$ and $\mathsf{H}_{4}$, are identically distributed, we have

$\displaystyle{\sf
Pr}[0\leftarrow\mathsf{H}_{1}^{\mathcal{A}}(1^{\lambda})]={\sf
Pr}[0\leftarrow\mathsf{H}_{0}^{\mathcal{A}}(1^{\lambda})]={\sf
Pr}[0\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},0)]\quad\text{ and }$
$\displaystyle{\sf
Pr}[1\leftarrow\mathsf{H}_{3}^{\mathcal{A}}(1^{\lambda})]={\sf
Pr}[1\leftarrow\mathsf{H}_{4}^{\mathcal{A}}(1^{\lambda})]={\sf
Pr}[1\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},1)].$

Plugging the identities above into the equation from before, we get

$\displaystyle\frac{1}{2}+\varepsilon(\lambda)$ $\displaystyle=\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},0)]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},1)]$
$\displaystyle=\frac{1}{2}+\delta_{1}(\lambda)+\delta_{2}(\lambda).$

In other words, we get
$\delta_{1}(\lambda)+\delta_{2}(\lambda)=\epsilon(\lambda)$, which implies
that either $\delta_{1}(\lambda)\geq 1/\mathrm{poly}(\lambda)$ or
$\delta_{2}(\lambda)\geq 1/\mathrm{poly}(\lambda)$. To complete the proof, we
show that both $\delta_{1}(\lambda)$ and $\delta_{2}(\lambda)$ are negligible,
which yields a contradiction to our assumption that
$\varepsilon=1/\mathrm{poly}(\lambda)$.

######  Claim 8.16.

By the shift-hiding property191919Technically, we are invoking the $1$-bit
indistinguishability variant of the shift-hiding property of
$({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ in 8.12, which is implied by the
regular indistinguishability notion. of
$({\mathcal{K}}{\mathcal{G}},{\mathcal{E}})$ in 8.12, we have
$\delta_{1}(\lambda)\leq\mathsf{negl}(\lambda)$.

###### Proof.

We first define alternate hybrids $\widetilde{\mathsf{H}_{1}}$ and
$\widetilde{\mathsf{H}_{2}}$ as follows:

  * •

$\widetilde{\mathsf{H}_{1}}$ is the same as $\mathsf{H}_{1}$ except that
$\mathsf{Revoke}$ is not applied on the returned state,

  * •

$\widetilde{\mathsf{H}_{2}}$ is the same as $\mathsf{H}_{2}$ except that
$\mathsf{Revoke}$ is not applied on the returned state.

Since ignoring $\mathsf{Revoke}$ only increases the success probability of the
adversary, the following holds:

$\frac{1}{2}{\sf
Pr}[0\leftarrow\widetilde{\mathsf{H}_{1}}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\widetilde{\mathsf{H}_{2}}^{\mathcal{A}}(1^{\lambda})]\geq\frac{1}{2}+\delta_{1}(\lambda)$

We now argue that $\delta_{1}(\lambda)\leq\mathsf{negl}(\lambda)$.

Suppose not. We design a reduction ${\mathcal{B}}$ that violates the shift-
hiding property as follows.

  * •

Sample $r\xleftarrow{\$}\\{0,1\\}^{\ell}$. Send $({\mathcal{Z}},H_{r})$ to the
challenger.

  * •

The challenger responds with
$pk=\left(\mathbf{A},\left\\{\mathsf{CT}_{b}^{(i,j,\tau)}\right\\}_{\begin{subarray}{c}i\in[n],j\in[m]\\\
\tau\in[\lceil\log(q)\rceil],b\in\\{0,1\\}\end{subarray}}\right)$

  * •

Compute
$(\ket{\psi_{\mathbf{y}}},\mathbf{y}\in\mathbb{Z}_{q}^{n})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
from the challenger.

  * •

Set $\rho_{k}=(pk,\rho)$.

  * •

Compute
$(\mathsf{CT}_{1},\mathsf{CT}_{2})\leftarrow\mathsf{RevDual}.\mathsf{Enc}(\mathbf{A},\mathbf{y},\mu)$,
where $\mathsf{CT}_{1}\in\mathbb{Z}_{q}^{n\times m}$ and
$\mathsf{CT}_{2}\in\mathbb{Z}_{q}^{n}$. Set $x^{*}=r\oplus{\sf
bindecomp}(\mathsf{CT}_{1})$.

  * •

Compute ${\sf Eval}(\rho_{k},x^{*})$ to obtain $y^{*}$ while recovering
$\rho^{*}_{k}$ (using almost as good as new lemma [Aar09]) such that ${\sf
TD}(\rho^{*}_{k},\rho_{k})\leq\mathsf{negl}(\lambda)$.

  * •

Send $\rho_{k}^{*}$ to $\mathcal{A}$.

  * •

$\mathcal{A}$ computes a state on two registers $R$ and aux. It returns the
state on the register $R$.

  * •

$\mathcal{A}$, on input the register aux and $(x^{*},y^{*})$, outputs a bit
$b^{\prime}$.

  * •

Output $b^{\prime}$.

If $pk$ is generated using
${\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},{\mathcal{Z}})$ then we
are in the hybrid, $\widetilde{\mathsf{H}_{1}}^{\mathcal{A}}$. If $pk$ is
generated using ${\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},q,\mathbf{A},H_{r})$
then we are in the hybrid, $\widetilde{\mathsf{H}_{2}}^{\mathcal{A}}$. Thus,
we violate the shift-hiding property with advantage $\delta_{1}(\lambda)$.
This completes the proof.

∎

Next, we invoke the security of the $n$-bit variant of our key-revocable Dual-
Regev scheme which follows from 5.8 and Theorem 6.1.

######  Claim 8.17.

By the security of our $n$-bit key-revocable Dual-Regev encryption scheme
which is based on the transformation in 1, we have that
$\delta_{2}(\lambda)\leq\mathsf{negl}(\lambda)$.

###### Proof.

Suppose $\delta_{2}(\lambda)=1/\mathrm{poly}(\lambda)$. Using $\mathcal{A}$,
we design a reduction ${\mathcal{B}}$ that violates the revocation security of
1, thus contradicting Theorem 6.1.

The reduction ${\mathcal{B}}$ proceeds as follows.

  * •

First, it receives as input $\mathbf{A},\mathbf{y}$ and a quantum state

$\ket{\psi_{\mathbf{y}}}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}.$

  * •

The reduction generates a quantum state $\rho_{k}$ as follows:

    * –

Sample a random string
$r\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}{\\{0,1\\}}^{\ell}$.

    * –

Let $H_{r}:\\{0,1\\}^{\ell}\rightarrow\mathbb{Z}_{q}^{n\times m}$ be as
defined in the beginning of Section 8.3.

    * –

Run the algorithm
$\kappa_{H}\leftarrow{\mathcal{K}}{\mathcal{G}}(1^{n},1^{m},1^{q},\mathbf{A},H_{r})$
and parse $\kappa_{H}$ as $(pk,sk)$.

    * –

Set $\rho_{k}=(pk,\ket{\psi_{\mathbf{y}}})$.

Send $\rho_{k}$ to $\mathcal{A}$.

  * •

$\mathcal{A}$ outputs a state on two registers $R$ and aux. The register $R$
is returned. The reduction forwards the register $R$ to the challenger.

  * •

The reduction then gets the challenge ciphertext
$\mathsf{CT}=[\mathsf{CT}_{1},\mathsf{CT}_{2}]^{\intercal}\in\mathbb{Z}_{q}^{n\times
m}\times\mathbb{Z}_{q}^{n}$. The reduction then sets

$x^{*}=r\oplus{\sf bindecomp}(\mathsf{CT}_{1})$

and sends $x^{*}$ to $\mathcal{A}$ in the guessing phase, together with
$y=\lfloor{\bf S}_{x^{*}}\mathbf{y}+\mathsf{CT}_{2}\rceil_{p}$ which is
computed using the secret key $\mathsf{SK}$ (c.f. 8.11).

  * •

$\mathcal{A}$ outputs a bit $b^{\prime}$. ${\mathcal{B}}$ outputs
$b^{\prime}$.

There are two cases to consider here. In the first case, we have
$\mathsf{CT}=[\mathsf{CT}_{1},\mathsf{CT}_{2}]^{\intercal}\in\mathbb{Z}_{q}^{n\times
m}\times\mathbb{Z}_{q}^{n}$ is a Dual-Regev ciphertext. Here, $y=\lfloor{\bf
S}_{x^{*}}\mathbf{y}+\mathsf{CT}_{2}\rceil_{p}$ precisely corresponds to the
output of the pseudorandom function on $\rho_{k}$ and $x$. In the second case,
we have
$\mathsf{CT}=[\mathsf{CT}_{1},\mathsf{CT}_{2}]^{\intercal}\in\mathbb{Z}_{q}^{n\times
m}\times\mathbb{Z}_{q}^{n}$, where
$\mathsf{CT}_{1}\xleftarrow{\$}\mathbb{Z}_{q}^{n\times m}$ and
$\mathsf{CT}_{2}\xleftarrow{\$}\mathbb{Z}_{q}^{m}$. Here, $y=\lfloor{\bf
S}_{x^{*}}\mathbf{y}+\mathsf{CT}_{2}\rceil_{p}$ is (negligibly close) to a
uniform distribution on $\mathbb{Z}_{p}^{m}$.

Thus, the first case precisely corresponds to $\mathsf{H}_{2}$ and the second
case corresponds to $\mathsf{H}_{3}$. As a result, ${\mathcal{B}}$ violates
the revocation security of 1 with advantage $\delta_{2}(\lambda)$. This
completes the proof. ∎

Putting everything together, we have shown that

$\Pr\left[b\leftarrow\mathsf{Expt}^{\mathcal{A}}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]\leq\frac{1}{2}+\mathsf{negl}(\lambda).$

∎

## References

  * [Aar09] Scott Aaronson  “Quantum copy-protection and quantum money”  In _2009 24th Annual IEEE Conference on Computational Complexity_ , 2009, pp. 229–242  IEEE
  * [Aar16] Scott Aaronson  “The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes”, 2016  arXiv:1607.05256 [quant-ph]
  * [AC02] Mark Adcock and Richard Cleve  “A quantum Goldreich-Levin theorem with cryptographic applications”  In _STACS 2002_ Springer, 2002, pp. 323–334  DOI: 10.1007/3-540-45841-7_26
  * [Ajt96] Miklós Ajtai  “Generating Hard Instances of Lattice Problems (Extended Abstract)”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996_ ACM, 1996, pp. 99–108  DOI: 10.1145/237814.237838
  * [AK21] Prabhanjan Ananth and Fatih Kaleoglu  “Unclonable encryption, revisited”  In _Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part I_ , 2021, pp. 299–329  Springer
  * [AK22] Prabhanjan Ananth and Fatih Kaleoglu  “A Note on Copy-Protection from Random Oracles”  In _arXiv preprint arXiv:2208.12884_ , 2022
  * [AKL+22] Prabhanjan Ananth et al.  “On the Feasibility of Unclonable Encryption, and More” https://eprint.iacr.org/2022/884, Cryptology ePrint Archive, Paper 2022/884, 2022  URL: https://eprint.iacr.org/2022/884
  * [AKL23] Prabhanjan Ananth, Fatih Kaleoglu and Qipeng Liu  “Cloning Games: A General Framework for Unclonable Primitives”  In _arXiv preprint arXiv:2302.01874_ , 2023
  * [AL21] Prabhanjan Ananth and Rolando L La Placa  “Secure Software Leasing”  In _Eurocrypt_ , 2021
  * [ALL+21] Scott Aaronson et al.  “New approaches for quantum copy-protection”  In _Annual International Cryptology Conference_ , 2021, pp. 526–555  Springer
  * [Ban93] W. Banaszczyk  “New bounds in some transference theorems in the geometry of numbers.”  In _Mathematische Annalen_ 296.4, 1993, pp. 625–636  URL: http://eudml.org/doc/165105
  * [BB84] C.. Bennett and G. Brassard  “Quantum cryptography: Public key distribution and coin tossing”  In _Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing_ , 1984, pp. 175
  * [BBK22] Nir Bitansky, Zvika Brakerski and Yael Tauman Kalai  “Constructive Post-Quantum Reductions”  arXiv, 2022  DOI: 10.48550/ARXIV.2203.02314
  * [BCM+21] Zvika Brakerski et al.  “A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device”, 2021  arXiv:1804.00640 [quant-ph]
  * [BDGM20] Zvika Brakerski, Nico Döttling, Sanjam Garg and Giulio Malavolta  “Factoring and pairings are not necessary for io: Circular-secure lwe suffices”  In _Cryptology ePrint Archive_ , 2020
  * [BGG+14] Dan Boneh et al.  “Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits” https://eprint.iacr.org/2014/356, Cryptology ePrint Archive, Paper 2014/356, 2014  URL: https://eprint.iacr.org/2014/356
  * [BGI+12] Boaz Barak et al.  “On the (Im)Possibility of Obfuscating Programs”  In _J. ACM_ 59.2 New York, NY, USA: Association for Computing Machinery, 2012  DOI: 10.1145/2160158.2160159
  * [BI20] Anne Broadbent and Rabib Islam  “Quantum Encryption with Certified Deletion”  In _Lecture Notes in Computer Science_ Springer International Publishing, 2020, pp. 92–122  DOI: 10.1007/978-3-030-64381-2_4
  * [BI20a] Anne Broadbent and Rabib Islam  “Quantum encryption with certified deletion”  In _Theory of Cryptography Conference_ , 2020, pp. 92–122  Springer
  * [BJL+21] Anne Broadbent et al.  “Secure software leasing without assumptions”  In _Theory of Cryptography Conference_ , 2021, pp. 90–120  Springer
  * [BK22] James Bartusek and Dakshita Khurana  “Cryptography with Certified Deletion”  arXiv, 2022  DOI: 10.48550/ARXIV.2207.01754
  * [BL20] Anne Broadbent and Sébastien Lord  “Uncloneable Quantum Encryption via Oracles”  In _15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)_ 158, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 4:1–4:22  DOI: 10.4230/LIPIcs.TQC.2020.4
  * [BMSZ16] Saikrishna Badrinarayanan, Eric Miles, Amit Sahai and Mark Zhandry  “Post-zeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits”  In _Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II_ , 2016, pp. 764–791
  * [BPR12] Abhishek Banerjee, Chris Peikert and Alon Rosen  “Pseudorandom functions and lattices”  In _Advances in Cryptology–EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings 31_ , 2012, pp. 719–737  Springer
  * [Bra18] Zvika Brakerski  “Quantum FHE (Almost) As Secure As Classical” https://ia.cr/2018/338, Cryptology ePrint Archive, Report 2018/338, 2018
  * [BV14] Zvika Brakerski and Vinod Vaikuntanathan  “Efficient fully homomorphic encryption from (standard) $\mathsf{LWE}$”  In _SIAM Journal on Computing_ 43.2, 2014, pp. 831–871  DOI: 10.1137/120868669
  * [BV14a] Zvika Brakerski and Vinod Vaikuntanathan  “Efficient fully homomorphic encryption from (standard) LWE”  In _SIAM Journal on computing_ 43.2 SIAM, 2014, pp. 831–871
  * [CFGN96] Ran Canetti, Uri Feige, Oded Goldreich and Moni Naor  “Adaptively Secure Multi-Party Computation”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96  Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 639–648  DOI: 10.1145/237814.238015
  * [CJJ22] Arka Rai Choudhuri, Abhihsek Jain and Zhengzhong Jin  “Snargs for P from LWE”  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 68–79  IEEE
  * [CLLZ21] Andrea Coladangelo, Jiahui Liu, Qipeng Liu and Mark Zhandry  “Hidden cosets and applications to unclonable cryptography”  In _Annual International Cryptology Conference_ , 2021, pp. 556–584  Springer
  * [CMP20] Andrea Coladangelo, Christian Majenz and Alexander Poremba  “Quantum copy-protection of compute-and-compare programs in the quantum random oracle model”, 2020  arXiv:2009.13865 [quant-ph]
  * [CV22] Eric Culf and Thomas Vidick  “A monogamy-of-entanglement game for subspace coset states”  In _Quantum_ 6 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp. 791
  * [CVW18] Yilei Chen, Vinod Vaikuntanathan and Hoeteck Wee  “GGH15 beyond permutation branching programs: proofs, attacks, and candidates”  In _Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part II 38_ , 2018, pp. 577–607  Springer
  * [DGT+10] Yevgeniy Dodis et al.  “Public-Key Encryption Schemes with Auxiliary Inputs”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 361–381
  * [Die82] DGBJ Dieks  “Communication by EPR devices”  In _Physics Letters A_ 92.6 Elsevier, 1982, pp. 271–272
  * [DQV+21] Lalita Devadas et al.  “Succinct LWE sampling, random polynomials, and obfuscation”  In _Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part II 19_ , 2021, pp. 256–287  Springer
  * [Gao15] Jingliang Gao  “Quantum union bounds for sequential projective measurements”  In _Physical Review A_ 92.5 APS, 2015, pp. 052331
  * [Gen09] Craig Gentry  “Fully homomorphic encryption using ideal lattices”  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , 2009, pp. 169–178
  * [GGM86] Oded Goldreich, Shafi Goldwasser and Silvio Micali  “How to construct random functions”  In _Journal of the ACM_ 33.4 New York, NY, USA: ACM, 1986, pp. 792–807  DOI: 10.1145/6490.6503
  * [Gol06] Oded Goldreich  “Foundations of Cryptography: Volume 1, Basic Tools”  Cambridge University Press, 2006
  * [Got02] Daniel Gottesman  “Uncloneable encryption”  In _arXiv preprint quant-ph/0210062_ , 2002
  * [GP21] Romain Gay and Rafael Pass  “Indistinguishability obfuscation from circular security”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 736–749
  * [GPV07] Craig Gentry, Chris Peikert and Vinod Vaikuntanathan  “Trapdoors for Hard Lattices and New Cryptographic Constructions” https://eprint.iacr.org/2007/432, Cryptology ePrint Archive, Report 2007/432, 2007
  * [GR02] Lov K. Grover and Terry Rudolph  “Creating superpositions that correspond to efficiently integrable probability distributions”  In _arXiv: Quantum Physics_ , 2002
  * [GSW13] Craig Gentry, Amit Sahai and Brent Waters  “Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based” https://ia.cr/2013/340, Cryptology ePrint Archive, Report 2013/340, 2013
  * [GZ20] Marios Georgiou and Mark Zhandry  “Unclonable decryption keys”  In _Cryptology ePrint Archive_ , 2020
  * [HH00] L. Hales and S. Hallgren  “An improved quantum Fourier transform algorithm and applications”  In _Proceedings 41st Annual Symposium on Foundations of Computer Science_ , 2000, pp. 515–525  DOI: 10.1109/SFCS.2000.892139
  * [HMNY21] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki and Takashi Yamakawa  “Certified Everlasting Zero-Knowledge Proof for QMA”, 2021  arXiv:2109.14163 [quant-ph]
  * [HMNY21a] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki and Takashi Yamakawa  “Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication”, 2021  arXiv:2105.05393 [quant-ph]
  * [Int15] Intercept  “How Spies Stole The Keys To The Encryption Castle”  In _https://theintercept.com/2015/02/19/great-sim-heist/_ , 2015
  * [JL00] Stanisław Jarecki and Anna Lysyanskaya  “Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures”  In _Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques_ , EUROCRYPT’00  Bruges, Belgium: Springer-Verlag, 2000, pp. 221–242
  * [JLS21] Aayush Jain, Huijia Lin and Amit Sahai  “Indistinguishability obfuscation from well-founded assumptions”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 60–73
  * [KNY21] Fuyuki Kitagawa, Ryo Nishimaki and Takashi Yamakawa  “Secure Software Leasing from Standard Assumptions”  In _Theory of Cryptography_ Springer International Publishing, 2021, pp. 31–61  DOI: 10.1007/978-3-030-90459-3_2
  * [KNY21a] Fuyuki Kitagawa, Ryo Nishimaki and Takashi Yamakawa  “Secure software leasing from standard assumptions”  In _Theory of Cryptography Conference_ , 2021, pp. 31–61  Springer
  * [LLQZ22] Jiahui Liu, Qipeng Liu, Luowen Qian and Mark Zhandry  “Collusion Resistant Copy-Protection for Watermarkable Functionalities” https://eprint.iacr.org/2022/1429, Cryptology ePrint Archive, Paper 2022/1429, 2022  URL: https://eprint.iacr.org/2022/1429
  * [Mah18] Urmila Mahadev  “Classical Verification of Quantum Computations”, 2018  arXiv:1804.01082 [quant-ph]
  * [MP11] Daniele Micciancio and Chris Peikert  “Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller” https://eprint.iacr.org/2011/501, Cryptology ePrint Archive, Report 2011/501, 2011
  * [MR04] D. Micciancio and O. Regev  “Worst-case to average-case reductions based on Gaussian measures”  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , 2004, pp. 372–381  DOI: 10.1109/FOCS.2004.72
  * [MR07] Daniele Micciancio and Oded Regev  “Worst-Case to Average-Case Reductions Based on Gaussian Measures”  In _SIAM J. Comput._ 37.1, 2007, pp. 267–302  DOI: 10.1137/S0097539705447360
  * [NC11] Michael A. Nielsen and Isaac L. Chuang  “Quantum Computation and Quantum Information: 10th Anniversary Edition”  USA: Cambridge University Press, 2011
  * [Por22] Alexander Poremba  “Quantum Proofs of Deletion for Learning with Errors”  arXiv, 2022  DOI: 10.48550/ARXIV.2203.01610
  * [PR06] Chris Peikert and Alon Rosen  “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 145–166
  * [PS18] Chris Peikert and Sina Shiehian  “Privately constraining and programming PRFs, the LWE way”  In _Public-Key Cryptography–PKC 2018: 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part II 21_ , 2018, pp. 675–701  Springer
  * [Reg05] Oded Regev  “On lattices, learning with errors, random linear codes, and cryptography”  In _Journal of the ACM_ 56.6 New York, NY, USA: ACM, 2005, pp. 34:1–34:40  DOI: 10.1145/1568318.1568324
  * [Riv98] Ronald L. Rivest  “Can We Eliminate Certificate Revocation Lists?”  In _Proceedings Financial Cryptography ’98_ 1465, Lecture Notes in Computer Science  Springer, 1998, pp. 178–183  DOI: 10.1007/BFb0055482
  * [SSTX09] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa  “Efficient Public Key Encryption Based on Ideal Lattices” https://eprint.iacr.org/2009/285, Cryptology ePrint Archive, Paper 2009/285, 2009  URL: https://eprint.iacr.org/2009/285
  * [Stu95] S. Stubblebine  “Recent-secure authentication: enforcing revocation in distributed systems”  In _2012 IEEE Symposium on Security and Privacy_ Los Alamitos, CA, USA: IEEE Computer Society, 1995, pp. 0224
  * [TL17] Marco Tomamichel and Anthony Leverrier  “A largely self-contained and complete security proof for quantum key distribution”  In _Quantum_ 1 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2017, pp. 14  DOI: 10.22331/q-2017-07-14-14
  * [Unr13] Dominique Unruh  “Revocable quantum timed-release encryption” https://ia.cr/2013/606, Cryptology ePrint Archive, Report 2013/606, 2013
  * [Wat05] John Watrous  “Zero-knowledge against quantum attacks”  arXiv, 2005  DOI: 10.48550/ARXIV.QUANT-PH/0511020
  * [Wie83] Stephen Wiesner  “Conjugate Coding”  In _SIGACT News_ 15.1 New York, NY, USA: Association for Computing Machinery, 1983, pp. 78–88  DOI: 10.1145/1008908.1008920
  * [Wil13] Mark M. Wilde  “Quantum Information Theory”  USA: Cambridge University Press, 2013
  * [WW21] Hoeteck Wee and Daniel Wichs  “Candidate obfuscation via oblivious LWE sampling”  In _Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part III_ , 2021, pp. 127–156  Springer
  * [WZ82] William K Wootters and Wojciech H Zurek  “A single quantum cannot be cloned”  In _Nature_ 299.5886 Nature Publishing Group, 1982, pp. 802–803
  * [Zha21] Mark Zhandry  “Quantum Lightning Never Strikes the Same State Twice. Or: Quantum Money from Cryptographic Assumptions”  In _J. Cryptol._ 34.1 Berlin, Heidelberg: Springer-Verlag, 2021  DOI: 10.1007/s00145-020-09372-x