Paper 2018/058

Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters

Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski

Abstract

Algebraic Manipulation Detection (AMD) codes [CDF+08] 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 r and the code rate k for leakage-resilient AMD codes. In particular we prove that 2r + k < 1 and for the weak case (security is averaged over a uniformly random message) r + k < 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 r and k. This shows that above bounds and constructions are in-fact optimal. In the last section we show that if a leakage function is computationally bounded (we use Ideal Cipher Model) then it is possible to break these bounds.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Leakage-resilient AMDAlgebraic Manipulation DetectionLeakage resilient codes
Contact author(s)
tkazana @ mimuw edu pl
History
2021-03-23: revised
2018-01-16: received
See all versions
Short URL
https://ia.cr/2018/058
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/058,
      author = {Divesh Aggarwal and Tomasz Kazana and Maciej Obremski},
      title = {Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2018/058},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/058}},
      url = {https://eprint.iacr.org/2018/058}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.