[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Constructing Leakage-Resilient Shamir’s Secret Sharing: Over Composite Order Fields

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2024 (EUROCRYPT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14654))

Abstract

Probing physical bits in hardware has compromised cryptographic systems. This work investigates how to instantiate Shamir’s secret sharing so that the physical probes into its shares reveal statistically insignificant information about the secret.

Over prime fields, Maji, Nguyen, Paskin-Cherniavsky, Suad, and Wang (EUROCRYPT 2021) proved that choosing random evaluation places achieves this objective with high probability. Our work extends their randomized construction to composite order fields – particularly for fields with characteristic 2. Next, this work presents an algorithm to classify evaluation places as secure or vulnerable against physical-bit probes for some specific cases.

Our security analysis of the randomized construction is Fourier-analytic, and the classification techniques are combinatorial. Our analysis relies on (1) contemporary Bézout-theorem-type algebraic complexity results that bound the number of simultaneous zeroes of a system of polynomial equations over composite order fields and (2) characterization of the zeroes of an appropriate generalized Vandermonde determinant.

Hemanta K. Maji, and Xiuyu Ye 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. Hai H. Nguyen is supported by the Zurich Information Security & Privacy Center (ZISC). Anat Paskin-Cherniavsky is supported by the Ariel Cyber Innovation Center in conjunction with the Israel National Cyber directorate in the Prime Minister’s Office.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 95.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 109.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Leakage-resilient secure computation considers adversaries that corrupt parties to obtain their shares and leak additional information from honest parties’ shares.

  2. 2.

    Looking ahead, we will prove a significantly stronger generalization of Lemma 9 for arbitrary number of parties.

  3. 3.

    First perform Gaussian elimination, and then the determinant is the product of the diagonal elements.

References

  1. Adams, D.Q., et al.: Lower bounds for leakage-resilient secret sharing schemes against probing attacks. In: ISIT 2021 (2021)

    Google Scholar 

  2. 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

    Chapter  Google Scholar 

  3. 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

    Chapter  Google Scholar 

  4. Bafna, M., Sudan, M., Velusamy, S., Xiang,D.: Elementary analysis of isolated zeroes of a polynomial system (2021). arXiv preprint arXiv:2102.00602

  5. 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

    Chapter  Google Scholar 

  6. Benhamouda, F., Degwekar, A., Ishai, Y., Rabin, T.: On the local leakage resilience of linear secret sharing schemes. J. Cryptol. 34(2), 10 (2021). https://doi.org/10.1007/s00145-021-09375-2

    Article  MathSciNet  Google Scholar 

  7. Bishop, A., Pastro, V., Rajaraman, R., Wichs, D.: Essentially optimal robust secret sharing with maximal corruptions. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 58–86. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_3

    Chapter  Google Scholar 

  8. 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

    Chapter  Google Scholar 

  9. Brandão, L.T.A.N., Peralta, R.: NIST first call for multi-party threshold schemes, 25 January 2023. https://csrc.nist.gov/publications/detail/nistir/8214c/draft

  10. Chandran, N., Kanukurthi, B., Lakshmi, S., Obbattu, B., Sekar, S.: Short leakage resilient and non-malleable secret sharing schemes. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part I, vol. 13507, LNCS, pp. 178–207. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15802-5_7

  11. Chattopadhyay, E., et al.: Extractors and secret sharing against bounded collusion protocols. In: 61st FOCS, pp. 1226–1242. IEEE Computer Society Press, November 2020. https://doi.org/10.1109/FOCS46700.2020.00117

  12. Con, R., Tamo, I.: Nonlinear repair of reed-Solomon codes. IEEE Trans. Inf. Theory 68(8), 5165–5177 (2022). https://doi.org/10.1109/TIT.2022.3167615

    Article  MathSciNet  Google Scholar 

  13. Costes, N., Stam, M.: Redundant code-based masking revisited. IACR TCHES. 2021(1), 426–450 (2021). https://tches.iacr.org/index.php/TCHES/article/view/8740, https://doi.org/10.46586/tches.v2021.i1.426-450

  14. Dimakis, A.G., Godfrey, P.B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE Trans. Inf. Theory 56(9), 4539–4551 (2010)

    Article  Google Scholar 

  15. El Rouayheb, S., Ramchandran,K.: Fractional repetition codes for repair in distributed storage systems. In: 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1510–1517. IEEE (2010)

    Google Scholar 

  16. Fehr, S., Yuan, C.: Towards optimal robust secret sharing with security against a rushing adversary. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 472–499. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_16

    Chapter  Google Scholar 

  17. Fehr, S., Yuan, C.: Robust secret sharing with almost optimal share size and security against rushing adversaries. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 470–498. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_17

    Chapter  Google Scholar 

  18. Goparaju, S., El Rouayheb, S., Calderbank, R., Vincent Poor, H.: Data secrecy in distributed storage systems under exact repair. In: 2013 International Symposium on Network Coding (NetCod), pp. 1–6. IEEE (2013)

    Google Scholar 

  19. Goparaju, S., Fazeli, A., Vardy, A.: Minimum storage regenerating codes for all parameters. IEEE Trans. Inf. Theory 63(10), 6318–6328 (2017)

    Article  MathSciNet  Google Scholar 

  20. Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Diakonikolas, I., Kempe, D., Henzinger, M. eds. 50th ACM STOC, pp. 685–698. ACM Press, June 2018. https://doi.org/10.1145/3188745.3188872

  21. Guruswami, V., Wootters, M.: Repairing reed-Solomon codes. In: Wichs, D., Mansour, Y., (eds.) 48th ACM STOC, pp. 216–226. ACM Press, June 2016. https://doi.org/10.1145/2897518.2897525

  22. 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

    Article  MathSciNet  Google Scholar 

  23. Hazay, C., Venkitasubramaniam, M., Weiss, M.: The price of active security in cryptographic protocols. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 184–215. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_7

    Chapter  Google Scholar 

  24. Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_27

  25. Klein, O., Komargodski, I.: New bounds on the local leakage resilience of Shamir’s secret sharing scheme. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology–CRYPTO 2023. CRYPTO 2023. LNCS, vol. 14081, pp. 139–170. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38557-5_5

  26. Kumar, A., Meka, R., Sahai, A.: Leakage-resilient secret sharing against colluding parties. In: Zuckerman, D., (ed.) 60th FOCS, pp. 636–660. IEEE Computer Society Press, November 2019. https://doi.org/10.1109/FOCS.2019.00045

  27. 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

    Chapter  Google Scholar 

  28. 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, July 5-7, 2022, Cambridge, MA, USA, vol. 230, LIPIcs, pp. 16:1–16:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ITC.2022.16

  29. 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, June 26–July 1, 2022, pp. 2678–2683. IEEE (2022). https://doi.org/10.1109/ISIT50566.2022.9834695

  30. Maji, H.K., Nguyen, H.H., Paskin-Cherniavsky, A., Ye, X.: Security of Shamir’s secret-sharing against physical bit leakage: Secure evaluation places (2023). https://www.cs.purdue.edu/homes/hmaji/papers/MNPY23.pdf

  31. 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

    Chapter  Google Scholar 

  32. Manurangsi, P., Srinivasan, A., Vasudevan, P.N.: Nearly optimal robust secret sharing against rushing adversaries. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 156–185. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_6

    Chapter  Google Scholar 

  33. 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

    Chapter  Google Scholar 

  34. NIST. Randomness beacon project. http://www.nist.gov/itl/csd/ct/nist_beacon.cfm

  35. Papailiopoulos, D.S., Dimakis, A.G., Cadambe, V.R.: Repair optimal erasure codes through Hadamard designs. IEEE Trans. Inf. Theory 59(5), 3021–3037 (2013)

    Article  MathSciNet  Google Scholar 

  36. Vinayak Rashmi, K., Shah, N.B., Vijay Kumar, P.: Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction. IEEE Trans. Inf. Theory 57(8), 5227–5239 (2011)

    Article  MathSciNet  Google Scholar 

  37. Shamir, A.: How to share a secret. Commun. Assoc. Comput. Mach. 22(11), 612–613 (1979)

    MathSciNet  Google Scholar 

  38. 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

    Chapter  Google Scholar 

  39. Tamo, I., Wang, Z., Bruck, J.: Zigzag codes: MDS array codes with optimal rebuilding. IEEE Trans. Inf. Theory 59(3), 1597–1616 (2012)

    Article  MathSciNet  Google Scholar 

  40. Wang, Z., Tamo, I., Bruck, J.: Explicit minimum storage regenerating codes. IEEE Trans. Inf. Theory 62(8), 4466–4480 (2016)

    Article  MathSciNet  Google Scholar 

  41. Wooley, T.D.: A note on simultaneous congruences. J. Number Theory. 58(2), 288–297 (1996)

    Article  MathSciNet  Google Scholar 

  42. Ye, M., Barg, A.: Explicit constructions of high-rate MDS array codes with optimal repair bandwidth. IEEE Trans. Inf. Theory 63(4), 2001–2014 (2017)

    Article  MathSciNet  Google Scholar 

  43. Ye, M., Barg, A.: Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization. IEEE Trans. Inf. Theory 63(10), 6307–6317 (2017)

    Article  MathSciNet  Google Scholar 

  44. Zhao, X.: A note on multiple exponential sums in function fields. Finite Fields Appl. 18(1), 35–55 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Purdue University, West Lafayette, USA

    Hemanta K. Maji & Xiuyu Ye

  2. Department of Computer Science, ETH Zurich, Zurich, Switzerland

    Hai H. Nguyen

  3. Department of Computer Science, Ariel University, Ariel, Israel

    Anat Paskin-Cherniavsky

Authors
  1. Hemanta K. Maji
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hai H. Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anat Paskin-Cherniavsky
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiuyu Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hai H. Nguyen .

Editor information

Editors and Affiliations

  1. Zama, Paris, France

    Marc Joye

  2. Ruhr University Bochum, Bochum, Germany

    Gregor Leander

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Maji, H.K., Nguyen, H.H., Paskin-Cherniavsky, A., Ye, X. (2024). Constructing Leakage-Resilient Shamir’s Secret Sharing: Over Composite Order Fields. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14654. Springer, Cham. https://doi.org/10.1007/978-3-031-58737-5_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-58737-5_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-58736-8

  • Online ISBN: 978-3-031-58737-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation