The Cramer-Shoup Strong-RSA Signature Scheme Revisited

  • Marc Fischlin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


We discuss a modification of the Cramer-Shoup strong-RSA signature scheme. Our proposal also presumes the strong RSA assumption, but allows faster signing and verification and produces signatures of roughly half the size. Then we present a stateful version of our scheme where signing (but not verifying) becomes almost as efficient as with RSA-PSS. We also show how to turn our signature schemes into “lightweight” anonymous yet linkable group identification protocols without random oracles.


Signature Scheme Random Oracle Quadratic Residue Security Proof Group Signature Scheme 
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]
    G. Ateniese, J. Camenisch, M. Joye, G. Tsudik: A Practical and Provably Secure Coalition-Resistant Group Signature Scheme,Advances in Cryptology— Crypto 2000, Lecture Notes in Computer Science, Vol. 1880, pp. 255–270, Springer-Verlag, 2000. 126CrossRefGoogle Scholar
  2. [2]
    N. Barić, B. Pfitzmann: Collision-free Accumulators and Fail-Stop Signature Schemes Without Trees, Advances in Cryptology—Eurocrypt’ 97, Lecture Notes in Computer Science, Vol. 1233, pp. 480–495, Springer-Verlag, 1997. 117Google Scholar
  3. [3]
    M. Bellare, M. Fischlin, S. Goldwasser, S. Micali: Identification Protocols Secure Against Reset Attacks, Advances in Cryptology—Eurocrypt 2001, Lecture Notes in Computer Science, Vol. 2045, pp. 495–511, Springer-Verlag, 2001. 127CrossRefGoogle Scholar
  4. [4]
    M. Bellare, P. Rogaway: The Exact Security of Digital Signatures — How to Sign with RSA and Rabin, Advances in Cryptology—Eurocrypt’ 96, Lecture Notes in Computer Science, Vol. 1070,pp. 399–416, Springer-Verlag, 1996. 116Google Scholar
  5. [5]
    D. Bleichenbacher: Efficiency and Security of Cryptosystems Based on Number Theory, Ph.D. thesis, Swiss Federal Institute of Technology, Zürich, 1996. 123Google Scholar
  6. [6]
    D. Boneh: Twenty Years of Attacks on the RSA Cryptosystem, Notices of the American Mathematical Society (AMS), Vol. 46, No. 2, pp. 203–213, 1999. 122, 125zbMATHMathSciNetGoogle Scholar
  7. [7]
    D. Boneh, M. Franklin: Anonymous Authentication with Subset Queries, Proceedings of the 6th ACM Conference on Computer and Communication Security, pp. 113–119, 1999. 126Google Scholar
  8. [8]
    R. Cramer, I. Damg∢rd, T. Pedersen: Efficient and Provable Security Ampli fication, CWI Reports, Computer Science, CS-R9529, 1995. 119Google Scholar
  9. [9]
    R. Cramer, I. Damg∢rd, B. Schoenmakers: Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Advances in Cryptology— Crypto’94, Lecture Notes in Computer Science, Vol. 839, pp. 174–187, Springer-Verlag, 1994. 119Google Scholar
  10. [10]
    R. Cramer, V. Shoup: Signature Schemes Based on the Strong RSA Assumption, ACM Transactions on Information and System Security (ACM TISSEC), 3(3), pp. 161–185, 2000. 116, 117, 118, 119, 120, 121, 122, 123, 125CrossRefGoogle Scholar
  11. [11]
    I. Damgtard, M. Koprowski: Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups, Advances in Cryptology—Eurocrypt 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002. 117Google Scholar
  12. [12]
    A. De Santis, G. Di Crescenzo, G. Persiano: Communication-Efficient Anonymous Group Identification, Proceedings of the 5th ACM Conference on Computer and Communication Security, pp. 73–82, 1998. 126Google Scholar
  13. [13]
    E. Fujisaki, T. Okamoto: Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations,Advances in Cryptology—Crypto’ 97, Lecture Notes in Computer Science, vol. 1294, pp. 16–30, Springer Verlag, 1997. 117CrossRefGoogle Scholar
  14. [14]
    C. Lee, X. Deng, H. Zhu: Desing and Security Analysis of Anonymous Group Identifcation Protocols, Public Key Cryptography (PKC) 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002. 126Google Scholar
  15. [15]
    U. Maurer: Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters, Journal of Cryptology, vol. 8, pp. 123–155, Springer-Verlag, 1995.zbMATHCrossRefMathSciNetGoogle Scholar
  16. [16]
    T. Okamoto: Provable Secure and Practical Identi.cation Schemes and Corresponding Signature Schemes,Advances in Cryptology—Crypto’ 92, Lecture Notes in Computer Science, vol. 740, pp. 31–53, Springer Verlag, 1993. 126CrossRefGoogle Scholar
  17. [18]
    T. Schweinberger, V. Shoup: ACE — The Advanced Cryptographic Engine, available at, August 2002.

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Marc Fischlin
    • 1
  1. 1.Security and Smart Card Technologies (SICA)Fraunhofer-Institute Secure Telecooperation (SIT)USA

Personalised recommendations