C14N use case: chains of trust

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 UTC