Affordable Access

Provably Secure and Practical Signature Schemes

Technische Universität
Publication Date
  • Computer Science
  • Physics


This work contributes to two independent topics: (1) Provably secure and efficient signature schemes and (2) the analysis of certain integer multiplication algorithms. It is uncertain whether quantum computers are feasible that are powerful enough to solve non-trivial problems. In 1994, Shor proposed a quantum algorithm for solving both the integer factorization problem and the discrete logarithm problem in polynomial time. This algorithm clearly renders signature schemes like RSA, DSA or ElGamal completely insecure as soon as powerful quantum computers come into existence. In this thesis we propose signature schemes that are provably secure and efficient. The security of the described schemes relies on the security of hash function and the pseudorandom bit generator used. We also study and compare certain integer multiplication algorithms. The motivation of this comparison is the use of modular exponentiation -- which, in turn, needs the multiplication of large integers -- in often used signature schemes like RSA, DSA, and ElGamal. Our study is more detailed than just the asymptotic behaviour, since we take multiplication and addition of base-words into account.

There are no comments yet on this publication. Be the first to share your thoughts.