Security of the TGII directed-signature construction

Definitions and mathematical statement

A directed transitive signature scheme signs directed edges and permits public derivation along directed paths. In a basic interface, signatures on $(u,v)$ and $(v,w)$ can be composed into a signature on $(u,w)$ that verifies under the same public key. Direction matters: reverse reachability is not automatically authorized.

A standard security goal allows adaptive signing queries for edges and forbids producing a valid signature on $(s,t)$ when $t$ is not reachable from $s$ in the directed graph of queried edges. The exact treatment of identity paths, labels, and composition data must be specified in the actual scheme. A proof should state its adversary model and bound forgery success under explicit assumptions.

Prove secure the source's simple construction from trapdoor groups with infeasible inversion (TGII), or repair it while retaining its intended directed transitive functionality. Such a group is intended to have encoded elements with feasible public group operations but computationally infeasible inversion absent trapdoor information; the precise encoding, trapdoor interface, distributions, and hardness game are not supplied. Nor are the key-generation, edge-signing, composition, and verification algorithms of the proposed construction.

Consequently there is no identified scheme to analyze from this record alone. The standard directed-reachability security description above gives context rather than replacing the missing source game. A repair must also specify which interfaces, assumptions, and efficiency constraints may change; these are not prescribed.

Short English statement

Prove or repair the TGII-based directed transitive signature scheme, preserving public signature derivation along directed paths. The construction, TGII assumption, and precise forgery game are absent from the extracted record.

Sources

• Ronald Rivest, IPAM Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6243, legacy PPT logical slide 17, schedule source https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule; accessed 2026-07-29. The supplied provenance records a PDF/legacy-PPT visual audit.
• Rivest--Shamir and Micali--Rivest, directed transitive signature/infeasible-inversion work named in the supplied summary, without full publication citations or formal definitions.
• Local registry data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8800085$, source code catalogue entry, Security of the TGII directed-signature construction. Dataset attribution: Ulam AI and the UnsolvedMath Contributors.