W3C home > Mailing lists > Public > public-rdf-wg@w3.org > June 2011

Re: Need for a canonical byte stream for an RDF graph

From: Jeremy Carroll <jeremy@topquadrant.com>
Date: Thu, 23 Jun 2011 17:03:54 -0700
Message-ID: <4E03D46A.4020607@topquadrant.com>
To: public-rdf-wg@w3.org
On 6/23/2011 4:48 PM, Ian Davis wrote:
> Wouldn't the skolemization proposals make this a lot easier? Skolemize
> the blank nodes according to a deterministic pattern, then sort, then
> sign.
>
> Ian

I have just been rereading my paper, it rejects that with the following 
argument:
[[
In a Semantic Web application, there is likely to be an RDF graph. If we 
wish to
verify that either it, or a subgraph of it, has been digitally signed in 
some way, then
we have to solve at least one well-known hard problem. Note this way of 
stating the
problem rules out one scenario which is that B has read the graph from a 
file signed
by A. If B has done this, then B can simply verify the signature on the 
file, and has no
need to verify the signature for the graph, as a graph.
We [...] assume the graph isomorphism problem is strictly harder than
polynomial time, and strictly easier than nondeterministic polynomial 
time. (i.e.
P < GI < NP). We also note that the subgraph isomorphism problem is well 
known to
be NP complete. These results are applicable to RDF, see section 2.3.
Thus, if A wishes to sign an RDF graph and B wishes to verify the 
signature, then
A needs to serialize the graph in some form, sign the serialization, and 
B needs to
verify that signature. This overall process of signature verification 
permits a
comparison (either for isomorphism or for subgraph) between the graph 
that A signs,
and the graph that B verifies. This overall process solves the graph 
isomorphism
problem or the subgraph isomorphism problem. Thus either the algorithm 
for signing
the graph, or the algorithm for verifying the signature of the graph 
must be of
complexity class GI or NP.
]]

====

So the 'skolemization' you propose is of complexity greater than P!

Jeremy
Received on Friday, 24 June 2011 00:04:05 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:25:44 GMT