Cryptology ePrint Archive: Report 2001/008
Fully Distributed Threshold RSA under Standard Assumptions
Pierre-Alain Fouque and Jacques Stern
Abstract: The aim of the present article is to propose a fully distributed environment for the RSA scheme.
What we have in mind is highly sensitive applications and even if we are ready to pay a price in
terms of efficiency, we do not want any compromise of the security assumptions that we make.
Recently Shoup proposed a practical RSA threshold signature scheme that allows to share the
ability to sign between a set of players. This scheme can be used for decryption as well.
However, Shoup's protocol assumes a trusted dealer to generate and distribute the keys.
This comes from the fact that the scheme needs a special assumption on the RSA modulus and
this kind of RSA moduli cannot be easily generated in an efficient way with many players.
Of course, it is still possible to call theoretical results on multiparty computation, but we
cannot hope to design efficient protocols. The only practical result to generate RSA moduli
in a distributive manner is Boneh and Franklin protocol but this protocol cannot be easily
modified to generate the kind of RSA moduli that Shoup's protocol requires.
The present work takes a different path by proposing a method to enhance the key generation
with some additional properties and revisits the proof of Shoup to work with the resulting
RSA moduli. Both of these enhancements decrease the performance of the basic protocols.
However, we think that in the applications that we target, these enhancements provide
practical solutions. Indeed, the key generation protocol is usually run only once and the
number of players have time to perform their task so that the communication or time complexity
are not overly important.
Category / Keywords: cryptographic protocols / Threshold cryptography
Date: received 8 Feb 2001
Contact author: Pierre-Alain Fouque at ens fr
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20010208:185149 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]