SpringerLink
Log in

Revisiting Non-Malleable Secret Sharing

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

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11476))

Abstract

A threshold secret sharing scheme (with threshold t) allows a dealer to share a secret among a set of parties such that any group of t or more parties can recover the secret and no group of at most \(t-1\) parties learn any information about the secret. A non-malleable threshold secret sharing scheme, introduced in the recent work of Goyal and Kumar (STOC’18), additionally protects a threshold secret sharing scheme when its shares are subject to tampering attacks. Specifically, it guarantees that the reconstructed secret from the tampered shares is either the original secret or something that is unrelated to the original secret.

In this work, we continue the study of threshold non-malleable secret sharing against the class of tampering functions that tamper each share independently. We focus on achieving greater efficiency and guaranteeing a stronger security property. We obtain the following results:

  • Rate Improvement. We give the first construction of a threshold non-malleable secret sharing scheme that has rate \(> 0\). Specifically, for every \(n,t \ge 4\), we give a construction of a t-out-of-n non-malleable secret sharing scheme with rate \(\varTheta (\frac{1}{t\log ^2 n})\). In the prior constructions, the rate was \(\varTheta (\frac{1}{n\log m})\) where m is the length of the secret and thus, the rate tends to 0 as \(m \rightarrow \infty \). Furthermore, we also optimize the parameters of our construction and give a concretely efficient scheme.

  • Multiple Tampering. We give the first construction of a threshold non-malleable secret sharing scheme secure in the stronger setting of bounded tampering wherein the shares are tampered by multiple (but bounded in number) possibly different tampering functions. The rate of such a scheme is \(\varTheta (\frac{1}{k^3t\log ^2 n})\) where k is an apriori bound on the number of tamperings. We complement this positive result by proving that it is impossible to have a threshold non-malleable secret sharing scheme that is secure in the presence of an apriori unbounded number of tamperings.

  • General Access Structures. We extend our results beyond threshold secret sharing and give constructions of rate-efficient, non-malleable secret sharing schemes for more general monotone access structures that are secure against multiple (bounded) tampering attacks.

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
EUR 32.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
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 96.29
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 128.39
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** 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.

    See Sect. 3 for a precise definition.

  2. 2.

    We refer the reader to [GK18a, GK18b] for a thorough discussion on the connection between non-malleable secret sharing and related notions such as verifiable secret sharing [CGMA85] and AMD codes [CDF+08].

  3. 3.

    As in the case of single tampering, a tampering function could just output the same shares and in which the reconstructed secret will be s. Our definition also captures this property and we refer to Sect. 3 for a precise definition.

  4. 4.

    812 bits is the minimal message length that gives 80 bits of security.

  5. 5.

    See the main body for the precise statement.

  6. 6.

    This is the reason why we could only achieve thresholds \(t \ge 4\).

  7. 7.

    We note that using perfect hash function families for constructing threshold secret sharing scheme is not new (see [Bla99, SNW01] for a comprehensive discussion). However, to the best of our knowledge, this is the first application of this technique to construct local leakage resilient secret sharing scheme.

  8. 8.

    Recall that this denotes that the function can choose to leak at most \(m_1\) bits from each share in a set of size \(t-2\) apart from the two that are completely leaked.

  9. 9.

    We refer the reader to Definition 1, Definition 2 for definitions of 4-monotone access structures and minimal authorized set.

  10. 10.

    We note that our proof of security goes through even if this secret sharing scheme only has statistical privacy.

References

  1. Aggarwal, D., Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: Optimal computational split-state non-malleable codes. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 393–417. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_15

    Chapter  Google Scholar 

  2. Aggarwal, D., Dodis, Y., Kazana, T., Obremski, M.: Non-malleable reductions and applications. In: STOC, pp. 459–468 (2015)

    Google Scholar 

  3. Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. In: STOC, pp. 774–783 (2014)

    Google Scholar 

  4. Aggarwal, D., et al.: Stronger leakage-resilient and non-malleable secret-sharing schemes for general access structures. Cryptology ePrint Archive, Report 2018/1147 (2018). https://eprint.iacr.org/2018/1147

  5. Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: Explicit non-malleable codes against bit-wise tampering and permutations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 538–557. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_26

    Chapter  Google Scholar 

  6. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)

    Article  MathSciNet  Google Scholar 

  7. Ball, M., Dachman-Soled, D., Guo, S., Malkin, T., Tan, L.-Y.: Non-malleable codes for small-depth circuits. In: FOCS (2018, to appear)

    Google Scholar 

  8. 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, Part I. LNCS, vol. 10991, pp. 531–561. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_18

    Chapter  Google Scholar 

  9. Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codes for bounded depth, bounded fan-in circuits. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 881–908. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_31

    Chapter  MATH  Google Scholar 

  10. Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codes from average-case hardness: \({\sf A\sf {\sf C}}^0\), decision trees, and streaming space-bounded tampering. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 618–650. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_20

    Chapter  Google Scholar 

  11. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of eliminating errors in cryptographic computations. J. Cryptol. 14(2), 101–119 (2001)

    Article  MathSciNet  Google Scholar 

  12. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC, pp. 1–10 (1988)

    Google Scholar 

  13. Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of AFIPS 1979 National Computer Conference, vol. 48, pp. 313–317 (1979)

    Google Scholar 

  14. Blackburn, S.R.: Combinatorics and Threshold Cryptography. Chapman and Hall CRC Research Notes in Mathematics, pp. 49–70 (1999)

    Google Scholar 

  15. Chaum, D., Crepeau, C., Damgaard, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC, pp. 11–19. ACM (1988)

    Google Scholar 

  16. Cramer, R., Dodis, Y., Fehr, S., Padró, C., Wichs, D.: Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 471–488. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_27

    Chapter  Google Scholar 

  17. Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17(2), 230–261 (1988)

    Article  MathSciNet  Google Scholar 

  18. Chattopadhyay, E., Goyal, V., Li, X.: Non-malleable extractors and codes, with their many tampered extensions. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18–21 June 2016, pp. 285–298 (2016)

    Google Scholar 

  19. Chandran, N., Goyal, V., Mukherjee, P., Pandey, O., Upadhyay, J.: Block-wise non-malleable codes. In: ICALP (2016)

    Google Scholar 

  20. Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: 26th Annual Symposium on Foundations of Computer Science, pp. 383–395. IEEE Computer Society Press, October 1985

    Google Scholar 

  21. Chandran, N., Kanukurthi, B., Raghuraman, S.: Information-theoretic local non-malleable codes and their applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016, Part II. LNCS, vol. 9563, pp. 367–392. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_14

    Chapter  Google Scholar 

  22. Chattopadhyay, E., Li, X.: Non-malleable codes and extractors for small-depth circuits, and affine functions. In: Hatami, H., McKenzie, P., King, V. (eds.) 49th Annual ACM Symposium on Theory of Computing, pp. 1171–1184. ACM Press, June 2017

    Google Scholar 

  23. De Santis, A., Desmedt, Y., Frankel, Y., Yung, M.: How to share a function securely. In: 26th Annual ACM Symposium on Theory of Computing, pp. 522–533. ACM Press, May 1994

    Google Scholar 

  24. Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_28

    Chapter  Google Scholar 

  25. Dziembowski, S., Kazana, T., Obremski, M.: Non-malleable codes from two-source extractors. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 239–257. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_14

    Chapter  Google Scholar 

  26. Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Proceedings of Innovations in Computer Science - ICS 2010, Tsinghua University, Bei**g, China, 5–7 January 2010, pp. 434–452 (2010)

    Google Scholar 

  27. Fredman, M.L., Komlós, J.: On the size of separating systems and families of perfect hash functions. SIAM J. Algebraic Discrete Methods 5(1), 61–68 (1984)

    Article  MathSciNet  Google Scholar 

  28. Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D.: Continuous non-malleable codes. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 465–488. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_20

    Chapter  Google Scholar 

  29. Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D.: A tamper and leakage resilient von neumann architecture. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 579–603. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_26

    Chapter  Google Scholar 

  30. Faust, S., Mukherjee, P., Venturi, D., Wichs, D.: Efficient non-malleable codes and key-derivation for poly-size tampering circuits. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 111–128. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_7

    Chapter  Google Scholar 

  31. Frankel, Y.: A practical protocol for large group oriented networks. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 56–61. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_8

    Chapter  Google Scholar 

  32. Faust, S., Rabin, T., Reyzin, L., Tromer, E., Vaikuntanathan, V.: Protecting circuits from leakage: the computationally-bounded and noisy cases. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 135–156. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_7

    Chapter  Google Scholar 

  33. Goyal, V., Kumar, A.: Non-malleable secret sharing. In: STOC, pp. 685–698 (2018)

    Google Scholar 

  34. Goyal, V., Kumar, A.: Non-malleable secret sharing for general access structures. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 501–530. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_17

    Chapter  Google Scholar 

  35. Goyal, V., Kumar, A., Park, S., Richelson, S., Srinivasan, A.: Non-malleable commitments from non-malleable extractors. Manuscript, accessed via personal communication (2018)

    Google Scholar 

  36. Gennaro, R., Lysyanskaya, A., Malkin, T., Micali, S., Rabin, T.: Algorithmic tamper-proof (ATP) security: theoretical foundations for security against hardware tampering. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 258–277. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_15

    Chapter  Google Scholar 

  37. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th Annual ACM Symposium on Theory of Computing, pp. 218–229. ACM Press, May 1987

    Google Scholar 

  38. Gupta, D., Maji, H.K., Wang, M.: Constant-rate non-malleable codes in the split-state model. Cryptology ePrint Archive, Report 2017/1048 (2017). https://eprint.iacr.org/2017/1048

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

    Chapter  Google Scholar 

  40. Jafargholi, Z., Wichs, D.: Tamper detection and continuous non-malleable codes. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 451–480. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_19

    Chapter  Google Scholar 

  41. Kiayias, A., Liu, F.-H., Tselekounis, Y.: Non-malleable codes for partial functions with manipulation detection. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 577–607. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_20

    Chapter  Google Scholar 

  42. Kumar, A., Meka, R., Sahai, A.: Leakage-resilient secret sharing. Cryptology ePrint Archive, Report 2018/1138 (2018). https://eprint.iacr.org/2018/1138

  43. Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Four-state non-malleable codes with explicit constant rate. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part II. LNCS, vol. 10678, pp. 344–375. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_11

    Chapter  Google Scholar 

  44. Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Non-malleable randomness encoders and their applications. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 589–617. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_19

    Chapter  Google Scholar 

  45. Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, 18–21 May 1993, pp. 102–111 (1993)

    Google Scholar 

  46. Li, X.: Improved non-malleable extractors, non-malleable codes and independent source extractors. In: STOC (2017)

    Google Scholar 

  47. Liu, F.-H., Lysyanskaya, A.: Tamper and leakage resilience in the split-state model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 517–532. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_30

    Chapter  Google Scholar 

  48. Liu, T., Vaikuntanathan, V.: Breaking the circuit-size barrier in secret sharing. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th Annual ACM Symposium on Theory of Computing, pp. 699–708. ACM Press, June 2018

    Google Scholar 

  49. Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22(4), 838–856 (1993)

    Article  MathSciNet  Google Scholar 

  50. Ostrovsky, R., Persiano, G., Venturi, D., Visconti, I.: Continuously non-malleable codes in the split-state model from minimal assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 608–639. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_21

    Chapter  Google Scholar 

  51. Rothblum, G.N.: How to compute under \({\cal{AC}}^{\sf 0}\) leakage without secure hardware. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 552–569. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_32

    Chapter  Google Scholar 

  52. Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)

    Article  MathSciNet  Google Scholar 

  53. Safavi-Naini, R., Wang, H.: Robust additive secret sharing schemes over ZM. In: Lam, K.-Y., Shparlinski, I., Wang, H., **ng, C. (eds.) Cryptography and Computational Number Theory, pp. 357–368. Birkhäuser, Basel (2001)

    Chapter  Google Scholar 

  54. Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775–786 (1990)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The first author’s research supported in part by the IBM PhD Fellowship. The first author’s research also supported in part from a DARPA /ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, an Okawa Foundation Research Grant, NSF-BSF grant 1619348, DARPA SafeWare subcontract to Galois Inc., DARPA SPAWAR contract N66001-15-1C-4065, US-Israel BSF grant 2012366, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C- 0205. The second author’s research supported in part from DARPA/ARL SAFEWARE Award W911NF15C0210, AFOSR Award FA9550-15-1-0274, AFOSR YIP Award, DARPA and SPAWAR under contract N66001-15-C-4065, a Hellman Award and research grants by the Okawa Foundation, Visa Inc., and Center for Long-Term Cybersecurity (CLTC, UC Berkeley) of Sanjam Garg. The views expressed are those of the authors and do not reflect the official policy or position of the funding agencies.

The authors thank Pasin Manurangsi for pointing to the work of Alon et al. [AYZ95] for the explicit construction of perfect hash function family. The authors also thank Sanjam Garg, Peihan Miao and Prashant Vasudevan for useful comments on the write-up.

Author information

Authors and Affiliations

  1. UCLA, Los Angeles, USA

    Saikrishna Badrinarayanan

  2. UC Berkeley, Berkeley, USA

    Akshayaram Srinivasan

Authors
  1. Saikrishna Badrinarayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Akshayaram Srinivasan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Saikrishna Badrinarayanan .

Editor information

Editors and Affiliations

  1. Technion, Haifa, Israel

    Yuval Ishai

  2. COSIC Group, KU Leuven, Heverlee, Belgium

    Vincent Rijmen

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Badrinarayanan, S., Srinivasan, A. (2019). Revisiting Non-Malleable Secret Sharing. In: Ishai, Y., Rijmen, V. (eds) Advances in Cryptology – EUROCRYPT 2019. EUROCRYPT 2019. Lecture Notes in Computer Science(), vol 11476. Springer, Cham. https://doi.org/10.1007/978-3-030-17653-2_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-17653-2_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-17652-5

  • Online ISBN: 978-3-030-17653-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation