Indifferentiability Separations in Ideal Public Key Encryption: Explicit vs. Implicit Rejection
摘要
Ideal public key encryption (PKE) characterizes the maximum security properties of PKE. Currently, two versions exist: in the explicit version, the decryption algorithm returns a rejection symbol for an invalid ciphertext, whereas in the implicit version, it returns a random string. While the implicit version can imply the explicit version, the reverse implication relationship remains unresolved. We provide a negative answer to this question. Our solution is based on the observation that the difference between the determinism of the explicit version and the randomness of the implicit version is closely related to the security of another fundamental cryptographic primitive, oblivious transfer (OT). Specifically, randomness is crucial for guaranteeing the confidentiality of secrets in OT protocols, whereas determinism may lead to secret leakage. This difference results in varying performances of the explicit and implicit versions in constructing OT. This separation conclusion suggests that the determinism in the explicit rejection of invalid ciphertexts is a property that cannot be masked by transformations. Furthermore, we conjecture, and subsequently demonstrate, a similar separation conclusion for ideal PKE with implicit and explicit rejection of invalid public keys. Finally, we extend our method of using OT as a bridge to prove separations between ideal PKE and ideal identity-based encryption (IBE).