Efficient Publicly Verifiable Secret Sharing Schemes with Fast or Delayed Recovery.
F. Boudot and J. Traore

A publicly verifiable secret sharing scheme is a secret sharing scheme in which everyone, not only the shareholders, can verify that the secret shares are correctly distributed. We present new such schemes and use them to share discrete logarithms and integer factorizations. The shareholders will be able to recover their shares quickly (fast recovery) or after a predetermined amount of computations (delayed recovery) to prevent the recovery of all the secrets by un-trustworthy shareholders (e.g. if these schemes are used for escrowing secret keys). The main contribution of this paper is that all the schemes we present need much less computations and communicated bits than previous ones [BGo, FOk, Mao, Sta, YYu]. By the way, we introduce in this paper several tools which are of independent interest: a proof of equality of two discrete logarithms modulo two different numbers, an efficient proof of equality of a discrete logarithm and a third root, and an efficient proof of knowledge of the factorization of any composite number n, where it is not necessary to prove previously that n is the product of two prime factors.