The security of chaffing and winnowing

Authors: M. Bellare and A. Boldyreva

Abstract: This paper takes a closer look at Rivest's chaffing-and-winnowing paradigm for data privacy. We begin with a definition which enables one to determine 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 bit-by-bit scheme is easily proven to meet a standard notion of privacy under chosen-plaintext attack, but is inefficient. His more efficient scheme ---based on all-or-nothing transforms (AONTs)--- can be attacked under Rivest's definition of security of an AONT. However we show that by using OAEP as the AONT one can prove security, and also present a different scheme, still using AONTs, that is equally efficient and easily proven secure even under a relatively weak notion of security of AONTs.

Ref: Extended abstract in Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed, Springer-Verlag, 2000. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).