Robust computational secret sharing and a unified account of classical secret-sharing goals

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Robust computational secret sharing and a unified account of classical secret-sharing goals

Full text

Pdf (333 KB)

Source

Conference on Computer and Communications Security archive
Proceedings of the 14th ACM conference on Computer and communications security table of contents

Alexandria, Virginia, USA

SESSION: Cryptography table of contents

Pages: 172 - 184

Year of Publication: 2007

ISBN:978-1-59593-703-2

Authors

Phillip Rogaway	University of California: Davis, Davis, CA
Mihir Bellare	University of California: San Diego, La Jolla, CA

Sponsors

ACM: Association for Computing Machinery
SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 152, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1315245.1315268 What is a DOI?

ABSTRACT

We give a unified account of classical secret-sharing goals from a modern cryptographic vantage. Our treatment encompasses perfect, statistical, and computational secret sharing; static and dynamic adversaries; schemes with or without robustness; schemes where a participant recovers the secret and those where an external party does so. We then show that Krawczyk's 1993 protocol for robust computational secret sharing (RCSS) need not be secure, even in the random-oracle model and for threshold schemes, if the encryption primitive it uses satisfies only one-query indistinguishability (ind1), the only notion Krawczyk defines. Nonetheless, we show that the protocol is secure (in the random-oracle model, for threshold schemes) if the encryption scheme also satisfies one-query key-unrecoverability (key1). Since practical encryption schemes are ind1+key1 secure, our result effectively shows that Krawczyk's RCSS protocol is sound (in the random-oracle model, for threshold schemes). Finally, we prove the security for a variant of Krawczyk's protocol, in the standard model and for arbitrary access structures, assuming ind1 encryption and a statistically-hiding, weakly-binding commitment scheme.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. Béguin and A. Cresti. General short computational secret sharing schemes. Eurocrypt '95.
	2	A. Beimel and B. Chor. Universally ideal secret sharing schemes. IEEE Trans. on Info. Theory, 40(3):786--794, 1994.
	3	Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
	4	M. Bellare and P. Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. Eurocrypt '06.
	5	Mihir Bellare , Phillip Rogaway, Collision-Resistant Hashing: Towards Making UOWHFs Practical, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.470-484, August 17-21, 1997
	6	Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
	7	M. Bellare and P. Rogaway. Robust computational secret sharing and a unified account of classical secret-sharing goals. Full version of this paper. Cryptology ePrint Report 2006/449, 2006.
	8	Josh Cohen Benaloh , Jerry Leichter, Generalized Secret Sharing and Monotone Functions, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.27-35, August 21-25, 1988
	9	G. Blakley. Safeguarding cryptographic keys. AFIPS National Computer Conference, vol. 48, pp. 313--317, 1979.
	10	Joan F. Boyar , Stuart A. Kurtz, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology, v.2 n.2, p.63-76, 1990
	11	E. F. Brickell , D. R. Stinson, The detection of cheaters in threshold schemes, SIAM Journal on Discrete Mathematics, v.4 n.4, p.502-510, Nov. 1991 [doi>10.1137/0404044]
	12	E. F. Brickell , D. R. Stinson, Some improved bounds on the information rate of perfect secret sharing schemes, Journal of Cryptology, v.5 n.3, p.153-166, 1992 [doi>10.1007/BF02451112]
	13	Christian Cachin, On-Line Secret Sharing, Proceedings of the 5th IMA Conference on Cryptography and Coding, p.190-198, December 18-20, 1995
	14	R. Capocelli, A. DeSantis, L. Gargano, and U. Vaccaro. On the size of shares for secret sharing schemes. J. of Cryptology, 6:157--167, 1993.
	15	Marco Carpentieri , Alfredo De Santis , Ugo Vaccaro, Size of shares and probability of cheating in threshold schemes, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.118-125, January 1994, Lofthus, Norway
	16	B. Chor, S. Goldwasser, S. Micali, and B. Awerbach. Verifiable secret sharing and achieving simultaneity in the presence of faults. FOCS '85.
	17	I. Damgård, T. Pedersen, and B. Pfitzmann. On the existence of statistically hiding bit commitment schemes and fail-stop signatures. J. of Cryptology, 10(3), pp. 163--194, 1997.
	18	Cynthia Dwork , Moni Naor , Omer Reingold , Larry Stockmeyer, Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998, Journal of the ACM (JACM), v.50 n.6, p.852-921, November 2003 [doi>10.1145/950620.950623]
	19	P. Feldman. A practical scheme for non-interactive verifiable secret sharing. FOCS '87.
	20	G. Ganger, P. Khosla, M. Bakkaloglu, M. Bigrigg, G. Goodson, S. Oguz, V. Pandurangan, C. Soules, J. Strunk, and J. Wylie. Survivable storage systems. DARPA Information Survivability Conference and Exposition, vol. 2, IEEE Press, pp. 184--195, 2001.
	21	S. Goldwasser and S. Micali. Probabilistic encryption. JCSS, 28(2):270--299, 1984.
	22	Shai Halevi , Silvio Micali, Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.201-215, August 18-22, 1996
	23	I. Haitner and O. Reingold. Statistically-hiding commitment from any one-way function. Cryptology ePrint report 2006/436, 2006.
	24	Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
	25	Y. Ishai. Personal communication, February 2007.
	26	M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structure. IEEE Globecom 87, pp. 99--102, 1987.
	27	A. Iyengar, R. Cahn, C. Jutla, and J. Garay. Design and implementation of a secure distributed data repository. 14th IFIP International Information Security Conference, pp. 123--135, 1998.
	28	W. Jackson and K. Martin. Combinatorial models for perfect secret-sharing schemes. J. of Comb. Mathematics and Comb. Computing, vol. 28, pp. 249--265, 1998.
	29	E. Karnin, J. Greene, and M. Hellman. On secret sharing systems. IEEE Trans. on Inf. Theory, 29(1):35--51, 1983.
	30	Hugo Krawczyk, Secret sharing made short, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.136-146, January 1994, Santa Barbara, California, United States
	31	Hugo Krawczyk, Distributed fingerprints and secure information dispersal, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.207-218, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164075]
	32	S. Lakshmanan, M. Ahamad, and H. Venkateswaran. Responsive security for stored data. IEEE Trans. on Parallel and Distributed Systems, 14(9):818--828, 2003.
	33	A. Mayer , M. Yung, Generalized Secret Sharing and Group-Key Distribution using Short Keys, Proceedings of the Compression and Complexity of Sequences 1997, p.30, June 11-13, 1997
	34	R. J. McEliece , D. V. Sarwate, On sharing secrets and Reed-Solomon codes, Communications of the ACM, v.24 n.9, p.583-584, Sept. 1981 [doi>10.1145/358746.358762]
	35	M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. Perfect zero-knowledge arguments for NP using any one-way permutation. J. of Crypt. 11(2):87--108, 1998.
	36	M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
	37	A. Paul, S. Adhikari, and U. Ramachandran. Design of a secure and fault tolerant environment for distributed storage. Tech. Report GIT-CERCS-04-02, Georgia Tech, 2004.
	38	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
	39	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	40	J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
	41	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
	42	C. Shannon. A mathematical theory of communication. Bell System Technical Journal, vol. 27, pp. 379--423 and pp. 623--656, July and October, 1948.
	43	D. R. Stinson, An explication of secret sharing schemes, Designs, Codes and Cryptography, v.2 n.4, p.357-390, Dec. 1992 [doi>10.1007/BF00125203]
	44	M. Tompa , H. Woll, How to share a secret with cheaters, Journal of Cryptology, v.1 n.2, p.133-138, Aug. 1988
	45	V. Vinod, A. Narayanan, K. Srinathan, C. Rangan, and K. Kim. On the power of computational secret sharing. Indocrypt '03.
	46	Marc Waldman , Aviel D. Rubin , Lorrie Faith Cranor, The architecture of robust publishing systems, ACM Transactions on Internet Technology (TOIT), v.1 n.2, p.199-230, November 2001 [doi>10.1145/502152.502154]
	47	H. Witsenhausen. The zero-error side information problem and chromatic numbers. IEEE Transactions on Information Theory, vol. 22, no. 5, pp. 592--593, 1976.
	48	Jay J. Wylie , Michael W. Bigrigg , John D. Strunk , Gregory R. Ganger , Han Kiliççöte , Pradeep K. Khosla, Survivable Information Storage Systems, Computer, v.33 n.8, p.61-68, August 2000 [doi>10.1109/2.863969]