Abstract
Assuming P < GI < NP, the creation and verification of a digital signature of an arbitrary RDF graph cannot be done in polynomial time. However, it is possible to define a large class of canonicalizable RDF graphs, such that digital signatures for graphs in this class can be created and verified in O(nlog(n)). Without changing its meaning, an arbitrary RDF graph can be nondeterministically pre-canonicalized into a graph of this class, before signing. The techniques in this paper are key enablers for the use of digital signature technology in the Semantic Web.
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
Klyne, G., Carroll, J.J. (eds.): RDF Concepts and Abstract Syntax. W3C (2003)
Köbler, J., Schöning, U., Torán, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser, Basel (1993)
Messmer, B.T., Bunke, H.: Subgraph Isomorphism Detection in Polynomial Time on Preprocessed Model Graphs. In: Li, S., Teoh, E.-K., Mital, D., Wang, H. (eds.) ACCV 1995. LNCS, vol. 1035, pp. 373–382. Springer, Heidelberg (1995)
Grant, J., Beckett, D. (eds.): RDF Test Cases. W3C Working Draft (2002), http://www.w3.org/TR/2002/WD-rdf-testcases-20021112/
Carroll, J.J.: Matching RDF Graphs. In: Horrocks, I., Hendler, J. (eds.) ISWC 2002. LNCS, vol. 2342, pp. 5–15. Springer, Heidelberg (2002)
Read, R.C., Corneil, D.G.: Graph Isomorphism Disease. Journal of Graph Theory, 339–363 (1977)
Fortin, S.: The Graph Isomorphism Problem, Technical Report TR 96–20, Department of Computer Science, University of Alberta (1996), ftp://ftp.cs.ualberta.ca/pub/TechReports/1996/TR96-20/TR96-20.ps.gz
McKay, B.D.: Practical Graph Isomorphism. Congressus Numerantium 30, 45–87 (1981), http://cs.anu.edu.au/~bdm/papers/pgi.pdf
McKay, B.D.: Nauty (1994), http://cs.anu.edu.au/~bdm/nauty/
Hayes, P. (ed.): RDF Semantics. W3C Working Draft (2003)
Patel-Schneider, P.F., Hayes, P., Horrocks, I. (eds.): OWL Semantics and Abstract Syntax. W3C Working Draft (2003)
Boyer, J. (ed.): Canonical XML. W3C Recommendation (2001)
Biron, P.V., Malhotra, A. (eds.): XML Schema Part 2: Datatypes. W3C Rec (2001)
Dean, M., Schrieber, G.: OWL Reference. W3C Working Draft (2003)
Adel’son-Vel’skii, G.M., Landis, E.M.: An algorithm for the Organization of Information. Doklady Akademia Nauk SSSR 146, 263–266 (1962); English translation in Soviet Mathematics Doklady 3, 1259–1263
Lynch, C.: Canonicalization: A Fundamental Tool to Facilitate Preservation and Management of Digital Information. D-Lib 5(9) (1999), http://www.dlib.org/dlib/september99/09lynch.html
Knuth, D.E.: The Art of Computer Programming. V.3: Sorting and Searching (1973)
Carroll, J.J.: Awk scripts for canonicalizing N-Triples (2002), http://www-uk.hpl.hp.com/people/jjc/rdf/c14n-impl/
Carroll, J.J., de Roo, J. (eds.): Web Ontology Language (OWL) Test Cases. W3C Working Draft (2002), http://www.w3.org/TR/2002/WD-owl-test-20021024/
Smith, M.K., Welty, C., McGuinness, D. (eds.): OWL Web Ontology Language, Guide. W3C Working Draft (2003), http://www.w3.org/TR/2003/WD-owl-guide-20030331/
Dean, M. (librarian): DAML Ontology Library, http://www.daml.org/ontologies/
Dean, M.: Baseball Ontology, http://www.daml.org/2001/08/baseball/baseball-ont
Chien, M., Mugnier, M.-L.: Conceptual Graphs: Fundamental Notions. Revue d’Intelligence Atificielle 5(4), 365–406 (1992)
Beckett, D. (ed.): RDF/XML Syntax Specification (Revised). W3C Working Draft (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carroll, J.J. (2003). Signing RDF Graphs. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds) The Semantic Web - ISWC 2003. ISWC 2003. Lecture Notes in Computer Science, vol 2870. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39718-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-39718-2_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20362-9
Online ISBN: 978-3-540-39718-2
eBook Packages: Springer Book Archive