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

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! JeremyReceived 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
*