Optimal-resilience proactive public-key cryptosystems

We introduce new efficient techniques for sharing cryptographic functions in a distributed dynamic fashion. These techniques dynamically and securely transform a distributed function (or secret sharing) representation between t-out-of-l (polynomial sharing) and t-out-of-t (additive sharing). We call the techniques poly-to-sum and sum-to-poly, respectively. Employing these techniques, we solve a number of open problems in the area of cryptographic function sharing. We design a threshold function sharing scheme with proactive security for general functions with a "homomorphic property" (a class which includes all RSA variants and Discrete Logarithm variants). The sharing has "optimal resilience" (server redundancy) and enables computation of the function by the servers assuring high availability, security and efficiency. Proactive security enables function sharing among servers while tolerating an adversary which is mobile and which dynamically corrupts and abandons servers (and perhaps visits all of them over the lifetime of the system, as long as the number of corruptions (faults) is bounded within a time period). Optimal resilience assures that the adversary can corrupt any minority of servers at any time-period. On the way, we solve other open problems: (1) A efficient robust RSA function sharing protocol is presented (all previous secure solution had a non-constant, blow-up of the permanent share held by servers); (2) A new "robust threshold RSA" scheme for any RSA (not necessarily strong-prime based), (3) We also give a particularly efficient "proactive RSA" as a modular extension of the "share efficient robust system". The techniques also allow dynamic updates to the set of servers employed and to the threshold size.