More Web Proxy on the site http://driver.im/

Article

A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic

Author:

Berry SchoenmakersAuthors Info & Claims

CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology

Pages 148 - 164

Published: 15 August 1999 Publication History

Abstract

A publicly verifiable secret sharing (PVSS) scheme is a veri fiable secret sharing scheme with the property that the validity of the shares distributed by the dealer can be verified by any party; hence verification is not limited to the respective participants receiving the shares. We present a new construction for PVSS schemes, which compared to previous solutions by Stadler and later by Fujisaki and Okamoto, achieves improvements both in efficiency and in the type of intractability assumptions. The running time is O(nk), where k is a security parameter, and n is the number of participants, hence essentially optimal. The intractability assumptions are the standard Diffie-Hellman assumption and its decisional variant. We present several applications of our PVSS scheme, among which is a new type of universally verifiable election scheme based on PVSS. The election scheme becomes quite practical and combines several advantages of related electronic voting schemes, which makes it of interest in its own right.

References

[1]

J. Benaloh. Secret sharing homomorphisms: Keeping shares of a secret secret. In Advances in Cryptology--CRYPTO '86, volume 263 of Lecture Notes in Computer Science, pages 251-260, Berlin, 1987. Springer-Verlag.

[2]

J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, Department of Computer Science Department, New Haven, CT, September 1987.

[3]

G.R. Blakley. Safeguarding cryptographic keys. In Proceedings of the National Computer Conference 1979, volume 48 of AFIPS Conference Proceedings, pages 313-317, 1979.

[4]

E. F. Brickell. Some ideal secret sharing schemes. Journal of Combinatorial Mathematics and Combinatorial Computing, 9:105-113, 1989.

[5]

J. Benaloh and M. Yung. Distributing the power of a government to enhance the privacy of voters. In Proc. 5th ACM Symposium on Principles of Distributed Computing (PODC '86), pages 52-62, New York, 1986. A.C.M.

[6]

R. Cramer, I. Damgård, and U. Maurer. General secure multi-party computation from any linear secret sharing scheme, 1999. Manuscript.

[7]

R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Advances in Cryptology--CRYPTO '94, volume 839 of Lecture Notes in Computer Science, pages 174-187, Berlin, 1994. Springer-Verlag.

[8]

J. Cohen and M. Fischer. A robust and verifiable cryptographically secure election scheme. In Proc. 26th IEEE Symposium on Foundations of Computer Science (FOCS '85), pages 372-382. IEEE Computer Society, 1985.

[9]

R. Cramer, M. Franklin, B. Schoenmakers, and M. Yung. Multiauthority secret ballot elections with linear work. In Advances in Cryptology-- EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 72-83, Berlin, 1996. Springer-Verlag.

[10]

B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. In Proc. 26th IEEE Symposium on Foundations of Computer Science (FOCS '85), pages 383-395. IEEE Computer Society, 1985.

[11]

R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Advances in Cryptology-- EUROCRYPT '97, volume 1233 of Lecture Notes in Computer Science, pages 103-118, Berlin, 1997. Springer-Verlag.

[12]

J. Camenisch, U. Maurer, and M. Stadler. Digital payment systems with passive anonymity-revoking trustees. In Computer Security - ESORICS 96, volume 1146 of Lecture Notes in Computer Science, pages 33-43, Berlin, 1996. Springer-Verlag.

[13]

D. Chaum and T. P. Pedersen. Transferred cash grows in size. In Advances in Cryptology--EUROCRYPT '92, volume 658 of Lecture Notes in Computer Science, pages 390-407, Berlin, 1993. Springer-Verlag.

[14]

P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proc. 28th IEEE Symposium on Foundations of Computer Science (FOCS '87), pages 427-437. IEEE Computer Society, 1987.

[15]

E. Fujisaki and T. Okamoto. A practical and provably secure scheme for publicly verifiable secret sharing and its applications. In Advances in Cryptology--EUROCRYPT '98, volume 1403 of Lecture Notes in Computer Science, pages 32-46, Berlin, 1998. Springer-Verlag.

[16]

Y. Frankel, Y. Tsiounis, and M. Yung. "Indirect discourse proofs": Achieving efficient fair off-line e-cash. In Advances in Cryptology--ASIACRYPT '96, volume 1163 of Lecture Notes in Computer Science, pages 286-300, Berlin, 1996. Springer-Verlag.

[17]

R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Secure distributed key generation for discrete-log based cryptosystems. In Advances in Cryptology--EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 295-310, Berlin, 1999. Springer-Verlag.

[18]

M. Karchmer and A. Wigderson. On span programs. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 102-111. IEEE Computer Society Press, 1993.

[19]

T. Pedersen. A threshold cryptosystem without a trusted party. In Advances in Cryptology--EUROCRYPT '91, volume 547 of Lecture Notes in Computer Science, pages 522-526, Berlin, 1991. Springer-Verlag.

[20]

T. P. Pedersen. Distributed Provers and Verifiable Secret Sharing Based on the Discrete Logarithm Problem. PhD thesis, Aarhus University, Computer Science Department, Aarhus, Denmark, March 1992.

[21]

T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Advances in Cryptology--CRYPTO '91, volume 576 of Lecture Notes in Computer Science, pages 129-140, Berlin, 1992. Springer-Verlag.

[22]

B. Pfitzmann and M. Waidner. How to break fraud-detectable key recovery. Operating Systems Review, 32(1):23-28, 1998.

[23]

A. Shamir. How to share a secret. Communications of the ACM, 22(11):612- 613, 1979.

[24]

M. Stadler. Publicly verifiable secret sharing. In Advances in Cryptology-- EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 190-199, Berlin, 1996. Springer-Verlag.

[25]

E. Verheul and H. van Tilborg. Binding ElGamal: A fraud-detectable alternative to key-escrow proposals. In Advances in Cryptology--EUROCRYPT '97, volume 1233 of Lecture Notes in Computer Science, pages 119-133, Berlin, 1997. Springer-Verlag.

[26]

A. Young and M. Yung. Auto-recoverable auto-certifiable cryptosystems. In Advances in Cryptology--EUROCRYPT '98, volume 1403 of Lecture Notes in Computer Science, pages 17-31, Berlin, 1998. Springer-Verlag.

Cited By

Sober MKobelt MScaffino GKaaser DSchulte SHong JLanperne MPark JCerny TShahriar H(2023)Distributed Key Generation with Smart Contracts using zk-SNARKsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577677(231-240)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577677
Han RYu JZhang RHerlihy MNarula N(2022)Analysing and Improving Shard Allocation Protocols for Sharded BlockchainsProceedings of the 4th ACM Conference on Advances in Financial Technologies10.1145/3558535.3559783(198-216)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1145/3558535.3559783
Das SXiang ZRen LKim YKim JVigna GShi E(2021)Asynchronous Data Dissemination and its ApplicationsProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484808(2705-2721)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484808
Show More Cited By

Recommendations

Paillier-based publicly verifiable (non-interactive) secret sharing

A verifiable secret sharing is a secret sharing scheme with an untrusted dealer that allows participants to verify validity of their own shares. A publicly verifiable secret sharing (PVSS) scheme is a verifiable secret sharing scheme that allows a third ...
Strong (n,t,n) verifiable secret sharing scheme

A (t,n) secret sharing divides a secret into n shares in such a way that any t or more than t shares can reconstruct the secret; but fewer than t shares cannot reconstruct the secret. In this paper, we extend the idea of a (t,n) secret sharing scheme ...
Publicly verifiable multi‐secret sharing scheme from bilinear pairings

In a verifiable multi‐secret sharing (VMSS) scheme, multiple secrets are shared among participants during one sharing process in such a way that some qualified subsets of them can recover these secrets. Verifiable property means that one participant may ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology

August 1999

638 pages

ISBN:3540663479

Editor:
Michael J. Wiener

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 August 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sober MKobelt MScaffino GKaaser DSchulte SHong JLanperne MPark JCerny TShahriar H(2023)Distributed Key Generation with Smart Contracts using zk-SNARKsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577677(231-240)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577677
Han RYu JZhang RHerlihy MNarula N(2022)Analysing and Improving Shard Allocation Protocols for Sharded BlockchainsProceedings of the 4th ACM Conference on Advances in Financial Technologies10.1145/3558535.3559783(198-216)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1145/3558535.3559783
Das SXiang ZRen LKim YKim JVigna GShi E(2021)Asynchronous Data Dissemination and its ApplicationsProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484808(2705-2721)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484808
Kokoris-Kogias EAlp EGasser LJovanovic PSyta EFord B(2020)CALYPSOProceedings of the VLDB Endowment10.14778/3436905.343691714:4(586-599)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.14778/3436905.3436917
Becerra DVega G(2019)Secret Sharing Scheme with Efficient Cheating DetectionProceedings of the 2nd International Conference on Networking, Information Systems & Security10.1145/3320326.3320331(1-7)Online publication date: 27-Mar-2019
https://dl.acm.org/doi/10.1145/3320326.3320331
Reniers VVan Landuyt DViviani PLagaisse BLombardi RJoosen WHung CPapadopoulos G(2019)Analysis of architectural variants for auditable blockchain-based private data sharingProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297316(346-354)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297316
Matos DPardal MCarle GCorreia MPierre GFerreira PShrira L(2018)RockFSProceedings of the 19th International Middleware Conference10.1145/3274808.3274817(107-119)Online publication date: 26-Nov-2018
https://dl.acm.org/doi/10.1145/3274808.3274817
Matos DPardal MAdão PSilva ACorreia M(2018)Securing Electronic Health Records in the CloudProceedings of the 1st Workshop on Privacy by Design in Distributed Systems10.1145/3195258.3195259(1-6)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3195258.3195259
Barreto LScheunemann LFraga JSiqueira FShin SShin DLencastre M(2017)Secure storage of user credentials and attributes in federation of cloudsProceedings of the Symposium on Applied Computing10.1145/3019612.3019627(364-369)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3019612.3019627
Pilaram HEghlidos T(2017)An Efficient Lattice Based Multi-Stage Secret Sharing SchemeIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2015.243280014:1(2-8)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TDSC.2015.2432800
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents