Article

Free access

How to share a function securely

Authors:

Alfredo De Santis,

Yvo Desmedt,

Yair Frankel,

Moti YungAuthors Info & Claims

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

Pages 522 - 533

https://doi.org/10.1145/195058.195405

Published: 23 May 1994 Publication History

PDF eReader

References

[1]

W. Alexi, B. Chor, O. Goldreich and C. Schnorr, RSA/Rabin Bits are 1/2+l/poly Secure, Siam Journal on Computing, 17(2) (1988), pp.194-209.

Digital Library

Google Scholar

[2]

M. Bellare, L. Cowen, and S. Goldwasser, On the Structure o} Secret Key Exchange, Distributed Computing and Cryptography, DIMACS series in Disc. Math. and Th. Comp. SCi., v. 2, AMS and ACM, pp 79-92, (Eds. J. Feigenbaum and M. Merritt).

Google Scholar

[3]

M. Bellare and S. Micali, How to Sign Given Any Trapdoor Function, Journal of the ACM, (39), 1992, pp. 214-233.

Digital Library

Google Scholar

[4]

J. C. Benaloh. Secret sharing homomorphisms: Keeping shares of a secret secret. Advances in Cryptology, Proc. of Crypto'86 LNCS 263, 1987, pp 251- 260.

Digital Library

Google Scholar

[5]

G.R. Blakley, Safeguarding Cryptographic Keys, AFIPS Con. Proc (v. 48), 1979, pp 313-317.

Google Scholar

[6]

M. Blum and S. Micali, How to generate cryptographically strong sequences of psuedo-random bits, SIAM Journal of Computing, 13(4), 1984.

Digital Library

Google Scholar

[7]

C. Boyd, Dig,tal Multisignatures, Cryptography and Coding, Claxedon Press, 241-246, (Eds. H. Baker and F. Piper).

Google Scholar

[8]

D.E. Denning at at., To Tap or Not To Tap. CACM 93.

Digital Library

Google Scholar

[9]

Y. Desmedt and Y. Frankel, Shared generation of authenticators and signatures, Advances in Cryptology-Froc. of Crypto 91, Springer-Verlag LNCS 576, 1992, pp. 307-315.

Digital Library

Google Scholar

[10]

Y. Desmedt and Y. Frankel, Perfect Zero-Knowledge Shamng Schemes over Any Abelian Group, Sequences II, Methods in Communication, Security and Computer Science, Springer-Verlag, 1993, pp. 369-378, (Eds. R. Capocelli, A. De Santis and U, Vaccaro). Journal version: SIAM J. on Disc. Math. (to appear).

Google Scholar

[11]

W. Diffle and M. Hellman, New Directions in Cryptography, IEEE Trans. on Information Theory 22 (6), 1976, pp. 644-654.

Digital Library

Google Scholar

[12]

T. E1 Gamal, A Public key cryptosystem and a signature scheme based on discrete logarithm, IEEE Trans. on Information Theory 31,465-472, 1985.

Google Scholar

[13]

M. Franklin and M. Yung, Secure and Efficient Off- Line Digital Money, Proc. of the 20th Int. Col. on Automata, Languages and Programming (ICALP), 1993, LNCS 700, Springer Verlag, pp. 265-276.

Digital Library

Google Scholar

[14]

Z. Galil, S. Haber and M. Yung, Minimum- Knowledge Interactive Proof for Decision Problems, SIAM J. Comp., 18, 1989, pp 711-739.

Digital Library

Google Scholar

[15]

S. Goldreich, S. Micah and A. Wigderson, Proofs that Yield Nothing But their Validity, and a Methodology of Cryptographic Protocol Design, J. ACM, 38 (1), 1991, pp 691-729.

Digital Library

Google Scholar

[16]

O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game, Proceedings of the Nineteenth annual ACM Syrup. Theory of Computing, 1987, pp 218-229.

Digital Library

Google Scholar

[17]

O. Goldreich and Y. Oren, Definitions and Properties of Zero-Knowledge Proof Systems, J. of Cryptology, 7(1), pp 1-32, 1994.

Digital Library

Google Scholar

[18]

S. Goldwasser and S. Micah, Probat, iIistic Encryption, J. Com. Sys. Sci. 28 (1984), pp 270-299.

Crossref

Google Scholar

[19]

S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof.Systems, Siam J. on Computing, 18(1) (1989), pp 186-208.

Digital Library

Google Scholar

[20]

S. Goldwasser, S. Micali and R. Rivest, A Secure Digital Signature Scheme, Siam Journal on Computing, Vol. 17, 2 (1988), pp. 281-308.

Digital Library

Google Scholar

[21]

G. Hardy and E. Wright An introducl!ion to the theory of numbers, Oxford Science Publications, London, Great Britain, fifth ed., 1985

Google Scholar

[22]

OSI Directory - Part 8: Authentication Framework. ISO (Int. Standard Organization) 9594-8, Geneva (19ss).

Google Scholar

[23]

M. Luby, PseudoRandomness and Applications, Princeton University Press, (to appeaw).

Digital Library

Google Scholar

[24]

S. Micali, Fair public-key cryptosystems, Crypto '92.

Digital Library

Google Scholar

[25]

T. Okamoto, A digital muItisignature scheme using bijective public-key cryptosystems, ACM Trans. on Computer Systems, 6(8), 1988, pp. 432-441.

Digital Library

Google Scholar

[26]

R. Ostrovsky, R. Venkatesan and M Yung, Fazr Games aga,nst an All-PowerJuI Adversary, Sequences II, Methods in Communication, Security and Computer Science, Springer-Verlag, 1993, pp. 418-429, (Eds. R. Capocelli, A. De Santis and U. Vaccaro).

Google Scholar

[27]

R. Ostrovsky and M Yung, On Necessary Condiputing and Cryptography, DIMACS series in Disc. Math. and Th. Comp. SCi., v. 2, AMS and ACM, pp 229-235, (Eds. J. Feigenbaum and M. Merritt).

Google Scholar

[28]

M. Naor and M. Yung, Public-key cryptosytems provably secure against chosen ciphertext attack, Proc. of the 22nd Annum Symposium on the Theory of Computing, 1990, pp. 427-437.

Digital Library

Google Scholar

[29]

M. Reiter and K. Birman, How to securely replicate services, TR92-1274, Cornell University, 1992.

Google Scholar

[30]

R. Rivest, A. Shamir and L. Adleman, A Method }or Obtaining Digital Signature and Pubhc Key Cryptosystems, Comm. of ACM, 21 (1978), pp 120-126.

Digital Library

Google Scholar

[31]

R. L. Rivest and M. E. HelIman and J. C. Anderson, Responses to NIST's proposal, Commun. ACM, 35(#), 1992, pp. 41-s4.

Digital Library

Google Scholar

[32]

RSA Data Security Inc. publication. Certificate Issuing Unit, manual.

Google Scholar

[33]

A. Shaxnir. How to share a secret, Colnmun. ACM, 22 (1979), pp 612-613.

Digital Library

Google Scholar

[34]

A. C. Yao, Theory and Applications of Trapdoor the Foundation of Computer Science, 1982, pp. 80- 91.

Google Scholar

Cited By

View all

Cheon JCho WKim J(2025)Improved Universal Thresholdizer from Iterative Shamir Secret SharingJournal of Cryptology10.1007/s00145-024-09536-z38:1Online publication date: 13-Jan-2025
https://doi.org/10.1007/s00145-024-09536-z
Desmedt Y(2025)Threshold CryptographyEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_330(2602-2609)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_330
Bleumer G(2025)Threshold SignatureEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_233(2610-2613)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_233
Show More Cited By

Index Terms

How to share a function securely

Recommendations

Ideal Secret Sharing Schemes with Share Selectability
Information and Communications Security
Abstract
In this paper, we investigate a new concept, called share selectable secret sharing, where no unauthorized set can obtain information of the secret (in the information-theoretic sense) even if shares are selectable as arbitrary values which are ...
The Size of a Share Must Be Large

A secret sharing scheme permits a secret to be shared among participants of an n -element group in such a way that only qualified subsets of participants can recover the secret. If any nonqualified subset has absolutely no information on the secret, ...
Image Secret Sharing Construction for General Access Structure with Meaningful Share

This article describes how the (k, n) threshold image secret sharing technology can recover the secret image even n − k shares are lost, or n−k servers do not work, which is useful for cloud storage, etc. Image secret sharing for general access ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

May 1994

822 pages

ISBN:0897916638

DOI:10.1145/195058

Chairmen:
F. Tom Leighton
Massachusetts Institue of Technology, Cambridge
,
Michael Goodrich
Johns Hopkins Univ., Baltimore, MD

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC94

Sponsor:

SIGACT

STOC94: Symposium on Theory of Computing

May 23 - 25, 1994

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

224
Total Citations
View Citations
2,276
Total Downloads

Downloads (Last 12 months)246
Downloads (Last 6 weeks)35

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cheon JCho WKim J(2025)Improved Universal Thresholdizer from Iterative Shamir Secret SharingJournal of Cryptology10.1007/s00145-024-09536-z38:1Online publication date: 13-Jan-2025
https://doi.org/10.1007/s00145-024-09536-z
Desmedt Y(2025)Threshold CryptographyEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_330(2602-2609)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_330
Bleumer G(2025)Threshold SignatureEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_233(2610-2613)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_233
Choudhuri AGarg SPiet JPolicharla GBalzarotti DXu W(2024)Mempool privacy via batched threshold encryptionProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699097(3513-3529)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699097
Mahe EAbdallah RTucci-Piergiovanni SPiriou P(2024)Adversary-Augmented Simulation to evaluate order-fairness on HyperLedger FabricProceedings of the 13th Latin-American Symposium on Dependable and Secure Computing10.1145/3697090.3697093(126-135)Online publication date: 26-Nov-2024
https://dl.acm.org/doi/10.1145/3697090.3697093
Dziembowski SFaust SLizurej TMielniczuk MLuo BLiao XXu JKirda ELie D(2024)Secret Sharing with SnitchingProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690296(840-853)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690296
Yoshida M(2024)Towards Optimal Non-interactive Secure Multiparty Computation for Abelian Programs2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619511(1878-1882)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619511
De Santis AFerrara AMasucci BVenditti G(2024)An Information-Theoretic Approach to Anonymous Access Control2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619391(3326-3331)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619391
Chairattana-Apirom RTessaro SZhu C(2024)Partially Non-interactive Two-Round Lattice-Based Threshold SignaturesAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0894-2_9(268-302)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0894-2_9
Bellare MRiepel DTessaro SZhang Y(2024)Count Corruptions, Not Users: Improved Tightness for Signatures, Encryption and Authenticated Key ExchangeAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0888-1_11(326-360)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0888-1_11
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Ideal Secret Sharing Schemes with Share Selectability

The Size of a Share Must Be Large

Image Secret Sharing Construction for General Access Structure with Meaningful Share