Directed Acyclic Graphs, One-way Functions and Digital Signatures

Extended Abstract
  • Daniel Bleichenbacher
  • Ueli M. Maurer
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


The goals of this paper are to formalize and investigate the general concept of a digital signature scheme based on a general one-way function without trapdoor for signing a predetermined number of messages. It generalizes and unifies previous work of Lamport, Winternitz, Merkle, Even et al. and Vaudenay. The structure of the computation yielding a public key from a secret key corresponds to a directed acyclic graph \( \mathcal{G} \). A signature scheme for \( \mathcal{G} \) can be defined as an antichain in the poset of minimal verifyable sets of vertices of \( \mathcal{G} \) with the naturally defined computability relation as the order relation and where a set is verifyable if and only if the public key can be computed from the set.


Directed Acyclic Graph Signature Scheme Signature Pattern Predetermined Number Message Space 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    J.N.E. Bos and D. Chaum, Provably unforgeable signatures, Advances in Cryptology — CRYPTO’ 92 (E. Brickell, ed.), Lecture Notes in Computer Science, vol. 740, Springer Verlag, 1993, pp. 1–14.Google Scholar
  2. 2.
    N. de Brujin, C. A. van Ebbenhorst Tengebergen, and D. R. Kruyswijk, “On the set of divisors of a number,” Nieuw Arch. Wisk, vol. 23, pp. 191–193, 1952.Google Scholar
  3. 3.
    S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures, Advances in Cryptology — CRYPTO’ 89, Lecture Notes in Computer Science, vol. 435 (G. Brassard, ed.), Springer Verlag, 1990, pp. 263–275.Google Scholar
  4. 4.
    W. Feller, An Introduction to Probability Theory and Its Applications, vol. II., second corrected printing, Wiley & Sons, 1966.Google Scholar
  5. 5.
    L. Lamport, Constructing digital signatures from a one-way function, Technical Report SRI Intl. CSL 98, 1979.Google Scholar
  6. 6.
    R. Merkle, A certified digital signature, Advances in Cryptology — CRYPTO’ 89, Lecture Notes in Computer Science, vol. 435 (G. Brassard, ed.), Springer Verlag, 1990, pp. 218–238.Google Scholar
  7. 7.
    C. Meyer and S. Matyas, Cryptography — a new dimension in computer data security, John Wiley & Sons, Inc., 1982.Google Scholar
  8. 8.
    R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, Vol. 21, No. 2, pp. 120–126, 1978.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proc. 22nd ACM Symp. on Theory of Computing (STOC), 1990, pp. 387–394.Google Scholar
  10. 10.
    C. P. Schnorr, Efficient identification and signatures for smart cards, Advances in Cryptology — Crypto’ 89, Lecture Notes in Computer Science, vol. 435 (G. Brassard, ed.), Springer-Verlag 1990, pp. 239–252.Google Scholar
  11. 11.
    E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift, vol. 27, pp. 544–548, 1928.CrossRefzbMATHMathSciNetGoogle Scholar
  12. 12.
    S. Vaudenay, One-time identification with low memory, Proc. of EUROCODE’ 92, Lecture Notes in Computer Science, Springer Verlag. CISM Courses and Lectures, No. 339, International Centre for Mechanical Sciences, P. Camion, P. Charpin and S. Harari (eds.), Springer-Verlag, pp. 217–228.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Daniel Bleichenbacher
    • 1
  • Ueli M. Maurer
    • 1
  1. 1.Institute for Theoretical Computer ScienceETH ZürichZürichSwitzerland

Personalised recommendations