Affine-evasive Sets Modulo a Prime

Divesh Aggarwal

Paper 2014/328

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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Contact author(s): divesha @ cs nyu edu
History: 2014-10-17: last of 2 revisions; 2014-05-13: received; See all versions
Short URL: https://ia.cr/2014/328
License: CC BY

BibTeX

@misc{cryptoeprint:2014/328,
      author = {Divesh Aggarwal},
      title = {Affine-evasive Sets Modulo a Prime},
      howpublished = {Cryptology ePrint Archive, Paper 2014/328},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/328}},
      url = {https://eprint.iacr.org/2014/328}
}