# Using digital signature to reduce storage requirement

Below question is a part of my assignment and I was completely clueless about where to start from. So, I am posting it here for the purpose of getting hints/resources to help me get started.

$$\ ''$$To store $$k$$ blocks of data/information (say each block is of $$b$$ bits) in a fault-tolerant way, you may encode the $$k$$ blocks into $$n$$ blocks (using some error-correction code) such that if any $$e$$ of the $$n$$ blocks are corrupted, it is still possible to retrieve the original $$k$$ blocks of information. Specifically (for large enough $$b$$), coding theory suggests that this is possible if and only if $$n \geq (k + 2e)$$. However, show that using digital signatures, it is possible to achieve the above fault-tolerant storage even when $$(k + e) \leq n \lt (k + 2e)$$, assuming a PPTM-adversary(Probabilistic polynomial time) and a negligible probability of error is permitted.$$\ ''$$

• Welcome to crypto.SE. Looks like a hard one to me, even if we assume an out-of-band digital signature of the data. – fgrieu Apr 6 '20 at 14:07
• There doesn't seem to be any size restriction on the $n$ blocks post encoding, which would make this trivial. So there are probably some unstated conditions here. – Maeher Apr 6 '20 at 14:35
• @Maeher-How can we do then? I mean from where do I start? – zeus Apr 6 '20 at 16:21
• @Maeher: I read the problem as requiring that each of the $n$ blocks is $b$-bit or negligibly above that. And while I do see how we could sneak a digital signature into that negligible, and how it could act as helper to select among multiple candidate decodings, I still fail to explicitly construct a code that matches the goal asked, even if I assume the information-theoretic code stated by the question. Or maybe the question assumes that the PPTM-adversary can break the signature? In other words, I do not get it. – fgrieu Apr 6 '20 at 17:18
• What's suggested in the second comment is detailed there – fgrieu Apr 6 '20 at 17:31