Can Bob prove that Alice have a key which encrypts C into A?

Question

Alice has a ciphertext $A$, its AES key $B$, and decrypted plaintext of $A$, let's call it $C$.
Alice sends $A$ and $C$ to Bob.
Bob wants to prove $C$ is just decrypted $A$, and has not been tampered with.

Can Bob achieve this without knowing the key $B$?

Answer 1

You do not really specify what your encryption scheme is. "AES" is a block-cipher, that requires a secure mode of operation to be turned into an actual secure encryption scheme.

But I will assume in the following that you are referring to some encryption scheme based on AES that is at least considered CPA secure. (e.g. AES-CBC or AES-CTR). In that case:

No, being able to do so would break CPA security of the encryption scheme.

To see why, consider the following. We have a symmetric encryption scheme $(\mathsf{Enc},\mathsf{Dec})$. Now assume towards contradiction that there exists some efficient algorithm $\mathcal{P}$ that Bob could use to convince himself that $(c,m)$ is a pair of ciphertext and plaintext such that $m = \mathsf{Dec}(k,c)$ with an unknown but fixed key $k$. I.e., let's say it holds that $$\Pr[\mathcal{P}(m,c) = 1\vert m = \mathsf{Dec}(k,c)] \ge 2/3$$ $$\Pr[\mathcal{P}(m',c) = 1\vert m' \neq \mathsf{Dec}(k,c)] \le 1/3$$

Then this algorithm trivially allows us to break CPA security. The attacker $\mathcal{A}(1^n)$ outputs two random messages $m_0,m_1$ and receives the challenge ciphertext $c^*$. $\mathcal{A}$ then simply outputs $\mathcal{P}(m_1,c^*)$. If $c^*$ is an encryption of $m_0$ then $\mathcal{A}$ outputs $0$ with probability at least $2/3$. Likewise if $c^*$ is an encryption of $m_1$ then $\mathcal{A}$ outputs $1$ with probability at least $2/3$. Therefore overall $\mathcal{A}$ can distinguish ciphertexts of $m_0$ and $m_1$ with probability $2/3$ and thus significantly better than random chance.

What is however possible is for Alice to prove to Bob that she knows a key $k$ such that $m = \mathsf{Dec}(k,c)$ without revealing $k$.