Yes, it is perfectly possible to prove that a ciphertext $C$ is of the form $\mathsf{Enc}_{\mathsf{pk}}(m;r)$, where $m$ is an arbitrary plaintext, $r$ an arbitrary random coin (both secret), and $\mathsf{pk}$ is a (known) public key, without revealing anything more beyond this fact.
Proving that something is true without revealing anything more beyond this fact is the realm of zero-knowledge proof, an active area of cryptography, I encourage you to look it up.
A few remarks, though:
- Zero-knowledge proofs exists for all $\mathsf{NP}$ statements, meaning, all statements of interest. However, for generic, unstructured encryption scheme, they might be quite costly. They will typically be more efficient if the encryption scheme has some algebraic structure, which the proof can exploit.
- One has to be careful about the statement itself: for some encryption schemes, it might not be meaningful!
Let me illustrate the second point with ElGamal encryption with public key $(g,h)$ over a group $\mathbb{G}$ of order $p$: a ciphertext $C = \mathsf{Enc}_{\mathsf{pk}}(m;r)$ where $m\in\mathbb{G}$ and $r\in\mathbb{Z}_p$ is constructed as $\mathsf{Enc}_{\mathsf{pk}}(m;r) = (g^r, h^r\cdot m)$. If it is not immediately clear to you, take some time to convince yourself that every ciphertext is a valid encryption under any public key for some $(m',r')$. Indeed, pick a different public key $\mathsf{pk}' = (g',h')$: there always exists some $(m',r')$ such that $C = ((g')^{r'}, (h')^{r'}\cdot m')$. Here, $r'$ would be $r\cdot a$ where $a$ is such that $(g')^a = g$ (which exists as $g'$ is a generator) and $m'$ would be $(h')^{-r'}\cdot h^r\cdot m$.
Hence, for ElGamal, proving that a ciphertext is a valid encryption under a given public key is a vacuous proof -- it is true for all ciphertexts. Nevertheless, we can instead prove something stronger, which probably matches more closely what you had in mind: we can use a proof of knowledge.
In a standard zero-knowledge proof, the prover proves that a property holds (e.g. $C$ is a valid encryption under $\mathsf{pk}$). But in a zero-knowledge proof of knowledge (ZKPoK), the prover shows that they know some piece of information. Here, you could ask the prover to demonstrate that they know a pair $(m,r)$ such that $C = (g^r, h^r\cdot m)$. Of course, such a pair always exists -- but in general, finding this pair is infeasible (you'd need to solve a discrete log), unless this is truly the pair you used to create $C$ in the first place! So here, using a ZKPoK would guarantee that indeed, the prover used the right public key to create the ciphertext. But it really depends on your context application whether this will be exactly what you want.
For some other schemes, however, the statement "$C$ was encrypted under $\mathsf{pk}$" is not vacuous anymore, and here even a standard zero-knowledge proof would make sense, depending (always) on the concrete use case you have in mind.
Just to finish: in the concrete case of ElGamal, proving knowledge of $(m,r)$ such that $C = (C_0,C_1) = (g^r, h^r\cdot m)$ for some public $(g,h)$ is equivalent to simply proving knowledge of $r$ such that $C_0 = g^r$ (indeed, you can always define $m$ from this $r$ as $C_1/h^r$ -- that's precisely ElGamal decryption). You will find many discussion, on this site and on the web, of methods to do exactly this proof, by looking up Schnorr discrete logarithm proofs. I'll let you have a look: it's a very simple interactive way to prove, without leaking any further information, that you know the discrete logarithm of a value.
