Watermarking PRFs against Quantum Adversaries

We first review the syntax of watermarking PRF used in this work. A watermarking PRF scheme consists of five algorithms $(\mathsf{Setup},\mathsf{Gen},\mathsf{Eval},\mathsf{Mark},\mathpzc{Extract})$.⁴⁴4In this paper, standard math font stands for classical algorithms, and calligraphic font stands for quantum algorithms. $\mathsf{Setup}$ outputs a public parameter $\mathsf{pp}$ and an extraction key $\mathsf{xk}$. $\mathsf{Gen}$ is given $\mathsf{pp}$ and outputs a PRF key $\mathsf{prfk}$ and a public tag $\tau$. $\mathsf{Eval}$ is the PRF evaluation algorithm that takes as an input $\mathsf{prfk}$ and $x$ in the domain and outputs $y$. By using $\mathsf{Mark}$, we can generate a marked evaluation circuit that has embedded message $\mathsf{m}\in\{0,1\}^{{\ell_{\mathsf{m}}}}$ and can be used to evaluate $\mathsf{Eval}(\mathsf{prfk},x^{\prime})$ for almost all $x^{\prime}$. Finally, $\mathpzc{Extract}$ is the extraction algorithm supposed to extract the embedded message from a pirated quantum evaluation circuit generated from the marked evaluation circuit. By default, in this work, we consider the public marking setting, where anyone can execute $\mathsf{Mark}$. Thus, $\mathsf{Mark}$ takes $\mathsf{pp}$ as an input. On the other hand, we consider both the private extraction and the public extraction settings. Thus, the extraction key $\mathsf{xk}$ used by $\mathpzc{Extract}$ is kept secret by an authority in the private extraction setting and made public in the public extraction setting.

In this work, we allow $\mathpzc{Extract}$ to take the public tag $\tau$ generated with the original PRF key corresponding to the pirate circuit. In reality, we execute $\mathpzc{Extract}$ for a software when a user claims that the software is illegally generated by using her/his PRF key. Thus, it is natural to expect we can use a user’s public tag for extraction. Moreover, pirate circuits are distinguishers, not predictors in this work. As discussed by Goyal et al. [GKWW21], security against pirate distinguishers is much preferable compared to security against pirate predictors considered in many previous works on watermarking. In this case, it seems that such additional information fed to $\mathpzc{Extract}$ is unavoidable. For a more detailed discussion on the syntax, see the discussion in Section 3.1.

It is also natural to focus on distinguishers breaking weak pseudorandomness of PRFs when we consider pirate distinguishers instead of pirate predictors. Goyal et al. [GKWW21] already discussed this point. Thus, we focus on watermarking weak PRF in this work.

We say that a watermarking PRF scheme satisfies unremovability if given a marked evaluation circuit $\widetilde{C}$ that has an embedded message $\mathsf{m}$, any adversary cannot generate a circuit such that it is a “good enough circuit”, but the extraction algorithm fails to output $\mathsf{m}$. In this work, we basically follow the notion of “good enough circuit” defined by Goyal et al. [GKWW21] as stated above. Let $D$ be the following distribution for a PRF $\mathsf{Eval}(\mathsf{prfk},\cdot):\mathsf{Dom}\rightarrow\mathsf{Ran}$.

$D$:

Generate $b\leftarrow\{0,1\}$, $x\leftarrow\mathsf{Dom}$, and $y_{0}\leftarrow\mathsf{Ran}$. Compute $y_{1}\leftarrow\mathsf{Eval}(\mathsf{prfk},x)$. Output $(b,x,y_{b})$.

A circuit is defined as good enough circuit with respect to $\mathsf{Eval}(\mathsf{prfk},\cdot)$ if given $(x,y_{b})$ output by $D$, it can correctly guess $b$ with probability significantly greater than $1/2$. In other words, a circuit is defined as good enough if the circuit breaks weak PRF security.

Below, for a distribution $D^{\prime}$ whose output is of the form $(b,x,y)$, let $\mathcal{M}_{D^{\prime}}=(\boldsymbol{M}_{D^{\prime},0},\boldsymbol{M}_{D^{\prime},1})$ be binary positive operator valued measures (POVMs) that represents generating random $(b,x,y)$ from $D^{\prime}$ and testing if a quantum circuit can guess $b$ from $(x,y)$. Then, for a quantum state $\ket{\psi}$, the overall distinguishing advantage of it for the above distribution $D$ is $\bra{\psi}\boldsymbol{M}_{D,0}\ket{\psi}$. Thus, a natural adaptation of the above notion of goodness for quantum circuits might be to define a quantum state $\ket{\psi}$ as good if $\bra{\psi}\boldsymbol{M}_{D,0}\ket{\psi}$ is significantly greater than $1/2$. However, this notion of goodness for quantum circuits is not really meaningful. The biggest issue is that it does not consider the stateful nature of quantum programs.

This issue was previously addressed by Zhandry [Zha20] in the context of traitor tracing against quantum adversaries. In the context of classical traitor tracing or watermarking, we can assume that a pirate circuit is stateless, or can be rewound to its original state. This assumption is reasonable. If we have the software description of the pirate circuit, such a rewinding is trivial. Even if we have a hardware box in which a pirate circuit is built, it seems that such a rewinding is possible by hard reboot or cutting power. On the other hand, in the context of quantum watermarking, we have to consider that a pirate circuit is inherently stateful since it is described as a quantum state. Operations to a quantum state can alter the state, and in general, it is impossible to rewind the state into its original state. Regarding the definition of good quantum circuits above, if we can somehow compute the average success probability $\bra{\psi}\boldsymbol{M}_{D,0}\ket{\psi}$ of the quantum state $\ket{\psi}$, the process can change or destroy the quantum state $\ket{\psi}$. Namely, even if we once confirm that the quantum state $\ket{\psi}$ is good by computing $\bra{\psi}\boldsymbol{M}_{D,0}\ket{\psi}$, we cannot know the success probability of the quantum state even right after the computation. Clearly, the above notion of goodness is not the right notion, and we need one that captures the stateful nature of quantum programs.

In the work on traitor tracing against quantum adversaries, Zhandry [Zha20] proposed a notion of goodness for quantum programs that solves the above issue. We adopt it. For the above POVMs $\mathcal{M}_{D}$, let $\mathcal{M}_{D}^{\prime}$ be the projective measurement $\{P_{p}\}_{p\in[0,1]}$ that projects a state onto the eigenspaces of $\boldsymbol{M}_{D,0}$, where each $p$ is an eigenvalue of $\boldsymbol{M}_{D,0}$. $\mathcal{M}_{D}^{\prime}$ is called projective implementation of $\mathcal{M}_{D}$ and denoted as $\mathsf{ProjImp}(\mathcal{M}_{D})$. Zhandry showed that the following process has the same output distribution as $\mathcal{M}_{D}$:

1. 1.

   Apply the projective measurement $\mathcal{M}_{D}^{\prime}=\mathsf{ProjImp}(\mathcal{M}_{D})$ and obtain $p$.

2. 2.

   Output $0$ with probability $p$ and output $1$ with probability $1-p$.

Intuitively, $\mathcal{M}_{D}^{\prime}$ project a state to an eigenvector of $\boldsymbol{M}_{D,0}$ with eigenvalue $p$, which can be seen as a quantum state with success probability $p$. Using $\mathcal{M}_{D}^{\prime}$, Zhandry defined that a quantum circuit is $\mathsf{Live}$ if the outcome of the measurement $\mathcal{M}_{D}^{\prime}$ is significantly greater than $1/2$. The notion of $\mathsf{Live}$ is a natural extension of the classical goodness since it collapses to the classical goodness for a classical decoder. Moreover, we can ensure that a quantum state that is tested as $\mathsf{Live}$ still has a high success probability. On the other hand, the above notion of goodness cannot say anything about the post-tested quantum state’s success probability even if the test is passed. In this work, we use the notion of $\mathsf{Live}$ quantum circuits as the notion of good quantum circuits.

From the above discussion, our goal is to construct a watermarking PRF scheme that guarantees that we can extract the embedded message correctly if a pirated quantum circuit is $\mathsf{Live}$. In watermarking PRF schemes, we usually extract an embedded message by applying several tests on success probability to a pirate circuit. When a pirate circuit is a quantum state, the set of tests that we can apply is highly limited compared to a classical circuit due to the stateful nature of quantum states.

One set of tests we can apply without destroying the quantum state is $\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})$ for distributions $D^{\prime}$ that are indistinguishable from $D$ from the view of the pirate circuit.⁵⁵5In the actual extraction process, we use an approximation of projective implementation introduced by Zhandry [Zha20] since applying a projective implementation is inefficient. In this overview, we ignore this issue for simplicity. We denote this set as $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$. Zhandry showed that if distributions $D_{1}$ and $D_{2}$ are indistinguishable, the outcome of $\mathsf{ProjImp}(\mathcal{M}_{D_{1}})$ is close to that of $\mathsf{ProjImp}(\mathcal{M}_{D_{2}})$. By combining this property with the projective property of projective implementations, as long as the initial quantum state is $\mathsf{Live}$ and we apply only tests contained in $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$, the quantum state remains $\mathsf{Live}$. On the other hand, if we apply a test outside of $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$, the quantum state might be irreversibly altered. This fact is a problem since the set $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$ only is not sufficient to implement the existing widely used construction method for watermarking PRF schemes.

To see this, we briefly review the method. In watermarking PRF schemes, the number of possible embedded messages is super-polynomial, and thus we basically need to extract an embedded message in a bit-by-bit manner. In the method, such a bit-by-bit extraction is done as follows. For every $i\in[{\ell_{\mathsf{m}}}]$, we define two distributions $S_{i,0}$ and $S_{i,1}$ whose output is of the form $(b,x,y)$ as $D$ above. Then, we design a marked circuit with embedded message $\mathsf{m}\in\{0,1\}^{{\ell_{\mathsf{m}}}}$ so that it can be used to guess $b$ from $(x,y)$ with probability significantly greater than $1/2$ only for $S_{i,0}$ (resp. $S_{i,1}$) if $\mathsf{m}[i]=0$ (resp. $\mathsf{m}[i]=1$). The extraction algorithm can extract $i$-th bit of the message $\mathsf{m}[i]$ by checking for which distributions of $S_{i,0}$ and $S_{i,1}$ a pirate circuit has a high distinguishing advantage.

As stated above, we cannot use this standard method to extract a message from quantum pirate circuits. The reason is that $S_{i,0}$ and $S_{i,1}$ are typically distinguishable. This implies that at least either one of $\mathsf{ProjImp}(\mathcal{M}_{S_{i,0}})$ or $\mathsf{ProjImp}(\mathcal{M}_{S_{i,1}})$ is not contained in $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$. Since the test outside of $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$ might destroy the quantum state, we might not be able to perform the process for all $i$, and fail to extract the entire bits of the embedded message.

It seems that to perform the bit-by-bit extraction for a quantum state, we need to extend the set of applicable tests and come up with a new extraction method.

We find that as another applicable set of tests, we have $\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})$ for distributions $D^{\prime}$ that are indistinguishable from $D^{\mathtt{rev}}$, where $D^{\mathtt{rev}}$ is the following distribution.

$D^{\mathtt{rev}}$:

Generate $b\leftarrow\{0,1\}$, $x\leftarrow\mathsf{Dom}$, and $y_{0}\leftarrow\mathsf{Ran}$. Compute $y_{1}\leftarrow\mathsf{Eval}(\mathsf{prfk},x)$. Output $(1\oplus b,x,y_{b})$.

We denote the set as $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D^{\mathtt{rev}}\}$. $D^{\mathtt{rev}}$ is the distribution the first bit of whose output is flipped from that of $D$. Then, $\mathcal{M}_{D^{\mathtt{rev}}}$ can be seen as POVMs that represents generating random $(b,x,y_{b})$ from $D$ and testing if a quantum circuit cannot guess $b$ from $(x,y_{b})$. Thus, we see that $\mathcal{M}_{D^{\mathtt{rev}}}=(\boldsymbol{M}_{D,1},\boldsymbol{M}_{D,0})$. Recall that $\mathcal{M}_{D}=(\boldsymbol{M}_{D,0},\boldsymbol{M}_{D,1})$.

Let $D_{1}\in\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$ and $D^{\mathtt{rev}}_{1}$ be the distribution that generates $(b,x,y)\leftarrow D_{1}$ and outputs $(1\oplus b,x,y)$. $D^{\mathtt{rev}}_{1}$ is a distribution contained in $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D^{\mathtt{rev}}\}$. Similarly to the relation between $D$ and $D^{\mathtt{rev}}$, if $\mathcal{M}_{D_{1}}=(\boldsymbol{M}_{D_{1},0},\boldsymbol{M}_{D_{1},1})$, we have $\mathcal{M}_{D^{\mathtt{rev}}_{1}}=(\boldsymbol{M}_{D^{\mathtt{rev}}_{1},1},\boldsymbol{M}_{D^{\mathtt{rev}}_{1},0})$. Since $\boldsymbol{M}_{D_{1},0}+\boldsymbol{M}_{D_{1},1}=\boldsymbol{I}$, $\boldsymbol{M}_{D_{1},0}$ and $\boldsymbol{M}_{D_{1},1}$ share the same set of eigenvectors, and if a vector is an eigenvector of $\boldsymbol{M}_{D_{1},0}$ with eigenvalue $p$, then it is also an eigenvector of $\boldsymbol{M}_{D_{1},1}$ with eigenvalue $1-p$. Thus, if apply $\mathsf{ProjImp}(\mathcal{M}_{D_{1}})$ and $\mathsf{ProjImp}(\mathcal{M}_{D^{\mathtt{rev}}_{1}})$ successively to a quantum state and obtain the outcomes $\widetilde{p}_{1}$ and $\widetilde{p}_{1}^{\prime}$, it holds that $\widetilde{p}_{1}^{\prime}=1-\widetilde{p}_{1}$. We call this property the reverse projective property of the projective implementation.

Combining projective and reverse projective properties and the outcome closeness for indistinguishable distributions of the projective implementation, we see that the following key fact holds.

Key fact:

As long as the initial quantum state is $\mathsf{Live}$ and we apply tests contained in $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$ or $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})|D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D^{\mathtt{rev}}\}$, the quantum state remains $\mathsf{Live}$. Moreover, if the outcome of applying $\mathsf{ProjImp}(\mathcal{M}_{D})$ to the initial state is $p$, we get the outcome close to $p$ every time we apply a test in $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$, and we get the outcome close to $1-p$ every time we apply a test in $\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D^{\mathtt{rev}}\}$.

In this work, we perform bit-by-bit extraction of embedded messages by using the above key fact of the projective implementation. To this end, we introduce the new notion of extraction-less watermarking PRF as an intermediate primitive.

An extraction-less watermarking PRF scheme has almost the same syntax as a watermarking PRF scheme, except that it does not have an extraction algorithm $\mathpzc{Extract}$ and instead has a simulation algorithm $\mathsf{Sim}$. $\mathsf{Sim}$ is given the extraction key $\mathsf{xk}$, the public tag $\tau$, and an index $i\in[{\ell_{\mathsf{m}}}]$, and outputs a tuple of the form $(\gamma,x,y)$. $\mathsf{Sim}$ simulates outputs of $D$ or $D^{\mathtt{rev}}$ for a pirate circuit depending on the message embedded to the marked circuit corresponding to the pirate circuit. More concretely, we require that from the view of the pirate circuit generated from a marked circuit with embedded message $\mathsf{m}\in\{0,1\}^{{\ell_{\mathsf{m}}}}$, outputs of $\mathsf{Sim}$ are indistinguishable from those of $D$ if $\mathsf{m}[i]=0$ and are indistinguishable from those of $D^{\mathtt{rev}}$ if $\mathsf{m}[i]=1$ for every $i\in[{\ell_{\mathsf{m}}}]$. We call this security notion simulatability for mark-dependent distributions (SIM-MDD security).

By using an extraction-less watermarking PRF scheme $\mathsf{ELWMPRF}$, we construct a watermarking PRF scheme $\mathsf{WMPRF}$ against quantum adversaries as follows. We use $\mathsf{Setup},\mathsf{Gen},\mathsf{Eval},\mathsf{Mark}$ of $\mathsf{ELWMPRF}$ as $\mathsf{Setup},\mathsf{Gen},\mathsf{Eval},\mathsf{Mark}$ of $\mathsf{WMPRF}$, respectively. We explain how to construct the extraction algorithm $\mathpzc{Extract}$ of $\mathsf{WMPRF}$ using $\mathsf{Sim}$ of $\mathsf{ELWMPRF}$. For every $i\in[{\ell_{\mathsf{m}}}]$, we define $D_{\tau,i}$ as the distribution that outputs randomly generated $(\gamma,x,y)\leftarrow\mathsf{Sim}(\mathsf{xk},\tau,i)$. Given $\mathsf{xk}$, $\tau$, and a quantum state $\ket{\psi}$, $\mathpzc{Extract}$ extracts the embedded message in the bit-by-bit manner by repeating the following process for every $i\in[{\ell_{\mathsf{m}}}]$.

• •

  Apply $\mathsf{ProjImp}(\mathcal{M}_{D_{\tau,i}})$ to $\ket{\psi_{i-1}}$ and obtain the outcome $\widetilde{p}_{i}$, where $\ket{\psi_{0}}=\ket{\psi}$ and $\ket{\psi_{i-1}}$ is the state after the $(i-1)$-th loop for every $i\in[{\ell_{\mathsf{m}}}]$.

• •

  Set $\mathsf{m}^{\prime}_{i}=0$ if $\widetilde{p}_{i}>1/2$ and otherwise $\mathsf{m}^{\prime}_{i}=1$.

The extracted message is set to $\mathsf{m}^{\prime}_{1}\|\cdots\|\mathsf{m}^{\prime}_{\ell_{\mathsf{m}}}$.

We show that the above construction satisfies unremovability. Suppose an adversary is given marked circuit $\widetilde{C}\leftarrow\mathsf{Mark}(\mathsf{pp},\mathsf{prfk},\mathsf{m})$ and generates a quantum state $\ket{\psi}$, where $(\mathsf{pp},\mathsf{xk})\leftarrow\mathsf{Setup}(1^{\lambda})$ and $(\mathsf{prfk},\tau)\leftarrow\mathsf{Gen}(\mathsf{pp})$. Suppose also that $\ket{\psi}$ is $\mathsf{Live}$. This assumption means that the outcome $p$ of applying $\mathsf{ProjImp}(\mathcal{M}_{D})$ to $\ket{\psi}$ is $1/2+\epsilon$, where $\epsilon$ is an inverse polynomial. For every $i\in[{\ell_{\mathsf{m}}}]$, from the SIM-MDD security of $\mathsf{ELWMPRF}$, $D_{\tau,i}$ is indistinguishable from $D$ if $\mathsf{m}[i]=0$ and is indistinguishable from $D^{\mathtt{rev}}$ if $\mathsf{m}[i]=1$. This means that $D_{\tau,i}\in\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D\}$ if $\mathsf{m}[i]=0$ and $D_{\tau,i}\in\{\mathsf{ProjImp}(\mathcal{M}_{D^{\prime}})\mid D^{\prime}\stackrel{{\scriptstyle\mathsf{c}}}{{\approx}}D^{\mathtt{rev}}\}$ if $\mathsf{m}[i]=1$. Then, from the above key fact of the projective implementation, it holds that $\widetilde{p}_{i}$ is close to $1/2+\epsilon>1/2$ if $\mathsf{m}[i]=0$ and is close to $1/2-\epsilon<1/2$ if $\mathsf{m}[i]=1$. Therefore, we see that $\mathpzc{Extract}$ correctly extract $\mathsf{m}$ from $\ket{\psi}$. This means that $\mathsf{WMPRF}$ satisfies unremovability.

The above definition, construction, and security analysis are simplified and ignore many subtleties. The most significant point is that we use approximated projective implementations introduced by Zhandry [Zha20] instead of projective implementations in the actual construction since applying a projective implementation is an inefficient process. Moreover, though the outcomes of (approximate) projective implementations for indistinguishable distributions are close, in the actual analysis, we have to take into account that the outcomes gradually change every time we apply an (approximate) projective implementation. These issues can be solved by doing careful parameter settings.

Some readers familiar with Zhandry’s work [Zha20] might think that our technique contradicts the lesson from Zhandry’s work since it essentially says that once we find a large gap in success probabilities, the tested quantum pirate circuit might self-destruct. However, this is not the case. What Zhandry’s work really showed is the following. Once a quantum pirate circuit itself detects that there is a large gap in success probabilities, it might self-destruct. Even if an extractor finds a large gap in success probabilities, if the tested quantum pirate circuit itself cannot detect the large gap, the pirate circuit cannot self-destruct. In Zhandry’s work, whenever an extractor finds a large gap, the tested pirate circuit also detects the large gap. In our work, the tested pirate circuit cannot detect a large gap throughout the extraction process while an extractor can find it.

The reason why a pirate circuit cannot detect a large gap in our scheme even if an extractor can find it is as follows. Recall that in the above extraction process of our scheme based on an extraction-less watermarking PRF scheme, we apply $\mathsf{ProjImp}(\mathcal{M}_{D_{\tau,i}})$ to the tested pirate circuit for every $i\in[{\ell_{\mathsf{m}}}]$. Each $D_{\tau,i}$ outputs a tuple of the form $(b,x,y)$ and is indistinguishable from $D$ or $D^{\mathtt{rev}}$ depending on the embedded message. In the process, we apply $\mathsf{ProjImp}(\mathcal{M}_{D_{\tau,i}})$ for every $i\in[{\ell_{\mathsf{m}}}]$, and we get the success probability $p$ if $D_{\tau,i}$ is indistinguishable from $D$ and we get $1-p$ if $D_{\tau,i}$ is indistinguishable from $D^{\mathtt{rev}}$. The tested pirate circuit needs to know which of $D$ or $D^{\mathtt{rev}}$ is indistinguishable from the distribution $D_{\tau,i}$ behind the projective implementation to know which of $p$ or $1-p$ is the result of an application of a projective implementation. However, this is impossible. The tested pirate circuit receives only $(x,y)$ part of $D_{\tau,i}$’s output and not $b$ part. (Recall that the task of the pirate circuit is to guess $b$ from $(x,y)$.) The only difference between $D$ and $D^{\mathtt{rev}}$ is that the first-bit $b$ is flipped. Thus, if the $b$ part is dropped, $D_{\tau,i}$ is, in fact, indistinguishable from both $D$ and $D^{\mathtt{rev}}$. As a result, the pirate program cannot know which of $p$ or $1-p$ is the result of an application of a projective implementation. In other words, the pirate circuit cannot detect a large gap in our extraction process.

In the rest of this overview, we will explain how to realize extraction-less watermarking PRF.

We consider the following two settings similar to the ordinary watermarking PRF. Recall that we consider the public marking setting by default.

Private-simulatable:

In this setting, the extraction key $\mathsf{xk}$ fed into $\mathsf{Sim}$ is kept secret. We require that SIM-MDD security hold under the existence of the simulation oracle that is given a public tag $\tau^{\prime}$ and an index $i^{\prime}\in[{\ell_{\mathsf{m}}}]$ and returns $\mathsf{Sim}(\mathsf{xk},\tau^{\prime},i^{\prime})$. An extraction-less watermarking PRF scheme in this setting yields a watermarking PRF scheme against quantum adversaries in private-extractable setting where unremovability holds for adversaries who can access the extraction oracle.

Public-simulatable:

In this setting, the extraction key $\mathsf{xk}$ is publicly available. An extraction-less watermarking PRF scheme in this setting yields a watermarking PRF scheme against quantum adversaries in the public-extractable setting.

We provide a construction in the first setting using private constrained PRF based on the hardness of the LWE assumption. Also, we provide a construction in the second setting based on IO and the hardness of the LWE assumption.

To give a high-level idea behind the above constructions, in this overview, we show how to construct a public-simulatable extraction-less watermarking PRF in the token-based setting [CHN⁺18]. In the token-based setting, we treat a marked circuit $\widetilde{C}\leftarrow\mathsf{Mark}(\mathsf{pp},\mathsf{prfk},\mathsf{m})$ as a tamper-proof hardware token that an adversary can only access in a black-box way.

Before showing the actual construction, we explain the high-level idea. Recall that SIM-MDD security requires that an adversary $\mathpzc{A}$ who is given $\widetilde{C}\leftarrow\mathsf{Mark}(\mathsf{pp},\mathsf{prfk},\mathsf{m})$ cannot distinguish $(\gamma^{\ast},x^{\ast},y^{\ast})\leftarrow\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$ from an output of $D$ if $\mathsf{m}[i^{\ast}]=0$ and from that of $D^{\mathtt{rev}}$ if $\mathsf{m}[i^{\ast}]=1$. This is the same as requiring that $\mathpzc{A}$ cannot distinguish $(\gamma^{\ast},x^{\ast},y^{\ast})\leftarrow\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$ from that of the following distribution $D_{\mathtt{real},i^{\ast}}$. We can check that $D_{\mathtt{real},i^{\ast}}$ is identical with $D$ if $\mathsf{m}[i^{\ast}]=0$ and with $D^{\mathtt{rev}}$ if $\mathsf{m}[i^{\ast}]=1$.

$D_{\mathtt{real},i^{\ast}}$:

Generate $\gamma\leftarrow\{0,1\}$ and $x\leftarrow\mathsf{Dom}$. Then, if $\gamma=\mathsf{m}[i^{\ast}]$, generate $y\leftarrow\mathsf{Ran}$, and otherwise, compute $y\leftarrow\mathsf{Eval}(\mathsf{prfk},x)$. Output $(\gamma,x,y)$.

Essentially, the only attack that $\mathpzc{A}$ can perform is to feed $x^{\ast}$ contained in the given tuple $(\gamma^{\ast},x^{\ast},y^{\ast})$ to $\widetilde{C}$ and compares the result $\widetilde{C}(x^{\ast})$ with $y^{\ast}$, if we ensure that $\gamma^{\ast}$, $x^{\ast}$ are pseudorandom. In order to make the construction immune to this attack, letting $\widetilde{C}\leftarrow\mathsf{Mark}(\mathsf{pp},\mathsf{prfk},\mathsf{m})$ and $(\gamma^{\ast},x^{\ast},y^{\ast})\leftarrow\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$, we have to design $\mathsf{Sim}$ and $\widetilde{C}$ so that

• •

  If $\gamma=\mathsf{m}[i^{\ast}]$, $\widetilde{C}(x^{\ast})$ outputs a value different from $y^{\ast}$.

• •

  If $\gamma\neq\mathsf{m}[i^{\ast}]$, $\widetilde{C}(x^{\ast})$ outputs $y^{\ast}$.

We achieve these conditions as follows. First, we set $(\gamma^{\ast},x^{\ast},y^{\ast})$ output by $\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$ so that $\gamma^{\ast}$ and $y^{\ast}$ is random values and $x^{\ast}$ is an encryption of $y^{\ast}\|i^{\ast}\|\gamma^{\ast}$ by a public-key encryption scheme with pseudorandom ciphertext property, where the encryption key $\mathsf{pk}$ is included in $\tau$. Then, we set $\widetilde{C}$ as a token such that it has the message $\mathsf{m}$ and the decryption key $\mathsf{sk}$ corresponding to $\mathsf{pk}$ hardwired, and it outputs $y^{\ast}$ if the input is decryptable and $\gamma^{\ast}\neq\mathsf{m}[i^{\ast}]$ holds for the decrypted $y^{\ast}\|i^{\ast}\|\gamma^{\ast}$, and otherwise behaves as $\mathsf{Eval}(\mathsf{prfk},\cdot)$. The actual construction is as follows.

Let $\mathsf{PRF}$ be a PRF family consisting of functions $\{\mathsf{F}_{\mathsf{prfk}}(\cdot):\{0,1\}^{n}\rightarrow\{0,1\}^{\lambda}|\mathsf{prfk}\}$, where $\lambda$ is the security parameter and $n$ is sufficiently large. Let $\mathsf{PKE}=(\mathsf{KG},\mathsf{E},\mathsf{D})$ be a CCA secure public-key encryption scheme satisfying pseudorandom ciphertext property. Using these ingredients, We construct an extraction-less watermarking PRF scheme $\mathsf{ELWMPRF}=(\mathsf{Setup},\mathsf{Gen},\mathsf{Eval},\mathsf{Mark},\mathsf{Sim})$ as follows.

$\mathsf{Setup}(1^{\lambda})$:

In this construction, $\mathsf{pp}:=\bot$ and $\mathsf{xk}:=\bot$.

$\mathsf{Gen}(\mathsf{pp})$:

It generates a fresh PRF key $\mathsf{prfk}$ of $\mathsf{PRF}$ and a key pair $(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KG}(1^{\lambda})$. The PRF key is $(\mathsf{prfk},\mathsf{sk})$ and the corresponding public tag is $\mathsf{pk}$.

$\mathsf{Eval}((\mathsf{prfk},\mathsf{sk}),x)$:

It simply outputs $\mathsf{F}_{\mathsf{prfk}}(x)$.

$\mathsf{Mark}(\mathsf{pp},(\mathsf{prfk},\mathsf{sk}),\mathsf{m})$:

It generates the following taken $\widetilde{C}[\mathsf{prfk},\mathsf{sk},\mathsf{m}]$.

Hard-Coded Constants: $\mathsf{prfk},\mathsf{sk},\mathsf{m}$. Input: $x\in\{0,1\}^{n}$. 1. Try to decrypt $y\|i\|\gamma\leftarrow\mathsf{D}(\mathsf{sk},x)$ with $y\in\{0,1\}^{\lambda}$, $i\in[{\ell_{\mathsf{m}}}]$, and $\gamma\in\{0,1\}$. 2. If decryption succeeds, output $y$ if $\gamma\neq\mathsf{m}[i]$ and $\mathsf{F}_{\mathsf{prfk}}(x)$ otherwise. 3. Otherwise, output $\mathsf{F}_{\mathsf{prfk}}(x)$.

$\mathsf{Sim}(\mathsf{xk},\tau,i)$:

It first generates $\gamma\leftarrow\{0,1\}$ and $y\leftarrow\{0,1\}^{\lambda}$. Then, it parses $\tau:=\mathsf{pk}$ and generates $x\leftarrow\mathsf{E}(\mathsf{pk},y\|i\|\gamma)$. Finally, it outputs $(\gamma,x,y)$.

We check that $\mathsf{ELWMPRF}$ satisfies SIM-MDD security. For simplicity, we fix the message $\mathsf{m}\in[{\ell_{\mathsf{m}}}]$ embedded into the challenge PRF key. Then, for any adversary $\mathpzc{A}$ and $i^{\ast}\in[{\ell_{\mathsf{m}}}]$, SIM-MDD security requires that given $\widetilde{C}[\mathsf{prfk},\mathsf{sk},\mathsf{m}]\leftarrow\mathsf{Mark}(\mathsf{mk},\mathsf{prfk},\mathsf{m})$ and $\tau=\mathsf{pk}$, $\mathpzc{A}$ cannot distinguish $(\gamma^{\ast},x^{\ast}=\mathsf{E}(\mathsf{pk},y^{\ast}\|i^{\ast}\|\gamma^{\ast}),y^{\ast})\leftarrow\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$ from an output of $D$ if $\mathsf{m}[i^{\ast}]=0$ and is indistinguishable from $D^{\mathtt{rev}}$ if $\mathsf{m}[i^{\ast}]=1$.

We consider the case of $\mathsf{m}[i^{\ast}]=0$. We can finish the security analysis by considering the following sequence of mutually indistinguishable hybrid games, where $\mathpzc{A}$ is given $(\gamma^{\ast},x^{\ast}=\mathsf{E}(\mathsf{pk},y^{\ast}\|i^{\ast}\|\gamma^{\ast}),y^{\ast})\leftarrow\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$ in the first game, and on the other hand, is given $(\gamma^{\ast},x^{\ast},y^{\ast})\leftarrow D$ in the last game. We first change the game so that $x^{\ast}$ is generated as a uniformly random value instead of $x^{\ast}\leftarrow\mathsf{E}(\mathsf{pk},y^{\ast}\|i^{\ast}\|\gamma^{\ast})$ by using the pseudorandom ciphertext property under CCA of $\mathsf{PKE}$. This is possible since the CCA oracle can simulate access to the marked token $\widetilde{C}[\mathsf{prfk},\mathsf{sk},\mathsf{m}]$ by $\mathpzc{A}$. Then, we further change the security game so that if $\gamma^{\ast}=1$, $y^{\ast}$ is generated as $\mathsf{F}_{\mathsf{prfk}}(x^{\ast})$ instead of a uniformly random value by using the pseudorandomness of $\mathsf{PRF}$. Note that if $\gamma^{\ast}=0$, $y^{\ast}$ remains uniformly at random. We see that if $\gamma^{\ast}=1$, the token $\widetilde{C}[\mathsf{prfk},\mathsf{sk},\mathsf{m}]$ never evaluate $\mathsf{F}_{\mathsf{prfk}}(x^{\ast})$ since $\mathsf{m}[i^{\ast}]\neq\gamma^{\ast}$. Thus, this change is possible. We see that now the distribution of $(\gamma^{\ast},x^{\ast},y^{\ast})$ is exactly the same as that output by $D$. Similarly, in the case of $\mathsf{m}[i^{\ast}]=1$, we can show that an output of $\mathsf{Sim}(\mathsf{xk},\tau,i^{\ast})$ is indistinguishable from that output by $D^{\mathtt{rev}}$. The only difference is that in the final step, we change the security game so that $y^{\ast}$ is generated as $\mathsf{F}_{\mathsf{prfk}}(x^{\ast})$ if $\gamma^{\ast}=0$.

In the actual public-simulatable construction, we implement this idea using iO and puncturable encryption [CHN⁺18] instead of token and CCA secure public-key encryption. Also, in the actual secret-simulatable construction, we basically follow the same idea using private constrained PRF and secret-key encryption.

Cohen et al. [CHN⁺18] present a publicly extractable watermarking PRF from IO and injective OWFs. It is unremovable against adversaries who can access the mark oracle only before a target marked circuit is given. The mark oracle returns a marked circuit for a queried arbitrary polynomial-size circuit. Suppose we additionally assume the hardness of the decisional Diffie-Hellman or LWE problem. In that case, their watermarking PRF is unremovable against adversaries that can access the mark oracle before and after a target marked circuit is given. However, adversaries can query a valid PRF key to the mark oracle in that case. They also present definitions and constructions of watermarking for public-key cryptographic primitives.

Boneh, Lewi, and Wu [BLW17] present a privately extractable watermarking PRF from privately programmable PRFs, which are variants of private constrained PRFs [BLW17, CC17]. It is unremovable in the presence of the mark oracle. However, it is not secure in the presence of the extraction oracle and does not support public marking. They instantiate a privately programmable PRF with IO and OWFs, but later, Peikert and Shiehian [PS18] instantiate it with the LWE assumption.

Kim and Wu [KW21] (KW17), Quach, Wichs, and Zirdelis [QWZ18] (QWZ), and Kim and Wu [KW19] (KW19) present privately extractable watermarking PRFs from the LWE assumption. They are secure in the presence of the mark oracle. KW17 construction is not secure in the presence of the extraction oracle and does not support public marking. QWZ construction is unremovable in the presence of the extraction oracle and supports public marking. However, it does not have pseudorandomness against an authority that generates a marking and extraction key. KW19 construction is unremovable in the presence of the extraction oracle and has some restricted pseudorandomness against an authority (see the reference [KW19] for the detail). However, it does not support public marking.⁶⁶6Their construction supports public marking in the random oracle model.

Yang et al. [YAL⁺19] present a collusion-resistant watermarking PRF from IO and the LWE assumption. Collusion-resistant watermarking means unremovability holds even if adversaries receive multiple marked circuits with different embedded messages generated from one target circuit.

Goyal, Kim, Manohar, Waters, and Wu [GKM⁺19] improve the definitions of watermarking for public-key cryptographic primitives and present constructions. In particular, they introduce collusion-resistant watermarking and more realistic attack strategies for public-key cryptographic primitives. Nishimaki [Nis20] present a general method for equipping many existing public-key cryptographic schemes with the watermarking functionality.

Goyal, Kim, Waters, and Wu [GKWW21] introduce the notion of traceable PRFs, where we can identify a user that creates a pirate copy of her/his authenticated PRF. The difference between traceable PRF and (collusion-resistant) watermarking PRF is that there is only one target original PRF and multiple authenticated copies of it with different identities in traceable PRF. In (collusion-resistant) watermarking PRF, we consider many different PRF keys. In addition, Goyal et al. introduce a refined attack model. Adversaries in previous watermarking PRF definitions output a pirate PRF circuit that correctly computes the original PRF values for $1/2+\epsilon$ fraction of inputs. However, adversaries in traceable PRFs output a pirate circuit that distinguishes whether an input pair consists of a random input and a real PRF value or a random input and output value. This definition captures wide range of attacks. For example, it captures adversaries who create a pirate PRF circuit that can compute the first quarter bits of the original PRF output. Such an attack is not considered in previous watermarking PRFs. We adopt the refined attack model in our definitions.

Zhandry [Zha20] introduces the definition of secure traitor tracing against quantum adversaries. In traitor tracing, each legitimate user receives a secret key that can decrypt broadcasted ciphertexts and where identity information is embedded. An adversary outputs a pirate decoder that can distinguish whether an input is a ciphertext of $m_{0}$ or $m_{1}$ where $m_{0}$ and $m_{1}$ are adversarially chosen plaintexts. A tracing algorithm must identify a malicious user’s identity such that its secret decryption key is embedded in the pirate decoder. Thus, we need to extract information from adversarially generated objects. Such a situation also appears in security proofs of interactive proof systems [Wat09, Unr12, ARU14, CMSZ21] (but not in real cryptographic algorithms) since we rewind a verifier.

Zhandry presents how to estimate the success decryption probability of a quantum pirate decoder without destroying the decoding (distinguishing) capability. He achieves a quantum tracing algorithm that extracts a malicious user identity by combining the probability approximation technique above with PLBE [BSW06]. However, his technique is limited to the setting where user identity spaces are only polynomially large while there are several traitor tracing schemes with exponentially large identity spaces [NWZ16, GKW19]. As observed in previous works [GKM⁺19, Nis20, GKWW21], traitor tracing and watermarking have similarities since an adversary outputs a pirate circuit in the watermarking setting and an extraction algorithm tries to retrieve information from it. However, a notable difference is that we must consider exponentially large message spaces by default in the (message-embedding) watermarking setting.

As we explained above, Aaronson et al. [ALL⁺21], and Kitagawa et al. [KNY21] achieve secure software leasing schemes by using watermarking. A leased software consists of a quantum state and watermarked circuit. Although they use watermarking schemes in the quantum setting, it is sufficient for their purpose to use secure watermarking against adversaries that output a classical pirate circuit. This is because a returned software is verified by a checking algorithm and must have a specific format in secure software leasing.⁷⁷7A valid software must run on a legitimate platform. For example, a video game title of Xbox must run on Xbox. That is, a returned software is rejected if it does not have a classical circuit part that can be tested by an extraction algorithm of the building block watermarking.