## The provable security of Graph-Based One-Time Signatures
and extensions to algebraic signature schemes

**Authors:**
Alejandro Hevia, and Daniele Micciancio

**Abstract:**
Essentially all known one-time signature schemes can be described as
special instances of a general scheme suggested by Bleichenbacher
and Maurer based on "graphs of one-way functions".
Bleichenbacher and Maurer thoroughly analyze graph based signatures
from a combinatorial point of view, studying the graphs that
result in the most efficient schemes (with respect to various
efficiency measures, but focusing mostly on key generation time).
However, they do not give a proof of security of their generic
construction, and they leave open the problem of determining under
what assumption security can be formally proved.
In this paper we analyze graph based signatures from a security
point of view and give sufficient conditions that allow to prove
the security of the signature scheme in the standard complexity model
(no random oracles).
The techniques used to prove the security of graph based one-time
signatures are then applied to the construction of a new class of
algebraic signature schemes, i.e., schemes where signatures can be
combined with a restricted set of operations.

**Ref:** In *Advances in Cryptology - Asiacrypt 2002 Proceedings*,
pp. 379-396, LNCS 2501, Springer-Verlag, Dec. 2002.

Available as
Compressed Postscript,
Postscript, and
PDF.

**Full paper:** Not yet available.