Almost k-wise independent sample spaces and their cryptologic applications
An almost k-wise independent sample space is a small subset of m bit sequences in which any k bits are “almost independent”. We show that this idea has close relationships with useful cryptologic notions such as multiple authentication codes (multiple A-codes), almost strongly universal hash families and almost k-resilient functions. We use almost k-wise independent sample spaces to construct new