Practical Threshold RSA Signatures without a Trusted Dealer

  • Ivan Damgård
  • Maciej Koprowski
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


We propose a threshold RSA scheme which is as efficient as the fastest previous threshold RSA scheme (by Shoup), but where two assumptions needed in Shoup's and in previous schemes can be dropped, namely that the modulus must be a product of safe primes and that a trusted dealer generates the keys. The robustness (but not the unforgeability) of our scheme depends on a new intractability assumption, in addition to security of the underlying standard RSA scheme.


Secret Sharing Random Oracle Maximal Order Large Prime Factor Signing Oracle 
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.
    D. Boneh and M. Franklin Efficient generation of shared RSA keys, Proc. of Crypto'97, Springer-Verlag LNCS series, nr. 1233.Google Scholar
  2. 2.
    R. Canetti, Security and Composition of Multiparty Cryptographic Protocols, Journal of Cryptology, vol.13, 2000. On-line version at
  3. 3.
    R. Canetti, A unified framework for analyzing security of protocols, Cryptology Eprint archive 2000/67,
  4. 4.
    Damgård and Jurik: A Generalization and some Applications of Paillier’s Probabilistic Public-key System, to appear in Public Key Cryptography 2001.Google Scholar
  5. 5.
    Yair Frankel, Peter Gemmell, Philip D. MacKenzie and Moti Yung Optimal-Resilience Proactive Public-Key Cryptosystems Proc. of FOCS 97.Google Scholar
  6. 6.
    Yair Frankel, Philip D. MacKenzie and Moti Yung Robust Efficient Distributed RSA-Key Generation, Proc. of STOC 98.Google Scholar
  7. 7.
    P. Fouque, G. Poupard, J. Stern: Sharing Decryption in the Context of Voting or Lotteries, Proceedings of Financial Crypto 2000.Google Scholar
  8. 8.
    Pierre-Alain Fouque and Jacques Stern: Fully Distributed Threshold RSA under Standard Assumptions, IACR Cryptology ePrint Archive: Report 2001/008, February 2001Google Scholar
  9. 9.
    Gennaro, Jarecki, Krawczyk and Rabin: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, Proc. of EuroCrypt 99, Springer Verlag LNCS series, nr. 1592.Google Scholar
  10. 10.
    Gennaro, Rabin, Jarecki and Krawczyk: Robust and Efficient Sharing of RSA Functions, J.Crypt. vol.13, no.2.Google Scholar
  11. 11.
    Shingo Miyazaki, Kouichi Sakurai and Moti Yung On Threshold RSA-Signing with no Dealer, Proc. of ICISC 1999, Springer Verlag LNCS series, nr.1787.Google Scholar
  12. 12.
    P. Pallier: Public-Key Cryptosystems based on Composite Degree Residue Classes, Proceedings of EuroCrypt 99, Springer Verlag LNCS series, pp. 223–238.Google Scholar
  13. 13.
    Pedersen: A Threshold cryptosystem without a trusted third party, proc. of Euro-Crypt 91, Springer Verlag LNCS nr. 547.Google Scholar
  14. 14.
    T. Rabin: A Simplified Approach to Threshold and Proactive RSA, proc. of Crypto 98, Springer Verlag LNCS 1462.Google Scholar
  15. 15.
    J. B. Rosser and L. Schoenfeld: Approximate formulas for some functions of prime numbers, Ill. J. Math. 6 (1962), 64–94.zbMATHMathSciNetGoogle Scholar
  16. 16.
    Victor Shoup Practical Threshold Signatures, Proceedings of EuroCrypt 2000, Springer Verlag LNCS series nr. 1807.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Ivan Damgård
    • 1
  • Maciej Koprowski
    • 1
  1. 1.BRICSAarhus UniversityAarhus

Personalised recommendations