Software watermarking enables one to embed some information called “mark” into a program while preserving its functionality, and to read it from the program. As a definition of function preserving, Cohen et al. (STOC 2016) proposed statistical function preserving which requires that the input/output behavior of the marked circuit is identical almost everywhere to that of the original unmarked circuit. They showed how to construct watermarkable cryptographic primitives with statistical function preserving, including pseudorandom functions (PRFs) and public-key encryption from indistinguishability obfuscation. Recently, Goyal et al. (CRYPTO 2019) introduced more relaxed definition of function preserving for watermarkable signature. Watermarkable signature embeds a mark into a signing circuit of digital signature. The relaxed function preserving only requires that the marked signing circuit outputs valid signatures. They provide watermarkable signature with the relaxed function preserving only based on (standard) digital signature.

In this work, we introduce an intermediate notion of function preserving for watermarkable signature, which is calledcomputational function preserving. Then, we examine the relationship among our computational function preserving, relaxed function preserving by Goyal et al., and statistical function preserving by Cohen et al. Furthermore, we propose a generic construction of watermarkable signature scheme satisfying computational function preserving based on public key encryption and (standard) digital signature.

1. 1.

   \(\mathbb {SIG}\) is a signature space for the watermarkable signature scheme.

A part of this work was supported by NTT Secure Platform Laboratories, JST OPERA JPMJOP1612, JST CREST JPMJCR14D6, JSPS KAKENHI JP16H01705, JP17H01695, JP19J22363, JP20J14338.

Authors and Affiliations

1. Tokyo Institute of Technology, Tokyo, Japan

   Kyohei Sudo, Masayuki Tezuka, Keisuke Hara, Yusuke Yoshida & Keisuke Tanaka

2. National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

   Keisuke Hara

Corresponding author

Correspondence toKyohei Sudo.

Editors and Affiliations

1. Nanyang Technological University, Singapore, Singapore

   Khoa Nguyen

2. Chinese Academy of Sciences, Beijing, China

   Wenling Wu

3. Nanyang Technological University, Singapore, Singapore

   Kwok Yan Lam

4. Nanyang Technological University, Singapore, Singapore

   Huaxiong Wang

A Basic Cryptographic Primitives

1.1A.1 Public Key Encryption

A public key encryption scheme\(\mathsf {PKE}\) with a message space\(\mathcal {M}\) is a tuple of PPT algorithms\((\mathsf {PKE.Gen}, \mathsf {PKE.Enc}, \mathsf {PKE.Dec})\).

• \(\mathsf {PKE.Gen}(1^{\lambda }) \rightarrow (\mathsf {ek}, \mathsf {dk}) :\) Given a security parameter\(1^{\lambda }\) as input, the key generation algorithm outputs a encryption/decryption key pair\((\mathsf {ek}, \mathsf {dk})\).

• \(\mathsf {PKE.Enc}(\mathsf {ek}, m) \rightarrow c :\) Given an encryption key\(\mathsf {ek}\) and a plaintextm as input, the encryption algorithm outputs a ciphertextc.

• \(\mathsf {PKE.Dec}(\mathsf {dk}, c) \rightarrow m/\bot :\) Given a decryption key\(\mathsf {dk}\) and a ciphertextc as input, the decryption algorithm outputs a messagem or invalid symbol\(\bot \).

• Correctness\(\mathsf {PKE}\) satisfies correctness if for all\(m \in \mathcal {M}\),\(\Pr [\mathsf {PKE.Dec}(\mathsf {dk}, c) = m :(\mathsf {ek}, \mathsf {dk}) \leftarrow \mathsf {PKE.Gen}(1^\lambda ), c \leftarrow \mathsf {PKE.Enc}(\mathsf {ek}, m)] = 1\) holds.

• variant of IND-CPA For any PPT adversary\(\mathcal {A}\),

  $$\begin{aligned} \mathsf{Adv}^{\mathsf {ind}\text {-}\mathsf {cpav}}_{\mathsf {PKE}, \mathcal {A}} := \left| \Pr \left[ b=b' : \begin{aligned}&(\mathsf {ek}, \mathsf {dk}) \leftarrow \mathsf {PKE.Gen}(1^\lambda ), (m_0, m_1) \leftarrow \mathcal {A}(\mathsf {ek}),\\&b \leftarrow \{0, 1\}, c_b \leftarrow \mathsf {PKE.Enc}(\mathsf {ek}, m_0),\\&c_b\oplus 1 \leftarrow \mathsf {PKE.Enc}(\mathsf {ek}, m_1), b' \leftarrow \mathcal {A}(c_0, c_1) \end{aligned}\right] - \frac{1}{2} \right| \end{aligned}$$

  is\(\mathsf {negl}(\lambda )\). This security is equivalent to the general one.

1.2A.2 Digital Signature

A digital signature scheme\(\mathsf {DS}\) with a message space\(\mathcal {M}\) is a tuple of PPT algorithms\((\mathsf {DS.Gen}, \mathsf {DS.Sign}, \mathsf {DS.Verify})\).

• \(\mathsf {DS.Gen}(1^{\lambda }) \rightarrow (\mathsf {vk}, \mathsf {sk}) :\) Given a security parameter\(1^{\lambda }\) as input, the key generation algorithm outputs a verification/signing key pair\((\mathsf {vk}, \mathsf {sk})\).

• \(\mathsf {DS.Sign}(\mathsf {sk}, m) \rightarrow \sigma :\) Given a signing key\(\mathsf {sk}\) and a messagem as input, the signing algorithm outputs a signature\(\sigma \).

• \(\mathsf {DS.Verify}(\mathsf {vk}, m, \sigma ) \rightarrow 0/1: \) Given a verification key\(\mathsf {vk}\), a messagem, and a signature\(\sigma \) as input, the verification algorithm outputs 0 or 1.

• Correctness\(\mathsf {DS}\) satisfies correctness if for all\(m \in \mathcal {M}\),\(\Pr [\mathsf {DS.Verify}(\mathsf {vk}, m, \sigma ) = 1 :(\mathsf {vk}, \mathsf {sk}) \leftarrow \mathsf {DS.Gen}(1^\lambda ), \sigma \leftarrow \mathsf {DS.Sign}(\mathsf {sk}, m) ] = 1\)

• sEUF-CMA The\(\mathrm {sEUF}\text {-}\mathrm {CMA}\) security for\(\mathsf {DS}\) is defined by the following game between a challenger and a PPT adversary\(\mathcal {A}\).

  1. 1.

     The challenger runs\((\mathsf {vk}, \mathsf {sk}) \leftarrow \mathsf {DS.Gen}(1^{\lambda })\), initializes a list\(Q \leftarrow \{\}\), and gives\(\mathsf {vk}\) to\(\mathcal {A}\).

  2. 2.

     Throughout the entire game,\(\mathcal {A}\) is given access to signing oracle\(\mathsf {DS.Sign}(\mathsf {sk}, \cdot )\). Given an inputm, the signing oracle runs\(\sigma \leftarrow \mathsf {DS.Sign}(\mathsf {sk}, m)\), updates\(Q \leftarrow Q \cup \{(m, \sigma )\}\), and returns\(\sigma \) to\(\mathcal {A}\)

  3. 3.

     \(\mathcal {A}\) outputs a forgery\((m^{*}, \sigma ^{*})\).

  \(\mathsf {DS}\) satisfies the\(\mathrm {sEUF}\text {-}\mathrm {CMA}\) security if for all PPT adversaries\(\mathcal {A}\),\(\mathsf{Adv}^{\mathsf {unf}}_{\mathsf {DS}, \mathcal {A}} := \Pr [\mathsf {DS.Verify}(\mathsf {vk}, m^{*}, \sigma ^{*})=1 \wedge (m^{*}, \sigma ^{*}) \notin Q] \le \mathsf {negl}(\lambda )\) holds.

B Watermarkable Signature in Previous Works

To compare with watermarkable signature in previous works, we describe formal definitions of watermarkable signature proposed by Goyal et al. [8] and Cohen et al. [6].

1.1B.1 Definition by Goyal et al. [8]

Definition 9 (Watermarkable Signature)

A watermarkable signature scheme with a message space\(\mathcal {M}\) and a mark space\(\mathcal {T}\) is a tuple of PPT algorithms\((\mathsf {WMSetup}, \mathsf {SigSetup}, \mathsf {Sign}, \mathsf {Verify}, \mathsf {Mark}, \mathsf {Extract})\).

Definition 10 (Correctness)

For any\(m \in \mathcal {M}\) and\(\tau \in \mathcal {T}\),

holds.

Definition 11 (Meaningfulness)

Meaningfulness requires the following two properties holds.

1. 1.

   For all fixed circuits\(C : \mathcal {M} \rightarrow \mathbb {SIG}\)^Footnote1,

   $$\begin{aligned} \Pr \left[ \mathsf {Extract}(\mathsf {xk}, \mathsf {vk}, C) \ne \bot : \begin{aligned}&(\mathsf {wpp}, \mathsf {mk}, \mathsf {xk}) \leftarrow \mathsf {WMSetup}(1^\lambda ), \\&(\mathsf {sk}, \mathsf {vk}) \leftarrow \mathsf {SigSetup}(1^{\lambda }, \mathsf {wpp})\end{aligned}\right] \le \mathsf {negl}(\lambda ) \end{aligned}$$
2. 2.
   $$\begin{aligned} \Pr \left[ \mathsf {Extract}(\mathsf {xk}, \mathsf {vk}, \mathsf {Sign}(\mathsf {sk}, \cdot )) \ne \bot : \begin{aligned}&(\mathsf {wpp}, \mathsf {mk}, \mathsf {xk}) \leftarrow \mathsf {WMSetup}(1^\lambda ), \\&(\mathsf {sk}, \mathsf {vk}) \leftarrow \mathsf {SigSetup}(1^{\lambda }, \mathsf {wpp})\end{aligned}\right] \le \mathsf {negl}(\lambda ) \end{aligned}$$

Definition 12 (Function Preserving)

For any\(m \in \mathcal {M}\) and\(\tau \in \mathcal {T}\),

holds.

Definition 13 (Unforgeability)

For any PPT adversary\(\mathcal {A}\),

holds, where\(\mathcal {Q} \subseteq \mathcal {M}\) is the set of messages\(\mathcal {A}\) submitted to the signing oracle.

Definition 14 (Unremovability)

For any PPT adversary\(\mathcal {A}\),

holds, where\(\mathcal {Q} \subseteq \mathcal {M}\) is the set of messages\(\mathcal {A}\) submitted to the Mark oracle.\(\mathcal {A}\) is said to be\(\epsilon \)-unremovable admissible if the circuit\(C^*\) it outputs is an\(\epsilon \)-good signer for key\(\mathsf {vk}\). Here we say that\(C^*\) is an\(\epsilon \)-good signer circuit for key\(\mathsf {vk}\) if the following\(\Pr \left[ \mathsf {Verify}(\mathsf {vk}, m, C^*(m)) = 1: m \leftarrow \mathcal {M}\right] \ge \epsilon \) holds.

1.2B.2 Definition by Cohen et al. [6]

Definition 15 (Watermarkable Signature)

A watermarkable signature scheme with a message space\(\mathcal {M}\) and a mark space\(\mathcal {T}\) is tuple of PPT algorithms\((\mathsf {WMSetup},\mathsf {SigSetup}, \mathsf {Sign}, \mathsf {Verify}, \mathsf {Extract})\).

Definition 16 (Correctness)

For any\(\lambda \in \mathbb {N}\),\(m \in \mathcal {M}\), and\(\tau \in \mathcal {T}\),

holds.

Definition 17 ((Selective) Unforgeability)

For any PPT adversary\(\mathcal {A}\),

holds where\(\mathsf {Sign}_{m^*}(\mathsf {sk}, \cdot )\) is an oracle that signs any message except for\(m^*\).

Definition 18 (Unremovability)

For any PPT adversary\(\mathcal {A}\) and for any mark\(\tau \),

holds, where\(C^* \approx _\epsilon \mathsf {Sign}_\mathsf {sk}\) denotes\(C^*\) and\(\mathsf {Sign}_\mathsf {sk}\) agree on\(\epsilon \) fraction of their inputs.

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics