nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Non-Malleable Codes Against Bounded Polynomial Time Tampering

verfasst von : Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

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 construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) \(\mathbf {E}\) is hard for \(\mathbf {NP}\) circuits of some exponential \(2^{\beta n}\) (\(\beta >0\)) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) \(\mathbf {P}\)-certificates with sub-exponential soundness exist.

While it is impossible to construct NMC secure against arbitrary polynomial-time tampering (Dziembowski, Pietrzak, Wichs, ICS ’10), the existence of NMC secure against \(O(n^c)\)-time tampering functions (for any fixed c), was shown (Cheraghchi and Guruswami, ITCS ’14) via a probabilistic construction. An explicit construction was given (Faust, Mukherjee, Venturi, Wichs, Eurocrypt ’14) assuming an untamperable CRS with length longer than the runtime of the tampering function. In this work, we show that under computational assumptions, we can bypass these limitations. Specifically, under the assumptions listed above, we obtain non-malleable codes in the plain model against \(O(n^c)\)-time tampering functions (for any fixed c), with codeword length independent of the tampering time bound.

Our new construction of NMC draws a connection with non-interactive non-malleable commitments. In fact, we show that in the NMC setting, it suffices to have a much weaker notion called quasi non-malleable commitments—these are non-interactive, non-malleable commitments in the plain model, in which the adversary runs in \(O(n^c)\)-time, whereas the honest parties may run in longer (polynomial) time. We then construct a 4-tag quasi non-malleable commitment from any sub-exponential OWF and the assumption that \(\mathbf {E}\) is hard for some exponential size \(\mathbf {NP}\)-circuits, and use tag amplification techniques to support an exponential number of tags.

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 Tight Time-Memory Trade-Offs for Symmetric Encryption

Nächstes Kapitel Continuous Non-Malleable Codes in the 8-Split-State Model

As we will see, in our setting of non-malleable codes against polynomially-bounded adversaries, our construction requires such derandomization assumptions in any case and so only standard one-way function is required in addition. However, for simplicity we will assume injective one-way function in the remainder of the exposition in this section.

For this exposition, we assume for simplicity that \(\psi '\) can be computed in deterministic time \(2^{\text{ input } \text{ length }}\) and that the injective OWF has linear circuit size. Recall that we do not require injective OWF and that any statistically binding, non-interactive commitment scheme is sufficient, but that for simplicity we assuming injective OWF in this exposition.

Applebaum, B., Artemenko, S., Shaltiel, R., Yang, G.: Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Comput. Complex. 25(2), 349–418 (2016). https://doi.org/10.1007/s00037-016-0128-9MathSciNetCrossRefMATH

Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unlessexptime has publishable proofs. Comput. Complex. 3(4), 307–318 (1993). https://doi.org/10.1007/BF01275486CrossRefMATH

Ball, M., Dachman-Soled, D., Guo, S., Malkin, T., Tan, L.Y.: Non-malleable codes for small-depth circuits. FOCS IEEE Computer Society Press, October 2018 (to appear). https://eprint.iacr.org/2018/207

Ball, M., Dachman-Soled, D., Kulkarni, M., Lin, H., Malkin, T.: Non-malleablecodes against bounded polynomial time tampering. Cryptology ePrint Archive, Report 2018/1015 (2018). https://eprint.iacr.org/2018/1015

Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codesfor bounded depth, bounded fan-in circuits. In: Fischlin and Coron [30], pp. 881–908CrossRef

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

Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: 43rd FOCS, pp. 345–355. IEEE Computer Society Press, November 2002

Barak, B., Ong, S.J., Vadhan, S.: Derandomization in cryptography. SIAM J. Comput. 37(2), 380–400 (2007). https://doi.org/10.1137/050641958MathSciNetCrossRefMATH

Barak, B., Pass, R.: On the possibility of one-message weak zero-knowledge. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 121–132. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_7CrossRefMATH

10.

Bitansky, N., Lin, H.: One-message zero knowledge and non-malleable commitments. Cryptology ePrint Archive, Report 2018/613 (2018). https://eprint.iacr.org/2018/613

11.

Chandran, N., Goyal, V., Mukherjee, P., Pandey, O., Upadhyay, J.: Block-wise non-malleable codes. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) ICALP 2016. LIPIcs, vol. 55, pp. 31:1–31:14. Schloss Dagstuhl (2016)

12.

Chattopadhyay, E., Goyal, V., Li, X.: Non-malleable extractors and codes, withtheir many tampered extensions. In: Wichs and Mansour [69], pp. 285–298

13.

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 ACM STOC, pp. 1171–1184. ACM Press, June 2017

14.

Cheraghchi, M., Guruswami, V.: Capacity of non-malleable codes. In: Naor, M. (ed.) ITCS 2014, pp. 155–168. ACM, January 2014

15.

Chung, K.M., Lin, H., Pass, R.: Constant-round concurrent zero knowledge from P-certificates. In: FOCS 2013 [32] , pp. 50–59

16.

Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Concurrent non-malleable commitments (and more) in 3 rounds. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 270–299. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_10CrossRefMATH

17.

Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Four-round concurrentnon-malleable commitments from one-way functions. In: Katz and Shacham [44], pp. 127–157CrossRef

18.

Coron, J.S., Holenstein, T., Künzler, R., Patarin, J., Seurin, Y., Tessaro, S.: How to build an ideal cipher: the indifferentiability of the Feistel construction. J. Cryptol. 29(1), 61–114 (2016)MathSciNetCrossRef

19.

Dachman-Soled, D., Katz, J., Thiruvengadam, A.: 10-round Feistel isindifferentiable from an ideal cipher. In: Fischlin and Coron [30], pp. 649–678CrossRef

20.

Dai, Y., Steinberger, J.: Indifferentiability of 8-round feistel networks. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 95–120. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_4CrossRef

21.

Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM Rev. 45(4), 727–784 (2003)MathSciNetCrossRef

22.

Drucker, A.: Nondeterministic direct product reductions and the success probability of SAT solvers. In: FOCS 2013 [32], pp. 736–745

23.

Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: Kleinberg, J.M. (ed.) 38th ACM STOC, pp. 711–720. ACM Press, May 2006

24.

Dwork, C., Naor, M.: Zaps and their applications. In: FOCS 2000 [31], pp. 283–293

25.

Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Yao, A.C.C. (ed.) ICS 2010, pp. 434–452. Tsinghua University Press, January 2010

26.

Faust, S., Hostáková, K., Mukherjee, P., Venturi, D.: Non-malleablecodes for space-bounded tampering. In: Katz and Shacham [44], pp. 95–126CrossRef

27.

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_7CrossRef

28.

Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)MathSciNetCrossRef

29.

Feige, U., Lund, C.: On the hardness of computing the permanent of random matrices. Comput. Complex. 6(2), 101–132 (1997)MathSciNetCrossRef

30.

Fischlin, M., Coron, J.-S. (eds.): EUROCRYPT 2016, Part II. LNCS, vol. 9666. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5CrossRefMATH

31.

41st FOCS. IEEE Computer Society Press, November 2000

32.

54th FOCS. IEEE Computer Society Press, October 2013

33.

58th FOCS. IEEE Computer Society Press (2017)

34.

Fortnow, L., Vadhan, S.P. (eds.): 43rd ACM STOC. ACM Press, June 2011

35.

Goldreich, O., Wigderson, A.: Derandomization that is rarely wrong from short advice that is typically good. In: Rolim, J.D.P., Vadhan, S. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 209–223. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45726-7_17CrossRef

36.

Goyal, V.: Constant round non-malleable protocols using one way functions. In: Fortnow and Vadhan [34], pp. 695–704

37.

Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: Wichs and Mansour [69], pp. 1128–1141

38.

Goyal, V., Richelson, S., Rosen, A., Vald, M.: An algebraic approach to non-malleability. In: 55th FOCS, pp. 41–50. IEEE Computer Society Press, October 2014

39.

Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_6CrossRef

40.

Gutfreund, D., Shaltiel, R., Ta-Shma, A.: Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Comput. Complex. 12(3–4), 85–130 (2003)MathSciNetMATH

41.

Harnik, D., Naor, M.: On the compressibility of \(\cal{NP}\) instances and cryptographic applications. SIAM J. Comput. 39(5), 1667–1713 (2010)MathSciNetCrossRef

42.

Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRef

43.

Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In: 29th ACM STOC, pp. 220–229. ACM Press, May 1997

44.

Katz, J., Shacham, H. (eds.): CRYPTO 2017, Part II. LNCS, vol. 10402. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0CrossRefMATH

45.

Khurana, D.: Round optimal concurrent non-malleability from polynomial hardness. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part II. LNCS, vol. 10678, pp. 139–171. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_5CrossRef

46.

Khurana, D., Sahai, A.: How to achieve non-malleability in one or two rounds. In: FOCS 2017 [33], pp. 564–575

47.

Klivans, A.R., Van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput. 31(5), 1501–1526 (2002)MathSciNetCrossRef

48.

Lin, H., Pass, R.: Non-malleability amplification. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 189–198. ACM Press, May/June 2009

49.

Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: Fortnow and Vadhan [34], pp. 705–714

50.

Lin, H., Pass, R., Soni, P.: Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles. In: FOCS 2017 [33], pp. 576–587

51.

Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 571–588. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_31CrossRef

52.

Lindell, Y.: A simpler construction of CCA2-secure public-key encryption under general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 241–254. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_15CrossRef

53.

Lipton, R.J.: New directions in testing. In: Feigenbaum, J., Merritt, M. (eds.) Distributed Computing and Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, 4–6 October 1989, pp. 191–202 (1989)

54.

Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)MathSciNetCrossRef

55.

Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. Comput. Complex. 14(3), 256–279 (2005)MathSciNetCrossRef

56.

Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: 22nd ACM STOC, pp. 427–437. ACM Press, May 1990

57.

Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149–167 (1994). https://doi.org/10.1016/S0022-0000(05)80043-1MathSciNetCrossRefMATH

58.

Ostrovsky, R., Persiano, G., Venturi, D., Visconti, I.: Continuously non-malleable codes in the split-state model from minimal assumptions. Cryptology ePrint Archive, Report 2018/542 (2018). https://eprint.iacr.org/2018/542

59.

Pass, R., Rosen, A.: Concurrent non-malleable commitments. In: 46th FOCS, pp. 563–572. IEEE Computer Society Press, October 2005

60.

Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 533–542. ACM Press, May 2005

61.

Pass, R., Wee, H.: Constant-round non-malleable commitments from sub-exponential one-way functions. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 638–655. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_32CrossRef

62.

Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto (1996)

63.

Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th FOCS, pp. 543–553. IEEE Computer Society Press, October 1999

64.

Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM (JACM) 52(2), 172–216 (2005)MathSciNetCrossRef

65.

Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. Comput. Complex. 15(4), 298–341 (2006)MathSciNetCrossRef

66.

Shaltiel, R., Umans, C.: Low-end uniform hardness versus randomness tradeoffs for AM. SIAM J. Comput. 39(3), 1006–1037 (2009)MathSciNetCrossRef

67.

Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR Lemma. J. Comput. Syst. Sci. 62(2), 236–266 (2001). http://www.sciencedirect.com/science/article/pii/S0022000000917306MathSciNetCrossRef

68.

Trevisan, L., Vadhan, S.P.: Extracting randomness from samplable distributions. In: FOCS 2000 [31], pp. 32–42

69.

Wichs, D., Mansour, Y. (eds.): 48th ACM STOC. ACM Press, June 2016

70.

Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November 1982, pp. 80–91. IEEE Computer Society (1982). https://doi.org/10.1109/SFCS.1982.45

Titel: Non-Malleable Codes Against Bounded Polynomial Time Tampering
verfasst von: Marshall Ball
Dana Dachman-Soled
Mukul Kulkarni
Huijia Lin
Tal Malkin
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17652-5

Electronic ISBN: 978-3-030-17653-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17653-2_17

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