All-but-one dual projective hashing and its applications

Recently, Wee (EUROCRYPT'12) introduced the notion of dual projective hashing as an extension of the Cramer-Shoup projective hashing, with a simple construction of lossy trapdoor functions, and a simple construction of deterministic encryption schemes which is chosen-plaintext-attack secure with respect to hard-to-invert auxiliary input. In this work, we further extend it to the all-but-one setting by introducing the notion of all-but-one dual projective hashing. We provide a simple construction of all-but-one lossy trapdoor functions. Our construction encompasses many known constructions of all-but-one lossy trapdoor functions, as presented by Peikert and Waters (STOC'08), and Freeman et al. (JoC'13). Particularly, we present a new construction of all-but-one lossy trapdoor functions based on the DLIN assumption, which can be viewed as an extension of Freeman et al.'s DDH-based construction to the DLIN setting, and therefore solves an open problem left by Freeman et al. We also provide a general construction of chosen-ciphertext- attack (CCA) secure deterministic encryption schemes in the standard model, under an additional assumption about the projective map. This extends the general approach of designing CCA secure deterministic encryption schemes by Boldyreva, Fehr and O'Neill (CRYPTO'08). In addition, we present a new construction of CCA secure deterministic encryption schemes based on the DLIN assumption.