2
$\begingroup$

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.$ \ ''$

Improve this question
$\endgroup$
5
  • $\begingroup$ Welcome to crypto.SE. Looks like a hard one to me, even if we assume an out-of-band digital signature of the data. $\endgroup$ – fgrieu♦ Apr 6 '20 at 14:07
  • $\begingroup$ 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. $\endgroup$ – Maeher Apr 6 '20 at 14:35
  • $\begingroup$ @Maeher-How can we do then? I mean from where do I start? $\endgroup$ – zeus Apr 6 '20 at 16:21
  • $\begingroup$ @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. $\endgroup$ – fgrieu♦ Apr 6 '20 at 17:18
  • $\begingroup$ What's suggested in the second comment is detailed there $\endgroup$ – fgrieu♦ Apr 6 '20 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.