research-article

Public Access

Watermarking cryptographic capabilities

Authors:

Justin Holmgren,

Vinod Vaikuntanathan,

Daniel WichsAuthors Info & Claims

STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

Pages 1115 - 1127

https://doi.org/10.1145/2897518.2897651

Published: 19 June 2016 Publication History

Abstract

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF key K, we create a marked program C that evaluates the PRF F(K,). An adversary that gets C cannot come up with any program C* in which the mark is removed but which still evaluates the PRF correctly on even a small fraction of the inputs. The work of Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO'01 and Journal of ACM 59(2)) shows that, assuming indistinguishability obfuscation (iO), such watermarking is impossible if the marked program C evaluates the original program with perfect correctness. In this work we show that, assuming iO, such watermarking is possible if the marked program C is allowed to err with even a negligible probability, which would be undetectable to the user. Our watermarking schemes are public key, namely we use a secret marking key to embed marks in programs, and a public detection key that allows anyone to detect marks in programs. Our schemes are secure against chosen program attacks, that is even if the adversary is given oracle access to the marking functionality. We emphasize that our security notion of watermark non-removability considers arbitrary adversarial strategies to modify the marked program, in contrast to the prior works (Nishimaki, EUROCRYPT '13).

References

[1]

{AKV03} André Adelsbach, Stefan Katzenbeisser, and Helmut Veith. Watermarking schemes provably secure against copy and ambiguity attacks. In Moti Yung, editor, Proceedings of the 2003 ACM workshop on Digital rights management 2003, Washington, DC, USA, October 27, 2003, pages 111–119. ACM, 2003.

Digital Library

[2]

10 Observed by Nir Bitansky. {BFP + 15} Abhishek Banerjee, Georg Fuchsbauer, Chris Peikert, Krzysztof Pietrzak, and Sophie Stevens. Key-homomorphic constrained pseudorandom functions. In Dodis and Nielsen {DN15}, pages 31–60. {BGI + 01} Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, pages 1–18, 2001.

Digital Library

[3]

{BGI + 12} Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6, 2012.

Digital Library

[4]

{BGI14} Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, pages 501–519, 2014.

[5]

{BLMR13} Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. Key homomorphic prfs and their applications. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 410–428. Springer, 2013.

[6]

{BV15} Zvika Brakerski and Vinod Vaikuntanathan. Constrained key-homomorphic prfs from standard lattice assumptions - or: How to secretly embed a circuit in your PRF. In Dodis and Nielsen {DN15}, pages 1–30. {BW13} Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II, pages 280–300, 2013.

[7]

{CHV15} Aloni Cohen, Justin Holmgren, and Vinod Vaikuntanathan. Publicly verifiable software watermarking. IACR Cryptology ePrint Archive, 2015:373, 2015.

[8]

{CS03} Ronald Cramer and Victor Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM Journal on Computing, 33(1):167–226, 2003.

Digital Library

[9]

{DN15} Yevgeniy Dodis and Jesper Buus Nielsen, editors. Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II, volume 9015 of Lecture Notes in Computer Science. Springer, 2015.

[10]

{HMW07} Nicholas Hopper, David Molnar, and David Wagner. From weak to strong watermarking. In Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings, pages 362–382, 2007.

Digital Library

[11]

{Kei70} Thomas Keightley. The Fairy Mythology: Illustrative of the Romance and Superstition of Various Countries. 1870. Retrieved from: http://www.sacred-texts.com/neu/celt/tfm/: 2 November 2015.

[12]

{KL93} Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807–837, 1993.

Digital Library

[13]

{KPTZ13} Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013, pages 669–684. ACM, 2013.

Digital Library

[14]

{KVH00} M. Kutter, S. Voloshynovskiy, and A. Herrigel. The watermark copy attack. In Proceedings of the SPIE, Security and Watermarking of Multimedia Contents II, volume 3971, pages 371–379, 2000.

[15]

{Nis13} Ryo Nishimaki. How to watermark cryptographic functions. In Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, pages 111–125, 2013. Full version available from http://eprint.iacr.org/2014/472. {NSS99} David Naccache, Adi Shamir, and Julien P. Stern. How to copyright a function? In Public Key Cryptography, Second International Workshop on Practice and Theory in Public Key Cryptography, PKC ’99, Kamakura, Japan, March 1-3, 1999, Proceedings, pages 188–196, 1999.

Digital Library

[16]

{NW15} Ryo Nishimaki and Daniel Wichs. Watermarking cryptographic programs against arbitrary removal strategies. IACR Cryptology ePrint Archive, 2015:344, 2015.

[17]

{SW14} Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 475–484, 2014. Full version available from http://eprint.iacr.org/2013/454. {Val84} Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.

Digital Library

[18]

{YF11} Maki Yoshida and Toru Fujiwara. Toward digital watermarking for cryptographic data. IEICE Transactions, 94-A(1):270–272, 2011.

Cited By

Bock EBrzuska CLai R(2024)Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom GeneratorsIACR Communications in Cryptology10.62056/aevur-10kOnline publication date: 8-Jul-2024
https://doi.org/10.62056/aevur-10k
Luo YZhou TCui SYe YLiu FCai Z(2024)Fixing the Double Agent Vulnerability of Deep Watermarking: A Patch-Level Solution Against Artwork PlagiarismIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.329589534:3(1670-1683)Online publication date: Mar-2024
https://doi.org/10.1109/TCSVT.2023.3295895
Cho HZhang LJiang X(2024)Digital Watermarking Technology of Data Element Circulation Transaction2024 IEEE 10th International Conference on Edge Computing and Scalable Cloud (EdgeCom)10.1109/EdgeCom62867.2024.00008(1-6)Online publication date: 28-Jun-2024
https://doi.org/10.1109/EdgeCom62867.2024.00008
Show More Cited By

Index Terms

Watermarking cryptographic capabilities

Recommendations

Watermarking Cryptographic Capabilities

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of ...
Visible watermarking with reversibility of multimedia images for ownership declarations

Digital watermarking technology is primarily the joining of the rightful owner of the protected media. Once the media are suspected to be illegally used, an open algorithm can be used to extract the digital watermark for the purpose of showing the media'...
Equipping Public-Key Cryptographic Primitives with Watermarking (or: A Hole Is to Watermark)
Theory of Cryptography
Abstract
Program watermarking enables users to embed an arbitrary string called a mark into a program while preserving the functionality of the program. Adversaries cannot remove the mark without destroying the functionality. Although there exist generic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

June 2016

1141 pages

ISBN:9781450341325

DOI:10.1145/2897518

General Chair:
Daniel Wichs
Northeastern, USA
,
Program Chair:
Yishay Mansour
Tel Aviv

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
U.S. Army Research Office

Conference

STOC '16

Sponsor:

SIGACT

STOC '16: Symposium on Theory of Computing

June 19 - 21, 2016

MA, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
686
Total Downloads

Downloads (Last 12 months)240
Downloads (Last 6 weeks)21

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bock EBrzuska CLai R(2024)Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom GeneratorsIACR Communications in Cryptology10.62056/aevur-10kOnline publication date: 8-Jul-2024
https://doi.org/10.62056/aevur-10k
Luo YZhou TCui SYe YLiu FCai Z(2024)Fixing the Double Agent Vulnerability of Deep Watermarking: A Patch-Level Solution Against Artwork PlagiarismIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.329589534:3(1670-1683)Online publication date: Mar-2024
https://doi.org/10.1109/TCSVT.2023.3295895
Cho HZhang LJiang X(2024)Digital Watermarking Technology of Data Element Circulation Transaction2024 IEEE 10th International Conference on Edge Computing and Scalable Cloud (EdgeCom)10.1109/EdgeCom62867.2024.00008(1-6)Online publication date: 28-Jun-2024
https://doi.org/10.1109/EdgeCom62867.2024.00008
Liu JZhandry M(2024)Composability in Watermarking SchemesTheory of Cryptography10.1007/978-3-031-78020-2_14(400-430)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_14
HUO WYU YYANG KZHENG ZLI XYAO LXIE J(2023)Privacy-preserving cryptographic algorithms and protocols: a survey on designs and applicationsSCIENTIA SINICA Informationis10.1360/SSI-2022-043453:9(1688)Online publication date: 6-Sep-2023
https://doi.org/10.1360/SSI-2022-0434
Wei JChen XWang JHuang XSusilo W(2023)Securing Fine-Grained Data Sharing and Erasure in Outsourced Storage SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.322527434:2(552-566)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TPDS.2022.3225274
Slamanig DStriecks C(2023)Revisiting Updatable Encryption: Controlled Forward Security, Constructions and a Puncturable PerspectiveTheory of Cryptography10.1007/978-3-031-48618-0_8(220-250)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48618-0_8
Yang R(2023)Privately Puncturing PRFs from Lattices: Adaptive Security and Collusion Resistant PseudorandomnessAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30620-4_6(163-193)Online publication date: 15-Apr-2023
https://doi.org/10.1007/978-3-031-30620-4_6
Dutta PJiang MDuong DSusilo WFukushima KKiyomoto SSuga YSakurai KDing XSako K(2022)Hierarchical Identity-based Puncturable Encryption from Lattices with Application to Forward SecurityProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3517400(408-422)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3517400
Wei JChen XWang JHu XMa J(2022)Enabling (End-to-End) Encrypted Cloud Emails With Practical Forward SecrecyIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2021.305549519:4(2318-2332)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TDSC.2021.3055495
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten