International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Security of Chaffing and Winnowing

Authors:
Mihir Bellare
Alexandra Boldyreva
Download:
URL: http://eprint.iacr.org/2000/010
Search ePrint
Search Google
Abstract: This paper takes a closer look at Rivest's chaffing-and-winnowing paradigm for data privacy. We begin with a \textit{definition} which enables one to determine clearly whether a given scheme qualifies as ``chaffing-and-winnowing.'' We then analyze Rivest's schemes to see what quality of data privacy they provide. His simplest scheme is easily proven secure but is ineffient. The security of his more efficient scheme ---based on all-or-nothing transforms (AONTs)--- is however more problematic. It can be attacked under Rivest's definition of security of an AONT, and even under stronger notions does not appear provable. We show however that by using a OAEP as the AONT one can prove security. We also present a different scheme, still using AONTs, that is equally efficient and easily proven secure even under the original weak notion of security of AONTs.
BibTeX
@misc{eprint-2000-11354,
  title={The Security of Chaffing and Winnowing},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Message authentication, symmetric},
  url={http://eprint.iacr.org/2000/010},
  note={ mihir@cs.ucsd.edu 11053 received 6 Apr 2000},
  author={Mihir Bellare and Alexandra Boldyreva},
  year=2000
}