Abstract
We introduce the notion of sanitizable signatures that offer many attractive security features for certain current and emerging applications. A sanitizable signature allows authorized semi-trusted censors to modify – in a limited and controlled fashion – parts of a signed message without interacting with the original signer. We present constructions for this new primitive, based on standard signature schemes and secure under common cryptographic assumptions. We also provide experimental measurements for the implementation of a sanitizable signature scheme and demonstrate its practicality.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ateniese, G., de Medeiros, B.: On the key exposure problem in chameleon hashes. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 165–179. Springer, Heidelberg (2005), Full version: Cryptology ePrint Archive, Report 2004/243 http://eprint.iacr.org/2004/243
Ateniese, G., de Medeiros, B.: Identity-based chameleon hash and applications. In: Juels, A. (ed.) FC 2004. LNCS, vol. 3110, pp. 164–180. Springer, Heidelberg (2004)
Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography: The case of hashing and signing. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 216–233. Springer, Heidelberg (1994)
Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography with application to virus protection. In: Proc. of the Twenty-Seventh Annual ACM Symposium on Theory of Computing (FOCS 1995), pp. 45–56. ACM Press, New York (1995)
Bellare, M., Micciancio, D.: A new paradigm for collision-free hashing: Incrementality at reduced cost. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 163–192. Springer, Heidelberg (1997)
Bellare, M., Neven, G.: Transitive signatures based on factoring and RSA. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 397–414. Springer, Heidelberg (2002)
Bellare, M., Rogaway, P.: PSS: Provably secure encoding method for digital signature. IEEE P1363a: Provably secure signatures (1998), http://grouper.ieee.org/groups/1363/p1363a/pssigs.html
Bishop, M., Bhumiratana, B., Crawford, R., Levitt, K.: How to Sanitize Data. In: Proceedings of the 13th IEEE International Workshops on Enabling Technologies: Infrastructures for Collaborative Enterprises (WETICE-2004), Modena, Italy, pp. 217–222 (June 2004)
Boyar, J., Chaum, D., Damgård, I.B., Pedersen, T.P.: Convertible undeniable signatures. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 189–205. Springer, Heidelberg (1990)
Burmester, M., van Le, T.: Secure communications in Ad-hoc networks. In: Proc. of the 5th IEEE Information Assurance Workshop (IAW 2005), pp. 234–241 (2004)
Crypto++ Library 5.2.1., http://www.eskimo.com/weidai/cryptlib.html
Chari, S., Rabin, T., Rivest, R.: An efficient signature scheme for route aggregation. Unpublished manuscript (2002), http://theory.lcs.mit.edu/~rivest/publications.html
Chaum, D.: Zero-knowledge undeniable signatures. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 458–464. Springer, Heidelberg (1990)
Chaum, D., Antwerpen, H.: Undeniable signatures. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 212–216. Springer, Heidelberg (1990)
Chaum, D., van Heijst, E., Pfitzmann, B.: Cryptographically strong undeniable signatures, unconditionally secure for the signer. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 470–484. Springer, Heidelberg (1991)
Chen, X., Zhang, F., Kim, K.: Chameleon hashing without key exposure. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 87–98. Springer, Heidelberg (2004)
Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)
Haber, S., Stornetta, W.S.: How to time-stamp a digital document. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 437–455. Springer, Heidelberg (1991)
Hacigümus, H., Iyer, B.R., Mehrotra, S.: Executing SQL over encrypted data in the database-service-provider model. In: Proc. Intern. Conf. Management of Data (ACM SIGMOD 2002), pp. 216–227. ACM Press, New York (2002)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (2001)
Mykletun, E., Narasimha, M., Tsudik, G.: Authentication and Integrity in Outsourced Databases. In: Proc. of the Network and Distributed System Security Symposium (NDSS 2004), Internet Society (ISOC) Press, p. 10 (2004), http://www.isoc.org/isoc/conferences/ndss/04/proceedings/Papers/Mykletun.pdf
Johnson, D., Maltz, D.: Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing (1996)
Johnson, R., Molnar, D., Song, D., Wagner, D.: Homomorphic signature schemes. In: Preneel, B. (ed.) Topics in Cryptology–CT-RSA 2002. LNCS, vol. 2771, pp. 244–262. Springer, Heidelberg (2002)
Kent, S., Lynn, C., Seo, K.: Secure Border Gateway Protocol (Secure-BGP), IEEE Journal on Selected Areas in Communications (April 2000)
Krawczyk, H., Rabin, T.: Chameleon signatures. In: Proceedings of the Network and Distributed Systems Security Symposium (NDSS 2000), pp. 143–154 (2000)
Micali, S., Rivest, R.: Transitive signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 236–243. Springer, Heidelberg (2002)
Murphy, S.L., Badger, M.R., Wellington, B.: OSPF with digital signatures. Internet Engineering Task Force (IETF) Request for Comments (RFC) 2154 (June 1997)
Naccache, D., Pointcheval, D., Stern, J.: Twin signatures: An alternative to the hash-and-sign paradigm. In: Samarati, P. (ed.) Proceedings of the Eighth Annual ACM Conference on Computer and Communications Security, pp. 20–27. ACM Press, New York (2001)
Nyberg, K., Rueppel, R.A.: Message recovery for signature schemes based on the discrete logarithm problem. Designs, Codes, and Cryptography 7(1–2), 61–81 (1996)
Pang, R., Paxson, V.: A High-level Programming Environment for Packet Trace Anonymization and Transformation. In: Proc. ACM SIGCOMM 2003 (2003)
Perlman, R.: Network layer protocols with Byzantine robustness. Ph.D. thesis, Dept. of Elect. Eng. and Comp. Sci., Massachusetts Institute of Technology (August 1988)
Peuhkuri, M.: A method to compress and anonymize packet traces. In: Proceedings of the ACM SIGCOMM Internet Measurement Workshop (November 2001)
Rekhter, Y., Li, T.: Border Gateway Protocol 4 (BGP-4), Internet Engineering Task Force (IETF) Request for Comments (RFC) 1771 (March 1995)
Rivest, R.: Two signature schemes. Slides from talk given at Cambridge University, October 17 (2000), http://theory.lcs.mit.edu/~rivest/publications.html
RSA Labs: RSA Cryptography Standard: EMSAPSS – PKCS#1 v2.1. (2002)
Steinfeld, R., Bull, L., Zheng, Y.: Content extraction signatures. In: Kim, K. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 285–304. Springer, Heidelberg (2002)
Shahandashti, S.F., Salmasizadeh, M., Mohajeri, J.: A provably secure short transitive signature scheme from bilinear group pairs. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 60–76. Springer, Heidelberg (2005)
United States of America Department of Health and Human Services. Standards for Privacy of Individually Identifiable Health Information: Final Rule, Federal Register 67(157), August 14 (2002)
Xu, J., Fan, J., Ammar, M., Moon, S.B.: On the design and performance of prefix preserving IP traffic trace anonymization. In: Proceedings of the ACM SIGCOMM Internet Measurement Workshop (November 2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ateniese, G., Chou, D.H., de Medeiros, B., Tsudik, G. (2005). Sanitizable Signatures. In: di Vimercati, S.d.C., Syverson, P., Gollmann, D. (eds) Computer Security – ESORICS 2005. ESORICS 2005. Lecture Notes in Computer Science, vol 3679. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11555827_10
Download citation
DOI: https://doi.org/10.1007/11555827_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28963-0
Online ISBN: 978-3-540-31981-8
eBook Packages: Computer ScienceComputer Science (R0)