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

Date: Thu, 23 Jun 2011 17:03:54 -0700

```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 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 22:01:59 UTC