Affine-evasive Sets Modulo a Prime.
Divesh Aggarwal · 2014
In this work, we describe a simple and efficient construction of a large subset S of Fp, where p is a prime, such that the set A(S) for any non-identity affine map A over Fp has small intersection with S. Such sets, called affine-evasive sets, were defined and constructed in [ADL14] as the central step in the construction of non-malleable codes against affine tampering over Fp, for a prime p. This was then used to obtain efficient non-malleable codes against split-state tampering. Our result resolves one of the two main open questions in [ADL14]. It improves the rate of non-malleable codes against affine tampering over Fp from log log p to a constant, and consequently the rate for non-malleable codes against split-state tampering for n-bit messages is improved from n 6 log 7 n to n 6.