W3C home > Mailing lists > Public > public-rdf-wg@w3.org > June 2011

C14N use case: chains of trust

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

Jeremy
Received on Monday, 27 June 2011 20:48:20 GMT

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