Short Transitive Signatures for Directed Trees

Author: Philippe Camacho, and A.H..


A transitive signature scheme allows to sign a graph in such a way that given the signature of edges (i,j) and (j,k) it is possible to compute the signature for the edge (i,k) without the signer's secret, thus allowing to ``compress" a path in the graph. Constructions for undirected graphs are known but the case of directed graphs remains an open problem. A first solution for the restricted case where the graph is a directed tree (DTTS) was given by Yi at CT-RSA 2007. In this construction, the signature for an edge is $O(n \log (n \log n))$ bits in the worst case. A year later, Neven designed a simpler scheme based on standard signatures where the signature size is reduced to $O(n \log n)i$ bits. Although Neven's construction is more efficient, handling $n\log n$ remains impractical for large $n$. In this work, we design a new transitive signature scheme for directed trees where for any value $\lambda \geq 1$ and the security parameter $k$: - A signature for an edge is only $O(k\lambda)$ bits, where $k$ is a security parameter. - The time to sign a new edge or verify the signature for a path takes $O(\lambda)$ cryptographic operations. - The time to compute a signature for any path in the tree takes $O(\lambda n^{1/\lambda}$ cryptographic operations. To the best of our knowledge this is the first construction with such trade off. In particular, we achieve $O(k\log(n))$-bit signatures, as well as $O(\log(n))$ time to generate edge signatures, verify signatures for any path, and even to compute a signature for any path in the tree. Our construction relies on a new variant of collision resistance, which we call {prefix collision resistance}. A family $\H$ is prefix collision resistant if for any $H \in \H$, given two strings $A$ and $B$ equal up to position $i$, then a Prover can convince a Verifier that $A[1..i]$ is a prefix of $B$ by sending only $H(A),H(B)$, and a small proof. We believe that this new primitive will lead to other interesting applications.

Ref: In Proceedings of The Cryptographers' Track at the RSA Conference 2012, San Francisco, CA, USA, February 27 - March 2, 2012. Lecture Notes in Computer Science, Vol. 7178. pp. XXX-YYY. Springer. 2012.

Paper: Not yet available.