## CryptoDB

### Paper: Continuous Space-Bounded Non-malleable Codes from Stronger Proofs-of-Space

Authors: Binyi Chen Yilei Chen Kristina Hostáková Pratyay Mukherjee DOI: 10.1007/978-3-030-26948-7_17 Search ePrint Search Google 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.
##### BibTeX
@article{crypto-2019-29870,
title={Continuous Space-Bounded Non-malleable Codes from Stronger Proofs-of-Space},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11692},
pages={467-495},
doi={10.1007/978-3-030-26948-7_17},
author={Binyi Chen and Yilei Chen and Kristina Hostáková and Pratyay Mukherjee},
year=2019
}