Abstract
Motivated by leakage-resilient secure computation of circuits with addition and multiplication gates, this work studies the leakage-resilience of linear secret-sharing schemes with a small reconstruction threshold against any bounded-size family of joint leakage attacks, i.e., the leakage function can leak global information from all secret shares.
We first prove that, with high probability, the Massey secret-sharing scheme corresponding to a random linear code over a finite field F is leakage-resilient against any \(\ell \)-bit joint leakage family of size at most \(|{F}|^{k-2.01}/8^\ell \), where k is the reconstruction threshold. Our result (1) bypasses the bottleneck due to the existing Fourier-analytic approach, (2) enables secure multiplication of secrets, and (3) is near-optimal. We use combinatorial and second-moment techniques to prove the result.
Next, we show that the Shamir secret-sharing scheme over a prime-order field F with randomly chosen evaluation places and with threshold k is leakage-resilient to any \(\ell \)-bit joint leakage family of size at most \(|{F}|^{2k-n-2.01}/(k!\cdot 8^\ell )\) with high probability. We prove this result by marrying our proof techniques for the first result with the existing Fourier analytical approach. Moreover, it is unlikely that one can extend this result beyond \(k/n\leqslant 0.5\) due to the technical hurdle for the Fourier-analytic approach.
Hemanta K. Maji, Hai H. Nguyen, Mingyuan Wang, Xiuyu Ye, and Albert Yu are supported in part by an NSF CRII Award CNS–1566499, NSF SMALL Awards CNS–1618822 and CNS–2055605, the IARPA HECTOR project, MITRE Innovation Program Academic Cybersecurity Research Awards (2019–2020, 2020–2021), a Ross-Lynn Research Scholars Grant (2021–2022), a Purdue Research Foundation (PRF) Award (2017–2018), and The Center for Science of Information, an NSF Science and Technology Center, Cooperative Agreement CCF–0939370. Anat Paskin-Cherniavsky and Tom Suad are supported by the Ariel Cyber Innovation Center in conjunction with the Israel National Cyber directorate in the Prime Minister’s Office. Mingyuan Wang is also supported in part by DARPA under Agreement No. HR00112020026, AFOSR Award FA9550-19-1-0200, NSF CNS Award 1936826, and research grants by the Sloan Foundation, and Visa Inc. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
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
Notes
- 1.
This random linear code only needs to be chosen once. With only an exponentially small failure probability, the Massey secret-sharing scheme corresponding to this code shall be leakage-resilient. For instance, this random linear code can be specified by, for example, a common random string (CRS).
- 2.
This observation is due to that a random square matrix over a large enough field F is full-rank with overwhelming probability.
References
Adams, D. Q., et al.: Lower bounds for leakage-resilient secret sharing schemes against probing attacks. In: IEEE International Symposium on Information Theory ISIT 2021 (2021)
Aggarwal, D., et al.: Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 510–539. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_18
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)
Badrinarayanan, S., Srinivasan, A.: Revisiting non-malleable secret sharing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 593–622. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_20
Benhamouda, F., Degwekar, A., Ishai, Y., Rabin, T.: On the local leakage resilience of linear secret sharing schemes. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 531–561. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_18
Benhamouda, F., Degwekar, A., Ishai, Y., Rabin, T.: On the local leakage resilience of linear secret sharing schemes. J. Cryptol. 34(2), 1–65 (2021). https://doi.org/10.1007/s00145-021-09375-2
Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation based on leaky correlations: high resilience setting. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_1
Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation with constant communication overhead using multiplication embeddings. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 375–398. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_20
Bogdanov, A., Ishai, Y., Srinivasan, A.: Unconditionally secure computation against low-complexity leakage. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 387–416. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_14
Cascudo, I., Cramer, R., Xing, C., Yuan, C.: Amortized complexity of information-theoretically secure MPC revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 395–426. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_14
Chattopadhyay, E., et al.: Extractors and secret sharing against bounded collusion protocols. In: 61st Annual Symposium on Foundations of Computer Science, Durham, NC, USA, 16–19 November 2020, pp. 1226–1242. IEEE (2020). https://doi.org/10.1109/FOCS46700.2020.00117
Cramer, R.: The arithmetic codex: theory and applications. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 1–1. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_1
Garcia, A., Stichtenoth, H.: A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound. Inventiones Math. 121(1), 211–222 (1995)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Alfred A., ed., 19th Annual ACM Symposium on Theory of Computing, New York City, NY, USA, 25–27 May 1987, pp. 218–229. ACM Press (1987). https://doi.org/10.1145/28395.28420
Goppa, V.D.: A new class of linear correcting codes. Problemy Peredachi Informatsii 6(3), 24–30 (1970)
Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Diakonikolas, I., Kempe, D., Henzinger, M., (eds.), 50th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, USA, 25–29 June 2018, pp. 685–698. ACM Press (2018). https://doi.org/10.1145/3188745.3188872
Guruswami, V., Wootters, M.: Repairing reed-solomon codes. In: Wichs, D., Mansour, Y., (eds.), 48th Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 18–21 June 2016, pp. 216–226. ACM Press (2018). https://doi.org/10.1145/2897518.2897525
Guruswami, V., Wootters, M.: Repairing reed-solomon codes. IEEE Trans. Inf. Theory 63(9), 5684–5698 (2017). https://doi.org/10.1109/TIT.2017.2702660
Kalai, Y.T., Reyzin, L.: A survey of leakage-resilient cryptography. Cryptology ePrint Archive, Report 2019/302 (2019). https://eprint.iacr.org/2019/302
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9
Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25
Kumar, A., Meka, R., Sahai, A.: Leakage-resilient secret sharing against colluding parties. In: Zuckerman, D., ed., 60th Annual Symposium on Foundations of Computer Science, Baltimore, MD, USA, 9–12 November 2019, pp. 636–660. IEEE Computer Society Press (2019). https://doi.org/10.1109/FOCS.2019.00045
Lin, F., Cheraghchi, M., Guruswami, V., Safavi-Naini, R., Wang, H.: Leakage-resilient secret sharing in non-compartmentalized models. In: Kalai, Y.T., Smith, A.D., Wichs, D., (eds.), ITC 2020: 1st Conference on Information-Theoretic Cryptography, Boston, MA, USA, 17–19 June 2020, pp. 7:1–7:24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ITC.2020.7
Florence Jessie MacWilliams and Neil James Alexander Sloane: The Theory of Error Correcting Codes, vol. 16. Elsevier, Amsterdam (1977)
Maji, H.K., Nguyen, H.H., Paskin-Cherniavsky, A., Suad, T., Wang, M.: Leakage-resilience of the Shamir secret-sharing scheme against physical-bit leakages. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 344–374. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_12
Maji, H.K., et al.: Tight estimate of the local leakage resilience of the additive secret-sharing scheme & its consequences. In: Dachman-Soled, D., ed., 3rd Conference on Information-Theoretic Cryptography, ITC 2022, 5–7 July 2022, Cambridge, MA, USA, volume 230 of LIPIcs, pp. 16:1–16:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ITC.2022.16
Maji, H.K., Nguyen, H.H., Paskin-Cherniavsky, A., Wang, M.: Improved bound on the local leakage-resilience of Shamir’s secret sharing. In IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, 26 June–1 July 2022, pp. 2678–2683. IEEE (2022). https://doi.org/10.1109/ISIT50566.2022.9834695
Maji, H.K., Paskin-Cherniavsky, A., Suad, T., Wang, M.: Constructing locally leakage-resilient linear secret-sharing schemes. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 779–808. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_26
Massey, J.L.: Threshold decoding (1963)
Massey, J.L.: Some applications of coding theory in cryptography. Mat. Contemp. 21(16), 187–209 (2001)
Nielsen, J.B., Simkin, M.: Lower bounds for leakage-resilient secret sharing. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 556–577. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_20
Pietrzak, K.: Cryptography from learning parity with noise. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 99–114. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27660-6_9
Regev, O.: The learning with errors problem. Invited Surv. CCC 7(30), 11 (2010)
Shamir, A.: How to share a secret. Commun. Assoc. Comput. Mach. 22(11), 612–613 (1979)
Srinivasan, A., Vasudevan, P.N.: Leakage resilient secret sharing and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 480–509. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_17
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Maji, H.K. et al. (2022). Leakage-resilient Linear Secret-sharing Against Arbitrary Bounded-size Leakage Family. In: Kiltz, E., Vaikuntanathan, V. (eds) Theory of Cryptography. TCC 2022. Lecture Notes in Computer Science, vol 13747. Springer, Cham. https://doi.org/10.1007/978-3-031-22318-1_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-22318-1_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22317-4
Online ISBN: 978-3-031-22318-1
eBook Packages: Computer ScienceComputer Science (R0)