We consider two leakage models. The first model, called \emph{linear leakage}, requires the adversary's uncertainty (entropy) about the message (or encoding randomness) to be a constant fraction of its length. This model can be seen as an extension of the original AMD study by Cramer et al. \cite{CDFPW08} to when some leakage to the adversary is allowed. We study \emph{randomized strong} and \emph{deterministic weak} constructions of linear (L)LR-AMD codes. We derive lower and upper bounds on the redundancy of these codes and show that known optimal (in rate) AMD code constructions can serve as optimal LLR-AMD codes. In the second model, called \emph{block leakage}, the message consists of a sequence of blocks and at least one block remains with uncertainty that is a constant fraction of the block length. We focus on deterministic block (B)LR-AMD codes. We observe that designing optimal such codes is more challenging: LLR-AMD constructions cannot function optimally under block leakage. We thus introduce a new optimal BLR-AMD code construction and prove its security in the model.
We show an application of LR-AMD codes to tampering detection over wiretap channels. We next show how to compose our BLR-AMD construction, with a few other keyless primitives, to provide both integrity and confidentiality in transmission of messages/keys over such channels. This is the best known solution in terms of randomness and code redundancy. We discuss our results and suggest directions for future research.
Category / Keywords: foundations / Algebraic manipulation detection, wiretap channel, leakage resilient Original Publication (with minor differences): ICITS 2013 Date: received 4 Oct 2013, last revised 4 Oct 2013 Contact author: hahmadi at ucalgary ca Available format(s): PDF | BibTeX Citation Version: 20131005:134510 (All versions of this report) Short URL: ia.cr/2013/637 Discussion forum: Show discussion | Start new discussion