Abstract
We propose techniques that allow construction of robust threshold RSA signature schemes that can work without a trusted dealer using known key generation protocols and is as efficient as the best previous schemes. We do not need special conditions on the RSA modulus, extra complexity or set-up assumptions or random oracles. An “optimistic” variant of the scheme is even more efficient in case no faults occur. Some potential more general applications of our basic idea are also pointed out.
Chapter PDF
Similar content being viewed by others
Keywords
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.
References
Algesheimer, J., Camenisch, J.L., Shoup, V.: Efficient computation modulo a shared secret with application to the generation of shared safe-prime products. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 417. Springer, Heidelberg (2002)
Boneh, D., Franklin, M.: Efficient generation of shared RSA keys. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 425–439. Springer, Heidelberg (1997)
Canetti, R.: Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology 13 (2000), On-line version at http://philby.ucsd.edu/cryptolib/1998/98-18.html
Canetti, R.: A unified framework for analyzing security of protocols, Cryptology Eprint archive 2000/67 (2000), http://eprint.iacr.org/2000/067.ps
Cramer, Damgård: Secret-Key Zero-Knowledge. In: Proc. of TCC 2003. LNCS. Springer, Heidelberg (2003)
Damgård, I.B., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125–142. Springer, Heidelberg (2002)
Damgård, J.: A Generalization and some Applications of Paillier’s Probabilistic Public-key System. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992. Springer, Heidelberg (2001) (to appear)
Damgård, I.B., Koprowski, M.: Practical threshold RSA signatures without a trusted dealer. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, p. 152. Springer, Heidelberg (2001)
De Santis, A., Desmedt, Y., Frankel, Y., Yung, M.: How to share a function securely. In: STOC 1994, pp. 522–533 (1994)
Frankel, Y., Gemmell, P., MacKenzie, P.D., Yung, M.: Optimal- Resilience Proactive Public-Key Cryptosystems. In: Proc. of FOCS 1997 (1997)
Frankel, Y., MacKenzie, P.D., Yung, M.: Robust Efficient Distributed RSA-Key Generation. In: Proc. of STOC 1998 (1998)
Fouque, P., Poupard, G., Stern, J.: Sharing Decryption in the Context of Voting or Lotteries. In: Proceedings of Financial Crypto 2000 (2000)
Fujisaki, E., Okamoto, T.: Statistical Zero-Knowledge Protocols to prove Modular Polynomial Relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997)
Fouque, P.-A., Stern, J.: Fully Distributed Threshold RSA under Standard Assumptions, IACR Cryptology ePrint Archive: Report 2001/008 (February 2001)
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 295. Springer, Heidelberg (1999)
Gennaro, R., Jarecki, S., Krawczyk, H.: Robust and Efficient Sharing of RSA Functions. J. Crypt. 13(2)
Miyazaki, S., Sakurai, K., Yung, M.: On Threshold RSA-Signing with no Dealer. In: Song, J.S. (ed.) ICISC 1999. LNCS, vol. 1787, Springer, Heidelberg (1999)
King, B.: Improved Methods to Perform Threshold RSA. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 359–372. Springer, Heidelberg (2000)
Koprowski, M.: Threshold Integer Secret Sharing (manuscript) (2003)
Paillier, P.: Public-Key Cryptosystems based on Composite Degree Residue Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Pedersen, T.P.: A Threshold cryptosystem without a trusted third party. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 522–526. Springer, Heidelberg (1991)
Rabin, T.: A Simplified Approach to Threshold and Proactive RSA. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 89. Springer, Heidelberg (1998)
Reiter, M.K., Birman, K.P.: How to securely replicate services. ACMTransactions on programming languages and systems 1994 16(3), 986–1009 (1994)
Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers, Ill. J. Math. 6, 64–94 (1962)
Shoup, V.: Practical Threshold Signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 207. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I., Dupont, K. (2005). Efficient Threshold RSA Signatures with General Moduli and No Extra Assumptions. In: Vaudenay, S. (eds) Public Key Cryptography - PKC 2005. PKC 2005. Lecture Notes in Computer Science, vol 3386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30580-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-30580-4_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24454-7
Online ISBN: 978-3-540-30580-4
eBook Packages: Computer ScienceComputer Science (R0)