View publication
| Title | Short Transitive Signatures for Directed Trees |
| Authors | Philippe Camacho, Alejandro Hevia |
| Publication date | 2012 |
| Abstract | 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) 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 L>=1 and the security parameter k: - A signature for an edge is only O(k*L) bits, where k is a security parameter. - The time to sign a new edge or verify the signature for a path takes O(L) cryptographic operations. - The time to compute a signature for any path in the tree takes O(L n^{1/L}) 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. |
| Pages | 35-50 |
| Conference name | The Cryptographer's Track at RSA Conference |
| Publisher | Springer (New York, NY, USA) |
| Reference URL |
|