Protocolo para transferência parcial de conhecimento e sua aplicação à verificação segura de marcas d’água

• Raphael Carlos Santos Machado INMETRO
• Davidson Rodrigo Boccardo INMETRO
• Vinícius Gusmão Pereira de Sá UFRJ
• Jayme Luiz Szwarcfiter UFRJ / INMETRO

DOI: https://doi.org/10.5753/sbseg.2014.20118

Abstract

Let y = f(x) for some one-way function f. We present a simple algorithm that allows that the bits of x are but partially exhibited in a demonstration, through a zero-knowledge proof scheme, that x is indeed an element of the preimage of y under f. As an application, we show that it is possible to disclose a watermark embedded into a digital artifact without the need of revealing its location. The result is a secure verification protocol for software watermarking which does not increase the likelihood that an attacker is successful in a removal attack.

References

Adelsbach, A., Katzenbeisser, S., and Sadeghi, A.-R. (2003). Watermark detection with zero-knowledge disclosure. Multimedia Syst., 9(3):266–278.

Adelsbach, A. and Sadeghi, A.-R. (2001). Zero-knowledge watermark detection and proof of ownership.

In Moskowitz, I. S., editor, Information Hiding, volume 2137 of Lecture Notes in Computer Science, pages 273–288. Springer.

Bento, L. M. S., Boccardo, D. R., Machado, R. C. S., de Sá, V. G. P., and Szwarcfiter, J. L. (2013). Towards a provably resilient scheme for graph-based watermarking. In Brandstädt, A., Jansen, K., and Reischuk, R., editors, WG, volume 8165 of Lecture Notes in Computer Science, pages 50–63. Springer.

Collberg, C. and Nagra, J. (2009). Surreptitious Software: Obfuscation, Watermarking, and Tamperproofing for Software Protection. Addison-Wesley Professional, 1st edition.

Craver, S. (1999). Zero knowledge watermark detection. In Pfitzmann, A., editor, Information Hiding, volume 1768 of Lecture Notes in Computer Science, pages 101–116. Springer.

Goldwasser, S., Micali, S., and Rackoff, C. (1985). The knowledge complexity of interactive proof-systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, pages 291–304, New York, NY, USA. ACM.

Hamilton, J. and Danicic, S. (2011). A survey of static software watermarking. Proc. World Congress on Internet Security, pages 100–107.

Karp, R. (1972). Reducibility among combinatorial problems. In Miller, R. and Thatcher, J., editors, Complexity of Computer Computations. Plenum Press, New York.

Kilian, J. (1990). Uses of randomness in algorithms and protocols. MIT Press.

Rabin, M. O. (1981). How to exchange secrets with oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory.

Schaefer, T. J. (1978). The complexity of satisfiability problems. In 10th annual ACM symposium on Theory of Computing, pages 216–226. ACM.

Tseitin, G. (1983). On the complexity of derivation in propositional calculus. In Siekmann, J. and Wrightson, G., editors, Automation of Reasoning, Symbolic Computation, pages 466–483. Springer Berlin Heidelberg.

Venkatachalam, B. (2005). Software watermarking as a proof of identity: A study of zero knowledge proof based software watermarking. In Barni, M., Cox, I. J., Kalker, T., and Kim, H. J., editors, IWDW, volume 3710 of Lecture Notes in Computer Science, pages 299–312. Springer.

Zhu, W., Thomborson, C. D., and Wang, F.-Y. (2005). A survey of software watermarking. In Kantor, P. B., Muresan, G., Roberts, F. S., Zeng, D. D., Wang, F.-Y., Chen, H., and Merkle, R. C., editors, Proc. IEEE Int’l Conference on Intelligence and Security Informatics, volume 3495 of ISI’05, pages 454–458. Springer.