Lower Bounds for Key Length of fc-wise Almost Independent Permutations and Certain Symmetric-Key Encryption Schemes

摘要

The fc-wise almost independent permutations are one of important primitives for cryptographic schemes and combinatorial constructions. Kaplan, Naor, and Reingold showed a general construction for fc-wise almost independent permutations, and Kawachi, Takebe, and Tanaka provided symmetric-key encryption schemes that achieve multi-message approximate secrecy and multi-ciphertext approximate non-malleability based on Kaplan et al.'s construction. In this paper, we show lower bounds of key length for these constructions. In particular, they are nearly optimal for fc-wise almost independent permutations and multi-message approximate secrecy if the approximation parameter is a constant.