- From: Jeremy Carroll <jeremy@topquadrant.com>
- Date: Mon, 27 Jun 2011 11:41:35 -0700
- 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 UTC