Cryptology ePrint Archive: Report 2000/010
The Security of Chaffing and Winnowing
Mihir Bellare and Alexandra Boldyreva
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.
Category / Keywords: secret-key cryptography / Message authentication, symmetric
Date: received 6 Apr 2000
Contact author: mihir at cs ucsd edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20000406:222502 (All versions of this report)
Short URL: ia.cr/2000/010
[ Cryptology ePrint archive ]