"Logical omniscience" can be defined for these purposes as a form of hypercomputation in which all Turing-computable functions can be computed in constant time. Practically speaking, this means that if you have all of the information that is logically necessary to solve a problem, you can effectively instantly know the answer to that problem.
Things like RSA are clearly out--they depend on certain theoretically-computable functions (like modular factorization) to be difficult to actually compute in practice, and fall apart under much weaker hypercomputation models. Other models, like elliptic-curve cryptography, are more robust than RSA, but still would fail against a logically omniscient oracle with infinite computing power.
Meanwhile, symmetric private key cryptography should still be mostly safe, because there is no algorithm to compute a single unique plaintext-key pair from a given ciphertext. An attacker could decide what they want the plaintext to be, and calculate what they key would've have to have been to get that, but that doesn't actually give you any information about what the original plaintext and key actually were. You can only build up statistical arguments if you have multiple messages that someone had the poor sense to encrypt with the same key, which is no different from how things work in the real world anyway.
So, are there any public-key encryption schemes that would be safe against a logically omniscient oracle? Where breaking them is not merely a matter of not having enough computational power, but for which a deterministic algorithm simply doesn't exist?
Background reason for the question: I have a world in which "demons" can be contacted to enact magic; one of their abilities, which is integral to the kind of magic they can perform, is hypercomputation, such that they can solve problems that are well beyond the technological abilities of the people summoning them (thus providing a justification for the risk of consorting with demons). However, making them too powerful may end up ruling out some magi-tech applications I want (like access to strong cryptography), so I'm trying to figure out what the maximum level of hypercomputation is that I can give to the demons without breaking the setting.