Book contents
- Frontmatter
- Contents
- List of Contributors
- Preface
- Part I Theoretical Foundations
- Part II Secure Communication
- Part III Secret Key Generation and Authentication
- Part IV Data Systems and Related Applications
- 15 Information Theoretic Analysis of the Performance of Biometric Authentication Systems
- 16 Joint Privacy and Security of Multiple Biometric Systems
- 17 Information Theoretic Approaches to Privacy-Preserving Information Access and Dissemination
- 18 Privacy in the Smart Grid: Information, Control, and Games
- 19 Security in Distributed Storage Systems
- Index
- References
19 - Security in Distributed Storage Systems
from Part IV - Data Systems and Related Applications
Published online by Cambridge University Press: 28 June 2017
Book contents
- Frontmatter
- Contents
- List of Contributors
- Preface
- Part I Theoretical Foundations
- Part II Secure Communication
- Part III Secret Key Generation and Authentication
- Part IV Data Systems and Related Applications
- 15 Information Theoretic Analysis of the Performance of Biometric Authentication Systems
- 16 Joint Privacy and Security of Multiple Biometric Systems
- 17 Information Theoretic Approaches to Privacy-Preserving Information Access and Dissemination
- 18 Privacy in the Smart Grid: Information, Control, and Games
- 19 Security in Distributed Storage Systems
- Index
- References
Summary
The proliferation of cloud applications in recent years has made securing the underlying distributed storage systems (DSSs) an important problem. This chapter focuses on the fundamental limits of information theoretic security in DSSs, with an emphasis on constructing efficient codes for achieving these limits. The challenge of studying security in DSSs results from their dynamic behavior characterized by nodes frequently leaving and joining the DSS. This dynamic behavior distinguishes them from static models typically studied in the area of information theoretic security. This chapter introduces the theoretical model of DSSs and summarizes the main results in the area. Three types of adversaries are studied: passive, active omniscient, and active limited-knowledge adversaries. For each type of attack, upper bounds on the secrecy or resiliency capacity are given, as well as capacity-achieving secure codes for certain regimes. Moreover, open problems are highlighted and discussed.
Introduction
Distributed storage systems have witnessed a rapid growth in recent years, driven by the advent of cloud applications. DSSs are used in data centers [1–6] and peer-to-peer (p2p) networks [7–10] to store large amounts of data and make it available online anywhere and anytime. The sheer volume of this data makes DSSs an obvious and lucrative target for malicious attacks, which can range from stealing private information (credit cards, fingerprints, etc.) to corrupting sensitive data [11–17]. This chapter focuses on the fundamental limits of information theoretic security [18–20] in DSSs, with an emphasis on constructing efficient codes for achieving these limits.
DSSs are typically formed of inexpensive and unreliable storage nodes that fail frequently, due to hardware failures [21], software failures and updates [22], and peer churning in p2p DSSs [7,9], causing temporary or even permanent data loss. Failures in DSSs are described by practitioners as being “the norm rather than the exception” [1]. To guarantee data reliability, the data is stored redundantly in DSSs. Moreover, when a node fails, or leaves the DSS, it is replaced by another node called a newcomer or replacement node, in what is referred to as the repair process [23]. This dynamic behavior of DSSs, in which nodes are frequently leaving and joining the system, distinguishes them from other communication systems in the literature on information theoretic security [24–27], which are static in general.
- Type
- Chapter
- Information
- Publisher: Cambridge University PressPrint publication year: 2017
References
[1] , , and , “The Google file system,” in Proc. 19th ACM Symp. Operating Systems Principles, Bolton Landing, NY, USA, Oct. 2003, pp. 29–43.
[2] , , , , , , , , and , “Dynamo: Amazon's highly available key–value store,” in Proc. 21st ACM Special Interest Group on Operating System, Stevenson, WA, USA, Oct. 2007, pp. 205–220.
[3] , Efficient and Reliable Storage Solutions.Redmond, WA: Microsoft Corporation, 2013.
[4] and , “Cassandra: A decentralized structured storage system,” SIGOPS Oper. Syst. Rev., vol. 44, no. 2, pp. 35–40, Apr. 2010.Google Scholar
[5] , , , , and , “Finding a needle in haystack: Facebook's photo storage,” in Proc. 9th USENIX Conf. Networked Systems Design Implementation, Vancouver, BC, Canada, Oct. 2010, pp. 47–60.
[6] , , , , , , , , , and , “Windows Azure storage: A highly available cloud storage service with strong consistency,” in Proc. 23rd ACM Symp. Operating Systems Principles, Cascais, Portugal, Oct. 2011, pp. 143–157.
[7] , , , , , , , , , , , and , “Oceanstore: An architecture for global-scale persistent storage,” in Proc. 9th Int. Conf. Architectural Support for Programming Languages and Operating Systems, Cambridge,MA, USA, Nov. 2000, pp. 190–201.
[8] , , , , , and , “Pond: The Oceanstore prototype,” in Proc. 2nd USENIX Conf. File Storage Technologies, San Francisco, CA, USA, Mar. 2003, pp. 1–14.
[9] , , , , and , “Total recall: System support for automated availability management,” in Proc. 1st USENIX Conf. Networked Systems Design Implementation, San Francisco, CA, USA, Mar. 2004, p. 25.
[10] , “P2P startup Space Monkey raises 2.25m led by Google Ventures and Venture51,” Jul. 2012. [Online]. Available: http://techcrunch.com/2012/07/11/spacemonkey-seed-round/
[11] , “The top 5 most brutal cyber attacks of 2014 so far,” Jul. 2014. [Online]. Available: www.forbes.com/sites/jaymcgregor/2014/07/28/the-top-5-mostbrutal-cyber-attacks-of-2014-so-far/
[12] , “Home depot admits 56 million payment cards at risk after cyber attack,” Sep. 2014. [Online]. Available: www.huffingtonpost.com/2014/09/18/home-depot-hackn-5845378.html
[13] , , and , “Was government hack our final warning?” Oct. 2014. [Online]. Available: http://dealbook.nytimes.com/2014/10/02/jpmorgan-discovers-further-cyber-security-issues/
[14] , “Hacking of government computers exposed 21.5 million people,” Jul. 2015. [Online]. Available: www.nytimes.com/2015/07/10/us/office-of-personnel-managementhackers-got-data-of-millions.html
[15] , “An expensive hack attack: Target's 148 million dollars breach,” Aug. 2014. [Online]. Available: http://blogs.wsj.com/corporate-intelligence/2014/08/05/anexpensive-hack-attack-targets-148-million-breach/
[16] , “Sony estimates 171 million dollars loss from PSN hack,” May 2011. [Online]. Available: www.wired.com/2011/05/sony-psn-hack-losses/
[17] Ponemon Institute LLC, “2014 cost of data breach study: United States,” May 2014.
[18] , , and (Shitz), “Information theoretic security,” Found. Trends Commun. Inf. Theory, vol. 5, no. 4–5, pp. 355–580, 2009.Google Scholar
[19] and , Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd edn. Cambridge: Cambridge University Press, 2011.
[20] and , Network Information Theory. Cambridge: Cambridge University Press, 2011.
[21] and , “Disk failure in the real world: What does an MTTF of 1,000,000 hours mean to you?” in Proc. 5th USENIX Conf. File Storage Technologies, San Jose, CA, USA, Feb. 2007, pp. 1–16.
[22] , , , , , , , and , “Erasure coding in Windows Azure storage,” in Proc. USENIX Annual Technical Conf., Boston, MA, USA, Jun. 2012, p. 2.
[23] , , , , and , “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539–4551, Sep. 2010.Google Scholar
[25] and , “Wire-tap channel II,” AT& T Bell Lab. Tech. J., vol. 63, no. 10, pp. 2135–2157, Dec. 1984.Google Scholar
[26] and , “Secure network coding on a wiretap network,” IEEE Trans. Inf. Theory, vol. 57, no. 1, pp. 424–435, Jan. 2011.Google Scholar
[27] , , and , “Secure network coding for wiretap networks of type II,” IEEE Trans. Inf. Theory, vol. 58, no. 3, pp. 1361–1371, Mar. 2012.Google Scholar
[28] , , and , Handbook of Applied Cryptography. London: CRC Press, 1996.
[29] and , Introduction to Modern Cryptography. London: CRC Press, 2014.
[30] , , , and , “POTSHARDS: Secure long-term storage without encryption,” in Proc. USENIX Annual Technical Conf., Santa Clara, CA, USA, Jun. 2007, pp. 11:1–11:14.
[31] and , “AONT-RS blending security and performance in dispersed storage systems,” in Proc. 9th USENIX Conf. File Storage Technol., San Jose, CA, USA, Feb. 2011, p. 14.
[32] www.cleversafe.com/.
[33] , , , and , “A survey on network codes for distributed storage,” Proc. IEEE, vol. 99, no. 3, pp. 476–489, Mar. 2011.Google Scholar
[34] , , and , “Repair optimal erasure codes through Hadamard designs,” in Proc. 49th Annual Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, Sep. 2011, pp. 1382–1389.
[35] and , “High-rate regenerating codes through layering,” in Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 1611–1615.
[36] , , , , , , and , “XORing elephants: Novel erasure codes for big data,” in Proc. VLDB Endowment, vol. 6, no. 5, Mar. 2013, pp. 325–336.Google Scholar
[37] , , , and , “Explicit codes minimizing repair bandwidth for distributed storage,” in Proc. IEEE Inf. Theory Workshop, Cairo, Egypt, Jan. 2010, pp. 1–5.
[38] , , and , “Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, Aug. 2011.Google Scholar
[39] , , and , “On codes for optimal rebuilding access,” in Proc. 49th Annual Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, Sep. 2011, pp. 1374–1381.
[40] , , and , “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616, Mar. 2013.Google Scholar
[41] and , “A family of optimal locally recoverable codes,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4661–4676, Aug. 2014.Google Scholar
[42] and , “Fractional repetition codes for repair in distributed storage systems,” in Proc. 48th Annual Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, Sep. 2010, pp. 1510–1517.
[43] , , , and , “DRESS codes for the storage cloud: Simple randomized constructions,” in Proc. IEEE Int. Symp. Inf. Theory, St. Petersburg, Russia, Jul. 2011, pp. 2338–2342.
[44] , , , and , “On the locality of codeword symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934, Nov. 2012.Google Scholar
[45] , , , and , “Distributed storage codes with repair-by-transfer and nonachievability of interior points on the storage–bandwidth tradeoff,” IEEE Trans. Inf. Theory, vol. 58, no. 3, Mar. 2012, pp. 1837–1852.
[46] , , and , “Searching for minimum storage regenerating codes,” Oct. 2009. [Online]. Available: http://arxiv.org/abs/0910.2245
[47] , “A construction of systematic MDS codes with minimum repair bandwidth,” IEEE Trans. Inf. Theory, vol. 57, no. 6, pp. 3738–3741, Jun. 2011.Google Scholar
[48] , , , , and , “Asymptotic interference alignment for optimal repair of MDS codes in distributed storage,” IEEE Trans. Inf. Theory, vol. 59, pp. 2974–2987, May 2013.Google Scholar
[49] , , , and , “Polynomial length MDS codes with optimal repair in distributed storage,” in Proc. 45th Asilomar Conf. Signals, Systems, Computers, Pacific Grove, CA, USA, Nov. 2011, pp. 1850–1854.
[50] , , and , “Progress on high-rate MSR codes: Enabling arbitrary number of helper nodes,” Jan. 2016. [Online]. Available: http://arxiv.org/abs/1601.06362
[51] , , and , “Minimum storage regenerating codes for all parameters,” Feb. 2016. [Online]. Available: http://arxiv.org/abs/1602.04496
[52] , , , and , “Explicit construction of optimal exact regenerating codes for distributed storage,” in Proc. 47th Annual Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, Sep. 2009, pp. 1243–1249.
[53] , “Erasure codes for optimal node repairs in distributed storage systems,” Ph.D. dissertation, Princeton University, 2014.
[54] , , and , “An improved sub-packetization bound for minimum storage regenerating codes,” IEEE Trans. Inf. Theory, vol. 60, no. 5, pp. 2770–2779, May 2014.Google Scholar
[55] , , , and , “Interference alignment in regenerating codes for distributed storage: Necessity and code constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2134–2158, Apr. 2012.Google Scholar
[56] , , , and , “Optimal repair of MDS codes in distributed storage via subspace interference alignment,” Jun. 2011. [Online]. Available: http://arxiv.org/abs/1106.1250
[57] , , and , “On secure distributed data storage under repair dynamics,” in Proc. IEEE Int. Symp. Inf. Theory, Austin, TX, USA, Jun. 2010, pp. 2543–2547.
[58] , , and , “Securing dynamic distributed storage systems against eavesdropping and adversarial attacks,” IEEE Trans. Inf. Theory, vol. 58, no. 3, pp. 6734–6753, Mar. 2012.Google Scholar
[59] , , and , “Securing dynamic distributed storage systems from malicious nodes,” in Proc. IEEE Int. Symp. Inf. Theory, St. Petersburg, Russia, Jul. 2011, pp. 1452–1456.
[60] , , and , “Information-theoretically secure regenerating codes for distributed storage,” in Proc. IEEE Global Commun. Conf., Houston, TX, USA, Dec. 2011, pp. 1–5.
[61] , , and , “Secure network coding for distributed secret sharing with low communication cost,” in Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 2404–2408.
[62] , , , and , “Regenerating codes for errors and erasures in distributed storage,” in Proc. IEEE Int. Symp. Inf. Theory, Cambridge, MA, USA, Jul. 2012, pp. 1202–1206.
[63] , , , and , “Data secrecy in distributed storage systems under exact repair,” in Proc. IEEE Int. Symp. Network Coding, Calgary, Canada, Jun. 2013, pp. 1–6.
[64] , , , and , “Towards optimal secure distributed storage systems with exact repair,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3477–3492, Jun. 2016.Google Scholar
[65] , “Polytope codes for distributed storage in the presence of an active omniscient adversary,” in Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 897–901.
[66] , , and , “Error resilience in distributed storage via rank-metric codes,” in Proc. 50th Annual Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, Sep. 2012, pp. 1150–1157.
[67] , , N. Silberstein, and , “Optimal locally repairable and secure codes for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 60, no. 1, pp. 212–236, Jan. 2014.Google Scholar
[68] and , “Security in locally repairable storage,” in Proc. IEEE Inf. Theory Workshop, Jerusalem, Israel, May 2015, pp. 1–5.
[69] , , , and , “Network coding theory part I: Single sources / part II: Multiple sources,” Found. Trends Commun. Inf. Theory, vol. 2, no. 4–5, pp. 241–381, 2005.
[70] and , “Network error correction, I: Basic concepts and upper bounds,” Commun. Inf. Systems, vol. 6, no. 1, pp. 19–35, 2006.Google Scholar
[71] and , “Network error correction, II: Lower bounds,” Commun. Inf. & Systems, vol. 6, no. 1, pp. 37–54, 2006.Google Scholar
[72] and , “Secure network coding,” in Proc. IEEE Int. Symp. Inf. Theory, Lausanne, Switzerland, Jun. 2002, p. 323.
[73] , , , , , , and , “Resilient network coding in the presence of byzantine adversaries,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2596–2603, Jun. 2008.Google Scholar
[74] , , and , “A rank-metric approach to error control in random network coding,” IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 3951–3967, Sep. 2008.Google Scholar
[75] and , “Coding for errors and erasures in random network coding,” IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3579–3591, Aug. 2008.Google Scholar
[76] and , “Network coding fundamentals,” Found. Trends Network., vol. 2, no. 1, pp. 1–133, 2007.Google Scholar
[77] and , Network Coding: An Introduction. Cambridge: Cambridge University Press, 2008.
[78] , , and , “On secure network coding with nonuniform or restricted wiretap sets,” IEEE Trans. Inf. Theory, vol. 59, no. 1, pp. 166–176, Jan. 2013.Google Scholar
[79] , , and , “Nonlinear network coding is necessary to combat general byzantine attacks,” in Proc. 47th Annual Allerton Conf. Commun., Control, Computing, Monticello, IL, USA, Oct. 2009, pp. 593–599.
[80] , , and , “Polytope codes against adversaries in networks,” IEEE Trans. Inf. Theory, vol. 60, no. 6, pp. 3308–3344, Jun. 2014.Google Scholar
[81] , , C. Hollanti, and , “Capacity and security of heterogeneous distributed storage systems,” IEEE J. Sel. Areas Commun., vol. 31, no. 12, pp. 2701–2709, Dec. 2013.Google Scholar
[82] , , , and , “Non-homogeneous two-rack model for distributed storage systems,” in Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 1237–1241.
[83] , , and , “Tradeoff between storage cost and repair cost in heterogeneous distributed storage systems,” Trans. Emerging Telecommun. Technol., vol. 26, no. 10, pp. 1201–1211, Oct. 2015.Google Scholar
[84] and , “Cooperative regenerating codes,” IEEE Trans. Inf. Theory, vol. 59, no. 11, pp. 7229–7258, Nov. 2013.Google Scholar
[85] , , and , “Secure cooperative regenerating codes for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5228–5244, Sep. 2014.Google Scholar
[86] , , , , , , and , “A random linear network coding approach to multicast,” IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4413–4430, Oct. 2006.Google Scholar
[87] , , and , “New codes and inner bounds for exact repair in distributed storage systems,” Feb. 2014. [Online]. Available: http://arxiv.org/abs/1402.2343
[88] , “Rate region of the (4, 3,3) exact-repair regenerating codes,” in Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 1426–1430.
[89] , , and , “An improved outer bound on the storage-repair-bandwidth tradeoff of exact-repair regenerating codes,” in Proc. IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jul. 2014, pp. 2430–2434.
[90] , , and , “Exact-repair regenerating codes via layered erasure correction and block designs,” in Proc. IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 1431–1435.
[91] , , and , “Linear exact repair rate region of (k + 1, k, k) distributed storage systems: A new approach,” in Proc. IEEE Int. Symp. Inf. Theory, Hong Kong, Jun. 2015, pp. 2061–2065.
[92] and , “New bounds on the (n, k, d) storage systems with exact repair,” in Proc. IEEE Int. Symp. Inf. Theory, Hong Kong, Jun. 2015, pp. 2056–2060.
[93] , “Codes between MBR and MSR points with exact repair property,” IEEE Trans. Inf. Theory, vol. 60, no. 11, pp. 6993–7005, Nov. 2014.Google Scholar
[94] , , and , “Security in distributed storage systems by communicating a logarithmic number of bits,” in Proc. IEEE Int. Symp. Inf. Theory, Austin, TX, USA, Jun. 2010, pp. 1948–1952.
[95] and , “On algebraic manipulation detection codes from linear codes and their application to storage systems,” in Proc. IEEE Inf. Theory Workshop, Jeju, Korea, Oct. 2015, pp. 64–68.
[96] , , and , “On block security of regenerating codes at the MBR point for distributed storage systems,” in Proc. IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jun. 2014, pp. 1967–1971.
[97] and , “Weakly secure regenerating codes for distributed storage,” in Proc. IEEE Int. Symp. Network Coding, Aalborg, Denmark, Jun. 2014, pp. 1–6.
[98] , , and , “Access vs. bandwidth in codes for storage,” in Proc. IEEE Int. Symp. Inf. Theory, Cambridge, MA, USA, Jul. 2012, pp. 1187–1191.
[99] , “Theory of codes with maximum rank distance,” Probl. Peredachi Inf., vol. 21, no. 1, pp. 3–16, 1985.Google Scholar
[100] , , and , “Can linear minimum storage regenerating codes be universally secure?” in Proc. 49th Asilomar Conf. Signals, Systems, Computers, Pacific Grove, CA, USA, Nov. 2015, pp. 549–553.
[101] and , The Theory of Error Correcting Codes. New York: Elsevier, 1977, vol. 16.
[102] and , “Securing data against limited-knowledge adversaries in distributed storage systems,” in Proc. IEEE Int. Symp. Inf. Theory, Hong Kong, Jun. 2015, pp. 2847–2851.
- 2
- Cited by