  We initiate the study of software watermarking against quantum adversaries. A
quantum adversary generates a quantum state as a pirate software that
potentially removes an embedded message from a classical marked software.
Extracting an embedded message from quantum pirate software is difficult since
measurement could irreversibly alter the quantum state.
  In this work, we define secure watermarking PRFs for quantum adversaries
(unremovability against quantum adversaries). We also present two watermarking
PRFs as follows.
  - We construct a privately extractable watermarking PRF against quantum
adversaries from the quantum hardness of the learning with errors (LWE)
problem. The marking and extraction algorithms use a public parameter and a
private extraction key, respectively. The watermarking PRF is unremovable even
if adversaries have (the public parameter and) access to the extraction oracle,
which returns a result of extraction for a queried quantum circuit.
  - We construct a publicly extractable watermarking PRF against quantum
adversaries from indistinguishability obfuscation (IO) and the quantum hardness
of the LWE problem. The marking and extraction algorithms use a public
parameter and a public extraction key, respectively. The watermarking PRF is
unremovable even if adversaries have the extraction key (and the public
parameter).
  We develop a quantum extraction technique to extract information (a classical
string) from a quantum state without destroying the state too much. We also
introduce the notion of extraction-less watermarking PRFs as a crucial building
block to achieve the results above by combining the tool with our quantum
extraction technique.
