Leakage-Resilient Algebraic Manipulation Detection Codes with Optimal Parameters

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Divesh Aggarwal, National University of Singapore
  • ,
  • Tomasz Kazana, University of Warsaw
  • ,
  • Maciej Obremski

Algebraic Manipulation Detection (AMD) codes [CDFPW08] are keyless message authentication codes that protect messages against additive tampering by the adversary assuming that the adversary cannot 'see' the codeword. For certain applications, it is unreasonable to assume that the adversary computes the added offset without any knowledge of the codeword c. Recently, Ahmadi and Safavi-Naini [AS13], and then Lin, Safavi-Naini, and Wang [LSW16] gave a construction of leakage-resilient AMD codes where the adversary has some partial information about the codeword before choosing added offset, and the scheme is secure even conditioned on this partial information. In this paper we show the bounds on the leakage rate rho and the code rate K for leakage-resilient AMD codes. In particular we prove that 2rho+kappa < 1 and for the weak case (security is averaged over a uniformly random message) rho+kappa < 1. These bounds hold even if adversary is polynomial-time bounded, as long as we allow leakage function to be arbitrary. We present the constructions of AMD codes that (asymptotically) fulfill above bounds for almost full range of parameters rho and kappa. This shows that above bounds and constructions are in-fact optimal. In the full version of the paper we also show that if a leakage function is computationally bounded (we use Ideal Cipher Model) then it is possible to break these bounds.

Original languageEnglish
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
Number of pages5
Publication year15 Aug 2018
Article number8437762
ISBN (print)9781538647806
Publication statusPublished - 15 Aug 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: 17 Jun 201822 Jun 2018


Conference2018 IEEE International Symposium on Information Theory, ISIT 2018
LandUnited States
SponsorHuawei, IEEE, IEEE InformationTheory Society, National Science Foundation, Qualcomm

See relations at Aarhus University Citationformats

ID: 143073514