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

On 2011-06-27, at 19:41, Jeremy Carroll wrote:

> 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 believe I read your paper when it was published, but not since sadly.

Other than a few papers I've read on the topic, my experience is based on what people are using currently, to sign personal data, which is likely not especially well thought out.

> 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)

I'm not sure about that. The implementations I'm familiar with - WoT (http://xmlns.com/wot/0.1/), OAuth, and HTTPS - don't require that, at least in a way which is obvious to me. Arguably OAuth and HTTPS don't count, but they're commonly used for HTML, XML, JSON, etc.

> - 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]

I'm not sure where graph isomorphism is required. None of the RDF signing techniques that I've seen in the wild use it.

You can only verify the signature of the graph at request time, but at that time you have access to the canonical byte stream anyway.

> - 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)

Good point. Efficient version control does seem like it would require C14N. I know that Talis Changesets for e.g. are in this area, but I don't know the implementation details.

> - signatures in chains of trust

That's satisfied by WoT, as far as I know.

Regards,
   Steve

-- 
Steve Harris, CTO, Garlik Limited
1-3 Halford Road, Richmond, TW10 6AW, UK
+44 20 8439 8203  http://www.garlik.com/
Registered in England and Wales 535 7233 VAT # 849 0517 11
Registered office: Thames House, Portsmouth Road, Esher, Surrey, KT10 9AD

Received on Monday, 27 June 2011 23:08:22 UTC