Correcting adversarial errors with generalized regenerating codes

Negin Karimi; Ahmad Yousefian Darani; Marcus Greferath

doi:10.3934/amc.2022005

Article Contents

2022. Doi: 10.3934/amc.2022005

Previous Article Next Article

Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Correcting adversarial errors with generalized regenerating codes

1.
University of Mohaghegh Ardabili, 5619911367, Ardabil, Iran
2.
Aalto University, 11000 Espoo, Finland
3.
University College Dublin, Dublin, Republic of Ireland

^*Corresponding author: Ahmad Youosefian Darani
^*Corresponding author: Ahmad Youosefian Darani

Received: November 30, 2019

Revised: September 30, 2021

Early access: February 2022

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

Traditional regenerating codes are efficient tools to optimize both storage and repair bandwidth in storing data across a distributed storage system, particularly in comparison to erasure codes and data replication. In traditional regenerating codes, the collection of any $ k $ nodes can reconstruct all stored information and is called the reconstruction set, $ \aleph _R $. A failed node can be regenerated from any $ d $ surviving nodes. These collections of $ d $ nodes are called the regeneration sets, $ \aleph _H $. The number of reconstruction sets and the number of regeneration sets satisfy $ |\aleph _R| = C_n^k $ and $ |\aleph _H| = C_{n-1}^d $. In generalized regenerating codes, we will have, $ 1\le|\aleph_R|\le C^k_n $ and $ 1\le|\aleph_H|\le C_{n-1}^d $. In this paper, we address the problem of secure generalized regenerating codes and present a coding scheme by focusing on the features of the generalized regenerating codes that protects data in the distributed storage system in presence of an active omniscient adversary. This adversary can maliciously alter the data stored on the nodes under its control and send erroneous outgoing message when contacted for the repair of failed nodes. In our scheme notwithstanding the presence of an adversary in distributed storage system, a data collector can still obtain the original file using a classical minimum distance decoder.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

FullText(HTML)

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. Bhagwan, K. Tati, Y.-C. Cheng, S. Savage and G. M. Voelker, Total recall: System support for automated availability management, Proc. of the Symposium on Networked Systems Design and Implementation, NSDI (2004).
[2]	N. Cai and R. Yeung, Secure network coding on a wiretap network, IEEE Trans. Inform. Theory, 57 (2010), 424-435. doi: 10.1109/TIT.2010.2090197.
[3]	N. Cai and R. W. Yeung, Network error correction, II: Lower bounds, Commun. Inf. Syst., 6 (2006), 37-54. doi: 10.4310/CIS.2006.v6.n1.a3.
[4]	Y. Desmedt, Unconditionally private and reliable communication in an untrusted network, Theory and Practice in Information-Theoretic Security, Information Theory Workshop on., IEEE (2005) 38–41.
[5]	A. Dimakis, P. Godfrey, Y. Wu, M. Wainright and K. Ramchandran, Network coding for distributed storage systems, IEEE Trans. Inform. Theory, 56 (2007), 4539-4551. doi: 10.1109/INFCOM.2007.232.
[6]	A. G. Dimakis, V. Prabhakaran and K. Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE Trans. Inform. Theory, 52 (2006), 2809-2816. doi: 10.1109/TIT.2006.874535.
[7]	T. Dikaliotis, A. G. Dimakis and T. Ho, Security in distributed storage systems by communicating a logarithmic number of bits, International Symposium on Information Theory, IEEE, (2010), 1948–1952. doi: 10.1109/ISIT.2010.5513354.
[8]	S. El Rouayheb and K. Ramchandran, Fractional repetition codes for repair in distributed storage systems, Communication, Control, and Computing (Allerton), 48th Annual Allerton Conference, IEEE, (2010), 1510–1517. doi: 10.1109/ALLERTON.2010.5707092.
[9]	T. Ho, B. Leong, R. Koetter, M. Medard, M. Effros and D. R. Karger, Byzantine modification detection in multicast networks using randomized network coding, International Symposium on Information Theory, ISIT (2004). doi: 10.1109/ISIT.2004.1365180.
[10]	S. Jaggi and M. Langberg, Resilient network codes in the presence of eavesdropping Byzantine adversaries, Information Theory, IEEE (2007), 541-545.
[11]	A. Kshevetskiy and E. Gabidulin, The new construction of rank codes, Proceedings. International Symposium on Information Theory, 2005. doi: 10.1109/ISIT.2005.1523717.
[12]	S. Pawar, S. Rouayheb and K. Ramchandran, Security dynamic distributed storage systems against eavesdropping and adversarial attacks, IEEE Trans. Inform. Theory, 57 (2011), 6734-6753. doi: 10.1109/TIT.2011.2162191.
[13]	K. Rashmi, N. B. Shah, P. V. Kumar and K. Ramchandran, Exact regenerating codes for distributed storage, Arithmetic of Finite Fields, 6087 (2010), 215-223. doi: 10.1007/978-3-642-13797-6_15.
[14]	S. Rouayheb and E. Soljanin, On wiretap networks II, IEEE International Symposium on Information Theory, (ISIT) (2007). doi: 10.1109/ISIT.2007.4557098.
[15]	N. Silberstein, A. S. Rawat and S. Vishwanath, Error resilience in distributed storage via rank-metric codes, 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2012.
[16]	D. Silva and F. R. Kschischang, Security for wiretap network via rank-metrik codes, IEEE Internat. Symp. Inform. Th., ISIT (2004), 616-624.
[17]	J. Xu, Y. Cao and D. Wang, Generalised regenerating codes for securing distributed storage systems against eavesdropping, Journal of Information Security and Applications, 34 (2017), 225-232. doi: 10.1016/j.jisa.2017.02.002.
[18]	H. Yao, D. Silva, S. Jaggi and M. Langberg, Network codes resilient to jamming and eavesdropping, IEEE International Symposium on Network Coding, 2010. doi: 10.1109/NETCOD.2010.5487669.
[19]	R. W. Yeung and N. Cai, Network error correction, I: Basic concepts and upper bounds, Commun. Inf. Syst., 6 (2006), 19-35. doi: 10.4310/CIS.2006.v6.n1.a2.