Algebraic manipulation detection codes via highly nonlinear functions
- PDF / 422,141 Bytes
- 17 Pages / 439.642 x 666.49 pts Page_size
- 59 Downloads / 181 Views
Algebraic manipulation detection codes via highly nonlinear functions Minfeng Shao1
· Ying Miao1
Received: 20 February 2020 / Accepted: 13 August 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study the relationship between algebraic manipulation detection (AMD) codes and highly nonlinear functions. As applications, on one hand, a generic construction for systematic AMD codes is introduced based on highly nonlinear functions. Systematic AMD codes with new parameters can be generated from known highly nonlinear functions. Especially, several infinite classes of optimal systematic AMD codes, some with asymptotically optimal tag size, can be constructed. On the other hand, systematic AMD codes are used to construct highly nonlinear functions. The known construction by Cramer et al. (2008) for systematic AMD codes turns out to be based on a special kind of functions with high nonlinearity. Keywords Algebraic manipulation detection code · Highly nonlinear function · Nonlinearity · Partial nonlinearity Mathematics Subject Classification (2010) Primary 94A62 · Secondary 11T71
1 Introduction Algebraic manipulation detection (AMD) codes were first introduced by Cramer et al. [13] to convert linear secret sharing schemes into robust secret sharing schemes and build nearly optimal robust fuzzy extractors. Generally speaking, an AMD code consists of a probabilistic encoding map E and a determined decoding function Dec, where E encodes a plaintext s into a random ciphertext g ∈R Gs such that any tampering will be detected, except with a small constant error probability. For AMD codes, we consider the attack model such that
This research is supported by JSPS Grant-in-Aid for Scientific Research (B) under Grant No. 18H01133. Minfeng Shao
[email protected] Ying Miao [email protected] 1
Graduate School of Systems and Information Engineering, University of Tsukuba, Tennodai 1-1-1, Tsukuba, 305-8573, Japan
Cryptography and Communications
an adversary may manipulate the valid message g = E(s) by adding some offset of his choice. The attack model is classified into two sub-models by distinguishing two different settings: the adversary has full knowledge of the source (the strong attack model) and the adversary has no knowledge about the source (the weak attack model). The main objective for an AMD code is, for a given tag size, to minimize the success probability of an adversary such that g + ∈ Gs , i.e., Dec(g ) = s = Dec(g) = s. Here the tag size denotes the difference between the length of the plaintext and its corresponding ciphertext. Upon to now, there are mainly two kinds of known constructions for AMD codes. One is via algebraic methods. In [13], Cramer et al. proposed a construction of AMD codes with nearly optimal tag size based on polynomial evaluations. Later in [25] and [15], linear codes such as Reed-Muller codes and BCH codes were included to generate AMD codes with small tag size. The other one is via combinatorial method, which gener
Data Loading...
