nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Non-malleability Against Polynomial Tampering

verfasst von : Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials. Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable code that is secure against tampering by bounded-size arithmetic circuits.

We show applications of our non-malleable code in constructing non-malleable secret sharing schemes that are robust against bounded-degree polynomial tampering. In fact our result is stronger: we can handle adversaries that can adaptively choose the polynomial tampering function based on initial leakage of a bounded number of shares.

Our results are derived from explicit constructions of seedless non-malleable extractors that can handle bounded-degree polynomial tampering functions. Prior to our work, no such result was known even for degree-2 (quadratic) polynomials.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Multiparty Generation of an RSA Modulus

Nächstes Kapitel Non-malleable Secret Sharing Against Bounded Joint-Tampering Attacks in the Plain Model

We say a distribution is flat if it is uniformly distributed on its support.

See Sect. 3 for a quick recap of characters of finite fields.

The definition of MDS codes and the construction of systematic MDS codes can be found in Sect. 3.5.

That is, there exists \(x\in L_{a,b}\) s.t. \(P(x)\ne x\).

Aggarwal, D., et al.: Stronger leakage-resilient and non-malleable secret-sharing schemes for general access structures. IACR Cryptology ePrint Archive 2018, 1147 (2018)

Aggarwal, D., Dodis, Y., Kazana, T., Obremski, M.: Non-malleable reductions and applications. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 459–468. ACM (2015)

Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. SIAM J. Comput. 47(2), 524–546 (2018)MathSciNetMATHCrossRef

Aggarwal, D., Obremski, M.: A constant-rate non-malleable code in the split-state model. IACR Cryptology ePrint Archive 2019, 1299 (2019)

Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: A rate-optimizing compiler for non-malleable codes against bit-wise tampering and permutations. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 375–397. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_16CrossRef

Badrinarayanan, S., Srinivasan, A.: Revisiting non-malleable secret sharing. IACR Cryptology ePrint Archive 2018, 1144 (2018)

Ball, M., Chattopadhyay, E., Liao, J., Malkin, T., Tan, L.: Non-malleability against polynomial tampering. IACR Cryptology ePrint Archive 2020, 147 (2020). https://eprint.iacr.org/2020/147

Ball, M., Dachman-Soled, D., Guo, S., Malkin, T., Tan, L.Y.: Non-malleable codes for small-depth circuits. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 826–837. IEEE (2018)

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_31MATHCrossRef

10.

Ball, M., Guo, S., Wichs, D.: Non-malleable codes for decision trees. IACR Cryptology ePrint Archive 2019, 379 (2019)

11.

Barak, B., Impagliazzo, R., Wigderson, A.: Extracting randomness using few independent sources. SIAM J. Comput. 36(4), 1095–1118 (2006). https://doi.org/10.1137/S0097539705447141MathSciNetMATHCrossRef

12.

Bennett, C., Brassard, G., Robert, J.M.: Privacy amplification by public discussion. SIAM J. Comput. 17, 210–229 (1988)MathSciNetMATHCrossRef

13.

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

14.

Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory 01(01), 1–32 (2005). https://doi.org/10.1142/S1793042105000108MathSciNetMATHCrossRef

15.

Bourgain, J.: On the construction of affine extractors. GAFA Geom. Funct. Anal. 17(1), 33–57 (2007)MathSciNetMATHCrossRef

16.

Chattopadhyay, E., Goyal, V., Li, X.: Non-malleable extractors and codes, with their many tampered extensions. In: STOC (2016)

17.

Chattopadhyay, E., Li, X.: Non-malleable codes and extractors for small-depth circuits, and affine functions. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1171–1184. ACM (2017)

18.

Chattopadhyay, E., Li, X.: Non-malleable codes, extractors and secret sharing for interleaved tampering and composition of tampering. Technical report, Cryptology ePrint Archive, Report 2018/1069, 2018 (2019)

19.

Chattopadhyay, E., Zuckerman, D.: Non-malleable codes against constant split-state tampering. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pp. 306–315 (2014)

20.

Chattopadhyay, E., Zuckerman, D.: Explicit two-source extractors and resilient functions. Ann. Math. 189(3), 653–705 (2019). https://doi.org/10.4007/annals.2019.189.3.1MathSciNetMATHCrossRef

21.

Cheraghchi, M., Guruswami, V.: Non-malleable coding against bit-wise and split-state tampering. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 440–464. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_19MATHCrossRef

22.

Cheraghchi, M., Shokrollahi, A.: Almost-uniform sampling of points on high-dimensional algebraic varieties. In: 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, 26–28 February 2009, Proceedings, pp. 277–288 (2009)

23.

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

24.

Chor, B., Goldreich, O., Hasted, J., Freidmann, J., Rudich, S., Smolensky, R.: The bit extraction problem or t-resilient functions. In: IEEE Symposium on Foundations of Computer Science, pp. 396–407 (1985). https://doi.org/10.1109/SFCS.1985.55

25.

Coretti, S., Maurer, U., Tackmann, B., Venturi, D.: From single-bit to multi-bit public-key encryption via non-malleable codes. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 532–560. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_22CrossRef

26.

Dodis, Y., Li, X., Wooley, T.D., Zuckerman, D.: Privacy amplification and nonmalleable extractors via character sums. SIAM J. Comput. 43(2), 800–830 (2014)MathSciNetMATHCrossRef

27.

Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: STOC, pp. 601–610 (2009)

28.

Dusart, P.: Estimates of some functions over primes without RH. arXiv preprint arXiv:1002.0442 (2010)

29.

Dvir, Z.: Extractors for varieties. Comput. Complex. 21(4), 515–572 (2012)MathSciNetMATHCrossRef

30.

Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. Comput. Complex. 18(1), 1–58 (2009)MathSciNetMATHCrossRef

31.

Dvir, Z., Kopparty, S., Saraf, S., Sudan, M.: Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 181–190 (2009)

32.

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

33.

Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. J. ACM 65(4), 20:1–20:32 (2018). https://doi.org/10.1145/3178432MathSciNetMATHCrossRef

34.

Gabizon, A., Raz, R.: Deterministic extractors for affine sources over large fields. Combinatorica 28(4), 415–440 (2008)MathSciNetMATHCrossRef

35.

Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 685–698. ACM (2018)

36.

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_17CrossRef

37.

Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 1128–1141. ACM (2016)

38.

Gupta, D., Maji, H.K., Wang, M.: Constant-rate non-malleable codes in the split-state model. Technical report, Technical Report Report 2017/1048, Cryptology ePrint Archive (2018)

39.

Guruswami, V., Umans, C., Vadhan, S.P.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56(4), 1–34 (2009)MathSciNetMATHCrossRef

40.

Huang, M.-D., Wong, Y.-C.: An algorithm for approximate counting of points on algebraic sets over finite fields. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 514–527. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054889CrossRef

41.

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. LNCS, vol. 10678, pp. 344–375. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_11CrossRef

42.

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

43.

Lacan, J., Fimes, J.: Systematic MDS erasure codes based on vandermonde matrices. IEEE Commun. Lett. 8(9), 570–572 (2004). https://doi.org/10.1109/LCOMM.2004.833807MATHCrossRef

44.

Li, X.: Improved non-malleable extractors, non-malleable codes and independent source extractors. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 1144–1156 (2017)

45.

Li, X.: Non-malleable extractors and non-malleable codes: partially optimal constructions. In: 34th Computational Complexity Conference, CCC 2019, New Brunswick, NJ, USA, 18–20 July 2019, pp. 28:1–28:49 (2019)

46.

Lin, F., Cheraghchi, M., Guruswami, V., Safavi-Naini, R., Wang, H.: Non-malleable secret sharing against affine tampering. arXiv preprint arXiv:1902.06195 (2019)

47.

Lu, C.-J.: Hyper-encryption against space-bounded adversaries from on-line strong extractors. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 257–271. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_17CrossRef

48.

Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43–52 (1996). https://doi.org/10.1006/jcss.1996.0004MathSciNetMATHCrossRef

49.

Rabin, M.O.: Probabilistic algorithms in finite fields. SIAM J. Comput. 9(2), 273–280 (1980). https://doi.org/10.1137/0209024MathSciNetMATHCrossRef

50.

Rao, A.: An exposition of Bourgain’s 2-source extractor. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 14 (2007)

51.

Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. 8(2), 300–304 (1960)MathSciNetMATHCrossRef

52.

Robin, G.: Permanence de relations de récurrence dans certains développements asymptotiques. Pub. Inst. Math. Beograd 43(57), 17–25 (1988)MATH

53.

Rosser, B.: The n-th prime is greater than nlogn. Proc. Lond. Math. Soc. 2(1), 21–44 (1939)MathSciNetMATHCrossRef

54.

Schwartz, J.T.: Probabilistic algorithms for verification of polynomial identities. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 200–215. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09519-5_72CrossRef

55.

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

56.

Singleton, R.C.: Maximum distance q-nary codes. IEEE Trans. Inf. Theory 10(2), 116–118 (1964). https://doi.org/10.1109/TIT.1964.1053661MathSciNetMATHCrossRef

57.

Ta-Shma, A., Zuckerman, D.: Extractor codes. IEEE Trans. Inf. Theory 50(12), 3015–3025 (2004)MathSciNetMATHCrossRef

58.

Weil, A.: On some exponential sums. Proc. Natl. Acad. Sci. U.S.A. 34(5), 204 (1948)MathSciNetMATHCrossRef

59.

Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216–226. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09519-5_73CrossRef

60.

Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 681–690 (2006)

Titel: Non-malleability Against Polynomial Tampering
verfasst von: Marshall Ball
Eshan Chattopadhyay
Jyun-Jie Liao
Tal Malkin
Li-Yang Tan
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner