The cryptographic impact of groups with infeasible inversion
Susan Hohenberger · DSpace@MIT (Massachusetts Institute of Technology) · 2003
Algebraic group structure is an important - and often overlooked - tool for constructing and comparing cryptographic applications. Our driving example is the open problem of finding provably secure transitive signature schemes for directed graphs, proposed by Micali and Rivest [41]. A directed transitive signature scheme (DTS) allows Alice to sign a subset of edges on a directed graph in such a way that anyone can compose Alice's signatures on ab and bc to obtain her signature on edge ac. We formalize the necessary mathematical criteria for a secure DTS scheme when the signatures can be composed in any order, showing that the edge signatures in such a scheme form a special (and powerful) mathematical group not known to exist: an Abelian trapdoor group with infeasible inversion (ATGII). Furthermore, we show that such a DTS scheme is more complex - in a black-box sense - than standard signatures, public key encryption and oblivious transfer. To our knowledge, this is the first separation between standard signature schemes and any of the many variant signature schemes proposed. We formalize