Paper 2022/631

Watermarking PRFs against Quantum Adversaries

Fuyuki Kitagawa and Ryo Nishimaki

Abstract

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 software watermarking against classical adversaries, a message extraction algorithm crucially uses the (input-output) behavior of a classical pirate software to extract an embedded message. Even if we instantiate existing watermarking PRFs with quantum-safe building blocks, it is not clear whether they are secure against quantum adversaries due to the quantum-specific property above. Thus, we need entirely new techniques to achieve software watermarking against quantum adversaries. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Keywords
watermarkingpseudorandom functionpost-quantum cryptography
Contact author(s)
fuyuki kitagawa yh @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp
ryo nishimaki @ gmail com
History
2022-05-23: received
Short URL
https://ia.cr/2022/631
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/631,
      author = {Fuyuki Kitagawa and Ryo Nishimaki},
      title = {Watermarking PRFs against Quantum Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2022/631},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/631}},
      url = {https://eprint.iacr.org/2022/631}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.