Abstract
Non-malleable codes are encoding schemes that provide protections against various classes of tampering attacks. Recently Faust et al. (CRYPTO 2017) initiated the study of space-bounded non-malleable codes that provide such protections against tampering within small-space devices. They put forward a construction based on any non-interactive proof-of-space (NIPoS). However, the scheme only protects against an a priori bounded number of tampering attacks.
We construct non-malleable codes that are resilient to an unbounded polynomial number of space-bounded tamperings. Towards that we introduce a stronger variant of \(\text {NIPoS}\) called proof-extractable \(\text {NIPoS}\) (\(\text {PExt-NIPoS}\)), and propose two approaches of constructing such a primitive. Using a new proof strategy we show that the generic encoding scheme of Faust et al. achieves unbounded tamper-resilience when instantiated with a \(\text {PExt-NIPoS}\). We show two methods to construct \(\text {PExt-NIPoS}\):
-
1.
The first method uses a special family of “memory-hard” graphs, called challenge-hard graphs (CHG), a notion we introduce here. We instantiate such family of graphs based on an extension of stack of localized expanders (first used by Ren and Devadas in the context of proof-of-space). In addition, we show that the graph construction used as a building block for the proof-of-space by Dziembowski et al. (CRYPTO 2015) satisfies challenge-hardness as well. These two CHG-instantiations lead to continuous space-bounded NMC with different features in the random oracle model.
-
2.
Our second instantiation relies on a new measurable property, called uniqueness of \(\text {NIPoS}\). We show that standard extractability can be upgraded to proof-extractability if the \(\text {NIPoS}\) also has uniqueness. We propose a simple heuristic construction of \(\text {NIPoS}\), that achieves (partial) uniqueness, based on a candidate memory-hard function in the standard model and a publicly verifiable computation with small-space verification. Instantiating the encoding scheme of Faust et al. with this \(\text {NIPoS}\), we obtain a continuous space-bounded NMC that supports the “most practical” parameters, complementing the provably secure but “relatively impractical” CHG-based constructions. Additionally, we revisit the construction of Faust et al. and observe that due to the lack of uniqueness of their \(\text {NIPoS}\), the resulting encoding schemes yield “highly impractical” parameters in the continuous setting.
We conclude the paper with a comparative study of all our non-malleable code constructions with an estimation of concrete parameters.
Work done at VISA Research.
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.
In the rest of the paper whenever we say that an encoding scheme satisfies continuous space-bounded non-malleability or is a \(\text {CSNMC}\), we mean that the encoding scheme is a leaky NMC for space-bounded tampering with \(\ell \propto \log (\theta )\).
- 2.
Note that we made some syntactical change to \(\text {FHMV}\)’s definition of extractability by introducing an explicit hint-producing function. We introduce the length of the hint as a new extractability parameter which must be small for making the definition meaningful. For example, if the leakage function leaks the entire pair \(( id ',\pi _ id ')\), then the definition would be trivially satisfied. Looking ahead, in the proof of \(\text {CSNMC}\) this hint will be used by the NMC simulator as a leakage to simulate the tampering experiment. For more details we refer to Sect. 5.
- 3.
This is without loss of generality, as in the tampering setting \(\mathsf {A}\) is chosen by PPT distinguisher \(\mathsf {D}\) (“big adversary” in our case) who can just hardwires its truly random coin to \(\mathsf {A}\).
- 4.
Note that the terminology “space-bounded” is slightly overloaded as we use it both for an encoding scheme as well as for an algorithm (cf. Definition 1).
- 5.
Recall that for any non-trivial leakage we must have \(\ell \le k - \omega (\log k)\) as otherwise the tampering adversary learns (almost) all information about the input rendering the notion useless.
- 6.
Note that \(\mathsf {B}\) does not make RO queries after outputting the small adversary \(\mathsf {A}\).
- 7.
We require the in-degree of the graph to be a constant, because for graph-labeling in the ROM this captures the essence of the standard model. To see this assume that \(\mathcal {H}\) is implemented by an iteration-based scheme (e.g., Merkle-Damgård extension), and thereby to compute the hash output, it is sufficient to store only a few labels at each iteration step. However, while in the ROM computing a label \(\mathsf {label}(v) :=\mathcal {H}(v, \mathsf {label}(\mathsf {pred}(v)))\) is only possible if the entire labeling \(\mathsf {label}(\mathsf {pred}(v))\) is stored. If the in-degree is high (e.g. super-constant) this distinction would affect the parameters. We refer to Appendix B.3 in [11] for more discussions.
- 8.
For ease of explanation, we assume that |V| and \(|V_{c}|\) are powers of 2.
- 9.
The polynomial factor in \(\varepsilon _\mathsf{p\text {-}ext}\) depends on the number of RO queries made by the adversary. We refer to full version [14] for the exact probability upper bound.
- 10.
Since popular memory-hard functions like SCrypt [39] are not conjectured to provide exponential space-time trade-off, we are unable to use them here.
- 11.
We remark that this corollary is very similar to Corollary 1 of [23] as one may expect. However the parameters here are much better in terms of efficiency.
- 12.
To achieve 128-bits of security, as suggested by [8], we will set \(\lceil \log (p) \rceil \approx 1536\).
- 13.
We stress that this value can be set much higher without affecting the main parameters significantly.
References
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, Part II. LNCS, vol. 9563, pp. 393–417. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_15
Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. In: Shmoys, D.B. (ed.) 46th Annual ACM Symposium on Theory of Computing, pp. 774–783, 31 May–3 June 2014. ACM Press, New York (2014)
Aggarwal, D., Dottling, N., Nielsen, J.B., Obremski, M., Purwanto, E.: Continuous non-malleable codes in the 8-split-state model. Cryptology ePrint Archive, Report 2017/357 (2017). https://eprint.iacr.org/2017/357
Aggarwal, D., Kazana, T., Obremski, M.: Inception makes non-malleable codes stronger. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part II. LNCS, vol. 10678, pp. 319–343. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_10
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, Part I. LNCS, vol. 9215, pp. 538–557. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_26
Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: Scrypt is maximally memory-hard. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 33–62. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_2
Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538–557. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10879-7_31
Guillevic, A., Morain, F.: Discrete logarithms. Book Chapter 9. https://hal.inria.fr/hal-01420485v1/document
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, Part II. LNCS, vol. 9666, pp. 881–908. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_31
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, Part III. LNCS, vol. 10822, pp. 618–650. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_20
Boneh, D., Corrigan-Gibbs, H., Schechter, S.: Balloon hashing: a memory-hard function providing provable protection against sequential attacks. Cryptology ePrint Archive, Report 2016/027 (2016). http://eprint.iacr.org/2016/027
Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of eliminating errors in cryptographic computations. J. Cryptology 14(2), 101–119 (2001)
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. 43rd International Colloquium on Automata, Languages and Programming, LIPIcs, Rome, Italy, 11–15 July 2016, vol. 55, pp. 31:1–31:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)
Chen, B., Chen, Y., Hostáková, K., Mukherjee, P.: Continuous space-bounded non-malleable codes from stronger proofs-of-space. Cryptology ePrint Archive, Report 2019/552 (2019). https://eprint.iacr.org/2019/552
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_19
Dachman-Soled, D., Liu, F.-H., Shi, E., Zhou, H.-S.: Locally decodable and updatable non-malleable codes and their applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 427–450. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_18
Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 585–605. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_29
Dziembowski, S., Kazana, T., Wichs, D.: Key-evolution schemes resilient to space-bounded leakage. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 335–353. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_19
Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125–143. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_9
Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Yao, A.C.-C. (ed.) ICS 2010: 1st Innovations in Computer Science, pp. 434–452. Tsinghua University, Beijing, China, 5–7 January 2010. Tsinghua University Press (2010)
Faonio, A., Nielsen, J.B., Simkin, M., Venturi, D.: Continuously non-malleable codes with split-state refresh. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 121–139. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_7
Faust, S., Hostáková, K., Mukherjee, P., Venturi, D.: Non-malleable codes for space-bounded tampering. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 95–126. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_4
Faust, S., Hostakova, K., Mukherjee, P., Venturi, D.: Non-malleable codes for space-bounded tampering. Cryptology ePrint Archive, Report 2017/530 (2017). http://eprint.iacr.org/2017/530
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
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
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
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12
Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: Wichs, D., Mansour, Y. (eds.) 48th Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 18–21 June 2016, pp. 1128–1141. ACM Press (2016)
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
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
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
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
Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Kleinberg, R.D. (ed.) ITCS 2013: 4th Innovations in Theoretical Computer Science, Berkeley, CA, USA, 9–12 January 2013, pp. 373–388. Association for Computing Machinery (2013)
Mukherjee, P.: Protecting cryptographic memory against tampering attack. Ph.D thesis (2015)
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. LNCS, vol. 10993, pp. 608–639. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_21
Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: 2013 IEEE Symposium on Security and Privacy, Berkeley, CA, USA, 19–22 May 2013, pp. 238–252. IEEE Computer Society Press (2013)
Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theory 10(1), 239–251 (1976)
Ren, L., Devadas, S.: Proof of space from stacked expanders. In: Hirt, M., Smith, A. (eds.) TCC 2016, Part I. LNCS, vol. 9985, pp. 262–285. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_11
Tarsnap. The scrypt key derivation function. https://eprint.iacr.org/2017/1125
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 International Association for Cryptologic Research
About this paper
Cite this paper
Chen, B., Chen, Y., Hostáková, K., Mukherjee, P. (2019). Continuous Space-Bounded Non-malleable Codes from Stronger Proofs-of-Space. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11692. Springer, Cham. https://doi.org/10.1007/978-3-030-26948-7_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-26948-7_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26947-0
Online ISBN: 978-3-030-26948-7
eBook Packages: Computer ScienceComputer Science (R0)
