**Simple construction of epsilon-biased distribution**

*Long Hoang Nguyen and Andrew William Roscoe*

**Abstract: **Epsilon-biased distribution has many applications in practice, including universal hashing computation. In this paper we will improve an existing epsilon-biased distribution construction due to Alon et al. that requires to uniformly and efficiently sample irreducible polynomials of a large degree, e.g. between 80 and 160. To remove the need for such a sampling which can be computationally expensive, we will replace the irreducible polynomials by random monic polynomials of higher degree, i.e. every degree r monic polynomial whether irreducible or reducible is selected with the same probability 2^{-r}. To analyse the security of the scheme, we need to
find the maximum number of degree r polynomials that divide a degree n polynomial where n > r.

**Category / Keywords: **foundations /

**Date: **received 30 Jul 2012

**Contact author: **Long Nguyen at cs ox ac uk

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

**Version: **20120805:142631 (All versions of this report)

**Short URL: **ia.cr/2012/429

[ Cryptology ePrint archive ]