Can we prove possession of an AES-256 key without showing it? Imagine this situation:


Alice has an AES256GCM key $K$, a plaintext $X$, and $Y$ which is the ciphertext of $X$ encrypted by $K$
Bob has $X$ and $Y$
Alice and Bob can communicate with each other
Bob wants to know whether Alice holds the key which encrypts $X$ into $Y$


In this situation, Can Alice prove that she has $K$ without showing $K$?
and if so, how to do it?
Yes she can. She would do so by relying on a boolean circuit that takes $K$ as input, uses it to encrypt the plaintext $X$, compares it to $Y$, and outputs $1$ if and only if the comparison succeeds. Given such a boolean circuit $C$ (that both parties can construct), Alice must prove that she knows an input $K$ to $C$ so that $C(K) = 1$.

The task of proving knowledge of a witness for a relation described by a boolean circuit (in zero-knowledge, hence without leaking any information about the witness) has been studied a lot in the cryptographic community. Several protocols exist for this task, Zkboo is one example. It has three moves, and is based on the MPC-in-the-head technique introduced in this seminal paper.

Other solutions (see also this paper and the related but somewhat different solution presented in this paper) achieve a comparable efficiency, and are based on garbled circuits: Alice will hand Bob a "garbling" of $C$, which takes as input an encoding of her witness $K$, and evaluates the circuit on $K$ in a hidden way, and outputs $C(K)$ (the details are quite technical, so I'll stick to this high level explanation unless you want a deeper overview of how it works).

EDIT: corrected the statement that Zkboo was based on garbled circuit, I had confused it with another paper, thanks to redplum for pointing this out.