|
ABSTRACT
In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k - 1 pieces reveals absolutely no information about D. This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
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
|
|
| |
2
|
Blakley, G.R. Safeguarding cryptographic keys. Proc. AFIPS 1979 NCC, Vol. 48, Arlington, Va., June 1979, pp. 313-317.
|
| |
3
|
|
| |
4
|
Liu, C.L. Introduction to Combinatorial Mathematics. McGraw- Hill, New York, 1968.
|
 |
5
|
|
CITED BY 431
|
|
|
|
|
|
|
|
|
|
|
Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States
|
|
|
|
|
|
|
|
|
Thomas Beth , Hans-Joachim Knobloch , Marcus Otten, Verifiable secret sharing for monotone access structures, Proceedings of the 1st ACM conference on Computer and communications security, p.189-194, November 03-05, 1993, Fairfax, Virginia, United States
|
|
|
|
|
|
|
|
|
David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
Mihir Bellare , Juan A. Garay , Tal Rabin, Distributed pseudo-random bit generators—a new way to speed-up shared coin tossing, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.191-200, May 23-26, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
Oded Goldreich , Dana Ron , Madhu Sudan, Chinese remaindering with errors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.225-234, May 01-04, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ronald Cramer , Ivan Damgård , Stefan Dziembowski, On the complexity of verifiable secret sharing and multiparty computation, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.325-334, May 21-23, 2000, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yair Frankel , Philip D. MacKenzie , Moti Yung, Robust efficient distributed RSA-key generation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.663-672, May 24-26, 1998, Dallas, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Boaz Barak , Amir Herzberg , Dalit Naor , Eldad Shai, The proactive security toolkit and applications, Proceedings of the 6th ACM conference on Computer and communications security, p.18-27, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
|
|
|
|
|
|
Amir Herzberg , Markus Jakobsson , Stanislław Jarecki , Hugo Krawczyk , Moti Yung, Proactive public key and signature systems, Proceedings of the 4th ACM conference on Computer and communications security, p.100-110, April 01-04, 1997, Zurich, Switzerland
|
|
|
|
|
|
|
|
|
|
|
|
Mike Just , Evangelos Kranakis , Danny Krizanc , Paul van Oorschot, On key distribution via true broadcasting, Proceedings of the 2nd ACM Conference on Computer and communications security, p.81-88, November 1994, Fairfax, Virginia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. J. Mitchell , F. C. Piper , M. Walker , P. Wild, Authentication Schemes, Perfect Local Randomizers, Perfect Secrecy and Secret Sharing Schemes, Designs, Codes and Cryptography, v.7 n.1-2, p.101-110, Jan. 1996
|
|
|
|
|
|
|
|
|
Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alfredo De Santis , Yvo Desmedt , Yair Frankel , Moti Yung, How to share a function securely, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.522-533, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
Ran Canetti , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Randomness vs. fault-tolerance, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.35-44, August 21-24, 1997, Santa Barbara, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
Ira S. Moskowitz , Myong H. Kang , LiWu Chang , Garth E. Longdon, Randomly roving agents for intrusion detection, Proceedings of the fifteenth annual working conference on Database and application security, p.135-149, July 15-18, 2001, Niagara, Ontario, Canada
|
|
|
|
|
|
|
|
|
Sergey Gorinsky , Sugat Jain , Harrick Vin , Yongguang Zhang, Robustness to inflated subscription in multicast congestion control, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Olivier Baudron , Pierre-Alain Fouque , David Pointcheval , Jacques Stern , Guillaume Poupard, Practical multi-candidate election system, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.274-283, August 2001, Newport, Rhode Island, United States
|
|
|
|
|
|
|
|
|
|
|
|
Biao Li , Zhen-fu Cao , Shen-sheng Zhang, Infinite resilient key-evolving scheme, Proceedings of the 15th international conference on Computer communication, p.561-564, August 12-14, 2002, Mumbai, Maharashtra, India
|
|
|
|
|
|
|
|
|
|
|
|
Biao Li , Shen-sheng Zhang , Ke-fei Chen, Scalable threshold scheme without a trusted third party, Proceedings of the 15th international conference on Computer communication, p.853-858, August 12-14, 2002, Mumbai, Maharashtra, India
|
|
|
Dag Johansen , Kåre J. Lauvset , Robbert van Renesse , Fred B. Schneider , Nils P. Sudmann , Kjetil Jacobsen, A TACOMA retrospective, Software—Practice & Experience, v.32 n.6, p.605-619, May 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hao Yang , Xiaoqiao Meng , Songwu Lu, Self-organized network-layer security in mobile ad hoc networks, Proceedings of the 3rd ACM workshop on Wireless security, p.11-20, September 28-28, 2002, Atlanta, GA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jiwu Jing , Peng Liu , Dengguo Feng , Ji Xiang , Neng Gao , Jingqiang Lin, ARECA: a highly attack resilient certification authority, Proceedings of the 2003 ACM workshop on Survivable and self-regenerative systems: in association with 10th ACM Conference on Computer and Communications Security, p.53-63, October 31-31, 2003, Fairfax, VA
|
|
|
Sara Miner More , Michael Malkin , Jessica Staddon , Dirk Balfanz, Sliding-window self-healing key distribution, Proceedings of the 2003 ACM workshop on Survivable and self-regenerative systems: in association with 10th ACM Conference on Computer and Communications Security, p.82-90, October 31-31, 2003, Fairfax, VA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alexandr Andoni , Jessica Staddon, Graceful service degradation (or, how to know your payment is late), Proceedings of the 6th ACM conference on Electronic commerce, p.9-18, June 05-08, 2005, Vancouver, BC, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vishal Kher , Yongdae Kim, Securing distributed storage: challenges, techniques, and systems, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA
|
|
|
|
|
|
|
|
|
Hao Yin , Chuang Lin , Berton Sebastien , Xiaowen Chu, A novel secure wireless video surveillance system based on Intel IXP425 network processor, Proceedings of the 1st ACM workshop on Wireless multimedia networking and performance modeling, October 13-13, 2005, Montreal, Quebec, Canada
|
|
|
|
|
|
Joseph Chee Ming Teo , Chik How Tan, Energy-efficient and scalable group key agreement for large ad hoc networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mark W. Storer , Kevin M. Greenan , Ethan L. Miller , Kaladhar Voruganti, POTSHARDS: secure long-term storage without encryption, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
|
|
|
|
|
|
|
|
|
|
|
|
Y. Dong , Ai-Fen Sui , S. M. Yiu , Victor O. K. Li , Lucas C. K. Hui, Providing distributed certificate authority service in cluster-based mobile ad hoc networks, Computer Communications, v.30 n.11-12, p.2442-2452, September, 2007
|
|
|
|
|
|
Kun-Yuan Chao , Ja-Chen Lin, (2, 3)-threshold visual cryptography for color images, Proceedings of the 6th WSEAS International Conference on Signal Processing, Computational Geometry & Artificial Vision, p.89-94, August 21-23, 2006, Elounda, Greece
|
|
|
|
|
|
Adam J. Lee , Marianne Winslett , Jim Basney , Von Welch, Traust: a trust negotiation-based authorization service for open systems, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA
|
|
|
H. W. Go , P. Y. Chan , Y. Dong , A. F. Sui , S. M. Yiu , Lucas C. K. Hui , Victor O. K. Li, Performance evaluation on CRL distribution using flooding in mobile ad hoc networks (MANETs), Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
|
|
|
Matthew Pirretti , Patrick Traynor , Patrick McDaniel , Brent Waters, Secure attribute-based systems, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mark W. Storer , Kevin M. Greenan , Ethan L. Miller , Kaladhar Voruganti, Secure, archival storage with POTSHARDS, Proceedings of the 5th conference on USENIX Conference on File and Storage Technologies, p.11-11, February 13-16, 2007, San Jose, CA
|
|
|
|
|
|
|
|
|
|
|
|
Vipul Goyal , Omkant Pandey , Amit Sahai , Brent Waters, Attribute-based encryption for fine-grained access control of encrypted data, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
|
|
|
|
|
|
|
|
|
Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
|
|
|
|
|
|
Bing Wu , Jie Wu , Eduardo B. Fernandez , Mohammad Ilyas , Spyros Magliveras, Secure and efficient key management in mobile ad hoc networks, Journal of Network and Computer Applications, v.30 n.3, p.937-954, August, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Marc Waldman , Aviel D. Rubin , Lorrie Faith Cranor, Publius: a robust, tamper-evident, censorship-resistant web publishing system, Proceedings of the 9th conference on USENIX Security Symposium, p.5-5, August 14-17, 2000, Denver, Colorado
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zachary N. J. Peterson , Randal Burns , Joe Herring , Adam Stubblefield , Aviel D. Rubin, Secure deletion for a versioning file system, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.11-11, December 13-16, 2005, San Francisco, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rongxing Lu , Xiaodong Lin , Zhenfu Cao , Jun Shao , Xiaohui Liang, New (t,n) threshold directed signature scheme with provable security, Information Sciences: an International Journal, v.178 n.3, p.756-765, February, 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Zero-knowledge from secure multiparty computation, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rabia Riaz , Ayesha Naureen , Attiya Akram , Ali Hammad Akbar , Ki-Hyung Kim , H. Farooq Ahmed, A unified security framework with three key management schemes for wireless sensor networks, Computer Communications, v.31 n.18, p.4269-4280, December, 2008
|
|
|
Daniel Sandler , Kyle Derr , Dan S. Wallach, VoteBox: a tamper-evident, verifiable electronic voting system, Proceedings of the 17th conference on Security symposium, p.349-364, July 28-August 01, 2008, San Jose, CA
|
|
|
David Chaum , Richard Carback , Jeremy Clark , Aleksander Essex , Stefan Popoveniuc , Ronald L. Rivest , Peter Y. A. Ryan , Emily Shen , Alan T. Sherman, Scantegrity II: end-to-end verifiability for optical scan election systems using invisible ink confirmation codes, Proceedings of the conference on Electronic voting technology, p.1-13, July 28-29, 2008, San Jose, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Carmela Troncoso , George Danezis , Eleni Kosta , Bart Preneel, Pripayd: privacy friendly pay-as-you-drive insurance, Proceedings of the 2007 ACM workshop on Privacy in electronic society, October 29-29, 2007, Alexandria, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wensheng Zhang , Minh Tran , Sencun Zhu , Guohong Cao, A random perturbation-based scheme for pairwise key establishment in sensor networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sergej Zerr , Elena Demidova , Daniel Olmedilla , Wolfgang Nejdl , Marianne Winslett , Soumyadeb Mitra, Zerber: r-confidential indexing for distributed documents, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xiaoyan Hong , Dijiang Huang , Mario Gerla , Zhen Cao, SAT: situation-aware trust architecture for vehicular networks, Proceedings of the 3rd international workshop on Mobility in the evolving internet architecture, August 22-22, 2008, Seattle, WA, USA
|
|
|
Jen-Bang Feng , Hsien-Chu Wu , Chwei-Shyong Tsai , Ya-Fen Chang , Yen-Ping Chu, Visual secret sharing for multiple secrets, Pattern Recognition, v.41 n.12, p.3572-3581, December, 2008
|
|
|
|
|
|
Mark W. Storer , Kevin Greenan , Darrell D.E. Long , Ethan L. Miller, Secure data deduplication, Proceedings of the 4th ACM international workshop on Storage security and survivability, October 31-31, 2008, Alexandria, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mark Manulis , Damien Leroy , Francois Koeune , Olivier Bonaventure , Jean-Jacques Quisquater, Authenticated wireless roaming via tunnels: making mobile guests feel at home, Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, March 10-12, 2009, Sydney, Australia
|
|
|
Cong Tang , Ruichuan Chen , Zhuhua Cai , Anmin Xie , Jianbin Hu , Liyong Tang , Zhong Chen, Securing key issuing in peer-to-peer networks, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Federica Paci , Ning Shang , Sam Kerr , Kevin Steuer, Jr , Jungha Woo , Elisa Bertino, Privacy-preserving management of transactions' receipts for mobile environments, Proceedings of the 8th Symposium on Identity and Trust on the Internet, April 14-16, 2009, Gaithersburg, Maryland
|
|
|
|
|
|
|
|
|
|
|
|
Jun Kurihara , Shinsaku Kiyomoto , Kazuhide Fukushima , Toshiaki Tanaka, A Fast (3,n)-Threshold Secret Sharing Scheme Using Exclusive-OR Operations, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.127-138, January 2008
|
|
|
|
|
|
|
|
|
Jun Kurihara , Shinsaku Kiyomoto , Kazuhide Fukushima , Toshiaki Tanaka, On a Fast (k,n)-Threshold Secret Sharing Scheme, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.9, p.2365-2378, September 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mark W. Storer , Kevin M. Greenan , Ethan L. Miller , Kaladhar Voruganti, POTSHARDS—a secure, recoverable, long-term archival storage system, ACM Transactions on Storage (TOS), v.5 n.2, p.1-35, June 2009
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xiaodong Lin , Pin-Han Ho , Xuemin (Sherman) Shen, Towards compromise-resilient localized authentication architecture for wireless mesh networks, The Fourth International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness & Workshops, August 14-17, 2007, Vancouver, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
K. Farkas , O. Wellnitz , M. Dick , X. Gu , M. Busse , W. Effelsberg , Y. Rebahi , D. Sisalem , D. Grigoras , K. Stefanidis , D. N. Serpanos, Real-time service provisioning for mobile and wireless networks, Computer Communications, v.29 n.5, p.540-550, March, 2006
|
|
|
Ryan W. Gardner , Sujata Garera , Matthew W. Pagano , Matthew Green , Aviel D. Rubin, Securing medical records on smart phones, Proceedings of the first ACM workshop on Security and privacy in medical and home-care systems, November 13-13, 2009, Chicago, Illinois, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mitsugu Iwamoto , Hirosuke Yamamoto , Hiroki Koga, A coding theorem for cheating-detectable (2, 2)-threshold blockwise secret sharing schemes, Proceedings of the 2009 IEEE international conference on Symposium on Information Theory, p.1308-1312, June 28-July 03, 2009, Coex, Seoul, Korea
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|