doi: 10.3934/amc.2022005
Online First

Online First 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). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” 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

Received  December 2019 Revised  October 2021 Early access February 2022

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.

Citation: Negin Karimi, Ahmad Yousefian Darani, Marcus Greferath. Correcting adversarial errors with generalized regenerating codes. Advances in Mathematics of Communications, doi: 10.3934/amc.2022005
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. DimakisP. GodfreyY. WuM. 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. DimakisV. 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. PawarS. 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. RashmiN. B. ShahP. 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. XuY. 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.

show all references

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. DimakisP. GodfreyY. WuM. 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. DimakisV. 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. PawarS. 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. RashmiN. B. ShahP. 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. XuY. 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.

[1]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058

[2]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[3]

José Ignacio Iglesias Curto. Generalized AG convolutional codes. Advances in Mathematics of Communications, 2009, 3 (4) : 317-328. doi: 10.3934/amc.2009.3.317

[4]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042

[5]

Fahd Jarad, Thabet Abdeljawad. Generalized fractional derivatives and Laplace transform. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 709-722. doi: 10.3934/dcdss.2020039

[6]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018

[7]

Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057

[8]

Kamil Otal, Ferruh Özbudak, Wolfgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042

[9]

Tatiana Odzijewicz. Generalized fractional isoperimetric problem of several variables. Discrete and Continuous Dynamical Systems - B, 2014, 19 (8) : 2617-2629. doi: 10.3934/dcdsb.2014.19.2617

[10]

Fahd Jarad, Thabet Abdeljawad. Variational principles in the frame of certain generalized fractional derivatives. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 695-708. doi: 10.3934/dcdss.2020038

[11]

Tarek Saanouni. Energy scattering for the focusing fractional generalized Hartree equation. Communications on Pure and Applied Analysis, 2021, 20 (10) : 3637-3654. doi: 10.3934/cpaa.2021124

[12]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002

[13]

Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006

[14]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[15]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[16]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[17]

Nupur Patanker, Sanjay Kumar Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021013

[18]

Hayden Schaeffer. Active arcs and contours. Inverse Problems and Imaging, 2014, 8 (3) : 845-863. doi: 10.3934/ipi.2014.8.845

[19]

Mauro Maggioni, James M. Murphy. Learning by active nonlinear diffusion. Foundations of Data Science, 2019, 1 (3) : 271-291. doi: 10.3934/fods.2019012

[20]

Mostafa El Haffari, Ahmed Roubi. Prox-dual regularization algorithm for generalized fractional programs. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1991-2013. doi: 10.3934/jimo.2017028

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (207)
  • HTML views (98)
  • Cited by (0)

[Back to Top]