Paper 2014/116

Optimal Algebraic Manipulation Detection Codes

Ronald Cramer and Carles Padrö and Chaoping Xing

Abstract

Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as {\em keyless} combinatorial authentication codes that provide security in the presence of an {\em oblivious}, {\em algebraic} attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive constant error probability $\epsilon$ in combination with unbounded cardinality $M$ of the message space. Adapting a known bound to this regime, it follows that the binary length $\rho$ of the tag satisfies $\rho\geq \log \log M + \Omega_{\epsilon}(1)$. We shall call AMD codes meeting this lower bound {\em optimal}. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor~2 {\em off} from being optimal. Bridging the gap to optimality efficiently turns out to be surprisingly nontrivial. Owing to our refinement of the mathematical perspective on AMD codes, which focuses on symmetries of codes, we propose novel constructive principles. This leads to an explicit construction of almost-optimal AMD codes and to an efficient randomized construction of optimal AMD codes, as we show in our main results. In all our results, the error probability $\epsilon$ can be chosen as an arbitrarily small positive real number.