Exploiting social networks for threshold signing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exploiting social networks for threshold signing: attack-resilience vs. availability

Full text

Pdf (526 KB)

Source

ASIAN ACM Symposium on Information, Computer and Communications Security archive
Proceedings of the 2008 ACM symposium on Information, computer and communications security table of contents

Tokyo, Japan

SESSION: Digital signatures (I) table of contents

Pages 325-336

Year of Publication: 2008

ISBN:978-1-59593-979-1

Authors

Shouhuai Xu	U. of Texas, San Antonio
Xiaohu Li	U. of Texas, San Antonio
Paul Parker	U. of Texas, San Antonio

Sponsor

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 98, 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/1368310.1368358 What is a DOI?

ABSTRACT

Digital signatures are an important security mechanism, especially when non-repudiation is desired. However, non-repudiation is meaningful only when the private signing keys and functions are adequately protected --- an assumption that is very difficult to accommodate in the real world because computers (and thus cryptographic keys and functions) could be relatively easily compromised. One approach to resolving, or at least alleviating, this problem is to use threshold cryptography. But how should such techniques be employed in the real world? In this paper we propose exploiting social networks whereby average users take advantage of their trusted ones to help secure their cryptographic keys. While the idea is simple from an individual user's perspective, we aim to understand the resulting systems from a whole-system perspective. Specifically, we propose and investigate two measures of the resulting systems: attack-resilience, which captures the security consequences due to the compromise of some computers and thus the compromise of the cryptographic key shares stored on them; availability, which captures the effect when computers are not always responsive (due to the peer-to-peer nature of social networks).

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	R. Albert and A. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47--97, 2002.
	2	R. Albert, H. Jeong, and A. Barabasi. Error and attack tolerance of complex networks. Nature, 406:378--482, 2000.
	3	Noga Alon, Spectral Techniques in Graph Algorithms, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.206-215, April 20-24, 1998
	4	R. Anderson. On the forward security of digital signatures. Technical report, 1997.
	5	Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
	6	Dan Boneh , Xuhua Ding , Gene Tsudik , Chi Ming Wong, A method for fast revocation of public key certificates and security capabilities, Proceedings of the 10th conference on USENIX Security Symposium, p.22-22, August 13-17, 2001, Washington, D.C.
	7	Srdjan Čapkun , Levente Buttyán , Jean-Pierre Hubaux, Small worlds in security systems: an analysis of the PGP certificate graph, Proceedings of the 2002 workshop on New security paradigms, September 23-26, 2002, Virginia Beach, Virginia [doi>10.1145/844102.844108]
	8	L. Costa, F. Rodrigues, G. Travieso, and P. Boas. Characterization of complex networks: A survey of measurements. Advances In Physics, 56:167--242, 2007.
	9	Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Strong Key-Insulated Signature Schemes, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.130-144, January 06-08, 2003
	10	Warwick Ford , Burton S. Kaliski, Jr., Server-Assisted Generation of a Strong Secret from a Password, Proceedings of the 9th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, p.176-180, June 04-16, 2000
	11	R. Ganesan, Yaksha: augmenting Kerberos with public key cryptography, Proceedings of the 1995 Symposium on Network and Distributed System Security (SNDSS'95), p.132, February 16-17, 1995
	12	R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold dss signatures. In EUROCRYPT'96, pages 354--371, 1996.
	13	Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
	14	Trusted Computing Group. https://www.trustedcomputinggroup.org/.
	15	Keith Harrison , Shouhuai Xu, Protecting Cryptographic Keys from Memory Disclosure Attacks, Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, p.137-143, June 25-28, 2007 [doi>10.1109/DSN.2007.77]
	16	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 [doi>10.1145/266420.266442]
	17	D. Hoover and B. Kausik. Software smart cards via cryptographic camouflage. In IEEE Symposium on Security and Privacy, pages 208--215, 1999.
	18	Gene Itkis , Leonid Reyzin, SiBIR: Signer-Base Intrusion-Resilient Signatures, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.499-514, August 18-22, 2002
	19	Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
	20	Philip MacKenzie , Michael K. Reiter, Networked Cryptographic Devices Resilient to Capture, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.12, May 14-16, 2001
	21	Philip D. MacKenzie , Michael K. Reiter, Two-Party Generation of DSA Signatures, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.137-154, August 19-23, 2001
	22	Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
	23	National Institute of Standards and Technology (NIST). FIPS Publication 186: Digital Signature Standard, May 19, 1994.
	24	M. Newman. The structure and function of complex networks. SIAM Review, 45:167, 2003.
	25	A. Nicolosi, M. Krohn, Y. Dodis, and D. Mazières. Proactive two-party signatures for user authentication. In Proceedings of the Network and Distributed System Security Symposium (NDSS'03), 2003.
	26	Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
	27	R. Perlman and C. Kaufman. Secure password-based protocol for downloading a private key. In Proceedings of the Network and Distributed System Security Symposium (NDSS'99), 1999.
	28	D. Piegdon and L. Pimenidis. Hacking in physically adressable memory. In Proc. 4th International Conference on Detection of Intrusions & Malware, and Vulnerability Assessment (DIMVA'07).
	29	Tal Rabin, A Simplified Approach to Threshold and Proactive RSA, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.89-104, August 23-27, 1998
	30	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	31	S. Ross. Stochastic Processes. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Inc, 1996.
	32	C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161--174, 1991.
	33	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]
	34	Adi Shamir , Nicko van Someren, Playing "Hide and Seek" with Stored Keys, Proceedings of the Third International Conference on Financial Cryptography, p.118-124, February 01, 1999
	35	Shouhuai Xu , Xiaohu Li , Paul Parker, Exploiting social networks for threshold signing: attack-resilience vs. availability, Proceedings of the 2008 ACM symposium on Information, computer and communications security, March 18-20, 2008, Tokyo, Japan [doi>10.1145/1368310.1368358]
	36	S. Xu and R. Sandhu. Two efficient and provably secure schemes for server-assisted threshold signatures. In Proc. CT-RSA 2003, pages 355--372.
	37	B. Yee. Using secure coprocessors. PhD thesis, Carnegie Mellon University, May 1994.
	38	Haifeng Yu , Michael Kaminsky , Phillip B. Gibbons , Abraham Flaxman, SybilGuard: defending against sybil attacks via social networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy