An Efficient Ramp Secret Sharing Scheme Based on Zigzag-Decodable Codes

Document Type : Special Issue

Authors

• saeideh Kabirirad ¹
• Sorour Sheidani ²
• Ziba Eslami ²

¹ Computer Science Department, Birjand University of Technology, Birjand, Iran

² Department of Data and Computer Sciences, Shahid Beheshti University, G.C., Tehran, Iran

10.22067/cke.2023.83418.1094

Abstract

Secret sharing schemes are ideally suited to save highly sensitive information in distributed systems. On the other hand, Zigzag-Decodable (ZD) codes are employed in wireless distributed platforms for encoding data using only bit-wise shift and XOR operations. Recently, Vandermonde-based ZD codes have been utilized in secret sharing schemes to achieve high computational efficiency such that sharing and recovering of secrets can be realized by lightweight operations. However, the storage overhead of using these ZD codes remains a problem which is addressed in the present paper. Here, a ramp secret sharing scheme is proposed based on an efficient ZD code with less storage overhead in comparison with existing literature. The novelty of the proposed scheme lies in the careful selection of the number of positions to shift the bits of the secret such that security and zigzag decodability are guaranteed simultaneously. In addition to prove gaining these features, we show that the scheme improves speed of recovery.

Keywords

• Boolean operation
• Efficiency
• Ramp secret sharing scheme
• Zigzag decodable codes

Main Subjects

• Computer Security and Cryptography

---

References

[1]   Shamir, A., "How to share a secret", Commun. ACM, Vol. 22, No. 11, pp. 612–613, 1979.

[2]   Hineman, A., and Mario, B., "A modified Shamir secret sharing scheme with efficient encoding", IEEE Communications Letters, Vol. 26.4, pp. 758-762, 2022.‏

[3]   Shiina, N., "How to convert 1-out-of-n proof into k-out-of-n proof", Proc SCIS2004, pp. 1435–1440, 2004.

[4]   Kurihara, J., Kiyomoto, S., Fukushima, K., and Tanaka, T., "A fast (3, n)-threshold secret sharing scheme using exclusive-or operations", IEICE Trans. Fundam. Electron. Commun. Comput. Sci., Vol. 91, No. 1, pp. 127–138, 2008.

[5]   Kurihara, J., Kiyomoto, S., Fukushima, K., and Tanaka, T., "A new (k, n)-threshold secret sharing scheme and its extension", in International Conference on Information Security, pp. 455–470, Springer, 2008.

[6]   Kurihara, J., Kiyomoto, S., Fukushima, K., and Tanaka, T., "A fast (k, L, n)-threshold ramp secret sharing scheme", IEICE Trans. Fundam. Electron. Commun. Comput. Sci., Vol. 92, No. 8, pp. 1808–1821, 2009.

[7]   Beimel, A., and Othman, H., "Evolving ramp secret sharing with a small gap", EUROCRYPT 2020, 2020.

[8]   Shima, K., and Doi, H., "New Proof Techniques Using the Properties of Circulant Matrices for XOR-based (k, n) Threshold Secret Sharing Schemes", J. Inf. Process., Vol. 29, pp. 266–274, 2021.

[9]   Wang, Y., and Desmedt, Y., "Efficient secret sharing schemes achieving optimal information rate", in 2014 IEEE Information Theory Workshop (ITW 2014), IEEE, pp. 516–520, 2014.

[10] Chen, L., Laing, T. M., and Martin, K. M., "Efficient, XOR-Based, Ideal (t, n)- threshold Schemes", in International Conference on Cryptology and Network Security, pp. 467–483, Springer, 2016.

[11] Shima, K., and Doi, H., "A hierarchical secret sharing scheme over finite fields of characteristic 2", J. Inf. Process., Vol. 25, pp. 875–883, 2017.

[12] Deshmukh, M., Maroti, Neeta, N., and Mushtaq, A., "Secret sharing scheme based on binary trees and Boolean operation", Knowledge and Information Systems, Vol. 60, No. 3, pp. 1377-1396, 2019.‏

[13] Pande, D., Rawat, A. S., Deshmukh, M., and Singh, M., "Single secret sharing scheme using chinese remainder theorem, modified Shamir’s scheme and XOR operation", Wireless Personal Communications, Vol. 130, No. 2, pp. 957-985, 2023.‏

[14] Kabirirad, S., and Eslami, Z., "Improvement of (n, n)-multi-secret image sharing schemes based on Boolean operations", J. Inf. Secur. Appl., Vol. 47, pp. 16–27, 2019.

[15] Bisht, K., and Deshmukh, M., "A novel approach for multilevel multi-secret image sharing scheme", J. Supercomput., pp. 1–35, 2021.

[16] Paul, A., Kandar, S., and Dhara, B. C., "Boolean operation based lossless threshold secret image sharing", Multimedia Tools and Applications, Vol. 81 No. 24, pp. 35293-35316, 2022.‏

[17] Huang, P.-C., Chang, C.-C., Li, Y.-H., and Liu, Y., "Enhanced (n, n)-threshold QR code secret sharing scheme based on error correction mechanism", J. Inf. Secur. Appl., Vol. 58, pp. 102719, 2021.

[18] Kabirirad, S., and Eslami, Z., "A (t, n)-multi secret image sharing scheme based on Boolean operations", J. Vis. Commun. Image Represent., Vol. 57, pp. 39–47, 2018.

[19] Nag, A., Singh, J. P., and Singh, A. K., "An efficient Boolean based multi-secret image sharing scheme", Multimed. Tools Appl., pp. 1–25, 2019.

[20] Chattopadhyay, A. K., Nag, A., Singh, J.P., and Singh, A. K., "A verifiable multi-secret image sharing scheme using XOR operation and hash function", Multimedia Tools and Applications, Vol 80, pp. 35051-35080, 2021.‏

[21] Sung, C. W., and Gong, X., "A ZigZag-decodable code with the MDS property for distributed storage systems", in 2013 IEEE International Symposium on Information Theory, IEEE, pp. 341–345, 2013.

[22] Dai, M., Sung, C. W., Wang, H., Gong, X., and Lu, Z., "A new zigzag-decodable code with efficient repair in wireless distributed storage", IEEE Trans. Mob. Comput., Vol. 16, No. 5, pp. 1218–1230, 2016.

[23] Hou, H., Lee, P. P., and Han, Y. S., "ZigZag-decodable reconstruction codes with asymptotically optimal repair for all nodes", IEEE Trans. Commun., Vol. 68, No. 10, pp. 5999–6011, 2020.

[24] Lu, S., Zhang, C., and Dai, M., "CP-BZD Repair Codes Design for Distributed Edge Computing", in 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS), IEEE, pp. 722–727, 2020.

[25] Gong, X., Hu, P., Shum, K. W., and Sung, C. W., "A zigzag-decodable ramp secret sharing scheme", IEEE Trans. Inf. Forensics Secur., Vol. 13, No. 8, pp. 1906–1916, 2018.

[26] Gong, X., and Sung, C. W., "Zigzag decodable codes: Linear-time erasure codes with applications to data storage", J. Comput. Syst. Sci., Vol. 89, pp. 190–208, 2017.

[27] Iwamoto, M., and Yamamoto, H., "Strongly secure ramp secret sharing schemes for general access structures", Inf. Process. Lett., Vol. 97, No. 2, pp. 52–57, 2006.

[28] Gollakota, S., and Katabi, D., "Zigzag decoding: Combating hidden terminals in wireless networks", in Proceedings of the ACM SIGCOMM 2008 conference on Data communication, pp. 159–170, 2008.

[29] Trappe, W., "Introduction to cryptography with coding theory", Pearson Education India, 2006.

[30] Hoffman, K., and Kunze, R., "Linear Algebra, Prentice-Hall", Inc Englewood Cliffs N. J., pp. 122–125, 1971.