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: Mon, 27 Jun 2011 11:41:35 -0700
Message-ID: <4E08CEDF.8060606@topquadrant.com>
To: public-rdf-wg@w3.org
On 6/24/2011 2:28 AM, Steve Harris wrote:
>
> So, my experience of signed RDF graphs is limited to FOAF, where signing the serialised form of the FOAF document is sufficient. Do you have example usecases where it is not sufficient?
>

Some of you will have noted that I have taken a long time to pursue the 
work in my 2003 paper, the above argument is one of the key reasons.

I will reply with two use cases, but on separate threads, but first I 
wish to compare the two approaches.

The signing serialized form method has the following features:
- very simple to specify
- signature is of length O(N) in the size of the graph (i.e. the 
signature includes the serialized form)
- theoretically of complexity GI, where probably N < GI < NP
   [ I am assuming that the implementation of your idea regards the 'RDF 
signature' as a standard fixed length (say 64 byte) signature combined 
with the 'serialized form'; so that signature verification consists of 
verifying the 64 byte signature of the serialized form, and the graph 
isomorphism compares the graph to be verified against the graph returned 
by parsing the serialized form]
- hits bad bad complexity issue in evil cases

The method in my 2003 paper has the following features:
- slightly complex to specify
- signature is of length O(1)
- theoretical complexity O(Nlog(N))
(There is a published version in awk that I believe achieves this 
complexity, but is probably not actually efficient in practice, I can 
circulate that if it is useful)
- requires addition of explicitly meaningless triples in evil cases

[The evil cases are of more theoretical importance than practical but still]

The two use cases are:
- version control (C14N use case not signing)
- signatures in chains of trust

Jeremy
Received on Monday, 27 June 2011 18:42:06 GMT

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