SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions

International audienceIn a selective-opening chosen ciphertext (SO-CCA) attack on an encryption scheme, an adversary A has access to a decryption oracle, and after getting a number of ciphertexts, can then adaptively corrupt a subset of them, obtaining the plaintexts and corresponding encryption randomness. SO-CCA security requires the privacy of the remaining plaintexts being well protected. There are two flavors of SO-CCA definition: the weaker indistinguishability-based (IND) and the stronger simulation-based (SIM) ones. In this paper, we study SO-CCA secure PKE constructions from all-but-many lossy trapdoor functions (ABM-LTFs) in pairing-friendly prime order groups. Concretely, we construct two ABM-LTFs with O(n/ log λ) size tags for n bits inputs and security parameter λ, which lead to IND-SO-CCA secure PKEs with ciphertext size O(n/ log λ) to encrypt n bits messages. In addition, our second ABM-LTF enjoys tight security, so as the resulting PKE. by equipping a lattice trapdoor for opening randomness, we show our ABM-LTFs are SIM-SO-CCA compatible