nach oben

International Journal of Information Security

Erschienen in:

01.11.2013 | Regular Contribution

Privacy-preserving authentication of trees and graphs

verfasst von: Ashish Kundu, Elisa Bertino

Erschienen in: International Journal of Information Security | Ausgabe 6/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Secure data sharing in third-party environments such as the cloud requires that both authenticity and confidentiality of the data be assured, especially when such structures encode sensitive information (such as in XML documents). Existing authentication schemes for trees and directed acyclic graphs (DAGs) are authenticity-preserving, but not confidentiality-preserving, and lead to leakage of sensitive information during authentication. In this paper, we propose a family of three leakage-free authentication schemes for (1) tree data structures, (2) directed acyclic graphs (DAGs), and (3) graphs (with cycles), which are also efficient. This family of schemes referred to as the “structural signatures” is based on the structure of the tree as defined by tree traversals and aggregate signatures. We also show through complexity and performance analysis that our scheme is practical in terms of the cost for authentication of data. We have also discussed two applications of the proposed scheme: (1) automatic correction and recovery from structural errors, and (2) secure publish /subscribe of XML documents.

Vorheriger Artikel Off-line/on-line signatures revisited: a general unifying paradigm, efficient threshold variants and experimental results

Nächster Artikel Aggregate message authentication codes (AMACs) with on-the-fly verification

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The inference problem is a widely investigated problem in computer and information security [17].

A function \(\epsilon (k)\) is negligible in cryptography, if for every polynomial \(p(.)\), an integer \(N\) exists such that for all integers \(k > N\), it holds that \(\epsilon (k)\) \(< \frac{1}{p(k)}\) ([24]: Definition 3.4).

In cryptography, a technique that leads to only negligible leakage is provably non-leaking [24].

PBC and GMP are available at http://crypto.stanford.edu/pbc and http://gmplib.org, respectively.

Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R.H., Konwinski, A., Lee, G., Patterson, D.A., Rabkin, A., Zaharia, M.: Above the Clouds: A berkeley View of Cloud Computing. Tech. rep., University of California, Berkeley (2009)

Hacigumus, H., Mehrotra, S., Iyer, B.: Providing database as a service. In: ICDE (2002)

Devanbu, P., Gertz, M., Kwong, A., Martel, C., Nuckolls, G., Stubblebine, S.G.: Flexible authentication of XML documents. In: CCS (2001)

Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica 39(1) (2004)

Goodrich, M.T., Tamassia, R., Triandopoulos, N.: Efficient authenticated data structures for graph connectivity and geometric search problems. In: Algorithmica, vol. Online (2009).

Papamanthou, C., Tamassia, R., Triandopoulos, N.: Authenticated hash tables. In: CCS (2008)

Li, F., Hadjieleftheriou, M., Kollios, G., Reyzin, L.: Dynamic authenticated index structures for outsourced databases. In: SIGMOD (2006)

Mouratidis, K., Sacharidis, D., Pang, H.: Partially materialized digest scheme: an efficient verification method for outsourced databases. VLDB J. 18(1) (2009)

Merkle, R.C.: A certified digital signature. In: CRYPTO (1989)

10.

Atallah, M., Cho, Y., Kundu, A.: Efficient data authentication in an environment of untrusted third-party distributors. ICDE (2008)

11.

Goel, S.K., Clifton, C., Rosenthal, A.: Derived access control specification for XML. In: XMLSEC (2003)

12.

Wang, H., Lakshmanan, L.V.S.: Efficient secure query evaluation over encrypted XML databases. In: VLDB (2006)

13.

Ma, D., Deng, R.H., Pang, H., Zhou, J.: Authenticating query results in data publishing. In: ICICS (2005)

14.

Pang, H., Mouratidis, K.: Authenticating the query results of text search engines. PVLDB 1(1) (2008)

15.

Bertino, E., Carminati, B., Ferrari, E., Thuraisingham, B., Gupta, A.: Selective and authentic third-party distribution of XML documents. IEEE TKDE 16(10) (2004)

16.

Buldas, A., Laur, S.: Knowledge-binding commitments with applications in time-stamping. In: Public Key Cryptography (2007)

17.

Morgenstern, M.: Security and inference in multilevel database and knowledge-base systems. SIGMOD Rec. 16(3) (1987)

18.

Pang, H., Tan, K.: Authenticating query results in edge computing. In: ICDE (2004)

19.

Pang, H., Jain, A., Ramamritham, K., Tan, K.L.: Verifying completeness of relational query results in data publishing. In: SIGMOD (2005)

20.

Mykletun, E., Narasimha, M., Tsudik, G.: Authentication and integrity in outsourced databases. Trans. Storage 2(2), 107–138 (2006)CrossRef

21.

Narasimha, M., Tsudik, G.: Authentication of outsourced databases using signature aggregation and chaining. In: DASFAA (2006)

22.

Boneh, D., Gentry, C., Shacham, H., Lynn, B.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Eurocrypt (2003)

23.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2001)

24.

Katz, J., Lindell, Y.: Introduction to Modern Cryptography: Principles and Protocols, 1 edn. Chapman & Hall/CRC (2007)

25.

Knuth, D.E.: The Art of Computer Programming, vol. 1, third edn. Pearson Education, Asia (2002)

26.

Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order preserving encryption for numeric data. In: SIGMOD (2004)

27.

Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-preserving symmetric encryption. In: Eurocrypt (2009)

28.

Kamakoti, V., Rangan, C.P.: An optimal algorithm for reconstructing a binary tree. Inf. Process. Lett. 42(2) (1992)

29.

Das, S.K., Min, K.B., Halverson, R.H.: Efficient parallel algorithms for tree-related problems using the parenthesis matching strategy. In: IEEE ISPP (1994)

30.

Kundu, A., Bertino, E.: Structural signatures for tree data structures. PVLDB 1(1), 138–150 (2008)

31.

Kundu, A., Bertino, E.: A new model for secure dissemination of xml content. IEEE Trans. Syst. Man Cybern. Part C Appl. Rev. 38(3), 292–301 (2008)CrossRef

32.

Kundu, A., Bertino, E.: Secure dissemination of XML content using structure-based routing. In: IEEE EDOC (2006)

33.

Naor, M., Nissim, K.: Certificate revocation and certificate update. In: SSYM (1998)

34.

Harn, L.: Batch verifying multiple rsa digital signatures. Electron. Lett. 34(12) (1998)

35.

Hwang, M.S., Lin, I.C., Hwang, K.F.: Cryptanalysis of the batch verifying multiple rsa digital signatures. Informatica 11(1) (2000)

36.

Hwang, M.S., Lee, C.C., Tang, Y.L.: Two simple batch verifying multiple digital signatures. In: ICICS (2001)

37.

Bao, F., Lee, C.C., Hwang, M.S.: Cryptanalysis and improvement on batch verifying multiple rsa digital signatures. Appl. Math. Comput. 172(2) (2006)

38.

Goodrich, M., Tamassia, R.: Efficient authenticated dictionaries with skip lists and commutative hashing. Technical Report, Johns Hopkins Information Security Institute (2000)

39.

Goodrich, M.T., Tamassia, R., Triandopoulos, N., Cohen, R.: Authenticated data structures for graph and geometric searching. In: CT-RSA (2003)

40.

Kundu, A., Bertino, E.: How to authenticate graphs without leaking. In: EDBT (2010)

Titel: Privacy-preserving authentication of trees and graphs
verfasst von: Ashish Kundu
Elisa Bertino
Publikationsdatum: 01.11.2013
Verlag: Springer Berlin Heidelberg
Erschienen in: International Journal of Information Security / Ausgabe 6/2013
Print ISSN: 1615-5262
Elektronische ISSN: 1615-5270
DOI: https://doi.org/10.1007/s10207-013-0198-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Premium Partner