Abstract
A publicly verifiable secret sharing (PVSS) scheme, named by Stadler in [Sta96], is a special VSS scheme in which anyone, not only the shareholders, can verify that the secret shares are correctly distributed. The property of public verifiability is what the first proposed VSS scheme [CGMA85] incorporated but later protocols [GMW87, Fel87, Ped91] failed to include. PVSS can provide some interesting properties in the systems using VSS. For instance, it gives a practical solution to (k, l)-threshold VSS assuming no broadcast channel. Stadler proposed two PVSS protocols: one is as secure as the Decision-Diffie-Hellman problem and the other is not formally discussed about security. This paper presents a practical and provably secure PVSS scheme which is O(¦v¦) times more efficient than Stadler's PVSS schemes where ¦v¦ denotes the size of the secret. It can be incorporated into various cryptosystems based on the factoring and the discrete logarithm to transform them into publicly verifiable key escrow (PVKE) systems. In addition, those key escrow cryptosystems can be easily modified into the verifiable partial key escrow (VPKE) ones with the property of delayed recovery [BG97]. To the best of our knowledge, this is the first realization of a VPKE cryptosystem based on the factoring with the delayed recovery.
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
Brickell, E. F., Chaum, D., Damgård, I., and Gråf, J. van de, “Gradual and verifiable release of a secret”, Proceedings of CRYPTO'87, pp.156–166. (1988).
Bellare, M., and Goldwasser, S., “Verifiable Partial Key Escrow”, To appear in Proceedings of the Fourth Annual Conference and Communications Security, ACM, 1997.
Blakley, G., “Safeguarding cryptographic keys”, AFIPS Conference Proceeding, June 1979.
Ben-Or, M., Goldwasser, S., and Wigderson, A., “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation”, Proceeding of STOC88, pp 11–17.
Chaum, D., Crepeau, C, and Damgård, I., “Multiparty Unconditionally Secure Protocol”, Proceeding of STOC88, pp 1–10.
Chor, B., Goldwasser, S., Micali, S. and Awerbuch, B.: Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, Proc. of FOCS, pp.383–395 (1985).
Feldman, P., “A Practical Scheme for Non-interactive Verifiable Secret Sharing,” In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pp.427–437 (1987).
Fujisaki, E., “Efficient PZK Proofs for Boolean Formulae whose atoms are Polynomials”, Manuscript.
Fujisaki, E., and Okamoto, T., “Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations,” Proceedings of Crypto'97, LNCS 1294, Springer, pp.16–30 (1997).
U. Feige, A. Fiat and A. Shamir, “Zero Knowledge Proofs of Identity,” Journal of Cryptology, Vol. 1, pp.77–94 (1988).
U.Feige, and A.Shamir, “Witness Indistinguishable and Witness Hiding Protocols,” Proc. of STOC90.
Goldreich, O., Micali, S. and Wiederson, A., “How to play any mental game”, Proceedings of STOC87, pp. 218–229.
Mao, W., “Publicly Verifiable Partial Key Escrow”, Proceedings of ICICS'97, Beijing, pp.409–413 (1997).
Micali, S., “Fair Public-Key Cryptosystems”, Proceedings of CRYPTO'92, pp.113–138 (1993).
Pedersen, T. P., “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing”, Proceedings of Crypto 91, pp. 129–140 (1992).
Shamir, A., “How to share a secret”, CACM, Vol 22, No.11, pp.612–613 (1979).
Stadler, M.: Publicly Verifiable Secret Sharing, Proc. of Eurocrypt'96, LNCS 1070, Springer, pp.190–199 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fujisaki, E., Okamoto, T. (1998). A practical and provably secure scheme for publicly verifiable secret sharing and its applications. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054115
Download citation
DOI: https://doi.org/10.1007/BFb0054115
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive