Abstract
As an essential building block in cryptosystem, linear secret sharing is widely used to safeguard the confidentiality and reliability of outsourced data. Though addition and constant multiplication are extremely easy thanks to the linear operation over shared secrets, how to efficiently multiply multiple shares remains an open problem. In this paper, we devised a non-interactive multiplication scheme based on Shamir’s secret sharing without parameter constrain. It is proved that our scheme is unconditionally secure if no more than k participants are compromised, meaning that both the security and access structure of Shamir’s scheme are immensely retained.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
El-Sayed, H., Sankar, S., Prasad, M., et al.: Edge of things: the big picture on the integration of edge, IoT and the cloud in a distributed computing environment. IEEE Access 6(99), 1706–1717 (2018)
SabatÉ, M., Costa, M.A., Kozuma, K., et al.: Survey on various data integrity attacks in cloud environment and the solutions. In: International Conference on Circuits, Power and Computing Technologies, pp. 1076–1081. IEEE (2013)
Patel, K: Secure multiparty computation using secret sharing. In: International Conference on Signal Processing, Communication, Power and Embedded System, pp. 863–866. IEEE (2017)
Liu, J., Li, W., Karame, G.O., et al.: Scalable byzantine consensus via hardware-assisted secret sharing. IEEE Trans. Comput. 1 (2016)
Xie, M.M., Liao, X.F., Zhou, Q.: Generalized oblivious transfer protocol in distributed setting based on secret sharing. Comput. Eng. 40(3), 184–187 (2014)
Attasena, V., Darmont, J., Harbi, N.: Secret sharing for cloud data security: a survey. VLDB J. 2017(2), 1–25 (2017)
Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979)
Blakley, G.R.: Safeguarding cryptographic keys, p. 313. IEEE Computer Society (1979)
Brickell, E.F.: Some ideal secret sharing schemes. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 468–475. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_45
Bertilsson, M., Ingemarsson, I.: A construction of practical secret sharing schemes using linear block codes. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 67–79. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57220-1_53
Van Dijk, M., Kevenaar, T., Schrijen, G.J., et al.: Improved constructions of secret sharing schemes by applying (λ, w)-decompositions. In: Proceedings of the IEEE International Symposium on Information Theory, p. 282. IEEE (2003)
Beimel, A., Weinreb, E.: Monotone circuits for monotone weighted threshold functions. Elsevier North-Holland, Inc. (2006)
Li, H., Liu, H.: Multi-access structure secret sharing schemes without dealer. Nat. Sci. J. Harbin Normal Univ. (2013)
Basit, A., Kumar, N.C., Venkaiah, V.C., et al.: Multi-stage multi-secret sharing scheme for hierarchical access structure. In: International Conference on Computing, Communication and Automation. IEEE (2017)
Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. Electron. Commun. Jpn. 72(9), 56–64 (2010)
Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_3
Karchmer, M., Wigderson, A.: On span programs. In: IEEE Conference on Structure in Complexity Theory, pp. 102–111. IEEE Computer Society (1993)
Csirmaz, L.: The size of a share must be large. J. Cryptol. 10(4), 223–231 (1997)
Jhanwar, M.P., Safavi-Naini, R.: Unconditionally-secure robust secret sharing with minimum share size. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 96–110. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39884-1_9
Tran, T., Rahman, M., Bhuiyan, M.Z.A., et al.: Optimizing share size in efficient and robust secret sharing scheme for big data. IEEE Trans. Big Data PP(99), 1 (2017)
Boyle, E., Couteau, G., Gilboa, N., et al.: Homomorphic secret sharing: optimizations and applications. In: ACM SIGSAC Conference on Computer and Communications Security, pp. 2105–2122. ACM (2017)
Damgård, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 285–304. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_15
Nishide, T., Ohta, K.: Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 343–360. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_23
Boyle, E., Gilboa, N., Ishai, Y., et al.: Foundations of homomorphic secret sharing. In: 9th Innovations in Theoretical Computer Science Conference, vol. 21, pp. 1–20 (2018)
Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 101–111. ACM Press (1998)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 294–304. IEEE (2000)
Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., Paskin-Cherniavsky, A.: On the power of correlated randomness in secure computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 600–620. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_34
Barkol, O., Ishai, Y., Weinreb, E.: On d-multiplicative secret sharing. J. Cryptol. 23(4), 580–593 (2010)
Yoshida, M., Obana, S.: Verifiably multiplicative secret sharing. In: International Conference on Information Theoretic Security, pp. 73–82 (2017)
Watanabe, T., Iwamura, K., Kaneda, K.: Secrecy multiplication based on a (k, n)-threshold secret-sharing scheme using only k servers. In: Park, J., Stojmenovic, I., Jeong, H., Yi, G. (eds.) Computer Science and its Applications. LNEE, vol. 330, pp. 107–112. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-45402-2_16
Blackburn, S.R., Burmester, M., Desmedt, Y., Wild, P.R.: Efficient multiplicative sharing schemes. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 107–118. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_10
Wang, H., Lam, K.Y., Xiao, G.-Z., Zhao, H.: On multiplicative secret sharing schemes. In: Dawson, E.P., Clark, A., Boyd, C. (eds.) ACISP 2000. LNCS, vol. 1841, pp. 342–351. Springer, Heidelberg (2000). https://doi.org/10.1007/10718964_28
Jackson, W.A., Martin, K.M., O’Keefe, C.M.: Mutually trusted authority-free secret sharing schemes. J. Cryptol. 10(4), 261–289 (1997)
Boyle, E., Gilboa, N., Ishai, Y.: Group-based secure computation: optimizing rounds, communication, and computation. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 163–193. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_6
Pilaram, H., Eghlidos, T.: An efficient lattice based multi-stage secret sharing scheme. IEEE Trans. Dependable Secure Comput. 14(1), 2–8 (2017)
Shi, M., Guan, Y., Solé, P.: Two new families of two-weight codes. IEEE Trans. Inf. Theory PP(99), 1 (2017)
Gopinath, V., Bhuvaneswaran, R.S.: Design of ECC based secured cloud storage mechanism for transaction rich applications. CMC: Comput. Mater. Continua 57(2), 341–352 (2018)
Zhong, J., Liu, Z., Xu, J.: Analysis and improvement of an efficient controlled quantum secure direct communication and authentication protocol. CMC: Comput. Mater. Continua 57(3), 621–633 (2018)
Acknowledgments
This work is supported by the National Science Foundation of China P. R. (NSFC) under Grants 61703063, 61573076, 61663008; Chongqing Research Program of Basic Research and Frontier Technology under Grant CSTC2017jcyjAX0411; the Scientific Research Foundation for the Returned Overseas Chinese Scholars under Grant 2015-49; the Program for Excellent Talents of Chongqing Higher School under Grant 2014-18; Science and Technology Research Project of Chongqing Municipal Education Commission of China P. R. under Grants KJ1705139, KJ1600518, KJ1705121 and KJ1605002; Chongqing Municipal Social Livelihood Science and Technology Innovation Project under Grant CSTC2016shmszx30026; Urumqi Science and Technology Plan Project under Grant Y161320008.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Mi, B., Huang, D., Cao, J., Long, P., Pan, H. (2019). Multiplicative Linear Secret Sharing Without Interaction. In: Sun, X., Pan, Z., Bertino, E. (eds) Artificial Intelligence and Security. ICAIS 2019. Lecture Notes in Computer Science(), vol 11634. Springer, Cham. https://doi.org/10.1007/978-3-030-24271-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-24271-8_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24270-1
Online ISBN: 978-3-030-24271-8
eBook Packages: Computer ScienceComputer Science (R0)