link.springer.com

Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing

  • ️Mon Jan 01 2001

Abstract

It is shown how to distribute a secret to n persons such that each person can verify that he has received correct information about the secret without talking with other persons. Any k of these persons can later find the secret (1 ≤ k ≤ n), whereas fewer than k persons get no (Shannon) information about the secret. The information rate of the scheme is 1/2 and the distribution as well as the verification requires approximately 2k modular multiplications pr. bit of the secret. It is also shown how a number of persons can choose a secret “in the well” and distribute it verifiably among themselves.

Chapter PDF

Similar content being viewed by others

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

  1. G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37:156–189, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  2. J. Bos, D. Chaum, and G. Purdy. A voting scheme. Preliminary draft.

    Google Scholar 

  3. E. F. Brickell and D. M. Davenport. On the classification of ideal secret sharing schemes. In Advances in Cryptology-proceedings of CRYPTO 89, pages 278–285, 1990.

    Google Scholar 

  4. J. C. Benaloh. Secret sharing homomorphisms: Keeping shares of a secret secret. In Advances in Cryptology-proceedings of CRYPTO 86, Lecture Notes in Computer Science, pages 251–260. Springer-Verlag, 1987.

    Google Scholar 

  5. G. R. Blakley. Safeguarding cryptographic keys. In Proceedings AFIPS 1979 Nat. Computer Conf., pages 313–319, 1979.

    Google Scholar 

  6. M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal of Computation, 13:850–864, 1984.

    Article  MATH  MathSciNet  Google Scholar 

  7. M. Ben-Or, S. Goldwasser, and A. Widgerson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 1–10, 1988.

    Google Scholar 

  8. D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 11–19, 1988.

    Google Scholar 

  9. P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pages 427–437, 1987.

    Google Scholar 

  10. I. Ingemarsson and G. J. Simmons. A protocol to set up shared secret schemes without the assistance of a mutually trusted party. In Advances in Cryptology — proceedings of EUROCRYPT 90, Lecture Notes in Computer Science, pages 266–282. Springer-Verlag, 1991.

    Google Scholar 

  11. T. P. Pedersen. Distributed provers with applications to undeniable signatures, 1991. To appear in the proceedings of Eurocrypt’91.

    Google Scholar 

  12. T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, pages 73–85, 1989.

    Google Scholar 

  13. A. Shamir. How to share a secret. Communications of the ACM, 22:612–613, 1979.

    Article  MATH  MathSciNet  Google Scholar 

  14. G. J. Simmons. How to (really) share a secret. In Advances in Cryptology-proceedings of CRYPTO 88, Lecture Notes in Computer Science, pages 390–448. Springer-Verlag, 1990.

    Chapter  Google Scholar 

  15. S. S. Wagstaff Jr. Greatest of the least primes in arithmetic progression having a given modulus. Mathematics of Computation, 33(147):1073–1080, July 1979.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Aarhus University, Denmark

    Torben Pryds Pedersen

Authors

  1. Torben Pryds Pedersen

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. AT&T Bell Laboratories, Room 2C473 600 Mountain Avenue, Murray Hill, NJ, 07974-0636, USA

    Joan Feigenbaum

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Pedersen, T.P. (1992). Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (eds) Advances in Cryptology — CRYPTO ’91. CRYPTO 1991. Lecture Notes in Computer Science, vol 576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46766-1_9

Download citation

  • DOI: https://doi.org/10.1007/3-540-46766-1_9

  • Published: 18 May 2001

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-55188-1

  • Online ISBN: 978-3-540-46766-3

  • eBook Packages: Springer Book Archive

Publish with us