From: Jeremy Carroll <jeremy@topquadrant.com>

Date: Mon, 27 Jun 2011 13:47:56 -0700

Message-ID: <4E08EC7C.5050504@topquadrant.com>

To: RDF Working Group WG <public-rdf-wg@w3.org>, rigo@w3.org

Date: Mon, 27 Jun 2011 13:47:56 -0700

Message-ID: <4E08EC7C.5050504@topquadrant.com>

To: RDF Working Group WG <public-rdf-wg@w3.org>, rigo@w3.org

On 6/27/2011 11:41 AM, Jeremy Carroll wrote: > > 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 > - theoretically of complexity GI, where probably N < GI < NP > - 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)) > - requires addition of explicitly meaningless triples in evil cases One case where the length of signature is significant is when one wishes to append a signature to an already signed document: this is not K people signing the same graph in parallel, but K people signing a graph in series where the ith person is signing the graph and also the signature of the jth person for each j<i. i Size of Graph Size of Graph + Signature 1 N 2N 2 2N 4N 3 4N 8N 4 8N 16N i.e. in the chain of signatures use case where K is the length of the chain, and N is the size of the original graph the size of the final graph is O(2^K*N), as opposed to O(N+K) for the case where signature is of length O(1). JeremyReceived on Monday, 27 June 2011 20:48:20 UTC

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