A simple approach to secretly sharing a factoring witness in publicly-verifiable manner

摘要

We give a simple solution to secretly sharing a factoring witness (or RSA secret-key d) in a publicly verifiable manner. This PVSS protocol is useful for various cryptosystems such as the fair-cryptosystem of RSA and the threshold and proactive RSA. As a primitive, we present a proof-of-knowledge protocol that works in a cyclic group of an unknown order. For this kind of protocols, the proof of soundness seems to have been provided incompletely in the literature [11,17, 6], even though they appear in many applications, for instance, PVSS [20, 12], group signature [4, 5] and optimistic fair-exchange [2, 1]. We provide a rigorous proof for our protocol. As PVSS for factoring witness, our solution is conceptually simple and the first practical and provably-secure scheme under some reasonable assumptions and, as PVSS for discrete log, it is almost as simple as that in [18].