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 notion such as multiple authentication codes (multiple A-codes), almost strongly universal hash families, almost k-resilient functions, almost correlation-immune functions, indistinguishable random variables and k-wise decorrelation bias of block ciphers.