IACR News item: 05 October 2013
Hadi Ahmadi, Reihaneh Safavi-Naini
ePrint ReportWe 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.
Additional news items may be found on the IACR news page.