A Watermarking Signature Scheme with Hidden Watermarks and Constraint Functions in the Symmetric Key Setting

Authors: Yanmin Zhao, Siu Ming Yiu

Abstract:

To claim the ownership for an executable program is a non-trivial task. An emerging direction is to add a watermark to the program such that the watermarked program preserves the original program’s functionality and removing the watermark would heavily destroy the functionality of the watermarked program. In this paper, the first watermarking signature scheme with the watermark and the constraint function hidden in the symmetric key setting is constructed. The scheme uses well-known techniques of lattice trapdoors and a lattice evaluation. The watermarking signature scheme is unforgeable under the Short Integer Solution (SIS) assumption and satisfies other security requirements such as the unremovability security property.

Keywords: Short integer solution problem, signatures, the symmetric-key setting, watermarking schemes.

References:

[1] A. Adelsbach, S. Katzenbeisser, and H. Veith, “Watermarking schemes provably secure against copy and ambiguity attacks,” in Proceedings of the 3rd ACM workshop on Digital rights management. ACM, 2003, pp. 111–119.
[2] C. I. Podilchuk and E. J. Delp, “Digital watermarking: algorithms and applications,” IEEE signal processing Magazine, vol. 18, no. 4, pp. 33– 46, 2001.
[3] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang, “On the (im) possibility of obfuscating programs,” in Annual International Cryptology Conference. Springer, 2001, pp. 1–18.
[4] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang, “On the (im) possibility of obfuscating programs,” Journal of the ACM (JACM), vol. 59, no. 2, p. 6, 2012.
[5] A. Cohen, J. Holmgren, R. Nishimaki, V. Vaikuntanathan, and D. Wichs, “Watermarking cryptographic capabilities,” in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. ACM, 2016, pp. 1115–1127.
[6] D. Naccache, A. Shamir, and J. P. Stern, “How to copyright a function?” in International Workshop on Public Key Cryptography. Springer, 1999, pp.188–196.
[7] M. Yoshida and T. Fujiwara, “Toward digital watermarking for cryp-tographic data,” IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 94, no. 1, pp. 270–272, 2011.
[8] R. Nishimaki, “How to watermark cryptographic functions,” in Annual International Conference on the Theory and Applications of Crypto-graphic Techniques. Springer, 2013, pp. 111–125.
[9] S. Kim and D. J. Wu, “Watermarking cryptographic functionalities from standard lattice assumptions,” in Annual International Cryptology Conference. Springer, 2017, pp. 503–536.
[10] W. Quach, D. Wichs, and G. Zirdelis, “Watermarking prfs under standard assumptions: Public marking and security with extraction queries,” in Theory of Cryptography Conference. Springer, 2018, pp. 669–698.
[11] R. Yang, M. H. Au, J. Lai, Q. Xu, and Z. Yu, “Collusion resistant watermarking schemes for cryptographic functionalities,” in Interna-tional Conference on the Theory and Application of Cryptology and Information Security. Springer, 2019, pp. 371–398.
[12] S. Kim and D. J. Wu, “Watermarking prfs from lattices: Stronger security via extractable prfs,” in Annual International Cryptology Conference. Springer, 2019, pp. 335–366.
[13] F. Baldimtsi, A. Kiayias, and K. Samari, “Watermarking public-key cryptographic functionalities and implementations,” in International Conference on Information Security. Springer, 2017, pp. 173–191.
[14] R. Goyal, S. Kim, N. Manohar, B. Waters, and D. J. Wu, “Watermarking public-key cryptographic primitives,” in Annual International Cryptolo-gy Conference. Springer, 2019, pp. 367–398.
[15] N. Hopper, D. Molnar, and D. Wagner, “From weak to strong water-marking,” in Theory of Cryptography Conference. Springer, 2007, pp. 362–382.
[16] M. Ajtai, “Generating hard instances of lattice problems,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996, pp. 99–108.
[17] D. Micciancio, “Almost perfect lattices, the covering radius problem, and applications to ajtai’s connection factor,” SIAM Journal on Computing, vol. 34, no. 1, pp. 118–169, 2004.
[18] D. Micciancio and O. Regev, “Worst-case to average-case reductions based on gaussian measures,” SIAM Journal on Computing, vol. 37, no. 1, pp. 267–302, 2007.
[19] D. Micciancio and C. Peikert, “Hardness of sis and lwe with small parameters,” in Advances in Cryptology–CRYPTO 2013. Springer, 2013, pp. 21–39.
[20] R. Tsabary, “An equivalence between attribute-based signatures and homomorphic signatures, and new constructions for both,” in Theory of Cryptography Conference. Springer, 2017, pp. 489–518.
[21] D. Micciancio and C. Peikert, “Trapdoors for lattices: Simpler, tighter, faster, smaller,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2012, pp. 700– 718.
[22] S. Agrawal, D. Boneh, and X. Boyen, “Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical ibe,” in Annual Cryptology Conference. Springer, 2010, pp. 98–115.
[23] S. Agrawal, D. Boneh, and X. Boyen, “Efficient lattice (h) ibe in the standard model,” in Annual Inter-national Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2010, pp. 553–572.
[24] C. Gentry, A. Sahai, and B. Waters, “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based,” in Advances in Cryptology–CRYPTO 2013. Springer, 2013, pp. 75–92.
[25] J. Alperin-Sheriff and C. Peikert, “Faster bootstrapping with polynomial error,” in International Cryptology Conference. Springer, 2014, pp. 297–314.
[26] D. Boneh, C. Gentry, S. Gorbunov, S. Halevi, V. Nikolaenko, G. Segev, V. Vaikuntanathan, and D. Vinayagamurthy, “Fully key-homomorphic encryption, arithmetic circuit abe and compact garbled circuits,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2014, pp. 533–556.
[27] S. Gorbunov, V. Vaikuntanathan, and D. Wichs, “Leveled fully homo-morphic signatures from standard lattices,” in Proceedings of the forty-seventh annual ACM symposium on Theory of computing. ACM, 2015, pp.469–477.
[28] Z. Brakerski and V. Vaikuntanathan, “Constrained key-homomorphic prfs from standard lattice assumptions,” in Theory of Cryptography Conference. Springer, 2015, pp. 1–30.
[29] Z. Brakerski, D. Cash, R. Tsabary, and H. Wee, “Targeted homomorphic attribute-based encryption,” in Theory of Cryptography Conference. Springer, 2016, pp. 330-360.
[30] Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” SIAM journal on computing, vol. 38, no. 1, pp. 97-139, 2008.