A New Shift-Add Secret Sharing Scheme for Partial Data Protection With Parallel Zigzag Decoding
Pages 10221 - 10232
Abstract
This paper studies distributed storage for protecting the confidentiality of partial data in the presence of storage node failures. It is required that not only the original data can be reconstructed from the remaining surviving nodes, but also the data lost by a failed node can be repaired from as few nodes as possible. The minimum number of surviving nodes required to repair a failed node is called the repair degree. Inspired by the zigzag-decodable secret sharing scheme, we propose a new shift-add secret sharing scheme based on the XOR and bitwise-shift operations, in which confidential data is protected by using random keys generated from non-confidential data. The reliability and repairability of the proposed scheme are measured by the message loss probability and the maximum repair degree among all nodes, respectively, and then compared with three benchmark schemes. In contrast to conventional zigzag-decodable codes, the special structure of our proposed scheme allows the design of fast parallel algorithms for modern devices with multi-core processors, which have a linear speedup in decoding time compared with various versions of serial zigzag decoding. Experiments are implemented on a multi-core computer, and the empirical results on decoding time are consistent with our theoretical observations.
References
[1]
S. Ghemawat, H. Gobioff, and S.-T. Leung, “The Google file system,” in Proc. 19th ACM Symp. Operating Syst. Princ., Oct. 2003, pp. 20–43.
[2]
S. B. Balaji, M. N. Krishnan, M. Vajha, V. Ramkumar, B. Sasidharan, and P. V. Kumar, “Erasure coding for distributed storage: An overview,” Sci. China Inf. Sci., vol. 61, no. 10, pp. 1–45, Oct. 2018.
[3]
A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, Nov. 1979.
[4]
G. R. Blakley, “Safeguarding cryptographic keys,” in Proc. Manag. Requirements Knowl., Int. Workshop, 1979, pp. 313–318.
[5]
C. Asmuth and J. Bloom, “A modular approach to key safeguarding,” IEEE Trans. Inf. Theory, vol. IT-29, no. 2, pp. 208–210, Mar. 1983.
[6]
M. Ito, A. Saito, and T. Nishizeki, “Multiple assignment scheme for sharing secret,” J. Cryptol., vol. 6, no. 1, pp. 15–20, Mar. 1993.
[7]
T. Liu and V. Vaikuntanathan, “Breaking the circuit-size barrier in secret sharing,” in Proc. 50th Annu. ACM SIGACT Symp. Theory Comput., Jun. 2018, pp. 699–708.
[8]
B. Applebaum, A. Beimel, O. Farràs, O. Nir, and N. Peter, “Secret-sharing schemes for general and uniform access structures,” in Advances in Cryptology—EUROCRYPT 2019, Y. Ishai and V. Rijmen, Eds., Cham, Switzerland: Springer, 2019, pp. 441–471.
[9]
N. Shiina, “How to convert 1-out-of-n proof into k-out-of-n proof,” in Proc. SCIS, 2004, pp. 1435–1440.
[10]
J. Kurihara, S. Kiyomoto, K. Fukushima, and T. Tanaka, “On a fast (k, n)-threshold secret sharing scheme,” IEICE Trans. Fundam. Electron., Commun. Comput. Sci., vol. E91-A, no. 9, pp. 2365–2378, 2008.
[11]
J. Kurihara, S. Kiyomoto, K. Fukushima, and T. Tanaka, “A fast (k, L, n)-threshold ramp secret sharing scheme,” IEICE Trans. Fundam. Electron., Commun. Comput. Sci., vol. E92-A, no. 8, pp. 1808–1821, 2009.
[12]
C. Lv, X. Jia, L. Tian, J. Jing, and M. Sun, “Efficient ideal threshold secret sharing schemes based on EXCLUSIVE-OR operations,” in Proc. 4th Int. Conf. Netw. Syst. Secur., Sep. 2010, pp. 136–143.
[13]
X. Gong, P. Hu, K. W. Shum, and C. W. Sung, “A zigzag-decodable ramp secret sharing scheme,” IEEE Trans. Inf. Forensics Security, vol. 13, no. 8, pp. 1906–1916, Aug. 2018.
[14]
S. Gollakota and D. Katabi, “Zigzag decoding: Combating hidden terminals in wireless networks,” in Proc. ACM SIGCOMM, Aug. 2008, pp. 159–170.
[15]
C. W. Sung and X. Gong, “A ZigZag-decodable code with the MDS property for distributed storage systems,” in Proc. IEEE ISIT, Jul. 2013, pp. 341–345.
[16]
X. Gong and C. W. Sung, “Zigzag decodable codes: Linear-time erasure codes with applications to data storage,” J. Comput. Syst. Sci., vol. 89, pp. 190–208, Nov. 2017.
[17]
M. Dai, C. W. Sung, H. Wang, X. Gong, and Z. Lu, “A new zigzag-decodable code with efficient repair in wireless distributed storage,” IEEE Trans. Mobile Comput., vol. 16, no. 5, pp. 1218–1230, May 2017.
[18]
T. Nozaki, “Fountain codes based on zigzag decodable coding,” in Proc. Int. Symp. Inf. Theory Appl., Oct. 2014, pp. 274–278.
[19]
C. W. Sung and X. Gong, “Combination network coding: Alphabet size and zigzag decoding,” in Proc. Int. Symp. Inf. Theory Appl., Oct. 2014, pp. 699–703.
[20]
M. Dai, X. Wang, H. Wang, X. Lin, and B. Chen, “Bandwidth overhead-free data reconstruction scheme for distributed storage code with low decoding complexity,” IEEE Access, vol. 5, pp. 6824–6832, 2017.
[21]
B. Jun, P. Yang, J.-S. No, and H. Park, “New fountain codes with improved intermediate recovery based on batched zigzag coding,” IEEE Trans. Commun., vol. 65, no. 1, pp. 23–36, Jan. 2017.
[22]
Y. Murayama and T. Nozaki, “Efficient scheduling of serial iterative decoding for zigzag decodable fountain codes,” in Proc. Int. Symp. Inf. Theory Appl. (ISITA), Oct. 2018, pp. 286–290.
[23]
M. Dai, B. Mao, X. Gong, C. W. Sung, W. Zhuang, and X. Lin, “Zigzag-division multiple access for wireless networks with long and heterogeneous delays,” IEEE Trans. Aerosp. Electron. Syst., vol. 55, no. 6, pp. 2822–2835, Dec. 2019.
[24]
H. Hou, P. P. C. Lee, and Y. S. Han, “Zigzag-decodable reconstruction codes with asymptotically optimal repair for all nodes,” IEEE Trans. Commun., vol. 68, no. 10, pp. 5999–6011, Oct. 2020.
[25]
X. Fu, S. Yang, and Z. Xiao, “Decoding and repair schemes for shift-XOR regenerating codes,” IEEE Trans. Inf. Theory, vol. 66, no. 12, pp. 7371–7386, Dec. 2020.
[26]
P. Shi, Z. Wang, D. Li, and W. Xiang, “Zigzag decodable online fountain codes with high intermediate symbol recovery rates,” IEEE Trans. Commun., vol. 68, no. 11, pp. 6629–6641, Nov. 2020.
[27]
X. Fu, C. Wu, Y. Guo, and S. Yang, “Two-tone shift-XOR storage codes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, pp. 2996–3001.
[28]
Y. Zhang, X. Fu, X. Wu, S. Yang, and K. W. Shum, “Solving monoshift systems and applications in random coding,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, pp. 1296–1301.
[29]
X. Cheng, X. Fu, Y. Guo, K. W. Shum, and S. Yang, “Successively solvable shift-add systems—A graphical characterization,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, pp. 946–951.
[30]
A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539–4551, Sep. 2010.
[31]
N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “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, pp. 1837–1852, Mar. 2012.
[32]
I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616, Mar. 2013.
[33]
Y. Wu, “Existence and construction of capacity-achieving network codes for distributed storage,” IEEE J. Sel. Areas Commun., vol. 28, no. 2, pp. 277–288, Feb. 2010.
[34]
H. Hou, K. W. Shum, M. Chen, and H. Li, “BASIC codes: Low-complexity regenerating codes for distributed storage systems,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3053–3069, Jun. 2016.
[35]
P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934, Nov. 2012.
[36]
D. S. Papailiopoulos and A. G. Dimakis, “Locally repairable codes,” IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 5843–5855, Oct. 2014.
[37]
Q. Yu, C. W. Sung, and T. H. Chan, “Irregular fractional repetition code optimization for heterogeneous cloud storage,” IEEE J. Sel. Areas Commun., vol. 32, no. 5, pp. 1048–1060, May 2014.
[38]
K. Asanovic et al., “A view of the parallel computing landscape,” Commun. ACM, vol. 52, no. 10, pp. 56–67, Oct. 2009. 10.1145/1562764.1562783.
[39]
I. S. Gradshteyn, I. M. Ryzhik, A. Jeffrey, and D. Zwillinger, Table of Integrals, Series, and Products, 6th ed., New York, NY, USA: Academic, 2000.
[40]
R. Trobec, B. Slivnik, P. Bulic, and B. Robic, Introduction To Parallel Computing: From Algorithms To Programming on State-of-the-Art Platforms. Cham, Switzerland: Springer, 2018.
[41]
C. Taylor. Longhair: O(N²) Cauchy Reed–Solomon Block Erasure Code for Small Data. Accessed: Apr. 2024. [Online]. Available: https://github.com/catid/longhair
[42]
M. Cornu and P. de Lara. Intel Intelligent Storage Acceleration Library. Accessed: Jun. 2024. [Online]. Available: https://github.com/intel/isa-l
[43]
R. Robey and Y. Zamora, Parallel and High Performance Computing. Shelter Island, NY, USA: Manning, 2021.
Index Terms
- A New Shift-Add Secret Sharing Scheme for Partial Data Protection With Parallel Zigzag Decoding
Index terms have been assigned to the content through auto-classification.
Recommendations
On a Fast (k,n)-Threshold Secret Sharing Scheme
In Shamir's ( k, n )-threshold secret sharing scheme (threshold scheme) [1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. ...
A New (k,n)-Threshold Secret Sharing Scheme and Its Extension
ISC '08: Proceedings of the 11th international conference on Information SecurityIn Shamir's (<em>k</em>,<em>n</em>)-threshold secret sharing scheme (threshold scheme), a heavy computational cost is required to make <em>n</em>shares and recover the secret. As a solution to this problem, several fast threshold schemes have been ...
Strong (n,t,n) verifiable secret sharing scheme
A (t,n) secret sharing divides a secret into n shares in such a way that any t or more than t shares can reconstruct the secret; but fewer than t shares cannot reconstruct the secret. In this paper, we extend the idea of a (t,n) secret sharing scheme ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1556-6021 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 January 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025