The Cramer-Shoup Strong-RSA Signature Scheme Revisited
- 1.3k Downloads
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.
KeywordsSignature Scheme Random Oracle Quadratic Residue Security Proof Group Signature Scheme
- 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
- 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
- D. Bleichenbacher: Efficiency and Security of Cryptosystems Based on Number Theory, Ph.D. thesis, Swiss Federal Institute of Technology, Zürich, 1996. 123Google Scholar
- 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
- R. Cramer, I. Damg∢rd, T. Pedersen: Efficient and Provable Security Ampli fication, CWI Reports, Computer Science, CS-R9529, 1995. 119Google Scholar
- 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
- 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
- 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
- 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
- T. Schweinberger, V. Shoup: ACE — The Advanced Cryptographic Engine, available at http://www.shoup.net, August 2002.