**Affine-evasive Sets Modulo a Prime**

*Divesh Aggarwal*

**Abstract: **In this work, we describe a simple and efficient construction of a large subset S of F_p, where p is a prime, such that the set A(S) for any non-identity affine map A over F_p has small intersection with S.

Such sets, called affine-evasive sets, were defined and constructed in~\cite{ADL14} as the central step in the construction of non-malleable codes against affine tampering over F_p, 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~\cite{ADL14}. It improves the rate of non-malleable codes against affine tampering over F_p 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.

**Category / Keywords: **

**Date: **received 10 May 2014, last revised 16 Oct 2014

**Contact author: **divesha at cs nyu edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20141017:031115 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]