Leakage-free redactable signatures

ABSTRACT

Redactable signatures for linear-structured data such as strings have already been studied in the literature. In this paper, we propose a formal security model for leakage-free redactable signatures (LFRS) that is general enough to address authentication of not only trees but also graphs and forests. LFRS schemes have several applications, especially in enabling secure data management in the emerging cloud computing paradigm as well as in healthcare, finance and biological applications. We have also formally defined the notion of secure names. Such secure names facilitate leakage-free verification of ordering between siblings/nodes. The paper also proposes a construction for secure names, and a construction for leakagefree redactable signatures based on the secure naming scheme. The proposed construction computes a linear number of signatures with respect to the size of the data object, and outputs only one signature that is stored, transmitted and used for authentication of any tree, graph and forest.

References

1. G. Ateniese, D. H. Chou, B. de Medeiros, and G. Tsudik. Sanitizable signatures. In ESORICS, pages 159--177, 2005.
2. Mihir Bellare, Juan A. Garay, and Tal Rabin. Fast batch verification for modular exponentiation and digital signatures. In EUROCRYPT, 1998.
3. C. Brzuska, H. Busch, Ö. Dagdelen, M. Fischlin, M. Franz, S. Katzenbeisser, M. Manulis, C. Onete, A. Peter, B. Poettering, and D. Schröder. Redactable signatures for tree-structured data: Definitions and constructions. In ACNS, 2010.
4. Christina Brzuska, Marc Fischlin, Anja Lehmann, and Dominique Schröder. Unlinkability of sanitizable signatures. In Public Key Cryptography, 2010.
5. A. Buldas and S. Laur. Knowledge-binding commitments with applications in time-stamping. In Public Key Cryptography, pages 150--165, 2007.
6. L. Bull, P. Stanski, and D. McG. Squire. Content extraction signatures using xml digital signatures and custom transforms on-demand. In WWW, 2003.
7. Danielh. Chou, Breno De Medeiros, and Gene Tsudik. Sanitizable signatures. In ESORICS, 2005.
8. S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2), 1988.
9. S. Haber, Y. Hatano, Y. Honda, W. Horne, K. Miyazaki, T. Sander, S. Tezoku, and D. Yao. Efficient signature schemes supporting redaction, pseudonymization, and data deidentification. In ASIACCS, 2008.
10. R. Johnson, D. Molnar, D. Song, and D. Wagner. Homomorphic signature schemes. In In CT-RSA, 2002.
11. J. Katz and Y. Lindell. Introduction to Modern Cryptography: Principles and Protocols. Chapman & Hall/CRC, 2007.
12. A. Kundu and E. Bertino. Structural signatures for tree data structures. In VLDB, 2008.
13. A. Kundu and E. Bertino. How to authenticate graphs without leaking. In EDBT, 2010.
14. R. C. Merkle. A certified digital signature. In CRYPTO, 1989.
15. K. Miyazaki, G. Hanaoka, and H. Imai. Digitally signed document sanitizing scheme based on bilinear maps. In ASIACCS, 2006.
16. E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in outsourced databases. ACM Trans. of Storage, 2(2):107--138, 2006.
17. R. Rivest. "two new signature schemes", presented at cambridge seminar, 2001.

Index Terms

• Security and privacy

  • Database and storage security

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Theory of database privacy and security