ℱ-Related-Key Attacks (RKAs) allow an adversary to tamper the key k stored in a cryptographic device by specifying related-key deriving (RKD) functions f in ℱ and subsequently learn the outcome of the device under related keys f(k)⁠. In this paper, we present RKA secure public-key encryption (PKE) and symmetric encryption (SE) schemes admitting a tight security reduction to the standard s-Linear assumption. The security loss depends only on the security parameter and is independent of the number of tampering queries made by the adversary. Our encryption schemes are resilient to RKAs w.r.t. the set of restricted affine functions ℱraff⁠, of which the set of linear functions ℱlin is a subset. In particular, • Our encryption schemes serve as the first ones possessing tight RKA security for a non-trivial RKD function class ℱ under standard assumptions. • Moreover, our encryption schemes enjoy tight super-strong RKA securities, which are the strongest ones among the existing RKA security notions.

In a selective-opening, chosen-ciphertext attack (SO-CCA) against a public key encryption scheme (PKE scheme), a probabilistic polynomial time (PPT) adversary obtains a vector of challenge ciphertexts, has access to a decryption oracle, adaptively selects to open some of the challenge ciphertexts and sees the corresponding messages together with the random coins. The simulation-based, selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA security) protects the security of the unopened messages in a semantic way, i.e. it requires that the output of the adversary can be simulated by a simulator who sees only the opened messages. In particular, all information that the adversary can get from the unopened messages can also be simulated from the opened messages alone by the simulator. All security proofs of the available PKEs achieving SIM-SO-CCA security are not tight, and the security loss depends either on the number of challenge ciphertexts or on the number of decryption queries. In this work, we present the first PKE scheme which achieves SIM-SO-CCA security with a tight reduction to standard assumptions. This partially solves the open problem proposed by Hofheinz in EuroCrypt 2012.

KDM [F] -CCA security of public-key encryption (PKE) ensures the privacy of key-dependent messages f(sk) which are closely related to the secret key sk , where f∈F , even if the adversary is allowed to make decryption queries. In this paper, we study the design of KDM-CCA secure PKE. To this end, we develop a new primitive named Auxiliary-Input Authenticated Encryption (AIAE). For AIAE, we introduce two related-key attack (RKA) security notions, including IND-RKA and weak-INT-RKA. We present a generic construction of AIAE from tag-based hash proof system (HPS) and one-time secure authenticated encryption (AE) and give an instantiation of AIAE under the Decisional Diffie-Hellman (DDH) assumption. Using AIAE as an essential building block, we give two constructions of efficient KDM-CCA secure PKE based on the DDH and the Decisional Composite Residuosity (DCR) assumptions. Specifically, (i) our first PKE construction is the first one achieving KDM [Faff] -CCA security for the set of affine functions and compactness of ciphertexts simultaneously. (ii) Our second PKE construction is the first one achieving KDM [Fpolyd] -CCA security for the set of polynomial functions and almost compactness of ciphertexts simultaneously. Our PKE constructions are very efficient; in particular, they are pairing-free and NIZK-free.