Article

Secret sharing homomorphisms: keeping shares of a secret secret

Author:

Josh Cohen BenalohAuthors Info & Claims

Proceedings on Advances in cryptology---CRYPTO '86

Pages 251 - 260

Published: 01 January 1987 Publication History

Abstract

In 1979, Blackley and Shamir independently proposed schemes by which a secret can be divided into many shares which can be distributed to mutually suspicious agents. This paper describes a homomorphism property attained by these and several other secret sharing schemes which allows multiple secrets to be combined by direct computation on shares. This property reduces the need for trust among agents and allows secret sharing to be applied to many new problems. One application described here gives a method of verifiable secret sharing which is much simpler and more efficient than previous schemes. A second application is described which gives a fault-tolerant method of holding verifiable secret-ballot elections.

References

[1]

Adleman, L. "Subexponential Algorithm for The Discrete Logarithm Problem." Proc. 20th IEEE Symp. on Foundations of Computer Science , San Juan, PR (Oct. 1979), 55-60.

[2]

Asmuth, C. and Bloom, J. "A Modular Approach to Key Safeguarding." Texas A&M University, Departement of Mathematics , College Station, TX (1980).

[3]

Benaloh, J. and Yung, M. "Distributing the Power of a Government to Enhance the Privacy of Voters." Proc. 5th ACM Symp. on Principles of Distributed Computing , Calgary, AB (Aug. 1986).

[4]

Blakley, G. "Safeguarding Cryptographic Keys." Proc. AFIPS 1979 National Computer Conference , New York, NY (June 1979), 313-317.

[5]

Blakley, G. and Meadows, C. "A Database Encryption Scheme Which Allows the Computation of Statistics Using Encrypted Data." Proc. IEEE Symposium on Computer Security and Privacy , Oakland, CA (Apr. 1985).

[6]

Chor, B., Goldwasser, S., Micali, S., and Awerbuch, B. "Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults." Proc. 26th IEEE Symp. on Foundations of Computer Science , Portland, OR (Oct. 1985), 383-395.

[7]

Cohen, J. and Fischer, M. "A Robust and Verifiable Cryptographically Secure Election Scheme." Proc. 26th IEEE Symp. on Foundations of Computer Science , Portland, OR (Oct. 1985), 372-382.

[8]

Cohen, J. "Improving Privacy in Cryptographic Elections." TR-454, Yale University, Departement of Computer Science , New Haven, CT (Feb. 1986).

[9]

Coppersmith, D., Odlyzko, A., and Schroeppel, R. "Discrete Logarithms in GF ( p )." Algorithmica , 1 (1986), 1-15.

[10]

DeMillo, R., Lynch, N., and Merritt, M. "Cryptographic Protocols." Proc. 14th ACM Symp. on Theory of Computing , San Francisco, CA (May 1982), 383-400.

[11]

Feigenbaum, J. "Encrypting Problem Instances or Can You Take Advantage of Someone Without Having to Trust Him", Proc. Crypto '85 , Santa Barbara, CA (Aug. 1985), 477-488. Published as Advances in Cryptology , ed. by H. Williams in Lecture Notes in Computer Science , vol. 218, ed. by G. Goos and J. Hartmanis. Springer-Verlag, New York (1985).

[12]

Fischer, M., Micali, S., and Rackoff, C. "A Secure Protocol for the Oblivious Transfer." Presented at Eurocrypt84 , Paris, France (Apr. 1984). (Not in proceedings.).

[13]

Goldwasser, S., Micali, S., and Rackoff C. "The Knowledge of Complexity of Interactive Proof-Systems." Proc. 17th ACM Symp. on Theory of Computing , Providence, RI (May 1985), 291-304.

[14]

Goldwasser, S. and Micali, S. "Probabilistic Encryption." J. Comput. System Sci. 28 , (1984), 270-299.

[15]

Kothari, S. "Generalized Linear Threshold Scheme." Proc. Crypto '84 , Santa Barbara, CA (Aug. 1984), 231-241. Published as Advances in Cryptology , ed. by G. Blakely and D. Chaum in Lecture Notes in Computer Science , vol. 196, ed. by G. Goos and J. Hartmanis. Springer-Verlag, New York (1985).

[16]

Pohlig, S. and Hellman, M. "An Improved Algorithm for Computing Logarithms Over GF(2) and Its Cryptographic Significance." IEEE Trans, on Information Theory 24 , 1 (Jan. 1978), 106-110.

[17]

Rivest, R., Adleman, L., and Dertouzos, M. "On Data Banks and Privacy Homomorphisms." Foundations of Secure Computation , ed. by R. A. DeMillo, et. al. Academic Press, New York (1978), 169-179.

[18]

Shamir, A. "How to Share a Secret." Comm. ACM 22 , 11 (Nov. 1979), 612-613.

[19]

Yao, A. "Protocols for Secure Computations." Proc. 23rd IEEE Symp. on Foundations of Computer Science , Chicago, IL (Nov. 1982), 160-164.

Cited By

Liu YZhao Q(2019)E-voting scheme using secret sharing and K-anonymityWorld Wide Web10.1007/s11280-018-0575-022:4(1657-1667)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s11280-018-0575-0
Grining KKlonowski MSyga P(2019)On practical privacy-preserving fault-tolerant data aggregationInternational Journal of Information Security10.1007/s10207-018-0413-518:3(285-304)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10207-018-0413-5
Singh PRaman BMisra M(2018)Just process me, without knowing meMultimedia Tools and Applications10.1007/s11042-017-4906-477:10(12581-12605)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11042-017-4906-4
Show More Cited By

Index Terms

Secret sharing homomorphisms: keeping shares of a secret secret

Recommendations

Enhance the visual quality of shares and recovered secret on meaningful shares visual secret sharing
ICUIMC '10: Proceedings of the 4th International Conference on Uniquitous Information Management and Communication

Visual secret sharing (VSS) schemes have been proposed by Naor and Shamir [1] in 1995. It encodes a binary secret image into several meaningless images called shares or transparencies. The secret image can be obtained by stacking the qualified set of ...
Fair secret reconstruction in (t, n) secret sharing

In Shamir's (t, n) threshold secret sharing scheme, one secret s is divided into n shares by a dealer and all shares are shared among n shareholders, such that knowing t or more than t shares can reconstruct this secret; but knowing fewer than t shares ...
Secret sharing with secure secret reconstruction
Abstract
Threshold secret sharing is a fundamental building block in information security to provide secrecy and robustness services for various cryptographic protocols. According to the definition of (t, n) threshold secret sharing, the secret ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings on Advances in cryptology---CRYPTO '86

January 1987

487 pages

ISBN:0387180478

Editor:
Andrew M. Odlyzko
AT&T Bell Laboratories, Murray Hill, NJ

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 1987

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YZhao Q(2019)E-voting scheme using secret sharing and K-anonymityWorld Wide Web10.1007/s11280-018-0575-022:4(1657-1667)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s11280-018-0575-0
Grining KKlonowski MSyga P(2019)On practical privacy-preserving fault-tolerant data aggregationInternational Journal of Information Security10.1007/s10207-018-0413-518:3(285-304)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10207-018-0413-5
Singh PRaman BMisra M(2018)Just process me, without knowing meMultimedia Tools and Applications10.1007/s11042-017-4906-477:10(12581-12605)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11042-017-4906-4
Harn LHsu CLi B(2018)Centralized Group Key Establishment Protocol without a Mutually Trusted Third PartyMobile Networks and Applications10.1007/s11036-016-0776-723:5(1132-1140)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s11036-016-0776-7
Wang ZCheung SLuo Y(2017)Information-Theoretic Secure Multi-Party Computation With Collusion DeterrenceIEEE Transactions on Information Forensics and Security10.1109/TIFS.2016.259853312:4(980-995)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TIFS.2016.2598533
Singh PRaman BMisra M(2017)A secure image sharing scheme based on SVD and Fractional Fourier TransformImage Communication10.1016/j.image.2017.04.01257:C(46-59)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.image.2017.04.012
Harn LHsu C(2017)(t, n) Multi-Secret Sharing Scheme Based on Bivariate PolynomialWireless Personal Communications: An International Journal10.1007/s11277-016-3862-z95:2(1495-1504)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s11277-016-3862-z
Sumana M. Hareesha K.S. (2016)Accurate Classification Models for Distributed Mining of Privately Preserved DataInternational Journal of Information Security and Privacy10.4018/IJISP.201610010410:4(58-73)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.4018/IJISP.2016100104
Singh PAgarwal NRaman BBatra DBrown MNatarajan V(2016)Don't see me, just filter meProceedings of the Tenth Indian Conference on Computer Vision, Graphics and Image Processing10.1145/3009977.3010036(1-8)Online publication date: 18-Dec-2016
https://dl.acm.org/doi/10.1145/3009977.3010036
Hu XZhang WLi KHu HYu N(2016)Secure Nonlocal Denoising in Outsourced ImagesACM Transactions on Multimedia Computing, Communications, and Applications10.1145/288677712:3(1-23)Online publication date: 8-Mar-2016
https://dl.acm.org/doi/10.1145/2886777
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents