Paper 2012/429

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
Long Nguyen @ cs ox ac uk
History
2012-08-05: received
Short URL
https://ia.cr/2012/429
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/429,
      author = {Long Hoang Nguyen and Andrew William Roscoe},
      title = {Simple construction of epsilon-biased distribution},
      howpublished = {Cryptology ePrint Archive, Paper 2012/429},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/429}},
      url = {https://eprint.iacr.org/2012/429}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.